Nonsmooth M-Estimation with Quantile Loss

Why Quantile Loss Requires Subgradients

Means arise naturally from squared-error loss, while quantiles arise from an asymmetric absolute-error loss. The absolute value has a corner at zero, so ordinary differentiation does not describe what happens when a residual is zero. Subgradients handle that corner exactly; they also make it possible to establish the large-sample behavior of sample quantiles and quantile regression.

Fix a quantile level $0<\tau<1$. The parameter of interest may be a scalar quantile $q$, or a vector of regression coefficients $\beta$. In both cases, the loss is convex but generally not differentiable everywhere. The correct first-order condition is therefore that zero belong to a subgradient, rather than that an ordinary derivative equal zero.

Definition: The quantile check loss is $$ \rho_\tau(u)=u\bigl(\tau-\mathbf{1}\{u<0\}\bigr) = \begin{cases} \tau u, & u\geq 0,\\ (\tau-1)u, & u<0. \end{cases} $$ For a residual $u$, its subgradient with respect to $u$ is $\tau$ if $u>0$, $\tau-1$ if $u<0$, and the interval $[\tau-1,\tau]$ if $u=0$. A subgradient is a slope that supports a convex function at a point; at a corner there can be an interval of such slopes.

For a scalar candidate quantile $q$, the residual is $Y_i-q$, so the objective is $\sum_{i=1}^n\rho_\tau(Y_i-q)$. The subgradient with respect to $q$ has the opposite sign from the subgradient with respect to the residual. A residual above zero contributes $-\tau$; one below zero contributes $1-\tau$; and a zero residual contributes any value in $[-\tau,1-\tau]$.

Sample Quantiles: The Exact Subgradient Condition

The sample quantile objective is convex in $q$. For a convex function, a point minimizes the function if and only if zero is in its subgradient there. Let $L(q)$ be the number of observations strictly below $q$, and $G(q)$ the number strictly above $q$. Observations tied at $q$ contribute intervals, not a single derivative.

Theorem: A value $q$ minimizes $\sum_{i=1}^n\rho_\tau(Y_i-q)$ if and only if $$ L(q)\leq n\tau \qquad\text{and}\qquad G(q)\leq n(1-\tau). $$ These inequalities use strict counts: observations equal to $q$ are counted in neither $L(q)$ nor $G(q)$.

To prove the characterization, each observation below $q$ contributes $1-\tau$ to the subgradient with respect to $q$, while each observation above $q$ contributes $-\tau$. If there are $E(q)$ ties, each tie contributes an interval $[-\tau,1-\tau]$. The total subgradient is therefore the interval

\left[(1-\tau)L(q)-\tau\{G(q)+E(q)\},\ (1-\tau)\{L(q)+E(q)\}-\tau G(q)\right].

Its lower endpoint is at most zero exactly when $(1-\tau)L(q)\leq \tau(n-L(q))$, or $L(q)\leq n\tau$. Its upper endpoint is at least zero exactly when $(1-\tau)(n-G(q))\geq \tau G(q)$, or $G(q)\leq n(1-\tau)$. Thus zero belongs to the subgradient precisely under the two stated inequalities, proving the result. Convexity makes this condition both necessary and sufficient. $\square$

Worked Example: Ties and an Interval of Sample Quantiles

Take observations $1,2,4,7$ and $\tau=0.75$. Determine the minimizers of the check-loss objective, paying particular attention to the endpoints.

For $4<q<7$, three observations are strictly below $q$ and one is strictly above it. Hence $L(q)=3\leq 4(0.75)=3$ and $G(q)=1\leq 4(0.25)=1$; every such $q$ minimizes the objective. At $q=4$, there are two strictly below, one strictly above, and one tied observation. Thus $L(4)=2$ and $G(4)=1$, and the condition also holds. At $q=7$, $L(7)=3$ and $G(7)=0$, so this endpoint also minimizes. Values below 4 or above 7 violate one of the two inequalities. The full minimizing set is therefore $[4,7]$.

The objective confirms the result. At $q=4$, the losses are $0.25(3)=0.75$, $0.25(2)=0.5$, $0$, and $0.75(3)=2.25$, totaling $3.5$. At $q=7$, the losses are $0.25(6)=1.5$, $0.25(5)=1.25$, $0.25(3)=0.75$, and $0$, again totaling $3.5$. For $4\leq q\leq7$, the slope of the objective is $3(0.25)-0.75=0$ away from the endpoints, so its value stays constant there.

At $q=4$, three observations are at or below $q$, and two are at or above it; these inclusive counts do not replace the strict counts in the theorem. The tied observation supplies the subgradient interval needed for zero to belong to the total subgradient.

Asymptotic Normality of a Sample Quantile

Let $Y_1,\ldots,Y_n$ be independent and identically distributed with distribution function $F$. Define the population quantile by $q_\tau=\inf\{y:F(y)\geq\tau\}$. Assume that $F(q_\tau)=\tau$, that $F$ is differentiable in a neighborhood of $q_\tau$, and that its density $f$ is continuous there with $f(q_\tau)>0$. These conditions make the target locally unique and ensure that probability changes at a positive rate near it.

