Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification

Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification Alex Buna

Shirley Xiaoqi Liu

Patrick Rebeschini

Department of Statistics, University of Oxford

arXiv:2608.06250v1 [stat.ML] 6 Aug 2026

Abstract In overparameterised classification, training data can be linearly separable even when the underlying distribution is not. In this setting, gradient descent (GD) on the logistic loss diverges in norm while converging in direction to a max-margin interpolating classifier, whose implicit bias can be statistically suboptimal. In this work, we show that early stopping can overcome this suboptimality: in a Gaussian mixture model with label-flipping noise, GD stopped at an appropriate oracle time achieves minimaxoptimal excess zero-one risk for covariance spectra with fast and continuous decay, including polynomial and exponential spectral decays. Our analysis combines a sharp upper bound for the early-stopped iterate with a matching statistical lower bound over arbitrary classifiers, yielding optimal rates that are validated by experiments. A central technical contribution is a new calibration result that converts excess logistic risk into excess zero-one risk; it handles the model misspecification induced by the label-flipping noise, and removes the square-root rate in standard bounds. We also establish a lower bound for linear interpolators, showing that interpolation can require exponentially more samples than early stopping to achieve the same excess risk.

1

Introduction

Machine learning models are routinely trained in overparameterised regimes, where the number of parameters d exceeds the sample size n. While interpolation [26] and early-stopping in gradient descent (GD) [40] are both known to generalise in classification settings under suitable conditions, their relative statistical efficiency remains less well-understood than in regression settings. In this work, we study classification in Gaussian mixtures with label-flipping noise, a canonical model that captures key challenges of highdimensional classification, including misspecification under the logistic loss. In this setting, we show that early-stopped GD, with an appropriately chosen stopping time, is minimax-optimal in certain regimes, whereas interpolating estimators can require exponentially more samples to achieve the same excess risk. Overparameterisation has been extensively studied in least-squares regression. Foundational studies [6; 7; 15; 35; 25] show that GD on least-squares converges to the minimum ℓ2 -norm interpolator, which, under sufficient overparameterisation and suitable spectral conditions on the data covariance, achieves vanishing excess risk as n → ∞, a phenomenon termed “benign overfitting”. Complementary to these results, early stopping for GD methods has been shown to act as an implicit regulariser in overparameterised regimes, closely connected to explicit ℓ2 -regularisation in least-squares regression [41; 33]. Under suitable spectral and signal regularity conditions, appropriately early-stopped iterates achieve statistically optimal rates for oracle stopping times [8; 41; 22; 27] and, despite the added difficulty, data-dependent stopping times [28; 38; 2; 19]. Most recently, it was shown in [39] that GD with a data-dependent stopping rule is minimax-optimal over a range of power-law spectral classes defined via the capacity and source conditions [10]. Emails: alex.bunamarginean@spc.ox.ac.uk, shirley.liu@stats.ox.ac.uk, and patrick.rebeschini@stats.ox.ac.uk.

1

excess 0/1 risk

Polynomial spectrum (a = 1)

Exponential spectrum (b = 0.12)

median excess risk

2 × 10−2

6 × 10−3 4 × 10−3 10−2 3 × 10−3 100

101

102

GD iteration t

103

104

100

101

102

GD iteration t

103

104

