Convergence of Gradient Descent on Separable Data

• Gradient descent’s implicit bias matters because over-parameterized objectives have multiple global optima, while deep models’ inductive bias is not sufficiently explained by explicit regularization or capacity limits.Different optimization algorithms can therefore produce different models and population generalization.Source: §1 · p. 1
• For separable logistic regression, gradient descent converges in direction to the unit-L2 maximum-margin separator, but the margin converges only at O(1/log(t)), much slower than the loss at O(1/t) [Soudry et al. (2018a)].The classification boundary can therefore keep changing after training error reaches zero; exponential-loss gradient descent on deep linear networks has the same asymptotic bias, without analyzed rates [Gunasekar et al. (2018a)].Source: §1 · p. 1
• The paper extends maximum-margin convergence to losses with super-polynomial tails, while convergence fails for losses with (sub)polynomial tails.This addresses whether tight exponential tails are uniquely necessary for convergence to the L2 maximum-margin solution.Source: §1 · p. 2
• Losses with exponential tails, including logistic loss, achieve the optimal margin-convergence rate, and the same asymptotic rates extend to fully connected deep linear networks with only marginal degradation as depth increases.The introduction frames these results as answers to how tail behavior and network depth affect convergence.Source: §1 · p. 2
• For exponential loss, normalized gradient updates with step size proportional to the inverse gradient accelerate maximum-margin convergence substantially over standard gradient descent, with evidence suggesting the improvement may extend to nonlinear neural networks.Standard fixed-step convergence is described as 1/log(t), whereas the normalized-update rate is reported as much faster; experiments suggest possible transfer beyond linear networks.Source: §1 · p. 2

Setup

• The setup considers unregularized empirical-loss minimization for homogeneous linear predictors on strictly linearly separable binary data, using gradient descent iterates and L2 norms.Labels can be transformed so that all y_n = 1 without loss of generality.Source: §2 · p. 2

Losses

• Strictly monotone losses include logistic, exponential, and probit losses; on separable data, their empirical risk has no finite minimizer, so iterates diverge while their directions determine the classification boundary.The loss is differentiable, strictly decreasing, positive, and approaches zero together with its derivative as the margin grows.Source: §2 · p. 2

Prior linear-model result

• For almost all separable datasets, fixed-step gradient descent converges toward the L2 maximum-margin separator when the negative loss derivative has a tight exponential tail and the loss is suitably smooth.The reviewed theorem allows any initialization and fixed step size satisfying η < 2β^-1; its exponential-loss extension uses η < 1/L(w(0)).Source: §2 · pp. 2–3
• Theorem 1 implies logarithmically slow convergence in direction and margin, despite the empirical loss itself decaying as O(1/t).The contrast is between slow directional and margin convergence and faster loss convergence.Source: §2 · p. 3

Multilayer linear networks

• For fully connected deep linear networks, prior work showed convergence toward the L2 maximum-margin separator only for exponential loss under additional convergence conditions, without specifying the margin-convergence rate.The network optimizes over layer weight matrices rather than directly over a single linear predictor.Source: §2 · p. 3

3.1 Linear networks with general tails

• For any depth, gradient descent converges in direction to the maximum-margin solution for almost all separable datasets and initializations under Assumption 1 and bounded step sizes.Assumption 1 requires a strictly monotone, asymptotically convex, non-oscillatory loss with a super-polynomial tail.Source: §3.1 · pp. 3–4
• Super-polynomial tails support maximum-margin convergence, whereas polynomial tails and unregularized hinge loss generally do not.The result extends the exponential-loss characterization to logistic loss and other losses covered by Assumption 1.Source: §3.1 · p. 4

3.2 Rates of convergence

