acceptodds
Under review as a conference paper at ICLR 2027

Accelerated Composite Optimization under Gradient-Dependent Curvature

Abstract

We study convex composite optimization under gradient-dependent curvature characterized by , which generalizes Lipschitz smoothness. Existing accelerated methods under this condition mainly focus on smooth minimization, where and the iteration complexity is governed by . In composite optimization, the smooth gradient may not vanish at a solution, so the local curvature is generally not determined by . We show that all minimizers share the same smooth gradient, whose norm is denoted by . Based on a localization of the smooth-gradient difference around the solution, we develop an accelerated proximal method with iteration complexity , where is independent of . An adaptive variant achieves the same complexity without requiring prior knowledge of . For -strongly convex objectives, a restarted algorithm gives iteration complexity. We also establish lower bounds matching the leading terms in both the convex and strongly convex settings. Numerical experiments are included to support our theoretical findings.

Primary area:
optimization
Keywords:
composite optimization, gradient-dependent smoothness, accelerated proximal methods

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_YLRdOpenReview ↗
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 f(x)+h(x)f(x) + h(x), where hh is a convex prox-friendly component and ff is (strongly) convex and obeys generalized ℓ\ell-smoothness. The authors first show that all minimizers induce the same gradient norm τ⋆\tau^\star. Then, convergence guarantees are provided for their methods for two scenarios: i) having knowledge of τ⋆\tau^\star, their algorithm converges at a rate of O(Tℓ+Rℓ(τ⋆)/ε)O(T_\ell + R\sqrt{ \ell(\tau^\star)/\varepsilon}) for convex ff and O(Tℓ,μ+(1+ℓ(θ⋆)/μ)log⁡(Δ0/ε))O\left(T_{\ell,\mu} + \left( 1 + \sqrt{\ell(\theta^\star)/\mu}\right) \log (\Delta_0/\varepsilon)\right) for μ\mu-strongly convex ff; ii) without knowledge of τ⋆\tau^\star, an adaptive variant of their method which estimates this value attains a convergence rate of O(T^ℓ+Rℓ(τ⋆)/ε)O(\hat T_\ell + R\sqrt{ \ell(\tau^\star)/\varepsilon}) for convex ff. Finally, the authors show that these rates are tight in their dependence on ℓ(τ⋆)\ell(\tau^\star). 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 ℓ\ell-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 (dim≤2\mathrm{dim} \leq 2) 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 h=0h = 0 (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 ∣x0−x⋆∣\\|x_0 - x^\star\\| 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 g⋆g^{\star} is inconsistent, e.g. ∇f(x⋆)\nabla f(x^{\star}) continues to be used after introducing g⋆g^\star, 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., v⋆v^\star, −g⋆-g^\star and −∇f(x⋆)-\nabla f(x^\star). Since v⋆v^\star is hardly used, I suggest keeping simply −g⋆-g^\star 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 f(x)+h(x)f(x) + h(x) with prox-friendly hh and locally-Lipschitz gradient ff (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 z∈Rdz \in \mathbb R^d with A∈Rn×dA\in\mathbb R^{n\times d} having rows ai⊤a_i^\top and rank⁡(A)=n\operatorname{rank}(A)=n, n≤dn\le d.
4 comments

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+hF=f+h into the convex algorithm. If a stage starts at xˉ\bar x with F(xˉ)−F⋆≤ΔF(\bar x)-F^\star\leq\Delta, strong convexity gives the distance bound RΔ=2Δ/μR_\Delta=\sqrt{2\Delta/\mu}. The convex potential then guarantees F(xk)−F⋆≤RΔ2Ak=2ΔμAk≤Δ2F(x_k)-F^\star\leq\frac{R_\Delta^2}{A_k}=\frac{2\Delta}{\mu A_k}\leq\frac{\Delta}{2} as soon as Ak≥4/μA_k\geq4/\mu. We can then restart with the smaller gap and distance bounds. After a finite startup, each stage requires O(1+ℓ(τ⋆)/μ)O(1+\sqrt{\ell(\tau_\star)/\mu}) 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 μ\mu 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=0h=0.

When h=0h=0, optimality gives ∇f(x⋆)=0\nabla f(x^\star)=0, so τ⋆=0\tau_\star=0 is known and ℓ(τ⋆)=L0\ell(\tau_\star)=L_0 in the (L0,L1)(L_0,L_1)-smooth setting. For L12ε<L0L_1^2\varepsilon<L_0, Corollary 10 reduces to Nε=O(RL0ε+(1+L1R)log⁡(2+Γ0(1+L1R)2L0)).N_\varepsilon=O\left(R\sqrt{\frac{L_0}{\varepsilon}}+(1+L_1R)\log\left(2+\frac{\Gamma_0(1+L_1R)^2}{L_0}\right)\right). 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/ε)O(\widehat T_\ell+R\sqrt{L_0/\varepsilon}), although estimating τ⋆\tau_\star is unnecessary when h=0h=0.

In the accelerated bound of Gorbunov et al. [3], the factor 1+L1Rexp⁡(L1R)\sqrt{1+L_1R\exp(L_1R)} multiplies RL0/εR\sqrt{L_0/\varepsilon}. Vankov et al. [4] obtain the same RL0/εR\sqrt{L_0/\varepsilon} 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 ν\nu in Table 1.

For strongly convex ff, Corollary 12 reduces to Nε=O((1+L0μ)log⁡Δ0ε+L1R0),R0=2Δ0μ.N_\varepsilon=O\left(\left(1+\sqrt{\frac{L_0}{\mu}}\right)\log\frac{\Delta_0}{\varepsilon}+L_1R_0\right),\qquad R_0=\sqrt{\frac{2\Delta_0}{\mu}}. This gives the usual accelerated strongly convex term, with L1L_1 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 jj, we use Δj=2−jΔ0\Delta_j=2^{-j}\Delta_0, Rj=2Δj/μR_j=\sqrt{2\Delta_j/\mu}, and Γ0=μ\Gamma_0=\mu, and stop when Ak≥4/μA_k\geq4/\mu. 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τQ_\tau.

As explained in the new remark at the end of the adaptive-method section, the scale estimates converge to τ⋆\tau_\star as the stage gaps decrease. This gives the same leading strongly convex complexity, with only a finite startup cost independent of ε\varepsilon. 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.

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 τ⋆=0.1,1,10\tau_\star=0.1,1,10, 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 τ⋆=1\tau_\star=1 and τ⋆=10\tau_\star=10 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 (L0,L1)(L_0,L_1)-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 (L0,L1)(L_0,L_1)-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 (L0,L1)(L_0,L_1)-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.

Reviewer_YLRdOpenReview ↗

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.

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

This paper studies accelerated composite optimization under gradient-dependent curvature. The authors develop localization bounds and accelerated proximal methods with complexity governed by ℓ(τ⋆)\ell(\tau^\star). They also propose an adaptive variant that does not require knowledge of τ⋆\tau^\star and a restarted method for strongly convex problems. Matching leading-order lower bounds are established, and numerical experiments demonstrate the methods' performance.

Critical strengths
  1. Extension to composite optimization. The paper extends accelerated methods under gradient-dependent curvature from smooth unconstrained minimization to composite problems, allowing nonsmooth regularizers and constraints. This broadens the applicability of existing acceleration results.

  2. Matching lower bounds. The paper establishes lower bounds matching the leading terms of the proposed upper bounds for both convex and strongly convex problems, demonstrating the optimality of their dependence on ℓ(τ⋆)\ell(\tau^\star).

Critical weaknesses
  1. Computational practicality of the proposed methods. The algorithms require evaluating integral functions and their inverses, including Qτ−1Q_\tau^{-1} and Pc−1P_c^{-1}, to determine the algorithmic parameters. For a general curvature function ℓ\ell, it is unclear how efficiently these quantities can be computed and whether numerical approximations preserve the convergence guarantees. This limits the practical applicability of the proposed methods.

  2. Limited experimental comparisons. The experiments compare the proposed accelerated methods primarily with a nonaccelerated proximal gradient baseline, without including existing accelerated proximal methods, such as Lu and Mei (2023). Moreover, all experiments use τ⋆=1\tau^\star=1, making it difficult to assess the effectiveness of the adaptive mechanism across different solution-gradient scales. These limitations weaken the empirical validation of the proposed approach.

Questions for authors
  1. Could the authors provide more intuition for the introduction of QτQ_\tau and PcP_c, particularly the construction of these functions and why two different integral functions are needed for the localization analysis and adaptive algorithm?

  2. Equation (3) requires Γ0≥2Δ0/R2\Gamma_0 \ge 2\Delta_0/R^2 and Γ0R2<Qτ⋆,∞\Gamma_0 R^2 < Q_{\tau^\star,\infty}, which can hold simultaneously only if 2Δ0<Qτ⋆,∞2\Delta_0 < Q_{\tau^\star,\infty}. However, this condition is not guaranteed for a general curvature function ℓ\ell. For example, even when τ⋆=0\tau^\star=0, choosing ℓ(s)=1+s3\ell(s)=1+s^3 gives Q0,∞=2π/(33)<∞Q_{0,\infty}=2\pi/(3\sqrt{3})<\infty, so the initialization is infeasible whenever Δ0≥π/(33)\Delta_0\ge\pi/(3\sqrt{3}). Although Algorithm 3 addresses this issue through a warm-start procedure, Theorem 11 retains the corresponding restriction in the strongly convex setting. Could the authors clarify whether this restriction is essential or can be removed?

  3. Could the authors comment on the possibility of extending the proposed framework to nonconvex composite optimization under gradient-dependent curvature?

4 comments

We thank the reviewer for the comments on the computation, initialization, and experiments. We provide further explanations below.

1. Intuition for the functions QτQ_\tau and PcP_c.

For a convex LL-smooth function, the classical inequality is ∣∇f(x)−∇f(y)∣22L≤f(x)−f(y)−⟨∇f(y),x−y⟩.\frac{\\|\nabla f(x)-\nabla f(y)\\|^2}{2L}\leq f(x)-f(y)-\langle\nabla f(y),x-y\rangle. Taking y=x⋆y=x^\star and using −g⋆∈∂h(x⋆)-g_\star\in\partial h(x^\star) gives s2/(2L)≤F(x)−F⋆s^2/(2L)\leq F(x)-F^\star, where s=∣∇f(x)−g⋆∣s=\\|\nabla f(x)-g_\star\\|. Both Qτ(s)Q_\tau(s) and Pc(s)P_c(s) reduce to s2/(2L)s^2/(2L) when ℓ≡L\ell\equiv L, and generalize this bound under gradient-dependent curvature based on different information.

To explain the construction of QτQ_\tau, fix τ≥τ⋆\tau\geq\tau_\star and consider the centered function ϕ(x)=f(x)−⟨g⋆,x⟩\phi(x)=f(x)-\langle g_\star,x\rangle. Along its gradient flow z˙(t)=−∇ϕ(z(t))\dot z(t)=-\nabla\phi(z(t)) with z(0)=xz(0)=x, define s(t)=∣∇ϕ(z(t))∣s(t)=\\|\nabla\phi(z(t))\\|. Whenever s(t)>0s(t)>0, convexity and the curvature condition give ddtϕ(z(t))=−s(t)2,−ℓ(τ+s(t))s(t)≤s′(t)≤0.\frac{d}{dt}\phi(z(t))=-s(t)^2,\qquad -\ell(\tau+s(t))s(t)\leq s'(t)\leq0. Thus s(t)2s(t)^2 is the decrease of the centered function value along this flow. Defining Qτ(s)=∫0su/ℓ(τ+u),duQ_\tau(s)=\int_0^s u/\ell(\tau+u)\\,du lets us compare its derivative directly with the function-value derivative ddtQτ(s(t))=s(t)s′(t)ℓ(τ+s(t))≥−s(t)2=ddtϕ(z(t)).\frac{d}{dt}Q_\tau(s(t))=\frac{s(t)s'(t)}{\ell(\tau+s(t))}\geq-s(t)^2=\frac{d}{dt}\phi(z(t)). Integrating this inequality, using s(t)→0s(t)\to0 and ϕ(z(t))≥ϕ(x⋆)\phi(z(t))\geq\phi(x^\star), gives Qτ(s(0))≤ϕ(x)−ϕ(x⋆)≤F(x)−F⋆Q_\tau(s(0))\leq\phi(x)-\phi(x^\star)\leq F(x)-F^\star. This explains how QτQ_\tau converts an objective-gap bound into a bound on the centered gradient.

