Optimal Excess Risk Bounds for Empirical Risk Minimization on $p$-Norm Linear Regression

To state our results, we will need to define two types of quantities first. The first kind are related to norms and their equivalence constants, which we will use in the analysis of the non-realizable case. The second are small ball probabilities, which we will use in the analysis of the realizable case.

We start by introducing the following functions on our space of coefficients $\mathbb{R}^{d}$. For $p,q\in[1,\infty)$, define, with the convention $\infty^{1/p}\vcentcolon=\infty$ for all $p\in[1,\infty)$,

As suggested by the notation, under appropriate moment assumptions on $X$, these functions are indeed norms on $\mathbb{R}^{d}$. In that case, we will be interested in norm equivalence constants between them

where $a$ and $b$ stand for one of $L^{p}$ or $(L^{q},p)$. Let us note that since we work in a finite dimensional vector space, all norms are equivalent, so that as soon as the quantities defined in (2) are indeed norms, the constants defined in (3) are finite. Furthermore, as suggested by the notation, $\sigma^{2}_{p}$ may be viewed as the maximum second moment of the random variables $\lVert w\rVert_{\nabla^{2}\ell_{p}(\langle w_{p}^{*},X\rangle-Y)}^{2}$ over the unit sphere of $\lVert\cdot\rVert_{L^{2},p}$. Finally, we record the following identities for future use

The first identity holds by linearity, and the second by noticing that $\nabla^{2}\ell_{2}(\langle w,X\rangle-Y)=XX^{T}$.

We now turn to small ball probabilities. We define the following functions on $\mathbb{R}^{d}$, for $q\in[1,\infty)$,

Assumptions on the functions $\rho_{0}$ and $\rho_{2}$ have been used extensively in the recent literature, see e.g. [Men14, KM15, LM17, LM17a, Men18, LM18, Mou22]. In particular, a standard assumption postulates the existence of strictly positive constants $\beta_{0}$, and $(\beta_{2},\kappa_{2})$ such that $\rho_{0}(w)\leq 1-\beta_{0}$ and $\rho_{2}(w,\kappa_{2})\geq\beta_{2}$ for all $w\in\mathbb{R}^{d}$. Conditions of this type are usually referred to as small ball conditions. Efforts have been made to understand when these conditions hold [Men14, RV15, LM17a] as well as reveal the dimension dependence of the constants with which they do [Sau18]. Here we prove that such conditions always hold for finite dimensional spaces. We leave the proof of Lemma 1 to Appendix B to not distract from our main development.

To better contextualize our results, we start by stating the best known high probability bound on ERM for the square loss, which we deduce from [Oli16] and [LM16].

Up to a constant factor and the dependence on $\delta$, Theorem 1 recovers the asymptotically exact rate (1). Let us briefly comment on the differences between Theorem 1 and the comparable statements in the original papers. First, the finiteness of $\sigma_{2}^{2}$ is deduced from the finiteness of the fourth moments of the components of $X$, instead of being assumed as in [Oli16] (see the discussion in Section 3.1 in [Oli16]). Second we combine Theorem 3.1 from [Oli16] with the proof technique of [LM16] to achieve a slightly better bound that the one achieved by the proof technique used in the proof of Theorem 4.2 in [Oli16], while avoiding the dependence on the small ball-constant present in the bound of Theorem 1.3 in [LM16], which is known to incur additional dimension dependence in some cases [Sau18].

We now move to the realizable case, where $Y=\langle w^{*},X\rangle$ so that $w_{p}^{*}=w^{*}$ for all $p\in(1,\infty)$. We immediately note that Theorem 1 is still applicable in this case, and ensures that we recover $w^{*}$ exactly with no more than $n=O(\sigma_{2}^{2}d)$ samples. However, we can do much better, while getting rid of all the moment assumptions in Theorem 1. Indeed, it is not hard to see that $\hat{w}_{p}\neq w^{*}$ only if for some $w\in\mathbb{R}^{d}\setminus\{0\}$, $\langle w,X_{i}\rangle=0$ for all $i\in[n]$ (taking $w=\hat{w}_{p}-w_{p}^{*}$ works). The implicit argument in Theorem 1 then uses the pointwise bound (see Lemma B.2 in [Oli16])

and uniformizes it over the $L^{2}$ unit sphere in $\mathbb{R}^{d}$, where the $L^{2}$ norm is as defined in (2). However, we can use the much tighter bound $\rho^{n}$ where $\rho$ is as defined in Lemma 1. To the best of our knowledge, the realizable case has not been studied explicitly before in the literature. However, with the above considerations in mind, we can deduce the following result from [LM17a], which uniformizes the pointwise bound we just discussed using a VC dimension argument.

