Sharp Oracle Inequalities Under Curvature

Why Curvature Can Preserve a Sharp Comparison

A basic inequality for a penalized empirical risk minimizer compares its empirical objective with that of any candidate predictor. Turning this comparison into a population-risk bound requires controlling the random difference between empirical and population risks. A direct bound on that fluctuation can leave a term proportional to the comparator’s risk; absorbing that term may then inflate the comparator coefficient.

Curvature offers a more targeted route. When population risk grows at least quadratically away from a point, a stochastic fluctuation that grows at most linearly with distance can be controlled by a quadratic term, plus a remainder. In a pairwise comparison, this lets us absorb part of the risk difference on the left while leaving the comparator’s population risk itself untouched.

Setup and Curvature

Let \(\Theta\) be a convex subset of a finite-dimensional inner-product space. Write \(R(\theta)\) for population risk and \(R_n(\theta)\) for empirical risk, and define the empirical deviation \(\Delta(\theta)=R_n(\theta)-R(\theta)\). A nonnegative penalty is denoted by \(\operatorname{pen}(\theta)\). Assume the penalized empirical risk minimizer \(\hat\theta\) exists, so that \(R_n(\hat\theta)+\operatorname{pen}(\hat\theta)\le R_n(\theta)+\operatorname{pen}(\theta)\) for every \(\theta\in\Theta\).

Use the norm \(\|\cdot\|\) to measure distances and its dual norm \(\|\cdot\|_*\) for gradients. The key stochastic assumption for the result below is that, on an event under consideration, the empirical deviation has a Lipschitz pairwise contrast: \(|\Delta(\theta)-\Delta(\eta)|\le Z\|\theta-\eta\|\) for all \(\theta,\eta\in\Theta\), for some \(Z\ge0\). This is a simultaneous condition, not merely a bound at one fixed candidate. In applications, \(Z\) is controlled probabilistically; here the result is deterministic on any event where the condition holds.

Absorbing a Pairwise Stochastic Contrast

For a comparator \(\theta\), write \(G_\theta=\|\nabla R(\theta)\|_*\). The gradient term in the strong-convexity inequality is important: curvature alone does not imply that risk increases quadratically from every comparator. The remainder below accounts for the comparator’s gradient.

Proof. Put \(t=\|\eta-\theta\|\) and \(D=R(\eta)-R(\theta)\). Strong convexity and the dual-norm inequality give \(D\ge -G_\theta t+\frac{\kappa}{2}t^2\). The deviation assumption gives \(\Delta(\theta)-\Delta(\eta)\le Zt\). If \(D\ge0\), then \[ Zt-\rho D \le (Z+\rho G_\theta)t-\frac{\rho\kappa}{2}t^2 \le \frac{(Z+\rho G_\theta)^2}{2\rho\kappa}. \] The final inequality follows by maximizing the quadratic expression over \(t\ge0\): its maximum is attained at \(t=(Z+\rho G_\theta)/(\rho\kappa)\). If \(D<0\), the lower bound on \(D\) implies \(0>D\ge t(\frac{\kappa}{2}t-G_\theta)\), so \(t<2G_\theta/\kappa\) when \(t>0\). Therefore \(Zt\le 2ZG_\theta/\kappa\); when \(t=0\), the same bound holds directly. These two cases prove the lemma. \(\square\)

Sharp Oracle Inequality

Proof. The minimizing property gives the basic inequality \(R_n(\hat\theta)+\operatorname{pen}(\hat\theta)\le R_n(\theta)+\operatorname{pen}(\theta)\). Substitute \(R_n=R+\Delta\) and rearrange: \[ R(\hat\theta)-R(\theta) \le \operatorname{pen}(\theta)-\operatorname{pen}(\hat\theta) +\Delta(\theta)-\Delta(\hat\theta). \] Apply the lemma to the pair \((\theta,\hat\theta)\), and use nonnegativity of the penalty: \[ D\le \operatorname{pen}(\theta)+r_\rho(\theta)+\rho D_+, \qquad D=R(\hat\theta)-R(\theta). \] If \(D>0\), then \((1-\rho)D\le\operatorname{pen}(\theta)+r_\rho(\theta)\). If \(D\le0\), the asserted upper bound on \(D\) also holds, since its right-hand side is nonnegative. Thus in either case \(D\le[\operatorname{pen}(\theta)+r_\rho(\theta)]/(1-\rho)\). Adding \(R(\theta)\) proves the first inequality. Since it holds for every comparator, taking the infimum proves the second. \(\square\)

This is a sharp comparison in the specific sense that no factor greater than one multiplies \(R(\theta)\). The penalty and the curvature remainder are multiplied by \(1/(1-\rho)\); the comparator risk is not. The remainder depends on the stochastic scale, the curvature, and the comparator’s gradient. A small \(\rho\) reduces the inflation of that remainder but increases its first term, so \(\rho\) represents a genuine trade-off.

Why the Leading Constant Matters

Population risk may contain a large baseline that is unrelated to the size of the estimation error. Consider \(R(\theta)=10+\frac12\theta^2\) and \(R_n(\theta)=R(\theta)-0.1\theta\) on \([-1,1]\), with no penalty. The empirical minimizer is \(\hat\theta=0.1\), and the comparator \(\theta=0\) has risk \(10\). Here \(\kappa=1\), \(Z=0.1\), \(G_0=0\), and, with \(\rho=0.5\), \(r_\rho(0)=0.01\). The theorem gives \(R(\hat\theta)\le 10+0.01/0.5=10.02\); the exact risk is \(10.005\). The baseline 10 appears once, not multiplied by a constant larger than one.

A common mistake is to first derive an inequality for excess risk, divide by a factor smaller than one to absorb a stochastic term, and then report a sharp bound on population risk. For example, an inequality of the form \((1-\rho)R(\hat\theta)\le R(\theta)+a\) would imply \(R(\hat\theta)\le [R(\theta)+a]/(1-\rho)\), which does inflate the comparator coefficient. The correction is to work with the pairwise difference \(D=R(\hat\theta)-R(\theta)\), control only its positive part, and absorb \(\rho D\) when \(D>0\). The theorem’s proof follows exactly this logic.

The assumptions also matter. Curvature does not itself give a bound on empirical fluctuations; the pairwise deviation condition supplies that separate control. Nor does curvature imply a quadratic increase from every comparator without accounting for its gradient. The \(G_\theta\)-dependent remainder makes this dependence explicit. In applications, one must verify the curvature and stochastic-deviation conditions on the same event before using the oracle inequality.