acceptodds
Under review as a conference paper at ICLR 2027

The Implicit Bias of Mirror Descent on Multiclass Separable Data: Stochasticity and Momentum

Abstract

The success of deep neural networks has spurred growing interest in understanding optimization dynamics and the solutions selected by different algorithms. In this paper, we study the implicit bias of normalized mirror descent (NMD) for multiclass linear classification with cross entropy loss, elucidating how stochasticity and momentum shape the selected direction. Our key insight is that mini-batch sampling can alter NMD's implicit bias, while momentum counteracts this effect. More specifically, under homogeneous mirror potentials, we show that full-batch NMD converges to the corresponding maximum-margin direction, irrespective of momentum. In contrast, under mini-batch sampling without momentum, NMD can lose sight of the full-batch maximum-margin direction. Crucially, momentum restores the full-batch implicit bias, enabling NMD to recover the same convergence direction. Experiments on linear models and neural networks support our theoretical findings.

Primary area:
learning theory
Keywords:
Implicit Bias, Stochastic Mirror Descent, Mini Batch, Momentum

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.25 over 4 reviews, above 96% of the others.
Reviewer_dte7OpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This work concludes the existing string of work of implicit bias of GD/SGD/MD for two-class/multi-class separable data. The authors show that with and without momentum, the normalized mirror descent and stochastic normalized mirror descent (with minibatch gradients) also converge to the maximum normalized margin direction.

Critical strengths
  • This work essentially combines existing work on either: 1. GD/SGD on multiclass data, and 2. MD/stochastic MD on binary classification. Therefore it finishes this picture.
  • Detailed rate splits (e.g. in Theorem 1) are interesting.
Critical weaknesses
  • Assumptions can be quite strong. For MD-based methods, especially for binary classification, there are no such homogeneity conditions required on the mirror potential. A short discussion on this would aid the paper.
  • The organization makes the paper quite difficult to read, for example random literature review (l. 278, l.395) appearing in the theoretical components. I would much rather have a detailed discussion section
Questions for authors
  • It would be very helpful to have a table comparing the assumptions on the mirror potential Φ\Phi compared to other works in the literature. E.g. is strict inequality ϵ>0\epsilon>0 in Definition 1 necessary, or can it be relaxed to ϵ≥0\epsilon \ge 0?
2 comments
AuthorsOpenReview ↗

Response to Reviewer dte7 (Part 1/2)

Thank you for your thoughtful and critical assessment. Many of your comments will help us produce a more readable and self-contained version of the paper. Below, we address each of your specific concerns in turn.

Strength and generality of assumptions (W1).

  • Homogeneity potentials in prior work.

    We conducted a more extensive literature review and found that prior implicit-bias analyses have assumed homogeneous mirror potentials for MD and NMD on binary linear classification models [1, 2] and MD on softmax attention models [3], as well as asymptotically homogeneous potentials for mirror flow on neural networks [4].

  • Discussions of assumptions.

    We have carefully reevaluated the assumptions in our paper: below, we show how several conditions can be relaxed and clarify why the remaining ones are essential to our analysis. We also added a brief note (line 171) and a fuller discussion (line 502) in the new Discussion section of the revised manuscript.

    • Relaxation of assumptions.

      1. Loss. Theorems 1–4 and Proposition 1 can extend with the same rate orders to the multiclass exponential loss Lexp(W)=1n∑i=1n∑l≠yie−mil(W)\mathcal{L}_{\mathrm{exp}}(W) = \frac{1}{n}\sum_{i=1}^n\sum_{l\ne y_i}\mathrm{e}^{-m_{il}(W)} and PairLogLoss Lpll(W)=1n∑i=1n∑l≠yilog⁡(1+e−mil(W))\mathcal{L}_{\mathrm{pll}}(W) = \frac{1}{n}\sum_{i=1}^n\sum_{l\ne y_i}\log(1+\mathrm{e}^{-m_{il}(W)}), where mil(W):=(eyi−el)⊤Wxim_{il}(W):=(e_{y_i}-e_l)^\top Wx_i. Specifically, in Appendix E we prove the counterparts of Lemmas B.1–B.3 and B.10 for both losses (Lemmas E.1–E.8), which Theorems 1, 3, and 4 follow by the same proof steps as for cross-entropy loss in Appendices C and D. Using the same datasets S1\mathcal{S}_1 and S2\mathcal{S}_2, Theorem 2 and Proposition 1 likewise follow by the same proof steps.

      2. Step size. Under the remaining assumptions of Theorems 1, 3, and 4, their direction, margin, and loss convergence conclusions hold for any deterministic positive steps with ηt→0\eta_t\to0 and ST:=∑t<Tηt→∞S_T := \sum_{t<T}\eta_t \to \infty. Specifically, St→∞S_t\to\infty gives ∥Wt∥ψL−1≍1+St\lVert W_t\rVert_\psi^{L-1}\asymp 1+S_t (Lemma B.11), while ηt→0\eta_t\to 0 (hence sup⁡tηt<∞\sup_t\eta_t<\infty) gives ∥Wt+1−Wt∥ψ→0\lVert W_{t+1}-W_t\rVert_\psi\to 0 (Lemma B.12), yielding an o(ST)o(S_T) cumulative mirror-step remainder in Theorem B.1 and, via the momentum recursion and stability bounds in Lemma B.2, a vanishing relative lag ∥Mt−M~t∥ψ,∗/G(Wt)→0\lVert M_t-\widetilde M_t\rVert_{\psi,*}/\mathcal G(W_t)\to 0 so that covered windows contribute o(ST)o(S_T) directional error for each fixed window length KK (Lemma D.2). Dividing by ∥WT∥ψL−1≍1+ST\lVert W_T\rVert_\psi^{L-1}\asymp 1+S_T then yields vanishing Bregman error under full-batch updates and reshuffling (Lemma D.3), whereas under independent sampling, grouping disjoint windows by t mod Kt\bmod K and using ∑tηt2/(1+St+1)2<∞\sum_t\eta_t^2/(1+S_{t+1})^2<\infty as in Lemma C.2(i) shows that the ηt\eta_t-weighted uncovered-window fraction in Lemma D.4 converges almost surely to πK\pi_K with a KK-independent prefactor and vanishes as K→∞K\to\infty. In our work, we adopt the power-law schedule ηt=η0t−a\eta_t = \eta_0 t^{-a} in Assumption 3 simply to obtain explicit rates in TT.

    • Necessity of LL-homogeneity.

      In our convergence proofs, LL-homogeneity is essential in three ways. (i) It induces the margin norm ∥W∥ψ=ψ(W)1/L\Vert{}W\Vert{}_\psi=\psi(W)^{1/L} and the dual norm used to normalize gradients and momentum. (ii) For Θt=∇ψ(Wt)\Theta_t=\nabla\psi(W_t), it yields ∥Wt∥ψ=L−1/(L−1)∥Θt∥ψ,∗1/(L−1)\Vert{}W_t\Vert{}_\psi=L^{-1/(L-1)}\Vert{}\Theta_t\Vert{}_{\psi,*}^{1/(L-1)} (Lemma B.6), translating dual-norm growth into primal-norm growth. (iii) It determines the scaling in the dual Hessian bound (Lemma B.8), which controls ∥Wt+1−Wt∥ψ\Vert{}W_{t+1}-W_t\Vert{}_\psi and hence the lag error from past gradients in MtM_t (Lemma D.1).

