acceptodds
Under review as a conference paper at ICLR 2027

Implicit Sparse Regularization in Momentum Gradient Descent: A Shifted Early Stopping Window Induced by Momentum and Depth

Abstract

In high-dimensional sparse regression, optimization algorithms are known to induce implicit sparsity through the interplay of overparameterization and early stopping. However, existing theory largely focuses on (stochastic) gradient descent (GD), leaving momentum-based methods — despite their widespread empirical success — poorly understood. This paper provides a theoretical characterization of implicit sparse regularization in momentum gradient descent (MGD). We show that for depth- diagonal networks, MGD with early stopping achieves minimax optimal sparse recovery with sufficiently small initialization and learning rate. Moreover, increasing depth significantly enlarges both the admissible initialization scale and the effective early stopping window, making implicit sparsity more likely to emerge. More importantly, we uncover a distinct temporal effect of momentum: a larger momentum shortens the early stopping window, but it shifts the entire window toward earlier iterations. As a result, MGD induces sparsity earlier than GD. Experimental results strongly support our theoretical findings.

Primary area:
learning theory
Keywords:
Momentum Gradient Descent, Sparse Regression, Depth, Early Stopping Window

Reviews

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

This work investigates the role of depth in a diagonal linear network when training with gradient descent with momentum. The work characterizes the dependence of the early stopping window and time of occurrence on the depth, initialization and learning rate to guarantee sparse recovery. The analysis leverages a Gauss-Newton approximation to derive this. Furthermore, the work draws connections to incremental learning and kernel regime experimentally in toy recovery problems.

Critical strengths

Investigating early stopping is an important topic even in simple models. The work makes clear progress on this by integrating momentum and the interplay with depth. The Gauss-Newton approximation is well-found and an interesting approach to this problem.

Critical weaknesses
  1. The analysis confounds initialization scale and learning rates with depth. The derived bounds are depending on the initialization scale and learning rate, however, to compare fairly in the experiments the same learning rate (the smaller one is fine) to ensure a fair comparison. Similarly, the effective update in the predictor θ\theta scales with α\alpha and depth NN. Therefore using the same α\alpha across depths inherently leads to smaller updates and thus affects the early stopping window. For instance, Fig. 3 should use the same initialization scale αN\alpha^N for each considered depth.

  2. The exposition can be significantly improved. The current theoretical results involve quite a lot of mathematical variables which makes it hard to parse the intended takeaway. For example, a condition on the initialization in Equation 6 is written out over two lines without direct guidance. This is persistent trough the theoretical section. Moreover, this makes it hard to compare similar expressions as it looks like that Init() at lines 209-215 is exactly Equation 6.

Questions for authors

Can the authors discuss the relationship between the manuscript and related work [1] as it directly involves flow analysis of momentum in diagonal linear networks?

[1] Papazov, Hristo et al. “Leveraging Continuous Time to Understand Momentum When Training Diagonal Linear Networks.” International Conference on Artificial Intelligence and Statistics (2024).

2 comments

Thank you for pointing us to Papazov et al. (2024). Both papers study how heavy-ball momentum influences sparsity in diagonal linear networks. Their analysis concerns the solution selected at convergence, while ours concerns the iterations at which early stopping permits sparse recovery.

AspectPapazov et al. (2024)Our work
Research objectiveCharacterize which interpolating solution momentum selects at convergence and explain when the resulting implicit bias favors sparsity.Identify a finite interval of iterations in which early stopping achieves sparse recovery in the presence of observation noise, and analyze how depth and momentum affect this interval.
Model and settingTwo-layer diagonal linear network with predictor a⊙ba\odot b in overparameterized least squares.Depth-NN diagonal linear network with predictor uN−vNu^N-v^N in noisy sparse regression under a design incoherence condition. Our recovery theory focuses on N>2N > 2. At N=2N=2, the two predictor parameterizations are related by a=u+va=u+v and b=u−vb=u-v.
Analysis of MGD dynamicsExpress the original heavy-ball update as a finite-difference discretization of a second-order momentum gradient flow. In our notation, the flow parameter is λ=η/(1−μ)2\lambda=\eta/(1-\mu)^2 and the discretization step is η/(1−μ)\eta/(1-\mu) (Proposition 1).Use a first-order modified flow and a block-diagonal Gauss–Newton approximation to derive the one-step update in Eqs. (4)–(5). After factoring out the leading step ητ=η/(1−μ)\eta\tau=\eta/(1-\mu), the coefficient of the Gauss–Newton correction is η2γτ\eta^2\gamma\tau. This shows where the same step-size–momentum combination enters our modified update.
Proof techniqueAnalyze the evolution of weight balancedness and use a time-varying mirror flow to derive the optimality conditions that characterize the limiting solution. A separate discrete-time argument covers momentum SGD, including the full-batch case.Track the coordinates on and off the true support. Incoherence controls interactions between coordinates. The proof bounds how many iterations are needed for the signal coordinates to approach the target and how long the off-support coordinates remain small.
Main conclusionUnder the stated assumptions, the limiting predictor is a Bregman projection onto the set of interpolators. In the continuous-time analysis, sufficiently small positive λ\lambda reduces limiting balancedness, strengthening the bias toward sparse solutions (Theorem 1, Corollary 2, and Proposition 3). Theorem 2 gives the discrete counterpart under its own assumptions.Theorems 2 and 5 give coordinatewise recovery bounds for the modified iteration throughout a sufficient early-stopping window. Theorem 3 shows that, under its assumptions and with fixed parameter initialization and step size, a lower bound on the window width increases with depth.

