Quadratic Growth and Fast Rates for Convex ERM

Why Quadratic Growth Matters

Empirical risk minimization chooses a parameter that performs well on the observed sample. Its population risk can still differ from the minimum population risk: the empirical objective fluctuates around its expectation. A useful way to control the effect of those fluctuations is to assume that population risk rises at least quadratically as we move away from its minimizer. This geometry makes a small empirical advantage costly to achieve far from the population optimum.

The key point is that quadratic growth is a lower bound on excess risk. Combined with a suitable bound on empirical fluctuations, it limits how far an empirical risk minimizer can move and, through a separate comparison, how much excess risk it can have. Neither conclusion follows by treating quadratic growth as an upper bound.

Setup and Quadratic Growth

Let $\Theta$ be a convex subset of a finite-dimensional normed vector space. Let $Z_1,\ldots,Z_n$ be independent observations with common distribution $P$, and let $\ell_\theta(z)$ be a measurable loss with finite expectation for each $\theta\in\Theta$. Define the population and empirical risks by

R(\theta)=E[\ell_\theta(Z)], \qquad R_n(\theta)=\frac{1}{n}\sum_{i=1}^n \ell_\theta(Z_i).

Assume that a population minimizer $\theta^\star\in\Theta$ exists, and that an empirical risk minimizer $\hat\theta\in\Theta$ exists. When discussing a random $\hat\theta$, assume a measurable minimizer has been selected. We write the excess risk as $\Delta(\theta)=R(\theta)-R(\theta^\star)$ and the parameter distance as $d(\theta)=\|\theta-\theta^\star\|$.

Definition: The population risk satisfies a quadratic-growth condition with constant $\kappa>0$ around $\theta^\star$ if, for every $\theta\in\Theta$, $$ R(\theta)-R(\theta^\star)\geq \frac{\kappa}{2}\|\theta-\theta^\star\|^2. $$

Quadratic growth concerns the risk relative to its minimizer. It does not require the entire risk function to have constant curvature everywhere. Strong convexity is one sufficient way to obtain quadratic growth, but quadratic growth can hold under weaker conditions. In this tutorial, the risks are convex as a natural setting for convex ERM; the main comparison below uses the growth condition and the minimizing property directly.

Worked Example: Quadratic Growth Without a Global Curvature Calculation

Take $\Theta=[-2,2]$ and $R(\theta)=3+\theta^2$. The unique minimizer is $\theta^\star=0$, and

R(\theta)-R(0)=\theta^2=\frac{2}{2}|\theta-0|^2.

Thus quadratic growth holds with $\kappa=2$, with equality everywhere on $\Theta$. The additive constant 3 has no effect on either the minimizer or the excess risk. The condition says that moving a distance $d$ from zero costs at least $d^2$ in population risk; it does not say that excess risk is at most $d^2$ in a general model.

A Basic Fast-Rate Bound

The empirical fluctuation relevant to ERM is the change in the empirical-versus-population discrepancy between $\theta$ and $\theta^\star$. Suppose that, on an event of interest, there are constants $a,b\geq 0$ such that, simultaneously for every $\theta\in\Theta$,

\left|(R_n-R)(\theta)-(R_n-R)(\theta^\star)\right| \leq a\|\theta-\theta^\star\|+b.

The constants may be deterministic or may describe an event whose probability is controlled by a separate concentration argument. The next result is deterministic on any event where the inequality holds.

Theorem: Suppose quadratic growth holds with $\kappa>0$, $\hat\theta$ minimizes $R_n$ over $\Theta$, and the displayed fluctuation bound holds for every $\theta\in\Theta$. Then, writing $D=\|\hat\theta-\theta^\star\|$, $$ D\leq \frac{a+\sqrt{a^2+2\kappa b}}{\kappa}, \qquad R(\hat\theta)-R(\theta^\star) \leq aD+b \leq \frac{\kappa D_{\max}^2}{2}, $$ where $D_{\max}=(a+\sqrt{a^2+2\kappa b})/\kappa$. In particular, the excess risk is at most $aD_{\max}+b=\kappa D_{\max}^2/2$.

Proof. Empirical optimality gives $R_n(\hat\theta)-R_n(\theta^\star)\leq 0$. Add and subtract the two empirical risks to write

\begin{aligned} R(\hat\theta)-R(\theta^\star) ={}&\big[(R-R_n)(\hat\theta)-(R-R_n)(\theta^\star)\big]\\ &+\big[R_n(\hat\theta)-R_n(\theta^\star)\big]\\ \leq{}&\left|(R_n-R)(\hat\theta)-(R_n-R)(\theta^\star)\right|\\ \leq{}&aD+b. \end{aligned}

