- 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 compared to other works in the literature. E.g. is strict inequality in Definition 1 necessary, or can it be relaxed to ?
2 comments
Response to Reviewer dte7 (Part 2/2)
Comparison of mirror potentials and relaxing to (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 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.
Work Optimizer Setting Homogeneity Other cond. on [5] Full-batch MD Binary linear Strong conv., smooth [6] Mirror flow Binary linear , PD [4] Mirror flow Binary hom. net (asymp.) Strict conv., loc. Lip. [1] Full-batch MD Binary linear [3] Full-batch MD Binary attention [2] Full-batch MD, NMD Binary linear , PD Ours Full/mini NMD ( mom.) Multiclass linear Smoothed , , PD MD and NMD denote mirror descent and normalized mirror descent. Full/mini denotes full-batch or mini-batch updates, and mom. denotes updates with or without momentum.
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.
A indicates that the stated assumptions allow nonhomogeneous potentials. A indicates absolute homogeneity of , and (asymp.) indicates asymptotic homogeneity.
PD denotes positive definite, conv. denotes convexity, and loc. Lip. denotes locally Lipschitz. Here is the base potential.
-
Relaxing to .
We can relax to allow by additionally assuming for every . Specifically, when , inherits -homogeneity directly, while continuity of on the compact Frobenius unit sphere implies , so we have for all . This lower bound yields (Lemma B.7), the bound on (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.
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.
Loss. Theorems 1–4 and Proposition 1 can extend with the same rate orders to the multiclass exponential loss Lexp(W)=n1∑i=1n∑l=yie−mil(W) and PairLogLoss Lpll(W)=n1∑i=1n∑l=yilog(1+e−mil(W)), where mil(W):=(eyi−el)⊤Wxi. 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 and S2, Theorem 2 and Proposition 1 likewise follow by the same proof steps.
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 and ST:=∑t<Tηt→∞. Specifically, St→∞ gives ∥Wt∥ψL−1≍1+St (Lemma B.11), while ηt→0 (hence suptηt<∞) gives ∥Wt+1−Wt∥ψ→0 (Lemma B.12), yielding an o(ST) 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−Mt∥ψ,∗/G(Wt)→0 so that covered windows contribute o(ST) directional error for each fixed window length K (Lemma D.2). Dividing by ∥WT∥ψL−1≍1+ST then yields vanishing Bregman error under full-batch updates and reshuffling (Lemma D.3), whereas under independent sampling, grouping disjoint windows by tmodK and using ∑tηt2/(1+St+1)2<∞ as in Lemma C.2(i) shows that the ηt-weighted uncovered-window fraction in Lemma D.4 converges almost surely to πK with a K-independent prefactor and vanishes as K→∞. In our work, we adopt the power-law schedule ηt=η0t−a in Assumption 3 simply to obtain explicit rates in T.
Necessity of L-homogeneity.
In our convergence proofs, L-homogeneity is essential in three ways. (i) It induces the margin norm ∥W∥ψ=ψ(W)1/L and the dual norm used to normalize gradients and momentum. (ii) For Θt=∇ψ(Wt), it yields ∥Wt∥ψ=L−1/(L−1)∥Θt∥ψ,∗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∥ψ and hence the lag error from past gradients in Mt (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.