• With fixed step sizes, the optimal margin-convergence rate is 1/log(t), attained by exponentially tailed losses with f(u)=Θ(u), including logistic and exponential loss.For f′(u)=o(1), the asymptotic rate is Ω(1/log(t)), so the optimal rate for any tail is O(1/log(t)); for poly-exponential losses with 0.25 < ν ≤ 1, constants are strictly worse when ν < 1.Source: §3.2 · p. 5
• For any depth, exponential-loss margin convergence remains O(1/log(t)) because depth-dependent factors negligibly affect the asymptotic solution.Theorem 4 applies when the SVM support vectors span the data and under the additional rate assumptions.Source: §3.2 · p. 5

3.3 Faster rates using variable step sizes

• For separable data and any initial point, normalized gradient descent with exponential loss and η_t = 1/√(t+1) yields margin convergence to max-margin γ at rate t^-1/2 log t, compared with O(1/log t) for fixed step sizes.The normalization makes the step-size choice independent of the unknown optimal margin γ.Source: §3.3 · p. 6
• The accelerated log(t)/√t rate matches the optimal margin-suboptimality rate known for hard-margin SVM, although the goal is to improve gradient descent rather than build a faster SVM optimizer.The paper suggests this aggressive step-size strategy may also apply to deep neural networks, supported by numerical results presented later.Source: §3.3 · p. 6

4 EXPERIMENTS WITH NORMALIZED GRADIENT DESCENT

• The experiments tune normalized-GD step sizes separately, use η = 5 × 10−3 for synthetic multilayer models, and apply scheduled learning-rate decay in image experiments.MNIST uses 3,000 iterations with decay at 50%, 75%, and 87.25%; CIFAR-10 follows decay at 30%, 60%, and 80%.Source: §4 · p. 6, §4.1 · p. 6, §4.2 · p. 6

4.1 Linear Networks on Synthetic Data

• On synthetic logistic regression and multi-layer linear networks, normalized GD converges significantly faster to the maximum-margin separator than GD.The comparison covers networks with 1, 2, or 3 layers; Figure 2 reports faster margin-gap convergence across models.Source: §4.1 · p. 6, Figure 1 · p. 7, Figure 2 · p. 7

4.2 Image Classification on MNIST

• On MNIST, normalized GD keeps reducing training loss and reaches 1.4% test error versus 1.91% for GD.GD training loss stagnates early as gradients become small, whereas normalized GD continues making progress.Source: §4.2 · p. 7, Figure 3 · p. 7

4.3 Image Classification on CIFAR-10

• Normalized GD achieves 6.93% test error versus 9.90% for GD on CIFAR-10 with a Wide ResNet 28-4.Both methods use η = 2.0, selected by validation, and are evaluated after 7,800 iterations.Source: Figure 4 · p. 7, §4.3 · p. 8
• On CIFAR-10, normalized GD remains worse than standard Wide ResNet optimization, while removing momentum and weight decay raises SGD error from 4.45% to 7.75%.This suggests reconciling gradient normalization with momentum and weight decay.Source: §4.3 · p. 8

5 DISCUSSION

• Super-polynomial tails yield convergence toward the L2 maximum-margin direction for multilayer linear networks, whereas polynomially tailed losses do not.The support vectors dominate gradients for super-polynomial tails, while non-support vectors remain non-negligible for polynomial or heavier tails.Source: §5 · p. 8
• Exponential-tailed losses achieve the optimal fixed-step convergence rate for linear classifiers, while multilayer linear networks incur only a negligible depth-dependent decrease, even with infinitely many layers.The multilayer result assumes that the loss converges to zero and is notable because exploding or vanishing gradients do not substantially affect the rate.Source: §5 · p. 8
• Normalized gradient descent can closely approximate the regularization path: after t ≥ log(n/ϵ)/γ^2 steps, its loss is ϵ-close to the best predictor with the same norm.For exponential loss, increasing the learning rate significantly accelerates gradient descent.Source: §5 · p. 8
• MNIST improves by 0.5% and CIFAR-10 by 3% with normalized gradient descent, although results remain below state-of-the-art and the gap is associated with weight decay and momentum.Normalized gradient descent also accelerates convergence on synthetic linear, multilayer linear, and nonlinear ReLU networks.Source: §5 · p. 8