Quadratic growth supplies the other inequality, $\kappa D^2/2\leq R(\hat\theta)-R(\theta^\star)$. Combining the two gives

\frac{\kappa}{2}D^2-aD-b\leq 0.

The roots of the corresponding quadratic equation are $(a\pm\sqrt{a^2+2\kappa b})/\kappa$. Its smaller root is nonpositive and its larger root is $D_{\max}$. Since $D\geq 0$, the inequality implies $D\leq D_{\max}$. For the risk bound, use the earlier empirical comparison, not quadratic growth as an upper bound:

R(\hat\theta)-R(\theta^\star)\leq aD+b\leq aD_{\max}+b =\frac{\kappa D_{\max}^2}{2}.

The final equality follows by substituting $D_{\max}$ into its defining equation $\kappa D_{\max}^2/2=aD_{\max}+b$. $\square$

Worked Example: Using Both Terms in the Fluctuation Bound

Let $\Theta=[-1,1]$, $R(\theta)=\theta^2/2$, and $R_n(\theta)=\theta^2/2-0.2\theta$. Both functions are convex, $\theta^\star=0$, and quadratic growth holds with $\kappa=1$. The empirical minimizer is $\hat\theta=0.2$, since the derivative of $R_n$ is $\theta-0.2$, which vanishes inside $\Theta$.

For any $\theta\in[-1,1]$, the centered fluctuation is $(R_n-R)(\theta)-(R_n-R)(0)=-0.2\theta$. With $d=|\theta|\leq 1$, we have $0.2d\leq 0.18d+0.02$. Thus we may take $a=0.18$, $b=0.02$. The theorem gives

D_{\max}=0.18+\sqrt{0.18^2+2(0.02)} =0.18+\sqrt{0.0724}\approx 0.4491.

The theorem's excess-risk bound is $aD_{\max}+b\approx 0.18(0.4491)+0.02\approx 0.1008$. The actual distance is $0.2$, and the actual excess risk is $R(0.2)-R(0)=0.2^2/2=0.02$, both within the bounds. The bound is conservative here: the chosen $a,b$ give a valid but loose fluctuation inequality.

Why These Bounds Give Fast Rates

If the fluctuation terms scale as $a=O(n^{-1/2})$ and $b=O(n^{-1})$, with fixed $\kappa>0$, the theorem gives $D=O(n^{-1/2})$ and excess risk $O(n^{-1})$. Indeed, the root is controlled by a term proportional to $a/\kappa$ and a term proportional to $\sqrt{b/\kappa}$. The distance therefore has the usual square-root sample-size scale, while the quadratic population geometry yields a faster, order-$1/n$ risk scale. The exact constants and probability level depend on how the fluctuation bound was established.

A related form makes the role of localization in risk especially transparent. Suppose that, on an event, the centered fluctuation obeys the following inequality simultaneously for every $\theta\in\Theta$, where $c,q\geq 0$:

\left|(R_n-R)(\theta)-(R_n-R)(\theta^\star)\right| \leq c\sqrt{\frac{\Delta(\theta)}{n}}+\frac{q}{n}.

The ERM comparison proved above, applied at $\hat\theta$, gives $\Delta(\hat\theta)\leq c\sqrt{\Delta(\hat\theta)/n}+q/n$. Set $u=\sqrt{\Delta(\hat\theta)}$, which is nonnegative. Then $u^2-(c/\sqrt n)u-q/n\leq 0$. Solving this quadratic inequality yields

u\leq \frac{c+\sqrt{c^2+4q}}{2\sqrt n}, \qquad \Delta(\hat\theta)\leq \frac{(c+\sqrt{c^2+4q})^2}{4n}.

This fully specified fluctuation condition therefore gives an order-$1/n$ excess-risk bound. If quadratic growth also holds, then $\kappa\|\hat\theta-\theta^\star\|^2/2\leq\Delta(\hat\theta)$, so it translates the risk guarantee into a parameter-distance guarantee as well. The condition is an assumption on the localized empirical process; quadratic growth alone does not establish it.

Worked Example: Gaussian Mean Estimation

Let $Z_i$ be independent $N(\mu,1)$ observations, let $\Theta=\mathbb{R}$, and use squared loss $\ell_\theta(z)=(z-\theta)^2/2$. The population risk is $R(\theta)=\big(1+(\theta-\mu)^2\big)/2$, so $\theta^\star=\mu$, $\Delta(\theta)=(\theta-\mu)^2/2$, and quadratic growth holds with $\kappa=1$.