We are now in position to state our main results. As discussed in Section 1, the $\ell_{p}(t)$ losses have degenerate second derivatives as $t\to 0$. When the problem is realizable, the risk is not twice differentiable at its minimizer for the cases $p\in(1,2)$, and is degenerate for the cases $p\in(2,\infty)$. If we want bounds of the form (1), we must exclude this case from our analysis. Our first main result is a strengthening of Theorem 2, and relies on a combinatorial argument to uniformize the pointwise estimate discussed in Section 2.2.

Comparing Theorem 2 and Theorem 3, we see that the bound on the number of samples required to reach a confidence level $\delta$ in Theorem 3 is uniformly smaller than the one in Theorem 2. The proof of Theorem 3 can be found in Appendix C.

We now move to the more common non-realizable case. Our first theorem here gives a non-asymptotic bound for the excess risk of ERM under a $p$-th power loss for $p\in(2,\infty)$. To the best of our knowledge, no such result is known in the literature.

Up to a constant factor that depends only on $p$ and the dependence on $\delta$, the bound of Theorem 4 is precisely of the form of the optimal bound (1). Indeed, as $p>2$, the second term is $o(1/n)$. At the level of assumptions, the finiteness of the $p$-th moment of $Y$ and the components of $X$ is necessary to ensure that the risk $R_{p}$ is finite for all $w\in\mathbb{R}^{d}$. The last assumption $\operatorname{E}[\lvert Y-\langle w_{p}^{*},X\rangle\rvert^{2(p-2)}(X^{j})^{4}]<\infty$ is a natural extension of the fourth moment assumption in Theorem 1. In fact, all three assumptions in Theorem 4 reduce to those of Theorem 1 as $p\to 2$. It is worth noting that the constant $c_{p}$ has the alternative expression $\sup_{w\in\mathbb{R}^{d}\setminus\{0\}}\{\lVert w\rVert_{L^{p}}/\lVert w\rVert_{H_{p}}\}$ by (4), i.e. it is the norm equivalence constant between the $L^{p}$ norm and the norm induced by $H_{p}$. Using again (4), we see that $c_{p}\to 1$ as $p\to 2$. As $p\to\infty$, $c_{p}$ grows, and we suspect in a dimension dependent way. However, this does not affect the asymptotic optimality of our rate as $c_{p}$ only enters an $o(1/n)$ term in our bound.

We now turn to the case of $p\in(1,2)$ where we need a slightly stronger version of non-realizability.

Just like the bounds of Theorems 1 and 4, the bound of Theorem 5 is asymptotically optimal up to a constant factor that depends only on $p$. Indeed, since $1<p<2$, $1/(p-1)>1$, and the second term is $o(1/n)$. At the level of assumptions, we have two additional conditions compared to Theorem 4. First, we require the existence of the second moment of the covariates instead of just the $p$-th moment. Second, we require a stronger version of non-realizability by assuming the existence of the $2(2-p)$ negative moment of $\lvert\langle w_{p}^{*},X\rangle-Y\rvert$. In the majority of applications, an intercept variable is included as a covariate, i.e. $X^{1}=1$, so that this negative moment assumption is already implied by the standard assumption $\operatorname{E}[\lvert Y-\langle w_{p}^{*},X\rangle\rvert^{2(p-2)}(X^{j})^{4}]<\infty$. In the rare case where an intercept variable is not included, any negative moment assumption on $\lvert\langle w_{p}^{*},X\rangle-Y\rvert$ can be used instead, at the cost of a larger factor in the $o(1/n)$ term.

Finally, it is worth noting that for the cases $p\in[1,2)$, there are situations where the asymptotic bound (1) does not hold, as the limiting distribution of the coefficients $\hat{w}_{p}$ as $n\to\infty$ does not necessarily converge to a Gaussian, and depends heavily on the distribution of $\langle w_{p}^{*},X\rangle-Y$, see e.g. [LL05] and [Kni98]. Overall, we suspect that perhaps a slightly weaker version of our assumptions is necessary for a fast rate like (1) to hold.

Here we give a detailed proof of Theorem 1. While the core technical result can be deduced by combining results from [Oli16] and [LM16], here we frame the proof in a way that makes it easy to extend to the cases $p\in(1,\infty)$, and differently from either paper. We split the proof in three steps. First notice that since the loss is a quadratic function of $w$, we can express it exactly using a second order Taylor expansion around the minimizer $w_{2}^{*}$

Taking empirical averages and expectations of both sides respectively shows that the excess empirical risk and excess risk also admit such an expansion

where in the second equality we used that the gradient of the risk vanishes at the minimizer $w_{2}^{*}$. Therefore, to bound the excess risk, it is sufficient to bound the norm $\lVert w-w_{2}^{*}\rVert_{H_{2}}$. This is the goal of the second step, where we use two ideas. First, by definition, the excess empirical risk of the empirical risk minimizer satisfies the upper bound