We will add this comparison to the related-work section and clarify that our contribution is a finite-time recovery guarantee for the modified iteration in noisy sparse regression.

Furthermore, we fix the initialization to a constant α=0.0005\alpha=0.0005 for all cases, instead of using the depth-dependent scheme αN=αN\alpha_N=\alpha^N. The experimental results demonstrate that the trend of the early stopping window persists (see Figure 14 in Appendix M).

I thank the authors for their response. The experiment resolves my first concern, however the current manuscript remains rather dense which is also in line with the responses of the other reviewers. I will maintain my score.

Reviewer_9xAJOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper theoretically investigates the behavior and specifically the early stopping window for momentum gradient descent. The authors study deep linear diagonal networks with the square loss. They show that the early stopping window (more precisely some bounds for it) becomes larger with increased depth of the diagonal network and shorter as the momentum parameter increases. Additionally, the influence on the initialization scale is being investigated. The theoretical findings are confirmed by numerical experiments.

Critical strengths

The paper provides a theoretical analysis of momentum gradient descent for deep diagonal networks. It extends previous results for gradient descent to the setting that includes momentum. In particular, the influence of network depth and momentum on the size and location of the early stopping window is interesting, suggesting that momentum shortens the window but also moves it to an earlier position. Numerical experiments validate the theoretical claims, showing longer early stopping windows for deeper models and that momentum shortens the window and moves it toward earlier iterations.

Critical weaknesses

The authors consider a modification of the MGD iteration obtained by discretizing an ODE that is related to MGD. In Theorem 1 they state upper bounds for the distance between the two iterations. However, in the following, it remains unclear how the results that are obtained for the modified sequence translate to corresponding results for the "original" MGD iteration. Please clarify how the error from Theorem 1 propagates into the final results.

Some results in the appendix are stated in a simplified setting (e.g., Appendix C assumes a noiseless one-dimensional setup with 1nXTX=I\frac{1}{n}X^TX = I). Please explicitly clarify the setting for these auxiliary results, especially in the following sections. Additionally, in Theorem 1, the phrasing of the assumptions suggests that every component of the target vector θ⋆\theta^\star is supposed to be strictly positive (which appears to be a typo), making the relation to sparsity unclear. This should also be clarified.

Finally, the authors claim to prove that MGD with early stopping achieves minimax optimal sparse recovery. It is unclear to me how the presented results support this claim.

For visualization it might be beneficial if the plots with the early stopping windows had identical scales on the x-axis to visualize the effect of how depth and momentum shift the window (or at least identical scales for identical depth settings).

Questions for authors

Could the authors comment on the restrictiveness of the coherence assumption needed for Theorem 2? Do the matrices in the numerical examples satisfy this condition?

Is the early stopping window that is displayed in the figures determined by the theoretical findings or numerically from the experiments? If empirical, to what extent do the windows coincide with the theoretically derived bounds?

Can the same effects of depth and momentum on the early stopping window empirically also be observed for more complex networks than linear diagonal ones?

3 comments

Weakness

Thank you for these suggestions. We will clarify the scope of the auxiliary results and revise the recovery claim and figures.

Appendix C analyzes the scalar, single-branch M-MGD recurrence with a positive target and zero perturbation. The noiseless and identity-Gram conditions are used to derive this scalar recurrence. Appendix D introduces bounded perturbations and extends the scalar estimates to a uniform bound over the support. Appendix E treats the two-branch scalar recurrence for a signed target. Appendix F controls the effective perturbations under the incoherence assumption, and Appendices G and H assemble these bounds for the nonnegative and signed high-dimensional settings, respectively. We will state these assumptions at the start of each section and make explicit where the scalar estimates are invoked in the high-dimensional analysis.