Write $\bar Z=n^{-1}\sum_i Z_i$ and $\varepsilon=\bar Z-\mu$. Expanding the empirical risk difference gives

R_n(\theta)-R_n(\mu) =\frac{(\theta-\mu)^2}{2}-(\theta-\mu)\varepsilon.

The population risk difference is $(\theta-\mu)^2/2$, so the centered fluctuation is $-(\theta-\mu)\varepsilon$. It is bounded in absolute value by $|\varepsilon||\theta-\mu|$, allowing $a=|\varepsilon|$, $b=0$. The empirical minimizer is $\hat\theta=\bar Z$. On the event $|\varepsilon|\leq 0.2$, the theorem gives $D\leq 2(0.2)=0.4$ and excess risk at most $aD=0.08$. In fact, the exact risk formula gives

R(\hat\theta)-R(\mu)=\frac{\varepsilon^2}{2}\leq \frac{0.2^2}{2}=0.02.

This event has probability $P(|\varepsilon|\leq 0.2)=P(|N(0,1)|\leq 0.2\sqrt n)$, since $\varepsilon\sim N(0,1/n)$. The sharper exact calculation is specific to this model; the theorem provides a general bound from the stated fluctuation inequality.

Worked Example: A Rademacher Linear Perturbation

Let $Z_i$ be independent Rademacher random variables, so each equals $1$ or $-1$ with probability $1/2$. On $\Theta=[-1,1]$, define $\ell_\theta(z)=\theta^2-z\theta+1$. This loss is convex in $\theta$; it is also nonnegative because $\theta^2-| \theta|+1\geq 3/4$ for $|\theta|\leq 1$. The population risk is $R(\theta)=\theta^2+1$, with $\theta^\star=0$, excess risk $\Delta(\theta)=\theta^2$, and quadratic-growth constant $\kappa=2$.

Writing $\bar Z=n^{-1}\sum_i Z_i$, the empirical risk is $R_n(\theta)=\theta^2-\bar Z\theta+1$. Its unconstrained minimizer is $\bar Z/2$, which belongs to $[-1,1]$ because $|\bar Z|\leq 1$. Thus $\hat\theta=\bar Z/2$. The centered fluctuation relative to zero is $-\bar Z\theta$, so the theorem applies with $a=|\bar Z|$ and $b=0$, giving $D\leq |\bar Z|$ and $\Delta(\hat\theta)\leq |\bar Z|^2$.

For $n=100$, Hoeffding's inequality gives $P(|\bar Z|>t)\leq 2\exp(-nt^2/2)$. With $\delta=0.1$, set $t=\sqrt{2\log(2/\delta)/n}=\sqrt{2\log(20)/100}\approx 0.2448$. With probability at least $0.9$, the theorem therefore gives $D\leq 0.2448$ and excess risk at most $0.2448^2\approx 0.0599$. Directly, $\Delta(\hat\theta)=\hat\theta^2=\bar Z^2/4$, so on the same event the exact excess risk is at most $0.2448^2/4\approx 0.0150$. The theorem's more general bound is valid but not sharp for this model.

Common Pitfall: Reversing the Growth Inequality

A frequent mistake is to write “quadratic growth gives $\Delta(\hat\theta)\leq \kappa D^2/2$.” The definition states the reverse inequality: $\Delta(\hat\theta)\geq\kappa D^2/2$. It helps to keep the two stages of the proof separate. Growth and the ERM comparison together bound the distance through $\kappa D^2/2\leq aD+b$. The risk upper bound comes from the ERM comparison itself, $\Delta(\hat\theta)\leq aD+b$, followed by the distance bound.

For example, in the Gaussian calculation, the upper bound $\Delta(\hat\theta)\leq \varepsilon^2/2$ follows from the exact risk formula $\Delta(\hat\theta)=\varepsilon^2/2$, not from reversing quadratic growth. Such model-specific equalities can sharpen a general theorem, but they do not change the direction of its assumptions.

Key takeaway: Quadratic growth turns control of empirical fluctuation into control of distance from the population minimizer. The population excess-risk upper bound must then be justified by the ERM comparison or another separate argument, never by reversing the growth condition.

Check Your Understanding

Check that you can identify which assumption supplies each inequality.

State the quadratic-growth inequality and explain why it is a lower bound on excess risk.
If the fluctuation bound has $b=0$, what distance bound follows from the theorem?
In the Gaussian example, which calculation justifies the exact excess-risk value at the empirical minimizer?
Suppose a risk-localized fluctuation bound has constants $c$ and $q$. What substitution turns the ERM inequality into a quadratic equation?
Why does quadratic growth alone not prove that the empirical fluctuation is of order $1/n$?