acceptodds
Under review as a conference paper at ICLR 2027

Homogenization of -Adversarial Training in High-Dimensions: Exact Dynamics under Stochastic Gradient Descent

Abstract

We develop a framework for analyzing the learning dynamics of -adversarial training of single-index models on binary mixtures of Gaussians in the high-dimensional limit under streaming stochastic gradient descent (SGD). We derive deterministic equivalents for a broad class of statistics of the SGD iterates, including the adversarial risk and distance to adversarial optimality, in terms of the solution to a system of ODEs. We use them to study two idealized learning rate schedules: the Polyak stepsize and exact line search. In the case of -adversarial least squares with a single class, we show that, unlike noiseless standard least squares, no constant learning rate guarantees monotone descent of SGD towards a minimizer of the adversarial risk. Moreover, we identify anisotropic covariance and a mismatch in ridge parameters as the two sources of suboptimality of exact line search relative to the Polyak stepsize. We also introduce a stochastic differential equation (SDE), called adversarial homogenized SGD, that captures the evolution of statistics of the iterates of SGD. For -adversarial least squares, using this SDE, we show the evolution of the risk is equivalent, up to a dimension-free error, to that of SGD on standard least squares with an adaptive learning rate and adaptive -regularization. When the dynamics converge, the limiting adversarial risk and SGD iterate are determined by a fixed-point equation, with the limiting iterate being the solution of a ridge regression problem whose regularization parameter is the limiting effective regularization of SGD.

Primary area:
optimization
Keywords:
adversarial training, high-dimensional probability, stochastic optimization, machine learning theory

Reviews

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

This paper develops a high-dimensional deterministic description of SGD dynamics under ℓ2\ell_2-adversarial training, revealing its connection to adaptive ridge regularization and explaining how adversarial perturbations influence learning-rate stability and convergence.

Critical strengths

The paper provides a rigorous and precise characterization of the entire SGD learning dynamics under ℓ2\ell_2-adversarial training

Critical weaknesses
  1. The paper is difficult to follow due to poorly organized notation and insufficient exposition of the problem setup. For example, Equation (1) introduces several variables and functions without clearly explaining their roles. Moreover, the formulation departs from the standard presentation of adversarial training objectives in the literature, making it unnecessarily difficult for readers to recognize the underlying problem.

  2. The paper is heavily driven by technical derivations and proofs, with limited discussion of the underlying insights and implications for adversarial training. Much of the analysis appears to be a direct extension of the existing homogenized SGD (HSGD) framework (Collins-Woodfin & Paquette, 2024; Paquette et al., 2022; Collins-Woodfin et al., 2024a) to adversarial training. While the theoretical results may be technically substantial, the paper does not sufficiently explain what fundamentally new understanding of adversarial training is gained from this extension. In particular, the authors should better motivate the research questions, highlight the insights behind the theoretical findings, and discuss how these findings could inform the design or improvement of adversarial training algorithms.

Questions for authors

The connection between ridge regression and adversarial training under ell2 perturbation has been well established in the literature, what different insight can be provided in this paper?

3 comments

We thank the reviewer for their feedback. The main text was revised to address them. The results are unchanged, with one addition (Proposition 3.1). The numbers below refer to the revised PDF. For a detailed description of the changes in the revised PDF, see https://openreview.net/forum?id=MHso2fuW13&noteId=s5BtWieFDl

Weakness 1 (notation and Eq. (1)). Eq. (1) is the usual min-max objective of adversarial training, written in the notation of single-index models used in the works we build on. In the more common notation, with input xx, label yy, parameter θ\theta and loss ℓ\ell, it reads

min⁡θE[max⁡∥Δ∥≤δℓ(θ⊤(x+Δ),y)]+λ2∥θ∥2.\min_\theta \mathbb{E}\Big[\max_{\Vert\Delta\Vert\le\delta}\ell\big(\theta^\top(x+\Delta),y\big)\Big]+\tfrac{\lambda}{2}\Vert\theta\Vert^2 .

