Source-linked AI summary
Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate
Mor Shpigel Nacson, Nathan Srebro, Daniel Soudry
TL;DR
Prior theory generally required a vanishing learning rate, iterate averaging, or other assumptions to guarantee SGD convergence, while fixed-rate training can reach zero loss in practice. This paper proves convergence results for homogeneous linear classifiers on separable data, including max-margin behavior and minibatch scaling. Under the stated conditions, SGD can converge with a fixed learning rate, and its asymptotic epoch rate is independent of minibatch size when support vectors span the data and the learning rate scales with batch size.
Problem
Prior SGD convergence analyses generally required a vanishing learning rate, iterate averaging, or assumptions such as partial strong convexity or the PL condition, while fixed-rate training can reach zero loss in practice.
Source: §1 · pp. 1–2Method
The paper analyzes SGD on homogeneous linear classifiers with smooth monotone losses and linearly separable data, for sampling with or without replacement.
Source: §1 · p. 2Results
Takeaways & Limitations
The results establish exact fixed-rate convergence in this separable linear setting without requiring a decreasing learning rate or iterate averaging.
Source: §5 · p. 7Whether the minibatch-size result also holds for deep networks remains to be seen.
Source: §6 · p. 8
Abstract
from arXiv · showhide
Stochastic Gradient Descent (SGD) is a central tool in machine learning. We prove that SGD converges to zero loss, even with a fixed (non-vanishing) learning rate - in the special case of homogeneous linear classifiers with smooth monotone loss functions, optimized on linearly separable data. Previous works assumed either a vanishing learning rate, iterate averaging, or loss assumptions that do not hold for monotone loss functions used for classification, such as the logistic loss. We prove our result on a fixed dataset, both for sampling with or without replacement. Furthermore, for logistic loss (and similar exponentially-tailed losses), we prove that with SGD the weight vector converges in direction to the $L_2$ max margin vector as $O(1/\log(t))$ for almost all separable datasets, and the loss converges as $O(1/t)$ - similarly to gradient descent. Lastly, we examine the case of a fixed learning rate proportional to the minibatch size. We prove that in this case, the asymptotic convergence rate of SGD (with replacement) does not depend on the minibatch size in terms of epochs, if the support vectors span the data. These results may suggest an explanation to similar behaviors observed in deep networks, when trained with SGD.
1 INTRODUCTION
The introduction asks why SGD learning rates are usually decreased, given that fixed-rate training can reach zero loss in practice. It presents proofs of zero-loss convergence for separable homogeneous linear classifiers and further results on max-margin direction and minibatch scaling.
1 INTRODUCTION
- Earlier analyses generally required a vanishing learning rate, iterate averaging, partial strong convexity, or the PL condition, which does not hold for neural-network losses near minima.These conditions left a gap between theory and the observed fixed-rate decrease of training loss.Source: §1 · pp. 1–2
- With a fixed learning rate, ResNet-18 on CIFAR10 reaches zero training loss and classification error; during training, validation classification error continues to decrease while validation loss starts to increase.Source: §1 · pp. 1–2
- The paper studies homogeneous linear classifiers with smooth monotone losses under sampling with or without replacement, focusing on binary classification.The authors suggest the results may extend to settings including deep networks, but do not establish those extensions here.Source: §1 · p. 2
- For a sufficiently small fixed learning rate, SGD loss and gradients converge to zero on linearly separable data with smooth monotone loss.The authors also prove that the weight norm diverges for any learning rate.Source: §1 · p. 2
- For almost all separable datasets with exponentially tailed loss, the weight direction converges to the L2 max-margin direction, with margin O(1/log(t)) and training loss O(1/t).The authors state these conclusions match gradient descent, apart from the maximal learning rate's dependence on minibatch size.Source: §1 · p. 2
- With learning rate proportional to minibatch size and support vectors spanning the data, minibatch size does not affect SGD's asymptotic convergence rate in epochs.In SGD iterations, the fastest asymptotic rate is obtained at full batch size, or gradient descent.Source: §1 · p. 2
2 PRELIMINARIES
The preliminaries define the binary homogeneous linear-classification setting and its separability and loss assumptions. They also describe the sampling schemes considered, including balanced passes through the dataset without replacement.
2 PRELIMINARIES
- The setup uses binary labels and homogeneous linear predictors, meaning the predictors have no bias term.Labels can be normalized to 1 by redefining each y_n x_n as x_n.Source: §2 · p. 2
- The dataset is assumed strictly linearly separable, and the loss is smooth, strictly decreasing, and nonnegative; logistic and probit losses satisfy the stated loss assumptions.Under these conditions, the infimum loss is zero but is not attained at any finite weight vector.Source: §2 · pp. 2–3
- In the illustrated CIFAR10 training example, training loss and classification error approach zero, while validation loss rises and validation classification error slowly improves.The example uses constant-rate SGD with softmax output and cross-entropy loss.Source: Figure 1 · p. 3
- Sampling with replacement draws a uniformly selected minibatch at each iteration, while sampling without replacement partitions the data into minibatches each epoch.Without replacement, each sample is selected exactly once per epoch; the order may be random, periodic, or adversarial.Source: §2 · p. 3
3 MAIN RESULT 1: THE LOSS CONVERGES TO A GLOBAL INFIMUM
For linearly separable data and smooth monotone losses, SGD with a sufficiently small fixed learning rate drives the loss to zero under either sampling regime. The iterates nevertheless diverge in norm, and the theorem also guarantees eventual correct classification and square-summable iterates.
3 MAIN RESULT 1: THE LOSS CONVERGES TO A GLOBAL INFIMUM
- The SGD iterates diverge in norm for either sampling regime, despite the loss approaching its infimum.The divergence holds from any starting point under the stated assumptions.Source: §3 · p. 3
- The loss converges to zero with a sufficiently small fixed learning rate under both sampling regimes.The result applies to linearly separable data and smooth monotone loss functions.Source: §3 · p. 4
- All samples are eventually classified correctly, and the SGD iterates are square summable.Both conclusions accompany the zero-loss result under the theorem's separability and loss assumptions.Source: §3 · p. 4
- For sampling with replacement, the maximal-learning-rate upper bound is proportional to minibatch size; without replacement, the bound is roughly proportional to 1/K.The without-replacement bound reflects a pessimistic schedule that can include adversarial sample ordering.Source: §3 · pp. 4–5
4 MAIN RESULT 2: THE WEIGHT VECTOR DIRECTION CONVERGES TO THE MAX MARGIN
For almost all separable datasets and exponentially tailed losses, SGD's normalized weights converge to the L2 max-margin direction. The paper gives logarithmic direction and margin-gap rates, a 1/t loss rate, and a minibatch-size result under a support-vector span condition.
4 MAIN RESULT 2: THE WEIGHT VECTOR DIRECTION CONVERGES TO THE MAX MARGIN
- The normalized SGD weight vector converges to the normalized L2 max-margin vector at rate 1/log(t) for almost all qualifying separable datasets.The result assumes a tight exponential tail for the negative loss derivative and holds for logistic loss.Source: §4 · p. 5
- The SGD-to-gradient-descent dynamics difference stays O(1) in t, with the proof using future sampling selections to bound that difference.The argument adapts the gradient-descent proof by controlling the effect of updating from data subsets.Source: §4 · p. 5
- The L2 distance and margin gap to the max-margin direction decrease logarithmically, while the training loss decreases as 1/t.These rates match those established for gradient descent.Source: §4 · p. 5
- When support vectors span the data, the asymptotic residual depends on the dataset and initialization, but not on K, η, or B.Under η proportional to B, changing K is equivalent to linearly rescaling time units.Source: §4 · p. 6
- With support vectors spanning the dataset and learning rate proportional to minibatch size, SGD has the same asymptotic convergence behavior across minibatch sizes in epoch units.The guarantee is asymptotic; initialization and dataset can affect earlier behavior.Source: §4 · p. 6
5 DISCUSSION AND RELATED WORKS
The discussion argues that fixed-rate SGD can reach zero loss without iterate averaging or the loss conditions required by earlier exact-convergence results. It also identifies exponential-tail rates and minibatch scaling results, with the latter conditional on support vectors spanning the data.
5 DISCUSSION AND RELATED WORKS
- With a sufficiently small fixed learning rate, SGD converges to zero loss on separable data without averaging; its inherent noise vanishes asymptotically.The paper proves this for smooth monotone losses and both sampling regimes, while noting that decaying the rate slows loss convergence.Source: §5 · p. 7
- Unlike earlier exact-convergence results requiring partial strong convexity or the PL condition, this analysis does not require either condition.The discussion notes these conditions do not hold for deep networks, even near finite or infinite critical points.Source: §5 · p. 7
- For random sampling with replacement, the convergence guarantee requires increasing the learning rate proportionally to minibatch size; the without-replacement bound is more pessimistic.The latter bound applies under a more general sampling assumption, including adversarial sampling.Source: §5 · p. 7
- For almost all datasets with exponential-tail loss, the weight direction converges to the L2 max margin as 1/log(t), while training loss converges as 1/t.The discussion says decaying the learning rate degrades convergence to the max-margin direction.Source: §5 · p. 7
- When support vectors span the data, scaling learning rate linearly with minibatch size leaves SGD's asymptotic convergence rate in epochs unaffected by minibatch size.The authors report matching asymptotic convergence plots across minibatch sizes and say the largest batch can reduce iterations when minibatches can be parallelized.Source: §5 · pp. 7–8
6 CONCLUSIONS
The conclusion reports that logistic regression without bias on separable data has SGD dynamics similar to GD in implicit bias and convergence rate, while the maximum learning rate scales with minibatch size. Whether this behavior extends to deep networks remains open; the appendix also describes a learning-rate notation change.
6 CONCLUSIONS
- For logistic regression without bias on separable data, SGD behaves similarly to GD in implicit bias and convergence rate.The conclusion identifies the maximum possible learning rate as the difference, scaling it proportionally to minibatch size.Source: §6 · p. 8
Appendix
- The appendix absorbs the constant 1/B into the learning-rate dynamics for notation, then modifies its results to match the main paper's SGD dynamics.Source: Appendix · p. 10
A Proof of Theorem 1
The proof treats sampling with and without replacement separately, using bounds on SGD updates and gradients to establish the relevant convergence claims. Its without-replacement argument controls changes within an epoch before showing the gradient norm vanishes and margins diverge.
A.1 Case 1: Random sampling with replacement
- With replacement, the proof establishes with probability 1 that all sample margins diverge, implying the loss tends to zero.Source: §A.1 · p. 11
A.2 Case 2: Sampling without replacement
- Linear separability supplies a lower bound on update increments, which lets the proof bound SGD increments and related quantities using the full-gradient norm.The proof then uses smoothness and bounds on within-epoch gradient changes to complete the without-replacement case.Source: §A.2 · p. 11
- The proof shows that the gradient norm tends to zero, then uses equation 17 and assumption 2, where the squared derivative vanishes only at infinity, to establish that the sample margins diverge to infinity.Source: §A.2 · p. 12
B.1 Theorem 2 Proof
The proof controls an auxiliary residual sequence to establish boundedness, using its update behavior and the square-summability of SGD increments. It also expresses the asymptotic weight vector through support-vector contributions and a bounded residual component.
B.1 Theorem 2 Proof
- The weight decomposition uses support-vector indices and SVM dual variables, with a finite vector constant in time and a remainder whose norm is o(·).The proof also defines projections onto the support-vector span and its complement.Source: §B.1 · p. 15
- The proof's goal is to bound r(t), which in turn bounds ρ(t); it establishes that r(t) is bounded.The argument uses an inner-product bound on successive residual changes and the squared-norm identity for r(t).Source: §B.1 · pp. 15–16
- The proof uses the finiteness of the sum of squared SGD increments to control the residual sequence's changes.Source: §B.1 · p. 16
B.2 Theorem 3 Proof
The proof addresses whether the residual term vanishes under the stated rank condition and whether the resulting vector is unique given the initialization. It handles an unchanged orthogonal component separately and uses bounds on the residual norm.
B.2 Theorem 3 Proof
- The proof targets ∥r(t)∥→0 when rank(XS) = rank(X), and uniqueness of w̃ given w(0).These are the two goals stated for continuing the proof of Theorem 2.Source: §B.2 · p. 17
- When rank(XS) = rank(X), the data columns are spanned by the support-vector columns, so the orthogonal component of r(t) is not updated.The proof absorbs this constant component into w̃ without affecting eq. 15.Source: §B.2 · p. 17
- The proof uses arbitrarily small bounds on h(t) and ∥r(t3)∥ at suitable indices t3 to control the residual.It derives ∥r(t3)∥ ≤ ϵ1 + ϵ0 and can choose t3 so that h(t3) < ϵ2.Source: §B.2 · p. 17
B.3 Proof of Lemma 6
The proof of Lemma 6 bounds the residual’s one-step inner product using exponential-tail losses and support-vector conditions. The following Lemma 5 proof establishes a vector representation for both sampling schemes.
B.3 Proof of Lemma 6
- The Lemma 6 argument assumes an exponential-tail loss and uses linear independence of support vectors for almost every dataset.The proof identifies the tail condition as part of its setup and invokes support-vector independence in bounding a matrix term.Source: §B.3 · pp. 18, 21
- The Lemma 6 proof obtains a negative asymptotic upper bound on (r(t + 1) − r(t))⊤r(t).It first gives a bound by terms proportional to t^-θ and t^-1-0.5μ̃, then derives a bound of −C′′t^-1 + o(t^-1).Source: §B.3 · pp. 18, 21
B.4 Proof of Lemma 5
- Lemma 5 gives a representation involving the support vectors, a finite time-constant vector, and a vanishing remainder for both sampling schemes.The result holds almost surely with replacement and surely without replacement.Source: §B.4 · p. 21
B.4.1 Proof for random sampling with replacement
The sampling proofs establish convergence of the sums used in the Lemma 5 argument. With replacement, the convergence is almost sure; without replacement, it follows from bounds on the sampled indices.
B.4.1 Proof for random sampling with replacement
- With replacement, the proof represents sample selection using an indicator for whether each example is chosen at an iteration.It then bounds the resulting infinite sum and its tail.Source: §B.4.1 · pp. 21–22
- The random-sampling sum is shown to converge with probability 1, and the proof combines its bounds to establish the lemma.The tail bound uses the Hoeffding inequality.Source: §B.4.1 · p. 22
B.4.2 Proof for sampling without replacement
- Without replacement, the proof uses the bounded minibatch indices to show the remaining sum converges and complete the lemma’s proof.Each term is stated to be Θ of a decaying quantity.Source: §B.4.2 · p. 23
C Additional empirical results
Figure 4 visualizes Theorem 2 on synthetic datasets with dimensions 5 and 10, where the L2 max-margin vector is known. It shows logarithmic norm growth, t^-1 loss decay, and logarithmic decreases in angle and margin gap.
C Additional empirical results
- The weight norm increases logarithmically over iterations in the d = 5 and d = 10 visualizations.The norm is normalized to equal 1 at the final iteration.Source: Figure 4 · p. 24
- The training loss decreases as t^-1 in the visualized synthetic datasets.The caption identifies this as the behavior expected from eq. 14.Source: Figure 4 · p. 24
- The angle and margin gap from the known L2 max-margin vector decrease logarithmically toward zero.The caption associates these trends with eqs. 12 and 13.Source: Figure 4 · p. 24