The wording "all components are positive" at line 200 of the submitted manuscript is incorrect. Theorem 2 concerns a nonnegative sparse target. For S=support⁡(θ⋆)S=\operatorname{support}(\theta^\star) with ∣S∣=π|S|=\pi, the intended assumption is θi⋆>0\theta_i^\star>0 for i∈Si\in S and θi⋆=0\theta_i^\star=0 for i∉Si\notin S. Theorem 1 concerns trajectory approximation and has no target-positivity assumption.

We will use identical linear iteration-axis limits and ticks across momentum values at each fixed depth in Figures 3, 4, 8, and 9. We will retain the window markers so that the shifts and widths can be compared directly in iteration units.

Questions

The coherence condition in Theorem 2 is a conservative theoretical sufficient condition. The main simulations lie outside the sufficient conditions of Theorem 2. We will make this explicit in the experimental section.

In Figures 3 and 8, the scale αN/4\alpha^{N/4} is motivated by the theoretical off-support error bound. We will specify the endpoint extraction rule for each figure and distinguish the empirical endpoints from the theoretical bounds. The current experiments show qualitative trends. They do not quantify overlap with the guaranteed stopping interval under the theorem’s assumptions.

The present experiments use diagonal linear networks, including the MNIST image-recovery experiment. Whether the same effects persist in more complex architectures remains an empirical question.

I would like to thank the authors for their response. However, my concerns regarding the relevance of the results for the original iteration or how the claim of minimax optimality is supported by the results, remain unsolved. I will therefore maintain my initial score.

Thank you for clarifying the remaining concerns. We provide the recovery consequence for original MGD below. The complete discrete-time tracking proof appears in our response to the reviewer xVwA.

The transfer proof directly compares the original and modified recursions. Under the recovery hypotheses for M-MGD, a stopping window containing an integer iterate, and the additional tracking conditions, it gives ∣θk,iMGD−θi⋆∣≤Ei(k)+DT,DT=2NRN−1ηCT.|\theta_{k,i}^{\mathrm{MGD}}-\theta_i^\star|\leq \mathcal E_i(k)+D_T,\qquad D_T=2NR^{N-1}\eta C_T. Here Ei(k)\mathcal E_i(k) is the coordinatewise recovery bound for the modified iterate. The linked proof makes the dependence of RR and CTC_T on momentum, depth, initialization, and the time horizon explicit. For a prescribed coordinatewise error budget r>0r>0, the additional sufficient condition 2NRN−1ηCT≤r2NR^{N-1}\eta C_T\leq r controls the transfer error by rr. These conditions can be restrictive when the initialization-dependent horizon is large. Summing the squared coordinate bounds gives

∣∣θkMGD−θ⋆∣∣22≤2∑i=1pEi(k)2+2pDT2.||\theta_k^{\mathrm{MGD}}-\theta^\star||_2^2\leq2\sum _ {i=1}^{p}\mathcal E_i(k)^2+2pD_T^2.

Thus, if the modified recovery theorem establishes ∑iEi(k)2≤CBstat\sum_i\mathcal E_i(k)^2\leq C B_{\mathrm{stat}}, imposing

η≤cBstat/p2NRN−1CT\eta\leq\frac{\sqrt{cB_{\mathrm{stat}}/p}}{2NR^{N-1}C_T}

together with the other tracking conditions yields

∣∣θkMGD−θ⋆∣∣22≤2(C+c)Bstat.||\theta_k^{\mathrm{MGD}}-\theta^\star||_2^2\leq 2(C+c)B _ {\mathrm{stat}}.

This preserves the squared-error rate BstatB_{\mathrm{stat}}. An asymptotically negligible transfer contribution requires the stronger condition pDT2=o(Bstat)pD_T^2=o(B_{\mathrm{stat}}).

Regarding minimax optimality, the statistical specialization additionally requires an explicit bound on ∑iEi(k)2\sum_i\mathcal E_i(k)^2, including the initialization and finite-iteration contributions. We will present that calculation and qualify the optimality claim according to the resulting rate, design assumptions, and parameter range. The statement for original MGD will include the additional step-size condition above.

Our stopping guarantee concerns integer iterates within a sufficient recovery window whose endpoints depend on the problem parameters. It is an existence guarantee for an appropriate stopping time. We will make this scope explicit in the abstract, introduction, and recovery corollary.

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

