Vector quantile regression and optimal transport, from theory to numerics

Quantile regression, introduced by Koenker and Bassett Jr (1978), has become a very popular tool for analyzing the response of the whole distribution of a dependent variable to a set of predictors. It is a far-reaching generalization of the median regression, allowing for a predition of any quantile of the distribution. We briefly recall classical quantile regression. For \(t\in \left[ 0,1\right] \), it is well-known that the t -quantile of \(\varepsilon =Y-q_{t}\left( x\right) \) given \(X=x\) minimizes the loss function \(\mathbb {E}\left[ t\varepsilon ^{+}+\left( 1-t\right) \varepsilon ^{-}|X\right] \), or equivalently \(\mathbb {E}\left[ \varepsilon ^{+}+\left( t-1\right) \varepsilon |X\right] \). As a result, if \(q_{t}\left( x\right) \) is specified under the parametric form \(q_{t}\left( x\right) =\beta _{t}^{\top } x+\alpha _{t}\), it is natural to estimate \(\alpha _{t}\) and \(\beta _{t}\) by minimizing the lossWhile the previous optimization problem estimates \(\alpha _{t}\) and \(\beta _{t}\) for pointwise values of t, if one would like to estimate the whole curve \(t\mapsto \left( \alpha _{t},\beta _{t}\right) \), one simply should construct the loss function by integrating the previous loss functions over \( t\in \left[ 0,1\right] \), and thus the curve \(t\mapsto \left( \alpha _{t},\beta _{t}\right) \) minimizesAs it is known since the original work by Koenker and Bassett, this problem has an (infinite-dimensional) linear programming formulation. Defining \( P_{t}=\left( Y-\beta _t^{\top } X-\alpha _{t}\right) ^{+}\) as the positive deviations of Y with respect to their predicted quantiles \(\beta _t^{\top } X+\alpha _{t}\), we have \(P_{t}\ge 0\) and \(\left( Y-\beta _t^{\top } X-\alpha _{t}\right) ^{-}=P_{t}-Y+\beta _t^{\top } X+\alpha _{t}\ge 0\), so the problem reformulates as¹which we will call “dual formulation” of the classical quantile regression problem². To the dual formulation corresponds a primal one (dual to the dual), which is formally obtained by a minimax formulationthushence we arrive at the primal formulationIf \(V_{t}\) and \(\left( \alpha _{t},\beta _{t}\right) \) are solutions to the above primal and dual programs, complementary slackness yields \(\mathbf {1} _{\left\{ Y>\beta _t^{\top } X+\alpha _{t}\right\} } \le V_{t}\le \mathbf {1} _{\left\{ Y\ge \beta _t^{\top } X+\alpha _{t}\right\} } \), hence if \(\left( X,Y\right) \) has a continuous distribution, then for any \(\left( \alpha ,\beta \right) \), \({\mathbb {P}}\left( Y-\beta ^{\top } X -\alpha =0\right) =0\) , and therefore one has almost surelyKoenker and Ng (2005) impose a monotonicity constraint of the estimated quantile curves. Indeed, if \(\beta _t^{\top } x+\alpha _{t}\) is the t -quantile of the conditional distribution of Y given \(X=x\), the curve \( t\mapsto \beta _t^{\top } x+\alpha _{t}\) should be nondecreasing. Hence, these authors impose a natural constraint on the dual, that is \(\beta _t^{\top } X + \alpha _{t}\ge \beta _{t^{\prime }}^{\top } X+\alpha _{t^{\prime }}\) for \(t\ge t^{\prime } \), and they incorporate this constraint into (1.1), yieldingNote that if \(t\mapsto \beta _t^{\top } x+\alpha _{t}\) is nondecreasing, then \( \mathbf {1}_{\left\{ y\ge \beta _t^{\top } x+\alpha _{t}\right\} }\) should be nonincreasing. Therefore, in that case, \(V_{t}\) should be nonincreasing in t, which allows us to impose a monotonicity constraint on the primal variable \(V_{t}\) instead of a monotonicity constraint on the dual variables \( \beta _{t}\) and \(\alpha _t\). This is precisely the problem we look at. ConsiderLet us now take a look at a sample version of this problem. Here, we observe as sample \(\left( X_{i},Y_{i}\right) \) for \(i\in \left\{ 1,...,N\right\} \). We shall discretize the probability space \(\left[ 0,1\right] \) into T points, \(t_{1}=0<t_{2}<...<t_{T}\le 1\). Let \(\overline{x}\) be the \(1\times K\) row vector whose k-th entry is \(\sum _{1\le i\le n}X_{ik}/N\). The sample analog of (1.3) isDenoting \(\mathbf {t}\) the \(T\times 1\) row matrix with entries \(t_{\tau }\), and D a \(T\times T\) matrix with ones on the main diagonal, and \(-1\) on the diagonal just below the main diagonal, and 0 elsewhere, the condition \( V_{\tau 1}\ge V_{\tau 2}\ge ...\ge V_{\tau \left( N-1\right) }\ge V_{\tau ,N}\ge 0\) reexpresses as \(V^{\top }D\ge 0\), and the program rewritesSetting \(\pi =D^{\top }V/N\), and \(U=D^{-1}1_{N}=\left( 1/T,2/T,...,1\right) \) , \(\mu =D^{\top }\left( 1_{T}-\mathbf {t}\right) =\left( 1/T,...,1/T\right) \) , and \(\nu =1_{N}/N\), one can reformulate the problem aswhich rewrites in the population asNote that this is a direct extension of the Monge-Kantorovich problem of optimal transport—in fact it boils down to it when the last constraint is absent. This should not be surprising, given the connection between optimal transport, as recalled below. In the present paper, we introduce the Regularized Vector Quantile Regression (RVQR) problem, which consists of adding an entropic regularization term in the expression (1.4), which yields, for a given data distribution \(\nu \),Due to smoothness and regularity, the regularized problem (1.5) enjoys computational and analytical properties that are missing from the original problem (1.4). In particular, the dual to (1.4) is a smooth, unconstrained problem that can be solved by computational methods. While here, unlike in the context of standard optimal transport, the Kullback-Leibler divergence projection onto the mean-independence constraint is not in closed form, we can use Nesterov’s gradient descent acceleration, which gives optimal convergence rates for first-order methods.

