Why Curvature Conditions Need to Be Distinguished
An oracle inequality typically compares the risk of a fitted predictor with the risk of a comparator. Its statistical conclusion may be an upper bound on excess risk, such as \(R(\hat\theta)-R(\theta^*)\). Curvature conditions describe how that excess risk changes as the fitted object moves away from an optimum. They are not interchangeable: one may control distance between parameters, another distance between predictions, and an error bound may relate a gradient residual to distance or risk.
This distinction matters when interpreting a rate. If a risk bound is of order \(n^{-1/2}\), a quadratic lower bound on risk in a relevant distance can turn it into a distance bound of order \(n^{-1/4}\). That conversion does not itself improve the risk bound to order \(n^{-1}\). Obtaining a faster statistical risk rate requires additional control of the stochastic deviations; curvature describes what can be deduced once such a risk bound is available.
Three Conditions and What They Measure
Let \(R:\mathbb R^d\to\mathbb R\) be a finite risk function with a minimizer \(\theta^*\), and write \(R^* = R(\theta^*)\) and \(\Theta^*=\{\theta:R(\theta)=R^*\}\). For a set \(A\), \(\operatorname{dist}(\theta,A)=\inf_{a\in A}\|\theta-a\|_2\). The parameter norm is shown explicitly here; other norms can be used if stated.
Strong convexity is a two-point condition: it lower-bounds the function by a quadratic everywhere between any pair of points. Quadratic growth is a one-point comparison with the minimum value. It directly says that excess risk cannot be small while the parameter is far from the solution set. A gradient error bound instead says that a small gradient forces proximity to a minimizer. The latter concerns a first-order residual, not excess risk itself.
For a prediction rule \(g_\theta\), define its prediction distance from \(g_{\theta^*}\) by \(d_{\mathrm{pred}}(\theta,\theta^*)=\{E[(g_\theta(X)-g_{\theta^*}(X))^2]\}^{1/2}\), when this expectation is finite. A quadratic lower bound in this distance controls prediction error. It controls parameter error only if the model also distinguishes parameters, for example through a lower bound relating prediction distance to parameter distance.
Worked Example: Least-Squares Risk and Identifiable Parameters
Suppose \(Y=X^\top\theta^*+\varepsilon\), \(E[\varepsilon\mid X]=0\), \(E[\varepsilon^2]<\infty\), and \(E[\|X\|_2^2]<\infty\). Let \(R(\theta)=\frac12 E[(Y-X^\top\theta)^2]\), and let \(\Sigma=E[XX^\top]\). Set \(h=\theta-\theta^*\). The finite second moments ensure the risks and cross term below are finite. Expanding the square and using the conditional-mean assumption gives $$ R(\theta)-R(\theta^*)= \frac12 E[(\varepsilon-X^\top h)^2-\varepsilon^2] =\frac12 h^\top\Sigma h-E[\varepsilon X^\top h] =\frac12 h^\top\Sigma h. $$
If \(\Sigma\) has smallest eigenvalue \(\lambda_{\min}>0\), then \(h^\top\Sigma h\ge\lambda_{\min}\|h\|_2^2\). Thus the risk is strongly convex with constant \(\lambda_{\min}\), and an excess-risk bound \(\Delta\) implies \(\|\theta-\theta^*\|_2\le\sqrt{2\Delta/\lambda_{\min}}\). The same identity says the excess risk is exactly half the squared prediction distance, since \(E[(X^\top h)^2]=h^\top\Sigma h\). Here both parameter and prediction errors are controlled because the design is identifiable.
Strong Convexity Implies Quadratic Growth
For a differentiable convex risk, strong convexity gives quadratic growth even when the minimizer is on the boundary of the domain. At a constrained minimizer, one should not simply assume that the gradient is zero. The needed first-order fact is that \(\nabla R(\theta^*)^\top(\theta-\theta^*)\ge0\) for every feasible \(\theta\): the directional derivative from \(\theta^*\) toward any feasible point cannot be negative.
Proof. For any feasible \(\theta\), the segment \(\theta^*+t(\theta-\theta^*)\), \(0\le t\le1\), lies in the domain. Since \(t=0\) minimizes \(R\) along this segment, its right derivative there is nonnegative: $$ \nabla R(\theta^*)^\top(\theta-\theta^*)\ge0. $$ Apply strong convexity with its first argument \(\theta^*\) and second argument \(\theta\): $$ R(\theta)\ge R(\theta^*)+\nabla R(\theta^*)^\top(\theta-\theta^*)+\frac{\mu}{2}\|\theta-\theta^*\|_2^2 \ge R(\theta^*)+\frac{\mu}{2}\|\theta-\theta^*\|_2^2. $$ If \(\theta\ne\theta^*\), the last term is strictly positive, so no other point can also minimize \(R\). This proves both claims. \(\square\)
In particular, if a fitted parameter has excess risk at most \(\Delta\), the theorem yields \(\|\theta-\theta^*\|_2\le\sqrt{2\Delta/\mu}\). This is a deterministic conversion: it does not assume how the bound \(\Delta\) was obtained.
Quadratic Growth Is Weaker Than Strong Convexity
The reverse implication does not hold. Quadratic growth compares each point only with the optimum; it does not require positive curvature between every pair of points. The following convex example has a unique minimizer and global quadratic growth on its domain, yet contains a linear segment.
Worked Example: Quadratic Growth Without Strong Convexity
On the domain \([-2,2]\), define $$ R(x)= \begin{cases} x^2, & |x|\le1,\\ 2|x|-1, & 1\le |x|\le2. \end{cases} $$ The pieces and their first derivatives agree at \(x=\pm1\). The derivative is nondecreasing, so \(R\) is convex, and its unique minimizer is \(x^*=0\).
For \(|x|\le1\), \(R(x)=x^2\ge x^2/2\). For \(1\le |x|\le2\), put \(u=|x|\). Then $$ 2u-1-\frac12u^2=\frac12(4u-u^2-2)\ge0, $$ because \(4u-u^2-2\) is increasing on \([1,2]\) and equals \(1\) at \(u=1\). Therefore \(R(x)-R(0)\ge x^2/2\) throughout the domain: quadratic growth holds with \(\mu=1\). But \(R\) is affine on \((1,2)\). Strong convexity with any \(\mu>0\) would require a strictly positive quadratic correction between distinct points on that segment, contradicting affinity. Thus quadratic growth does not imply strong convexity.
Quadratic growth is often the condition directly needed to turn risk into distance. If \(R(\theta)-R^*\le\Delta\) and the quadratic-growth condition holds with constant \(\mu\), then $$ \operatorname{dist}(\theta,\Theta^*)\le\sqrt{\frac{2\Delta}{\mu}}. $$ This follows by combining the upper bound \(\Delta\) with the defining lower bound \(\frac{\mu}{2}\operatorname{dist}(\theta,\Theta^*)^2\), then taking square roots. When \(\Theta^*\) is not a single point, the conclusion is distance to the set of minimizers, not to a particular parameterization.
Error Bounds Concern Residuals, Not Just Risk
For an unconstrained differentiable convex risk, a gradient error bound controls parameter distance from the size of the gradient. Strong convexity implies this particular error bound. Indeed, at an unconstrained minimizer \(\theta^*\), differentiability gives \(\nabla R(\theta^*)=0\). Strong convexity applied in both directions, and then added, gives $$ \big(\nabla R(\theta)-\nabla R(\theta^*)\big)^\top(\theta-\theta^*)\ge\mu\|\theta-\theta^*\|_2^2. $$ By Cauchy–Schwarz, the left side is at most \(\|\nabla R(\theta)\|_2\|\theta-\theta^*\|_2\). For \(\theta\ne\theta^*\), division gives \(\|\theta-\theta^*\|_2\le\|\nabla R(\theta)\|_2/\mu\); at the minimizer it also holds. The error-bound constant is therefore \(1/\mu\).
The term “error bound” is also used for a different, value-based condition. One example is the Polyak–Łojasiewicz inequality, \(\frac12\|\nabla R(\theta)\|_2^2\ge\mu(R(\theta)-R^*)\). It controls excess risk by a gradient residual; it is not the same statement as bounding distance to the minimizer set. When reading or applying an error-bound result, check which quantity is on each side and what norm or residual is being used. For constrained problems, the ordinary gradient may not vanish at a minimizer; the corresponding condition must use an appropriate constrained residual, such as a projected-gradient mapping.
Worked Example: A Flat Minimum That Defeats Distance Bounds
On \([-1,1]\), take \(R(x)=x^4\), whose unique minimizer is \(0\). Its excess risk is \(x^4\), and its gradient is \(4x^3\). Quadratic growth with any \(\mu>0\) would require \(x^4\ge(\mu/2)x^2\) for every nonzero \(x\). Dividing by \(x^2\) gives \(x^2\ge\mu/2\), which fails as \(x\) approaches zero.
A gradient error bound would require \(|x|\le4\kappa|x|^3\). For nonzero \(x\), this is \(1\le4\kappa x^2\), which also fails arbitrarily close to zero for every fixed \(\kappa\). Thus a small excess risk or gradient can coexist with a comparatively large parameter error: if \(R(x)\le\Delta\), the direct calculation gives \(|x|\le\Delta^{1/4}\), not a square-root conversion. The example shows why a curvature or error-bound hypothesis must be verified rather than inferred merely from the existence of a minimizer.
Prediction Geometry and Nonidentifiability
Parameter curvature can be stronger than prediction curvature. In the linear least-squares example, suppose instead that \(X=(Z,0)^\top\), where \(E[Z^2]=1\), and \(Y=Z+\varepsilon\), with \(E[\varepsilon\mid X]=0\) and \(E[\varepsilon^2]<\infty\). The same finite-risk expansion gives $$ R(\theta)-R((1,0))=\frac12(\theta_1-1)^2. $$ Changing \(\theta_2\) has no effect on predictions or risk. The risk has quadratic growth in prediction distance, but no positive quadratic lower bound in the full parameter distance: parameters \((1,M)\) have zero excess risk for every \(M\). There is a whole set of minimizers \(\Theta^*=\{(1,t):t\in\mathbb R\}\); distance to this set is controlled, while distance to a selected representative such as \((1,0)\) is not.
This is not a paradox or a failure of prediction accuracy. It is a consequence of the model map from parameters to predictions being non-injective. A positive lower eigenvalue of the design covariance is needed to turn prediction control into full Euclidean parameter control. Without such identifiability, report the controlled prediction error or distance to the minimizer set rather than claiming a unique parameter estimate is accurate.
Common Pitfall and Practical Use
- Confusing risk control with curvature. A bound on excess risk comes from the statistical analysis; a curvature condition translates that bound into another scale. Curvature alone does not supply the statistical bound.
- Calling quadratic growth strong convexity. The former compares with the optimum; the latter constrains every pair of points. The piecewise example satisfies the first but not the second.
- Assuming prediction error identifies parameters. It does so only with a suitable identifiability condition, such as a positive lower eigenvalue in the linear example.
- Using the wrong error-bound residual. A gradient-to-distance bound and a gradient-to-excess-risk inequality are different claims. For constrained optimization, an unconstrained gradient may not be the right residual.
When using an oracle inequality, first identify the quantity it bounds. Then check whether the curvature condition is stated in parameter distance, prediction distance, or another metric, and whether it is global or local. Only after those checks should an excess-risk rate be converted into a prediction or parameter rate.
Check Your Understanding
Use the definitions and examples above to answer the following.
- Which part of the strong-convexity inequality yields quadratic growth at a constrained minimizer, and why is the gradient term nonnegative?
- Can global quadratic growth on a domain imply strong convexity? Explain using the piecewise example.
- If excess risk is at most \(\Delta\) and quadratic growth holds with constant \(\mu\), what bound follows for distance to the minimizer set?
- In a nonidentifiable regression model, how can prediction error be controlled while parameter error is not?
- State the difference between a gradient error bound and the Polyak–Łojasiewicz inequality in terms of the quantities they relate.