This paper studies the implicit bias of momentum gradient descent in noisy linear regression using the depth-NN diagonal network θ=uN−vN\theta=u^N-v^N. The analysis relies on a modified discrete algorithm, M-MGD, obtained by forward Euler discretization of a modified ODE, together with Gauss–Newton and block-diagonal Hessian approximations. Theorem 1 claims an O(η)O(\eta) trajectory approximation between M-MGD and the original momentum algorithm. The subsequent results analyze sparse recovery and early-stopping windows for M-MGD and interpret these results in terms of the effects of depth and momentum. Numerical experiments validate the analysis.

Critical strengths

The paper addresses a relevant question: how momentum interacts with depth, initialization, and early stopping when solving a sparse regression with gradient methods. A rigorous finite-time recovery guarantee for actual momentum descent in the noisy, depth-N>2N>2 setting would be a useful extension of existing results.

Critical weaknesses
  • The recovery theorems analyze equations (4)–(5), which define the modified algorithm. Theorem 1 provides an O(η)O(\eta) approximation over a horizon K=O(1/η)K=O(1/\eta), but I could not find a quantitative argument showing that this error is negligible at the statistical accuracy and initialization-dependent stopping times required by the recovery results. In particular, the dependence of the approximation constant on momentum, depth, initialization, and the time horizon needs to be made explicit. I am not against to using continuous-time approximations in principle. However an explicit recovery corollary for original MGD, including any additional error terms and step-size conditions introduced by the approximation would add a lot.

  • Under suitable regularity and boundedness assumptions, vanilla GD with learning rate η/(1−μ)\eta/(1-\mu) is already O(η)O(\eta)-close to momentum with parameters (η,μ)(\eta,\mu). Therefore, Theorem 1 alone does not establish that the particular Gauss–Newton correction captures the leading finite-step effect of momentum more accurately than rescaled GD. The small-step correspondence with rescaled GD is also discussed in Papazov et al. (AISTATS 2024). In addition, a direct increase in optimization speed makes the early-stopping window both earlier and narrower when measured in iterations, without changing the optimization path. A comparison against GD with matched effective learning rate is therefore important. The stopping-window experiments instead fix the raw learning rate across momentum values.

  • Several theorem statements and proof steps require clarification or correction (see my questions below)

  • Vaskevicius et al. and Li et al. already establish optimal statistical recovery rates for related GD-based methods. Li et al. also study the effects of depth and small initialization on early stopping. Thus, the statistical rate and the depth-related phenomena are not new by themselves. A rigorous extension to actual momentum could nevertheless be meaningful; my concern is that this extension is not sufficiently justified, and the principal timing phenomenon is not clearly separated from known speed effects.

Questions for authors
  1. Could you provide a quantitative version of Theorem 1, including the dependence on T=KηT=K\eta, μ\mu, NN, and α\alpha. What additional conditions ensure that the resulting error is negligible relative to the claimed statistical recovery error and the off-support bound?Is it possible to obtain the resulting guarantee directly for the original MGD?

  2. In Appendix A, lines 732–735, boundedness of θ=uN−vN\theta=u^N-v^N is used to infer boundedness of uu and vv. This implication does not hold without an additional argument. How do you prove that?

  3. Theorems 2 uses minimum operators involving the noise level and ε\varepsilon. These expressions imply exact recovery on the support after finitely many iterations in the noiseless case. Are maximum operators intended instead? Similarly, should the separate initialization upper bounds be combined using a minimum rather than a maximum? Please explain how any corrections affect the subsequent results.

  4. At lines 257–258, why can the first initialization term, involving β(μ)\beta(\mu), be ignored when discussing the effect of momentum? Being bounded above does not establish that it is inactive among the simultaneous initialization constraints. Or am I missing something?

  5. Is it clear under the stated assumptions, that K1+K3≤K2+K4K_1+K_3\le K_2+K_4 and that the interval contains an integer stopping time? Could you keep the dependence on β/τ\beta/\tau when you compare the endpoints?

  6. In Lemma 10, should θmax⁡⋆\theta_{\max}^\star in the iteration lower bound be replaced by θmin⁡⋆\theta_{\min}^\star? The largest coordinate does not seem appropriate for controlling the convergence time of every coordinate. How does the corrected statement connect to the subsequent expressions?

  7. In Theorem 4, does the theorem establish that Kup−KlowK_{\mathrm{up}}-K_{\mathrm{low}} decreases, or only that a particular lower bound decreases? The main theorem is different from the one in the appendix. Furthermore, if c(μ)c(\mu) at line 2304 denotes β(μ)\beta(\mu), how do you prove its monotonicity? Positivity of the denominator alone is not sufficient. Is the range compatible with the learning-rate and initialization assumptions?

  8. Could you state the squared-ℓ2\ell_2 recovery guarantee explicitly and distinguish estimation-rate optimality from sample-complexity optimality? With κ=θmax⁡⋆/θmin⁡⋆\kappa=\theta_{\max}^\star/\theta_{\min}^\star, the coherence assumption σ≲1/(πκ)\sigma\lesssim1/(\pi\kappa) appears to yield the sufficient scaling $n\gtrsim\pi^2 \kappa^2\log p $ for independent normalized Gaussian, rather than the optimal $ \kappa \log p$ scaling. Is this the intended interpretation, or is there a sharper design argument?

  9. In Lemma 1, what does “for a sufficiently large iteration kk” mean quantitatively, and how does it depend on η\eta and μ\mu? Do you use it in your analysis?