The present paper in part provides a survey of previous results, and in part conveys new results. In the vein of the previous papers on the topic (2016, 2017), this paper seeks to apply the optimal transport toolbox to quantile regression. In contrast with these papers, a particular focus in the present paper is to propose a regularized version of the problem as well as new computational methods. The two main new contributions of the paper are (1) a connection with shape-constrained classical regression (Sect. 4), and (2) the introduction of the regularized vector quantile regression problem (RVQR) along with a duality theorem for that problem (Sect. 6).

The paper is organized as follows. Section 2 will offer reminders on the notion of quantile; Sect. 3 will review the previous results of (Carlier et al. 2016, 2017) on the “specified” case; Sect. 4 offers a new result (theorem 4.1) on the comparison with the shape-constrained classical quantile regression; and Sect. 5 will review results on the multivariate case. Section 6 introduces RVQR and introduces results relevant for that problem, in particular a duality result in that case (theorem 6.1).

Throughout the paper, \((\Omega , {\mathcal {F}}, \mathbb {P})\) will be some fixed nonatomic space³ probability. Given a random vector Z with values in \({\mathbb {R}}^k\) defined on this space we will denote by \({\mathscr {L}}(Z)\) the law of Z, given a probability measure \( \theta \) on \({\mathbb {R}}^k\), we shall often write \(Z\sim \theta \) to express that \({\mathscr {L}}(Z)=\theta \). Independence of two random variables \(Z_1\) and \(Z_2\) will be denoted as \(Z_1 \perp \! \! \! \perp Z_2\).

Now we wish to address quantile regression in the case where neither specification nor quasi-specification can be taken for granted. In such a general situation, keeping in mind the remarks from the previous paragraphs, we can think of two natural approaches.