We write XX for θ\theta and aa for xx, and the label enters through the loss: fI(X⊤a,ϵ)f_I(X^\top a,\epsilon) stands for ℓ(X⊤a,y)\ell(X^\top a,y), where yy is given by the class II (hard labels) or by a teacher model with noise ϵ\epsilon (soft labels). The introduction now defines each of these symbols before Eq. (1), and derives Eq. (2) in one line: the adversary can change X⊤aX^\top a by at most δ∥X∥\delta\Vert X\Vert. In Sections 1.1 and 2, each object is now introduced where it is first used, with a sentence on its role. For instance, the matrix B^i(W)\widehat B_i(W) collects the mean and covariance of X⊤aX^\top a and the size of the perturbation. Notation not needed for the statements now appears only in Appendix B.

Weakness 2 (insights, relation to HSGD, implications).

  • New relative to the HSGD framework (Section 2, "Differences with prior work", previously Remark 2.1). Each update depends on the adversarial perturbation, which scales with ∥Xk∥\Vert X_k\Vert and is selected through an argmax. The equations must therefore also track the norm of the iterate and its overlap with the adversarial minimizer X⋆,AdvX^{\star,\mathrm{Adv}}, which need not coincide with X⋆X^\star. Already for least squares, the linear Volterra equation of standard training becomes a system of coupled nonlinear ones.

  • New understanding of adversarial training. The introduction now poses three questions, and a Key Takeaway box in each of Sections 2–4 answers one: (i) the risk curves of SGD are predictable at non-vanishing learning rates; (ii) the ridge correspondence holds during training, with fluctuations that persist (see below); (iii) for any δ>0\delta\gt 0 the problem no longer interpolates, so no constant learning rate gives monotone decrease of the distance to X⋆, AdvX^{\star, \mathrm{Adv}}, even when the minimizer is unchanged.

  • Implications for algorithms (Section 4). The learning rate must decay. Moreover, an adaptive schedule should account for both the shift of the minimizer (i.e. different objective) and the adversarial perturbation. Greedy schedules such as exact line search are penalized by anisotropy as in least squares for small δ\delta, and less as δ\delta grows (Eq. (15)). We do not propose a new algorithm: designing a practical schedule on these principles is left for future work (Section 5).

Question (insight beyond the known ridge connection). The known results are static: under appropriate assumptions, they identify the minimizer of ℓ2\ell_2-adversarial least squares with a ridge regression solution (Xing et al., 2021; Ribeiro et al., 2023). To our knowledge, the correspondence had not been characterized along the trajectory of SGD. Section 3 shows that it extends there, through the ratio q(Xk)=∥Xk∥/2R(Xk)q(X_k)=\Vert X_k\Vert/\sqrt{2\mathcal{R}(X_k)}, in three ways.

  1. Risk. Adversarial training induces an effective learning rate and an effective regularization on SGD, both explicit functions of this ratio. The adversarial risk follows, up to a dimension-free error, that of SGD on standard least squares run with this adaptive learning rate and adaptive ℓ2\ell_2-regularization (Theorem 3.1).
  2. Iterates. The iterates fluctuate around the gradient flow of a ridge objective whose parameter is the deterministic equivalent of this effective regularization, at a squared distance of order at most γ\gamma for small learning rate γ\gamma (new Proposition 3.1). These fluctuations do not vanish because adversarial training does not interpolate.
  3. Long-time limit. Under the convergence assumption q(t)→q∞q(t) \to q_{\infty}, in the long-time limit of the deterministic equivalents this flow converges to the ridge solution whose parameter is the limit of the effective regularization, while the fluctuations persist. They vanish only as γ→0\gamma\to 0, where the minimizer of the adversarial risk is recovered (Theorems 3.2 and 3.3). This minimizer corresponds to the ridge regression solution computed in Xing et al., 2021.

Could you explain to me in two sentences the new insights your paper has beyond ridge regularization and HSGD?

We studied the impact of the adversarial objective on the choice of learning rate: in general, the learning rate that decreases the distance to the minimizer fastest (Polyak stepsize) combines the standard descent term with two corrections, one for the shift of the minimizer and one for the adversarial perturbation, which suggests that a schedule designed for standard training cannot be reused as is: it should also account for the adversarial perturbation, even when the minimizer is unchanged, and for the shift of the minimizer when it moves. For least squares with a single class, the loss can no longer be driven to zero for any δ>0\delta \gt 0, so the learning rate must decay, and for small δ\delta the behaviour of standard training persists, with strong anisotropy making greedy schedules such as exact line search slow, a penalty that fades as δ\delta grows (see the Key Takeaway of Section 4).