Manuscript organization (W2)

Thank you for this helpful suggestion. In the revised manuscript, we have added a dedicated Discussion section (line 480) and moved the literature comparisons originally at lines 278 and 395 into it.

AuthorsOpenReview ↗

Response to Reviewer dte7 (Part 2/2)

Comparison of mirror potentials and relaxing ϵ>0\epsilon > 0 to ϵ≥0\epsilon \geq 0 (Q1)

  • Comparison with mirror potentials in prior work.

    Thank you for this helpful suggestion. Below, we provide a table comparing the mirror-potential assumptions on ψ\psi in implicit-bias analyses for classification, which we have also added (along with a detailed discussion) to Appendix F of the revised manuscript.

    Table 1 Comparisons of mirror potential assumptions in implicit-bias analyses for classification.

    WorkOptimizer a^{\mathrm{a}}Setting b^{\mathrm{b}}Homogeneity c^{\mathrm{c}}Other cond. on ψ\psi d^{\mathrm{d}}
    [5]Full-batch MDBinary linear×\timesStrong conv., smooth
    [6]Mirror flowBinary linear×\timesC2C^2, PD ∇2ψ\nabla^2\psi
    [4]Mirror flowBinary hom. net✓\checkmark (asymp.)Strict conv., loc. Lip. ∇2ψ\nabla^2\psi
    [1]Full-batch MDBinary linear✓\checkmarkψ(w)=∥w∥pp/p\psi(w)=\lVert w\rVert_p^p/p
    [3]Full-batch MDBinary attention✓\checkmarkψ(W)=1p∑i,j∣Wij∣p\psi(W)=\frac{1}{p}\sum_{i,j}\lvert W_{ij}\rvert^p
    [2]Full-batch MD, NMDBinary linear✓\checkmarkC2C^2, PD ∇2ψ\nabla^2\psi
    OursFull/mini NMD (±\pm mom.)Multiclass linear✓\checkmarkSmoothed Φ\Phi, C2C^2, PD ∇2ψ\nabla^2\psi

    a^{\mathrm{a}} MD and NMD denote mirror descent and normalized mirror descent. Full/mini denotes full-batch or mini-batch updates, and ±\pm mom. denotes updates with or without momentum.

    b^{\mathrm{b}} Hom. net denotes a homogeneous neural network. Binary attention denotes binary classification with a single-head, one-layer softmax attention model and a linear prediction head.

    c^{\mathrm{c}} A ×\times indicates that the stated assumptions allow nonhomogeneous potentials. A ✓\checkmark indicates absolute homogeneity of ψ\psi, and ✓\checkmark (asymp.) indicates asymptotic homogeneity.

    d^{\mathrm{d}} PD denotes positive definite, conv. denotes convexity, and loc. Lip. denotes locally Lipschitz. Here Φ\Phi is the base potential.

  • Relaxing ϵ>0\epsilon > 0 to ϵ≥0\epsilon \geq 0.

    We can relax ϵ>0\epsilon>0 to allow ϵ≥0\epsilon\geq 0 by additionally assuming ∇2Φ(W)≻0\nabla^2\Phi(W)\succ 0 for every W≠0W\ne 0. Specifically, when ϵ=0\epsilon=0, ψ=Φ\psi=\Phi inherits LL-homogeneity directly, while continuity of ∇2Φ\nabla^2\Phi on the compact Frobenius unit sphere implies mΦ:=min⁡∥U∥F=1λmin⁡(∇2Φ(U))>0m_\Phi:=\min_{\Vert{}U\Vert{}_F=1}\lambda_{\min}(\nabla^2\Phi(U))>0, so we have ∇2ψ(W)⪰mΦ∥W∥FL−2I\nabla^2\psi(W)\succeq m_\Phi\Vert{}W\Vert{}_F^{L-2}I for all W≠0W\ne 0. This lower bound yields ψ∗∈C2(Rk×d∖0)\psi^*\in C^2(\mathbb{R}^{k\times d}\setminus\\{0\\}) (Lemma B.7), the ∥Θ∥ψ,∗−(L−2)/(L−1)\Vert{}\Theta\Vert{}_{\psi,*}^{-(L-2)/(L-1)} bound on ∇2ψ∗\nabla^2\psi^* (Lemma B.8), and the one-step Bregman bound (Lemma B.12). Therefore, Theorems 1, 3, and 4 all continue to hold with the same rate orders up to constants.

References

  • [1] Sun et al. (2022). Mirror Descent Maximizes Generalized Margin and Can Be Implemented Efficiently. NeurIPS.

  • [2] Sun et al. (2023). A Unified Approach to Controlling Implicit Regularization via Mirror Descent. JMLR.

  • [3] Julistiono et al. (2026). Optimizing Attention with Mirror Descent: Generalized Max-Margin Token Selection. JMLR.

  • [4] Jacobs and Montúfar (2026). Implicit Bias of Mirror Flow in Homogeneous Neural Networks: Sparse and Dense Feature Learning. arXiv:2605.19458.

  • [5] Li et al. (2021). Implicit Regularization of Bregman Proximal Point Algorithm and Mirror Descent on Separable Data. arXiv:2108.06808.

  • [6] Pesme et al. (2024). Implicit Bias of Mirror Flow on Separable Data. NeurIPS.