A Additional Related Work

• Unlike Rosset et al. (2004), this work studies optimization dynamics and implicit bias of gradient-descent iterates, including fully connected linear networks rather than only explicit regularization paths for linear models.The paper’s Assumption 1 is stronger than Rosset et al. (2004)’s condition, and additional assumptions are needed to analyze iterate and gradient convergence.Source: A Additional Related Work · p. 10

B Adaptive Learning Rate

• For exponential loss with a fixed step size η < 1/L(w(0)), Theorem 6 establishes margin convergence at rate O(1/log t), but does not establish the same rate for convergence of w(t) itself.The result applies to any separable dataset and any initial point.Source: B Adaptive Learning Rate · pp. 10–11

B.1 Proof for Theorems 6 and 5

• The proofs extend the analysis to general norms and steepest descent, using Fenchel duality to lower-bound the dual gradient norm by the margin and thereby connect the optimization argument to the norm-SVM program.Gradient descent is recovered when the norm is L2.Source: §B.1 · p. 11, §B.2 · p. 12

B.2 Proof of Theorem 6

• Theorem 6 is proved by analyzing fixed-step steepest-descent updates for exponential loss, deriving a decreasing-loss recursion and converting it into logarithmic growth of the unnormalized margin.The proof assumes ||x_n||_* ≤ 1 and η ≤ 1/L(w(0)).Source: §B.2 · pp. 12–13

B.3 Proof of Theorem 5

• Theorem 8 applies normalized steepest descent with η_t = 1/√(t+1) to separable linear classification using exponential loss ℓ(u) = exp(−u).The result holds for any separable dataset and initialization.Source: §B.3 · p. 14
• The iterate margin converges to the maximum margin γ at rate t^-1/2 log t.The proof states this convergence rate and derives the corresponding bound in equations (49) and (59).Source: §B.3 · pp. 14–15
• Because η_t/L(w_t) < 1/L(w_t), the stepsize satisfies Lemma 12’s conditions, ensuring that the objective function decreases.The proof then analyzes one-step progress and pointwise margins.Source: §B.3 · pp. 14–15

C Tail Analysis – Proof sketch

• For strictly monotone losses with −ℓ′(u) = exp(−f(u)), the analysis studies how the increasing tail function f controls gradient-descent convergence rates.The complete proofs are deferred to later appendix sections.Source: C Tail Analysis – Proof sketch · p. 15

C.1 Convergence to the max-margin separator

• When f grows sufficiently fast, only minimum-margin samples dominate the gradients, making the limiting direction a nonnegative combination of support vectors and hence proportional to the SVM solution.This identifies the KKT conditions underlying convergence to the L2 maximum-margin separator.Source: §C.1 · p. 15

C.2 Calculation of rates and validity conditions

• The rate analysis uses continuous-time gradient descent and separates the iterate into a diverging margin scale g(t) and a lower-order residual ρ(t).The support-vector set is defined by the minimum normalized margin, while non-support-vector contributions are expected to become negligible when f increases sufficiently fast.Source: §C.2 · p. 16
• The asymptotic calculation requires f′(t) = ω(t^-1), equivalently f(t) = ω(log(t)), so that the residual scale remains lower order than g(t).Under the additional condition log(f′(t)) = o(f(t)), the differential equation for g(t) can be approximated in closed form.Source: §C.2 · p. 16

D.1 Auxillary lemma

• Lemma 3 shows that if f′(u) = ω(u^-1), then for any a1 > a2 and g(t) → ∞, f(a1 · g(t)) − f(a2 · g(t)) diverges.This establishes the asymptotic separation between larger and smaller margins needed by the general-tail proof.Source: §D.1 · p. 17
• The auxiliary argument extends the exponential-tail support-vector lemma of Gunasekar et al. (2018b) to strictly monotone losses satisfying ℓ′(u) = −exp(−f(u)) with f′(u) > 0 and f′(u) = ω(u^-1).The result applies to almost all linearly separable datasets and uses the minimum-margin support-vector set of the limiting direction.Source: §D.1 · p. 17
• The proof completes the general-tail result by showing that the normalized gradient direction is governed by the support-vector contribution, with non-support-vector terms suppressed by the margin gap.The argument relies on strict monotonicity, bounded data norms, and positivity of the relevant minimal singular value for almost all datasets.Source: §D.1 · pp. 18–19

