{"id":"850a0421-4c8c-43a4-9711-7a71da6f6fdb","arxiv_id":"2602.11557","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Mini-batch stochastic steepest descent has a batch-size-dependent margin gap; momentum or variance reduction eliminates it, while batch-size-1 sign/normalized SGD converges to a sample-frequency-biased direction rather than the max-margin solution.","lead":"Many popular optimizers (SignSGD, Muon, Normalized-SGD) are steepest descent under different norms; this paper shows how mini-batch training shifts their implicit bias. Without momentum, small batches lose margin; momentum or variance reduction restore it, while batch-1 updates converge to a sample-averaged direction instead.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Momentum recovery hinges on random-reshuffling epoch cancellation; under with-replacement sampling the effective-margin gap does not vanish as β1→1.","rationale":"The reader's weakest-assumption and my stress-test converge on the Random Reshuffling dependence of the momentum/variance-reduction recovery. This is the most load-bearing concern because the headline practical message—momentum closes the batch-size margin gap while preserving small-batch training—is an artifact of the zero-sum epoch cancellation. The theorems are not internally inconsistent: the assumption is explicit in Section 3.1 and used in Lemma C.12. But the abstract and introduction do not carry this caveat, and with-replacement SGD is common enough that the scope should be stated. A computational comparison of reshuffling vs. with-replacement on the paper's own setting would settle whether the effect is real outside the epochal model. Since this is a scope/presentation issue rather than a demonstrated theorem flaw, the conditional verdict stands: the paper should be accepted only with the scope made explicit and the abstract adjusted.","tokens_in":60072,"tokens_out":27458,"duration_ms":256202,"concrete_test":"Implement N-MSGD (or Signum) with b=20, β1=0.99, ηt=0.5·t^{-1/2} on the Section 5 synthetic dataset under two sampling schemes: standard Random Reshuffling and with-replacement sampling of each mini-batch. After 20k iterations, compare normalized margin and cosine similarity to the full-batch max-margin solution. If with-replacement sampling plateaus below the reshuffling margin, the concern lands. Analytically, re-derive the Lemma C.12 bound for i.i.d. batch errors: if the worst-case accumulated error is O(RG(W)) and independent of (1−β1), then the momentum trade-off in Theorem 4.3 has no analogue outside the epochal reshuffling model.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central positive claim is that momentum enables small-batch convergence to an approximate max-margin solution (Theorem 4.3). This depends on Lemma C.12, which bounds the momentum-accumulated sampling error using the zero-sum property of batch gradient errors within a complete Random Reshuffling epoch. That cancellation yields the (1−β1)m(m²−1)R coefficient: as β1→1, the within-epoch coefficient variation vanishes and the accumulated error shrinks. Without Random Reshuffling—e.g., with-replacement sampling or a non-epochal stream—the zero-sum property fails. The best worst-case accumulated-error bound becomes O(RG(W)), independent of (1−β1), so the effective margin ρ = γ − 2(1−β1)m(m²−1)R would not be restored by taking β1→1. Similarly, the no-momentum Theorem 4.1 relies on the finite-population identity in Lemma C.11, which assumes the mini-batches partition the dataset; under with-replacement sampling the worst-case batch noise need not decrease with b under Assumption 3.2. The theorems are internally consistent under the stated Random Reshuffling assumption, but the abstract and contributions present the results as general mini-batch phenomena, leaving a load-bearing scope gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":60353,"tokens_out":19659,"duration_ms":196741,"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":[{"comment":"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.","section":"§3.1, Lemma C.12, Theorems 4.1/4.3/4.6"},{"comment":"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.","section":"§4.4, Theorem 4.9"}],"minor_comments":[{"comment":"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).","section":"Corollary 4.5 and Appendix E.5, a=1 case"},{"comment":"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.","section":"Definition 4.8"},{"comment":"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.","section":"Lemma C.3 proof"},{"comment":"'paves the way for perform deeper explorations' should read 'paves the way for deeper explorations'.","section":"Abstract"},{"comment":"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.","section":"Section 5"},{"comment":"The reference 'Kingma, 2014' should be 'Kingma and Ba, 2015' (Adam paper).","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The technical machinery appears sound under the Random Reshuffling assumption, and the proofs are impressive in scope. The main issue is that the paper sells the results as applying to mini-batch SGD in general, while the proofs crucially exploit epoch-level cancellation that is specific to Random Reshuffling. This is fixable with a careful revision of the abstract, contribution list, and theorem statements, plus softening the overbroad interpretation of the batch-size-one construction. I would not reject; the core results are likely correct and valuable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is the first paper I know that gives a unified margin-gap account of batch size, momentum, and variance reduction for steepest descent families (SignSGD, Normalized-SGD, Muon), and the proof chain is coherent. The mini-batch effective-margin characterization with dimension-free rates is genuinely new. Theorems 4.3 and 4.6, if they hold up, close a real gap. I spot-checked Lemma C.12, the no-momentum descent lemma, the momentum decomposition, and the variance-reduction bounds, and they are consistent. The external anchoring to Fan et al. 2025 is appropriate; the proxy function framework is borrowed with proofs, not reverse-engineered.\n\nWhere I'd push back: the title and abstract say \"mini-batch stochastic,\" but the momentum and variance-reduction recovery results are proved under random reshuffling, and the zero-sum epoch cancellation in Lemma C.12 is load-bearing. Under with-replacement sampling or non-epochal streams that cancellation fails, and the β1→1 restoration of the margin has no analogue. That does not break the paper—random reshuffling is a legitimate, widely used protocol and it is stated in Section 3.1—but the general phrasing invites overreading, and the authors should say plainly that the momentum trade-off is an RR-specific statement. The no-momentum abstract also says convergence \"only occurs with large batches,\" but the theorem proves a sufficient large-batch condition, not a necessity; that's an overclaim. The batch-1 \"fundamentally different bias\" is proved for one constructed orthogonal, scale-skewed dataset; extrapolating from that to a general claim about small-batch bias is a stretch, and the paper mostly hedges with \"may,\" which is honest but should be sharpened. Experiments have no error bars, no seeds, no code, and the figures are qualitative. Minor, fixable. The momentum analysis also leaves a seam at β1=0, but Remark 4.4 says so explicitly.\n\nWho benefits: any theorist working on implicit bias of Adam/SignSGD/Muon or on why batch size changes generalization will get real value. This deserves a serious referee round. My recommendation: send it out, ask for a scope statement on RR, tone down the abstract, and either add code/seeds or cut the experimental claims.","headline":"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.","tokens_in":60905,"tokens_out":2342,"would_cite":true,"duration_ms":26895,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"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","keywords":["implicit bias","steepest descent","mini-batch stochastic gradient","max-margin","momentum","variance reduction","random reshuffling","multi-class classification"],"falsifier":"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","tokens_in":59867,"feed_emoji":"🎯","tokens_out":12811,"duration_ms":114163,"temperature":0.7,"pith_summary":"This paper asks which solution stochastic mini-batch training actually finds when the optimizer is steepest descent under a norm — the family that includes SignSGD, Normalized-SGD, and Muon. Its central claim is that the implicit bias of these algorithms is governed by an 'effective margin' ρ, which falls strictly below the true margin γ exactly when batches are small and no momentum is used: the run converges to a lower-margin classifier with a quantified gap. Momentum raises ρ back toward γ through a batch–momentum trade-off, variance reduction restores ρ = γ for any batch size, and pure batch-size-one updates can converge to a different limit that averages samples by class frequency rather than by geometric difficulty. If correct, this means batch size and momentum are not merely speed controls — they shape which classifier is selected, and only specific regimes silently reproduce the full-batch max-margin solution.","feed_headline":"Small batches break the max-margin bias; momentum fixes it","feed_subtitle":"For SignSGD- and Muon-style optimizers, batch size and momentum decide which classifier training actually finds.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Momentum restores max-margin bias in mini-batch steepest descent","Without momentum, mini-batch SGD misses max-margin; momentum fixes it","Variance reduction recovers full-batch bias for any batch size","Batch-size-one SGD converges to a sample-averaged bias","Small-batch momentum trade-off: approach max margin, but slower"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Momentum restores max-margin bias in mini-batch steepest descent","Without momentum, mini-batch SGD misses max-margin; momentum fixes it","Variance reduction recovers full-batch bias for any batch size","Batch-size-one SGD converges to a sample-averaged bias","Small-batch momentum trade-off: approach max margin, but slower"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001133,"raw_usage":{"total_tokens":4563,"prompt_tokens":779,"completion_tokens":3784,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":3699}},"tokens_in":523,"tokens_out":3784,"duration_ms":28302,"temperature":1.0,"reasoning_tokens":3699,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T00:07:36.224910+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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","supporting_citations":[],"review_version":1}