For the adaptive method, we first need an upper bound on the unknown τ⋆\tau_\star. We therefore use the observable quantity c=∣∇f(x)∣c=\\|\nabla f(x)\\| to construct PcP_c. The purpose is to bound the decrease of the centered function using curvature information at xx. For s=∣∇ϕ(x)∣>0s=\\|\nabla\phi(x)\\|>0, consider the direction e=−∇ϕ(x)/se=-\nabla\phi(x)/s for the analysis. The gradient variation r(t)=∣∇f(x+te)−∇f(x)∣r(t)=\\|\nabla f(x+te)-\nabla f(x)\\| satisfies r′(t)≤ℓ(c+r(t))r'(t)\leq\ell(c+r(t)) almost everywhere. Integrating this inequality gives a step length ts=∫0sdu/ℓ(c+u)t_s=\int_0^s du/\ell(c+u) over which the gradient variation is at most ss. Integrating the gradient variation along this step then bounds the Taylor remainder by ∫0su/ℓ(c+u),du\int_0^s u/\ell(c+u)\\,du. Consequently, ϕ(x)−ϕ(x+tse)≥s,ts−∫0suℓ(c+u),du=∫0ss−uℓ(c+u),du=Pc(s).\phi(x)-\phi(x+t_s e)\geq s\\,t_s-\int_0^s\frac{u}{\ell(c+u)}\\,du=\int_0^s\frac{s-u}{\ell(c+u)}\\,du=P_c(s). Here s,tss\\,t_s is the decrease predicted by the linear term, and the subtracted integral accounts for the curvature. Their difference gives the weight s−us-u. Since x⋆x^\star minimizes ϕ\phi, this guarantees Pc(s)≤ϕ(x)−ϕ(x⋆)≤F(x)−F⋆P_c(s)\leq\phi(x)-\phi(x^\star)\leq F(x)-F^\star.