D.2 Theorem 2 Proof

• For any depth, almost all separable datasets and initializations, and any bounded step-size sequence, the iterates satisfy Theorem 2’s directional-convergence characterization under Assumption 1.The characterization applies when the empirical loss vanishes, the predictors converge to a positive-margin separator, and predictor gradients converge in direction.Source: §D.2 · p. 19
• The proof follows Gunasekar et al. (2018a) but replaces their exponential-loss-only Lemma 8 with the extended Lemma 4.The argument uses Lemma 4 to relate the limiting parameter and gradient directions and establish the required optimality conditions.Source: §D.2 · pp. 19–20
• The limiting scaled predictor satisfies the KKT conditions of the explicitly regularized convex problem, with nonnegative dual variables supported on unit-margin samples.Positive margin permits scaling the limiting predictor to unit margin, while the limiting gradient is represented using support vectors.Source: §D.2 · p. 20
• Gradient updates for the first layer are proportional to the predictor gradient times the downstream-layer transpose, causing update and parameter directions to align asymptotically.The proof then shows the first-layer iterate and its cumulative update converge in the same direction, while the scaled residual term vanishes.Source: §D.2 · pp. 20–21
• The proof concludes that the normalized gradient–downstream-layer scale converges to the norm of the limiting predictor, yielding the final limiting relation.This follows from the vanishing error term and a squeeze-theorem argument.Source: §D.2 · p. 21

E.1 Asymptotic rates for depth L linear networks

• For depth-L linear networks, the proof obtains general-tail convergence rates by explicitly calculating the asymptotic solution from Theorem 9.The calculation completes the proof of Theorem 4, while the L = 1 specialization uses Theorem 10 to prove Theorem 3.Source: E Proof of Theorems 3 and 4 · p. 22, §E.1 · p. 22

E Proof of Theorems 3 and 4

• Theorem 9 represents the equivalent predictor as w(t) = ẇg(t) + ρ(t), with ρ(t) = o(ĝ(t)) orthogonal to the L2 maximum-margin separator.The theorem supplies the general asymptotic framework used to derive Theorems 3 and 4.Source: E Proof of Theorems 3 and 4 · p. 22

E.2 Asymptotic rates for L = 1

• For L = 1, tight exponential tails yield the optimal margin convergence rate O(1/log(t)), and this bound is tight [Soudry et al. (2018a)].Faster-than-exponential tails have rates proportional to 1/g(t), with g(t) asymptotically tied to f^-1(log(t)), implying slower convergence than 1/log(t).Source: §E.2 · p. 24

E.4 g(t) = log(t) + o(log(t)) proof for L > 1 and f(u)=u

• For L > 1 with exponential-tail f(u)=u, the proof establishes g(t) = log(t) + o(log(t)).The argument bounds the auxiliary term h(t) and combines upper and lower bounds to obtain g(t) = θ(log(t)).Source: §E.4 · pp. 28–29

F.1 Preliminaries and Auxiliary Lemma

