acceptodds
Under review as a conference paper at ICLR 2027

Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimization

Abstract

We propose \sf ALFPG, an Adaptive Lipschitz-Free Proximal Gradient framework for stochastic composite nonconvex minimization. The framework adapts its stepsizes using information collected along the optimization trajectory, without requiring prior knowledge of smoothness constants or performing line search. For finite-sum problems, ALFPG-FS combines coordinate-wise stepsizes, Nesterov's extrapolation, and the SPIDER estimator, with ALFPG-D as its full-batch specialization. Under component-wise smoothness and a bounded effective domain, ALFPG-FS achieves -stationarity in expectation using component-gradient evaluations. For expectation problems, we develop ALFPG-MVR1 and \sf ALFPG-MVR2, where MVR stands for momentum-based variance reduction. Both use one fresh sample per iteration: ALFPG-MVR1 uses one stochastic-gradient evaluation, whereas \sf ALFPG-MVR2 uses at most two evaluations at different points with the same sample. ALFPG-MVR1 requires smoothness of the expected loss; \sf ALFPG-MVR2 additionally requires uniformly smooth sample losses. When the regularizer is convex or Lipschitz continuous on its effective domain, and stochastic gradients are almost surely bounded, the two methods achieve -stationarity in expectation using and stochastic-gradient evaluations, respectively. Here, is the number of component functions, bounds the gradient noise variance, and hides logarithmic factors. Neither expectation variant requires prior knowledge of , and both recover complexity in the zero-noise regime.

Primary area:
optimization
Keywords:
Nonconvex composite optimization, stochastic optimization, adaptive proximal gradient methods, Lipschitz-free optimization, variance reduction, noise-adaptive convergence

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_eB7GOpenReview ↗
Rating
3(+1)
Confidence
1(−1)
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes a family of algorithms, so-called ALFPG, an adaptive proximal gradient methods for stochastic composite nonconvex optimization that require neither prior knowledge of smoothness constants nor line search. The finite-sum variant (ALFPG-FS) combines displacement-based diagonal scaling, metric-dependent extrapolation, and SPIDER estimation, achieving O(N+Nϵ−2)O(N+\sqrt{N}\epsilon^{-2}) gradient complexity. Two expectation variants (ALFPG-MVR1/MVR2) combine adaptive momentum with proximal-residual normalization and achieve noise-dependent complexities of O~(ϵ−2+σ2ϵ−4)\widetilde O(\epsilon^{-2}+\sigma^2\epsilon^{-4}) and O~(ϵ−2+σϵ−3)\widetilde O(\epsilon^{-2}+\sigma\epsilon^{-3}), respectively, under their stated assumptions. The paper provides detailed convergence analyses using a subdifferential stationarity criterion.

Critical strengths
  1. Motivation of ALFPG-algorithm is clear and good. Removing smoothness-dependent tuning and line search is relevant to stochastic composite optimization. Using proximal displacements to construct adaptive stepsizes incorporates the effect of the regularizer into the adaptation mechanism.
  2. Comparison with AdaGrad-Norm is informative. In several subsections, the authors connect ALFPG displacement-based adaptation to AdaGrad-Norm through a smooth scalar-metric special case, carefully explaining the difference in denominator-update order. This comparison helps readers understand the adaptive normalization mechanism underlying AdaGrad-Norm and how related ideas can extend to composite optimization through proximal displacements. Such a connection provides useful conceptual insight beyond the convergence guarantees.
  3. Detailed theoretical analysis of ALFPG. The paper develops detailed convergence analyses for both finite-sum and expectation problems, addressing the interaction among adaptive stepsizes, gradient-estimation errors, extrapolation, and proximal updates. Both expectation variants use one fresh sample per iteration and achieve noise-adaptive complexity bounds that explicitly reflect the noise magnitude, recovering a O~(ϵ−2)\widetilde O(\epsilon^{-2}) bound in the zero-noise regime.
Critical weaknesses