The above inequality gives τ⋆≤c+Pc−1(δ)\tau_\star\leq c+P_c^{-1}(\delta) whenever F(x)−F⋆≤δF(x)-F^\star\leq\delta. Since PcP_c depends on the observable gradient norm cc and is unbounded for every finite cc, it provides an initial scale bound for any finite gap and supports the warm start when the gap is too large to invert QτQ_\tau. Once an upper bound τ≥τ⋆\tau\geq\tau_\star is available and the gap lies within the range of QτQ_\tau, we use QτQ_\tau to obtain a centered-gradient bound directly from the gap certificate for the subsequent accelerated iterations.

2. Scalar computation and numerical approximations.

For the affine curvature function ℓ(s)=L0+L1s\ell(s)=L_0+L_1s, both integrals have elementary expressions. Their inverses can therefore be computed by solving monotone scalar equations, for example by bisection. In our experiments, we use analytic expressions and a safeguarded Newton method, with series expansions near zero for numerical stability. The CPU time reported in Figures 1–2 includes these computations.

We can also evaluate these integrals explicitly for some nonlinear curvature functions. For example, the log-cosine problem in the original submission uses ℓ(s)=1+s2\ell(s)=1+s^2, for which

Q_\tau(s)= & \frac12\log\frac{1+(\tau+s)^2}{1+\tau^2}-\tau\bigl(\arctan(\tau+s)-\arctan\tau\bigr), \\\\ P_c(s)= & (c+s)\bigl(\arctan(c+s)-\arctan c\bigr)-\frac12\log\frac{1+(c+s)^2}{1+c^2}, \\\\ \rho_\tau(s)= & \arctan(\tau+2s)-\arctan(\tau+s). \end{aligned}$$ These formulas involve only logarithms and arctangents, and the inverses of $Q_\tau$ and $P_c$ can be computed by monotone scalar root-finding. Thus this nonlinear example also avoids numerical quadrature.