Reviewer_QDPVOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper builds on the classical implicit-bias results, including the work of Soudry et. al. 2018, which shows that, for logistic regression under perfectly linearly separate binary datasets, the gradient descend converge to the direction to the max-margin solution, while the weight norm diverge. (It's actually one of my favorite papers in that year!).

This paper studies the normalized mirror descent for multi class linear classification with cross entropy loss. It studies them from the three different perspectives, the full gradient updates, mini-batch sampling and momentum effect the direction selected by the optimization algorithm.

Critical strengths

The author extend the classic binary case work into multi class separable linear classification problem with cross entropy loss. It show how under mirror descend, mini-batch sampling and momentum affect the selected direction. The authors show shot under the stated assumption, full-batch normalized mirror descend converge to the corresponding max-margin direction, while mini-batch sampling can disrupt this converges and momentum restore it.

Overall, I think it's a good paper, that has added one interesting element to the implicit-biaseness line of work.

Critical weaknesses

I guess this is just like how one may feel about Soudry et. al. 2018: the weakness can be the restricted assumptions used: i.e., the result rely on the separable multi-class linear classification, cross-entropy loss and the specified mirror-potential class. But then again, any theoretical paper needs to make some assumptions.

I felt including some more experiments may make the paper stronger. For example, Figure 1 shows mini-batch nomlaised mirror descent with momentum under entry wise l4l_4 and schatten-4 potential. It would be too do show the corresponding mini-batch cures without momentum.

Questions for authors

n/a

4 comments
AuthorsOpenReview ↗

Response to Reviewer QDPV (Part 1/2)

Thank you for your thoughtful and critical assessment. Many of your comments will help us produce a more readable and self-contained version of the paper. Below, we address each of your specific concerns in turn.

Relaxation and extension of assumptions (W1).

Thank you for this thoughtful comment. Several of our assumptions can be directly weakened or broadened while preserving our guarantees, as detailed below:

  • Mirror potential (removing the smoothing term). Whenever the base potential satisfies ∇2Φ(W)≻0\nabla^2\Phi(W)\succ 0 for every W≠0W\ne 0, we can drop this smoothing term by relaxing ϵ>0\epsilon>0 to ϵ=0\epsilon=0 (so ψ=Φ\psi=\Phi). Specifically, ψ=Φ\psi=\Phi inherits LL-homogeneity directly, while continuity of ∇2Φ\nabla^2\Phi on the compact Frobenius unit sphere gives mΦ:=min⁡∥U∥F=1λmin⁡(∇2Φ(U))>0m_\Phi:=\min_{\Vert{}U\Vert{}_F=1}\lambda_{\min}(\nabla^2\Phi(U))>0, yielding ∇2ψ(W)⪰mΦ∥W∥FL−2I\nabla^2\psi(W)\succeq m_\Phi\Vert{}W\Vert{}_F^{L-2}I for all W≠0W\ne 0. This lower bound preserves ψ∗∈C2(Rk×d∖0)\psi^*\in C^2(\mathbb{R}^{k\times d}\setminus\\{0\\}) (Lemma B.7), the ∥Θ∥ψ,∗−(L−2)/(L−1)\Vert{}\Theta\Vert{}_{\psi,*}^{-(L-2)/(L-1)} bound on ∇2ψ∗\nabla^2\psi^* (Lemma B.8), and the one-step Bregman bound (Lemma B.12), so Theorems 1, 3, and 4 all continue to hold with the same rate orders up to constants.

  • Loss functions (beyond cross-entropy). Our theoretical guarantees are not limited to cross-entropy loss. All conclusions and rate orders in Theorems 1–4 and Proposition 1 carry over to the multiclass exponential loss and PairLogLoss [1, 2]. Since the proofs in Appendices C and D rely on the loss function solely through gradient alignment, batch stability, ray comparison, and momentum alignment (Lemmas B.1–B.3 and B.10), establishing the corresponding estimates in the new Appendix E (Lemmas E.1–E.8) directly yields Theorems 1, 3, and 4, and the counterexamples in Theorem 2 and Proposition 1 likewise hold on the same datasets S1\mathcal{S}_1 and S2\mathcal{S}_2.

  • Step size (general diminishing schedules). While Assumption 3 adopts the power-law schedule ηt=η0t−a\eta_t = \eta_0 t^{-a} to obtain explicit rates in TT, all asymptotic directional, margin, and loss convergence guarantees in Theorems 1, 3, and 4 hold for any deterministic positive step sizes satisfying ηt→0\eta_t\to 0 and ∑tηt=∞\sum_t \eta_t = \infty. These two limits alone ensure diverging iterate norms and vanishing single-step increments, which suffices to control the mirror-step remainders, momentum lag, and mini-batch sampling errors so that the Bregman error vanishes.

  • Data assumption. Input boundedness holds automatically on any finite dataset with B=max⁡i∥xi∥1B=\max_i\lVert x_i\rVert_1. Relaxing linear separability is left for future work: for nonseparable binary data, Ji and Telgarsky [3] characterize gradient descent through a maximal separable subset and an offset on the remaining data, motivating an analogous target for multiclass NMD.

AuthorsOpenReview ↗

Response to Reviewer QDPV (Part 2/2)

Mini-batch NMD without momentum (W2).

Thank you for this constructive suggestion. Below, we present results for mini-batch NMD without momentum (β=0\beta = 0). More detailed setups, full convergence trajectories, and complete tables are provided in Appendix A of the revised manuscript.

On the five clustered datasets from Figure 1 (n=500n = 500, k=10k = 10, d=25d = 25), we run NMD from W0=0W_0 = 0 with ηt=0.1/max⁡1,t\eta_t = 0.1/\sqrt{\max\\{1, t\\}} for 3×1063\times 10^6 updates under independent sampling with replacement (IID) and random reshuffling (RR). We use the smoothed potentials ψ(W)=12(N(W)2+0.1∣W∣F2)\psi(W) = \frac{1}{2}(N(W)^2 + 0.1\\|W\\|_F^2) (L=2L = 2, ϵ=0.1\epsilon = 0.1), where N(W)N(W) is the entrywise ℓ4\ell_4 or Schatten-4 norm. Tables 1 and 2 below report the median relative margin gaps (%) across batch sizes after 3×1063\times 10^6 updates under IID and RR.

Table 1: Relative margin gap (%) on the clustered data under IID (T=3×106T = 3\times 10^6).

Potential (ss)β=0\beta = 0β=0.1\beta = 0.1β=0.5\beta = 0.5β=0.9\beta = 0.9
Entrywise ℓ4\ell_4 (5)10.9198.9345.8612.002
Entrywise ℓ4\ell_4 (10)10.0967.1103.7201.497
Entrywise ℓ4\ell_4 (25)8.1834.3742.2691.220
Entrywise ℓ4\ell_4 (50)4.3272.7271.6431.101
Schatten-4 (5)12.42510.7597.6253.108
Schatten-4 (10)11.4149.0915.6012.347
Schatten-4 (25)9.0796.1763.4661.884
Schatten-4 (50)6.0354.2732.5431.739

Table 2: Relative margin gap (%) on the clustered data under RR (T=3×106T = 3\times 10^6).

Potential (ss)β=0\beta = 0β=0.1\beta = 0.1β=0.5\beta = 0.5β=0.9\beta = 0.9
Entrywise ℓ4\ell_4 (5)10.9158.8885.6041.815
Entrywise ℓ4\ell_4 (10)10.0677.0203.5321.371
Entrywise ℓ4\ell_4 (25)8.1034.1572.0951.086
Entrywise ℓ4\ell_4 (50)4.0152.6091.5001.004
Schatten-4 (5)12.41410.7197.4692.831
Schatten-4 (10)11.3668.9535.3602.111
Schatten-4 (25)8.9855.9993.2391.720
Schatten-4 (50)5.7994.0492.3171.613

Within the fixed 3×1063\times 10^6 budget, the relative margin gap decreases monotonically across β∈0,0.1,0.5,0.9\beta \in \\{0, 0.1, 0.5, 0.9\\} for every batch size, and decreases with ss at every β\beta.

References

  • [1] C. Fan, M. Schmidt, and C. Thrampoulidis. Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data. NeurIPS, 2025.

  • [2] H. Ravi, C. Scott, D. Soudry, and Y. Wang. The Implicit Bias of Gradient Descent on Separable Multiclass Data. NeurIPS, 2024.

  • [3] Z. Ji and M. Telgarsky. The implicit bias of gradient descent on nonseparable data. COLT, 2019.

Thank you for a thorough response. It has sufficiently addressed my concerns. I apologies for my late response. I would maintain my score of 3 (weak accept) in any case.

For W2, the table shows that momentum has reduce the relative margin gap. One outstanding question is whether the no-momentum trajectories continue to decrease at later iterations or appear to level off. I guess plot the with and without momentum trajectories together could show the difference clearer.

Dear Reviewer QDPV,

Thank you for your positive recommendation and continued engagement. We are glad to hear that our responses have resolved your main concerns. We also appreciate your helpful suggestion to plot the trajectories with and without momentum together. In the final manuscript, we will combine them into a single figure to allow for a clearer direct comparison, specifically illustrating whether the trajectories without momentum continue to decrease or plateau in later iterations.

We sincerely appreciate your constructive feedback and strong support for our work.

Reviewer_qZCUOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the implicit bias of normalized mirror descent for separable multiclass linear classification. It shows that mini-batch sampling can disrupt maximum-margin convergence, while momentum restores it under both independent sampling and random reshuffling. Theoretical convergence guarantees and rates are supported by synthetic experiments, with additional empirical observations on a small MNIST neural network.

Critical strengths
  1. Clear characterization of momentum’s role in implicit bias. The paper proves that fixed positive momentum restores maximum-margin directional convergence when mini-batch NMD can fail, under both independent sampling and random reshuffling. This gives a substantive theoretical explanation of how momentum affects solution selection.

  2. Complementary counterexamples and guarantees. The constructions distinguish vanishing loss with a suboptimal limiting direction from outright loss divergence. Together with the recovery theorem and supporting synthetic experiments, they clearly establish the consequences of omitting momentum.

Critical weaknesses
  1. Limited evidence beyond the theoretical setting. The guarantees concern separable linear classification, while the neural-network validation uses only a small MNIST subset and measures training margins. This leaves the relevance to broader neural-network training and generalization insufficiently established.

  2. Unclear finite-time significance of momentum recovery. The theorem covers any fixed positive momentum, but the experiments primarily compare zero momentum with β=0.9\beta = 0.9. A sensitivity study over momentum and batch size would help establish whether the asymptotic recovery occurs within practical training budgets, particularly for small positive momentum.

Questions for authors
  1. How do the constants in Theorem 4 depend on β\beta and batch size, particularly as β\beta approaches zero? Can the bounds indicate when maximum-margin recovery becomes observable?

  2. Do intermediate or small positive momentum values reproduce the recovery observed with β=0.9\beta = 0.9 within comparable training budgets? Such evidence would materially strengthen the finite-time significance of the main result.

6 comments
AuthorsOpenReview ↗

Response to Reviewer qZCU (Part 1/4)

Thank you for your thoughtful and critical assessment. Many of your comments will help us produce a more readable and self-contained version of the paper. Below, we address each of your specific concerns in turn.

Broader evaluation (W1).

Thank you for raising this important point. Below, we report expanded neural network results across more benchmarks and architecture, non-Euclidean mirror potentials, potential cross-evaluation, and both training and test classification errors. More detailed setups can be found in Appendix A of the revised manuscript.

(1) More datasets, architectures, and mirror potentials.

Beyond the n=1,000n = 1{,}000 MNIST subset, we scaled our evaluation in two directions:

  • Two-layer ReLU network on full MNIST: Trained on 50,000 images and evaluated on the 10,000-image test set (T=50,000T = 50{,}000) across s∈20,100,500s \in \\{20, 100, 500\\}, IID and RR, and quadratic Euclidean, smoothed entrywise ℓ4\ell_4, and Schatten-4 potentials.
  • ResNet-18 on full CIFAR-10: Trained on all 50,000 training images (T=25,000T = 25{,}000) and evaluated on the official test set across s∈50,100,500s \in \\{50, 100, 500\\} under Euclidean (L∈2,4,6L \in \\{2, 4, 6\\}) and grouped ℓ4\ell_4 (L=4L = 4) potentials.

(2) Margin recovery and cross-evaluation of mirror potentials.

  • Margin recovery with momentum. Table 1 and Table 2 report the final normalized minimum training margins (×103\times 10^3) under the quadratic Euclidean potential on full MNIST and CIFAR-10, respectively.

    Table 1: Final normalized minimum training margins (×103\times 10^3) for the two-layer ReLU network on MNIST.

    Samplingβ\betas=20s = 20s=100s = 100s=500s = 500
    IID0−49.496-49.496−33.496-33.496−16.515-16.515
    IID0.9−19.290-19.2901.2341.2344.8544.854
    RR0−53.579-53.579−32.138-32.138−16.809-16.809
    RR0.9−21.210-21.2102.2702.2705.1975.197

    Table 2: Final normalized minimum training margins (×103\times 10^3) for ResNet-18 on CIFAR-10.

    Samplingβ\betas=50s = 50s=100s = 100s=500s = 500
    IID0−0.807±0.168-0.807 \pm 0.168−0.311±0.066-0.311 \pm 0.0660.010±0.0070.010 \pm 0.007
    IID0.9−0.163±0.034-0.163 \pm 0.034−0.061±0.028-0.061 \pm 0.0280.469±0.0540.469 \pm 0.054
    RR0−0.720±0.111-0.720 \pm 0.111−0.273±0.093-0.273 \pm 0.0930.008±0.0060.008 \pm 0.006
    RR0.9−0.145±0.012-0.145 \pm 0.012−0.048±0.031-0.048 \pm 0.0310.616±0.1050.616 \pm 0.105

    Under both IID and RR, raising β\beta from 0 to 0.9 increases the normalized minimum margin across every batch size on both benchmarks. In particular, on MNIST at the two larger batch sizes, momentum turns the margin positive on every seed, whereas all β=0\beta = 0 runs remain negative. It is consistent with the theoretical analysis for linear models.

  • Cross-evaluation of mirror potentials. To test whether nonlinear networks exhibit potential-dependent margin selection analogous to our linear theory, we follow Neyshabur et al. [1] on the MNIST set (s=100s = 100, β=0.5\beta = 0.5) and cross-evaluate the fifth-percentile training logit margin normalized by each degree-two evaluation potential, Qij=quantile⁡0.05mθT(i)(x,y)/ψj(θT(i))Q_{ij} = \operatorname{quantile}_{0.05}\\{m_{\theta_T^{(i)}}(x,y)\\} / \psi_j(\theta_T^{(i)}). Table 3 reports the median scores (×103\times 10^3) over five paired seeds.

    Table 3: Median fifth-percentile normalized margins (×103\times 10^3) on MNIST.

    SamplingTrained potentialEval: EuclideanEval: Schatten-4
    IIDEuclidean quadratic4.7430.43
    IIDSchatten-44.5231.85
    RREuclidean quadratic4.7230.33
    RRSchatten-44.6532.84

    Under both samplers, each model achieves a larger normalized margin under the corresponding potential used to train it (Qii>QkiQ_{ii} > Q_{ki}), matching the qualitative margin-selection behavior predicted by our linear theory.

AuthorsOpenReview ↗

Response to Reviewer qZCU (Part 2/4)

(3) Empirical observations on training and test errors and generalization.

Our theoretical guarantees focus on implicit bias, characterizing the limiting solution direction selected by NMD rather than directly bounding training classification error or test generalization. To observe how momentum and mirror geometry affect optimization and generalization empirically, we evaluate both training and test classification errors (%). Table 4 reports the three seed mean training / test errors (%) for ResNet-18 on CIFAR-10 under RR across four potentials and three batch sizes. Due to space constraints, more experiments can be found in the Appendix A.

Table 4: Mean training / test errors (%) for ResNet-18 on CIFAR-10 under RR.

Potential (ss)β=0\beta = 0β=0.1\beta = 0.1β=0.5\beta = 0.5β=0.9\beta = 0.9
Euclidean L=2L=2 (50)1.379 / 8.291.191 / 7.900.737 / 7.350.796 / 7.91
Euclidean L=2L=2 (100)0.061 / 7.200.027 / 7.090.017 / 6.780.016 / 6.66
Euclidean L=2L=2 (500)<0.001 / 5.74<0.001 / 5.85<0.001 / 5.75<0.001 / 5.83
Euclidean L=4L=4 (50)1.355 / 8.121.169 / 7.980.716 / 7.450.658 / 7.54
Euclidean L=4L=4 (100)0.054 / 7.340.037 / 7.180.014 / 6.720.011 / 6.75
Euclidean L=4L=4 (500)<0.001 / 5.67<0.001 / 5.94<0.001 / 5.84<0.001 / 5.80
Euclidean L=6L=6 (50)1.310 / 8.001.107 / 7.740.732 / 7.400.653 / 7.92
Euclidean L=6L=6 (100)0.051 / 7.510.040 / 7.150.015 / 6.850.005 / 6.58
Euclidean L=6L=6 (500)<0.001 / 5.64<0.001 / 5.84<0.001 / 5.63<0.001 / 5.65
Grouped L=4L=4 (50)1.781 / 8.351.525 / 8.270.823 / 7.810.656 / 7.87
Grouped L=4L=4 (100)0.117 / 7.620.080 / 7.620.026 / 7.040.019 / 6.70
Grouped L=4L=4 (500)<0.001 / 5.89<0.001 / 5.76<0.001 / 5.90<0.001 / 5.74
  • Momentum improves small-batch errors. In Table 4, positive momentum lowers both training and test error at smaller batch sizes across all tested potentials, whereas at the largest batch size all runs interpolate with comparable test errors.
  • Limitations of theoretical explanations for generalization. Theoretically, whether a larger ψ\psi-margin translates into lower test error depends on how the chosen geometry aligns with the underlying class-signal structure [2], which goes beyond our scope. Extending rigorous implicit-bias guarantees for stochastic NMD with momentum to nonlinear networks [3, 4] and analyzing its generalization implications remain important directions for future work.
AuthorsOpenReview ↗

Response to Reviewer qZCU (Part 3/4)

Sensitivity to β\beta and batch size (W2 & Q2).

Thank you for this constructive suggestion. Intermediate (β∈0.1,0.5\beta \in \\{0.1, 0.5\\}) and even very small (β=0.01\beta = 0.01) positive momentum values consistently improve over β=0\beta = 0 and progressively reproduce the maximum-margin recovery within the same training budgets. Below, we present systematic sensitivity analyses across β∈0,0.01,0.1,0.5,0.9\beta \in \\{0, 0.01, 0.1, 0.5, 0.9\\} and batch sizes ss on all three separable linear settings. Full iteration trajectories and complete tables are provided in Appendix A of the revised manuscript.

(1) Clustered synthetic data.

On the five clustered datasets from Figure 1 (n=500n = 500, k=10k = 10, d=25d = 25), we run NMD from W0=0W_0 = 0 with ηt=0.1/max⁡1,t\eta_t = 0.1/\sqrt{\max\\{1, t\\}} for T=3×106T = 3\times 10^6 updates under independent sampling with replacement (IID) and random reshuffling (RR), using smoothed entrywise ℓ4\ell_4 and Schatten-4 potentials (L=2L = 2, ϵ=0.1\epsilon = 0.1). Table 3 below reports the terminal median IID / RR relative margin gaps (%) across all tested momentum values and batch sizes.

Table 3: IID / RR relative margin gaps (%) on clustered synthetic data (T=3×106T = 3\times 10^6).

Smoothed entrywise ℓ4\ell_4:

Momentum β\betas=5s = 5s=10s = 10s=25s = 25s=50s = 50
0010.919 / 10.91510.096 / 10.0678.183 / 8.1034.327 / 4.015
0.010.0110.051 / 10.0268.683 / 8.5836.421 / 6.2713.812 / 3.560
0.10.18.934 / 8.8887.110 / 7.0204.374 / 4.1572.727 / 2.609
0.50.55.861 / 5.6043.720 / 3.5322.269 / 2.0951.643 / 1.500
0.90.92.002 / 1.8151.497 / 1.3711.220 / 1.0861.101 / 1.004

Smoothed Schatten-4:

Momentum β\betas=5s = 5s=10s = 10s=25s = 25s=50s = 50
0012.425 / 12.41411.414 / 11.3669.079 / 8.9856.035 / 5.799
0.010.0111.669 / 11.64310.583 / 10.5158.003 / 7.8905.642 / 5.420
0.10.110.759 / 10.7199.091 / 8.9536.176 / 5.9994.273 / 4.049
0.50.57.625 / 7.4695.601 / 5.3603.466 / 3.2392.543 / 2.317
0.90.93.108 / 2.8312.347 / 2.1111.884 / 1.7201.739 / 1.613

Within the fixed 3×1063\times 10^6 budget, the relative margin gap decreases monotonically across β∈0,0.01,0.1,0.5,0.9\beta \in \\{0, 0.01, 0.1, 0.5, 0.9\\} for every batch size, and decreases with ss at every β\beta.

(2) Imbalanced synthetic data.

On the imbalanced three-class dataset from Figure 2 (n=32n = 32, k=d=3k = d = 3) with ψ(W)=∥W∥F2\psi(W) = \lVert W\rVert_F^2 under the same initialization and step-size schedule for T=106T = 10^6 updates, Table 4 below reports median IID / RR relative margin gaps (%) over ten runs.

Table 4: IID / RR relative margin gaps (%) on imbalanced synthetic data (T=106T = 10^6).

Momentum β\betas=1s = 1s=4s = 4s=8s = 8s=16s = 16
00390.24 / 390.19357.97 / 355.00279.10 / 250.19111.16 / 5.54
0.010.01322.44 / 312.36131.58 / 79.7745.55 / 26.8018.73 / 5.15
0.10.1253.67 / 225.0146.07 / 31.6018.60 / 11.236.95 / 3.02
0.50.559.81 / 41.029.57 / 5.563.76 / 1.981.81 / 1.39
0.90.94.94 / 2.701.42 / 1.371.39 / 1.331.36 / 1.32
  • Small momentum (β=0.01\beta = 0.01) already flips the terminal margin from negative to positive at s≥4s \ge 4 under RR and at s≥8s \ge 8 under IID.
  • Intermediate momentum restores positive margins for s≥4s \ge 4 under IID and RR at β=0.1\beta = 0.1, and across all batch sizes at β=0.5\beta = 0.5.

(3) Orthogonal synthetic data.

On the orthogonal three-class dataset from Figure 2 (n=300n = 300, k=d=3k = d = 3) under the same potential, and 10610^6-update budget, Table 5 below reports representative IID / RR relative margin gaps (%).

Table 5: ID / RR relative margin gaps (%) on orthogonal synthetic data (T=106T = 10^6).

Momentum β\betas=1s = 1s=2s = 2s=4s = 4s=20s = 20
0033.97 / 33.906.23 / 6.192.91 / 2.911.01 / 0.99
0.010.013.09 / 3.072.27 / 2.261.69 / 1.680.88 / 0.86
0.10.12.29 / 2.281.72 / 1.711.29 / 1.280.72 / 0.70
0.50.51.41 / 1.391.08 / 1.060.84 / 0.820.53 / 0.51
0.90.90.72 / 0.700.60 / 0.560.50 / 0.480.40 / 0.38

We observe that the relative margin gap decreases monotonically across β∈0,0.01,0.1,0.5,0.9\beta \in \\{0, 0.01, 0.1, 0.5, 0.9\\} for every batch size, and decreases with ss at every β\beta.

Reviewer_MhRfOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper describes the implicit bias properties of normalized mirror descent, with a specific mirror map that maintains positive homogeneity, and thus replicate norm properties (with degree L). It shows margin maximization is approachable deterministically, but with stochasticity (sampling with replacement or random reshuffling) there is a counterexample that shows divergence and no max margin achieved. It shows that momentum can paper over this issue, and re-achieve the maximum margin.

Critical strengths

As far as I am aware, the paper covers a genuinely new space with the mirror descent extensions and momentum fixes. I also found no substantive issues in the mathematical analysis / proofs.

Critical weaknesses
  • The appendix proofs are very dense. For example, in the line above (B.12), it is not clear why W^\hat W and WhmW_hm are related in this way. In line 931: its finite maximum over what? I guess the compact dual unit sphere?

  • Actually the claims on B.12 is never fully proven. AI was able to prove it in two steps so I'm not concerned about correctness, but it makes the proof harder to read than is reasonable. Things like this pepper the appendix.

  • Actually, (C.9) shows that γ(WT)<0\gamma(W_T) < 0, not just bounded away from the margin maximizer. Not a weakness, but the counterexample is underselling.

  • Line 1288: Authors may want to double check this constant in ∥Z∥ψ,∗=∥Z∥F/ν\|Z\|_{\psi,*} = \|Z\|_F/\nu. Seems potentially wrong, though not a critical error.

  • (maybe minor) the time-varying βt\beta_t in Alg b.1 seems not that necessary, unless I'm missing something? (e.g. why not just static β\beta?)

  • (maybe major) See questions in next box on dependency on β\beta. A discussion on the reliance of the rates on β\beta may be needed, for the momentum analysis to be fully transparent.

Questions for authors
  • What are the applications of this class of mirror maps? Are there specific functions / DNNs for example, that specifically benefit from this class? I do not know of a practical method that is often used that is not using either Frobenius norm mirror map, or negative entropy. Can the authors discuss where they see this analysis going in terms of practical usage (in analyzing existing methods or existing model architectures, for example)? And is L>2L > 2 a reasonable regime?

  • What restrictions would you have to have on ψ\psi such that you could have ϵ=0\epsilon = 0? Is that possible? That is, can λmin⁡(∇2ψ(W))\lambda_{\min}(\nabla^2 \psi(W)) be lower bounded even without the extra ϵ∥W∥F2\epsilon \|W\|_F^2 term?

  • What is the dependence of beta in Thm 4 (or in any of the momentum results)?

  • It seems like Prop C.2 is saying something deeper about the minibatch normalization problem for multiclass, that may not apply for binary logistic regression. Is there something fundamentally more challenging about the multiclass case that this example is trying to illustrate, or is this just a handy counterexample that could also be applied to the binary case?

  • Can you elaborate, for each result in appendix D, on the relance on β\beta? If indeed the constants are very big, they should not be hidden in the main statement of each result.

6 comments
AuthorsOpenReview ↗

Response to Reviewer MhRf (Part 1/4)

Thank you for your thoughtful and critical assessment. Many of your comments will help us produce a more readable and self-contained version of the paper. Below, we address each of your specific concerns in turn.

Clearer and more detailed appendix proofs (W1&W2).

Thank you for your feedback. In the revised manuscript, we have added intermediate derivations and refined the exposition in the appendix, which we hope makes the proofs easier to follow.

  • Full proof of the equivalence between W^\widehat{W} and WhmW_{\mathrm{hm}} (originally above (B.12)). We proved the equivalence between W^\widehat{W} and WhmW_{\mathrm{hm}} in Lemma B.9. Specifically, Assumption 1 gives γ^>0\widehat{\gamma} > 0, and the positive homogeneity of the margin objective and of the norm ∥⋅∥ψ\lVert\cdot\rVert_\psi implies that every maximizer UU of (4) satisfies ∥U∥ψ=1\lVert U\rVert_\psi = 1. Normalizing any feasible WW of (B.21) then gives ∥W∥ψ≥1/γ^\lVert W\rVert_\psi \ge 1/\widehat{\gamma}, which is attained by the feasible point U/γ^U/\widehat{\gamma}. Finally, since minimizing ∥W∥ψ\lVert W\rVert_\psi in (B.21) is equivalent to minimizing ψ(W)=∥W∥ψL\psi(W) = \lVert W\rVert_\psi^L and ψ\psi is strictly convex (Lemma B.5), both WhmW_{\mathrm{hm}} and W^\widehat{W} are unique, with W^=γ^Whm\widehat{W} = \widehat{\gamma}W_{\mathrm{hm}}.
  • Compact domain of the finite maximum (originally line 931). Your intuition regarding the compact dual unit sphere is completely correct. Define the compact dual unit sphere Sψ,∗:=U∈Rk×d:∥U∥ψ,∗=1\mathcal{S}_{\psi,*} := \\{U \in \mathbb{R}^{k\times d} : \lVert U\rVert_{\psi,*} = 1\\}. We take the maximum of the continuous map (U,Z)↦∥∇2ψ∗(U)[Z]∥ψ(U, Z) \mapsto \lVert\nabla^2\psi^*(U)[Z]\rVert_\psi over the compact product Sψ,∗×Sψ,∗\mathcal{S}_{\psi,*} \times \mathcal{S}_{\psi,*}. We added intermediate derivations now in line 1659.

Negative normalized margin in the mini-batch counterexample (W3).

Thank you for pointing this out. For every sufficiently large TT, (C.9) establishes γ(WT)≤−δ<0\gamma(W_T) \le -\delta < 0 (with δ>0\delta > 0) under both sampling schemes, rather than merely keeping γ(WT)\gamma(W_T) bounded away from γ^\widehat{\gamma}. This negative margin implies that WTW_T misclassifies at least one training sample, which is indeed a stronger and more noteworthy conclusion. In the revised manuscript, we state γ(WT)≤−δ<0\gamma(W_T) \le -\delta < 0 directly in Theorem 2 and highlight this conclusion.

Verification of ∥Z∥ψ,∗=∥Z∥F/ν\lVert Z\rVert_{\psi,*} = \lVert Z\rVert_F / \nu (W4).

Thank you for raising this question. To our understanding, the identity ∥Z∥ψ,∗=∥Z∥F/ν\lVert Z\rVert_{\psi,*} = \lVert Z\rVert_F / \nu (originally at line 1288 and now Eq. (C.34) in the proof of Theorem C.1) holds as stated. In Theorem C.1, the mirror potential is defined in Eq. (C.30) as ψ(W)=νL∥W∥FL\psi(W) = \nu^L \lVert W\rVert_F^L, which gives ∥W∥ψ=ψ(W)1/L=ν∥W∥F\lVert W\rVert_\psi = \psi(W)^{1/L} = \nu\lVert W\rVert_F. By the definition of the dual norm, it follows directly that ∥Z∥ψ,∗=sup⁡∥W∥ψ≤1⟨Z,W⟩=sup⁡∥W∥F≤1/ν⟨Z,W⟩=∥Z∥Fν\lVert Z\rVert_{\psi,*} = \sup_{\lVert W\rVert_\psi \le 1}\langle Z, W\rangle = \sup_{\lVert W\rVert_F \le 1/\nu}\langle Z, W\rangle = \frac{\lVert Z\rVert_F}{\nu}.

Static momentum parameter β\beta (W5).

Thank you for your suggestion. In the revised manuscript, we have simplified both the momentum update in the main text (Eq. (7)) and Algorithm B.1 to use a static parameter β∈[0,1)\beta \in [0, 1) directly.

AuthorsOpenReview ↗

Response to Reviewer MhRf (Part 2/4)

Explicit β\beta dependence of the convergence rates in Theorems 3 and 4 (W6 & Q3 & Q5)

Thank you for this constructive suggestion. We have revised both the main text (Theorems 3 and 4) and all intermediate lemmas and theorems in the appendix D to state the explicit dependence on β\beta throughout. Following your advice, we added a discussion after each of Theorems 3 and 4 in Section 4.2 explaining how the corresponding convergence bounds depend on the momentum parameter β\beta.

The rates in Theorems 3 and 4 follow from the finite-time bounds in Theorems D.1 and D.2, respectively, by absorbing the lower-order initialization terms. The table below summarizes the resulting upper bounds on Dψ(W^,WT/∥WT∥ψ)D_\psi(\widehat{W}, W_T/\lVert W_T\rVert_\psi) and shows how their dependence on β\beta differs across the three settings.

SettingConvergence rate
Full gradient (Thm 3)O((1+γ^−1log⁡2n2(k−1)1−β+nβ(1−β)2)q(T))O\left(\left(1 + \widehat{\gamma}^{-1}\log\frac{2n^2(k-1)}{1-\beta} + \frac{n\beta}{(1-\beta)^2}\right) q(T)\right)
Mini batch IID (Thm 4i)O((1+γ^−1log⁡2ns(k−1)1−β+sβ(1−β)2)log⁡2(e+τT)τTr2(β))O\left(\left(1 + \widehat{\gamma}^{-1}\log\frac{2ns(k-1)}{1-\beta} + \frac{s\beta}{(1-\beta)^2}\right) \frac{\log^2(e+\tau_T)}{\tau_T^{r_2(\beta)}}\right)
Mini batch RR (Thm 4ii)O((1+γ^−1log⁡2ns(k−1)(1−β)β2m−1+sβ2−2m(1−β)2)q(T))O\left(\left(1 + \widehat{\gamma}^{-1}\log\frac{2ns(k-1)}{(1-\beta)\beta^{2m-1}} + \frac{s\beta^{2-2m}}{(1-\beta)^2}\right) q(T)\right)

Here m=n/sm = n/s is the number of batches per epoch, χ=−slog⁡(1−min⁡i∈[n]pi)>0\chi = -s\log(1 - \min_{i \in [n]} p_i) > 0, τT=T\tau_T = T for 0<a<10 < a < 1 and log⁡T\log T for a=1a = 1, q(T)q(T) is the rate function in Theorem 3, and r_2(\beta) = \min\left\\{\frac{1-a}{L-1}, \frac{\chi}{\chi+\log(1/\beta)}\min\left\\{\frac{L-2+a}{L-1}, 1-a\right\\}\right\\} for 0<a<10 < a < 1 (with 1/(L−1)1/(L-1) and 11 when a=1a = 1). Below we discuss the β\beta dependence in each bound:

  • Full gradient (Theorem 3): In the prefactor, the factor (1−β)−1(1-\beta)^{-1} inside the logarithm reflects the weight 1−β1-\beta assigned to the current gradient, while nβ(1−β)2\frac{n\beta}{(1-\beta)^2} arises from bounding the normalized temporal lag error from past iterates. As β↓0\beta \downarrow 0, the lag term vanishes as O(β)O(\beta) and the prefactor approaches a finite limit, so the bound remains uniformly valid for arbitrarily small β>0\beta > 0. In particular, Theorem 3 also holds at β=0\beta = 0, where the update reduces to NMD without momentum (though Theorem 1 gives a tighter bound at β=0\beta = 0 by avoiding the merged lag rate q(T)q(T) and the extra factor of nn inside the logarithm). Conversely, as β↑1\beta \uparrow 1, slower decay of past gradient weights amplifies the temporal lag error and causes the prefactor to grow at order (1−β)−2(1-\beta)^{-2}.
  • Independent sampling with replacement (Theorem 4i): The factor (1−β)−1(1-\beta)^{-1} inside the logarithm and the term sβ(1−β)2\frac{s\beta}{(1-\beta)^2} in the prefactor arise from the weight scaling of the current batch and the normalized temporal lag error, while the factor χχ+log⁡(1/β)\frac{\chi}{\chi+\log(1/\beta)} in the rate exponent r2(β)r_2(\beta) reflects balancing the historical weight decay across the coverage window against the probability of missing a sample. As β↓0\beta \downarrow 0, the lag term vanishes as O(sβ)O(s\beta) and the prefactor approaches a finite positive limit, whereas the rate exponent r2(β)=Θ(1/log⁡(1/β))r_2(\beta) = \Theta(1/\log(1/\beta)) tends to zero. Conversely, as β↑1\beta \uparrow 1, r2(β)r_2(\beta) approaches the exponent of q(T)q(T) for full gradients, while the lag term dominates the prefactor and grows at order s/(1−β)2s/(1-\beta)^2.
  • Random reshuffling (Theorem 4ii): Covering all nn samples requires a window of 2m2m batches (m=n/sm = n/s), yielding a minimum effective sample weight of s−1(1−β)β2m−1s^{-1}(1-\beta)\beta^{2m-1}. This weight lower bound introduces ((1−β)β2m−1)−1((1-\beta)\beta^{2m-1})^{-1} inside the logarithm, and dividing the temporal lag factor β1−β\frac{\beta}{1-\beta} by it yields sβ2−2m(1−β)2\frac{s\beta^{2-2m}}{(1-\beta)^2}. For m>1m > 1 (s<ns < n), this lag term dominates the prefactor, growing at order sβ2−2ms\beta^{2-2m} as β↓0\beta \downarrow 0 and at order s/(1−β)2s/(1-\beta)^2 as β↑1\beta \uparrow 1. Unlike the bound in Theorem 3 for full gradients, both mini batch bounds in Theorem 4 degenerate as β↓0\beta \downarrow 0 and do not extend to β=0\beta = 0 for s<ns < n, consistent with the failure of NMD with mini batches and without momentum in Theorem 2 and Proposition 1.
AuthorsOpenReview ↗

Response to Reviewer MhRf (Part 3/4)

Applications of homogeneous mirror potentials and the L>2L > 2 regime (Q1).

Q1.1 Applications beyond Frobenius and negative entropy. Homogeneous mirror potentials in Definition 1 (including entrywise power potentials Φ(W)=∥W∥pp/p\Phi(W) = \lVert W \rVert_p^p / p with L=p≥2L = p \ge 2, Schatten-pp potentials, and grouped matrix potentials) have concrete applications across CNN image classification, Transformer attention, and reinforcement learning policy optimization, where they outperform or complement the Euclidean baseline (p=2p = 2):

  • CNN image classification: Sun et al. [1] train MobileNetV2 on CIFAR-10 with pp-GD (Φ(W)=∥W∥pp/p\Phi(W) = \lVert W \rVert_p^p / p) and report a higher mean test accuracy at p=3p = 3 (93.2393.23\\%) than at Euclidean p=2p = 2 (91.9791.97\\%), while Azizan et al. [2] show that varying pp directly shapes the learned weight distribution in ResNet-18.
  • Softmax attention and Vision Transformers: Julistiono et al. [3] use entrywise pp-power potentials to achieve generalized max-margin token selection in softmax attention and validate the cubic potential (p=3p = 3) in Vision Transformer training.
  • Policy optimization in reinforcement learning: Li, Lan, and Zhao [4] show that homotopic policy mirror descent with the power potential ∣⋅∣pp\\|\cdot\\|_p^p for p>1p>1 reaches the optimal policy set in finitely many iterations and converges to a policy that is uniform over the optimal actions at each state. Li and Wei [5] illustrate finite-time termination of policy mirror descent on Grid World with a cubic Tsallis potential (q=3q=3).

Q1.2 Practical usage illustrated on a medical image classification pipeline. Consider adapting a pretrained Vision Transformer to multiclass medical image diagnosis, where high-resolution scans are split into visual patches, processed through self-attention and MLP blocks, and classified by a linear head under memory-constrained small mini-batches and class imbalance. Our framework suggests concrete analyses and potential gains across three key modules:

  • Multiclass diagnostic head (linear probing): On frozen, linearly separable encoder features, Theorem 4 characterizes the exact ∥⋅∥ψ\lVert \cdot \rVert_\psi max-margin classifier selected by mini-batch NMD with momentum. Applying this analysis may prevent the directional bias or divergence of momentum-free mini-batch normalization under small batches and rare-class imbalance (Theorem 2), while entrywise ℓp\ell_p or Schatten-pp potentials may improve generalization via sparse biomarker selection or low-rank sharing across related disease classes.
  • Self-attention module (lesion patch selection): Because diagnosis often hinges on a few localized lesion patches amid background tissue, combining our dual-momentum analysis with two-stage attention fine-tuning that freezes the feed-forward block to train the key-query matrix (adapted from [6]) may extend full-batch max-margin token selection [3] to mini-batch training, helping attention stably isolate diagnostic patches under stochastic sampling.
  • Feed-forward MLP / ReLU blocks: Extending homogeneous-network mirror flow [7] to discrete mini-batch NMD with momentum may clarify how potential geometry governs sparse versus dense feature sharing across hidden units, potentially improving morphological feature robustness when fine-tuning on limited clinical cohorts.

Q1.3 Reasonableness of the L>2L > 2 regime.

  • Theoretically, first, for potentials Φ(W)=∥W∥pp/p\Phi(W) = \lVert W \rVert_p^p / p (p>2p > 2), setting L=p>2L = p > 2 in Definition 1 ensures ∇2ψ(W)≻0\nabla^2 \psi(W) \succ 0 away from zero (Lemma B.7) while preserving exact LL-homogeneity. Second, for L>2L > 2, as ∥Θt∥ψ,∗≍1+St→∞\lVert \Theta_t \rVert_{\psi,*} \asymp 1 + S_t \to \infty (Lemma B.11), the dual Hessian bound O(∥Θt∥ψ,∗−(L−2)/(L−1))O(\lVert \Theta_t \rVert_{\psi,*}^{-(L-2)/(L-1)}) (Lemma B.8) decays along the trajectory, which tightens single-step primal increments ∥Wt+1−Wt∥ψ\lVert W_{t+1} - W_t \rVert_\psi (Lemma B.12) and momentum lag errors (Lemma D.1). This yields global convergence from arbitrary initialization for all L≥2L \ge 2 and removes the L<(3+5)/2L < (3 + \sqrt{5})/2 restriction in prior binary NMD rate analyses [8, Theorem 22]. Third, pairing primal norm growth ∥Wt∥ψ≍(1+St)1/(L−1)\lVert W_t \rVert_\psi \asymp (1 + S_t)^{1/(L-1)} (Lemma B.11) with the directional rate O(T−(1−a)/(L−1))O(T^{-(1-a)/(L-1)}) (Theorem 1) shows that moderate L>2L > 2 tempers weight growth while maintaining practical convergence speed.
  • Practically, the LL-homogeneous (L>2) potentials highlighted in Q1.1 already operate in this regime and show concrete gains across MobileNetV2 classification, Vision Transformer training, and policy mirror descent.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.