Reviewer_eZPVOpenReview ↗
Rating
3
Confidence
2
Informativeness
3(+1)
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper studies streaming SGD for ℓ2\ell_2-adversarial training on binary Gaussian mixtures with bounded, commuting covariances. It derives deterministic equations for the risk, parameter norm, and overlaps, and proves a finite-time approximation under stopping conditions. For least squares, it relates the drift to an adaptive learning rate and ridge penalty, bounds the risk difference from adaptively regularized SGD, and characterizes stationary statistics assuming a key ratio converges. It also compares idealized line search and Polyak stepsizes. Experiments on synthetic regression and classification problems compare the predicted curves with SGD.

Critical strengths

This is an interesting work.

  1. The finite-time description of adversarial SGD is useful. I find Theorem 2.1 a meaningful extension of the existing homogenization framework. The attack depends on the current iterate, so its contribution must be included in the drift and the error analysis. Allowing anisotropic, commuting covariances also makes the result more informative than an isotropic calculation. The regression and classification experiments in Figure 1 support the predicted concentration.

  2. The least-squares analysis gives a concrete optimization interpretation. I appreciate the explicit effective learning rate and regularization parameter in Section 3. I also find Eq.~(13) helpful: it separates the effect of the covariance spectrum from the mismatch between the current ridge penalty and the one associated with the adversarial optimum. This gives a clear explanation for the learning-rate comparisons in Figures 2 and 5

Critical weaknesses
  1. The ridge solution does not account for the remaining SGD fluctuations. I am not convinced by the statement that SGD converges to a ridge optimum in Appendix E (p. 71). Theorem 3.2 identifies the limits of deterministic coordinate approximations. In high dimensions, however, fluctuations that vanish in each coordinate can still have a nonzero total squared norm. A simple example makes this distinction explicit. Take K=IdK=I_d, δ=1\delta=1, η=λ=0\eta=\lambda=0, ∥X⋆∥=1\|X^\star\|=1, X0=X⋆/2X_0=X^\star/2, and a constant 0<γ<20<\gamma<2. Equation (364) gives q(t)=1q(t)=1, so λ~eff(t)=1\widetilde\lambda_{\mathrm{eff}}(t)=1 and the ridge vector is Xridge=X⋆/2X_{\mathrm{ridge}}=X^\star/2. Yet Eqs. (398)–(399) give
\qquad \|X_{\mathrm{ridge}}\|^2=\frac14.$$ Their difference is $\gamma/[4(2-\gamma)]>0$, independently of $d$. Thus even the limiting statistics retain a contribution that is absent from the ridge vector. This prevents interpreting the result as convergence in Euclidean norm to that vector. I would like the authors to state precisely which limiting object is a ridge solution and to retain the fluctuation contribution when describing the SGD endpoint. This affects a main contribution, rather than only its presentation. 2. **The long-time SGD conclusions require an additional argument.** I do not see how the finite-time approximation establishes the claimed endpoint behavior of SGD. Theorem 2.1 applies on a fixed interval and stops before the trajectory becomes unbounded or approaches the nonsmooth region. Theorem 3.2 then assumes bounded risk and convergence of $q(t)$. Proposition G.2 bounds $q(t)$, but boundedness alone does not imply convergence. The distinction matters because an approximation valid for each fixed time need not control a stationary limit: its error can grow with time, or the trajectory can approach the stopping boundary. Figure 6 is useful numerical evidence, but it does not resolve this issue. I would need either an argument sufficient to transfer the endpoint result to SGD, or a clear restriction of the endpoint claims to conditional statements about the deterministic equations. As written, the theory does not yet justify the long-run SGD interpretation emphasized in the paper.
Questions for authors
  1. Could you clarify the meaning of convergence to the ridge optimum on p.~71, particularly in the isotropic example above? Is the intended claim about deterministic projections, convergence in norm, or a stationary distribution?

  2. Which endpoint conclusions are proved for SGD itself? Could you give conditions that justify convergence of q(t)q(t) and passage from the stopped, finite-time approximation to the long-time limit, or explicitly limit the claims to conditional ODE results?