Figure 1: Early stopping along the GD trajectory. Excess zero-one population risk along GD iterates trained on n = 972 samples from the d = 3888-dimensional Gaussian mixture model X ∼ N (±µ, Σ) with label-flip probability p = 0.1 (see (1)). The centres µ satisfy ∥Σ−1 µ∥ ≲ 1. Left: polynomial spectrum λi (Σ) ≍ i−2a with a = 1. Right: exponential spectrum λi (Σ) ≍ e−bi with b = 0.12. The solid curve shows the median over independent repetitions, and the shaded band shows the interquartile range. In both cases, the excess risk first decreases and then increases as GD approaches interpolation, illustrating the statistical benefit of early stopping. These regression results rely heavily on closed-form solutions and linear GD dynamics under least-squares loss. In contrast, even for linear classifiers, the logistic loss admits neither property, making the theory for classification far less developed despite its central role in machine learning. Specifically, in overparameterised logistic regression, GD behaves fundamentally differently from least-squares regression. Its iterates diverge in ℓ2 -norm while converging in direction to the max-margin on linearly-separable data [32; 31], and to the same direction up to a bounded offset on nonseparable data [17]. As a consequence of this implicit bias, classification analyses [11; 37; 9; 13] depart from those for leastsquares regression, taking the max-margin classifier as the key object of study. A complementary line of work [26; 16; 1] shows that, under sufficient overparameterisation where all samples become support vectors, the max-margin classifier coincides with the minimum ℓ2 -norm interpolator, enabling tools from least-squares analysis to transfer to classification [26; 16; 37; 36]. Both strands of work characterise sufficient spectral conditions under which the max-margin classifier exhibits benign overfitting. Moreover, [37; 36] explicitly compare interpolation with the ℓ2 -regularised classifier. However, none of these works on classification establishes how interpolation compares to early-stopped GD in terms of sample complexity, i.e., the number of samples n required to achieve a target excess zero-one risk, or more fundamentally, whether interpolation or early-stopped GD is statistically optimal. This question is motivated by the phenomenon illustrated in Figure 1. When running GD with the logistic loss for binary classification on linearly separable data, the population excess zero-one risk initially decreases, but then increases again as GD approaches the interpolating regime, illustrating that early stopping improves generalisation, whereas interpolation can be statistically suboptimal. Characterising this statistical benefit of early stopping is the focus of this work. We study a canonical generative model in classification: Gaussian mixtures with label-flipping noise. In this model, the covariate vector X ∈ Rd clusters around class-conditional means ±µ ∈ Rd , and the observed label Y is obtained by flipping a latent label Ye independently with probability p ∈ [0, 0.5). Formally, each sample (X, Y ) ∈ Rd×{±1} is generated by first drawing a latent label Ye ∈ {±1} uniformly, then setting ( −Ye w.p. p , X = Ye µ + ε, ε ∼ N (0, Σ) , and Y = (1) Ye w.p. 1 − p , where Σ ∈ Rd×d is symmetric positive definite. A key challenge in this model is the presence of label-flipping noise, as studied for Gaussian mixtures in the interpolation regime in [11; 37; 13; 36]. When p > 0, the distribution of Y | X differs from the sigmoid model and is thus misspecified under the logistic loss. As 2

excess 0/1 risk

Polynomial spectrum (a = 1)

10−1

Exponential spectrum (b = 0.12)

10−2

10−2

2 × 102

4 × 102

sample size n

6 × 102

103

2 × 102

4 × 102

sample size n

6 × 102

103

Cor. 1 rate: left ∝ n −2a/(2a + 1) , right ∝ log n/n

GD at oracle stopping time (theory) GD lowest zero-one risk iterate (hindsight)

Figure 2: Empirical rates for early-stopped GD. Excess zero-one population risk as a function of the sample size n, under the same experimental setting as Figure 1. The blue curve shows GD at the oracle stopping time used in our theory, while the orange curve shows the GD iterate with the lowest (in hindsight) excess zero-one risk, along the same GD trajectory. Solid curves and shaded bands show medians and interquartile ranges over independent repetitions. The thin black dashed lines show the rates from Corollary 1, n−2a/(2a+1) and log n/n, up to multiplicative constants. a result, standard calibration bounds that relate excess zero-one and logistic risks [42; 5] yield suboptimal rates, necessitating new proof techniques. In this work, we overcome the challenge due to misspecification and prove that, early-stopped GD on the logistic loss is minimax-optimal for classification in the model in (1) when the covariance spectrum is fast and continuously decaying (FCD), in line with the terminology used in earlier regression literature [39, Assumption 3]. To our knowledge, this is the first result establishing the statistical optimality of early-stopped GD for Gaussian mixture classification. The FCD class covers a range of spectral decays, including both polynomial and exponential spectra, whereas [39] establishes minimax rates for GD in regression within power-law spectral classes, which correspond to polynomial decay. Figure 2 provides a finite-sample validation of our theory: it plots the empirical excess risk as a function of the sample size under both polynomial and exponential spectra, showing close agreement with the minimax rates predicted by our theory, summarised in Table 1.

1.1

Main Contributions

We study GD under the logistic loss for Gaussian mixture classification with label-flipping noise. We establish that in certain regimes early stopping is sufficient and necessary for statistical optimality: • (Sufficiency) We prove that for FCD covariance spectra, there exists an oracle stopping time at which the GD iterate achieves minimax-optimal excess zero-one risk (Theorem 3). This is established via an upper bound for the early-stopped GD iterate (Theorem 1) and a matching statistical lower bound for arbitrary classifiers (Theorem 2). To the best of our knowledge, this is the first minimax optimality result for early-stopped GD for Gaussian mixture classification. • For common FCD spectral regimes, specialising Theorem 3 yields Corollary 1, which provides explicit minimax rates for polynomially and exponentially-decaying spectra. These rates are summarised in Table 1, and are closely matched by the empirical rates in Figure 2. • A key technical contribution is a calibration result (Lemma 4) linking excess logistic and zero-one risks in the Gaussian mixture model with label-flipping noise, which renders the model misspecified under the logistic loss. Unlike standard calibration bounds [42; 5], which incur a square-root rate and optimise 3

Table 1: Summary of main results: minimax-optimal excess zero-one risk achieved by early-stopped GD at the oracle stopping time τ ; excess zero-one risk lower bound at interpolation. Excess zero-one risk At oracle stopping time τ

Polynomial decay λi (Σ) ≍ i−2a , a > 21

Exponential decay λi (Σ) ≍ e−bi , b > 0

≍ n−2a/(2a+1)

≍ log n/n

≳ 1/ log n

≳ 1/ log n

At interpolation (for d ≍ n log n)

over all measurable predictors, our result achieves a linear rate and is restricted to linear classifiers. This sharper calibration is essential for deriving our minimax-optimal upper bound. • (Necessity) Finally, we prove an excess risk lower bound over all linear interpolators (Theorem 4), including the max-margin classifier that GD converges to in direction. As summarised in Table 1, in scaling regimes such as d ≍ n log n, this interpolation lower bound vanishes strictly more slowly in n than the minimax rate of early-stopped GD for polynomial and exponential spectra. This result builds on and generalises Theorem 4.2 of [40] by removing its signal-sparsity assumption. This generalisation is essential for bringing this interpolation lower bound within the scope of our minimax theory, since the worst-case signal directions that determine the minimax rates need not be sparse.

1.2

Related Work

A first step towards understanding the statistical benefit of early stopping is taken by [40], which analyses early-stopped GD in well-specified logistic regression, a discriminative model. It shows that early-stopped GD incurs only polynomial sample complexity in certain overparameterised regimes where interpolation requires exponential sample complexity. Our work goes beyond [40] in two directions. First, we study a qualitatively distinct Gaussian mixture model, a generative model that becomes misspecified under the logistic loss in the presence of label-flipping noise p > 0. This misspecification requires new calibration bounds for the analysis. Second, we show that early-stopped GD is not only more sample-efficient than interpolation in common overparametrised regimes, but it is, in fact, minimax-optimal for the class of FCD covariance spectra. Analyses of GD often characterise problem difficulty through the capacity-source conditions, e.g., [10], where capacity measures spectral decay and source measures signal alignment via a parameter r. A closely related work to ours on the regression side is [39], which establishes the minimax optimality of early-stopped GD over power-law spectral classes. These classes are defined via the capacity-source conditions, thus corresponding to polynomial spectral decay, and allowing a general alignment parameter r ≥ 0. Their minimax rates capture explicit dependence on r. Our work is similar in spirit but focuses on classification under the logistic loss. We show minimax optimality of early-stopped GD for a broader class of spectral decays than [39], namely the FCD class, which includes both polynomial and exponential spectral decays. However, our minimax rates can be seen as corresponding to r = 12 and therefore do not explicitly capture dependence on r. Interpolation in Gaussian mixtures is studied as a canonical linear classification setting for benign overfitting in recent works [11; 26; 37; 9; 13; 36]; see [13, Table 1] for a summary of results across different regimes depending on the covariance spectrum, the signal-to-noise ratio, and label-flip probability. Our work studies the same model with general covariance spectrum, but focuses on the statistical performance of early-stopped GD, using interpolation as an important point of comparison. In contrast to the finite-sample results reviewed above and developed in this paper, a long line of work [34; 29; 12; 20; 23; 18; 30; 24] studies overparameterised linear classification in the proportional asymptotic regime, where d, n → ∞ with d/n converging to a constant. This regime enables precise asymptotic characterisation of the generalisation error. However, these results often rely on systems of equations that are hard to approach

4

analytically and focus on isotropic covariance, with less attention given to anisotropic settings, which are important for generalisation of ℓ2 -regularised solutions [6; 26]. Notation: We use ordinary letters for scalars, boldface letters for vectors or matrices, uppercase letters for d×d random variables, , √ definite matrix Σ√∈ R Pd and lowercase for their realisations. For a symmetric positive let tr(Σ) := i=1 Σii denote its trace. For a vector x ∈ Rd we denote ∥x∥ := x⊤ x and ∥x∥Σ := x⊤ Σx. For an arbitrary matrix X ∈ Rn×d , let ∥X∥ := supv∈Rd ,∥v∥=1 ∥Xv∥ denote its spectral norm. We use c with various subscripts to denote positive universal constants independent of n and d. Throughout, a ≲ b (resp. a ≳ b) means a ≤ c1 b (resp. a ≥ c2 b) for universal constants c1 , c2 > 0, and a ≍ b means a ≲ b and a ≳ b hold simultaneously.

2

Problem Setup

We study binary classification in the Gaussian mixtures model defined in (1). For a classifier h : Rd → {±1}, define its population zero-one risk as E(h) := P (h(X) ̸= Y ) , and for a linear classifier parametrised by w ∈ Rd , hw (x) = sign(x⊤ w), we abbreviate E(w) := E(hw ) . It is known (see, e.g., [14]) that the Bayes classifier is unique and linear, given by arg min E(h) = hw∗ ,

where

w∗ := Σ−1 µ.

h:Rd →{±1}

Hence, the goal of a training algorithm is to learn a linear classifier w that minimises the excess zero-one risk E(w) − E(w∗ ).1 Since the zero-one loss is discontinuous, training commonly minimises the logistic loss ℓ(z) = log(1 + exp(−z)), a smooth convex surrogate. As before, we define the logistic risk of a generic classifier h : Rd → {±1} or a linear classifier hw (x) = sign(x⊤ w), respectively, as: L(h) := E[ℓ(Y h(X))]

and

L(w) := L(hw ) .

The following lemma characterises the minimiser ∗ wL ∈ arg min L(w) , w∈Rd

which plays a central role in our early-stopped GD analysis: Lemma 1 (Population logistic risk minimiser). The minimiser of L(w) over Rd is unique and has the form ∗ wL = ρ∗ w∗ where ρ∗ ∈ (0, 2]. Training via GD: Let (Xi , Yi )ni=1 be n training samples drawn i.i.d. from the joint distribution of (X, Y ) in (1). The most common training procedure is to minimise the empirical logistic risk n 1X b ℓ(Yi Xi⊤ w), L(w) := n i=1 1 If, instead, one is interested in measuring the excess zero-one risk with respect to the latent labels Y e , note that the identity E(w) = p + (1 − 2p)P(sign(X ⊤ w) ̸= Ye ) gives an exact characterisation. Hence, the Bayes classifiers coincide under both risk measures and the excess risks differ only by a factor of 1 − 2p. By the same identity, when p = 0.5, i.e., Y is random noise, E(w) = 0.5 for any w ∈ Rd and the excess risk is always 0. To avoid such degenerate cases, we fix p < 0.5.

5

over linear classifiers via GD, initialised at the origin with a fixed step size γ > 0: w0 = 0,

b t) wt+1 = wt − γ∇L(w

for t ≥ 0 .

Let X1:n ∈ Rn×d denote the design matrix whose rows are X1⊤ , . . . , Xn⊤ , and let ∥X1:n ∥ denote its spectral 2 norm. To ensure monotone descent, we set the step size to γ ≤ min(1/β, 1), where β := ∥X1:n ∥ /n is the smoothness constant of Lb (see Lemma 7 in Appendix B.2). Early stopping: We focus on the overparameterised regime with d ≥ n, where two contrasting phenomena arise that explain the empirical observations in Figure 1. On one hand, the training samples (Xi , Yi )ni=1 are almost surely linearly separable, that is, there exists some w ∈ Rd such that min Yi Xi⊤ w > 0 .

1≤i≤n

On the other hand, the Bayes risk E(w∗ ) > 0, implying the population distribution is not linearly separable, even when p = 0. In this regime, the implicit bias of GD under the empirical logistic risk [32; 17] drives the GD iterates to diverge in norm while converging in direction to the max-margin classifier, an interpolating solution that can incur suboptimal excess risk, as we prove in Section 4. To prevent this, we propose to stop GD early, at iteration τ := inf{t ≥ 1 : ∥wt ∥ ≥ 4 ∥w∗ ∥}.

(2)

Lemma 2 (Existence of τ ). Suppose n ≤ d. Then ∥wt ∥ → ∞ as t → ∞ almost surely, and so τ = inf{t ≥ 1 : ∥wt ∥ ≥ 4 ∥w∗ ∥} is finite. Our stopping rule in (2) ensures that the early-stopped iterate wτ remain bounded in the sense of Lemma 3 (i) below. On a technical level, this allows us to localise the iterate wτ , and thus apply a refined concentration analysis yielding the sharp upper bound in Theorem 1 below. At the same time, stopping too b τ ) from decreasing sufficiently, which is needed to ensure early would prevent the empirical logistic risk L(w progress towards a good classifier. As is customary in risk decomposition, we show that our stopping time b τ ) ≤ L(w b ∗ ) (Lemma 3 (ii)). also guarantees L(w L Lemma 3 (Properties of the early-stopped iterate). The early-stopped iterate wτ satisfies the following: (i) b τ ) ≤ L(w b ∗ ). ∥wτ ∥ < 4 ∥w∗ ∥ + 1; and (ii) L(w L Similar oracle stopping rules, typically derived from bias-variance tradeoffs, are commonly used in the statistical analysis of early stopping [8; 41; 22; 27; 40]. We detail the proof of Lemmas 1 in Appendix B.1 and the proofs of Lemmas 2–3 in Appendix B.2.

3

Minimax Optimality of Early-Stopped GD

In this section, we present our main results, establishing the statistical optimality of GD at the oracle stopping time τ . We first prove a high-probability upper bound on the excess zero-one risk of the earlystopped GD iterate wτ (Section 3.1), and then a lower bound that applies to any arbitrary classifier, including the linear classifier induced by wτ (Section 3.2). Finally, we show that these bounds match as functions of the sample size n, for the FCD spectral class, including polynomially and exponentially-decaying spectra (Section 3.3). Throughout, our results depend on the spectrum of Σ, whose eigenvalues we denote by λ1 ≥ λ2 ≥ . . . ≥ λd > 0.

6

3.1

Upper Bound for Early-Stopped GD

We first present our excess zero-one risk upper bound for the early-stopped GD iterate wτ . This bound involves the spectrum of Σ through a soft-thresholding operator, namely the effective rank of Σ, defined for every η > 0 as reff (η) := tr(Σ(Σ + ηId )−1 ) =

d X

λi . λ +η i i=1

This corresponds to the effective dimension commonly used in analyses of ridge regression, e.g., [10]. We also ∗ recall from Lemma 1 that the population logistic risk minimiser has the form wL = ρ∗ w∗ where ρ∗ ∈ (0, 2]. These quantities will be used in the theorem below. Theorem 1 (Upper bound for early-stopped GD). There exist a universal constant c0 > 0 and some c1 , c2 , c3 , c4 > 0 depending on µ and Σ only, but not on n or p, such that the following holds: Fix δ ∈ (0, 1) and n ≥ 3. Suppose there exists ηn > 0 satisfying n ≥ c0 (reff (ηn ) +1+ log(2/δ)) and Ψ(ηn ) :=

reff (ηn ) + log(1/δ) + log log(n) + c2 2 + c3 ηn ≤ c4 (ρ∗ )2 ∥w∗ ∥Σ . n

(3)

Then, with probability at least 1 − δ, E(wτ ) − E(w∗ ) ≤ c1

1 − 2p (ρ∗ )2 ∥w∗ ∥Σ

Ψ(ηn ).

The proof of Theorem 1, including explicit constants, is provided in Appendix C, with a preview of the main technical challenges and new proof techniques provided in Section 3.1.1. We now interpret the key quantities in the bound to build intuition: The upper bound depends on Ψ(ηn ), which must be small enough for condition (3) to hold. Since the right hand side of (3) is constant in n, this is ensured if Ψ(ηn ) → 0 as n → ∞. Moreover, the bound E(wτ ) − E(w∗ ) ≲ Ψ(ηn ) shows that the same behaviour suffices for vanishing excess risk. Hence, condition (3) imposes no restrictions beyond those already sufficient for vanishing excess risk. The tightness of the upper bound is governed by the choice of ηn through Ψ(ηn ), which consists of two terms: one involving reff (ηn ) and one linear in ηn . Since reff (ηn ) decreases with ηn , this induces a tradeoff that determines the optimal choice of ηn . For commonly studied spectral decays, such as polynomial (λi ≍ i−2a for a > 21 ) and exponential (λi ≍ e−bi for b > 0), this tradeoff can be solved analytically, yielding the optimal rates n−2a/(2a+1) and log n/n, respectively. In Section 3.3, we prove that this optimality extends more generally to fast and continuously decaying spectrum (FCD). A natural notion of signal-to-noise ratio (SNR) in the Gaussian mixtures model is ∥µ∥Σ−1 , which is equal to ∥w∗ ∥Σ . Our upper bound scales inversely with the SNR, as expected: as the noise level increases, the SNR decreases, leading to a looser upper bound, consistent with the deterioration in the performance of the early-stopped GD iterate. 3.1.1

New Proof Techniques

The proof of Theorem 1 has several technical steps; we highlight the ones capturing the main novelty. A new calibration result: Standard calibration arguments [42; 5] compare the excess zero-one risk to the excess logistic risk relative to the unrestricted logistic optimum: q (4) E(w) − E(w∗ ) ≲ L(w) − min L(h) . h:Rd →R

This bound has two limitations. First, the square-root dependence leads to suboptimal rates in the excess zero-one risk guarantees. Second, and more importantly, the minimum of L(h) is taken over all measurable 7

functions h : Rd → R, rather than binary classifiers. Consequently, the L(w) − minh:Rd →R L(h) bound in (4) ∗ ∗ is strictly looser than one based on L(w) − L(wL ), with an irreducible difference L(wL ) − minh:Rd →R L(h). In well-specified models such as the sigmoid, Proposition 2.1.B of [40] overcomes this second limitation, albeit with the suboptimal square-root dependence. However, this result is not directly transferable to our Gaussian mixtures model when p > 0, since it is misspecified under the logistic loss. Together, the square-root rate, the misspecification of our model under logistic loss, and the fact that the unrestricted logistic risk minimiser under our model is real-valued imply that existing calibration results yields not only suboptimal rates, but rates that do not vanish as n → ∞. We overcome these limitations via a new calibration result in Lemma 4. Its proof, provided in Appendix C.1, leverages the local α-strong ∗ convexity of L around wL (see Lemma 9). Lemma 4 (Linear-rate calibration for linear classifiers). Let w ∈ Rd satisfy ∥w∥ ≤ 4∥w∗ ∥ + 1 and ∗ L(w) − L(wL )≤

α(ρ∗ )2 ∥w∗ ∥2Σ , 8

(5)

p
where α = 12 ℓ′′ 3(4∥w∗ ∥ + 1) ∥Σ + µµ⊤ ∥ . Then, E(w) − E(w∗ ) ≤ √

8(1 − 2p) ∗ (L(w) − L(wL )) . 2πα(ρ∗ )2 ∥w∗ ∥Σ

The right hand side of (5) is constant in n, so this condition is satisfied whenever the excess logistic risk vanishes as n → ∞. Thus, bounding the excess zero-one risk reduces to bounding the excess logistic risk. We now focus on this step, highlighting the technical ingredients that depart from prior work. Bounding excess logistic risk using effective rank and localisation: Since ∥wτ ∥ ≤ 4 ∥w∗ ∥ + 1 ∗ (Lemma 3 (i)), it suffices to bound the excess logistic risk L(wτ ) − L(wL ) of the early-stopped GD iterate ∗ wτ over the ball B = {w : ∥w∥ ≤ 4 ∥w ∥ + 1}. For this, [40, Theorem 3.2] uses a standard risk decomposition combined with Rademacher complexity, pP yielding a bound of the form k/n + i>k λi /n. We improve this in two ways: (i) We replace hard thresholding at the k-th eigenvalue with the soft effective rank reff (ηn ) to obtain finer spectral control (see Appendix C.2). In [40], the bias-variance tradeoff is governed by the discrete parameter k, whereas in our bound it is governed by the continuous parameter ηn , allowing for more effective optimisation of the bound by tuning ηn . (ii) We perform a refined risk deviation analysis by localising to low-excess-risk regions, ∗ ) ≤ r} for a fixed r > 0, and extending the resulting restricting B to the shell {w : w ∈ B, L(w) − L(wL bounds to B via a peeling argument over r (see Appendix C.3). Together, these techniques allow us to remove the square-root dependence in the bound.

3.2

Statistical Lower Bound

To establish the statistical optimality of early-stopped GD, we provide a statistical lower bound for arbitrary classifiers, a strictly larger class than the linear classifiers obtained by logistic regression. We work in the Gaussian mixture model (1), where the distribution of (X, Y ) is parametrised by the centre µ, the noise covariance Σ, and the label-flip probability p. For the purpose of the statistical lower bound, we fix Σ and p, and denote the resulting distribution of (X, Y ) by Pµ . Then the n i.i.d. samples S := (Xi , Yi )ni=1 are distributed as Pµ⊗n . For any procedure b h that takes S as input, we denote its output d b (a learned classifier) by hS : R → {±1}, which is measurable with respect to S. Our lower bound involves an eigenvalue count N (e η ), defined via the hard-thresholding operator N (·) as the number of eigenvalues of Σ larger than a fixed ηe > 0: N (e η ) = {i : i ∈ [d], λi ≥ ηe} . This hard-thresholding operator N (·) can be viewed as the discrete analogue of the soft-thresholding operator reff (·) in Theorem 1; their outputs correspond to hard and soft effective dimension notions. 8

Theorem 2 (Statistical lower bound). There exists a universal constant c > 0 such that the following holds: Fix n and let ηen ∈ (0, λ2 /2] ηn ) > 9. Let b h be any procedure. Then, there exists p be small enough so that N (2e µ ∈ Rd with Σ−1 µ ≤ 2/λ1 such that   h i 2e ηn N (2e ηn ) − 1 ∗ b E ⊗n E(hS ) − E(w ) ≥ c(1 − 2p) min , . λ1 n S∼Pµ This lower bound applies to any procedure that outputs a binary classifier b hS based on the samples S. In particular, this includes the linear classifier induced by the early-stopped iterate wτ of Theorem 1. As is standard in learning theory, a lower bound in expectation can be converted into a statement in probability via Markov’s inequality [3], making it directly comparable to Theorem 1. To clarify the role of the tuning parameter ηen , note that ηen captures a tradeoff between the two terms in the minimum, one increasing and the other decreasing in ηen . Although the effective rank reff (ηn ) in the upper bound (Theorem 1) and the eigenvalue count N (e ηn ) in the lower bound (Theorem 2) are not directly comparable, we show in Section 3.3 that, under a common spectral regularity assumption, they are of the same order, making the two bounds comparable. In fact, with an appropriate choice of tuning parameters satisfying ηen = ηn /2, the bounds match as functions of n (see Theorem 3). We provide the proof of Theorem 2 in Appendix D. The proof proceeds in two steps. We first establish a triangle-inequality-type bound relating the excess zero-one risks of two centres µ1 and µ2 to their distance in p Σ-geometry (Lemma 18). We then construct a packing within a suitable subspace of {µ : Σ−1 µ ≤ 2/λ1 } (Lemma 20), and use it to perform a reduction to hypothesis testing.

3.3

Statistical Optimality for Fast and Continuously Decaying Covariance Spectrum

In this section, we combine Theorems 1 and 2 to show that early-stopped GD is statistically optimal for the FCD spectral class. We begin by defining a FCD spectrum, following [39, Assumption 3]. Assumption 1 (Fast and Continuously Decaying spectrum). For all sufficiently small η > 0, the spectrum of Σ satisfies 1 X λi ≲ N (η). (FCD) η i:λi <η

Canonical examples of such spectral decays include polynomial (λi ≍ i−2a with a > 1/2) and exponential (λi ≍ e−bi with b > 0) decay. In linear regression, these spectra are known to prevent benign overfitting [6]. While this observation does not directly transfer to classification, it motivates early-stopped GD as an alternative to interpolation in these regimes. We next show that early-stopped GD is, in fact, statistically optimal for FCD spectra, and achieves vanishing excess zero-one risk: Theorem 3 (Statistical optimality of early-stopped GD for FCD spectrum). Define ηn∗ := sup{η > 0 : N (η) ≥ nη}, and assume that (FCD) holds on (0, 2ηn∗ ]. Then, reff (η) ≍ N (η) for all η ∈ (0, ηn∗ ]. Moreover, if ηn∗ → 0 as n → ∞, and log log(n)/n ≲ ηn∗ , then the upper bound in Theorem 1 with ηn = ηn∗ matches the statistical lower bound in Theorem 2 with ηen = ηn∗ /2, with common rate ≍ ηn∗ . The implications of Theorem 3 are twofold. First, under Assumption 1, it identifies an interval (0, ηn∗ ] on which the effective rank reff (η) and the eigenvalue count N (η), appearing in the upper and lower bounds of Theorems 1 and 2, respectively, are of the same order for all η. In this regime, these two notions of effective dimensions agree up to constants, reconciling the difference between the bounds. Second, it establishes that the optimal tuning parameters satisfy ηn = ηn∗ and ηen = ηn∗ /2. With this choice, the upper and lower bounds match, giving the common rate ≍ ηn∗ . This rate is analytically tractable for common spectral decays, as we show next in Corollary 1. The proofs of Theorem 3 and Corollary 1 are provided in Appendix E. 9

Corollary 1 (Minimax rates for polynomially and exponentially-decaying spectra). For polynomial decay p λi ≍ i−2a with a > 1/2, there exists µ ∈ Rd with Σ−1 µ ≤ 2/λ1 such that 2a

E(wτ ) − E(w∗ ) ≍ ηn∗ ≍ n− 2a+1 . For exponential decay λi ≍ e−bi with b > 0, there exists µ ∈ Rd with Σ−1 µ ≤ E(wτ ) − E(w∗ ) ≍ ηn∗ ≍

4

p 2/λ1 such that

log n . n

Interpolation Lower Bound

To show the benefit of early-stopped GD over interpolation, we prove a lower bound for all interpolating linear classifiers, extending [40, Theorem 4.2] by removing any sparsity assumption on the Bayes direction w∗ , so the result holds uniformly over all w∗ . This generalisation is essential for enabling a meaningful comparison with our minimax rates in Corollary 1: the worst case µ does not guarantee a sparse w∗ , so the interpolation lower bound of [40] that assumes sparsity does not apply. We now state this result formally. Its full proof appears in Appendix F, with a sketch in Appendix F.1. Theorem 4 (Interpolation lower bound). Suppose ∥w∗ ∥Σ ≍ 1. Fix any c ∈ (0, 1) and δ ∈ (0, 1), and let k ∈ {1, . . . , n} be arbitrary. There exist constants c1 , c2 , c3 > 0 such that if   √ 4 and d − k ≥ c2 n , (6) + log n ≥ c1 · k log ck + k log log 2k δ δ then, defining the set of interpolators I := {w ∈ Rd : mini Yi Xi⊤ w > 0}, with probability at least 1−δ, ∀w ∈ I, E(w) − E(w∗ ) ≥ 

√

c3 · (1 − 2p)n 2 . p √ n + d − k + 2 log(2/δ)

(7)

The tuning parameter k trades off sample size requirement in (6) and the tightness of the lower bound in (7): larger values of k require larger n but yield tighter lower bounds. In the high-dimensional regime n/d → 0, choosing k such that k/d → 0 (e.g., k = 1) gives E(w) − E(w∗ ) ≳ n/d, matching the excess mean-squared error lower bound for interpolators in regression [25]. In addition, when d ≍ n log n, Theorem 4 implies that the max-margin classifier w∞ , i.e., the interpolator that GD converges to in direction, satisfies the following lower bound: E(w∞ ) − E(w∗ ) ≳

1 . log n

By contrast, Corollary 1 shows that early-stopped GD achieves the minimax rates n−2a/(2a+1) and log n/n under polynomial and exponential spectral decays, both of which vanish strictly faster than 1/ log n. Taken together, early stopping is sufficient for minimax optimality in these canonical FCD spectral regimes, and necessary when additionally, d is mildly overparameterised, e.g., d ≍ n log n.

5

Conclusion

We show that early-stopped GD on the logistic loss for Gaussian mixture classification is minimax-optimal for covariance spectra with fast and continuous decay, including polynomial and exponential decays (Theorem 3). The corresponding minimax rates are explicit (Corollary 1) and closely matched by empirical performance of GD (Figure 2). We further show that early stopping can be substantially more sampleefficient than interpolation in common overparameterised regimes (Theorem 4), establishing a statistical separation between the two, and thus the necessity of early stopping to achieve minimax optimality. 10

The stopping time studied in our work is oracle-based. This is standard in statistical analyses of early stopping [8; 41; 22; 27; 40], where the stopping rule commonly identifies the statistically-optimal scale given by a bias-variance decomposition. Thus, our stopping time should be viewed as an existence result, rather than an algorithm ready to be deployed in practice. Existing data-dependent rules are best understood in regression settings such as non-parametric least squares [28], where the losses used in testing and training coincide. Extending such guarantees to noisy classification with logistic loss presents additional challenges. For instance, our theory aims to minimise the zero-one risk, but the logistic loss is used instead as a surrogate.

11

References [1] Navid Ardeshir, Clayton Sanford, and Daniel J Hsu. Support vector machines and linear regression coincide with very high-dimensional features. Advances in Neural Information Processing Systems, 34: 4907–4918, 2021. [2] Yaroslav Averyanov and Alain Celisse. Early stopping and polynomial smoothing in regression with reproducing kernels. arXiv preprint arXiv:2007.06827, 2020. [3] Francis Bach. Learning theory from first principles. MIT press, 2024. [4] Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. The Annals of Statistics, 33(4), August 2005. [5] Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138–156, 2006. [6] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30063–30070, 2020. [7] Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4):1167–1180, 2020. [8] Peter Bühlmann and Bin Yu. Boosting With the L2 Loss. Journal of the American Statistical Association, 98(462):324–339, 2003. [9] Yuan Cao, Quanquan Gu, and Misha Belkin. Risk bounds for over-parameterized maximum margin classification on sub-gaussian mixtures. In Advances in Neural Information Processing Systems, 2021. [10] A. Caponnetto and E. De Vito. Optimal Rates for the Regularized Least-Squares Algorithm. Foundations of Computational Mathematics, 7(3):331–368, July 2007. [11] Niladri S. Chatterji and Philip M. Long. Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime. Journal of Machine Learning Research, 22(129):1–30, 2021. [12] Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for highdimensional binary linear classification. Information and Inference: A Journal of the IMA, 11(2): 435–495, 2022. [13] Ichiro Hashimoto, Stanislav Volgushev, and Piotr Zwiernik. Universality of benign overfitting in binary linear classification. arXiv preprint arXiv:2501.10538, 2025. [14] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Series in Statistics. Springer, 2 edition, 2009. [15] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. Annals of statistics, 50(2):949, 2022. [16] Daniel Hsu, Vidya Muthukumar, and Ji Xu. On the proliferation of support vectors in high dimensions. In International Conference on Artificial Intelligence and Statistics, pages 91–99. PMLR, 2021. [17] Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1772–1798. PMLR, 25–28 Jun 2019. [18] Abla Kammoun and Mohamed-Slim Alouini. On the precise error analysis of support vector machines. IEEE Open Journal of Signal Processing, 2:99–118, 2021.

12

[19] Varun Kanade, Patrick Rebeschini, and Tomas Vaškevičius. The statistical complexity of early-stopped mirror descent. Information and Inference: A Journal of the IMA, 12(4):3010–3041, 2023. [20] Ganesh Ramachandra Kini and Christos Thrampoulidis. Analytic study of double descent in binary classification: The impact of loss. In International Symposium on Information Theory, pages 2527–2532. IEEE, 2020. [21] Vladimir Koltchinskii and Karim Lounici. Concentration inequalities and moment bounds for sample covariance operators. Bernoulli, pages 110–133, 2017. [22] Junhong Lin and Lorenzo Rosasco. Optimal rates for multi-pass stochastic gradient methods. Journal of Machine Learning Research, 18(97):1–47, 2017. [23] Francesca Mignacco, Florent Krzakala, Yue Lu, Pierfrancesco Urbani, and Lenka Zdeborova. The role of regularization in classification of high-dimensional noisy gaussian mixture. In International conference on machine learning, pages 6874–6883. PMLR, 2020. [24] Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime. The Annals of Statistics, 53(2):822 – 853, 2025. [25] Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpolation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 1(1):67–83, 2020. [26] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparameterized regimes: does the loss function matter? J. Mach. Learn. Res., 22(1), January 2021. [27] Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. Advances in Neural Information Processing Systems, 31, 2018. [28] Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Early stopping and non-parametric regression: an optimal data-dependent stopping rule. The Journal of Machine Learning Research, 15(1):335–366, 2014. [29] Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The Impact of Regularization on High-dimensional Logistic Regression. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. [30] Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The performance analysis of generalized margin maximizers on separable data. In International conference on machine learning, pages 8417–8426. PMLR, 2020. [31] Ohad Shamir. Gradient methods never overfit on separable data. Journal of Machine Learning Research, 22(85):1–20, 2021. [32] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70):1–57, 2018. [33] Arun Sai Suggala, Adarsh Prasad, and Pradeep Ravikumar. Connecting optimization and regularization paths. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, page 10631–10641, Red Hook, NY, USA, 2018. Curran Associates Inc. [34] Pragya Sur and Emmanuel J. Candès. A modern maximum-likelihood theory for high-dimensional logistic regression. Proceedings of the National Academy of Sciences, 116(29):14516–14525, 2019.

13

[35] Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. Journal of Machine Learning Research, 24(123):1–76, 2023. [36] Alexander Tsigler, Luiz FO Chamon, Spencer Frei, and Peter L Bartlett. Benign overfitting and the geometry of the ridge regression solution in binary classification. arXiv preprint arXiv:2503.07966, 2025. [37] Ke Wang and Christos Thrampoulidis. Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting, and Regularization. SIAM Journal on Mathematics of Data Science, 4(1):260–284, 2022. [38] Yuting Wei, Fanny Yang, and Martin J Wainwright. Early stopping for kernel boosting algorithms: A general analysis with localized complexities. IEEE Transactions on Information Theory, 65(10): 6685–6703, 2019. [39] Jingfeng Wu, Peter L Bartlett, Jason D Lee, Sham M Kakade, and Bin Yu. Risk comparisons in linear regression: Implicit regularization dominates explicit regularization. arXiv preprint arXiv:2509.17251, 2025. [40] Jingfeng Wu, Peter L. Bartlett, Matus Telgarsky, and Bin Yu. Benefits of early stopping in gradient descent for overparameterized logistic regression. In Proceedings of the 42nd International Conference on Machine Learning. JMLR.org, 2025. [41] Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On Early Stopping in Gradient Descent Learning. Constructive Approximation, 26(2):289–315, August 2007. [42] Tong Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56–85, 2004.