The critical weakness include:

  1. The notation and presentation make the manuscript difficult to follow. The reuse of symbols for different roles across settings, frequent boldface emphasis, and numerous remarks obscure the main idea presentation. Algorithm 2, for example, introduces several coupled adaptive quantities, including ρt,αt,βt,\rho_t,\alpha_t,\beta_t, and γt\gamma_t, whose relationships require considerable effort to track. Although individual definitions and explanations are provided, the presentation offers insufficient guidance on their relative importance. More consistent notation, selective emphasis, and integration of essential remarks into the main narrative would substantially improve readability.

  2. The convergence analysis needs a clearer conceptual hierarchy. Although ALFPG-FS, ALFPG-MVR1, and ALFPG-MVR2 share a similar adaptive proximal backbone, their convergence guarantees rely on different update mechanisms and assumptions. The existing organization does not sufficiently explain how these differences arise from the distinct challenges of finite-sum and expectation problems. The authors should first identify the main obstacle in each setting, then explain the corresponding algorithmic modification, the assumptions needed to analyze it, and the resulting guarantee. Within the expectation setting, the additional requirements and improved complexity of MVR2 relative to MVR1 should be explained explicitly. This structural presentation would help readers understand the common analytical structure and the setting-specific arguments. The breadth and technical depth of the work may also benefit from an expanded treatment in an optimization journal, where they typically have more space to present the full narrative.

  3. Lack of empirical validation. Even modest experiments on regression and classification problems would help establish the practical value of the proposed framework. At a minimum, the authors should compare with AdaGrad-Norm, reporting convergence curves or the number of gradient evaluations. Such results would help readers understand the algorithm and justify whether the proposed adaptation mechanisms improve convergence behavior.

Questions for authors

See the weakness section above. All weaknesses should be addressed before the manuscript is ready for acceptance.

4 comments

Thank you for the concrete suggestions on notation, proof organization, and empirical validation.


Q1. The notation and presentation make the manuscript difficult to follow.

Response. Thank you for pointing out that Algorithm 2 is difficult to follow. Section 3.2 now explains the update in the order in which its quantities are used. The statistic ρt\rho_t summarizes the history of gradient discrepancies. Its lagged value αt=ρt−1\alpha_t=\rho_{t-1} sets the current momentum weight. The factor βt\beta_t uses past proximal residuals to normalize the stepsize, and γt=θβtαtλ\gamma_t=\theta\beta_t\alpha_t^\lambda combines these two effects. Thus, the current momentum weight and stepsize are determined before the fresh sample is drawn. We will place this explanation immediately after Algorithm 2, distinguish the notation reused across settings, and fold the essential remarks into the main text.


Q2. The convergence analysis needs a clearer conceptual hierarchy.

Response. We will first present the common argument. Proximal optimality bounds the stationarity residual at the output iterate in terms of the iterate displacement and the gradient-estimation error. The three analyses differ in how they control these quantities.

  • ALFPG-FS. The main difficulty is controlling the SPIDER error as the diagonal metric and extrapolation evolve. Component-wise smoothness links the estimator error to the motion of the extrapolated iterates. Under the stated assumptions, including separate lower bounds on ff and hh, Theorem 4.6 controls the stationarity constant uniformly over refresh periods and batch sizes satisfying (q−1)/b≤1(q-1)/b\leq 1. This gives the O(N+Nϵ−2)\mathcal O(N+\sqrt N \epsilon^{-2}) gradient oracle bound.
  • ALFPG-MVR1. The estimator uses one gradient evaluation per iteration. Its discrepancy statistic reflects both sampling variation and iterate motion. The analysis controls the latter using smoothness of the expected loss and gives a O~(ϵ−2+σ2ϵ−4)\widetilde{\mathcal O}(\epsilon^{-2}+\sigma^2\epsilon^{-4}) oracle bound under the shared expectation-setting assumptions.
  • ALFPG-MVR2. The estimator uses up to two gradient evaluations with the same fresh sample to correct for iterate motion. The discrepancy statistic compares gradients from successive samples at the same point, so it measures sampling variation at that point. The analysis uses uniform sample-wise smoothness to control the correction and obtains a O~(ϵ−2+σϵ−3)\widetilde{\mathcal O}(\epsilon^{-2}+\sigma\epsilon^{-3}) oracle bound.

This organization will make explicit what the two expectation variants share and how MVR2 uses an additional gradient evaluation and stronger smoothness to improve the noise-dependent term.