3. Initialization of the strongly convex method.

We thank the reviewer for identifying this failur example. This restriction can be removed by a finite warm start, as shown in the new Lemma 14 of our revised paper. We start Algorithm 1 with R=2Δ0/μR=\sqrt{2\Delta_0/\mu} and Γ0=μ\Gamma_0=\mu. For any fixed c>0c>0, we replace the inverse-based gradient bound by Mk=max⁡c,∣∇f(xk)∣+τ⋆M_k=\max\\{c,\\|\nabla f(x_k)\\|+\tau_\star\\}, and use the corresponding LkL_k and ρk\rho_k. It can be ensured that MkM_k bounds the centered gradient, hence this phase does not require inverting Qτ⋆Q_{\tau_\star} during the warm start step.

The lemma shows that after finitely many iterations, the gap certificate satisfies F(xK)−F⋆≤δK≤Δ0,2δK≤Qτ⋆(c)<Qτ⋆,∞.F(x_K)-F^\star\leq\delta_K\leq\Delta_0,\qquad 2\delta_K\leq Q_{\tau_\star}(c)<Q_{\tau_\star,\infty}. Algorithm 2 can then start from xKx_K with the gap bound δK\delta_K. The warm-start cost is independent of the target accuracy ε\varepsilon, so it only changes the additive startup term and preserves the leading strongly convex rate.

4. Extension to nonconvex composite optimization.

Our current analysis uses convexity to center the smooth gradient at a minimizer and bound its variation by the objective gap. For nonconvex problems, the natural goal is to find an approximately stationary point.

One possible direction is to use our methods to solve regularized subproblems. If ff is ρ\rho-weakly convex and hh is convex, adding κ∣x−y∣2/2\kappa\\|x-y\\|^2/2 with κ>ρ\kappa>\rho makes the subproblem strongly convex. Related approaches use convex solvers for nonconvex optimization [3], or accelerated composite gradient methods for proximal subproblems under Lipschitz gradient assumptions [4]. In our setting, the regularized smooth gradient becomes ∇f(x)+κ(x−y)\nabla f(x)+\kappa(x-y), while the original curvature condition depends on ∣∇f(x)∣\\|\nabla f(x)\\|. We would therefore need to establish suitable curvature bounds for the subproblems and translate their solution accuracy into a stationarity guarantee for the original problem. We believe this extension is possible with some efforts.

5. Comparisons with accelerated baselines and computational costs.

We have conducted new experiments for both convex and strongly convex problems, with the dimension increased to 1000. Figures 1–2 compare our methods with APG [1] and AC-FGM [2]. All methods use the same initial point on each instance. We report objective gaps against both gradient calls and CPU time. The counts include initialization and backtracking evaluations, and the CPU time includes solver initialization, scalar integration and inversion, and the backtracking or restart computations used by each method.