Theorem: Let $\hat q_\tau$ be a sample quantile minimizing $\sum_i\rho_\tau(Y_i-q)$, for example the order statistic $Y_{(\lceil n\tau\rceil)}$. Under the conditions above, $$ \sqrt{n}(\hat q_\tau-q_\tau) \xrightarrow{d} N\left(0,\frac{\tau(1-\tau)}{f(q_\tau)^2}\right). $$

Here is the derivation. Write $F_n$ for the empirical distribution function. With probability one there are no ties in a neighborhood of $q_\tau$, since $F$ has a density there. For the stated order-statistic choice, on the event that $\hat q_\tau$ lies in the neighborhood of $q_\tau$ where $F$ is continuous, there are almost surely no ties at $\hat q_\tau$, so $F_n(\hat q_\tau)=\lceil n\tau\rceil/n=\tau+O(n^{-1})$; this event has probability tending to one by the consistency argument below. First, $\hat q_\tau$ is within order $n^{-1/2}$ of $q_\tau$ in probability. To see this, compare $F_n$ at $q_\tau\pm M/\sqrt n$ with $\tau$. Differentiability gives $F(q_\tau\pm M/\sqrt n)=\tau\pm f(q_\tau)M/\sqrt n+o(n^{-1/2})$. The variance of each empirical proportion is at most $1/(4n)$; Chebyshev's inequality then bounds the probability of crossing the wrong side by a constant times $M^{-2}$, for large $n$. Letting $M$ increase establishes $\hat q_\tau-q_\tau=O_p(n^{-1/2})$.

On any fixed interval of radius $M/\sqrt n$ around $q_\tau$, the probability mass is $O(n^{-1/2})$. The empirical-process maximal inequality for intervals gives $$ \sup_{|t-q_\tau|\leq M/\sqrt n} \left|(F_n-F)(t)-(F_n-F)(q_\tau)\right|=o_p(n^{-1/2}). $$ Indeed, the expected supremum of the centered increments is bounded by a constant times the square root of the interval probability divided by $n$, which is $O(n^{-3/4})$; the bound is $o(n^{-1/2})$. Combining this fact with the order-statistic identity and the differentiability expansion of $F$ yields $$ 0=F_n(\hat q_\tau)-\tau =F_n(q_\tau)-\tau+f(q_\tau)(\hat q_\tau-q_\tau)+o_p(n^{-1/2}). $$ Consequently, $$ \sqrt n(\hat q_\tau-q_\tau) =-\frac{1}{f(q_\tau)}\frac{1}{\sqrt n} \sum_{i=1}^n\bigl(\mathbf{1}\{Y_i\leq q_\tau\}-\tau\bigr)+o_p(1). $$ The summands are independent, mean zero, and have variance $\tau(1-\tau)$. The central limit theorem and Slutsky's theorem give the claimed normal limit. $\square$

Worked Example: The Sample Median from a Uniform Distribution

Suppose $Y_i$ are independent and uniformly distributed on $[-2,2]$, and estimate the population median. Symmetry gives $q_{0.5}=0$. The density is $f(y)=1/4$ in the interior of this interval, so $f(0)=1/4>0$.

The asymptotic variance for the square-root-$n$ scaled median is $$ \frac{0.5(1-0.5)}{(1/4)^2} =\frac{1/4}{1/16}=4. $$ Thus $\sqrt n(\hat q_{0.5}-0)$ converges in distribution to $N(0,4)$. Equivalently, for large $n$, the median is approximately $N(0,4/n)$. The calculation uses the density at the target; it is not the variance of the original uniform observations.

Quantile Regression as a Nonsmooth M-Estimator

In quantile regression, observations have covariate vectors $X_i$, and the fitted conditional quantile is $X_i^\top\beta$. The estimator minimizes $\sum_i\rho_\tau(Y_i-X_i^\top\beta)$. Define $\psi_\tau(u)=\tau-\mathbf{1}\{u<0\}$ when $u\ne0$; at zero, use the subgradient interval $[\tau-1,\tau]$. A necessary and sufficient condition for a global minimizer is $$ 0\in-\sum_{i=1}^n X_i\,\partial\rho_\tau(Y_i-X_i^\top\beta), $$ where the set on the right consists of all sums formed by choosing an allowed subgradient for each residual. Sufficiency follows from convexity; necessity is the convex first-order condition.

Worked Example: Verifying a Median Regression Fit

Consider four observations with intercept-and-slope covariates $X=(1,x)^\top$: two at $x=-1$ with responses $-2,0$, and two at $x=1$ with responses $0,2$. At $\tau=0.5$, check whether $\hat\beta=(0,1)^\top$ minimizes the objective.