Q3. Lack of empirical validation.

Response. The revision adds 12 figures covering sparse phase retrieval, linear eigenvalue problems, and neural network regression. Numerical experiments show that the four variants of ALFPG generally outperform state-of-the-art proximal gradient baselines.

Reviewer_eB7GOpenReview ↗

Thanks for your rebuttal

I would like to thank the authors for their rebuttal. I have no further questions. When I read the experiments section, I noticed it still lacks comparisons with Adagrad. Additionally, I still think the presentation of the main algorithms should undergo a major revision. At this stage, I have to maintain my original evaluation. Reviewers and ACs who have disagreements on my review can reply to my review so that I will re-evaluate the paper comprehensively.

AuthorsOpenReview ↗

Thank you for your reply

Thank you for the follow-up. We have made further revisions addressing the AdaGrad comparison and the presentation of the algorithms and convergence analysis.

1. Added comparison with AdaGrad-Norm. Our initial comparisons prioritized methods that explicitly handle regularizers or constraints. The original AdaGrad-Norm formulation targets smooth unconstrained optimization, whereas all three applications in our experiments involve regularization or explicit constraints.

Following your suggestion, we have added Prox-AdaGrad-Norm, which combines the scalar stepsize of AdaGrad-Norm with a proximal update for h. This allows comparison on the same composite objective while retaining gradient-norm accumulation. The comparisons cover sparse phase retrieval, linear eigenvalue problems, and neural network regression in the expectation setting. The baseline is described in Section 6, with results in Appendix D.5, Figures 7–12.

2. Clarified the algorithmic mechanisms and proof structure. Sections 3.1–3.2 now explain the algorithm design and its relationship to existing methods. For Algorithm 2, we clarify the distinct roles of the gradient-discrepancy statistic, the averaging coefficient α_t = ρ_{t−1}, the proximal-residual factor β_t, and the stepsize γ_t = θβ_t α_t^λ. We also explain gradient reuse and why the averaging coefficient and stepsize are determined before drawing the current sample.

We have rewritten the proof overviews in Appendices B.1–B.2 and C.1–C.2. Each overview now starts from a core descent inequality and presents numbered steps connecting it to the stationarity guarantee, with references to the supporting lemmas. These steps distinguish SPIDER error control in the finite-sum setting from tracking-error and moment estimates in the expectation setting. They also explain how inverse-weight bounds produce the different noise-dependent rates of MVR1 and MVR2. Sections 5.1–5.2 explicitly state the additional uniform sample-wise smoothness assumption required by MVR2.

For ease of review, the revisions described above are highlighted in dark red in the revised manuscript. We would appreciate your reconsideration in light of these additional revisions.

Reviewer_eB7GOpenReview ↗

Thanks for your rebuttal

Thanks authors, for your tremendous effort working on this rebuttal. I increased my score, but I have to lower my confidence. My biggest concern is not around the experiments and theory themselves. It is actually about presentation. I think the overall narrative is still very chaotic. This might be caused by the ICLR page limit. Nine pages cannot fully accommodate so many comparisons. Different algorithms correspond to different assumptions. I still think the author should consider submitting this manuscript to a Journal, such as SIAM Journal on Optimization, etc. Anyway, wish you all the best of luck with submissions.

AC can ignore my evaluation and make an independent judgment

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

The paper studies stochastic composite nonconvex optimization of F=f+h with a possibly nonsmooth regularizer. It proposes four methods requiring neither a smoothness constant as input nor line search: ALFPG-D, ALFPG-FS, ALFPG-MVR1, and ALFPG-MVR2. The finite-sum methods combine a displacement-based diagonal metric, metric-coupled extrapolation, and SPIDER estimation, obtaining O(Nϵ−2)O(N \epsilon^{-2}) and$ O(N+\sqrt{N} \epsilon^{-2})$ gradient complexities under bounded effective domains, component smoothness, and exact global proximal computation. The expectation methods combine an EMA or same-sample recursive estimator with gradient-discrepancy statistics and proximal-residual normalization. Under bounded stochastic gradients and the stated additional conditions, their complexities are O~(ϵ−2+σ2ϵ−4)\tilde O(\epsilon^{-2}+\sigma^2 \epsilon^{-4}) and O~(ϵ−2+σϵ−3)\tilde O(\epsilon^{-2}+\sigma \epsilon^{-3}). Stationarity is measured by the limiting-subdifferential residual at a proximal output. But there is no numerical experiments.