Second, we use the Cauchy-Schwartz inequality to lower bound the excess empirical risk by

and we further lower bound it by deriving high probability bounds on the two random terms $\lVert\nabla R_{2,n}(w_{2}^{*})\rVert_{H_{2}^{-1}}$ and $\lVert\hat{w}_{2}-w_{2}^{*}\rVert_{H_{2,n}}^{2}$. The first can easily be bounded using Chebyshev’s inequality and the elementary fact that the variance of the average of $n$ i.i.d. random variables is the variance of their common distribution divided by $n$. Here we state the result for all $p\in(1,\infty)$; the straightforward proof can be found in the Appendix D.

For the second random term $\lVert\hat{w}_{2}-w_{2}^{*}\rVert_{H_{2,n}}^{2}$, we use Theorem 3.1 of [Oli16], which we restate here, emphasizing that the existence of fourth moments of the components of the random vector is enough to ensure the existence of the needed norm equivalence constant.

Using this result we can immediately deduce the required high probability lower bound on the second random term $\lVert\hat{w}_{2}-w^{*}_{2}\rVert_{H_{2,n}}^{2}$; we leave the obvious proof to Appendix D.

Combining Lemma 2, Corollary 1, and (8) yields that with probability at least $1-\delta$

Finally, combining (7) and (9) gives that with probability at least $1-\delta$

Replacing in (6) finishes the proof. ∎

The main challenge in moving from the case $p=2$ to the case $p\in(2,\infty)$ is that the second order Taylor expansion of the loss is no longer exact. The standard way to deal with this problem is to assume that the loss is upper and lower bounded by quadratic functions, i.e. that it is smooth and strongly convex. Unfortunately, as discussed in Section 1, the $\ell_{p}$ loss is not strongly convex for any $p>2$, so we need to find another way to deal with this issue. Once this has been resolved however, the strategy we used in the proof of Theorem 1 can be applied almost verbatim to yield the result. Remarkably, a result of [AKPS22] allows us to upper and lower bound the $p$-th power loss for $p\in(2,\infty)$ by its second order Taylor expansion around a point, up to some residual terms. An application of this result yields the following Lemma.

Up to constant factors that depend only on $p$ and an $L^{p}$ norm residual term, Lemma 3 gives matching upper and lower bounds on the excess risk and excess empirical risk in terms of their second order Taylor expansions around the minimizer. We can thus use the approach taken in the proof of Theorem 1 to obtain the result. The only additional challenge is the control of the term $\lVert\hat{w}_{p}-w_{p}^{*}\rVert_{L^{p}}$, which we achieve by reducing it to an ${\lVert\hat{w}_{p}-w_{p}^{*}\rVert}_{H_{p}}$ term using norm equivalence. A detailed proof of Theorem 4, including the proof of Lemma 3, can be found in Appendix E.

The most technically challenging case is when $p\in(1,2)$. Indeed as seen in the proof of Theorem 1, the most involved step is lower bounding the excess empirical risk with high probability. For the case $p\in[2,\infty)$, we achieved this by having access to a pointwise quadratic lower bound, which is not too surprising. Indeed, at small scales, we expect the second order Taylor expansion to be accurate, while at large scales, we expect the $p$-th power loss to grow at least quadratically for $p\in[2,\infty)$.

In the case of $p\in(1,2)$, we are faced with a harder problem. Indeed, as $p\to 1$, the $\ell_{p}$ losses behave almost linearly at large scales. This means that we cannot expect to obtain a global quadratic lower bound as for the case $p\in[2,\infty)$, so we will need a different proof technique. Motivated by related concerns, [BCLL18] introduced the following approximation to the $p$-th power function

for $t,x\in[0,\infty)$ and with $\gamma_{p}(0,0)=0$. This function was further studied by [AKPS19], who showed in particular that for any $t\in\mathbb{R}$, the function $x\mapsto\gamma_{p}(\lvert t\rvert,\lvert x\rvert)$ is, up to constants that depend only on $p$, equal to the gap between the function $x\mapsto\ell_{p}(t+x)$ and its linearization around $0$; see Lemma 4.5 in [AKPS19] for the precise statement. We use this result to derive the following Lemma.

As expected, while we do have the desired quadratic upper bound, the lower bound is much more cumbersome, and is only comparable to the second order Taylor expansion when $\lvert\langle w-w_{p}^{*},X_{i}\rangle\rvert\leq\lvert\langle w_{p}^{*},X_{i}\rangle-Y_{i}\rvert$. What we need for the proof to go through is a high probability lower bound of order $\Omega(\lVert w-w^{*}\rVert_{H_{p}}^{2})$ on the first term in the lower bound (12). We obtain this in the following Proposition.