4 comments
AuthorsOpenReview ↗

Rebuttal (Part 1)

We thank the reviewer for the careful reading, and in particular for the isotropic example, which is correct. Both points are addressed in the revised PDF, to which the numbers below refer. For a detailed description of the changes in the revised PDF, see https://openreview.net/forum?id=MHso2fuW13&noteId=s5BtWieFDl

Q1. Which object is a ridge solution. Of the three readings you propose, the intended one is deterministic projections. We do not claim convergence in norm or a stationary distribution, and the sentence on p. 71 of the submission overstated the result. Let ρj(t)\rho_j(t) be the deterministic equivalent of ⟨X⌊td⌋,ωj⟩\langle X_{\lfloor td\rfloor},\omega_j\rangle. The deterministic vector ∑jρj(t)ωj\sum_j\rho_j(t)\omega_j is the gradient flow of the ridge objective R(⋅)+12λ~eff(t)∥⋅∥2\mathcal{R}(\cdot)+\tfrac12\tilde\lambda^{\mathrm{eff}}(t)\Vert\cdot\Vert^2 with learning rate γ~eff(t)\tilde\gamma^{\mathrm{eff}}(t), which we call the adaptive ridge flow. It is this flow, and not the iterate, that converges to the ridge solution X∞X_\infty.

Each coordinate ⟨X⌊td⌋,ωj⟩\langle X_{\lfloor td\rfloor},\omega_j\rangle concentrates around ρj(t)\rho_j(t), but the deterministic equivalent of the squared distance ∥X⌊td⌋−∑jρj(t)ωj∥2\Vert X_{\lfloor td\rfloor}-\sum_j\rho_j(t)\omega_j\Vert^2 sums dd contributions, each at most γsup⁡s≤tRAdv(s)/d\gamma\sup_{s\le t}\mathscr{R}^{\mathrm{Adv}}(s)/d. These contributions are nonnegative, so they cannot cancel, and their sum does not necessarily vanish. The new Proposition 3.1 (Proposition E.1, p. 72) addresses this. Indeed, it shows that, with overwhelming probability, ∥X⌊td⌋−∑jρj(t)ωj∥2\Vert X_{\lfloor td\rfloor}-\sum_j\rho_j(t)\omega_j\Vert^2 is within Cd−εCd^{-\varepsilon} of B^44(t)−∑jρj(t)2\widehat B_{44}(t)-\sum_j\rho_j(t)^2 uniformly on [0,T][0,T], where B^44(t)\widehat B_{44}(t) is the deterministic equivalent of ∥X⌊td⌋∥2\Vert X_{\lfloor td\rfloor}\Vert^2, and that for t>0t\gt 0

0<B^44(t)−∑jρj(t)2≤γsup⁡s≤tRAdv(s),0\lt \widehat B_{44}(t)-\sum_j\rho_j(t)^2\le\gamma\sup_{s\le t}\mathscr{R}^{\mathrm{Adv}}(s),

which is O(γ)O(\gamma) uniformly in tt and dd for γ≤γ0\gamma\le\gamma_0. Theorem 3.2 now states both limits: the flow converges to X∞X_\infty, and the deterministic equivalent of the fluctuation term converges to B^44(∞)−∥X∞∥2>0\widehat B_{44}(\infty)-\Vert X_\infty\Vert^2\gt 0. Appendix E (p. 75) gives this limit in closed form,

B^44(∞)−∥X∞∥2=γd∑jλjRAdv(∞)λj(1+δ2πq∞)+δ2+δ2π1q∞.\widehat B_{44}(\infty)-\Vert X_\infty\Vert^2=\frac{\gamma}{d}\sum_j\frac{\lambda_j\mathscr{R}^{\mathrm{Adv}}(\infty)}{\lambda_j(1+\delta \sqrt{\frac{2}{\pi}}q_\infty) + \delta^2+\delta \sqrt{\frac{2}{\pi}} \frac{1}{q_{\infty}}}.