14

Technical Appendices Contents A Gaussian Mixtures Model Properties

16

B Proofs Omitted from Section 2 17 B.1 Population Logistic Risk Minimiser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 B.2 Optimisation Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 C Proof of the Early-Stopped GD Upper Bound 20 C.1 Zero-One to Logistic Calibration via Σ-geometry . . . . . . . . . . . . . . . . . . . . . . . . . 20 C.2 Effective Rank and Empirical Covariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 C.2.1 Effective Rank of Population Covariances . . . . . . . . . . . . . . . . . . . . . . . . . 23 C.2.2 Spectral Control of the Empirical Covariance via Effective Rank . . . . . . . . . . . . 24 C.3 Localisation and Concentrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 C.3.1 Useful Properties of G(r) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 C.3.2 Empirical Excess Logistic Risk Concentration on G(r) . . . . . . . . . . . . . . . . . . 27 C.3.3 Empirical Excess Logistic Risk Concentration on B . . . . . . . . . . . . . . . . . . . . 31 C.4 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 D Proof of the Statistical Lower Bound 34 D.1 A Triangle Inequality for Excess Zero-One Risk . . . . . . . . . . . . . . . . . . . . . . . . . . 35 D.2 Information Theory Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 D.3 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 E Proofs for Fast and Continuously Decaying Spectrum

41

F Proof of the Interpolation Lower Bound 44 F.1 Setup via Whitening and Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 F.2 Preliminary Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 F.3 Signal Component Induces Large Negative Margins on Constant Fraction of Samples . . . . . 46 F.4 Nuisance Component Cannot Fix Large Negative Margins for Affected Samples . . . . . . . . 48 F.5 Proof of Theorem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Additional Notation We will use additional notation throughout the supplementary material. For a positive integer k, we will denote [k] = {1, 2, . . . , k}. Given a symmetric positive definite matrix matrix M ∈ Rd×d , we use λi (M) d to denote its p i-th largest eigenvalue. For vectors x, y ∈ R , we denote their M-induced inner product as ⟨x, y⟩Σ = x⊤ Σy. We use fX to denote the PDF of the random variable X, and ϕ and Φ to denote the PDF and CDF, respectively, of N (0, 1). Throughout our proofs, we will denote the sigmoid function by σ(z) =

1 , 1 + exp(−z)

and the population covariance of the covariates by Γ = Cov(X) = Cov(Ye µ + ε) = Σ + µµ⊤ .

15

A

Gaussian Mixtures Model Properties

In this section, we collect some useful properties of the Gaussian mixtures model introduced in (1). Lemma 5 (Conditional probabilities and excess zero-one risk). For Gaussian mixtures, we have for y ∈ {±1} and x ∈ Rd , P(Ye = y | X = x) = σ(2yx⊤ w∗ ), P(Y = y | X = x) = p + (1 − 2p)σ(2yx⊤ w∗ ). Moreover, for any w ∈ Rd , the excess zero-one risk can be expressed as   E(w) − E(w∗ ) = (1 − 2p)E | tanh(X ⊤ w∗ )|1{sign(X ⊤ w) ̸= sign(X ⊤ w∗ )} .

(8)

Proof. Although these results are well-known, we prove them here for completeness. Start by noting that for ye ∈ {±1}, X | Ye = ye ∼ N (e y µ, Σ). Together with the fact that P(Ye = ±1) = 1/2, the Bayes’ rule gives: P(Ye = 1 | X = x) =

fX|Ye =1 (x) fX|Ye =1 (x) + fX|Ye =−1 (x)

= σ(2x⊤ Σ−1 µ) = σ(2x⊤ w∗ ).

Since σ(−t) = 1 − σ(t), P(Ye = y | X = x) = σ(2yx⊤ w∗ ). Furthermore, since Ye is flipped with probability p ∈ [0, 0.5) to obtain Y , we have P(Y = y | X = x) = p + (1 − 2p)σ(2yx⊤ w∗ ) . Finally, conditioning on X and computing the excess zero-one risk gives   E(w) − E(w∗ ) = E |2P(Y = 1 | X) − 1|1{sign(X ⊤ w) ̸= sign(X ⊤ w∗ )} , and (8) follows from the identity tanh(z) = 2σ(2z) − 1. 2

Lemma 6 (Subgaussian covariates). For any w ∈ Rd , X ⊤ w is subgaussian with variance proxy ∥w∥Γ . Consequently, for any t > 0, ! 2 t P(|X ⊤ w| > t) ≤ 2 exp − . (9) 2 2 ∥w∥Γ Proof. Fix any w ∈ Rd and any t ∈ R. Then, by the independence of Ye and ε ∼ N (0, Σ), we have  2  t ⊤ E[exp(tX ⊤ w)] = E[exp(tYe µ⊤ w)]E[exp(tε⊤ w)] = cosh(tµ⊤ w) exp w Σw 2  2   2   2  t t t 2 ≤ exp (w⊤ Σw + (µ⊤ w)) = exp w⊤ Γw = exp ∥w∥Γ . 2 2 2 2

Thus, X ⊤ w is subgaussian with variance proxy ∥w∥Γ . The concentration inequality (9) follows from a Chernoff bound.

16

B

Proofs Omitted from Section 2

B.1

Population Logistic Risk Minimiser

We restate Lemma 1 and detail its proof. Lemma 1 (Population logistic risk minimiser). The minimiser of L(w) over Rd is unique and has the form ∗ wL = ρ∗ w∗ where ρ∗ ∈ (0, 2]. Proof. Recall that w∗ = Σ−1 µ. Fix an arbitrary w ∈ Rd and decompose it as w = ρw∗ + u, where ρ = w⊤ µ/(w∗ )⊤ µ ∈ R

and u = w − ρw∗

By construction, u⊤ µ = 0, so w is split into a component along the signal direction w∗ and a component u orthogonal to µ. Step 1: We first prove that each minimiser of L(·) satisfies u = 0d , i.e., it lies along w∗ . For this, let T ∗ = X ⊤ w∗ and Tu = X ⊤ u. These random variables are independent. Indeed, since w∗ = Σ−1 µ and u⊤ µ = 0, we have 2 T ∗ = (Ye µ + ε)⊤ w∗ = Ye ∥µ∥Σ−1 + ε⊤ w∗ , Tu = (Ye µ + ε)⊤ u = ε⊤ u.

(10) (11)

These are independent because Ye is independent of ε and the Gaussians ε⊤ w∗ and ε⊤ u are uncorrelated: Cov(ε⊤ w∗ , ε⊤ u) = u⊤ Σw∗ = 0. Now, for t, s ∈ R, define ζ(t) = p + (1 − 2p)σ(2t),

ϑt (s) = ζ(t)ℓ(s) + (1 − ζ(t))ℓ(−s) ,

(12)

where recall σ(z) = 1/(1 + exp(−z)) denotes the sigmoid function and ℓ(z) = log(1 + exp(−z)) denotes the logistic loss. Then, using the decomposition of w and the tower law, we can write L(w) = E[ℓ(Y X ⊤ w)] = E[ℓ(Y X ⊤ (ρw∗ + u))] = E[ℓ(Y (ρT ∗ + Tu ))] = E [E[ℓ(Y (ρT ∗ + Tu )) | X]] = E[ϑT ∗ (ρT ∗ + Tu )] , where the last step applies P(Y = 1 | X) = ζ(T ∗ ) due to Lemma 5. Since ℓ′′ > 0, the function ϑt is strictly convex for any t ∈ R. Hence, conditioning on T ∗ and applying the tower law, we can write L(w) = E[ϑT ∗ (ρT ∗ + Tu )] = E [E[ϑT ∗ (ρT ∗ + Tu ) | T ∗ ]] (i)

(ii)

≥ E [ϑT ∗ (ρT ∗ + E[Tu | T ∗ ])] = E[ϑT ∗ (ρT ∗ )] = L(ρw∗ ) ,

where (i) is Jensen’s inequality applied to the strictly convex function ϑT ∗ , and (ii) uses the independence of T ∗ and Tu , together with E[Tu ] = 0. Equality in (i) holds if and only if Tu = 0, which implies u = 0d .

17

Step 2: We have shown every minimiser of L(·) in Rd takes the form ρw∗ , so it remains to minimise over ρ. For this, we study the function f (ρ) = L(ρw∗ ). 2 To begin, by noticing T ∗ = X ⊤ w∗ = (Ye µ + ε)⊤ w∗ = Ye ∥µ∥Σ−1 + ε⊤ w∗ and ε⊤ w∗ ⊥ Ye , we have

E[T ∗ Ye ] = µ⊤ Σ−1 µ = ∥µ∥2Σ−1 .

(13)

Thus, we can write (i)

E[T ∗ ζ(T ∗ )] = 21 E[T ∗ (2ζ(T ∗ ) − 1)] (ii) 1 ∗e = 2 E[T ∗ E[Y | X]] = 12 E[T ∗ Y ] = 1−2p 2 E[T Y ] (iii) 1−2p 2 = 2 ∥µ∥Σ−1 ,

(14)

where (i) uses E[T ∗ ] = 0, (ii) holds because P(Y = 1 | X) = ζ(T ∗ ) from Lemma 5 implies E[Y | X] = 2P(Y = 1 | X) − 1 = 2ζ(T ∗ ) − 1, and (iii) applies (13). Let ϑt (s), ζ(t) be defined as in (12), then note that the derivative ϑ′t (s) = σ(s) − ζ(t). Using this and applying (14), we obtain d E[ϑT ∗ (ρT ∗ )] = E[T ∗ ϑ′T ∗ (ρT ∗ )] = E[T ∗ (σ(ρT ∗ ) − ζ(T ∗ ))] dρ = E[T ∗ σ(ρT ∗ )] − E[T ∗ ζ(T ∗ )]

f ′ (ρ) =

2

= E[T ∗ σ(ρT ∗ )] − 1−2p 2 ∥µ∥Σ−1 .

(15)

Setting f ′ (ρ∗ ) = 0 and rearranging, any stationary point ρ∗ of f (·) satisfies 2

E[T ∗ σ(ρ∗ T ∗ )] = 1−2p 2 ∥µ∥Σ−1 . Step 3: The final step is to show that f (·) has a unique stationary point ρ∗ ∈ (0, 2] and that it is a minimiser. Since σ ′ (z) > 0 for all z ∈ R and T ∗ ̸= 0 almost surely, we have f ′′ (ρ) = E[(T ∗ )2 σ ′ (ρT ∗ )] > 0 , meaning f is strictly convex. Hence, ρ∗ is the unique minimiser of f (·). Finally, note that ρ∗ ∈ (0, 2] because f ′ (0) < 0 and f ′ (2) ≥ 0. Indeed, Eq. (15) implies that 2

2

1−2p f ′ (0) = 21 E[T ∗ ] − 1−2p 2 ∥µ∥Σ−1 = − 2 ∥µ∥Σ−1 < 0 ,

and 2

f ′ (2) = E[T ∗ σ(2T ∗ )] − 1−2p 2 ∥µ∥Σ−1 (i) 1 2 = 2 E [T ∗ (2σ(2T ∗ ) − 1)] − 1−2p 2 ∥µ∥Σ−1 (ii) 1 2 = 2 E[T ∗ Ye ] − 1−2p 2 ∥µ∥Σ−1 (iii) 1 2 2 2 = 2 ∥µ∥Σ−1 − 1−2p 2 ∥µ∥Σ−1 = p ∥µ∥Σ−1 ≥ 0 ,

where (i) uses E[T ∗ ] = 0, (ii) holds because P(Ye = 1 | X) = σ(2T ∗ ) from Lemma 5 implies E[Ye | X] = 2P(Ye = 1 | X) − 1 = 2σ(2T ∗ ) − 1, and (iii) applies (13).

18

B.2

Optimisation Lemmas

As detailed in Section 2, we train a linear classifier on the Gaussian mixture samples by minimising the b via early-stopped GD. To analyse the optimisation, we first establish the Lipschitz empirical logistic risk L(·) b and smoothness properties of L(·), then characterise the stopping time τ (Lemma 2) and the early-stopped GD iterate wτ (Lemma 3). Throughout this section, we will denote 2

β :=

∥X1:n ∥ . n

b is Lemma 7 (Lipschitz and smoothness). The empirical logistic risk L(·) b ≤ ∇L(w)

sup

p β

and

sup

w∈Rd

√

β-Lipschitz and β-smooth, i.e.,

b ≤ β. ∇2 L(w)

w∈Rd

Proof. Recall ∥X1:n ∥ denotes the spectral norm of X1:n . Let a(w) ∈ Rn be the vector whose i-th coordinate d b is defined as [a(w)]i = Yi /(1 + exp(Yi Xi⊤ w)). Then we have ∇L(w) = − n1 X⊤ 1:n a(w) ∈ R . Since the √ entry-wise absolute value |[a(w)]i | ≤ 1 for all i ∈ [n], we have ∥a(w)∥ ≤ n and so b ∇L(w) ≤

∥X1:n ∥ ∥a(w)∥ ∥X1:n ∥ p ≤ √ = β. n n

d×d b = n1 X⊤ For the Hessian, note that ∇2 L(w) , where D(w) is the n × n diagonal matrix 1:n D(w)X1:n ∈ R ′′ ⊤ whose i-th diagonal entry is [D(w)]ii = ℓ (Yi Xi w). Since 0 ≤ ℓ′′ (z) ≤ 1/4 for all z ∈ R, we have 2

b ∇2 L(w) ≤

∥X1:n ∥ ∥X1:n ∥ ∥D(w)∥ ∥X1:n ∥ ≤ ≤ β. n 4n