Critical strengths

The paper provides smoothness-oblivious adaptation in meaningful composite settings. It integrates a diagonal displacement metric, extrapolation, SPIDER, and potentially nonconvex regularization in one finite-sum analysis. Its expectation methods directly control dist(0,∇f+∂h)dist(0,\nabla f+\partial h), avoid accuracy-dependent large initialization batches under the stated regularizer assumptions, and recover the noiseless order without changing the update rule.

Critical weaknesses

Positioning and comparisons need sharpening. The complexity orders have precedents in SPGR, AdaSPIDER, STORM+, and ProxHSGD, which the authors largely acknowledge. Comparisons should additionally include AdaPGNC [1] and OptEMA [2] and isolate the gain under matched regularizers, oracle conditions, and stationarity criteria. The bounded effective domain, globally bounded stochastic oracle, and exact global proximal computation restrict the scope. A checkmark for smoothness-oblivious tuning alone does not establish overall dominance. Moreover, the cited ProxGen complexity uses batch size Θ(ϵ−2)\Theta(\epsilon^{-2}), not O(ϵ−1)O(\epsilon^{-1}) as listed in Table 2. The four algorithms are not validated empirically or through worked implementations. Assumption 5.2 is relatively strong, as far as I know, some work based on the Storm algorithm can also achieve optimal complexity without this assumption. Can it be removed? The description of the algorithm is not detailed enough and not clear enough. For example, does min⁡(vt÷vt+1)\min(v_t \div v_{t+1}) mean taking the smallest component value?

[1] Ye Z, Ma S, Yang J, et al. A simple adaptive proximal gradient method for nonconvex optimization. arXiv preprint arXiv:2510.06079, 2025. [2] Yuan G. OptEMA: Adaptive Exponential Moving Average for Stochastic Optimization with Zero-Noise Optimality. arXiv preprint arXiv:2603.09923, 2026.

Questions for authors

[1]Table 2 lists ProxGen's batch size as O(ϵ−1)O(\epsilon^{-1}) alongside O(ϵ−4)O(\epsilon^{-4}) total complexity, please check it.

[2] Table 2 overlooks the result that the PStorm algorithm can achieve a log-free O(ϵ−3)O(\epsilon^{-3}) complexity with a constant step size and a constant initial batch size.

[3] Assumption 5.2 is relatively strong, can it be removed?

[4] Can the authors give a concrete global proximal calculation for Algorithm 1 with a representative nonconvex, non-Lipschitz regularizer and a general diagonal metric, explaining how the bounded-domain constraint preserves tractability?

[5] Could the authors provide experimental results to support the theory?

2 comments

Thank you for reading our manuscript carefully and for your encouraging feedback.


Q1. Comparisons should additionally include AdaPGNC [1] and OptEMA [2] and isolate the gain under matched regularizers, oracle conditions, and stationarity criteria.

Response. We have added AdaPGNC to Table 1, OptEMA to Table 2, and both comparisons to Section 2.

  • Deterministic setting. With convex hh and full gradients, AdaPGNC and ALFPG-D both attain an ϵ\epsilon-small subdifferential residual at a proximal iterate in O(ϵ−2)\mathcal O(\epsilon^{-2}) iterations under their respective assumptions. For AdaPGNC, this follows from its proximal-gradient mapping bound. ALFPG-D also allows a possibly nonconvex hh.

  • Stochastic setting. For h≡0h\equiv0, OptEMA and ALFPG-MVR1 both use one stochastic gradient per iteration and attain O~(ϵ−2+σ2ϵ−4)\widetilde{\mathcal O}(\epsilon^{-2}+\sigma^2\epsilon^{-4}) gradient oracle complexity for the expected gradient norm under their shared assumptions. MVR1 extends this order to the expected composite stationarity residual by coupling discrepancy-based momentum with proximal-residual normalization. With uniform sample-wise smoothness, MVR2 attains O~(ϵ−2+σϵ−3)\widetilde{\mathcal O}(\epsilon^{-2}+\sigma\epsilon^{-3}) using up to two gradient evaluations on the same fresh sample.