The first one consists in studying directly the correlation maximization with a mean-independence constraint (3.16). The second one consists in getting back to the Koenker and Bassett t by t problem (3.8) but adding as an additional global consistency constraint that \(V_t\) should be nonincreasing (which we abbreviate as \(V_t \downarrow \)) with respect to t:Our aim is to compare these two approaches (and in particular to show that the maximization problems (3.16) and (4.1) have the same value) as well as their dual formulations. Before going further, let us remark that (3.16) can directly be considered in the multivariate case, whereas the monotonicity constrained problem (4.1) makes sense only in the univariate case.

As proven in Carlier et al. (2016), (3.16) is dual towhich can be reformulated as:in the sense that⁸The existence of a solution to (4.2) is not straightforward and is established under appropriate assumptions in Carlier et al. (2017) in the multivariate case. The following result shows that there is a t-dependent reformulation of (3.16):

Let us now defineLet \((V_t)_t\) be admissible for (4.1) and setit is obvious that \((V_t)_t\) is admissible for (4.1) and by construction \({\mathbb {E}}(V_t Y)={\mathbb {E}}(V_t Y)\). Moreover, the deterministic function \((t,x,y)\mapsto v_t(x,y)\) satisfies the following conditions:and for a.e. \(t\in [0,1]\),Conversely, if \((t,x,y)\mapsto v_t(x,y)\) satisfies (4.6), (4.7 ), \(V_t:=v_t(X,Y)\) is admissible for (4.1) and \({\mathbb {E}}(V_t Y)=\int v_t(x,y) y \nu (dx, dy)\). All this proves that \(\sup \)(4.1) coincides with

In the previous proof, we have used the elementary result (proven in the “Appendix”)

We now consider the case where Y is a random vector with values in \({ \mathbb {R}}^d\) with \(d\ge 2\). The notion of quantile does not have an obvious generalization in the multivariate setting however, the various correlation maximization problems we have encountered in the previous sections still make sense (provided Y is integrable say) in dimension d and are related to optimal transport theory. The aim of this section is to briefly summarize the optimal transport approach to quantile regression introduced in Carlier et al. (2016) and further analyzed in their follow-up 2017 paper.

Quantiles computation The discrete probability \(\pi ^\varepsilon \) is an approximation (because of the regularization \(\varepsilon \)) of \({\mathscr {L}} (U,X,Y)\) where U solves (5.9). The corresponding approximate quantile \(Q^\varepsilon _X(U)\) is given by \({\mathbb {E}}_{\pi ^\varepsilon } [Y|X,U]\). In the above discrete setting, this yields

Empirical illustrations We demonstrate the use of this approach on a series of health related experiments. We use the “ANSUR II” dataset (Anthropometric Survey of US Army Personnel), which can be found online¹⁶. This dataset is one of the most comprehensive publicly available data sets on body size and shape, containing 93 measurements for over 4,082 male adult US military personnel. It allows us to easily build multivariate dependent variables.

One-dimensional VQR We start by one-dimensional dependent variables (\(d=1\)), namely Weight (\(Y_1\)) and Thigh circumference (\(Y_2\)), explained by \(X=\)(1, Height), to allow for comparison with classical quantile regression of Koenker and Bassett Jr (1978). Figure 1 displays results of our method compared to the classical approach, for different height quantiles (10%, 30%, 60%, 90%). Figure 1 is computed with a “soft” potential \(\varphi \) while Table 1 depicts the difference with its “hard” counterpart (see the beginning of Sect. 6.2). Figure 2 and Table 2 detail the impact of regularization strength on these quantiles.

Multi-dimensional VQR In contrast, multivariate quantile regression explains the joint dependence \(Y=(Y_1,Y_2)\) by \(X=\)(1,Height). Figures 4 and 5 (each corresponding to an explained component, either \(Y_1\) or \(Y_2\)) depict how smoothing operates in higher dimension for different Height quantiles (10%, 50% and 90%), compared to a previous unregularized approach Carlier et al. (2016). Figure 3 details computational times in 2D using an Intel(R) Core(TM) i7-7500U CPU 2.70GHz.