• Under Assumption 2, an auxiliary claim controls functions h(t) = o(g(t)) when g(t) diverges, supporting the asymptotic proof framework.Assumption 2 requires f(u) to be real analytic on R++ and satisfy the stated derivative conditions.Source: §F.1 · p. 29
• A Taylor expansion gives f(g(t)+h(t)) = f(g(t)) + f′(g(t))h(t) + R(t), with R(t) = o(f′(g(t))h(t)) under the stated asymptotic conditions.The proof uses h(t) = o(g(t)), g(t) → ∞, and real analyticity of f on R++.Source: §F.1 · pp. 29–30
• These preliminary results are combined with Theorem 2, Lemmas 4–5, and claim 6 to prove Theorem 9, which characterizes the asymptotic behavior of w(t).The auxiliary lemma is introduced specifically to characterize w(t)'s asymptotic behavior.Source: §F.1 · p. 30
• For linearly independent vectors x_1, ..., x_n, the proof constructs separating vectors and applies Cauchy–Schwarz to control the coefficients α_n in asymptotic linear combinations.The argument uses, for each k, a vector u orthogonal to all x_n with n ≠ k and satisfying ⟨x_k,u⟩ = 1.Source: §F.1 · p. 30

Theorem 9

• The equivalent predictor decomposes as w(t) = ˜g(t)ˆw + ρ(t), where ρ(t) = o(˜g(t)) and ρ(t)⊤ˆw = 0.Here ˆw is the L2 maximum-margin separator.Source: §F.2 · p. 30
• When the support vectors span the dataset, the normalized predictor converges to the normalized maximum-margin separator.The stated limit is w(t)/∥w(t)∥ = ˆw/∥ˆw∥.Source: §F.2 · p. 30

Proof

• For every support vector, the correction quantity ψ_n(t) = f′(˜g(t))ρ(t)⊤x_n + R_n(t) remains asymptotically bounded.The proof establishes both upper and lower bounds, yielding ψ_n(t) = O(1).Source: §F.2 · p. 31
• The bounded support-vector corrections imply that the component of ρ(t) in the support-vector span is controlled asymptotically.Specifically, f′(˜g(t))ρ(t)⊤x_n = O(1) for every support vector, which bounds the corresponding components of ρ(t).Source: §F.2 · p. 32
• The asymptotic quantity ζ(t) is independent of the loss function, and the resulting projection scale τ(t) depends only on the dataset and network depth.The summary gives ζ(t) = Θ(1) independent of f and τ(t) = Θ(1) independent of the loss function.Source: §F.2 · pp. 33–34

G Proof that non-support vectors direction converge for L = 1

• Theorem 10 treats L = 1 under a β-smooth loss and η < 2β−1, proving the stated convergence behavior for non-support-vector directions.The proof decomposes iterates using the support-vector subspace projection Q and its complement ¯Q.Source: G Proof that non-support vectors… · p. 34
• The proof controls the complementary projection ¯Qr(t) through gradient-tail bounds, the small residual r(t) = o(g(t)), and asymptotic derivative estimates.These steps yield a bounded factor and the required decay estimate for the non-support-vector component.Source: G Proof that non-support vectors… · p. 35

G.1 Integrability proof

• Claim 8 supplies the integrability argument when f ′(u) has the stated lower-growth condition for some ϵ > 0.The derivation uses a change of variables, g(t) →∞, and bounds involving log(g) and Bernoulli’s inequality.Source: §G.1 · p. 36

H Examples

• The general-tail theorem covers any depth L, almost all separable datasets and initializations, and bounded step-size sequences under the stated strictly monotone-tail assumptions.When loss vanishes, the iterates yield a positive-margin separator, and predictor gradients converge directionally, the limit direction is specified by the theorem.Source: H Examples · pp. 36–37

H.1 Example: non-convergence to the max-margin separator

• For polynomial-tailed losses, the iterates do not converge to the max-margin separator: in the example, f(t) = 2 log(t), violating the required ω(log(t)) growth.The continuous-time solution produces distinct cubic-root scaling for the two coordinates, and the analysis verifies failure whenever −ℓ′(u) is polynomial.Source: §H.1 · p. 37
• With exponential loss on the same example, f(u) = u and g(t) ≍ log(t), yielding convergence to the max-margin separator.This agrees with the earlier theorem because h(t) = 1.Source: §H.1 · p. 37

H.2 Example: sub-poly-exponential tails that converge to the max margin separator