For the convex problems in Figure 1, APG has gradient costs comparable to those of our methods in the τ⋆=1\tau_\star=1 and τ⋆=10\tau_\star=10 groups, but requires more CPU time. The additional function-value evaluations used by its backtracking contribute to this cost. For the strongly convex problems in Figure 2, our restarted implementation has lower mean gradient and CPU costs at accuracy 10−1210^{-12} when τ⋆=0.1\tau_\star=0.1 and τ⋆=1\tau_\star=1. When τ⋆=10\tau_\star=10, AC-FGM uses fewer gradient calls, while our implementation uses less CPU time.

6. Experiments at different solution-gradient scales.

Both figures now include τ⋆=0.1,1,10\tau_\star=0.1,1,10. For each value and each problem family, we generate 20 independent instances. Each curve shows the mean objective gap over these instances, and CPU time uses the median of five timing repetitions per instance.

We hope these responses have addressed all of the reviewer's concerns, and we would be happy to discuss any remaining questions.

References

[1] 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.

[2] Tianjiao Li and Guanghui Lan. A Simple Uniformly Optimal Method without Line Search for Convex Optimization. Mathematical Programming, 219:219–256, 2026.

[3] Courtney Paquette, Hongzhou Lin, Dmitriy Drusvyatskiy, Julien Mairal, and Zaid Harchaoui. Catalyst for Gradient-based Nonconvex Optimization. Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, 84:613–622, 2018.

[4] Weiwei Kong, Jefferson G. Melo, and Renato D. C. Monteiro. Complexity of a Quadratic Penalty Accelerated Inexact Proximal Point Method for Solving Linearly Constrained Nonconvex Composite Programs. SIAM Journal on Optimization, 29(4):2566–2593, 2019.

Thank you for the detailed rebuttal and substantial revisions. I appreciate the theoretical clarifications, and the new warm-start result. These improvements address several of my original concerns.

My main remaining concern is the overall algorithmic significance. While the solution-scale curvature dependence ℓ(τ⋆)\ell(\tau_\star) is theoretically valuable, it comes with additional problem-dependent information requirements and scalar computations. Although the authors have addressed several implementation concerns, the computational tradeoff between these requirements and the improved asymptotic guarantees remains insufficiently clear for general curvature functions.

I recognize the value of the localization analysis and matching leading-order lower bounds. Nevertheless, I remain insufficiently convinced of the overall algorithmic advantage over existing accelerated methods and therefore maintain my score of 2.

We thank the reviewer for the follow-up. To further clarify the computational trade-off, we have added four experiments with nonlinear ℓ\ell-functions in Appendix C (Figures 3-6). The considered ℓ\ell-functions are as follows:

  1. Convex exponential-square objectives with ℓ(s)=σ2(1+W(8s2σ2))exp⁡(12W(8s2σ2)),\ell(s)=\frac{\sigma}{2}\left(1+W\left(\frac{8s^2}{\sigma^2}\right)\right)\exp\left(\frac12W\left(\frac{8s^2}{\sigma^2}\right)\right), where WW is the principal Lambert WW function.

  2. Convex double-exponential objectives with ℓ(s)=σ2(1+22sσ)(1+W(1+22sσ)).\ell(s)=\frac{\sigma}{2}\left(1+\frac{2\sqrt{2}s}{\sigma}\right)\left(1+W\left(1+\frac{2\sqrt{2}s}{\sigma}\right)\right).

  3. Strongly convex objectives with logarithmic curvature, with ℓ(s)=1+μ+12log⁡(1+r(s)2),\ell(s)=1+\mu+\frac12\log(1+r(s)^2), where r(s)r(s) is the unique nonnegative solution of the equation s=μr+r2log⁡(1+r2)+arctan⁡r.s=\mu r+\frac r2\log(1+r^2)+\arctan r.

  4. Strongly convex objectives with spectral curvature, with ℓ(s)=λmax⁡(Λ+φ′′(p(s))aa⊤).\ell(s)=\lambda_{\max}\bigl(\Lambda+\varphi''(p(s))aa^\top\bigr). Here Λ\Lambda is a positive diagonal matrix, aa is a unit vector, and φ(t)=exp⁡(tarsinh⁡(t)−1+t2+1)−1\varphi(t)=\exp(t\operatorname{arsinh}(t)-\sqrt{1+t^2}+1)-1. The value p(s)p(s) is determined by a scalar equation specified in Appendix C, and the largest eigenvalue requires solving another scalar equation.

The comparison results of the first three instances indicate that the computational cost of integration and inversion is not the bottleneck compared to the function-value evaluation cost of the two baseline algorithms. For the fourth experiment, as the integration and inversion operations require repeated evaluations of ℓ\ell, the computational cost is much higher than in the other three examples.

We use two methods to estimate the required quantities and report the results in Figure 6. The first one maintains a piecewise Chebyshev table to approximate the integrals and perform their inversion. At the beginning of the algorithm, there is a plateau in the CPU time where the table is constructed. When this process is finished, our proposed algorithm decreases the function value rapidly.

