- Rating
- 4(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper proposes accelerated proximal gradient-type methods for optimizing (strongly) convex composite objectives of the form , where is a convex prox-friendly component and is (strongly) convex and obeys generalized -smoothness. The authors first show that all minimizers induce the same gradient norm . Then, convergence guarantees are provided for their methods for two scenarios: i) having knowledge of , their algorithm converges at a rate of for convex and for -strongly convex ; ii) without knowledge of , an adaptive variant of their method which estimates this value attains a convergence rate of for convex . Finally, the authors show that these rates are tight in their dependence on . These theoretical results are supported by preliminary numerical experiments.
Critical strengths
- The problem is well motivated and fills a relevant gap in the literature on optimizing convex functions under generalized -smoothness
- The study is rigorous (claims are accompanied by proofs, which are correct to the extent that I have read them), and well placed within the existing literature, to the best of my knowledge (with one exception detailed later).
- The contributions are well-presented and clear
Critical weaknesses
- The experiments are conducted on very small problems () and compared with a rather weak baseline (see comments in the next section).
Questions for authors
-
Clarification requests:
- Please explain the requirement for restarts in the strongly convex case. Is there a blocker in obtaining the same rate without restarts, i.e., are restarts a technical requirement, or is it just a convenient way to ensure the rate?
- Please provide a discussion of how your rates in Corollaries 10, 12, 16 reduce to / compare with the existing L_0, L_1 rates of the works cited in Table 1 for (since the latter do not address the composite case)
- Convergence for the adaptive accelerated proximal method is only proven in the non-strongly convex case. Are there any technical blockers for proving accelerated convergence in the adaptive strongly convex scenario?
-
Notes for improvement:
- Inaccurate terminology: the authors use "Lipschitz smoothness" or "L-Lipschitz smoothness" in multiple places. The correct terminology is either of the following "L-smoothness", "Lipschitz (continuous) gradient" or "L-Lipschitz (continuous) gradient".
- The authors introduce a couple of quantities prior to defining them: R and T_{\ell} (lines 041 and 084). While R is the classical notation for in this niche of work, non-specialists will possibly be confused.
- The assumtpion that h is "proximable" (i.e., wither available in closed-form or via some efficient computational procedure) should be stated explicitly and early in the paper. Right now it is implicit.
- Typo 108: Gradient-dependent smoothness ---> The gradient-dependent smoothness
- Usage of is inconsistent, e.g. continues to be used after introducing , for example in the body of Theorem 4 and throughout the appendix (e.g., line 711). Furthermore, I find three different notations for almost the same quantity to be superfluous, i.e., , and . Since is hardly used, I suggest keeping simply to ease the reader's memory burden.
- Typo: missing right parenthesis in 1st term of line 262
- An overview of the approach to constructing the hard instance in the lower-bound proof would be useful. The first paragraphs until line 1146 essentially aim to get rid of the proximal contribution via separability, and to use established hard instances from smooth non-composite problems. As the proof is written now, this intention is implicit, which makes the presentation a bit opaque.
- Typo: missing full stop in Prop. 2.
-
Missing references:
- Li, Tianjiao, and Guanghui Lan. "A simple uniformly optimal method without line search for convex optimization: T. li, g. lan." Mathematical Programming. This work provides an accelerated method for convex composite objectives with prox-friendly and locally-Lipschitz gradient (see Remark following Corollary 1, on pg. 12). Please include a short discussion on this work, and perhaps a Table 1 entry. Furthermore, please include this method as a baseline for the experiments in Section 5.
-
Additional experiments:
- Please include a higher-dimensional, data-dependent problem instance. Here is a GPT-assisted example (feel free to use any other, of course): $ f_\mu(x)=\frac1n\sum_{i=1}^n\cosh(a_i^\top x)+\frac{\mu}{2}\|x\|_2^2$, $ h(x)=\lambda\|x-z\|_1$, for some fixed with having rows and , .
4 comments
4. Experiments and typos.
We have revised the presentation and added the suggested reference [5] following the reviewer's suggestions.
We have conducted new experiments for both convex and strongly convex problems involving random dense matrices, with the dimension increased to 1000. Figures 1–2 compare our methods with AC-FGM [5] and APG [6] for , with 20 independent instances in each group. We report objective gaps against both gradient calls and CPU time. The CPU time includes solver initialization, scalar integration and inversion, and backtracking or restart computations. For the convex problems, APG has comparable gradient costs in the and groups, but requires more CPU time.
We hope these responses have addressed all of the reviewer's concerns, and we would be happy to discuss any remaining questions.
References
[1] Ekaterina Borodich and Dmitry Kovalev. Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization. International Conference on Learning Representations, 2026.
[2] Alexander Tyurin. Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and -Smoothness. Proceedings of the 43rd International Conference on Machine Learning, 306:122876–122905, 2026.
[3] Eduard Gorbunov, Nazarii Tupitsa, Sayantan Choudhury, Alen Aliev, Peter Richtárik, Samuel Horváth, and Martin Takáč. Methods for Convex -Smooth Optimization: Clipping, Acceleration, and Adaptivity. International Conference on Learning Representations, 2025.
[4] Daniil Vankov, Anton Rodomanov, Angelia Nedić, Lalitha Sankar, and Sebastian U. Stich. Optimizing -Smooth Functions by Gradient Methods. International Conference on Learning Representations, 2025.
[5] Tianjiao Li and Guanghui Lan. A Simple Uniformly Optimal Method without Line Search for Convex Optimization. Mathematical Programming, 219:219–256, 2026.
[6] Zhaosong Lu and Sanyou Mei. Accelerated First-Order Methods for Convex Optimization with Locally Lipschitz Continuous Gradient. SIAM Journal on Optimization, 33(3):2275–2310, 2023.
Thank you for your response
I have read the authors' response to my and the other reviewers' concerns, and have read the updated manuscript. For me, this paper now meets the clear acceptance threshold, as the contribution is solid and adequately substantiated, the paper is well written, and the problem is relevant to the community. I have adjusted my score accordingly.
Thank you for your time and re-evaluation. We sincerely appreciate your encouraging feedback and support.
We thank the reviewer for recognizing the motivation and theoretical contributions, and for the suggestions on the analysis, presentation, and experiments. We address these points below.
1. Restarts in the strongly convex case.
We use restarts to incorporate the strong convexity of the full objective F=f+h into the convex algorithm. If a stage starts at xˉ with F(xˉ)−F⋆≤Δ, strong convexity gives the distance bound RΔ=2Δ/μ. The convex potential then guarantees F(xk)−F⋆≤AkRΔ2=μAk2Δ≤2Δ as soon as Ak≥4/μ. We can then restart with the smaller gap and distance bounds. After a finite startup, each stage requires O(1+ℓ(τ⋆)/μ) iterations, which gives the stated logarithmic dependence on the target accuracy.
Thus restarting is a convenient way to obtain the rate with our current potential. A method without restarts would require an analysis that incorporates μ directly while controlling the curvature along the extrapolation path. This is beyond the scope of this paper and we leave it as future work.
2. Comparison with existing rates when h=0.
When h=0, optimality gives ∇f(x⋆)=0, so τ⋆=0 is known and ℓ(τ⋆)=L0 in the (L0,L1)-smooth setting. For L12ε<L0, Corollary 10 reduces to Nε=O(RεL0+(1+L1R)log(2+L0Γ0(1+L1R)2)). The leading term agrees with those of Borodich and Kovalev [1] and Tyurin [2]. Tyurin's Theorem 4.3 also separates an accuracy-independent startup term. Corollary 16 similarly gives O(Tℓ+RL0/ε), although estimating τ⋆ is unnecessary when h=0.
In the accelerated bound of Gorbunov et al. [3], the factor 1+L1Rexp(L1R) multiplies RL0/ε. Vankov et al. [4] obtain the same RL0/ε term in their iteration bound, together with an additional logarithmic term. Their method also solves a one-dimensional minimization problem at each iteration, whose oracle cost is accounted for by the factor ν in Table 1.
For strongly convex f, Corollary 12 reduces to Nε=O((1+μL0)logεΔ0+L1R0),R0=μ2Δ0. This gives the usual accelerated strongly convex term, with L1 appearing only in the additive startup term.
3. Adaptive acceleration in the strongly convex case.
Algorithm 3 can be used as the inner solver in the restart scheme under the same strong convexity assumption. At stage j, we use Δj=2−jΔ0, Rj=2Δj/μ, and Γ0=μ, and stop when Ak≥4/μ. Algorithm 3 guarantees that each stage terminates and decreases the gap bound by half. Its warm-start procedure also handles initialization when the gap is outside the range of Qτ.
As explained in the new remark at the end of the adaptive-method section, the scale estimates converge to τ⋆ as the stage gaps decrease. This gives the same leading strongly convex complexity, with only a finite startup cost independent of ε. Combining this adaptive idea with a method without restarts, as discussed in our response to Question 1, could lead to an interesting new accelerated algorithm.