• For sub-poly-exponential tails with ϵ > 1, f(t) = Θ(log^ϵ(t)) = ω(log(t)), and the example converges to the max-margin separator.The integrated dynamics satisfy exp(log^ϵ(w1(t))) = t + C and exp(log^ϵ(2w2(t))) = 4t + C; for ϵ ≤ 1, convergence fails.Source: §H.2 · p. 38

H.3 Example: Demonstrating that the upper bound in Theorem 3.1 is not always obtained

• In H.3, the iterate decomposes as w(t) = g(t) ˆw + ρ(t), linking the trajectory to the max-margin direction.The cited example identifies ˆw = (1, 0.5).Source: §H.3 · p. 38
• The H.3 example yields the same asymptotic margin-convergence rate as exponential loss, but with better constants.The rate is proportional to 1 ν log(t).Source: §H.3 · p. 38

H.4 Example: Demonstrating that the upper bound in Theorem 3.1 is tight

• The H.4 construction shows that the Theorem 3.1 rate upper bound is tight for a loss satisfying the stated tail condition.The example uses one data point x1 = (1, 0) and takes the continuous-time limit η → 0.Source: §H.4 · p. 39
• In the H.4 example, integrating the continuous-time dynamics gives w2(t) = w2(0), and choosing w2(0) > 0 establishes tightness.Source: §H.4 · p. 39

I.1 Implementation details of Figure 1

• Figure 1 uses four original support vectors, adds 6 random points per class outside the support-vector set, and rescales all datapoints so maxn ||xn|| < 1.The original labels are y1 = y2 = 1 and y3 = y4 = −1.Source: §I.1 · p. 39
• Training initializes w(0) ∼N(0, Id), uses η = 1/β for GD, and uses the same initial step size for normalized GD.Source: §I.1 · p. 39
• Normalized GD’s training error converges to zero much faster than GD, but its margin-gap curve is less stable under the aggressive learning rate.The instability is attributed to rapid switching of the datapoint with the smallest margin near numerical precision limits.Source: §I.1 · p. 39

Experimental setup

• A learning rate of η = 0.005 was chosen for stable, non-slow optimization, while larger rates often caused GD and Normalized GD to struggle to maintain data separation.Weights were initialized from N(0, 0.1), gradients were normalized together, and hidden layers contained 10 neurons.Source: §I.2 · p. 39

Logistic regression

• Normalized GD converges significantly faster than GD to the max-margin solution on logistic regression trained for 5×10^4 epochs.The experiment uses angle and margin gaps relative to an L2 max-margin vector obtained from an SVM solver.Source: §I.2 · p. 39, Figure 5 · p. 40

Experimental setup

• The experiments use a 600-point, 2-dimensional synthetic dataset with 300 positive and 300 negative samples, reused across all experiments.Positive and negative samples are generated from separate Gaussian distributions.Source: §I.2 · p. 39, Figure 5 · p. 40

2-layer neural networks

• For 2-layer networks, linear and ReLU convergence plots are similar, while Normalized GD remains noticeably faster and reaches zero numerical loss in roughly 10^4 epochs.The architecture is 2 × 10 × 1 and training lasts 5×10^4 epochs.Source: §I.2 · p. 39, Figure 6 · p. 40

3-layer neural networks

• For 3-layer networks, linear and ReLU convergence plots are similarly shaped, indicating comparable behavior across these activations.The architecture is 2 × 10 × 10 × 1 and training lasts 5×10^4 epochs.Source: §I.2 · p. 39, Figure 7 · p. 41

J Losses with poly-exponential tails

• For almost all linearly separable datasets, gradient descent with a β-smooth objective and tight poly-exponential loss-derivative tail converges in direction to the normalized L2 maximum-margin separator when ν > 0.25 and η < 2β^-1.The result holds for any initialization and strictly monotone loss satisfying the stated tail condition.Source: J Losses with poly-exponential tails · p. 41

K Calculation of convergence rates for poly-exponential tails