5 comments

We thank the reviewer for their careful reading of our manuscript and constructive feedback. Regarding Weakness 1, Weakness 2, and Question 1, the formal revisions have been made in the revised PDF. Please refer to the text highlighted in blue. We provide our point-by-point responses below.

Weakness 1 and Question 1

Let wkw_k and wˉk\bar w_k denote the original and modified MGD iterates, respectively, with the same initialization and h0=0h_0=0. Set τ=(1−μ)−1\tau=(1-\mu)^{-1} and γ=(1+μ)/[2(1−μ)3]\gamma=(1+\mu)/[2(1-\mu)^3]. Take T≥ηKupT\ge\eta K _ {\mathrm{up}}. In particular, under the recovery hypotheses, Eq. (19) and β≥1\beta\ge1 give the following step-size-independent choice for 0<α<10<\alpha<1: T=20α−(N−2)N(N−1)ζ+100α−(N−2)/2N(N−1)θmin⁡∗.T=\frac{20\alpha^{-(N-2)}}{N(N-1)\zeta}+\frac{100\alpha^{-(N-2)/2}}{N(N-1)\theta_{\min}^{\ast}}. Let a=∣∣X⊤X/n∣∣∞a=||X^\top X/n|| _ {\infty}, b=∣∣X⊤y/n∣∣∞b=||X^\top y/n|| _ \infty. Define ΩR=[(u,v):∣∣u∣∣∞≤R,∣∣v∣∣∞≤R],\Omega _ R =[(u, v) : ||u|| _ \infty \leq R, ||v||_\infty \leq R], where R=α+2τTL0+1,L0=L(w0).R = \alpha + 2\sqrt{\tau T L_0} + 1, L_0 = L(w_0). The block-diagonal Gauss--Newton matrix used in Eqs. (4)-(5) is B(w)=N2diag(DuADu, DvADv),B(w)=N^2\mathrm{diag}(D_u A D_u,\,D_v A D_v), where diag\mathrm{diag} of two matrices forms a block-diagonal matrix. Define Q=2aRN+b,  G0=NαN−1b,  G=NRN−1Q,  M=N2aR2N−2,  H=2M+N(N−1)RN−2Q.Q = 2aR^N+b, ~~ G_0 = N\alpha^{N-1}b,~~G = NR^{N-1}Q, ~~ M = N^2aR^{2N-2}, ~~ H = 2M+N(N-1)R^{N-2}Q. To see that these are the required bounds, write q(w)=A(uN−vN)−X⊤y/nq(w)=A(u^N-v^N)-X^\top y/n. On ΩR\Omega_R, ∣∣q(w)∣∣∞≤Q||q(w)|| _ \infty\leq Q and ∇L(w)=N(Duq(w),−Dvq(w))\nabla L(w)=N(D_uq(w),-D_vq(w)), so that ∣∣∇L(w)∣∣∞≤G||\nabla L(w)|| _ \infty\leq G and ∣∣∇L(w0)∣∣∞=G0||\nabla L(w_0)|| _ \infty=G_0. The definition of B(w)B(w) gives ∣∣B(w)∣∣∞≤M||B(w)|| _ {\infty}\leq M. Write J=[Du,−Dv]J=[D_u,-D_v]. The full Hessian has a Gauss--Newton term ∣∣N2J⊤AJ∣∣∞≤2M||N^2 J^\top A J|| _ \infty\leq 2M, and a diagonal residual term with norm at most N(N−1)RN−2QN(N-1)R^{N-2}Q. Hence ∣∣∇2L(w)∣∣∞≤H||\nabla^2 L(w)|| _ {\infty}\leq H. Let CT=eτHT[μτ2G0+TG(μτ3H+γM)].C_T=e^{\tau HT}\bigl[\mu\tau^2G_0+TG(\mu\tau^3H+\gamma M)\bigr].

