- 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 gradient complexity. Two expectation variants (ALFPG-MVR1/MVR2) combine adaptive momentum with proximal-residual normalization and achieve noise-dependent complexities of and , respectively, under their stated assumptions. The paper provides detailed convergence analyses using a subdifferential stationarity criterion.
Critical strengths
- 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.
- 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.
- 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 bound in the zero-noise regime.
Critical weaknesses
The critical weakness include:
-
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 and , 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.
-
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.
-
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
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.
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.
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
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 summarizes the history of gradient discrepancies. Its lagged value αt=ρt−1 sets the current momentum weight. The factor βt uses past proximal residuals to normalize the stepsize, and γt=θβtαtλ 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.
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.