• The convergence-rate analysis shows that poly-exponential tails achieve their optimal rate at ν = 1, while rates become slower as |ν − 1| increases for ν > 0.25.The analysis covers distance, margin suboptimality, and angle convergence rates through Theorem 11 and Table 1.Source: J Losses with poly-exponential tails · p. 41, Table 1 · p. 42
• The proof decomposes the iterates into a maximum-margin component and a residual, then derives normalized-weight, angle, and margin convergence from the residual’s asymptotic behavior.The decomposition is written as w(t) = ˆw g(t) + ρ(t), with subsequent calculations yielding the three convergence measures.Source: K Calculation of convergence rates for… · pp. 42–43

K.1 Proof of Theorem 11

• The proof framework establishes that the loss tends to zero, the weight norm diverges, and every training margin tends to infinity under separability and η < 2β^-1.These properties supply the asymptotic basis for analyzing the poly-exponential tail.Source: §K.1 · p. 44

K.2.1 Definitions and auxiliary calculations

• The auxiliary calculations define functions controlling the asymptotic expansion and establish bounds such as a vanishing increment error for g(t).These estimates use basic analysis and Bernoulli’s inequality to control the remainder terms.Source: §K.2.1 · pp. 44–45

K.2.2 Proof Of Theorem 11 for ν > 1

• For ν > 1, the proof aims to show that the residual r(t) remains bounded, which makes the correction term ρ(t) bounded up to the stated asymptotic component.The argument expands ||r(t + 1)||^2 and separately bounds its increment and cross terms.Source: §K.2.2 · p. 45
• In the ν > 1 proof, the residual increment becomes arbitrarily small, while its cross term is bounded by a decaying logarithmic expression, enabling the final boundedness argument.The proof combines these estimates with convergent power-series bounds for ν > 1.Source: §K.2.2 · pp. 45–46

K.2.3 Proof Of Lemma 8

• The residual is defined as r(t) = w(t) − g(t) ˆw − g1−ν(t) ˜w, and for all sufficiently large t, (r(t + 1) − r(t))⊤r(t) ≤ C1t−1(log(t))−1−1.Source: §K.2.3 · p. 46

K.3.1 Auxiliary results

• The auxiliary results show that the correction functions and remainder terms are o(log^ϵ(t)) for every ϵ > 0.These asymptotic estimates support the Taylor expansions and error bounds used in the subsequent proofs.Source: §K.3.1 · pp. 52–53

K.3.2 Proof Of main Theorem ( 1

• The main-theorem proof aims to show ∥r(t)∥ = o(g1−ν(t)), implying ρ(t) = O(g1−ν(t)), and uses the residual-norm recursion together with Lemma 9.It expands ∥r(t + 1)∥2 into increment, cross, and previous-norm terms, then bounds each contribution.Source: §K.3.2 · p. 55

K.3.3 Proof Of Lemma 9

• Lemma 9 bounds the residual cross term using the decomposition of r(t), Taylor expansions, auxiliary estimates, and the facts that relevant inner products are o(t) and gradients vanish.The proof handles the terms in the recurrence separately and exploits the margin condition θ = min_n∉S ˆw^⊤x_n > 1.Source: §K.3.3 · pp. 56, 57, 59
• The proof handles x_k^T r(t) ≥ 0 and x_k^T r(t) < 0 separately, applying Taylor’s theorem, e^-x ≤ 1 − x + x^2, Bernoulli’s inequality, and asymptotic decay from Lemma 6.For the negative-sign case, the argument further splits according to the magnitude of x_k^T r(t) and shows the relevant expression eventually becomes negative.Source: §K.3.3 · pp. 61–62
• For every t > t0, each term in equation (213) is bounded above by either zero or a term proportional to t−1 log−1.Source: §K.3.3 · p. 63
• Combining the bounds from equations (206), (209), and (212) with equation (205) gives constants C8, C9, and C10, after which some t1 > t0 and C1 ensure equation (150) holds.The conclusion is established for sufficiently large t.Source: §K.3.3 · p. 63