Lemma A. Assume ηγM≤τ, 2ητmax⁡{G,H}≤1.\eta\gamma M\leq\tau, ~ 2\eta\tau\max\{G,H\}\leq1. Then the modified MGD iterates satisfy ∣∣wˉk∣∣∞≤R−1||\bar{w} _ k|| _ \infty\leq R-1 for all kη≤Tk\eta\leq T. For every kk with (k+1)η≤T(k+1)\eta\leq T, L(wˉk+1)≤L(wˉk)−∣∣wˉk+1−wˉk∣∣224ητ.L(\bar w_{k+1})\leq L(\bar{w}_k)-\frac{||\bar{w} _ {k+1}-\bar{w}_k||_2^2}{4\eta\tau}. Proof. Denote the modified MGD increment by sk=wˉk+1−wˉk=−Pk∇L(wˉk),Pk=ητI+η2γB(wˉk).s_k=\bar{w} _ {k+1}-\bar{w}_k=-P_k\nabla L(\bar{w}_k),\qquad P_k=\eta\tau I+\eta^2\gamma B(\bar{w}_k). For wˉk∈ΩR\bar w_k\in\Omega_R, ητI⪯Pk⪯2ητI\eta\tau I\preceq P_k\preceq2\eta\tau I. Indeed, B(wˉk)B(\bar w_k) is symmetric positive semidefinite, and the spectral norm of a symmetric matrix is bounded by its induced infinity norm. The same norm comparison shows that HH bounds the Hessian spectral norm on ΩR\Omega_R.

The initial point satisfies ∣∣wˉ0∣∣∞=α≤R−1||\bar{w}_0|| _ \infty=\alpha\leq R-1. Suppose the claim holds through iteration kk with (k+1)η≤T(k+1)\eta\leq T. Since ∣∣sk∣∣∞≤2ητG≤1||s_k|| _ \infty\leq2\eta\tau G\leq1, the segment from wˉk\bar{w} _ k to wˉk+1\bar{w} _ {k+1} lies in ΩR\Omega_R. Taylor's inequality on this segment gives L(wˉk+1)−L(wˉk)≤⟨∇L(wˉk),sk⟩+H2∣∣sk∣∣22=−sk⊤Pk−1sk+H2∣∣sk∣∣22≤−(12ητ−H2)∣∣sk∣∣22≤−∣∣sk∣∣224ητ.L(\bar{w} _ {k+1})-L(\bar{w}_k)\leq \langle\nabla L(\bar{w}_k),s_k\rangle+\frac{H}{2}||s_k||_2^2=-s_k^\top P_k^{-1}s_k+\frac{H}{2}||s_k||_2^2\leq-\left(\frac{1}{2\eta\tau}-\frac{H}{2}\right)||s_k||_2^2\leq-\frac{||s_k||_2^2}{4\eta\tau}.

By Cauchy--Schwarz, ∣∣wˉk+1−wˉ0∣∣∞≤∑j=0k∣∣sj∣∣2≤k+1(∑j=0k∣∣sj∣∣22)1/2≤2(k+1)ητL0≤2τTL0.||\bar{w} _ {k+1}-\bar{w}_0|| _ \infty\leq \sum _ {j=0}^k||s_j||_2\leq\sqrt{k+1}\left(\sum _ {j=0}^k||s_j||_2^2\right)^{1/2}\leq2\sqrt{(k+1)\eta\tau L_0}\leq 2\sqrt{\tau T L_0}.

Thus ∣∣wˉk+1∣∣∞≤R−1||\bar{w} _ {k+1}|| _ \infty\leq R-1, closing the induction. $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$ $ \square$

Let dk=∣∣wk−wˉk∣∣∞d_k=||w_k-\bar{w}_k|| _ \infty and gj=∇L(wj)g_j=\nabla L(w_j). Subtracting the modified update from the original one yields wk+1−wˉk+1=wk−wˉk+(hk+1+ητgk)+ητ(∇L(wˉk)−gk)+η2γB(wˉk)∇L(wˉk).w _ {k+1}-\bar{w} _ {k+1}=w_k-\bar{w}_k+(h _ {k+1}+\eta\tau g_k)+\eta\tau\bigl(\nabla L(\bar{w}_k)-g_k\bigr)+\eta^2\gamma B(\bar{w}_k)\nabla L(\bar{w}_k).