The second method uses a relaxed curvature bound ℓ~(s)=max⁡iλi+φ′′(p(s))≥ℓ(s)\widetilde\ell(s)=\max_i\lambda_i+\varphi''(p(s))\geq\ell(s) to avoid the eigenvalue computation. Although this looser bound requires slightly more gradient calls, its lower scalar-computation cost leads to shorter CPU time.

We would also like to clarify the motivation of our proposed algorithms. Our goal is to use available information about ℓ\ell to design accelerated methods with solution-scale curvature guarantees. When this information is provided, our algorithms can avoid the function-value oracle and reduce the corresponding cost. The additional experiments further indicate that our algorithms can be more suitable for some problems with general ℓ\ell-functions, as they have lower CPU costs at high accuracy even after accounting for the required computations.

We hope these additional experiments have addressed the reviewer's remaining concern and would be grateful if the reviewer could consider raising the score.

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

The paper studies convex composite minimization under gradient-dependent curvature. It develops accelerated proximal methods with leading complexity governed by ℓ(τ⋆)\ell(\tau_\star), where τ⋆=∥∇f(x⋆)∥\tau_\star=\|\nabla f(x^\star)\|, an adaptive variant for unknown τ⋆\tau_\star, and a separate strongly convex restart guarantee. Lower bounds match the leading terms. Validation comprises theoretical analysis, reported Lean formalizations, and six synthetic experiments against proximal GD.

Critical strengths
  1. The solution-centered localization and pathwise analysis handle the nonzero smooth gradient at a composite optimum. Together with matching leading-order lower bounds, this identifies a sharp asymptotic curvature scale for the composite problem class, which is a substantive theoretical contribution.

  2. The adaptive method retains the leading rate without prior knowledge of τ⋆\tau_\star, including a finite warm start when localization cannot be initialized directly. This extends the guarantee beyond an algorithm requiring knowledge of the solution-gradient scale.

Critical weaknesses
  1. Empirical advantage over existing accelerated methods is not established. Figures 1–2 compare only with nonaccelerated proximal GD, omitting Lu–Mei's locally smooth APG and Li–Lan's AC-FGM. The experiments support acceleration over GD, but cannot isolate the practical benefit of solution-scale control over existing acceleration. No running-time comparison accounts for startup and scalar-computation costs. This limits the empirical conclusions, while leaving the theoretical contribution intact.

  2. The provenance and scope of the technical novelty need clearer attribution. Proposition 13's integral inequality is Tyurin (2025), Lemma I.1, Eq. (30), after a change of variables. Its continuous-ℓ\ell version follows by approximation. This relationship should be explicit. Important uncited work includes AC-FGM, which provides adaptive composite acceleration under local smoothness, and Yu et al., which covers nonaccelerated composite optimization under subquadratic generalized smoothness. These are precedents for individual ingredients, not evidence that the solution-scale composite analysis, adaptive warm start, and matching bounds are collectively redundant.

Questions for authors
  1. Clarification on the theoretical advance: How do the curvature dependence, startup terms, and required inputs compare with Lu–Mei APG and AC-FGM under comparable assumptions and oracle accounting?

  2. Clarification of available empirical evidence: Are comparisons with these accelerated methods available that account for startup and scalar-computation costs? They would help assess practical benefits beyond the demonstrated asymptotic guarantee.

  3. Clarification of theorem statements and coverage: Theorem 15 permits an already-optimal initialization with Δ0=Γ0=0\Delta_0=\Gamma_0=0, for which A0=1/Γ0A_0=1/\Gamma_0 is undefined. Is strict positivity intended? What domain-preservation result justifies applying the theory to the log-cosine experiment? These concern initialization and coverage, rather than a counterexample to the full-space rate for positive initialization.

4 comments

We thank the reviewer for recognizing the theoretical contribution and for the suggestions on comparisons, attribution, and theorem coverage. We address these points below.

1. Comparison with APG and AC-FGM: curvature dependence, startup, and required inputs.

Our analysis uses the known curvature function ℓ\ell to obtain an accelerated convex composite objective-gap guarantee of Nε=O(Tℓ+Rℓ(τ⋆)ε).N_\varepsilon=O\left(T_\ell+R\sqrt{\frac{\ell(\tau_\star)}{\varepsilon}}\right). Here TℓT_\ell is independent of the target accuracy ε\varepsilon, and ℓ(τ⋆)\ell(\tau_\star) bounds the smooth curvature at the optimal solution. Our proposed Algorithm 3 also attains the same leading term without knowing τ⋆\tau_\star, with a finite startup term T^ℓ\widehat T_\ell.