Q2. The bounded effective domain, globally bounded stochastic oracle, and exact global proximal computation restrict the scope. A checkmark for smoothness-oblivious tuning alone does not establish overall dominance.

Response. Revised Assumption 4.1 requires bounded sublevel sets of FF, which permits an unbounded effective domain. For a fixed refresh period, Lemma B.4 establishes a uniform upper bound on the objective values along the trajectory, placing the iterates in a single compact sublevel set. The expectation results retain Assumption 5.2, and all variants require exact global solutions of their respective proximal subproblems. The checkmark in the tables refers specifically to stepsize selection without prior knowledge of the smoothness constant. We will make this interpretation explicit alongside the assumptions for each guarantee.


Q3. ProxGen complexity uses batch size \Theta(\epsilon^{-2}), not \Theta(\epsilon^{-1}) as listed in Table 2.

Response. The reviewer is correct. Corollary 1 of Yun et al. takes a constant batch size b=Θ(T)b=\Theta(T) and bounds the expected squared stationarity residual by O(1/T)\mathcal O(1/T). Taking T=Θ(ϵ−2)T=\Theta(\epsilon^{-2}) gives b=Θ(ϵ−2)b=\Theta(\epsilon^{-2}) and O(ϵ−4)\mathcal O(\epsilon^{-4}) total gradient evaluations. We will correct the batch-size entry in Table 2. Yun et al., Corollary 1


Q4. The four algorithms are not validated empirically

Response. Section 6 and Appendix D now report results on sparse phase retrieval, linear eigenvalue problems, and neural network regression.


Q5. Assumption 5.2 is relatively strong .. Can it be removed?

Response. We retain Assumption 5.2 in the current analysis. Lemmas C.2 and C.8 use this bound to control the momentum estimator or its increments and the proximal residuals that enter the adaptive stepsize. Bounded variance provides conditional second-moment control.


Q6. The description of the algorithm is not detailed enough .. does min⁡(vt÷vt+1)\min(v_t\div v_{t+1}) mean taking the smallest component value?

Response. Yes. The division is coordinatewise, so the expression denotes min⁡1≤j≤n(vt)j/(vt+1)j\min_{1\le j\le n}(v_t)_j/(v_{t+1})_j.


Q7. Table 2 overlooks the result that the PStorm algorithm can achieve a log-free O(ϵ−3)O(\epsilon^{-3}) complexity with a constant step size and a constant initial batch size.

Response. Revised Table 2 now records PStorm's log-free O(ϵ−3)\mathcal O(\epsilon^{-3}) complexity under mean-squared smoothness with constant-size initialization.


Q8. [4] Can the authors give a concrete global proximal .. preserves tractability?

Response. Consider h(x)=λ∑j∣xj∣1/2+ι[−R,R]n(x)h(x)=\lambda\sum_j |x_j|^{1/2}+\iota_{[-R,R]^n}(x) with λ,R>0\lambda,R>0. This regularizer is nonconvex and non-Lipschitz on its effective domain. For a proximal center aa and positive diagonal weights cjc_j, the subproblem separates by coordinate. A minimizer can be chosen with the same sign as aja_j when aj≠0a_j\ne0. Setting s=∣xj∣s=\sqrt{|x_j|} gives the scalar problem

min⁡0≤s≤Rcj2(s2−∣aj∣)2+λs.\min_{0\le s\le\sqrt R} \frac{c_j}{2}(s^2-|a_j|)^2+\lambda s.

We evaluate the objective at both endpoints and at every interior real root of 2cjs(s2−∣aj∣)+λ=02c_js(s^2-|a_j|)+\lambda=0, then select the candidate with the smallest value.

Appendix D.2 details the proximal operators used in the new experiments, including the exact diagonal-metric proximal step for box-constrained capped ℓ1\ell_1 regularization.

Thank you for the author's reply. I have no further questions.

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