By h0=0h_0=0, hk+1=−η∑j=0kμk−jgjh_{k+1}=-\eta\sum_{j=0}^k\mu^{k-j}g_j. Writing gj=g0+∑ℓ=1j(gℓ−gℓ−1)g_j=g_0+\sum_{\ell=1}^j(g_\ell-g_{\ell-1}) and summing the geometric weights gives the identity hk+1+ητgk=ητμk+1g0+ητ∑j=1kμk−j+1(gj−gj−1).h_{k+1}+\eta\tau g_k=\eta\tau\mu^{k+1}g_0+\eta\tau\sum_{j=1}^k\mu^{k-j+1}(g_j-g_{j-1}). Assume for this step that w0,…,wk∈ΩRw_0,\ldots,w_k\in\Omega_R. For 1≤j≤k1\leq j\leq k, convexity of ΩR\Omega_R gives ∣∣gj−gj−1∣∣∞≤H∣∣hj∣∣∞≤HητG,∣∣hj∣∣∞≤η∑ℓ=0j−1μj−1−ℓ∣∣gℓ∣∣∞≤ητG.||g_j-g_{j-1}|| _ \infty\leq H||h_j|| _ \infty\leq H\eta\tau G,\qquad||h_j|| _ \infty\leq\eta\sum_{\ell=0}^{j-1}\mu^{j-1-\ell}||g_\ell|| _ \infty\leq\eta\tau G. Using ∑j=1kμk−j+1≤μτ\sum _ {j=1}^k\mu^{k-j+1}\leq\mu\tau, we obtain ∣∣hk+1+ητgk∣∣∞≤ητμk+1G0+η2μτ3HG.||h_{k+1}+\eta\tau g_k|| _ \infty\leq\eta\tau\mu^{k+1}G_0+\eta^2\mu\tau^3HG. Also ∣∣∇L(wˉk)−gk∣∣∞≤Hdk||\nabla L(\bar w_k)-g_k|| _ \infty\leq Hd_k and ∣∣B(wˉk)∇L(wˉk)∣∣∞≤MG||B(\bar w_k)\nabla L(\bar w_k)|| _ \infty\leq MG. Therefore dk+1≤(1+ητH)dk+ϵk,ϵk=ητμk+1G0+η2G(μτ3H+γM),d0=0.d_{k+1}\leq (1+\eta\tau H)d_k+\epsilon_k,\qquad\epsilon_k=\eta\tau\mu^{k+1}G_0+\eta^2 G(\mu\tau^3H+\gamma M),\qquad d_0=0. (Due to space/character constraints, the continuation follows in the subsequent response box.)

I thank the authors for their reply. After reading the other reviews, I have decided to maintain my overall rating.

(Continued from the above response)

Unrolling the recurrence over valid steps gives, for kη≤Tk\eta\leq T,