We next restate Lemmas 2 and 3 and provide their proofs, respectively. Lemma 2 (Existence of τ ). Suppose n ≤ d. Then ∥wt ∥ → ∞ as t → ∞ almost surely, and so τ = inf{t ≥ 1 : ∥wt ∥ ≥ 4 ∥w∗ ∥} is finite. Proof. When n ≤ d, we have rank(X1:n ) = n almost surely, since the covariates X = Ye µ + N (0, Σ) have a continuous density on Rd and are therefore linearly independent almost surely. Then, linear separability of the training samples follows from [40, Proposition 2.2]. On linearly-separable data, the implicit bias of GD under logistic loss [32; 31] implies ∥wt ∥ → ∞ as t → ∞, so τ is finite. Lemma 3 (Properties of the early-stopped iterate). The early-stopped iterate wτ satisfies the following: (i) b τ ) ≤ L(w b ∗ ). ∥wτ ∥ < 4 ∥w∗ ∥ + 1; and (ii) L(w L Proof. Proof of part (i): By the definition of the stopping time τ := inf{t ≥ 1 : ∥wt ∥ ≥ 4 ∥w∗ ∥}, we have ∥wτ −1 ∥ < 4 ∥w∗ ∥. Using the GD update rule, Lemma 7, and the choice of step size γ ≤ min(1/β, 1) in Section 2, we can write b τ −1 ) ≤ γ ∥wτ − wτ −1 ∥ = γ ∇L(w

p

β≤

√

γ·

p

γβ ≤

Hence, by the triangle inequality, ∥wτ ∥ ≤ ∥wτ −1 ∥ + ∥wτ − wτ −1 ∥ < 4 ∥w∗ ∥ + 1.

19

√

γ ≤ 1.

b τ ) > L(w b ∗ ). Since L(·) b is β-smooth and Proof of part (ii): Suppose, towards a contradiction, that L(w L ∗ the step size γ ≤ 1/β, Lemma 3.3 in [40] with the comparator wL gives 2

2

∗ ∗ ∥wτ − wL ∥ ∥wL ∥ ∗ b τ ) ≤ L(w b L + L(w . )+ 2γτ 2γτ

b τ ) > L(w b ∗ ) then forces ∥wτ − w∗ ∥ < ∥w∗ ∥. But by the definition of the stopping Our assumption L(w L L L ∗ time τ , the triangle inequality, and ∥wL ∥ = ∥ρ∗ w∗ ∥ ≤ 2 ∥w∗ ∥ due to Lemma 1, we arrive at a contradiction: ∗ ∗ ∗ 4 ∥w∗ ∥ ≤ ∥wτ ∥ ≤ ∥wτ − wL ∥ + ∥wL ∥ < 2 ∥wL ∥ ≤ 4 ∥w∗ ∥ .

C

Proof of the Early-Stopped GD Upper Bound

We prove the excess zero-one risk upper bound of Theorem 1 for the early-stopped iterate wτ via a sequence of lemmas (Sections C.1–C.3.3), culminating in the proof of Theorem 1 at the end of this section (Section C.4). Throughout, for symmetric matrices A, B ∈ Rd×d , we write A ≻ B (resp. ⪰) to mean that A − B is positive definite (resp. positive semidefinite), i.e., h⊤ (A − B)h > 0 (resp. ≥ 0) for all h ∈ Rd .

C.1

Zero-One to Logistic Calibration via Σ-geometry

In this section, we prove the calibration result in Lemma 4, which upper bounds the excess zero-one risk by ∗ ∥Σ as a bridge the excess logistic risk. The key technique is to introduce the Σ-geometry distance ∥w − wL ∗ between the two risks: Lemma 8 upper bounds the excess zero-one risk by ∥w − wL ∥Σ , while Lemma 9 ∗ allows us to lower bound the excess logistic risk by ∥w − wL ∥Σ . Combining the two yields Lemma 4. d ∗ To begin, we show in Lemma 8 that if w ∈ R is sufficiently close to wL in the Σ-norm, then its excess ∗ ∗ zero-one risk E(w) − E(w ) can be upper bounded by ∥w − wL ∥Σ . Lemma 8 (Σ-geometry calibration of excess zero-one risk). Suppose w ∈ Rd satisfies ∗ ∥w − wL ∥Σ ≤

ρ∗ ∥µ∥Σ−1 . 2

(16)

Then, E(w) − E(w∗ ) ≤ √

4(1 − 2p) ∗ 2 ∥w − wL ∥Σ . 2π(ρ∗ )2 ∥µ∥Σ−1

(17)

Proof. Recall w∗ = Σ−1 µ. As in Lemma 1, decompose w = ρw∗ + u with u⊤ µ = 0. We first show that ∗ ρ > 0. Since wL = ρ∗ w∗ , we have 2

2

2

2

∗ ∥w − wL ∥Σ = ∥(ρ − ρ∗ )w∗ + u∥Σ = (ρ − ρ∗ )2 ∥µ∥Σ−1 + ∥u∥Σ ,

(18)

∗ which implies ∥w − wL ∥Σ ≥ |ρ − ρ∗ | ∥µ∥Σ−1 . Combining with the assumption in (16) gives |ρ − ρ∗ | ≤ ρ∗ /2. ∗ Since ρ > 0 (c.f. Lemma 1), it follows that

ρ≥

ρ∗ > 0. 2

(19)

The decomposition w = ρw∗ + u implies X ⊤ w = ρT ∗ + Tu , where T ∗ = X ⊤ w∗ and Tu = X ⊤ u are independent and each can be expanded as in (10)–(11). Applying the excess risk expression (8) of Lemma 5 and applying tanh(z) ≤ |z| yields   E(w) − E(w∗ ) = (1 − 2p)E | tanh(X ⊤ w∗ )|1{sign(X ⊤ w) ̸= sign(X ⊤ w∗ )}   ≤ (1 − 2p)E |X ⊤ w∗ |1{sign(X ⊤ w) ̸= sign(X ⊤ w∗ )} = (1 − 2p)E [|T ∗ |1{sign(ρT ∗ + Tu ) ̸= sign(T ∗ )}] . 20

Since ρ > 0, we have the following event inclusion: ∗

∗

{sign(ρT + Tu ) ̸= sign(T )} ⊆



|Tu | |T | ≤ ρ ∗

 .

2 Note that conditionally on Ye , T ∗ | Ye ∼ N (Ye ∥µ∥2Σ−1 , ∥µ∥Σ−1 ), so the conditional density satisfies √ fT ∗ |Ye (t) ≤ 1/( 2π ∥µ∥Σ−1 ). Since this bound is uniform over Ye ∈ {±1}, the marginal density of T ∗ satisfies √ the same bound fT ∗ (t) ≤ 1/( 2π ∥µ∥Σ−1 ). Therefore, we have

E(w) − E ∗ ≤ (1 − 2p)E [|T ∗ |1{sign(ρT ∗ + Tu ) ̸= sign(T ∗ )}]         |Tu | |Tu | ∗ ∗ ∗ ∗ Tu = (1 − 2p)E E |T |1 |T | ≤ ≤ (1 − 2p)E |T |1 |T | ≤ ρ ρ "Z # "Z # |Tu |/ρ |Tu |/ρ 1 − 2p = (1 − 2p)E |t|fT ∗ (t)dt ≤ √ |t|dt E 2π ∥µ∥Σ−1 −|Tu |/ρ −|Tu |/ρ  2 2 ∥u∥Σ (1 − 2p) 1 − 2p T √ √ = E u = · , ρ2 ρ2 2π ∥µ∥Σ−1 2π ∥µ∥Σ−1 2

2

2

∗ where the last step holds because Tu ∼ N (0, ∥u∥Σ ). Combining this with the bound ∥u∥Σ ≤ ∥w − wL ∥Σ implied by (18), and with (19), we arrive at the result in (17).

∗ ∗ 2 minimises L(·), we do so by ∥Σ . Since wL The next step is to link the excess logistic risk to ∥w − wL ∗ establishing local strong convexity of L(·) around wL . By Lemma 3, we know the early-stopped iterate wτ satisfies ∥wτ ∥ ≤ 4∥w∗ ∥ + 1. We therefore work over the ball

B = {w ∈ Rd : ∥w∥ ≤ R} ,

where

R := 4 ∥w∗ ∥ + 1 .

(20)

∗ ∈ B as well. As we show in Lemma 9 below, the local strong-convexity Clearly w∗ ∈ B and, by Lemma 1, wL parameter of L(·) is given by p α = 21 ℓ′′ (3R ∥Γ∥), where Γ = Cov(X) = µµ⊤ + Σ. (21)

Lemma 9 (Local strong convexity of logistic risk). For every w ∈ B it holds that ∇2 L(w) ⪰ αΓ. Consequently, ∗ L(w) − L(wL )≥

α ∗ 2 ∥w − wL ∥Γ 2

for all w ∈ B.

Proof. Step 1: We first show that for every w ∈ B, ∇2 L(w) ⪰ αΓ. Note that ℓ′′ (z) = ez /(1 + ez )2 is even, so ∇2 L(w) = E[ℓ′′ (Y X ⊤ w)XX ⊤ ] = E[ℓ′′ (X ⊤ w)XX ⊤ ] . Hence, for any h ∈ Rd , h⊤ ∇2 L(w)h = E[ℓ′′ (X ⊤ w)(X ⊤ h)2 ]. To show ∇2 L(w) ⪰ αΓ, it suffices to show that E[ℓ′′ (X ⊤ w)(X ⊤ h)2 ] ≥ αh⊤ Γh .

21

Towards this objective, using the fact that ℓ′′ is even and decreasing on [0, ∞), we have p p ℓ′′ (X ⊤ w) ≥ ℓ′′ (3R ∥Γ∥)1{|X ⊤ w| ≤ 3R ∥Γ∥}, so it follows that p ∥Γ∥) · E[(X ⊤ h)2 1{|X ⊤ w| ≤ 3R ∥Γ∥}] p = 2α · E[(X ⊤ h)2 1{|X ⊤ w| ≤ 3R ∥Γ∥}]. p It remains to show that E[(X ⊤ h)2 1{|X ⊤ w| ≤ 3R ∥Γ∥}] ≥ 21 h⊤ Γh, or, equivalently, p p E[(X ⊤ h)2 1{|X ⊤ w| > 3R ∥Γ∥}] = E[(X ⊤ h)2 ] − E[(X ⊤ h)2 1{|X ⊤ w| ≤ 3R ∥Γ∥}] p = h⊤ Γh − E[(X ⊤ h)2 1{|X ⊤ w| ≤ 3R ∥Γ∥}] E[ℓ′′ (X ⊤ w)(X ⊤ h)2 ] ≥ ℓ′′ (3R

p

≤ 12 h⊤ Γh. We do this as follows: starting with Cauchy-Schwarz, q q p p E[(X ⊤ h)2 1{|X ⊤ w| > 3R ∥Γ∥}] ≤ E[(X ⊤ h)4 ] P(|X ⊤ w| > 3R ∥Γ∥).

(22)

(23)

We bound each of the terms under the square roots. For the expectation, note that, since ε ∼ N (0, Σ), Ye 2 = 1 and ε ⊥ Ye , we have E[(X ⊤ h)4 ] = E[(Ye µ⊤ h + ε⊤ h)4 ] = (µ⊤ h)4 + 6(µ⊤ h)2 (h⊤ Σh) + 3(h⊤ Σh)2 ≤ 3((µ⊤ h)2 + (h⊤ Σh))2 = 3(h⊤ Γh)2 . For the probability term, using Lemma 6 and the fact that ∥w∥ ≤ R,   p
9R2 ∥Γ∥ ⊤ P(|X w| > 3R ∥Γ∥) ≤ 2 exp − ⊤ ≤ 2 exp − 92 . 2w Γw

(24)

(25)

Plugging (24) and (25) into (23), we arrive at √ p √
 2 exp − 49 ≤ 12 h⊤ Γh, E[(X ⊤ h)2 1{|X ⊤ w| > 3R ∥Γ∥}] ≤ ( 3h⊤ Γh) · which establishes (22) and hence for every w ∈ B, ∇2 L(w) ⪰ αΓ. Step 2: For the excess logistic risk lower bound, using the second-order Taylor expansion of w ∈ B around ∗ ∗ such that ∈ B, there is some ξ ∈ B on the line connecting w and wL wL ∗ ∗ ⊤ ∗ ∗ ⊤ 2 ∗ L(w) − L(wL ) ≥ ∇L(wL ) (w − wL ) + 21 (w − wL ) ∇ L(ξ)(w − wL ) α ∗ ⊤ 2 ∗ ∗ 2 1 ≥ 2 (w − wL ) ∇ L(ξ)(w − wL ) ≥ ∥w − wL ∥Γ . 2 ∗ where the first term vanishes by the first-order optimality condition ∇L(wL ) = 0 (c.f. Lemma 1).

We now restate Lemma 4 and prove it by combining Lemmas 8–9 above. Lemma 4 (Linear-rate calibration for linear classifiers). Let w ∈ Rd satisfy ∥w∥ ≤ 4∥w∗ ∥ + 1 and ∗ L(w) − L(wL )≤

where α = 12 ℓ′′ 3(4∥w∗ ∥ + 1)

α(ρ∗ )2 ∥w∗ ∥2Σ , 8

p
∥Σ + µµ⊤ ∥ . Then,

E(w) − E(w∗ ) ≤ √

8(1 − 2p) ∗ (L(w) − L(wL )) . 2πα(ρ∗ )2 ∥w∗ ∥Σ 22

(5)

Proof. Recall Γ = µµ⊤ + Σ so Γ ⪰ Σ. Together with Lemma 9, we have 2

2

∗ ∗ ∥w − wL ∥Σ ≤ ∥w − wL ∥Γ ≤

2 ∗ (L(w) − L(wL )). α

Using the assumption in (5), this implies ∗ ∥w − wL ∥Σ ≤

ρ∗ ∥w∗ ∥Σ ρ∗ ∥µ∥Σ−1 = . 2 2

We can now apply Lemma 8 to conclude: E(w) − E(w∗ ) ≤ √

4(1 − 2p) 2 4(1 − 2p) ∗ 2 ∗ (L(w) − L(wL )) . ∥w − wL ∥Σ ≤ √ 2π(ρ∗ )2 ∥µ∥Σ−1 2π(ρ∗ )2 ∥µ∥Σ−1 α

By Lemma 3, the early-stopped iterate wτ lies in the ball B, so Lemma 4 reduces the problem of bounding ∗ the population excess zero-one risk to bounding the population excess logistic risk L(wτ ) − L(wL ), which admits the decomposition below in (26). By Lemma 3 (ii), Term I of (26) is non-positive. Hence, it remains to control the uniform deviation between the empirical and population excess logistic risks, i.e., Term II of (26), and we do so using empirical process theory. ∗ L(wτ ) − L(wL )=

   ∗ ∗ ∗ b τ ) − L(w b L b τ ) − L(w b L )) − L(w ) . L(w ) + (L(wτ ) − L(wL {z } | {z } | 

(26)

Term II: controlled by empirical process theory

Term I≤0 by Lemma 3 (ii)

To this end, a direct uniform convergence bound over the entire ball B would be too loose. To obtain a sharper upper bound in terms of the effective rank of Σ, we exploit the fact that wτ has small excess ∗ risk, confining it to a thin shell around wL within B. This localisation yields a smaller function class with better-controlled complexity, which we detail in Section C.3. For clarity, we first recall in Section C.2 the definition of the effective rank and establish a key spectral property of the empirical covariance of the covariates (Xi )ni=1 in terms of the effective rank. We then present the localisation and concentrations proofs in Section C.3.

C.2

Effective Rank and Empirical Covariance

We define the effective rank and establish two spectral properties in terms of the effective rank (Lemmas 10– 11) which will be used in the sequel. C.2.1

Effective Rank of Population Covariances

Recall that in our Gaussian mixture model, the population covariance of the noise variable ε is Σ, while that of the covariates X is Γ = Σ + µµ⊤ . Both matrices induce geometries that play a role in our analysis, so we introduce the effective rank for each and use Σ or Γ as a superscript to avoid any confusion. For any η > 0, define the regularised matrices Ση := Σ + ηId and Γη := Γ + ηId , and define Σ −1 reff (η) := tr(ΣΣ−1 )= η ) = tr(Σ(Σ + ηId )

Γ −1 reff (η) := tr(ΓΓ−1 )= η ) = tr(Γ(Γ + ηId )

d X

λi (Σ) , λ (Σ) + η i=1 i

d X

λi (Γ) . λ (Γ) + η i i=1

Note that throughout the main text we only work with the effective rank associated with Σ, and so we Σ Σ Γ write reff (η) to refer to reff (η) for brevity. In the appendices, both reff (η) and reff (η) appear, so we retain the superscripts for clarity. We show in Lemma 10 that the two effective ranks differ by at most 1. 23

Lemma 10 (Effective ranks of Σ and Γ). For any η > 0, Σ Γ Σ reff (η) ≤ reff (η) ≤ reff (η) + 1. Γ Σ −1 Proof. It suffices to show 0 ≤ reff (η) − reff (η) ≤ 1. Note the identities ΣΣ−1 and ΓΓ−1 η = Id − ηΣη η = −1 Id − ηΓη . Then the Sherman-Morrison formula applied to Ση ≻ 0 gives

(Ση + µµ⊤ )−1 = Σ−1 η −

⊤ −1 Σ−1 η µµ Ση

1 + µ⊤ Σ−1 η µ

,

so we have Γ Σ −1 reff (η) − reff (η) = tr(ΓΓ−1 η − ΣΣη ) −1 = tr(Id − ηΓ−1 η − Id + ηΣη ) ⊤ −1 = η tr(Σ−1 ) η − (Ση + µµ )

= =

⊤ −1 η tr(Σ−1 η µµ Ση )

1 + µ⊤ Σ−1 η µ ηµ⊤ Σ−2 η µ 1 + µ⊤ Σ−1 η µ

.

Γ Σ Γ Σ −2 Since Σ−1 η , Ση ≻ 0, we clearly have reff (η) − reff (η) ≥ 0. Next, to show reff (η) − reff (η) ≤ 1, it suffices to show ⊤ −1 ηµ⊤ Σ−2 η µ ≤ µ Ση µ. −1 −1 −1 This holds because Ση ⪰ ηId , so that Σ−2 Ση , i.e., ηΣ−2 η ⪯η η ⪯ Ση .

C.2.2

Spectral Control of the Empirical Covariance via Effective Rank

Now, define the empirical covariance of the covariates as n X b := 1 Γ Xi Xi⊤ , n i=1

and define the good event b −1/2 || ≤ 2} , Ecov := {||Γ−1/2 ΓΓ η η

(27)

on which the empirical covariance is well-behaved in that it does not introduce spurious high-variance directions, and is spectrally controlled relative to the regularised population covariance Γη . We show in Lemma 11 that the event Ecov holds with high probability, whenever the sample size n is sufficiently large Γ relative to reff (η). Lemma 11 (Spectral control of the empirical covariance). There exists a universal constant c > 0 such that the following holds: Fix η > 0. For every δ ∈ (0, 1), if Γ n ≥ c(reff (η) + log(1/δ)) ,

then we have P(Ecov ) ≥ 1 − δ. Proof. We split this proof into three steps:

24

−1/2

Step 1: The random vector Γη with variance proxy 2, i.e.,

X ∈ Rd has mean zero. In this step, we show that it is also subgaussian

  2 E[exp(tu⊤ Γ−1/2 X)] ≤ exp t2 ∥u∥ η

for all u ∈ Rd , t ∈ R.

(28)

Fix arbitrary u ∈ Rd and t ∈ R and note that ⊤ −1/2 u⊤ Γ−1/2 X = Ye u⊤ Γ−1 ε. η η µ + u Γη | {z } | {z } signal term

noise term

The two terms are independent, so we can bound their moment generating functions (MGFs) individually. For the signal term, as Ye is symmetric ±1, using cosh(z) ≤ exp(z 2 /2), we have ! 2 ⊤ −1/2 2 t (u Γ µ) η ⊤ −1/2 ⊤ −1/2 . E[exp(tYe u Γη µ)] = cosh (tu Γη µ) ≤ exp 2 −1/2

We next bound (u⊤ Γη

µ)2 . By Cauchy-Schwarz and the fact that Γη = Γ + ηId ⪰ Γ, 2

2

⊤ −1 (u⊤ Γ−1/2 µ)2 ≤ ∥u∥ µ⊤ Γ−1 µ, η η µ ≤ ∥u∥ µ Γ

and moreover, recall that Γ = Σ + µµ⊤ , so by the Sherman-Morrison formula,  
µ⊤ Σ−1 µ Σ−1 µµ⊤ Σ−1 ⊤ −1 ⊤ ⊤ −1 ⊤ −1 µ = ≤ 1. µ Γ µ = µ Σ + µµ µ=µ Σ − 1 + µ⊤ Σ−1 µ 1 + µ⊤ Σ−1 µ Thus, putting together the last three displays yields E[exp(tYe u⊤ Γ−1/2 µ)] ≤ exp η

  2 t 2 ∥u∥ . 2

(29)

For the noise term, as ε ∼ N (0, Σ), Gaussian MGF gives  2  t ⊤ −1/2 ⊤ −1/2 −1/2 E[exp(tu Γη ε)] = exp u Γη ΣΓη u , 2 −1/2

and together with the fact Γη ⪰ Σ which implies Id ⪰ Γη

−1/2

ΣΓη , we obtain  2  t 2 ⊤ −1/2 E[exp(tu Γη ε)] ≤ exp ∥u∥ . 2

(30)

Hence, combining (29) and (30) yields (28), concluding step 1 of the proof. Step 2:

−1/2

Let Zi = Γη

Xi for 1 ≤ i ≤ n, so their empirical covariance takes the form n

1X b −1/2 , Zi Zi⊤ = Γ−1/2 ΓΓ η η n i=1 and define its population covariance as Υ = E[Zi Zi⊤ ] = Γ−1/2 ΓΓ−1/2 = ΓΓ−1 η η η . Γ where note ∥Υ∥ ≤ 1 and tr(Υ) = reff (η). In this step of the proof, we will apply [21, Theorem 9] to bound the spectral norm deviation of the sample −1/2 b −1/2 covariance from the population covariance ∥Γη ΓΓ − Υ∥. To verify the conditions in the hypothesis η of this theorem, note that the Zi ’s are:

25

• weakly-square integrable, i.e., E[(Zi⊤ u)2 ] < ∞ for all u ∈ Rd , which holds as ∥Υ∥ ≤ 1; −1/2 b

• centred and have covariance Υ and empirical covariance Γη

−1/2

ΓΓη

;

• 2-subgaussian; • pregaussian, i.e., there exists a centred Gaussian random vector with the same covariance Υ. Indeed N (0, Υ) satisfies this condition. Then, by [21, Theorem 9], there exists a universal constant c′ > 0 such that, for all t ≥ 1, with probability at least 1 − e−t ! r r r e (Υ) t r e (Υ) t b −1/2 − Υ ≤ c′ ∥Υ∥ max , , , , Γ−1/2 ΓΓ η η n n n n where, using the notation from [21, Definition 1], re(Υ) =

tr(Υ) rΓ (η) = eff . ∥Υ∥ ∥Υ∥

Since ∥Υ∥ ≤ 1, we have r b −1/2 − Υ Γ−1/2 ΓΓ η η

′

≤ c max

−1/2

Γ (η) reff rΓ (η) , eff , n n

r

t t , n n

! .

−1/2

b η || ≤ 2) ≥ 1 − δ. Combining the last display with the Step 3: The final step establishes P(||Γη ΓΓ triangle inequality and setting t = log(1/δ), we obtain with probability at least 1 − δ, b −1/2 ≤ ∥Υ∥ + Γ−1/2 ΓΓ b −1/2 − Υ Γ−1/2 ΓΓ η η η η ! r r Γ Γ (η) r r (η) log(1/δ) log(1/δ) eff ≤ 1 + c′ max , eff , , . n n n n Γ Hence, if n ≥ c(reff (η) + log(1/δ)) for a sufficiently large universal constant c, then ! r r Γ Γ (η) reff reff (η) log(1/δ) log(1/δ) ′ c max , , , ≤ 1, n n n n

and this concludes the proof.

C.3

Localisation and Concentrations

For brevity, we adopt standard notation from empirical process theory. For each w ∈ R, define gw : Rd × {±1} → R by ∗ gw (x, y) := ℓ(yx⊤ w) − ℓ(yx⊤ wL ),

and let P and Pn denote the population and empirical expectation operators, so that ∗ P gw := E[gw (X, Y )] = L(w) − L(wL ), n X 1 ∗ b b L gw (Xi , Yi ) = L(w) − L(w ). Pn gw := n i=1

26

Then,   ∗ ∗ b b L (P − Pn )gw = P gw − Pn gw = (L(w) − L(wL )) − L(w) − L(w ) is the term that we need to bound in the risk decomposition in (26). For any r > 0, we work over the localised function class G(r) = {gw : w ∈ B and P gw ≤ r} , which contains gwL∗ for every r > 0 because P gwL∗ = 0. This class consists of functions indexed by parameters w lying in a localised shell within the ball B. d ∗ Notation-wise, recall the ball B = {w p∈ R : ∥w∥ ≤ R} with R = 4 ∥w ∥ + 1 from (20), and the local 1 ′′ strong-convexity parameter α = 2 ℓ (3R ∥Γ∥) of L(·) over B from Eq. (21). C.3.1

Useful Properties of G(r)

We first present some useful properties of the function class G(r), which we will use in our proofs later in this section. ∗ Lemma 12. If gw ∈ G(r), then ∥w − wL ∥ ≤ 2R and 2

∗ ∥w − wL ∥Γ ≤

2r . α

∗ ∈ B and the triangle inequality. The second Proof. The first inequality is simply by the fact that w, wL inequality is obtained by rearranging the conclusion of Lemma 9 and using P gw ≤ r. ∗ )|. As a consequence, Lemma 13. For every gw ∈ G(r), |gw (X, Y )| ≤ |X ⊤ (w − wL

E[gw (X, Y )2 ] ≤

2r . α

Proof. The first inequality is a consequence of the fact that ℓ is 1-Lipshitz and Y ∈ {±1}, whereas for the second inequality we can apply Lemma 9 to obtain 2

∗ 2 ∗ E[gw (X, Y )2 ] ≤ E[(X ⊤ (w − wL )) ] = ∥w − wL ∥Γ ≤

C.3.2

2P gw 2r ≤ . α α

Empirical Excess Logistic Risk Concentration on G(r)

On the event Ecov , defined in (27) and characterised in Lemma 11, we provide the first uniform concentration bound: it controls how much the empirical excess logistic risk Pn gw deviates from the population excess logistic risk P gw uniformly over all functions gw ∈ G(r). We introduce an auxiliary parameter λ > 0 that we will later optimise over. Lemma 14 (Concentration on G(r)). Assume Ecov holds. Fix r, n, λ > 0 and define ϱr =

2r + 4ηR2 . α

Then, for any δ ∈ (0, 1), with probability at least 1 − δ, rΓ (η) sup (P − Pn )gw ≤ eff + 4λϱr + 5 λn gw ∈G(r) 27

r

ϱr log(1/δ) n

Proof. The proof follows a standard truncation argument. We clip each function gw ∈ G(r) at a threshold mr into a bounded part gw and a tail residual sw . The bounded part is controlled via Rademacher complexity and a Bernstein-type inequality (Steps 1-2), while the tail is bounded in Step 3. Introduce the clipping threshold r nϱr mr = , log(1/δ) and use this to clip each function gw into gw with a tail residue sw , respectively defined as gw := max(−mr , min(gw , mr )),

and

sw := gw − gw

with |sw | ≤ tw := (|gw | − mr )+ .

Denote the corresponding class of clipped functions by G(r) = {gw : gw ∈ G(r)}. Step 1: Bounding ERadn G(r): Recall that for a class F of functions f : Rd × {±1} → R, its Rademacher complexity with respect to the training samples (Xi , Yi )ni=1 is defined as n

1X ϵi f (Xi , Yi ), f ∈F n i=1

Radn F := sup

where ϵi are ±1 Rademacher random variables, and let ϵ = (ϵ1 , . . . , ϵn ). Since the map g 7→ max(−mr , min(g, mr )) is 1-Lipschitz, a standard contraction result (for example, Theorem A.6 in [4]) gives that, conditional on the samples, the expectations over the Rademacher variables ϵ satisfy Eϵ Radn G(r) ≤ Eϵ Radn G(r) . Taking an expectation over all samples, ERadn G(r) ≤ ERadn G(r), and we next upper bound the right hand side. ∗ does not depend on gw , we have To do so, note that, since wL n

Radn G(r) =

1X ∗ ϵi ℓ(Yi Xi⊤ w) − ℓ(Yi Xi⊤ wL ) n gw ∈G(r) i=1

=−

sup

n n 1X 1X ∗ ϵi ℓ(Yi Xi⊤ wL ) + sup ϵi ℓ(Yi Xi⊤ w), n i=1 gw ∈G(r) n i=1

where taking expectation over ϵ (and then over the samples) makes the first term vanish, resulting in n

1X ϵi ℓ(Yi Xi⊤ w). gw ∈G(r) n i=1

ERadn G(r) = E sup

Now, since ℓ is 1-Lipschitz, applying contraction again and using the fact that ϵi Yi are still Rademacher random variables, we obtain n n 1X 1X ϵi Yi Xi⊤ w = E sup ϵi Xi⊤ w. gw ∈G(r) n i=1 gw ∈G(r) n i=1

ERadn G(r) ≤ E sup

28

Next, we can subtract

Pn

⊤ ∗ i=1 ϵi Xi wL because in expectation this is 0, so we arrive at n

1X ∗ ∗ ϵi Xi⊤ (w − wL ERadn G(r) ≤ E sup ) = E sup V ⊤ (w − wL ). n gw ∈G(r) gw ∈G(r) i=1 Pn where we have introduced V = n1 i=1 ϵi Xi ∈ Rd . Next, recall Γη = Γ + ηId and note that for any h ∈ Rd and any λ > 0,   2 2 2 2 1/2 1/2 ⊤ , Γ u + λ Γ1/2 Γ h ≤ sup V u − λ h + λ V ⊤ h = V ⊤ h − λ Γ1/2 η h η η η u∈Rd

∗ therefore, setting h = w − wL and taking supremum over gw ∈ G(r) yields   2 2 ⊤ ∗ ⊤ 1/2 ∗ Γ1/2 sup V (w − wL ) ≤ sup V u − λ Γη u + λ sup . η (w − wL ) gw ∈G(r)

gw ∈G(r)

u∈Rd

Optimising over u in the first supremum we get   2 1 ⊤ 1/2 sup V u − λ Γη µ = Γ−1/2 V η 4λ d u∈R

2

,

whose expectation is 1 E Γ−1/2 V η 4λ

2

1 1 1 E[V ⊤ Γ−1 E[tr(V V ⊤ Γ−1 tr(E[V V ⊤ ]Γ−1 η V]= η )] = η ) 4λ 4λ 4λ Γ (i) 1 (ii) reff (η) = tr(ΓΓ−1 , η ) = 4λn 4λn

=

Γ where (i) uses E[V V ⊤ ] = Γ/n and (ii) applies the definition reff (η) := tr(ΓΓ−1 η ). Finally, for the second supremum, using the fact that Γη = Γ + ηId ,

λ sup gw ∈G(r)

∗ Γ1/2 η (w − wL )

2

2

2

∗ ∗ = λ sup (∥w − wL ∥Γ + η ∥w − wL ∥ ) gw ∈G(r)

 ≤λ

2r + 4ηR2 α

 = λϱr ,

(31)

where the inequality holds because of the two inequalities from Lemma 12. Putting everything together, we arrive at ERadn G(r) ≤

Γ reff (η) + λϱr . 4λn

(32)

Step 2: High-probability bound for gw : Each gw takes values in [−mr , mr ], an interval of length 2mr . Additionally, clipping cannot increase the variance, hence by Lemma 13, sup Var(gw ) ≤ gw ∈G(r)

sup Var(gw ) ≤ gw ∈G(r)

sup E[(gw )2 ] ≤ gw ∈G(r)

2r ≤ ϱr . α

We can now apply Theorem 2.1 in [4] (with F = G(r), x = log(1/δ), α = 1, a = −mr , b = mr , r = ϱr ) to get that, with probability at least 1 − δ, r 2ϱr log(1/δ) 8 log(1/δ) sup (P − Pn )gw ≤ 4ERadn G(r) + + mr . n 3 n gw ∈G(r) 29

Using the bound (32) together with mr log(1/δ)/n = 1 − δ,

p

ϱr log(1/δ)/n, we have that, with probability at least

√ rΓ (η) + 4λϱr + ( 2 + 8/3) sup (P − Pn )gw ≤ eff λn gw ∈G(r)

r

ϱr log(1/δ) . n

(33)

Step 3: Bounding the tail residual: Starting from (|g| − mr )+ ≤ g 2 /4mr valid for all g ∈ R, Lemma 13 gives r 1 ϱr log(1/δ) ϱ = . (34) sup P (|gw | − mr )+ = sup P tw ≤ 4mr 4 n gw ∈G(r) gw ∈G(r) One the empirical side, the same inequality and Lemma 13 gives tw (Xi , Yi ) = (|gw (Xi , Yi )| − mr )+ ≤

∗ ⊤ ∗ gw (Xi , Yi )2 (w − wL ) Xi Xi⊤ (w − wL ) ≤ , 4mr 4mr

so that Pn t w ≤

1 ∗ ⊤b ∗ (w − wL ) Γ(w − wL ). 4mr

1/2 ∗ ∗ ⊤b ∗ ) ) ≤ Γη (w − wL Now, since (w − wL ) Γ(w − wL

2

−1/2 b

1/2

∗ ) Ecov holds and the fact that, by (31), Γη (w − wL

−1/2

ΓΓη

Γη

, with the assumption that the event

2

≤ ϱr ,

2ϱr 1 sup Pn tw ≤ = 4mr 2 gw ∈G(r)

r

ϱr log(1/δ) . n

(35)

Step 4: Conclusion: Using the decomposition gw = gw + sw with |sw | ≤ tw , we have (P − Pn )gw = (P − Pn )gw + P sw − Pn sw ≤ (P − Pn )gw + P tw + Pn tw . Taking a supremum over gw ∈ G(r) and using (33), (34), and (35), we get that, with probability 1 − δ, r Γ √ reff (η) ϱr log(1/δ) sup (P − Pn )gw ≤ + 4λϱr + ( 2 + 35/12 + 1/2) . λn n gw ∈G(r) The conclusion follows by noting that

√

2 + 35/12 + 1/2 < 5.

We now can pick λ conveniently in Lemma 14 and process it further to have only n−1 rates: Corollary 2. Assume Ecov holds. Fix any confidence δ > 0 and any r, η > 0. Then, with probability 1 − δ, sup (P − Pn )gw ≤ gw ∈G(r)

Σ 128(reff (η) + 1) 1 3 log(1/δ) + r + αηR2 + 600 . αn 8 16 αn

√ √ a + b ≤ a + b to arrive at r r Γ 128reff (η) 1 1 50r log(1/δ) 100ηR2 log(1/δ) 2 sup (P − Pn )gw ≤ + r + αηR + + , αn 16 8 αn n gw ∈G(r)

Proof. First, take λ = α/128 in Lemma 14 and then use

30

√

(36)

√ Next, applying the inequality ab ≤ a/16 + 4b to each of the square root terms we have r 1 log(1/δ) 50r log(1/δ) ≤ r + 200 , αn 16 αn r r 100ηR2 log(1/δ) 100αηR2 log(1/δ) 1 log(1/δ) = ≤ αηR2 + 400 . n αn 16 αn Substituting these into (36), we arrive at sup (P − Pn )gw ≤ gw ∈G(r)

Γ 128reff (η) 1 3 log(1/δ) + r + αηR2 + 600 , αn 8 16 αn

Γ Σ and the conclusion follows by using reff ≤ reff + 1 (c.f. Lemma 10).

Now, having proved empirical logistic risks deviation bounds on the shell G(r), we next extend them to the whole of B = {w : ∥w∥ ≤ R} using a peeling argument over r. C.3.3

Empirical Excess Logistic Risk Concentration on B

Σ Lemma 15 (Concentration on B). Fix δ > 0 and η > 0 and assume that n ≥ c0 (reff (η) + log(1/δ)) for some universal constant c0 > 0. With probability at least 1 − 2δ, for any w ∈ B:  Σ  1 reff (η) + log(π 2 /(6δ)) + log log(n) + c′2 ′ 2 (P − Pn )gw ≤ P gw + c1 + αηR , 4 nα

where c′1 and c′2 have the following form: c′1 =

21251 , 12 

c′2 = 1 + log

p 1 + (log2 ((log 2 + R ∥Γ∥)α))+ +

1 log 2

 .

Proof. Given the assumption on the sample size n and Lemma 11, we will work on the event Ecov , which holds with probability at least 1 − δ. Thus, by a Union Bound, we need show that the upper-bound on (P − Pn )gw form the Lemma holds with probability 1 − δ. Step 1: Bounding P gw for w ∈ B: First of all, note that if w ∈ B, i.e. ∥w∥ ≤ R, then p p ∥w∥Γ ≤ ∥w∥ ∥Γ∥ ≤ R ∥Γ∥ := RΓ . ∗ Let MΓ = log 2 + RΓ and note that MΓ ≥ sup P gw = sup (L(w) − L(wL )). Indeed, using 0 ≤ ℓ(z) ≤ w∈B

w∈B

|z| + log 2 and Jensen’s inequality, ∗ sup (L(w) − L(wL )) ≤ sup L(w) = sup E[ℓ(Y X ⊤ w)] ≤ log 2 + sup E[|Y X ⊤ w|] w∈B w∈B w∈B q ≤ log 2+ sup E[(X ⊤ w)2 ] = log 2+ sup ∥w∥Γ ≤ log 2 + RΓ = MΓ .

w∈B

w∈B

w∈B

Step 2: Peeling: Now, for k ≥ 0, set rk = 2−k MΓ and δk = 6δ/(π 2 (k + 1)2 ), so that Note that log(1/δk ) = 2 log(k + 1) + log(π 2 /(6δ)).

31

P

k≥0 δk = δ.

Applying Corollary 2 for all rk and δk (with the same η), we have, by a Union Bound, that with probability 1 − δ, for any k ≥ 0, sup (P − Pn )gw ≤ gw ∈G(r)

Σ 128(reff (η) + 1) 1 3 2 log(k + 1) + log(π 2 /(6δ)) + rk + αηR2 + 600 . αn 8 16 αn

(37)

Step 3: Bounding k: We now claim there exists c′3 , depending on RΓ (through MΓ ) and α only, such that if rk = 2−k MΓ ≥

1 , nα

then log(k + 1) ≤ c′3 + log log(n).

(38)

Indeed, in this case, k ≤ log2 (nαMΓ ), so that k + 1 ≤ 1 + (log2 (MΓ α))+ + log2 (n). But, as log2 (n) = log(n)/ log(2) and, assuming for simplicity n ≥ 3 > e (as otherwise we can replace n by n + e everywhere, log n ≥ 1,   1 log(n). k + 1 ≤ 1 + (log2 (MΓ α))+ + log 2 By taking log again, we arrive at (38) with c′3 = log



1 1 + (log2 (MΓ α))+ + log 2



For the remaining of the proof, we fix w ∈ B, define c′2 = c′3 + 1, and introduce the notation  Σ  reff (η) + log(π 2 /(6δ)) + 2 log log(n) + c′2 ′ 2 Ξ(η) := c1 + αηR . nα Note that, up to constants, this is the same as Ψ(η) in the hypothesis of Theorem 1. Step 4: The case P gw > Ξ(η): Since P gw ≤ MΓ = r0 , there exists some k ≥ 0 such that rk+1 < P gw ≤ rk . In this case gw ∈ G(rk ), so that (37) applies. Additionally, note that rk ≥ P gw > Ξ(η) ≥ c′1

c′2 1 ≥ , nα nα

(39)

as c′1 , c′2 > 1. So, (38) also holds in this case. And, also using rk ≤ 2P gw , we get: Σ 128(reff (η) + 1) 1 3 2c′ + 2 log(log(n)) + log(π 2 /(6δ)) + P gw + αηR2 + 600 3 αn 4 16 αn  Σ  reff (η) + 1 + log(π 2 /(6δ)) + c′3 + log log(n) 1 2 + αηR ≤ P gw + 1200 4 nα  Σ  1 reff (η) + log(π 2 /(6δ)) + log log(n) + c′2 = P gw + c′1 + αηR2 , 4 nα

(P − Pn )gw ≤

where the last inequality from c′2 = c′3 + 1 and c′1 ≥ 1200. Step 5: The case P gw ≤ Ξ(η): In this case, let k be the smallest index with rk ≤ 2Ξ(η). If k = 0, then log(k + 1) ≤ c′3 + log log(n) clearly holds. Otherwise, by minimality, rk−1 > 2Ξ(η), and then rk = rk−1 /2 > Ξ(η), so that again, by (38) and (39), log(k + 1) ≤ c′3 + log log(n). Moreover, since P gw ≤ Ξ(η) < rk , we have gw ∈ G(rk ) and so (37) applies. Using rk ≤ 2Ξ(η): (P − Pn )gw ≤

Σ 128(reff (η) + 1) 1 3 2c′ + 2 log log(n) + log(π 2 /(6δ)) + Ξ(η) + αηR2 + 600 3 . αn 4 16 αn

32

By the definition of Ξ(η) and the fact that c′2 = c′3 + 1 > 1, we have the following: Σ 128(reff (η) + 1) 128 ≤ ′ Ξ(η), αn c1 3 3 Ξ(η), αηR2 ≤ 16 16c′1 2c′ + 2 log log(n) + log(π 2 /(6δ)) 1200 600 3 ≤ ′ Ξ(η), αn c1

and thus, using the value of c′1 , we have     1 128 3 1200 1 21251 (P − Pn )gw ≤ + Ξ(η) = Ξ(η) + ′ + + 4 c1 16c′1 c′1 4 16c′1   1 3 1 = + Ξ(η) = Ξ(η) ≤ P gw + Ξ(η) 4 4 4  Σ  1 reff (η) + log(π 2 /(6δ)) + log log(n) + c′2 ′ 2 + αηR = P gw + c1 . 4 nα This concludes the proof. We are now ready to put everything together to prove the excess zero-one risk upper bound in Theorem 1.

C.4

Proof of Theorem 1

Theorem 1 (Upper bound for early-stopped GD). There exist a universal constant c0 > 0 and some c1 , c2 , c3 , c4 > 0 depending on µ and Σ only, but not on n or p, such that the following holds: Fix δ ∈ (0, 1) and n ≥ 3. Suppose there exists ηn > 0 satisfying n ≥ c0 (reff (ηn ) +1+ log(2/δ)) and Ψ(ηn ) :=

reff (ηn ) + log(1/δ) + log log(n) + c2 2 + c3 ηn ≤ c4 (ρ∗ )2 ∥w∗ ∥Σ . n

(3)

Then, with probability at least 1 − δ, E(wτ ) − E(w∗ ) ≤ c1

1 − 2p (ρ∗ )2 ∥w∗ ∥Σ

Ψ(ηn ).

Proof. Fix ηn > 0. Recall that R = 4 ∥w∗ ∥ + 1. Note that by Lemma 3 (i) we have wτ ∈ B. By Lemma 1, ∗ ∈ B. By Lemma 3 (ii), Pn gwτ ≤ 0, so we observe that recall that wL P gwτ = (P − Pn )gwτ + Pn gwτ ≤ (P − Pn )gwτ . Now, for c′1 and c′2 as in Lemma 15, consider  Σ  c′1 reff (ηn ) + log(π 2 /(3δ)) + log log(n) + c′2 2 2 Ξ(ηn ) = + α R ηn . α n Then, by Lemma 15 (applied with δ/2 instead of δ), with probability at least 1 − δ, P gwτ ≤ (P − Pn )gwτ ≤

1 P gwτ + Ξ(ηn ), 4

which can be rearranged into ∗ L(wτ ) − L(wL ) = P gwτ ≤

33

4 Ξ(ηn ). 3

(40)

Assume that the following inequality holds, which will coincide with the assumption (3) for appropriate c2 , c3 , and c4 , stated at the end of the proof: Ξ(ηn ) ≤

3 2 α(ρ∗ )2 ∥w∗ ∥Σ . 32

Then, by (40) we have ∗ L(wτ ) − L(wL )≤

α ∗ 2 2 (ρ ) ∥w∗ ∥Σ , 8

so that we can apply Lemma 4 and (40) to arrive at the conclusion that, with probability 1 − δ, E(wτ ) − E ∗ ≤

8(1 − 2p) 32(1 − 2p) ∗ √ √ (L(wτ ) − L(wL )) ≤ Ξ(ηn ). ∗ ∗ 2π ∥w ∥Σ 3(ρ )2 α 2π ∥w∗ ∥Σ

(ρ∗ )2 α

Unfolding the definition of Ξ(ηn ) and absorbing additional constants into c′1 and c′2 , we have  Σ  1 − 2p reff (ηn ) + log(1/δ) + log log(n) + c2 ∗ E(wτ ) − E ≤ c1 ∗ 2 + c 3 ηn . (ρ ) ∥w∗ ∥Σ n Σ The last factor corresponds exactly to Ψ(ηn ), since reff (ηn ) = reff (ηn ). The missing definitions of the constants in the Theorem statement are given by

Γ = µµ⊤ + Σ, R = 4 ∥w∗ ∥ + 1 = 4 Σ−1 µ + 1, p 1 α = ℓ′′ (3R ∥Γ∥), 2 170008 √ , c1 = 9α2 2π  p 2 c2 = 1 + log(π /3) + log 1 + (log2 ((log 2 + R ∥Γ∥)α))+ +

1 log 2

 ,

c3 = α 2 R 2 , c4 =

D

9α2 . 170008

Proof of the Statistical Lower Bound

Recall that for the purposes of the statistical lower bound we keep the noise covariance Σ and the noise-flip probability p fixed, so that the class of Gaussian Mixtures introduced in (1) is effectively parametrised by µ only. To ease the notation, we will denote denote the Bayes linear classifier by ∗ wµ = Σ−1 µ, ∗ so that, with a slight abuse of notation we will write h∗µ (x) = sign(x⊤ wµ ). With a slight abuse of notation, we will denote by Pµ and Eµ the probability and expectation, respectively, when the underlying randomness comes from the marginal of X only. Unlike in the proof Theorem 1, all spectral quantities will involve the spectrum of Σ. In particular, the geometry of cov(X) = Γ = Σ + µµ⊤ does not enter this statistical lower bound proof.

34

D.1

A Triangle Inequality for Excess Zero-One Risk

Lemma 16. For any µ ∈ Rd with ∥µ∥Σ−1 = 1 and any h : Rd → R, √
2 (1 − 2p) 2π ∗ Pµ (h(X) ̸= h∗µ (X)) . Eµ (h) − Eµ (wµ ) ≥ 16 Proof. Similarly to (8), we have   ∗ ∗ Eµ (h) − Eµ (wµ ) = (1 − 2p)Eµ | tanh(X ⊤ wµ )|1{h(X) ̸= h∗µ (X)} . Consider the thresholding √ t :=

2π Pµ (h(X) ̸= h∗µ (X)) ≤ 1. 4

We proceed as follows:   ∗ ∗ Eµ (h) − Eµ (wµ ) = (1 − 2p)Eµ | tanh(X ⊤ wµ )|1{h(X) ̸= h∗µ (X)}   ∗ ∗ ≥ (1 − 2p)Eµ | tanh(X ⊤ wµ )|1{h(X) ̸= h∗µ (X)}1{|X ⊤ wµ | > t}   ∗ ≥ (1 − 2p)Eµ tanh(t)1{h(X) ̸= h∗µ (X), |X ⊤ wµ | > t} ∗ = (1 − 2p) tanh(t)Pµ (h(X) ̸= h∗µ (X), |X ⊤ wµ | > t),

where the second inequality follows from the fact that tanh(t) is even and increasing on [0, ∞). Further, by a Union Bound, we get
∗ ∗ Eµ (h) − Eµ (wµ ) ≥ (1 − 2p) tanh(t) Pµ (h(X) ̸= h∗µ (X)) − Pµ (|X ⊤ wµ | ≤ t) . (41) 2 2 ∗ ∗ is bounded | Ye ∼ N (Ye ∥µ∥Σ−1 , ∥µ∥Σ−1 )) ≡ N (Ye , 1), so that the density of X ⊤ wµ Now, note that X ⊤ wµ √ above by 1/ 2π and thus, by the definition of t,

2t 1 ∗ Pµ (|X ⊤ wµ | ≤ t) ≤ √ = Pµ (h(X) ̸= h∗µ (X)). 2 2π Plugging this back into (41) and using the fact that tanh(t) ≥ t/2 (because 0 ≤ t ≤ 1) and the definition of t, √
2 (1 − 2p)t (1 − 2p) 2π ∗ Eµ (h) − Eµ (wµ )≥ Pµ (h(X) ̸= h∗µ (X)) = Pµ (h(X) ̸= h∗µ (X)) . 4 16

Lemma 17. For any µ1 , µ2 ∈ Rd with ∥µ1 ∥Σ−1 = ∥µ2 ∥Σ−1 = 1 and any classifier h : Rd → R, Pµ1 (h(X) ̸= h∗µ1 (X)) + Pµ2 (h(X) ̸= h∗µ2 (X)) ≥

1 √ ∥µ1 − µ2 ∥Σ−1 . π e

Proof. Step 1: First, we will prove that we can do a change of measure to the µ1 , µ2 -independent Q ≡ N (0d , Σ) in the sense that for µ ∈ {µ1 , µ2 } (with ∥µ∥Σ−1 = 1), Pµ (h(X) ̸= h∗µ (X)) ≥ e−1/2 P (h(X) ̸= h∗µ (X)). X∼Q

(42)

To do so, note that The Cameron-Martin Theorem, together with ∥µ1 ∥Σ−1 = 1, give that the RadonNikodym derivative of N (µ, Σ) with respect to Q is     dN (µ, Σ) 1 1 2 ⊤ −1 ⊤ ∗ (x) = exp x Σ µ − ∥µ∥Σ−1 = exp x wµ − . dQ 2 2 35

Thus, since X | Ye ∼ N (Ye µ, Σ), taking expectation over Ye = ±1, we have
dPµ 1 ∗ ∗ (x) = exp(−1/2) exp(x⊤ wµ ) + exp(−x⊤ wµ ) ≥ exp(−1/2) dQ 2 which proves (42). Step 2: Now, using (42) for µ = µ1 , µ2 and a Union Bound, we can lower bound the left-hand of the inequality in the conclusion of the Lemma as

 1  P h(X) ̸= h∗µ1 (X) + P h(X) ̸= h∗µ2 (X) LHS ≥ √ X∼Q e X∼Q
1 ≥ √ P h∗µ1 (X) ̸= h∗µ2 (X) e X∼Q
1 ∗ ∗ = √ P sign(X ⊤ wµ ) ̸= sign(X ⊤ wµ ) . 1 2 X∼Q e Step 3: Thus, it remains to show that ∗ ∗ ) ̸= sign(X ⊤ wµ )) ≥ P (sign(X ⊤ wµ 1 2

X∼Q

1 ∥µ1 − µ2 ∥Σ−1 . π

(43)

To do so, we will work with the whitened X ∼ N (0d , Σ). Recall the notation X = Σ1/2 Z so that ∗ ∗ Z ∼ N (0d , Id ), and additionally consider v1∗ := Σ1/2 wµ = Σ−1/2 µ1 , and v2∗ := Σ1/2 wµ = Σ−1/2 µ2 with 1 2 ∗ ∗ ∥v1 ∥ = ∥v2 ∥ = 1. So, (43) reduces to P(sign(Z ⊤ v1∗ ) ̸= sign(Z ⊤ v2∗ )) ≥

∥v1∗ − v2∗ ∥ , π

(44)

where the probability is taken over Z ∼ N (0d , Id ) and we suppress this for convenient. To prove (44) , note that P(sign(Z ⊤ v1∗ ) ̸= sign(Z ⊤ v2∗ )) = 1 − 2P(Z ⊤ v1∗ > 0, Z ⊤ v2∗ > 0). Let θ ∈ [0, π] be the angle between v1∗ and v2∗ , i.e. (v1∗ )⊤ v2 = cos θ. Then, the scalar random variables Z ⊤ v1∗ and Z ⊤ v2∗ are both mean 0, variance 1, and have correlation cos θ, so we can write Z ⊤ v2∗ = Z ⊤ v1∗ cos θ + | sin θ|N, where N ∼ N (0, 1) is independent of Z. Then, recalling that ϕ and Φ are the p.d.f. and c.d.f, respectively, of N (0, 1), we have     Z ∞ Z ∞ t cos θ t cos θ ⊤ ∗ ⊤ ∗ P(Z v1 > 0, Z v2 > 0) = ϕ (t) P N > − dt = ϕ(t)Φ dt. | sin θ| | sin θ| 0 0 Note that this also is valid at θ ∈ {0, π}: if θ = 0, then Z ⊤ v1∗ = Z ⊤ v2∗ and the previous equality reads Z ∞ P(Z ⊤ v1∗ > 0) = ϕ(t)dt, 0

whereas for θ = π, Z ⊤ v1∗ = −Z ⊤ v2∗ and P(Z ⊤ v1∗ > 0, Z ⊤ v2∗ > 0) = 0 =

Z ∞ ϕ(t)Φ(−∞)dt. 0

So, using the identity Z ∞ ϕ(t)Φ(at)dt = 0

36

1 arctan a + , 4 2π

valid for any a ∈ R, we get P(sign(Z ⊤ v1∗ ) ̸= sign(Z ⊤ v2∗ )) = 1 − 2



1 arctan(cos θ/| sin θ|) + 4 2π

 =

θ . π

We arrive at (44) by using θ ≥ 2 sin(θ/2) (recall that θ ≥ 0) and ∥v1∗ ∥ = ∥v2∗ ∥ = 1: p √ 2 − 2(v1∗ )⊤ v2∗ 2 − 2 cos θ 2 sin(θ/2) ∥v ∗ − v2∗ ∥ θ ≥ = = = 1 . π π π π π

Putting together Lemmas 16 and 17, we arrive at: Lemma 18 (“Triangle inequality” for zero-one excess risk). For any µ1 , µ2 ∈ Rd with ∥µ1 ∥Σ−1 = ∥µ2 ∥Σ−1 = 1 and any classifier h : Rd → {−1, 1}, we have

2 ∗ ∗ Eµ1 (h) − Eµ1 (wµ ) + Eµ2 (h) − Eµ2 (wµ ) ≥ c1 (1 − 2p) ∥µ1 − µ2 ∥Σ−1 , 1 2 where

√ c1 =

2

32π 3/2 e

.

Proof. Using Lemma
16, the inequality a2 +
b2 ≥ (a + b)2 /2, and Lemma 17, we have that the left hand side ∗ ∗ Eµ1 (h) − Eµ1 (wµ ) + Eµ2 (h) − Eµ2 (wµ ) is at least 1 2 √ 
2
2  (1 − 2p) 2π Pµ1 (h(X) ̸= h∗µ1 (X)) + Pµ2 (h(X) ̸= h∗µ2 (X)) ≥ 16 √
2 (1 − 2p) 2π Pµ1 (h(X) ̸= h∗µ1 (X)) + Pµ2 (h(X) ̸= h∗µ2 (X)) ≥ 32 √ (1 − 2p) 2 2 . ∥µ1 − µ2 ∥Σ−1 . ≥ 32π 3/2 e

D.2

Information Theory Tools

Lemma 19. For any µ1 , µ2 ∈ Rd , KL(Pµ1 ∥ Pµ2 ) ≤

1 2 ∥µ1 − µ2 ∥Σ−1 . 2

Proof. By standard KL-facts, for any ye ∈ {±1}, KL(N (e y µ1 , Σ) ∥ N (e y µ2 , Σ)) =

1 1 2 2 ∥e y (µ1 − µ2 )∥Σ−1 = ∥µ1 − µ2 ∥Σ−1 . 2 2

Hence, denoting by Peµ1 and Peµ2 the laws of (X, Ye ) under µ1 and µ2 , respectively, since Ye has the same law irrespective of µ1 or µ2 : h i 1 2 KL(Peµ1 ∥ Peµ2 ) = EYe KL(N (Ye µ1 , Σ) ∥ N (Ye µ2 , Σ)) = ∥µ1 − µ2 ∥Σ−1 . 2 Finally, when including the random classification noise ε, the data processing inequality gives 1 2 KL(Pµ1 ∥ Pµ2 ) ≤ KL(Peµ1 ∥ Peµ2 ) ≤ ∥µ1 − µ2 ∥Σ−1 . 2

37

Now, recall that Σ is a symmetric positive semidefinite matrix and let (ui , λi )di=1 be its eigendecomposition, with λ1 ≥ λ2 . . . ≥ λd > 0 and ∥ui ∥ = 1. We will show that the lower bound holds with respect to µ ∈ U ⊆ Rd defined as follows: r   2 −1 . U = µ : ∥µ∥Σ−1 = 1, Σ µ ≤ λ1 Additionally, recall that for ηe ∈ (0, λ2 ] we consider the eigenvalue counting function N (e η ) = |{i : 1 ≤ i ≤ d, λi ≥ ηe}|, and note that N (e η ) ≥ 2. We are now ready to present the packing that will be used throughout our statistical lower bound. Lemma 20 (Dense packing of U ). There exists a universal constant 12 < c2 < 1 such that the following holds: Fix ηe ∈ (0, λ2 /2] and assume N (2e η ) ≥ 9. Consider any κ > 0 with κ2 ≤ 2e η /λ1 . Then, there exist a subset Uκ ⊂ U with log |Uκ | ≥ c2 (N (2e η ) − 1) and for any µ1 , µ2 ∈ Uκ with µ1 ̸= µ2 , κ ≤ ∥µ1 − µ2 ∥Σ−1 ≤ 2κ. 4 Proof. We start with the Gilbert-Varshamov bound, which states that there exists a constant 1 > c2 > 1/2 (in fact, we can be taken as c2 = (1 − H2 (1/64)) log 2 ≈ 0.61) such that, if N (2e η ) ≥ 9, then there is a packing subset P ⊂ {±1}N (2eη)−1 with log |P| ≥ c2 (N (2e η ) − 1) and dH (a, a′ ) ≥ (N (2e η ) − 1)/64 for any a, a′ ∈ P, where dH denotes the Hamming distance. Define the set of N (2e η ) − 1 dimensional set of unit vectors ( ) 1 V= p a:a∈P . N (2e η) − 1 Then log |V| ≥ c2 (N (2e η )−1) and for any v = a/ 2

∥v − v ′ ∥ =

p

p (N (2e η ) − 1), v ′ = a′ / (N (2e η ) − 1) ∈ Θ (with a, a′ ∈ P),

4 4 N (2e η) − 1 1 dH (a, a′ ) ≥ · = , N (2e η) − 1 N (2e η) − 1 64 16

i.e. ∥v − v ′ ∥ ≥

1 . 4

(45)

We next convert elements of V ⊂ RN (2eη)−1 to elements of U. Each v ∈ V has N (2e η ) − 1 coordinates, and we denote its i’th coordinate by vi . Since ηe ≤ λ2 /2, we have N (2e η ) − 1 = |{i : 1 ≤ i ≤ d, λi ≥ 2e η }| − 1 = |{i : 2 ≤ i ≤ d, λi ≥ 2e η }| ∈ {2, . . . , d}. and, recalling the d eigenvectors ui of Σ, we can define N (2e η)

µv =

p

λ1 (1 − κ2 )u1 + κ

X

vi−1

p

λi ui ∈ Rd .

i=2

We consider all these vectors to define Uκ = {µv : v ∈ V}. Firstly, this satisfies log |Uκ | = log |V| ≥ c2 (N (2e η ) − 1), and we next show that Uκ ⊆ U. 38

Indeed, for any such µv ∈ Uκ we have 2

2

∥µv ∥Σ−1 = (1 − κ2 ) + κ2 ∥v∥ = 1, and, using the fact that λi ≥ 2e η for i ∈ {2, . . . , N (2e η )} and the fact that κ2 ≤ 2e η /λ1 , Σ−1 µv

2

=

N (2e N (2e η) 2 Xη) vi−1 1 κ2 X 2 1 κ2 2 1 − κ2 + κ2 ≤ + vi−1 = + ≤ . λ1 λ λ 2e η λ 2e η λ i 1 1 1 i=2 i=2

Finally, let µv1 , µv2 ∈ Uκ . Note that, using (45), N (2e η)

∥µv1 − µv2 ∥Σ−1 = κ

X

p (v1,i−1 − v2,i−1 ) λi ui

i=2

= κ ∥v1 − v2 ∥ ≥

κ , 4

Σ−1

and, since v1 , v2 are unit vectors, using the triangle inequality, ∥µv1 − µv2 ∥Σ−1 = κ ∥v1 − v2 ∥ ≤ 2κ. This concludes the proof. The final ingredient that we will need in the lower bound proof is: b be three random variables where U and U b are conditionally Lemma 21 (Fano’s inequality). Let U , S, and U b take values in a finite set of size M . Then: independent, given S, and U and U b ) ≥ 1 − I(U ; S) + ln 2 , P(U ̸= U ln(M ) where I(U ; S) denotes the mutual information between U and S.

D.3

Proof of Theorem 2

Theorem 2 (Statistical lower bound). There exists a universal constant c > 0 such that the following holds: Fix n and let ηen ∈ (0, λ2 /2] ηn ) > 9. Let b h be any procedure. Then, there exists p be small enough so that N (2e d −1 µ ∈ R with Σ µ ≤ 2/λ1 such that   h i 2e ηn N (2e ηn ) − 1 ∗ b E(hS ) − E(w ) ≥ c(1 − 2p) min E , . ⊗n λ1 n S∼Pµ Proof. Fix ηe ∈ (0, λ2 /2] and recall the constant 1/2 < c2 < 1 from Lemma 20. We will apply this Lemma with (s ) r √ c2 2e η N (2e η) − 1 κ= min , . (46) 4 λ1 n Note that, as c2 < 1, we have κ2 ≤ 2e η /λ1 , so that Lemma 20 can be indeed applied. Thus, there exists a subset Uκ of U with log |Uκ | ≥ c2 (N (2e η ) − 1) and κ/4 ≤ ∥µ − µ′ ∥Σ−1 ≤ 2κ for any distinct µ, µ′ ∈ Uκ . Using Lemma 18, for any µ1 , µ2 ∈ Uκ ,

2 ∗ ∗ Eµ1 (h) − Eµ1 (wµ ) + Eµ2 (h) − Eµ2 (wµ ) ≥ c1 (1 − 2p) ∥µ1 − µ2 ∥Σ−1 1 2 ≥

39

c1 (1 − 2p)κ2 1{µ1 ̸= µ2 }. 16

(47)

Now, fix some µ ∈ Uκ and draw S ∼ Pµ⊗n . Let b h be any procedure and b hS : X ∈ Rd 7→ Y ∈ {±1} be the induced sample-based estimator. Define the decoder   ∗ b S = arg min Eµ′ (b µ hS ) − Eµ′ (wµ , (48) ′) µ′ ∈Uκ

b S , this further which is a function of S and an element of Uκ . Note that, using (47) with µ1 := µ and µ2 = µ implies that    1  ∗ ∗ ∗ Eµ (b hS ) − Eµ (wµ ) + EµbS (b hS ) − EµbS (wµ Eµ (b hS ) − Eµ (wµ )≥ bS ) 2 c1 (1 − 2p)κ2 ≥ 1{µ ̸= µb S }. 32 Thus, taking expectations over S ∼ Pµ⊗n and then supremum over µ ∈ U , we arrive at h i c (1 − 2p)κ2 1 ∗ b S ). sup P ⊗n (µ ̸= µ (49) sup E ⊗n Eµ (b hS ) − Eµ (wµ ) ≥ 32 µ∈Uκ S∼Pµ µ∈Uκ S∼Pµ We are now ready to apply Fano’s inequality (c.f. Lemma 21). Consider a uniform random variable U b S the estimator based on the sample S defined over Uκ and, conditional on U = µ, draw S ∼ Pµ⊗n , and let µ b S and U are conditionally independent given S. Thus, in (48). Note that µ bS ) ≥ 1 − P (U ̸= µ

U ,S

I(U ; S) + log 2 . log |Uκ |

By the law of total probability we have bS ) = P (U ̸= µ

U ,S

1 X b S ), P ⊗n (µ ̸= µ |Uκ | S∼Pµ µ∈Uκ

so that sup

b S ) ≥ P (U ̸= µ bS ) ≥ 1 − P ⊗n (µ ̸= µ U ,S

µ∈Uκ S∼Pµ

I(U ; S) + log 2 . log |Uκ |

We now work on the right-hand side term of (50). For that, define the average law 1 X ⊗n Pµ . P̄ = |Uκ | µ∈Uκ

Then, (i)

I(U ; S) =

1 X KL(Pµ⊗n ∥ P̄ ) |Uκ | µ∈Uκ

(ii)

≤

1 X 1 X KL(Pµ⊗n ∥ Pµ⊗n ′ ) |Uκ | |Uκ | ′ µ ∈Uκ

µ∈Uκ

≤ max ′

µ,µ ∈Uκ µ̸=µ′

KL(Pµ⊗n ∥ Pµ⊗n ′ )

(iii) n

≤

2

max ∥µ − µ′ ∥Σ−1 2 µ,µ′ ∈Uκ µ̸=µ′

(iv)

≤ 2nκ2

(v) 1

≤

8

c2 (N (2e η ) − 1)

1 ≤ log |Uκ | , 8 40

(50)

where (i) uses the definition of mutual information together with conditioning on U , (ii) uses convexity of the KL in the second argument, (iii) uses KL tensorisation and Lemma 19, (iv) follows from the fact that ∥µ − µ′ ∥Σ−1 ≤ 2κ for any µ, µ′ ∈ Uκ , and (v) uses the definition of κ in (46). Thus, plugging this into (50), 1

sup

P

⊗n µ∈Uκ S∼Pµ

bS ) ≥ 1 − 8 (µ ̸= µ

log |Uκ | + log 2 7 log 2 = − . log |Uκ | 8 log |Uκ |

Since c2 > 1/2 and N (2e η ) ≥ 9, we have log |Uκ | ≥ c2 (N (2e η ) − 1) > 1/2 · 8 = 4, and thus we arrive at sup

P

⊗n µ∈Uκ S∼Pµ

bS ) ≥ (µ ̸= µ

3 7 log 2 − ≥ , 8 4 8

and then (49) gives i 3c (1 − 2p) 1 ∗ κ2 . Eµ (b hS ) − Eµ (wµ ) ≥ ⊗n 256 µ∈Uκ S∼Pµ sup

h

E

Finally, as b h was chosen arbitrarily and using the definition of κ in (46),   h i 2e η N (2e η) − 1 ∗ b inf sup E ⊗n Eµ (hS ) − Eµ (wµ ) ≥ c(1 − 2p) min , , b λ1 n h µ∈Uκ S∼Pµ where we recall all universal constants: √ c1 =

2

32π 3/2 e

c2 ∈ (1/2, 1) 3c1 c2 c= . 4096 The conclusion of the theorem follows from the fact that Uκ ⊆ {µ ∈ Rd : ∥µ∥Σ−1 = 1}.

E

Proofs for Fast and Continuously Decaying Spectrum

In this section we provide the proofs of Theorem 3 and Corollary 1. Theorem 3 (Statistical optimality of early-stopped GD for FCD spectrum). Define ηn∗ := sup{η > 0 : N (η) ≥ nη}, and assume that (FCD) holds on (0, 2ηn∗ ]. Then, reff (η) ≍ N (η) for all η ∈ (0, ηn∗ ]. Moreover, if ηn∗ → 0 as n → ∞, and log log(n)/n ≲ ηn∗ , then the upper bound in Theorem 1 with ηn = ηn∗ matches the statistical lower bound in Theorem 2 with ηen = ηn∗ /2, with common rate ≍ ηn∗ . Proof. We split the proof into multiple steps: Step 1: We prove that reff (η) ≍ N (η) for 0 < η ≤ ηn∗ . If λi ≥ η, then 1 λi ≥ , λi + η 2 and so we can lower bound reff (η) as reff (η) =

d X

X X X 1 λi λi λi 1 = + ≥0+ = N (η), λ + η λ + η λ + η 2 2 i i i=1 i i:λi <η

i:λi ≥η

41

i:λi ≥η

i.e. reff (η) ≲ N (η). To upper bound reff (η), note that reff (η) =

X i:λi ≥η

X X λi λi 1 X 1 X + ≤ 1+ λi = N (η) + λi . λi + η λi + η η η i:λi ≥η

i:λi <η

i:λi <η

λi <η

P 1

Since, by the (FCD) assumption, η λi <η λi ≲ N (η), we arrive at reff (η) ≲ N (η). Thus, we have reff (η) ≍ N (η) for all η ∈ (0, ηn∗ ]. Step 2: We now show that for all 0 < ηe ≤ ηn∗ /2, N (e η ) ≲ N (2e η ).

(51)

Indeed, N (e η ) − N (2e η ) = |{i : ηe ≤ λi < 2e η }|, so that ηe(N (e η ) − N (2e η )) = ηe|{i : ηe ≤ λi < 2e η }| ≤

X

λi ≤

η e≤λi <2e η

X

λi ≲ ηeN (2e η ),

λi <2e η

where the last inequality uses the (FCD) assumption for 2e η ∈ (0, ηn∗ ]. Thus, (51) follows. Step 3: We show that N (ηn∗ ) ≍ nηn∗ , so that reff (ηn∗ ) ≍ nηn∗ also holds by Step 1. The definition of ηn∗ = sup{η > 0 : N (η) ≥ nη} implies that N (2ηn∗ ) < 2nηn∗ . Thus, according to (51), N (ηn∗ ) ≲ N (2ηn∗ ) ≲ nηn∗ , η > 0 : N (e η ) ≥ ne η }, we have N (ηn∗ ) ≥ nηn∗ , and thus N (ηn∗ ) ≍ nηn∗ . Since ηn∗ = sup{e Step 4: We first evaluate the upper bound in Theorem 1 at η = ηn∗ , after which we will check its two conditions that ηn∗ must satisfy. Note that, as reff (ηn∗ ) ≍ nηn∗ and log log(n)/n ≲ ηn∗ by assumption, this upper bound is E(wτ ) − E(w∗ ) ≲

reff (ηn∗ ) + log log(n) nη ∗ + log log(n) + ηn∗ ≍ n + ηn∗ ≲ ηn∗ . n n

(52)

Now, note that the first condition n ≳ reff (ηn ) holds because reff (ηn ) and ηn → 0 as n → ∞. To verify condition (3), note that its left hand side is ≲ ηn∗ by the derivation in (52), and its right hand side is independent of n. Since ηn∗ → 0 as n → ∞ by assumption, the condition (3) is also verified. Step 5: Finally, we evaluate the statistical lower bound of Theorem 2 at ηe = ηn∗ /2. For its condition N (2η) > 9, note that, by the result of Step 3 and the assumption log log(n)/n ≲ ηn∗ , N (2ηn∗ /2) = N (ηn∗ ) ≍ nηn∗ ≳ log log(n), so that the lower bound condition holds. At ηe = ηn∗ /2, since N (ηn∗ ) ≍ nηn∗ , the lower bound is  ∗  h i ηn N (ηn∗ ) ∗ inf sup E ⊗n Eµ (b hS ) − Eµ (wµ ) ≳ min , ≍ ηn∗ , b 2 n µ S∼Pµ h This concludes that the upper and statistical lower bounds of Theorems 1 and 2, respectively, are matching with common rate ≍ ηn∗ . Corollary 1 (Minimax rates for polynomially and exponentially-decaying spectra). For polynomial decay p λi ≍ i−2a with a > 1/2, there exists µ ∈ Rd with Σ−1 µ ≤ 2/λ1 such that 2a

E(wτ ) − E(w∗ ) ≍ ηn∗ ≍ n− 2a+1 . For exponential decay λi ≍ e−bi with b > 0, there exists µ ∈ Rd with Σ−1 µ ≤ E(wτ ) − E(w∗ ) ≍ ηn∗ ≍ 42

log n . n

p 2/λ1 such that

Proof. The proof for both spectra will verify the conditions (FCD), ηn∗ → 0 as n → ∞, and log log(n)/n ≲ ηn∗ of Theorem 3, and then apply its conclusion. For this, we will compute in both p cases N (η) and, as a result, deduce ηn∗ . Note that the existence of an appropriate µ ∈ Rd with Σ−1 µ ≤ 2/λ1 for which the presented rates hold is due to Theorem 2. Polynomially decaying spectrum: Suppose c− i−2a ≤ λi ≤ c+ i−2a for some constants c+ ≥ c− > 0. Then i ≤ (c− /e η )1/(2a) implies that λi ≥ ηe, i.e. N (e η ) ≳ ηe−1/(2a) ; and λi ≥ ηe gives i ≤ (c+ /e η )1/(2a) , i.e. N (e η ) ≲ ηe−1/(2a) ; combining these two we get 1

N (e η ) ≍ ηe− 2a . Next, if λi < ηe, then i > (c− /e η )1/(2a) , so that X

λi ≤ c+

i:λi <e η

X

X

i−2a ≤ c+

i:λi <e η

i−2a ≲

Z ∞

1

(c− /e η )1/(2a)

i>(c− /e η )1/(2a)

t−2a dt ≍ ηe1− 2a .

Thus, 1 1 X λi ≲ ηe− 2a ≍ N (e η ), ηe

i:λi <e η

and the (FCD) requirement of Theorem 3 is met (for any ηe > 0). By Step 3 of Theorem 3, N (ηn∗ ) ≍ nηn∗ , which gives 1

(ηn∗ )− 2a = nηn∗ ,

i.e.

2a

ηn∗ ≍ n− 2a+1 ,

which is the common upper and statistical lower bound matching rate. We have ηn∗ → 0 as n → ∞ and log log(n)/n ≲ ηn∗ . Exponentially decaying spectrum: Suppose c− e−bi ≤ λi ≤ c+ e−bi for some constants c+ ≥ c− > 0. Then, i ≤ 1b log(c− /e η ) implies that λi ≥ ηe, i.e. N (e η ) ≳ log(1/e η ); and λi ≥ ηe gives i ≤ 1b log(c+ /e η ), i.e. N (e η ) ≲ log(1/e η ); combining these two we get   1 for any ηe > 0. (53) N (e η ) ≍ log ηe Next, if λi < ηe, then i > 1b log(c− /e η ), so that X i:λi <e η

≤ c+

X

e−bi ≤ c+

X

e−bi ≲

i> 1b log(c− /e η)

i:λi <e η

Z ∞ 1 η) b log(c− /e

e−bt dt ≍ ηe.

Thus, 1 X λi ≲ 1 ≲ log ηe i:λi <e η

  1 ≍ N (e η ), ηe

and the (FCD) requirement of Theorem 3 is met (for any ηe > 0). Now, in order to identify ηn∗ in this case, we proceed as follows. First, note that by (53) we have that for any ηe > 0, c1 log(1/e η ) ≤ N (e η ) ≤ c2 log(1/e η ) for some constants c2 ≥ c1 > 0. Consider ηn− =

c1 log(n) . 4 n

43

Then, for n larger than an appropriate universal constant, since c1 log(1/e η ) ≤ N (e η ) for any ηe > 0,      n 4 c1 N (ηn− ) ≥ c1 log = c1 log(n)−log log(n)−log ≥ log(n) > nηn− . (c1 /4) log(n) c1 2 Thus, by the definition of ηn∗ = sup{η > 0 : N (η) ≥ nη}, we have ηn− ≤ ηn∗ . Similarly, take ηn+ = 2c2

log(n) , n

Then, for n larger than an appropriate universal constant, since N (e η ) ≤ c2 log(1/e η ) for any ηe > 0,   n N (ηn+ ) ≤ c2 log = c2 (log(n) − log log(n) − log(2c2 )) < 2c2 log(n) = nηn+ . 2c2 log(n) Thus, by the definition of ηn∗ = sup{η > 0 : N (η) ≥ nη}, we have ηn∗ < ηn+ . Thus, c1 log(n) log(n) ≤ ηn∗ < 2c2 , 4 n n

i.e.

ηn∗ ≍

log(n) , n

which is the common upper and statistical lower bound matching rate. Clearly we have ηn∗ → 0 as n → ∞ and log log(n)/n ≲ ηn∗ .

F

Proof of the Interpolation Lower Bound

In this section, we prove Theorem 4, following a similar sequence of steps to the proof of [40, Theorem 4.2]. We show that, with high probability, every interpolating linear classifier x 7→ sign(x⊤ w) with w ∈ I := {w ∈ Rd : mini∈[n] Yi Xi⊤ w > 0} incurs an excess zero-one risk bounded below. Throughout, we use Sm−1 := {x ∈ Rm : ∥x∥ = 1} to denote the unit sphere in Rm , (a, b) ∈ Rna × Rnb to denote the vertical concatenation of a ∈ Rna and b ∈ Rnb , and ϕ and Φ to denote the PDF and CDF, respectively, of N (0, 1).

F.1

Setup via Whitening and Rotation

Whitening:

We work in a whitened covariate space to simplify the presentation of the proofs. We write Z := Σ−1/2 X ∈ Rd ,

ε0 := Σ−1/2 ε ∈ Rd ,

and

v ∗ := Σ1/2 w∗ ∈ Rd

for the whitened covariate, noise, and Bayes linear classifier, respectively. The Gaussian mixture model then takes the form Z = Ye v ∗ + ε0

with

ε0 ∼ N (0, Id ) .

Rotation and contrast with [40]: Our interpolation lower bound is proved after rotating to a convenient coordinate system. Unlike [40, Theorem 4.2], this does not impose any structural assumption (e.g., sparsity) on v ∗ itself. Indeed, since the whitened Gaussian noise ε0 is rotationally invariant, for any nonzero v ∗ ∈ Rd and any k ∈ [d], there exists an orthogonal matrix R ∈ Rd×d such that   Rv ∗ = ∥v ∗ ∥ √1k 1k , 0d−k . Specifically, a valid choice is R = Id − 1{u ̸= 0} · 2uu⊤ /∥u∥2 where u := v ∗ − ∥v ∗ ∥( √1k 1k , 0d−k ). Thus, in the rotated coordinates, the signal is supported on the first k coordinates, while the remaining d − k coordinates are nuisance directions. Importantly, k and R are free parameters that merely define a choice of 44

basis that influences the behaviour of the lower bound, so this representation applies to any v ∗ rather than strictly sparse ones only. For clarity, we write ZR := RZ = (S, N ) ∈ Rk × Rd−k

and

∗ vR := Rv ∗ = (ψ ∗ , 0d−k ) ∈ Rk × Rd−k

for the signal-nuisance decomposition. For the i-th sample (Xi , Yi ), we write ZR,i , Si and Ni for the corresponding quantities. Proof sketch: The key proof idea is to show that using only the k signal directions can create large negative margins on a constant fraction of samples (Section F.3), so any interpolating classifier must use the d − k nuisance directions to fix those bad margins (Section F.4). This reliance on nuisance directions ultimately incurs the lower bound in Theorem 4 (Section F.5). To begin, we prove some preliminary lemmas in Section F.2.

F.2

Preliminary Lemmas

Lemma 22 (Bound on norm of signal coordinates). For every δ ∈ (0, 1),   p √ ∗ P max ∥Si ∥ ≤ k + 2 log(2n/δ) + ∥v ∥ ≥ 1 − 2δ . i∈[n]

∗ ∗ Proof. Since ZR = Ye vR + ε0 with Ye ∈ {±1}, vR = Rv ∗ = (ψ ∗ , 0d−k ) and ε0 ∼ N (0, Id ), we have ∗ ∥S∥ = ∥ZR[1:k] ∥ = ∥Ye vR[1:k] + ε0[1:k] ∥ ≤ ∥ψ ∗ ∥ + ∥ε0[1:k] ∥ = ∥v ∗ ∥ + ∥ε0[1:k] ∥,

where by ZR[1:k] we denote the vector obtained from the first k coordinates of ZR . The result follows from standard Gaussian concentration on ∥ε0[1:k] ∥:   p √ δ , P ∥ε0[1:k] ∥ > k + 2 log(2n/δ) ≤ 2n together with a union bound. The next lemma is an angular calibration result, analogous to [40, Lemma C.1], which lower bounds the excess zero-one risk in terms of the angle between the learned linear classifier and the Bayes classifier. Working in the whitened space, let v = Σ1/2 w for w ∈ Rd \ {0} and recall v ∗ = Σ1/2 w∗ . The Euclidean angle ∠(v, v ∗ ) coincides with the Σ-angle ∠Σ (w, w∗ ). Lemma 23 (Angular calibration of excess zero-one risk). Let θ := ∠(v, v ∗ ) ∈ [0, π]. Then, 2

E(w) − E(w∗ ) ≥ √12π (1 − 2p)(1 − cos θ) ∥v ∗ ∥ exp(− 12 ∥v ∗ ∥ ). Proof. To begin, recall that E(w) − E(w∗ ) = (1 − 2p)(P(Ye v ⊤ Z ≤ 0) − P(Ye (v ∗ )⊤ Z ≤ 0)), where we have
2 P(Ye v ⊤ Z ≤ 0) = P(Ye v ⊤ (Ye v ∗ + ε0 ) ≤ 0) = P v ⊤ v ∗ + N (0, ∥v∥ ) ≤ 0   v⊤ v∗ = Φ(−∥v ∗ ∥ cos θ) , =Φ − ∥v∥
and similarly, P(Ye (v ∗ )⊤ Z ≤ 0) = Φ − ∥v ∗ ∥ . Hence, combining the two yields Z −∥v∗ ∥ cos θ ⊤ ∗ ⊤ ∗ ∗ e e P(Y v Z ≤ 0) − P(Y (v ) Z ≤ 0) = Φ(− ∥v ∥ cos θ) − Φ(− ∥v ∥) = ϕ(x)dx −∥v ∗ ∥

Z −∥v∗ ∥ cos θ ≥ −∥v ∗ ∥

min ∗

−∥v ∗ ∥≤x≤−∥v ∥ cos θ

ϕ(x)dx = − ∥v ∗ ∥ cos θ + ∥v ∗ ∥ · ϕ(−∥v ∗ ∥) .

45

F.3

Signal Component Induces Large Negative Margins on Constant Fraction of Samples

Lemma 24, analogous to [40, Lemma C.2], gives a uniform lower bound on the probability of large negative margins for any fixed classifier v̄ ∈ Sd−1 , where the bar ¯· indicates a unit vector. Lemma 24 (Bad margin occurs with constant probability). For any v̄ ∈ Sd−1 and every c ∈ (0, 1), !
1 − 2p ⊤ ∗
+p . P Y ZR v̄ < −c ≥ ϱ(∥v ∥) := 2 (Φ(−c) − Φ(−1)) 1 + exp 2∥v ∗ ∥(∥v ∗ ∥ + 1) ⊤ Proof. Since v̄ ′ := R⊤ v̄ ∈ Sd−1 for any v̄ ∈ Sd−1 , we have P(Y ZR v̄ < −c) = P(Y Z ⊤ v̄ ′ < −c). We bound ⊤ ′ P(Y Z v̄ < −c) in the rest of the proof. Recall σ(t) = 1/(1 + exp(−t)) denotes the sigmoid function. For the Gaussian mixture model Z = Ye v ∗ + ε0 , we recall from Lemma 5 that

P(Y = y | Z) = (1 − 2p)σ(2yZ ⊤ v ∗ ) + p

for y ∈ {±1} .

Using this we can write P(Y Z ⊤ v̄ ′ < −c)   =E 1{Y = 1, Z ⊤ v̄ ′ < −c} + 1{Y = −1, Z ⊤ v̄ ′ > c}   =E P(Y = 1 | Z)1{Z ⊤ v̄ ′ < −c} + P(Y = −1 | Z)1{Z ⊤ v̄ ′ > c} 

 =E (1 − 2p)σ(2Z ⊤ v ∗ ) + p 1{Z ⊤ v̄ ′ < −c} + (1 − 2p)σ(−2Z ⊤ v ∗ ) + p 1{Z ⊤ v̄ ′ > c} (i) 
 ≥E (1 − 2p)σ(−2|Z ⊤ v ∗ |) + p 1{|Z ⊤ v̄ ′ | > c} (ii)

for any κ ≥ 0 , ≥ (1 − 2p)σ(−κ) + p 1 − P(|Z ⊤ v̄ ′ | ≤ c) − P(|Z ⊤ v ∗ | ≥ κ/2) {z } | {z } | Term I

(54)

Term II

 where step (i) holds because σ(−|t|) ≤ min σ(t), σ(−t) for any t ∈ R, and step (ii) holds for any constant κ ≥ 0. We next upper bound Term I and Term II separately and choose κ accordingly. 2
To this end, first note that for any vector u ∈ Rd , Z ⊤ u | Ye ∼ N Ye u⊤ v ∗ , ∥u∥ , so we can write
P |Z ⊤ u| ≤ c h
i = EYe P |Z ⊤ u| ≤ c | Ye h
i = EYe P − c ≤ Z ⊤ u ≤ c | Ye " ! !# c − Ye u⊤ v ∗ −c − Ye u⊤ v ∗ = EYe Φ −Φ ∥u∥ ∥u∥          1 c − u⊤ v ∗ −c − u⊤ v ∗ c + u⊤ v ∗ −c + u⊤ v ∗ Φ −Φ +Φ −Φ = 2 ∥u∥ ∥u∥ ∥u∥ ∥u∥       ⊤ ∗ ⊤ ∗ (ii) c−u v c+u v c (i) =Φ +Φ − 1 ≤ 1 − 2Φ − , ∥u∥ ∥u∥ ∥u∥ where step (i) is due to Φ(t) + Φ(−t) = 1 and step (ii) uses the fact that for any a ≥ 0, t 7→ Φ(a − t) + Φ(a + t) is maximised at t = 0 for t ∈ R. Then taking u = v̄ ′ in the last display and using ∥v̄ ′ ∥ = 1 gives Term I = P(|Z ⊤ v̄ ′ | ≤ c) ≤ 1 − 2Φ(−c) .

46

(55)

To control Term II, first note that by choosing κ = 2 ∥v ∗ ∥ (∥v ∗ ∥ + 1), we have  ⊤ ∗ 

|Z v | ∗ Term II = P |Z ⊤ v ∗ | ≥ κ/2 = P |Z ⊤ v ∗ | ≥ ∥v ∗ ∥ (∥v ∗ ∥ + 1) = P ≥ ∥v ∥ + 1 , ∥v ∗ ∥ where Z ⊤ v ∗ /∥v ∗ ∥ = Ye ∥v ∗ ∥ + G with G ∼ N (0, 1), which by the triangle inequality implies |Z ⊤ v ∗ |/∥v ∗ ∥ ≤ |Ye |∥v ∗ ∥ + |G| = ∥v ∗ ∥ + |G|. Therefore, we have Term II ≤ P(∥v ∗ ∥ + |G| ≥ ∥v ∗ ∥ + 1) = P(|G| ≥ 1) = 2Φ(−1) .

(56)

Finally, substituting (55) and (56) into (54) along with κ = 2 ∥v ∗ ∥ (∥v ∗ ∥ + 1), we obtain ! 1 − 2p ⊤ ′
+ p · 2 (Φ(−c) − Φ(−1)) , P(Y Z v̄ < −c) ≥ 1 + exp 2∥v ∗ ∥(∥v ∗ ∥ + 1) where 2 (Φ(−c) − Φ(−1)) > 0 given c ∈ (0, 1). Lemma 24, analogous to [40, Lemma C.3], gives a population guarantee for any fixed classifier v̄ ∈ Sd−1 , Lemma 25 below lifts this to a finite-sample statement that holds uniformly over all signal components that an interpolator might learn. To isolate the role of the signal component, we consider classifiers of the form ⊤ v̄ = (ψ̄, 0d−k ) ∈ Sd−1 with ψ̄ ∈ Sk−1 . Then ZR v̄ = S ⊤ ψ̄, implying the margin depends only on the signal component ψ̄. We show that, for every candidate signal direction ψ̄ ∈ Sk−1 , a constant fraction of samples have large negative margins. As before, the bar ¯· denotes a unit vector. Lemma 25 (Bad margins occur on a constant fraction
of samples). Fix c ∈ (0, 1) and define ϱ(∥v ∗ ∥) :=   2 (Φ(−c) − Φ(−1)) (1 − 2p)/ 1 + exp 2∥v ∗ ∥(∥v ∗ ∥ + 1) + p > 0. For every δ ∈ (0, 1), if for a sufficiently large constant c1 > 0, ! ! √   c1 k c1 k + ∥v ∗ ∥ · k log + k log log + log 2δ , (57) n≥ ϱ(∥v ∗ ∥) c ϱ(∥v ∗ ∥)δ then the following holds: k−1

P ∀ψ̄ ∈ S

! n X  ⊤ ∗ c n , 1 Yi Si ψ̄ ≤ − 2 ≥ 2 ϱ(∥v ∥) ≥ 1 − δ . i=1

Proof. Define the binary random variables ξi (ψ̄) := 1{Yi Si⊤ ψ̄ ≤ −c},

for i ∈ [n] .

By Lemma 24, E[ξi (ψ̄)] ≥ ϱ(∥v ∗ ∥). So by the Chernoff bound, we have ! ! n n X X
∗ n n P ξi (ψ̄) < 2 ϱ(∥v ∥) ≤ P ξi (ψ̄) < 2 E[ξ1 (ψ̄)] ≤ exp − n8 E[ξ1 (ψ̄)] i=1

i=1

≤ exp − n8 ϱ(∥v ∗ ∥) .

(58)

We now use a covering argument to turn a pointwise probability bound which holds for a fixed v̄ = (ψ̄, 0d−k ) into a uniform bound over all ψ̄ ∈ Sk−1 . Since |Sk−1 | = ∞, we discretise Sk−1 with a finite ϵ-ℓ2 -covering C,
k so that a union bound can be applied. Since |C| ≤ 3ϵ , applying a union bound over C and using (58), we obtain ! n X
∗ ′ ′ n P ∃ψ̄ ∈ C : ξi (ψ̄ ) < 2 ϱ(∥v ∥) ≤ |C| exp − n8 ϱ(∥v ∗ ∥) i=1

  ≤ exp − n8 ϱ(∥v ∗ ∥) + k log 3ϵ ≤ 2δ , 47

(59)

where the last inequality holds provided n ≥ 8ϱ(∥v ∗ ∥)−1 · k log 3ϵ + log 2δ , which is ensured by the sample size n condition (57) a sufficiently large constant c1 > 0. √ forp Define A := k + 2 log(2n/δ) + ∥v ∗ ∥. On the high-probability event {maxi∈[n] ∥Si ∥ ≤ A} from Lemma 22, we choose ϵ = c/(2A). Then, for every ψ̄ ∈ Sk−1 , there exists ψ̄ ′ ∈ C such that for all i ∈ [n], Si⊤ (ψ̄ − ψ̄ ′ ) ≤ ∥Si ∥ ψ̄ − ψ̄ ′ ≤ Aϵ ≤ 2c , which implies − 2c ≤ Yi Si⊤ ψ̄ − Yi Si⊤ ψ̄ ′ ≤ 2c , so whenever Yi Si⊤ ψ̄ ′ ≤ −c, we must have Yi S ⊤ ψ̄ ≤ 2c − c = − 2c . This means that on the event {maxi∈[n] ∥Si ∥ ≤ A}, n X

ξi (ψ̄ ′ ) =

i=1

n X

1{Yi Si⊤ ψ̄ ′ ≤ −c} ≤

i=1

n X

1{Yi Si⊤ ψ̄ ≤ − 2c } .

(60)

i=1

Therefore, using (60) and (59) we can write k−1

P ∀ψ̄ ∈ S

,

n X

!

1

{Yi Si⊤ ψ̄ ≤ − 2c } ≥ n2 ϱ(∥v ∗ ∥)

i=1 k−1

= 1 − P ∃ψ̄ ∈ S

:

n X

!

1

{Yi Si⊤ ψ̄ ≤ − 2c } < n2 ϱ(∥v ∗ ∥)

i=1

!  n X ′ ′ ∗ n ≥ 1 − P max ∥Si ∥ > A − P ∃ψ̄ ∈ C : ξi (ψ̄ ) < 2 ϱ(∥v ∥) 

i∈[n]

i=1

≥ 1 − 2δ − 2δ = 1 − δ .

F.4

Nuisance Component Cannot Fix Large Negative Margins for Affected Samples

∗ Recall the rotated Bayes classifier admits a signal-nuisance decomposition vR = (ψ ∗ , 0d−k ) ∈ Rd . Lemma 25 shows that a learned classifier using only its signal component, i.e., v̄ = (ψ̄, 0d−k ) ∈ Sd−1 , produces large negative margins on a constant fraction of samples. To interpolate, a general classifier (ψ, ν) ∈ Rk × Rd−k must therefore use its nuisance component ν to correct these bad margins. Lemma 26 shows that this correction is limited: even the best nuisance direction ν̄ ∈ Sd−k−1 can only achieve margins no larger than m over the affected subset of samples J (ψ̄).

Lemma 26 (Nuisance component cannot fix bad margins). For each ψ̄ ∈ Sk−1 , let J (ψ̄) ⊂ [n] be a random subset independent of (Ni )ni=1 . Suppose there exists a function ϱe(n, ∥v ∗ ∥) ≥ 0 such that |J (ψ̄)| ≥ ϱe(n, ∥v ∗ ∥) for all ψ̄ ∈ Sk−1 , then for every δ ∈ (0, 1),   k−1 ⊤ P ∀ψ̄ ∈ S , sup min Yi Ni ν̄ ≤ m ≥ 1 − δ . ν̄∈Sd−k−1 i∈J (ψ̄)

where √ ∗

m(n, d, k, ∥v ∥) =

n+

p √ d − k + 2 log(1/δ) p . ϱe(n, ∥v ∗ ∥)

∗ Proof. Recall we have ZR,i = Yei vR + ε0,i = (Si , Ni ) with ε0,i ∼ N (0, Id ), so i.i.d.

(Ni )ni=1 ∼ N (0, Id−k ) . 48

Collect N1 , . . . , Nn into a matrix N1:n ∈ Rn×(d−k) , then N1:n is a standard Gaussian matrix, with the standard spectral-norm upper bound   p √ √ P ∥N1:n ∥ ≤ n + d − k + 2 log(1/δ) ≥ 1 − δ . In the rest of the proof, we work on this event. Fix ψ̄ ∈ Sk−1 and write J ≡ J (ψ̄) ⊂ [n] for simplicity. Fix ν̄ ∈ Sd−k−1 , and stack (Yi Ni⊤ ν̄)i∈J into a vector A ∈ R|J | . If mini∈J Ai ≤ 0, then since m ≥ 0, it holds that mini∈J Ai ≤ m. If mini∈J Ai > 0, then by Cauchy-Schwarz p ∥A∥ ≥ |J | min Ai , (61) i∈J

and note also since Y1 , . . . , Yn ∈ {±1} does not change Euclidean norms, ∥A∥ = ∥NJ ν̄∥ where NJ ∈ R|J |×(d−k) is the submatrix of N1:n formed by the rows indexed by J , a subset that does not itself depend on N1:n . Since (61) holds for every ν̄ ∈ Sd−k−1 , we have sup

∥NJ ν̄∥ (i) ∥NJ ∥ (ii) ∥N1:n ∥ p ≤ p ≤ p |J | |J | |J | ν̄∈Sd−k−1 p √ √ (iii) n + d − k + 2 log(1/δ) p ≤ =: m , ϱe(n, ∥v ∗ ∥)

min Ai ≤

ν̄∈Sd−k−1 i∈J

sup

where step (i) is due to ∥v̄∥ = 1, step (ii) holds because ∥NJ ∥ ≤ ∥N1:n ∥ for any random subset J (ψ̄) ⊂ [n] that is itself independent of N1:n , and step (iii) is by assumption |J | ≥ ϱe(n, ∥v ∗ ∥). Hence, the bound in the last display applies simultaneously to all J (ψ̄) ⊂ [n], and hence to all ψ̄ ∈ Sk−1 .

F.5

Proof of Theorem 4

Combining the lemmas above, we prove the main theorem. Theorem 4 (Interpolation lower bound). Suppose ∥w∗ ∥Σ ≍ 1. Fix any c ∈ (0, 1) and δ ∈ (0, 1), and let k ∈ {1, . . . , n} be arbitrary. There exist constants c1 , c2 , c3 > 0 such that if   √ 4 n ≥ c1 · k log ck + k log log 2k + log and d − k ≥ c2 n , (6) δ δ then, defining the set of interpolators I := {w ∈ Rd : mini Yi Xi⊤ w > 0}, with probability at least 1−δ, ∀w ∈ I, E(w) − E(w∗ ) ≥ 

√

c3 · (1 − 2p)n 2 . p √ n + d − k + 2 log(2/δ)

(7)

Proof. Fix δ ∈ (0, 1). The proof follows four steps. Step 1: We first recall the key consequences of Lemmas 25 and 26. Fix c ∈ (0, 1). For each ψ̄ ∈ Sk−1 , define ∗ J (ψ̄) := {i ∈ [n] : Yi Si⊤ ψ̄ ≤ − 2c }. In our model, ZR,i = Yei vR + ε0,i = (Si , Ni ), where Si = Yei ψ ∗ + ε0,i[1:k] n n and Ni = ε0,i[k+1:d] . Thus (Si , Yi )i=1 ⊥ (Ni )i=1 , which implies J (ψ̄) ⊥ (Ni )ni=1 . Under the sample size condition (6) and since ∥v ∗ ∥ = ∥Σ1/2 w∗ ∥ = ∥w∗ ∥Σ ≍ 1, Lemma 25 yields   P ∀ψ̄ ∈ Sk−1 , |J (ψ̄)| ≥ n2 ϱ(∥v ∗ ∥) ≥ 1 − δ/2 ,

49

(62)

(63)

where ϱ(∥v ∗ ∥) is defined as in Lemma 25 with δ/2 instead of δ, and ϱ(∥v ∗ ∥) ≍ 1 given ∥v ∗ ∥ ≍ 1. Define p √ √ n + d − k + 2 log(2/δ) pn m(n, d, k, ∥v ∗ ∥) = . ∗ 2 ϱ(∥v ∥) Combining the independence J (ψ̄) ⊥ (Ni )ni=1 in (62) with the lower bound |J (ψ̄)| ≥ n2 ϱ(∥v ∗ ∥) in (63), Lemma 26 implies   k−1 ⊤ P ∀ψ̄ ∈ S , sup min Yi Ni ν̄ ≤ m ≥ 1 − δ/2 . (64) ν̄∈Sd−k−1 i∈J (ψ̄)

Step 2:

⊤ Define I0 := {v̄ ∈ Sd−1 : mini∈[n] Yi ZR,i v̄ > 0}. The second step of the proof is to establish   q ∗ v̄ ⊤ vR c2 ≥ 1−δ. (65) P ∀v̄ ∈ I0 , ∗ ∥ ≤ 1/ 1 + 4m2 ∥vR

Let E1 and E2 denote the events that hold with probability 1 − δ/2 in (63) and (64), respectively. We work on E1 ∩ E2 with P(E1 ∩ E2 ) ≥ 1 − δ. Fix any v̄ ∈ I0 and write its signal-nuisance decomposition as ∗ ∗ v̄ = (ψ, ν) with ψ ∈ Rk and ν ∈ Rd−k . If ψ = 0, then v̄ ⊤ vR /∥vR ∥ = 0 so the claimed upper bound in (65) is trivial. Thus, we focus on ψ ̸= 0 in the rest of the proof, and denote ψ̄ = ψ/∥ψ∥ ∈ Sk−1 . On E1 , the classifier v̄ = (ψ̄, 0) ∈ Sd−1 incorrectly classifies many samples with large negative margins. Therefore, for a different, general classifier v̄ = (ψ, ν) ∈ Sd−1 to interpolate, we must use ν to fix the negative margins caused by ψ (or ψ̄), that is, we must have for every i ∈ J (ψ̄), ⊤ 0 < Yi ZR,i v̄ = Yi Si⊤ ψ + Yi Ni⊤ ν = Yi Si⊤ ψ̄∥ψ∥ + Yi Ni⊤ ν.

On E1 , the last display implies 2c ∥ψ∥ < mini∈J (ψ̄) Yi Ni⊤ ν. If ν = 0, this forces ψ = 0, contradicting our assumption that ψ ̸= 0. So ν ̸= 0, and we denote ν̄ = ν/∥ν∥ ∈ Sd−k−1 . Now given E2 holds, we can write c ∥ψ∥ 2 ∥ν∥ <

min Yi Ni⊤ ν̄ ≤ m.

i∈J (ψ̄)

2

2 Together with ∥v̄∥2 = ∥ψ∥2 + ∥ν∥2 = 1, we can solve for ∥ψ∥ to obtain ∥ψ∥2 ≤ 4m c2 (1 − ∥ψ∥ ) =⇒ ∥ψ∥ ≤ q 2 c 1/ 1 + 4m 2 . We complete the proof of (65) by noticing ∗ ∗ v̄ ⊤ vR ⊤ ψ = ψ ≤ ∥ψ∥. ∗ ∥ ∥vR ∥ψ ∗ ∥

In the rest of the proof, we work on the event in (65). Step 3: The next step is to transform from the rotated-whitened coordinates to the original coordinates. To this end, for each v̄ ∈ I0 define w := Σ−1/2 R⊤ v̄. Then for every sample i, we have ⊤ Yi ZR,i v̄ = Yi (RΣ−1/2 Xi )⊤ v̄ = Yi Xi⊤ (Σ−1/2 R⊤ v̄) = Yi Xi⊤ w ,

which implies that the two interpolator sets I0 and I have a one-to-one correspondence (up to scaling) where v̄ ∈ I0 ⇐⇒ w = Σ−1/2 R⊤ v̄ ∈ I . Moreover, note that ∥w∥Σ = ∥v̄∥ = 1, and so ∗ v̄ ⊤ vR (RΣ1/2 w)⊤ (RΣ1/2 w∗ ) w⊤ Σw∗ w⊤ Σw∗ = = = = cos θ , ∗ ∗ 1/2 ∗ ∥vR ∥ ∥w ∥Σ ∥w∥Σ ∥w∗ ∥Σ ∥RΣ w ∥

where θ := ∠Σ (w, w∗ ). This implies that the following events are equivalent ( ) ( ) q q ∗ v̄ ⊤ vR c2 c2 ∀v̄ ∈ I0 , = ∀w ∈ I, cos θ ≤ 1/ 1 + 4m2 . ∗ ∥ ≤ 1/ 1 + 4m2 ∥vR 50

Step 4: The final step is to apply the calibration result from Lemma 23, which lower bounds the excess zero-one risk in√terms of 1 − cos θ. √First, note that if d − k ≥ c2 n for a sufficiently large c2 > 0, then q √ √

m=

n+ d−k+

√n

2 log(2/δ)

∗ 2 ϱ(∥v ∥)

≥

√ 1+ c2 +

√1

2 n log(2/δ)

∗ 2 ϱ(∥v ∥)

≥ 3. Using the inequality 1 − 1/

3 1 + a1 ≥ 8a for all a ≥ 3,

we obtain that q 3 c2 3c2 c2 1 − cos θ ≥ 1 − 1/ 1 + 4m 2 ≥ 32 m2 = 64 · 

nϱ(∥v ∗ ∥) 2 . p √ √ n + d − k + 2 log(2/δ)

Applying Lemma 23, we have 2

E(w) − E(w∗ ) ≥ √12π (1 − 2p)(1 − cos θ) ∥v ∗ ∥ exp(− 12 ∥v ∗ ∥ ) 2

√ (1 − 2p)  ≥ 643c 2π √

nϱ(∥v ∗ ∥) ∗ ∗ 2 1 2 ∥v ∥ exp(− 2 ∥v ∥ ). p √ n + d − k + 2 log(2/δ)

Since ∥v ∗ ∥ = ∥Σ1/2 w∗ ∥ = ∥w∗ ∥Σ ≍ 1 and so ϱ(∥v ∗ ∥) ≍ 1, we obtain that there exists a constant c3 > 0 such that E(w) − E(w∗ ) ≥ c3 · (1 − 2p) · 

n √

51

n+

√

d−k+

2 . p 2 log(2/δ)

Related documents

• Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification#27547
• A Continuous Gaussian Mixture Approach to Sample Multivariate Gaussians constrained by linear inequalities#370891
• Regularisation of mixture density networks#234228
• Optimal Transport for Domain Adaptation through Gaussian Mixture Models#354118
• Flexibly regularized mixture models and application to image segmentation#175785