The paper proposes ALFPG, a family of adaptive proximal gradient methods that determine step sizes from trajectory information without requiring known smoothness constants or line search.

  • The full-batch variant, ALFPG-D, achieves O(ε−2)O(\varepsilon^{-2}) iterations.
  • The finite-sum variant, ALFPG-FS, combines a displacement-based diagonal metric, metric-coupled Nesterov extrapolation, and SPIDER, achieving O(N+Nε−2)O(N+\sqrt{N}\varepsilon^{-2}) component-gradient evaluations while allowing a possibly nonconvex regularizer hh on a bounded effective domain.
  • For expectation problems, ALFPG-MVR1 and ALFPG-MVR2 combine EMA and STORM-type estimators, respectively, with noise-sensitive adaptive weights, attaining O~(ε−2+σ2ε−4)\widetilde{O}(\varepsilon^{-2}+\sigma^2\varepsilon^{-4}) and O~(ε−2+σε−3)\widetilde{O}(\varepsilon^{-2}+\sigma\varepsilon^{-3}) without knowing σ\sigma, under almost surely bounded stochastic gradients and their respective smoothness and regularizer assumptions.
Critical strengths
  1. The stochastic variants adapt to the noise level while providing guarantees for a strong composite stationarity measure. Without knowing LL or σ\sigma, they achieve complexities O~(ε−2+σ2ε−4)\widetilde{O}(\varepsilon^{-2}+\sigma^2\varepsilon^{-4}) for the moving-average variant and O~(ε−2+σε−3)\widetilde{O}(\varepsilon^{-2}+\sigma\varepsilon^{-3}) for the STORM-type variant. They accommodate certain nonconvex regularizers and control the expected limiting-subdifferential residual, extending noise-adaptive guarantees to composite optimization.

2)) ALFPG-FS supports adaptive updates for a broad class of composite nonconvex problems. It combines an adaptive diagonal metric and extrapolation with proper, lower-semicontinuous regularizers that may be nonconvex and non-Lipschitz, provided the effective domain is bounded and the required diagonal-metric proximal subproblems are exactly and efficiently solvable. This extends the framework beyond smooth objectives and convex regularization.

Critical weaknesses
  1. The novelty in complexity order is limited. The rates largely match existing methods, including ADA-SPIDER, STORM, AdaGrad-Norm, and the auto-conditioned methods of Lan, Li, and Xu [1], under differing assumptions. The contribution primarily combines Lipschitz-free tuning, potentially nonconvex regularization, diagonal scaling, and extrapolation.
  2. The adaptive guarantees require restrictive assumptions. These include a bounded effective domain (Assumption 4.1) and almost surely bounded stochastic gradients (Assumption 5.2). Several adaptive baselines avoid these restrictions, making the trade-off between adaptivity and applicability important.
  3. The paper provides no empirical evaluation. The practical benefits of reduced tuning, extrapolation, and diagonal scaling remain unvalidated.
  4. The comparison with existing Lipschitz-free methods is incomplete. Tables 1 and 2 omit relevant competitors, making the incremental contribution difficult to assess.

[1] Lan, Li, and Xu. “Projected gradient methods for nonconvex and stochastic smooth optimization: New complexities and auto-conditioned stepsizes.” arXiv:2412.14291.

Questions for authors

Can Assumption 4.1 be relaxed or replaced with a weaker condition, such as bounded level sets, by establishing boundedness of the iterates through a suitable Lyapunov function?

2 comments

Thank you for the careful review. Your question about boundedness prompted us to revise the finite-sum assumption and the corresponding proof. Changes in the revised manuscript are marked in blue.


Q1. The novelty in complexity order is limited. The rates largely match existing methods, including ADA-SPIDER, STORM, AdaGrad-Norm, and the auto-conditioned methods of Lan, Li, and Xu [1], under differing assumptions. The contribution primarily combines Lipschitz-free tuning, potentially nonconvex regularization, diagonal scaling, and extrapolation.

Response. Our contributions are twofold.

  1. Finite-sum setting. We establish a stationarity guarantee for ALFPG with a possibly nonconvex regularizer. ALFPG combines displacement-based diagonal scaling, metric-coupled extrapolation, and SPIDER variance reduction.

  2. Online setting. We establish noise-adaptive oracle guarantees for composite nonconvex optimization. Both variants adapt their momentum coefficients and stepsizes without prior knowledge of the smoothness constant or the noise level.