For APG in [1], the convergence rate given in their Theorem 2 is F(xt)−F⋆≤4r02(2+(t−1)α0min⁡1,δ/(γ0LS^))2,F(x^t)-F^\star\leq\frac{4r_0^2}{\left(2+(t-1)\alpha_0\sqrt{\min\\{1,\delta/(\gamma_0L_{\widehat S})\\}}\right)^2}, where r0r_0 is their initialization-energy quantity and LS^L_{\widehat S} is a Lipschitz constant on a fixed enlarged region containing the iterates. Such a result indeed can be translated into our curvature-dependent condition by letting LS^=sup⁡x∈S^ℓ(∣∇f(x)∣)L_{\widehat S}=\sup_{x\in\widehat S}\ell(\\|\nabla f(x)\\|), which may be substantially larger than ℓ(τ⋆)\ell(\tau_\star) as our τ∗\tau_* is the gradient norm on the optimal solution while theirs is the maximum norm over a larger set.

For AC-FGM [3], the same issue holds. In Corollary 1 of [3], the convergence rate is \Psi(x_k)-\Psi^\star\leq\frac{12\widehat L_k}{k(k+1)}C_{\rm init},\qquad \widehat L_k=\max\left\\{\frac{1}{4(1-\beta)\eta_1},L_1,\ldots,L_k\right\\}, where we use CinitC_{\rm init} to represent a complicated term that includes the initial-distance term and an initial-displacement correction. The curvature coefficient L^k\widehat L_k depends on the initial stepsize and the largest local curvature estimate along the trajectory, so it can be substantially larger than ℓ(τ⋆)\ell(\tau_\star).

As for the required information of these algorithms, indeed APG and AC-FGM do not require ℓ\ell, RR, or Γ0\Gamma_0 as inputs. But they still require initial stepsize choices, namely γ0\gamma_0 for APG and η1\eta_1 for AC-FGM. The constants in their convergence bounds explicitly depend on these choices. In the same time, our methods require more information, but we provide a more favorable separation of the initialization and curvature dependence. Γ0\Gamma_0 enters only the accuracy-independent startup term, while the leading curvature dependence is governed by ℓ(τ⋆)\ell(\tau_\star). Nevertheless, we agree the reviewer raises an important practical issue, since this problem information may be unavailable. Designing algorithms that retain the same solution-scale guarantee without requiring such information is a promising direction for future work.

There is another difference between our algorithms and the other two algorithms. APG applies back-tracking technique to esitmate local curvature information. Such a step requires the function value oracle, which in some problems may be heavy to calculate. AC-FGM also requires function value to estimate curvature. We discuss the practical impact of this difference in our response to Question 2 below.

2. Empirical comparisons including startup and scalar-computation costs.

We have conducted new experiments for both convex and strongly convex problems, while the original toy examples are removed. For the new instances, the dimension has been increased to 1000. We also include the baseline algorithms APG and AC-FGM to compare the performance of three accelerated proximal methods that can be used to solver the problem we consider in the paper. Furthermore, we also report gradient oracle and CPU time to account for all of the costs of the algorithm. The new results are presented in Fig 1 and 2 in the revised paper.

For different values of τ∗\tau_*, it can be observed that in convex scenario, even though the gradient oracle numbers are similar, the CPU times differ. Such a performance shows that the APG does suffer from the heavy function value evaluation cost and our startup as well as scalar-computation do note cost much time.

3. Attribution of Proposition 13 and related work.

We agree that the integral inequality in Proposition 13 is Tyurin's Lemma I.1, Eq. (30), after a change of variables. We proof this because the assumption we use is a relaxed version to Tyurin's. We have extented the inequality from locally Lipschitz to continuous, nondecreasing ℓ\ell. We have explicitly acknowledged this relationship in the appendix.

We have also added [2-3] to the related work. We thank the reviewer for pointing this out.

4. Positive initialization in Theorem 15.

Yes, strict positivity is intended whenever the algorithm is run. If the supplied bound satisfies Δ0=0\Delta_0=0 or R=0R=0, then x0x_0 is already optimal and can be returned immediately. We now state this explicitly after the initial bounds and assume R>0R>0 and Δ0>0\Delta_0>0 for the remaining analysis.

5. Domain preservation for the log-cosine example.