In your isotropic example, this limit of the deterministic equivalents of the fluctations equals precisely B^44(∞)−∥X∞∥2=γ4(2−γ),\widehat B_{44}(\infty)-\Vert X_\infty\Vert^2=\frac{\gamma}{4(2-\gamma)}, exactly the gap you computed. The fluctuations vanish only as γ→0\gamma\to 0, where X⋆,AdvX^{\star,\mathrm{Adv}} is recovered (Theorem 3.3 and the discussion after it).

We made the following changes described in the comment:

Changes:

  • We updated the abstract and contributions to reflect the comment above.
  • In Section 3, we added the paragraph "Fluctuations around the adaptive ridge flow", updated Theorem 3.2 to include the fluctuations and added a Key Takeaway to the section to highlight the main insight of the section.
  • We updated the table of contents in the Appendix and Appendix E with Proposition E.1 which proves Proposition 3.1 in the main text and updated the discussion after it to remove the initial wording of convergence of SGD. We also updated the statement of Theorem G.1 in Appendix G to reflect it contains the proof of the convergence of the adaptive ridge flow in the long-time limit.
AuthorsOpenReview ↗

Rebuttal (Part 2)

Q2. What is proved for SGD. We agree, and we followed your second option. Theorems 3.2 and 3.3 are now presented as limits of the deterministic equivalents (paragraph "Limit t→∞t\to\infty of the deterministic equivalents"), conditional on q(t)→q∞q(t)\to q_\infty. Given the short window of the discussion period, we leave the proof of q(t)→q∞q(t) \to q_{\infty} for future work and use Figures 1 (right) and 6 as numerical evidence supporting this assumption.

What is proved for SGD are finite-horizon statements, with TT independent of dd. In the least-squares setting of Section 3, the stopping time of Theorem 2.1 can be removed on every [0,T][0,T]. Indeed, under the condition of Proposition 3.1, the proof of Proposition E.1 shows that the deterministic equivalents stay bounded and at a fixed distance from the nonsmooth region, uniformly in dd. Hence, for a statistic φ\varphi covered by Theorem 2.1 with deterministic equivalent ϕ\phi,

∣φ(X⌊Td⌋)−ϕ(∞)∣≤C(T)d−ε+∣ϕ(T)−ϕ(∞)∣.\lvert\varphi(X_{\lfloor Td\rfloor})-\phi(\infty)\rvert\le C(T)d^{-\varepsilon}+\lvert\phi(T)-\phi(\infty)\rvert.

The first term vanishes as d→∞d\to\infty at fixed TT, and the second as T→∞T\to\infty when q(t)→q∞q(t) \to q_{\infty}. Since C(T)C(T) grows with TT, the two limits cannot be interchanged, and we make no claim when TT grows with dd. We would be glad to add this inequality as a remark if you find it useful. Once again, given the short time frame of the discussion period, we leave the dependence of TT on dd to future work.

Finally, of the two hypotheses of Theorem 3.2 that you mention, the bounded risk is now proved for γ≤γ0\gamma\le\gamma_0 (Proposition 3.1), so the convergence of q(t)q(t) is the only remaining assumption on the dynamics.

Thank you for the detailed responses and for revising the manuscript. Proposition 3.1 and the revised Theorem 3.2 clarify that the adaptive ridge flow converges to the ridge solution. The fluctuation term also recovers the positive gap in the isotropic example.

The scope of the long-time results is now clear. The approximation for SGD holds on fixed time horizons, and the long-time results concern the deterministic equivalents under the assumption that q(t)→q∞q(t)\to q_\infty. I would welcome the proposed remark with the error bound, as it would make the role of the fixed time horizon explicit.

With these clarifications, I consider both of my concerns addressed. And I will raise my Informativeness and Soundness of the work. I will keep my initial positive evaluation.

Thank you for the feedback. The remark is now in the main text, right after Theorem 3.2 (lines 432–440, page 9 of the latest PDF).

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