The fitted values are $-1$ at $x=-1$ and $1$ at $x=1$. The residuals are therefore $-1,1,-1,1$. For $\tau=0.5$, $\psi_\tau(-1)=-0.5$ and $\psi_\tau(1)=0.5$. At $x=-1$, the two score contributions sum to $(1,-1)^\top(-0.5)+(1,-1)^\top(0.5)=(0,0)^\top$. At $x=1$, they sum to $(1,1)^\top(-0.5)+(1,1)^\top(0.5)=(0,0)^\top$. Thus zero is a subgradient of the objective at $\hat\beta$, so convexity proves it is a minimizer. Its objective value is $0.5+0.5+0.5+0.5=2$.

A standard asymptotic result makes the role of the density and covariate design explicit. Suppose $(Y_i,X_i)$ are independent and identically distributed, the conditional $\tau$-quantile satisfies $Q_\tau(Y\mid X)=X^\top\beta_0$, and the conditional error $\varepsilon=Y-X^\top\beta_0$ has a density $f_{\varepsilon\mid X}(0\mid X)$ that is positive at zero. Assume finite moments sufficient for the score central limit theorem and a uniform local density bound sufficient for the objective expansion; also assume the matrices below exist and $A$ is positive definite. Then $$ A=E\!\left[f_{\varepsilon\mid X}(0\mid X)XX^\top\right], \qquad B=\tau(1-\tau)E[XX^\top]. $$

Theorem: Under these conditions, a consistent quantile regression minimizer satisfies $$ \sqrt n(\hat\beta-\beta_0)\xrightarrow{d} N\left(0,A^{-1}BA^{-1}\right). $$

For the derivation, write $\varepsilon_i=Y_i-X_i^\top\beta_0$ and compare the objective at $\beta_0+h/\sqrt n$ with its value at $\beta_0$. Knight's identity for check loss is $$ \rho_\tau(u-v)-\rho_\tau(u) =-v\psi_\tau(u)+\int_0^v\left\{\mathbf{1}(u\leq s)-\mathbf{1}(u\leq0)\right\}\,ds. $$ The identity follows by evaluating both sides on either side of the kink at zero; at the kink it holds with the corresponding one-sided values. Summing with $u=\varepsilon_i$, $v=X_i^\top h/\sqrt n$, the linear term is $-h^\top n^{-1/2}\sum_iX_i\psi_\tau(\varepsilon_i)$. Its summands have mean zero by the conditional quantile restriction and covariance matrix $B$. The conditional density expansion at zero makes the expectation of each integral term equal to $\tfrac12 f_{\varepsilon\mid X}(0\mid X)(X^\top h)^2/n+o(n^{-1})$. The stated moment and local-bound conditions justify averaging this expansion, giving the quadratic term $\tfrac12h^\top Ah+o_p(1)$, uniformly for bounded $h$. The multivariate central limit theorem gives a Gaussian limit for the linear term. Minimizing the resulting strictly convex quadratic approximation gives $h=A^{-1}Z$, where $Z$ has covariance $B$; hence the covariance is $A^{-1}BA^{-1}$, as asserted. $\square$

Worked Example: A Symmetric Logistic Regression Error Model

Suppose the conditional median model has an intercept and a covariate $x$ taking values $-1$ and $1$ with equal probability. Let the errors have a standard logistic distribution, independently of $x$. Its density at zero is $1/4$, and $\tau=0.5$.

With $X=(1,x)^\top$, equal probabilities give $E[XX^\top]=I_2$: the diagonal entries are one and the off-diagonal entry is $E[x]=0$. Therefore $A=(1/4)I_2$ and $B=(1/4)I_2$. The asymptotic covariance is $$ A^{-1}BA^{-1}=4I_2. $$ So each coefficient has square-root-$n$ limiting variance 4, and their limiting covariance is zero in this balanced design. The positive conditional density supplies curvature in the expected objective, while the covariate variation makes both coefficients identifiable.

Common Mistake and Why the Conditions Matter

A tempting but incorrect argument is: “Differentiate the loss, set the derivative to zero, and apply a smooth M-estimator theorem.” At a zero residual the derivative does not exist, and ignoring that observation can incorrectly exclude minimizers at data points or at endpoints of a minimizing interval. The correction is to use the full subgradient interval and impose the condition that zero belongs to the total subgradient.

The positive-density condition is also substantive. If the density vanishes at the target or the distribution has an atom there, the local change in probability need not be linear with a positive slope. The square-root-$n$ normal limit derived above may then fail or require a different scaling and argument. In regression, a singular $A$ similarly prevents the stated inverse and signals that the local quadratic approximation does not identify every coefficient.

Check Your Understanding

Use the subgradient conditions and asymptotic results to check your understanding.

For $\tau=0.25$, what two strict-count inequalities characterize a minimizer of the sample quantile objective?
Why can an observation equal to $q$ not simply be assigned the derivative from only one side when checking whether $q$ minimizes quantile loss?
If $f(q_\tau)$ is halved while $\tau$ is fixed, how does the asymptotic variance of the sample quantile change?
In quantile regression, what roles do $A$ and $B$ play in the limiting covariance?
Why does a zero subgradient establish a global minimum for the quantile regression objective?