Such an issue can be fixed. In summary, since this example is defined on D=(c−π/2,c+π/2)×RD=(c-\pi/2,c+\pi/2)\times\mathbb R, we can prove both the evaluation points and the auxiliary paths used in the proofs satisfy the curvature condition. For u=(x,y)∈Du=(x,y)\in D, τ≥τ⋆\tau\geq\tau_\star, and finite M≥∣∇f(u)−g⋆∣M\geq\\|\nabla f(u)-g_\star\\|, the path radius satisfies ρτ(M)=arctan⁡(τ+2M)−arctan⁡(τ+M)<π/2−∣x−c∣=dist⁡(u,∂D).\rho_\tau(M)=\arctan(\tau+2M)-\arctan(\tau+M)<\pi/2-|x-c|=\operatorname{dist}(u,\partial D). Thus the path-length restriction keeps the extrapolation and update paths inside DD. The centered gradient flow used for localization also remains in DD, since its gradient stays bounded whereas ∣tan⁡(x−c)∣|\tan(x-c)| diverges at the boundary. Similarly, the auxiliary segment used for the PcP_c inequality has length smaller than the distance to the boundary, so it stays in DD. Starting from x0∈Dx_0\in D with the stated initialization, these arguments ensure xk,yk∈Dx_k,y_k\in D for Algorithms 1 and 3 and justify applying the localization and convergence analysis to this example.

But since we have replaced this toy example with a new one, this analysis is not included in the revised paper.

We hope these responses have addressed all of the reviewer's concerns, and we would be happy to discuss any remaining questions.

References

[1] 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.

[2] Dingzhi Yu, Wei Jiang, Hongyi Tao, Yuanyu Wan, and Lijun Zhang. Mirror Descent Under Generalized Smoothness. Proceedings of the 43rd International Conference on Machine Learning, 2026.

[3] Tianjiao Li and Guanghui Lan. A Simple Uniformly Optimal Method without Line Search for Convex Optimization. Mathematical Programming, 219:219–256, 2026.

Thank you for the point-by-point response and revisions. The new comparisons (Remark 11, Figures 1,2) and clarifications on initialization and attribution have addressed my concerns.
I maintain my original score of 3.

Thank you for your response. Your constructive suggestions have helped us improve the quality of our manuscript.

Comments on the paper

2 comments
Area_Chair_1NehOpenReview ↗

Reviewers: please read and comment on author's feedback, and consider editing your rating.

Dear Reviewers,

The authors have replied to your reviews. Does the author solve your concerns? Please respond to the author and consider editing your rating. The author-reviewer discussion phase will end on November 18 at 11:59pm AoE. Thanks.

AC

AuthorsOpenReview ↗

Summary of Revisions

We thank the Area Chair for coordinating the rebuttal process. We also thank the reviewers for their time and constructive comments. We have improved our manuscript following the reviewers' suggestions. As all three reviewers suggested comparing our methods with accelerated baselines in the experiments, we first clarify how our methods differ from the baselines. It is true that APG [1] and AC-FGM [2] do not require prior knowledge of ℓ\ell, but both of them depend on function value to estimate local curvature. Our methods use the ℓ\ell-smoothness condition to bound the curvature along the trajectory, so appropriate stepsize can be selected without function-value evaluations. Using the same condition, we also obtain an accelerated rate whose leading term depends on curvature bound at the optimal solution ℓ(τ⋆)\ell(\tau_\star). Below is a summary of the major updates we have made.

1. New experiments with baselines.

We have conducted new experiments with 1000-dimensional convex and strongly convex problems with different values of τ∗\tau_*. As advised by the reviewer, we compare our proposed algorithms with APG [1] and AC-FGM [2]. We present both gradient calls and CPU time, where CPU time includes all algorithm costs when solving the problems, including the backtracking step in APG, curvature estimation step in AC-FGM and the integral and inversion calculations in our proposed algorithms. The results show that even though these compared algorithms have similar performance with respect to gradient oracles, the consumed CPU times are different. Such results indicate that our algorithms are more efficient than the two compared baselines in these problems.

2. Initialization and algorithmic explanations.

We have added a finite warm-start lemma to remove the initial-gap restriction in the strongly convex method. This only adds a cost independent of the target accuracy and preserves the leading convergence rate. We have also clarified the positive initialization requirement and added a remark explaining how the adaptive method can be combined with restarts. In our responses, we explain the roles of QτQ_\tau and PcP_c and explain how the scalar integrals and their inverses are computed in our implementation. Furthermore, the numerical experiments also show that these two operators are not the bottleneck of our algorithms.

3. Theoretical comparisons and attribution.

We have clarified in the response how our curvature dependence differs from APG and AC-FGM, whose bounds use curvature information over a larger region or along the trajectory. Our methods require more problem information, but separate an accuracy-independent startup cost from the leading term governed by ℓ(τ⋆)\ell(\tau_\star). We have explicitly acknowledged the connection of the integral inequality to Tyurin's result and added AC-FGM [2] and Yu et al. [3] to the related work. We have also improved our presentation following the reviewers' suggestions.

[1] 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.

[2] Tianjiao Li and Guanghui Lan. A Simple Uniformly Optimal Method without Line Search for Convex Optimization. Mathematical Programming, 219:219–256, 2026.

[3] Dingzhi Yu, Wei Jiang, Hongyi Tao, Yuanyu Wan, and Lijun Zhang. Mirror Descent Under Generalized Smoothness. Proceedings of the 43rd International Conference on Machine Learning, 2026.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.