This paper studies how SGD behaves during ℓ2\ell_ 2 -adversarial training of simple linear-type models on Gaussian mixture data when the dimension is large. It shows that the training dynamics can be predicted exactly by a deterministic system of ODEs, even with large learning rates. For adversarial least squares, adversarial training turns out to act like ordinary SGD with an adaptive learning rate and adaptive ridge regularization, and the final solution is a ridge regression solution. Simulations on synthetic data match the theory well.

Critical strengths

The paper provides a rigorous theoretical analysis for high-dimensional SGD theory to a min-max objective. It covers large learning rates, unlike earlier SDE approximations that need vanishing step sizes. Under the ridge-regression setting, the paper presents what adversarial training does along the whole SGD path. Theory and simulations agree closely, and full proofs and reproducibility details are provided.

Critical weaknesses

The paper is difficult to follow, particularly for readers who are not already familiar with the authors' prior work. The Introduction introduces substantial mathematical formalism and notation before adequately establishing the problem's motivation, the specific questions the paper seeks to answer, or the key insights that its theoretical results are intended to provide. As a result, it is difficult to understand the purpose of the technical development and what new understanding it offers beyond the derivations themselves.

Moreover, the paper relies heavily on Collins-Woodfin et al. (2024a) and Collins-Woodfin & Seroussi (2025) without providing sufficient background or intuition to make the presentation self-contained. Readers unfamiliar with these works may struggle to understand the problem setup, the rationale behind the analysis, and how the present paper builds upon existing results. Overall, the exposition is overly technical without providing sufficient conceptual guidance, making it challenging to identify the paper's main contributions and assess their significance. I encourage the authors to better motivate the theoretical investigation, introduce the key concepts and notation more gradually, explain the intuition behind the main results, and explicitly clarify what new insights this paper contributes beyond the cited prior work.

Without a clearer explanation of the motivation, intuition, and incremental contributions, it is difficult to assess the significance of the theoretical results and to determine what the paper adds to the existing literature.

Questions for authors

In Section 1.1, a line of assumptions are introduced. Could the authors provide intuition for these assumptions and justify why they are reasonable and realistic in the problem setting? In particular, it would be helpful to clarify whether these assumptions are motivated by practical considerations or are primarily imposed to facilitate the theoretical analysis.

2 comments
AuthorsOpenReview ↗

Rebuttal (Part 1)

We thank the reviewer for the comments, which led us to revise the main text. The results are unchanged, with one addition (Proposition 3.1). The numbers below refer to the revised PDF. For a detailed description of the changes in the revised PDF, see https://openreview.net/forum?id=MHso2fuW13&noteId=s5BtWieFDl

Motivation, questions and insights before the formalism. The introduction now states the gap before any formula: theory mostly describes the minimizers of adversarial objectives, and existing descriptions of the dynamics require vanishing learning rates. It then poses three questions:

  • Can the learning curves of SGD under adversarial training be predicted in high dimension for anisotropic data?
  • Does the known correspondence of the minimizer of ℓ2\ell_2-adversarial training with the solution of a ridge regression problem hold during training?
  • What does the adversary change for the choice of learning rate?

The contributions answer them in this order, and a Key Takeaway box states the main message of each of Sections 2, 3 and 4.

Background and intuition (Section 2). We reorganized Section 2 with the goal of introducing the concepts more gradually, and we lightened its wording and notation. It now starts from the goal in plain terms: scalar statistics of the iterates concentrate around deterministic curves, on the time scale t=k/dt=k/d. It then gives the intuition for why resolvents and contour integrals appear, and explains the role of the stopping time before Theorem 2.1 is stated. The least-squares example now comes right after the theorem, to make the objects concrete.

Notation that is not needed to state the results was moved to Appendix B. There we have more space, and we added further justification: why resolvents are needed and intuition behind how the result extends to general statistics (Assumption 9). How our work builds on Collins-Woodfin et al. (2024a) and Collins-Woodfin & Seroussi (2025) is summarized in the paragraph "Differences with prior work" which previously was Remark 2.1 in the main text of our original submission.