\eta\tau G_0\sum_{j=0}^{k-1}\mu^{j+1}+k\eta^2G(\mu\tau^3H+\gamma M)\right]\leq \eta e^{\tau HT}\bigl[\mu\tau^2G_0+TG(\mu\tau^3H+\gamma M)\bigr]=\eta C_T.$$ If $\eta C_T\leq1$, this argument applies throughout the horizon. The initial point is in $\Omega_R$. If the original iterates are in $\Omega_R$ through $k$, and $(k+1)\eta\leq T$, the recurrence and its unrolled bound give $d_{k+1}\leq1$. **Lemma A** then yields $$||w_{k+1}|| _ \infty\leq||\bar{w} _ {k+1}|| _ \infty+d_{k+1}\leq (R-1)+1=R.$$ Thus $d_k\leq\eta C_T$ holds for every integer $k$ with $k\eta\leq T$. Let $\theta_k^{\mathrm{MGD}}=u_k^N-v_k^N$ and $\theta_k^{\mathrm{M\text{-}MGD}}=\bar u_k^N-\bar v_k^N$. For $x, z\in[-R,R]$, we know that $|x^N-z^N|\leq NR^{N-1}|x-z|$. Applying this to both branches gives $$|\theta_{k,i}^{\mathrm{MGD}}-\theta_{k,i}^{\mathrm{M\text{-}MGD}}|\leq NR^{N-1}\bigl( |u_{k,i}-\bar u_{k,i}|+|v_{k,i}-\bar v_{k,i}|\bigr)\leq 2NR^{N-1}d_k.$$ Consequently, for all $k\eta\leq T$, $$\|\theta_k^{\mathrm{MGD}}-\theta_k^{\mathrm{M\text{-}MGD}}\|_\infty \leq 2NR^{N-1}\eta C_T=:D_T.$$ **Corollary.** Assume the hypotheses of the nonzero-signal case of Theorem 5 for the modified iteration (4)--(5). In addition, assume $\eta\gamma M\leq\tau, 2\eta\tau\max\{G,H\}\leq1.$ and $\eta C_T\leq1$. Let $\mathcal E_i(k)$ denote a valid coordinatewise error bound from Theorem 5, including its multiplicative constant. Then for every $k\in[K_{\mathrm{low}},K_{\mathrm{up}}]$ and every coordinate $i$, $$|\theta_{k,i}^{\mathrm{MGD}}-\theta_i^\ast|\leq \mathcal E_i(k)+D_T.$$ For a per-coordinate transfer budget $r>0$, the additional condition $2NR^{N-1}\eta C_T\leq r$. In particular, $r\leq\min[\varepsilon,\alpha^{N/4}]$ preserves the $O(\varepsilon)$ on-support bound and the $O(\alpha^{N/4})$ off-support bound. A smaller coordinatewise noise scale in $\mathcal E_i(k)$ requires a correspondingly smaller transfer budget to preserve that scale. The added $\ell_2$ error is at most $\sqrt p\,D_T$, so $r\leq r_{\mathrm{stat}}/\sqrt p$ controls the transfer at the $\ell_2$ scale $r_{\mathrm{stat}}$. **Proof.** Apply the predictor bound at each $k$ in the recovery window, which satisfies $k\eta\leq T$, and use the triangle inequality with the corresponding bound for the modified iterate. For the $\ell_2$ statement, use $||z||_2\leq\sqrt p, ||z|| _ \infty$ for $z\in\mathbb R^p$. The additional step-size conditions are sufficient. To make the transfer error asymptotically negligible at a prescribed $\ell_2$ statistical scale, one may impose $\sqrt p\,D_T=o(r_{\mathrm{stat}})$. The factor $e^{\tau HT}$ can make the sufficient step size restrictive when the initialization is small. **Weakness 2** Please refer to our newly added content in Appendix M. **Question 2** Boundedness of $u_k^N-v_k^N$ does not imply boundedness of the two parameter branches. Both one-step maps compared in Appendix A can be written as $w _ {k+1}=w_k-P_k\nabla L(w_k)$, with $P_k=\eta\tau I+\eta^2\gamma B(w_k)$, where $B$ is the symmetric Hessian or block-diagonal Gauss--Newton matrix used by the corresponding map. Set $L_0=L(w_0)$ and $R=\alpha+2\sqrt{\tau T L_0}+1$. On the box $||w|| _ \infty\le R$, let $G,H,M$ bound the gradient, Hessian, and both choices of $B$, respectively, using the infinity norm for vectors and its induced matrix norm. These bounds are finite by smoothness on a compact set. Assume $\eta\gamma M\le\tau/2$ and $2\eta\tau\max\{G,H\}\le1$. Then $P_k$ is positive definite, with spectral norm at most $2\eta\tau$. Starting from $||w_0|| _ \infty=\alpha$, suppose $||w_k|| _ \infty\le R-1$. The next increment $\Delta_k=w_{k+1}-w_k$ has infinity norm at most $2\eta\tau G\le1$, so the entire update segment lies in the box. Taylor's inequality on that segment gives $$L(w _ {k+1})-L(w_k)\le -\Delta_k^\top P_k^{-1}\Delta_k+\frac{H}{2}||\Delta_k||_2^2\le -\frac{||\Delta_k||_2^2}{4\eta\tau}.$$ Summing this inequality and using $L\ge0$ gives $\sum_{j<k}||\Delta_j||_2^2\le4\eta\tau L_0$. Thus, for $k\eta\le T$, Cauchy--Schwarz gives $||w_k-w_0|| _ \infty\le2\sqrt{\tau T L_0}$, maintaining $||w_k|| _ \infty\le R-1$ by induction. This establishes a common compact set for both trajectories before we use the Jacobian bound. **Question 3** In the noiseless setting, if the data matrix satisfies certain conditions (e.g., the restricted null space property), exact sparse recovery can be achieved. **Question 4** I will take $\beta(\mu)$ into consideration. It is worth noting that when the momentum $\mu$ is relatively large,$\beta(\mu)$increases as $\mu$ increases. **Question 5** The theoretical analysis do not guarantee that the interval contains an integer stopping time. We will consider this issue in the future.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.