REVIEW 2 major objections 6 minor 14 references
Mini-batch stochastic steepest descent — the family behind SignSGD and Muon — converges to a norm-max-margin solution only with large batches, momentum, or variance reduction; at batch size one, it can converge to a different solution entir
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
2026-08-03 00:07 UTC pith:PLIXWXL4
load-bearing objection Real, carefully built theory for mini-batch steepest descent bias, but the momentum result is tied to random reshuffling and the experiments are too thin; deserves a serious referee. the 2 major comments →
The Implicit Bias of Steepest Descent with Mini-batch Stochastic Gradient
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For linearly separable multi-class data, the paper shows that the implicit bias of mini-batch stochastic steepest descent is governed by an effective margin: without momentum, ρ = γ − 4(n/b − 1)R, so only a large batch reaches an approximate max-margin solution; with momentum, ρ = γ − 2(1−β1)(n/b)((n/b)²−1)R, so small batches converge as β1 → 1 at the price of slower rates; with variance reduction, the full margin γ is recovered for any batch size. On an orthogonal scale-skewed dataset, batch-size-one SignSGD and Normalized-SGD converge instead to a sample-averaged, class-frequency-dependent direction, a bias fundamentally different from the max-margin solution.
What carries the argument
A proxy function G(W) — the average softmax misclassification probability — brackets the gradient norm between γ·G(W) and 2R·G(W), and an effective margin ρ quantifies how much the stochastic direction misaligns with the full gradient. Two bounds carry the argument: the mini-batch noise bound ∥∇L_B(W) − ∇L(W)∥ ≤ 2(n/b − 1)R·G(W), and the momentum bound (1−β1)(n/b)((n/b)²−1)R·G(W), which uses the zero-sum property of batch errors within each random-reshuffling epoch. Variance-reduced estimators remove the batch-dependent noise term. Positivity of ρ forces monotone loss decrease and margin growth.
Load-bearing premise
The momentum and variance-reduction recovery theorems assume random reshuffling, where each epoch visits every sample exactly once so batch errors sum to zero across the epoch; if batches are drawn with replacement, or data arrives in a non-epochal stream, that cancellation breaks and the recovery results have no stated analogue.
What would settle it
Train a separable multi-class problem with mini-batch SignSGD or Normalized-SGD without momentum, using a batch b well below n, and measure the margin of the converged direction: the theory predicts a limiting margin of γ − 4(n/b − 1)R, strictly below the full margin γ. Observing convergence to γ — or a gap that does not scale with (n/b − 1) — would refute the central claim. A second check targets the mechanism: run the same comparisons with with-replacement sampling; if momentum and variance reduction still recover the full-batch margin, the epoch-wise zero-sum cancellation is not what carrie
If this is right
- Without momentum, small-batch steepest descent — including SignSGD and Normalized-SGD — converges to a margin ρ below the full margin γ, with the gap roughly proportional to (n/b − 1)R; only as the batch approaches the full data size does the limit approach the true norm-max-margin solution.
- Momentum acts as a partial substitute for batch size: taking β1 → 1 removes the large-batch requirement, and the effective margin gap is governed by the product (1 − β1)(n/b)((n/b)² − 1)R, at the cost of slower convergence.
- Variance reduction makes the implicit bias independent of batch size and momentum: the algorithm converges to the exact full-batch max-margin solution for any batch size, with more conservative rates.
- The margin convergence rates are explicit and free of the feature dimension d, a technical improvement over earlier full-batch analyses.
- Batch-size-one stochastic steepest descent without momentum can converge to a fundamentally different, sample-averaged bias, so no unified implicit-bias theorem can cover all batch sizes for these algorithms.
Where Pith is reading between the lines
- A practical reading the paper leaves implicit: in runs where the max-margin solution is the goal, batch size is a solution-shaping hyperparameter, and the predicted gap (n/b − 1)R gives a quantitative rule for how far the batch can shrink before the bias degrades.
- An extension worth testing: measure the normalized margin of converged mini-batch runs across a range of batch sizes; the effective-margin formula predicts the gap γ − ρ should scale linearly with n/b − 1.
- The random-reshuffling epoch structure is essential to the momentum and variance-reduction results; with with-replacement sampling the epoch-wise cancellation fails, so the same guarantees may shift or disappear — a gap the paper does not address.
- The batch-size-one construction suggests other per-sample stochastic update rules beyond steepest descent may also drift toward class-frequency-averaged limits on structured data, implying max-margin convergence is the exception rather than the default for small-batch stochastic training.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the implicit bias of mini-batch stochastic steepest descent for multi-class linear classification under entry-wise and Schatten-p norms, assuming Random Reshuffling. It characterizes how batch size, momentum, and variance reduction affect convergence to norm-induced max-margin solutions. The main results are: (i) without momentum, large batches are needed and the limiting margin is an effective margin ρ = γ − 4(n/b − 1)R, with full-batch rates; (ii) momentum enables small-batch convergence with effective margin ρ = γ − 2(1−β1)m(m²−1)R, so the gap closes as β1→1 or b→n; (iii) SVRG-style variance reduction recovers the exact full-batch margin γ for any batch size, with slower rates; and (iv) for a specific orthogonal scale-skewed dataset, batch-size-one SignSGD and Normalized-SGD converge to a sample-averaging bias different from the max-margin solution. The proofs are detailed and organized as descent lemmas, loss convergence, unnormalized margin growth, and normalized margin gap bounds.
Significance. If the results hold, this is a substantial contribution to the theory of stochastic steepest descent. The paper unifies several practical optimizers (SignSGD, Normalized-SGD, Muon) into a single norm-based framework and gives the first systematic analysis of how mini-batching changes implicit bias. The dimension-free rates and the explicit batch–momentum trade-off are concrete improvements over earlier full-batch analyses. The paper also provides a clean positive result for variance reduction. The experiments support the theoretical predictions, and the appendix contains detailed, mostly self-contained proofs. These strengths make the paper worth serious consideration.
major comments (2)
- [§3.1, Lemma C.12, Theorems 4.1/4.3/4.6] The central results are proved only for Random Reshuffling (sampling without replacement in complete epochs), but the theorem statements do not state this assumption and the abstract/contributions describe them as results on 'mini-batch stochastic steepest descent' in general. Lemma C.12's key bound relies on the zero-sum property of batch errors over a full epoch, and Lemma C.11 uses the finite-population identity. Under with-replacement sampling or a non-epochal stream, these identities fail; the accumulated momentum error would no longer carry the (1−β1) factor that makes the effective margin ρ = γ − 2(1−β1)m(m²−1)R close to γ as β1→1. Thus the advertised generality is broader than what is proved. Please add 'random reshuffling' explicitly to the theorem statements and qualify the abstract and contribution bullets, or provide a separate treatment of the with-replacement case.
- [§4.4, Theorem 4.9] The statement that batch-size-one steepest descent 'reveals a key limitation of purely stochastic updates' and that 'there may not exist a unified implicit bias theory covering steepest descent with small batch sizes' goes beyond what is proved. Theorem 4.9 establishes convergence to a different bias only on the specific orthogonal scale-skewed dataset with x_i = α_i e_{y_i}. This is a construction, not a general characterization; the broader claim is an extrapolation. The limitations paragraph acknowledges the restricted dataset, but the abstract and contribution list still state the conclusion more strongly. Please soften those statements or prove a formal general counterexample.
minor comments (6)
- [Corollary 4.5 and Appendix E.5, a=1 case] The displayed rate for a=1 appears to be missing the denominator ∑η_s = log t. As written, O(n log(m/(1−β1)) + (m/(1−β1)) log t) diverges, which contradicts Theorem 4.3. It should be O((n log(m/(1−β1)) + m/(1−β1))/log t).
- [Definition 4.8] The formula for the Normalized-SGD bias matrix is garbled by line breaks. Use consistent notation such as \bar W = ∑ (e_{y_i} − 1/K 1)/||e_{y_i} − 1/K 1||_2 · x_i^⊤/||x_i||_2.
- [Lemma C.3 proof] There is a typo 'Fisrt' and the sentence 'we compute the entry-wise 1-norm of x' should refer to the matrix H. The argument is correct but these need fixing.
- [Abstract] 'paves the way for perform deeper explorations' should read 'paves the way for deeper explorations'.
- [Section 5] The experiments would be more convincing with multiple seeds and error bars, and with a statement about whether the large-batch condition b > 4Rn/(γ+4R) is satisfied in the b=20 panels. As is, the 'failure' of b=20 is plausible but not quantitatively connected to the theory.
- [References] The reference 'Kingma, 2014' should be 'Kingma and Ba, 2015' (Adam paper).
Circularity Check
No significant circularity: central margin claims are proved from data-defined margins and derived worst-case bounds; effective margins are not fitted inputs.
full rationale
The paper's main results—convergence of mini-batch steepest descent without momentum to an effective margin ρ = γ − 4(n/b − 1)R, and restoration of the full-batch margin by momentum or variance reduction—are not equivalent to their inputs by construction. The target γ is the standard data-defined max margin, and ρ is a deterministic worst-case quantity derived in Lemmas C.11 and C.12 via finite-population identities and the zero-sum epoch property; looser noise bounds would only make the guaranteed margin smaller, so the direction of the argument is safe. The proxy-function framework is imported from Fan et al. (2025) with proofs reproduced in the appendix, not from the present authors' own prior work, and the results are benchmarked externally against the full-batch max-margin solution. All load-bearing technical lemmas (descent, loss convergence, unnormalized margin growth) are proved in Appendices D–G. The only self-citations (Zhang et al. 2024, Tang et al. 2025a) appear in background or assumption context and are not load-bearing. Section 4.4's bias matrix Wbar is indeed defined as a sum of per-sample update directions, and Theorem 4.9 shows convergence to it; for the constructed orthogonal dataset this conclusion is close to the definition, but the proof supplies the nontrivial invariant-gradient lemma and the epoch-drift bound, so it is not a fitted input renamed as a prediction. The dependence on random reshuffling is an explicit scope assumption rather than a circular step.
Axiom & Free-Parameter Ledger
free parameters (3)
- learning rate exponent a (and scale c, η0)
- momentum β1
- batch size b (equivalently m = n/b)
axioms (7)
- domain assumption Assumption 3.1: data linearly separable with positive margin γ
- domain assumption Assumption 3.2: ∥xi∥1 ≤ R
- standard math Assumption 3.3: ηt → 0 and Σηt = ∞
- ad hoc to paper Assumption 3.4: technical β-weighted learning-rate condition
- domain assumption Random reshuffling with epoch partition (n = mb)
- standard math Proxy-function framework from Fan et al. 2025 (Lemmas C.1–C.10)
- ad hoc to paper Orthogonal scale-skewed dataset xi = αi e_{y_i} (Section 4.4)
invented entities (1)
-
Bias directions matrix W̄ (Definition 4.8)
independent evidence
Cite this review
Pith. "Pith review of The Implicit Bias of Steepest Descent with Mini-batch Stochastic Gradient." pith.science (2026). https://pith.science/paper/PLIXWXL4
@misc{pith2026260211557,
author = {Pith},
title = {Pith review of: The Implicit Bias of Steepest Descent with Mini-batch Stochastic Gradient},
year = {2026},
howpublished = {\url{https://pith.science/paper/PLIXWXL4}},
note = {Machine review of arXiv:2602.11557}
}
read the original abstract
A variety of widely used optimization methods like SignSGD and Muon can be interpreted as instances of steepest descent under different norm-induced geometries. In this work, we study the implicit bias of mini-batch stochastic steepest descent in multi-class classification, characterizing how batch size, momentum, and variance reduction shape the limiting max-margin behavior and convergence rates under general entry-wise and Schatten-$p$ norms. We show that, without momentum, worst-case convergence and successful classification can only be guaranteed with full-batch gradient. In contrast, momentum enables small-batch convergence to an approximate max-margin solution through a batch-momentum trade-off, though it slows convergence. This approach provides fully explicit, dimension-free rates that improve upon prior results. Moreover, we prove that variance reduction can recover the exact full-batch implicit bias for any batch size, albeit at a slower convergence rate. Finally, we further investigate the batch-size-one steepest descent without momentum, and reveal its convergence to a fundamentally different bias via a concrete data example, which reveals a key limitation of purely stochastic updates. Overall, our unified analysis clarifies when stochastic optimization aligns with full-batch behavior, and paves the way for perform deeper explorations of the training behavior of stochastic gradient steepest descent algorithms.
Figures
Reference graph
Works this paper leans on
-
[1]
Denominator Estimation ( P ηs):Using integral approximation Pt s=1 s−a ≈ R t 1 x−adx, we have: t−1X s=0 ηs = ( O(t1−a) ifa <1 O(logt) ifa= 1
-
[2]
Thus, for any p≥ 1, vv⊤ S = ∥v∥2
-
[3]
Estimation of the Quadratic Term ( P η2 s ):Similarly, using integral approximationPt s=1 s−2a: t−1X s=t2 η2 s = Θ(t1−2a) ifa <1/2 Θ(logt) ifa= 1/2 Θ(1) ifa >1/2 (converges to a constant)
-
[4]
20 •Case II: Entry-wise p-norms.Using the consistency of vector and matrix norms: ∥vv⊤∥=∥v∥ 2 p ≤(∥∆∥∥x∥ ∗)2 ≤R 2∥∆∥2
Using the spectral norm property ∥∆∥S∞ ≤ ∥∆∥Sp and∥x∥ 2 ≤R: vv⊤ S =∥v∥ 2 2 ≤ ∥∆∥2 S∞ ∥x∥2 2 ≤ ∥∆∥2 S ∥x∥2 2 ≤R 2 ∥∆∥2 S . 20 •Case II: Entry-wise p-norms.Using the consistency of vector and matrix norms: ∥vv⊤∥=∥v∥ 2 p ≤(∥∆∥∥x∥ ∗)2 ≤R 2∥∆∥2. In both cases, we obtain: ∥vv⊤∥ ≤R2∥∆∥2.(C.10) Conclusion.Substituting (C.9) and (C.10) back into (C.8) yields the d...
2025
-
[6]
Since t1 is a constant independent of n (determined only by ρ and curvature), for large n, the LHS is dominated by the sum up to t2
Estimation oft 2 and Pt2−1 s=0 ηs:Recall the condition fort 2 from Lemma D.2: t2X s=t1 ηs ≥ C ρ ˜L = C·n ρlog 2 , where C depends on L(W0) and R, but is independent of t. Since t1 is a constant independent of n (determined only by ρ and curvature), for large n, the LHS is dominated by the sum up to t2. Thus: t2−1X s=0 ηs =O(n). This directly bounds the se...
-
[8]
Let Ss = Ps−1 τ=t 2 ητ
Estimation of the Exponential Decay T erm:The term Pt−1 s=t2 ηse− ρ 4 Ps−1 τ=t 2 ητ is bounded by a constant for all a∈ (0, 1]. Let Ss = Ps−1 τ=t 2 ητ . The sum approximates the integral R e− ρ 4 SdS, which converges. Thus, this term is O(1). Combining these estimates, let G(t) denote the margin gap bound. •a <1/2:The numerator is dominated by P η2 s ≈t 1...
-
[9]
The contribu- tion to the sum is: t1,polyX s=0 ηs =O (ξ1/a)1−a =O ξ 1 a −1 .(Fora= 1 : logξ)
Polynomial Stability (t1,poly):From ξt−a ≤ O(1), we have t1,poly = Θ(ξ1/a). The contribu- tion to the sum is: t1,polyX s=0 ηs =O (ξ1/a)1−a =O ξ 1 a −1 .(Fora= 1 : logξ). 48
-
[10]
The contribution to the sum is: t1,expX s=0 ηs = Θ (log(1/β1))a−1 .(Fora= 1 : log( 1 log(1/β1) ))
Exponential Stability ( t1,exp):From βt/2 1 ≤ O(1), we have t1,exp = Θ( 1 log(1/β1) ). The contribution to the sum is: t1,expX s=0 ηs = Θ (log(1/β1))a−1 .(Fora= 1 : log( 1 log(1/β1) ))
-
[11]
The order of t0 is given in Eq
Assumption 2 V alidity (t0):We explicitly invoke Lemma C.15. The order of t0 is given in Eq. (C.15) and (C.16). Define ˜t= ( (1/log(1/β 1)) 1 a + 1 log(1/β1) log( 1 log(1/β1) ),ifa∈(0,1) 1 log(1/β1) log( 1 log(1/β1) ),ifa= 1 The variable ˜trepresents the integral of the learning rate up to this timet 0. Thus: t0X s=0 ηs =O( ˜t1−a).(Fora= 1 : log ˜t). Summ...
-
[12]
Since 1 − 1/a <0, the function y1−1/a logy is bounded on [1 ,∞ ), and hence there exists a constant Ca >0 such that L−1 log(1/L)≤C a L−1/a,∀L∈(0,1]
Absorbing ˜t 1−a.For a∈ (0, 1), recall ˜t = L−1/a + L−1 log(1/L) with L = log(1/β1). Since 1 − 1/a <0, the function y1−1/a logy is bounded on [1 ,∞ ), and hence there exists a constant Ca >0 such that L−1 log(1/L)≤C a L−1/a,∀L∈(0,1]. Therefore, ˜t≤C a L−1/a ⇒ ˜t 1−a ≤C a L−(1−a)/a. UsingL≥1−β 1 andm≥1, we obtain ˜t 1−a ≤C a(1−β 1)−(1−a)/a ≤C a m 1−β 1 1−a...
-
[13]
Then, the accumulated error in epochris bounded by: ∥Er∥F ≤ nX k=1 |ηrn+k−1 −η rn|∥Msign σr(k)∥F ≤n· can (rn)a+1 CM = caCM n2 (rn)a+1
Let CM = √ K. Then, the accumulated error in epochris bounded by: ∥Er∥F ≤ nX k=1 |ηrn+k−1 −η rn|∥Msign σr(k)∥F ≤n· can (rn)a+1 CM = caCM n2 (rn)a+1 . By the triangle inequality and the bound on∥E r∥F , we have R−1X r=0 Er F ≤ R−1X r=0 ∥Er∥F ≤ R−1X r=1 caCM n2 (rn)a+1 = caCM n2 na+1 R−1X r=1 1 ra+1 . Since a∈ (0, 1], we have a + 1 > 1, hence the series P∞ ...
-
[14]
61 Proof
Implicit Bias:The parameter matrix direction converges to the normalized Specific Bias Matrix ¯W: lim t→∞ Wt ∥Wt∥F = ¯W ∥ ¯W∥F . 61 Proof. The proof relies on the invariant geometric update property established in Lemma H.4, which states that for any step t utilizing sample i, the update is strictlyM i. We analyze the convergence of the loss and the direc...
-
[2014]
1 Yiwen Kou, Zixiang Chen, and Quanquan Gu. Implicit bias of gradient descent for two-layer relu and leaky relu networks on nearly-orthogonal data.Advances in Neural Information Processing Systems, 36:30167–30221, 2023. 3 Jingyuan Liu, Jianlin Su, Xingcheng Yao, Zhejun Jiang, Guokun Lai, Yulun Du, Yidao Qin, Weixin Xu, Enzhe Lu, Junjie Yan, et al. Muon is...
Pith/arXiv arXiv 2023
-
[2025]
2, 3 Yuan Cao, Difan Zou, Yuanzhi Li, and Quanquan Gu. The implicit bias of batch normalization in linear models and two-layer linear convolutional neural networks. InThe Thirty Sixth Annual Conference on Learning Theory, pages 5699–5753. PMLR, 2023. 3 David Carlson, Volkan Cevher, and Lawrence Carin. Stochastic spectral descent for restricted boltzmann m...
Pith/arXiv arXiv 2023
This paper was first reviewed by deepseek-v4-flash on August 3, 2026.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.