New insights. We added boxes which highlight the Key Takeaway of Sections 2, 3 and 4 in the main text. Here they are:

  • Section 2: In high dimension, SGD under ℓ2\ell_2-adversarial training is predictable: on any fixed time horizon and without a vanishing learning rate, its risk curves follow deterministic curves that can be computed without running SGD.

  • Section 3: Beyond the minimizer, ℓ2\ell_2-adversarial least squares remains tied to ridge regression along the dynamics of SGD. Since adversarial training does not interpolate, for sufficiently small learning rate γ\gamma the iterates fluctuate around an adaptive ridge flow at a squared distance of order at most γ\gamma, which vanishes only as γ→0\gamma \to 0.

  • Section 4: For any δ>0\delta > 0 the problem no longer interpolates, so the learning rate must decay, even when the minimizer is unchanged (δ≤δ−\delta \leq \delta_-), and an adaptive schedule should account for the shift of the minimizer and for the adversarial perturbation. Anisotropy penalizes greedy schedules as in least squares for small δ\delta, and less as δ\delta grows.

AuthorsOpenReview ↗

Rebuttal (Part 2)

Question (assumptions of Section 1.1). The assumptions are now accompanied by sentences explaining their role. To answer directly: together, they give a setting in which two practical aspects of training can be analyzed exactly, the geometry of the data (anisotropy and class structure) and non-vanishing learning rates. This scope is motivated by practice, while the Gaussian model and the regularity conditions are imposed for the analysis. In more detail, they are of four kinds:

  • Modelling assumptions (Assumptions 1 and 2). The data come from a two-class Gaussian mixture with commuting covariances and means, with hard labels (classification) or a noisy teacher model (regression). This is an idealization and is a standard model in the high-dimensional theory of adversarial training and of SGD, and it keeps the two features of real data whose effect we study: anisotropy and class structure.

  • Scaling assumptions (Assumptions 1, 4). The bounds on ∥Ki∥op\Vert K_i\Vert_{\mathrm{op}}, ∥μi∥\Vert\mu_i\Vert, ∥X0∥\Vert X_0\Vert and ∥X⋆∥\Vert X^\star\Vert are a normalization. They keep X⊤aX^\top a, the targets and the risk of order one as dd grows. They fix the regime we study and are not a claim about real data. For instance, the initialization X0∼N(0,Id/d)X_0\sim\mathcal{N}(0,I_d/d) used in our experiments has norm of order one.

  • Learning rate (Assumption 8). The schedule only needs to be bounded. It does not need to vanish, unlike in the SDE approximation of Gu et al. (2023), so our results cover the non-vanishing learning rates used in practice, including large constant ones and decaying schedules. Adaptive schedules that depend on the iterates, such as the Polyak stepsize and exact line search of Section 4, can also be included (Remark B.3). Implementable adaptive stepsizes such as AdaGrad-Norm or RMSprop-Norm could also be studied (Collins-Woodfin et al., 2024b).

  • Technical conditions, imposed for the analysis. Commutativity of the covariances (Assumption 1) is only used to close the equations. It holds for a single class and for classes with a common covariance, as in our experiments. Assumptions 3, 6 and 7 are regularity conditions, which are satisfied for example by phase retrieval and generalized linear models. We provide examples for the functions hih_i and Ii\mathcal{I}_i for least squares and binary logistic regression in Appendix I. See Appendix D in Collins-Woodfin et al. (2024a) for more examples. Assumption 5 (bounded adversarial minimizer) is only needed for statistics involving X⋆,AdvX^{\star,\mathrm{Adv}}. It holds for least squares and can fail when the classes become separable (Remark B.4), in which case Theorem 2.1 still holds for the other statistics.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Revised Submission PDF - Version 1

We have uploaded a revised PDF. We are thankful to all reviewers for their feedback. Section, theorem, equation and page numbers refer to the revised PDF. We did not color the changes: the main text was revised throughout and several passages moved, so nearly all of it would be colored. Instead, we list the changes below and where to find them.

No theorem of the original submission was removed or weakened, and the proofs are unchanged up to notation. The revision contains the following:

  • We revised the main text so that the motivation, the questions and the insights come before the formalisation of the problem setup.
  • We state precisely what is proved about the long-time behaviour of SGD and add one result on its fluctuations.
  • We also simplify the notation to help readability