(i) Novel discrepancy-based momentum cofficient. AdaGrad-Norm scales its stepsize by (1+∑i=1t∥∇f(xi;ξi)∥2)−1/2\bigl(1+\sum_{i=1}^{t}\|\nabla f(x_i;\xi_i)\|^2\bigr)^{-1/2}. ALFPG uses gradient discrepancies to adapt the momentum coefficient. MVR1 accumulates squared differences between consecutive stochastic gradients and sets αt=(1+∑i=1t∥∇f(xi;ξi)−∇f(xi−1;ξi−1)∥2)−1/2.\alpha_t=\left(1+\sum_{i=1}^{t} \bigl\|\nabla f(x_i;\xi_i)-\nabla f(x_{i-1};\xi_{i-1})\bigr\|^2\right)^{-1/2}.

MVR2 accumulates squared discrepancies between stochastic gradients evaluated at the same iterate, of the form αt=(1+∑i=1t∥∇f(xi−1;ξi−1)−∇f(xi−1;ξi)∥2)−2/3.\alpha_t=\left(1+\sum_{i=1}^{t} \bigl\| \nabla f(x_{i-1};\xi_{i-1})-\nabla f(x_{i-1};\xi_i) \bigr\|^2\right)^{-2/3}.

We also introduce a running-maximum safeguard to mitigate the impact of gradient spikes and ensure that the reciprocal momentum coefficient increases by at most pp per iteration, so that 1/αt−1/αt−1≤p.1/\alpha_t - 1/\alpha_{t-1} \le p.

(ii) Novel proximal-residual-based stepsizes. We set

\left(1+\sum_{i<t}\|r_i\|^2\right)^{-1/2}, \qquad r_i=\frac{x_i-x_{i+1}}{\gamma_i}.$$ The stepsize depends on both the momentum coefficient and the history of normalized proximal displacements. This dependence allows the stepsize to respond to the effect of the regularizer on past updates. (iii) Noise adaptation and the zero-noise limit. MVR1 and MVR2 attain the stationarity rates $$\widetilde{\mathcal O}\left(T^{-1/2}+\sqrt{\sigma} T^{-1/4}\right) \qquad\text{and}\qquad \widetilde{\mathcal O}\left(T^{-1/2}+\sigma T^{-1/3}\right),$$ respectively. At $\sigma=0$, both recover the $\widetilde{\mathcal O}(T^{-1/2})$ stationarity rate and the corresponding $\widetilde{\mathcal O}(\epsilon^{-2})$ oracle complexity. --- **Q2.** Can Assumption 4.1 be relaxed or replaced with a weaker condition, such as bounded level sets, by establishing boundedness of the iterates through a suitable Lyapunov function? **Response.** Yes. We have revised Assumption 4.1 to require that $F=f+h$ have bounded sublevel sets and that $f$ and $h$ each be bounded below. --- **Q3.** The paper provides no empirical evaluation. The practical benefits of reduced tuning, extrapolation, and diagonal scaling remain unvalidated. **Response.** Section 6 and Appendix D now report objective-versus-time comparisons on sparse phase retrieval, linear eigenvalue problems, and neural network regression. --- **Q4.** The comparison with existing Lipschitz-free methods is incomplete. Tables 1 and 2 omit relevant competitors, making the incremental contribution difficult to assess. **Response.** 1. We have added Lan, Li, and Xu’s AC-PG to Table 1 and AC-SPG and AC-VR-SPG to Table 2. Section 2 now discusses how these methods relate to ALFPG. 2. AC-PG addresses smooth minimization over compact convex sets. ALFPG-FS allows a possibly nonconvex regularizer when each diagonal-metric proximal subproblem is solved globally. 3. AC-SPG and AC-VR-SPG use **stochastic function values** and **tune batch sizes** to the noise level for their refined complexity bounds. ALFPG-MVR1 and ALFPG-MVR2 query **only stochastic gradients** and use a **fixed**, noise-independent batch size.

I thank the authors for their responses and clarifications. I appreciate their efforts to revise the finite-sum assumption and include additional comparisons with Lipschitz-free methods. These revisions have addressed some of my concerns, and I have therefore increased my review score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.