Main text

  • Abstract. It no longer says that the limiting SGD iterate is a ridge solution. It now says that the iterates fluctuate around the gradient flow of an adaptive ridge regression problem and that, under a convergence assumption, these fluctuations persist in the long-time limit of the deterministic equivalents.

  • Introduction. A new paragraph states the gap and motivation: whether the learning curves can be predicted, whether the ridge regression correspondence holds during training, and what the adversary changes for the choice of learning rate. The objective is given in its standard min-max form (Eq. (1)), with each symbol introduced before it.

  • Section 1.1. The assumptions are accompanied by sentences on their role, for example that commutativity of the covariances is a technical condition and that Assumption 5 may fail (Remark B.4). The matrix B^i(W)\widehat B_i(W) is now defined entry by entry to simplify the notation.

  • Section 2. Reorganized with the goal of introducing the concepts more gradually. We start with the goal of the section and the time scale of the deterministic equivalents. Then we proceed with intuition for the deterministic equivalents (why resolvents and contour integrals appear), the description of the limit dynamics, the diffusion approximation, the role of the stopping time, the main result Theorem 2.1, the least-squares example, the "Differences with prior work" (formerly Remark 2.1) and finally the proof intuition. Notation not needed for the statements now appears only in Appendix B.

  • Section 3. The section opens by recalling the known ridge correspondence at the minimizer, which it then studies along the trajectory of SGD. New Proposition 3.1: under a non-degeneracy condition, on any $ [0,T] $, with no stopping time and a constant independent of dd, the squared distance between SGD and an adaptive ridge flow concentrates around a deterministic quantity that is positive and O(γ)O(\gamma) for small learning rate γ\gamma. Theorem 3.2 now separates the limit of this flow (a ridge solution) from the limit of deterministic equivalent of the fluctuations (positive). The long-time statements are explicitly about the deterministic equivalents and assume that q(t)q(t) converges. The bounded-risk assumption of Theorem 3.2 is now proved for small γ\gamma. Former Remark 3.1 is now Remark B.3 in Appendix B.

  • Section 4. Same results, with an added explanation of why the effective regularization damps the effect of anisotropy.

  • Key Takeaway boxes state the main message of Sections 2, 3 and 4.

Appendix

  • Table of contents. Updated the table of contents to reflect the proof of Proposition 3.1 in Appendix E.

  • Appendix B (pp. 20–28). New opening on why resolvents are needed and how the concentration results transfer to general statistics. Remark B.3 (adaptive schedules) was moved from the main text. We also updated the wording of Remark B.4 to make it clear that Assumption 5 is essential only for statistics involving X⋆,AdvX^{\star,\mathrm{Adv}}.

  • Appendix E (pp. 71–78). New Proposition E.1 with its proof (pp. 72–75): the full version of Proposition 3.1. The proof shows that the deterministic equivalents stay bounded and away from the nonsmooth region uniformly in dd, which removes the stopping time. The discussion after it (p. 75) replaces the sentence "SGD converges to the ridge optimum" and gives the limit of the fluctuations in closed form. The proof of Corollary E.1 is edited for readability.

  • Appendix G. Theorem G.1 (p. 95) now also states the limit of the adaptive ridge flow.

  • Appendices G, I.1 and J. A typo in the set U\mathcal{U} for least squares was fixed (η2\eta^2 instead of η\eta). The sentence on the ODEs used for the simulations moved from a footnote of the main text to Appendix J.

  • Throughout. Notation aligned with the main text, unused notation removed (Appendices C.2 and D.3), typos fixed.

Numbering. Theorems 2.1 and 3.1–3.3, the assumptions and the figures keep their numbers. Among the equations cited in the reviews, former (13) is now (15), and former (398)–(399) are (401)–(402).

AuthorsOpenReview ↗

Revised Submission PDF - Version 2

We have uploaded a revised PDF to include the remark regarding the role of the fixed time horizon in https://openreview.net/forum?id=MHso2fuW13&noteId=9dKi1fb8MW.

See lines 432-440 on page 9. We have also done minor revisions to the caption of Figure 2, the end of Section 4 and Section 5 to make space for this.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.