acceptodds
Under review as a conference paper at ICLR 2027

A Few Accelerated Algorithms for Convex Optimization under -Smoothness

Abstract

We develop accelerated algorithms for convex -smooth optimization, where . This class generalizes standard smoothness and contains the -smooth class. The technical challenge is to combine acceleration with the resulting local quadratic model: every trial step must remain within its validity radius. Combining this condition with accelerated coupling and phase restarts, we obtain the full-gradient complexity . We extend the same approach to randomized coordinate methods, obtaining the corresponding uniform rate with the standard factor , and a non-uniform rate governed by . These results provide, to our knowledge, the first accelerated full-gradient and coordinate guarantees for this convex class. Experiments support the predicted acceleration and the advantage of non-uniform sampling.

Primary area:
optimization
Keywords:
Accelerated Algorithms, Convex Optimization, $(H_0, H_1)$-Smoothness, Full-Gradient and Coordinate Guarantees

Reviews

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

This paper studies convex (H0,H1)(H_0, H_1)-smooth minimization, a problem class that generalizes the convex (L0,L1)(L_0, L_1)-smooth minimization. It develops a Nesterov-type accelerated scheme adjusted to local curvature bound for the (H0,H1)(H_0, H_1)-smooth function class, and combines it with a general restart meta-algorithm to achieve an accelerated complexity. It also extends the accelerated complexity to a coordinate method.

Critical strengths

(L0,L1)(L_0, L_1)-smooth problems have recently become a popular setting in the intersection of ML and optimization, and this paper is studying an even more generalized type of smoothness, which is relevant and perhaps interesting to researchers working in this area.

I have not seen a prior work claiming acceleration for (H0,H1)(H_0, H_1)-smooth optimization, so the paper's claim that they first achieve acceleration for this problem class is probably correct. If that is the case, the complexity analysis itself would be a solid technical contribution.

Critical weaknesses

My first main concern is whether this paper is providing a substantially novel insight or impact. The Algorithm 2, the main inner loop of the proposed acceleration framework, seems like an adaptation of AGMsDR from [1, Section 6] where the choice of MkM_k is adjusted so that the curvature control for (H0,H1)(H_0, H_1)-smooth function class can be applied. While this high-level idea is simple and seems sound, it is not clear if this is a fundamentally new insight. Furthermore, the nature of the result itself is a generalization of a previously known phenomenon from (L0,L1)(L_0, L_1)- to (H0,H1)(H_0, H_1)-smooth setting, and it is questionable whether that generalization is significant; the paper does explain that there are functions that belong to the (H0,H1)(H_0, H_1) class but not to the (L0,L1)(L_0, L_1) class, but what is the practical relevance of those functions? It is also notable that while the paper's result is applicable to (L0,L1)(L_0, L_1)-smooth problems with H0=L0+L0L1H_0 = L_0 + L_0 L_1 and H1=(4L12+L1)/2H_1 = (4L_1^2 + L_1) / 2, then it displays a rather worse dependence on the parameters L0L_0 and L1L_1 compared to the result of [1]. Hence, the benefit of this result seems to be really confined to the (H0,H1)∖(L0,L1)(H_0, H_1) \setminus (L_0, L_1) class, which seems narrow.

Second, as a related point, it is unclear why Algorithm 1 (Restart Meta-Algorithm) is needed. I think at least the acceleration result of Section 4.1 can be proved without the need of double-loop structure, considering that it seems to share the same analytical backbone with AGMsDR. Is this not the case? Is Algorithm 1 genuinely necessary, and does that represent a new conceptual contribution of this work?

Finally, Algorithms 2 and 3 involve the computation of yk∈argminy∈[xk,vk]f(y)y_k \in \mathrm{argmin}_{y \in [x_k, v_k]} f(y), which can, of course, be computed efficiently but still is possible only up to a numerical error. The main paper does not explain how convergence analysis is affected by, or could control, the accumulation of those errors. The appendix seems to have a related explanation, but I think this is something that should be explained within the main paper.

A side note here: The paper denotes the argmin operation as yk∈argminβ∈[0,1]f(vk+β(xk−vk))y_k \in \mathrm{argmin}_{\beta \in [0,1]} f(v_k + \beta(x_k - v_k)), but this notation seems to require a fix because yky_k is not the minimizing β\beta itself.

[1] Daniil Vankov, Anton Rodomanov, Angelia Nedich, Lalitha Sankar and Sebastian U Stich. Optimizing (L0,L1)(L_0, L_1)-Smooth Functions by Gradient Methods. ICLR, 2025.

Questions for authors

Please refer to the Weaknesses section, which already includes all the main points that would materially affect my rating.

4 comments

Dear Reviewer SGQy,

Thank you for your careful review and for raising fundamental questions about the novelty of the method, the role of restarts, and the segment minimization. These comments motivated us to redesign the algorithms and develop a new unified analysis. We provide detailed responses below.

My first main concern is whether this paper is providing a substantially novel insight or impact. The Algorithm 2, the main inner loop of the proposed acceleration framework, seems like an adaptation of AGMsDR from [1, Section 6] where the choice of MkM_k is adjusted so that the curvature control for (H0,H1)(H_0,H_1)-smooth function class can be applied. While this high-level idea is simple and seems sound, it is not clear if this is a fundamentally new insight. Furthermore, the nature of the result itself is a generalization of a previously known phenomenon from (L0,L1)(L_0,L_1)- to (H0,H1)(H_0,H_1)-smooth setting, and it is questionable whether that generalization is significant; the paper does explain that there are functions that belong to the (H0,H1)(H_0,H_1) class but not to the (L0,L1)(L_0,L_1) class, but what is the practical relevance of those functions? It is also notable that while the paper's result is applicable to (L0,L1)(L_0,L_1)-smooth problems with H0=L0+L0L1H_0=L_0+L_0L_1 and H1=(4L12+L1)/2H_1=(4L_1^2+L_1)/2, then it displays a rather worse dependence on the parameters L0L_0 and L1L_1 compared to the result of [1]. Hence, the benefit of this result seems to be really confined to the (H0,H1)∖(L0,L1)(H_0,H_1)\setminus(L_0,L_1) class, which seems narrow.

Thank you for raising this central question. We agree that the novelty should be distinguished clearly from the standard components of acceleration. The coupling point yky_k follows the classical Nesterov (1983, 2012) construction, while the two-regime weight principle is related to El Bakkali El Kadi and Gorbunov (2026). Our new contribution is the realized-displacement correction that makes acceleration possible under gap-dependent curvature without evaluating the gap or solving a segment-minimization problem.

To explain the key obstacle, let

\qquad q_k=H_1b_k^2||v_{k+1}-v_k||^2.$$ After coupling the primal and auxiliary sequences, the potential estimate contains the coefficient $$B_k-a_k-\frac{q_k}{a_k}$$ in front of $F(y_k)$. With the standard choice $a_k=B_k$, this coefficient is negative, leaving an uncontrolled positive contribution depending on the unknown gap. We instead set $$a_k=B_k-\frac{c_kq_k}{B_k}.$$ Consequently, $$B_k-a_k-\frac{q_k}{a_k} = \frac{q_k}{B_k} \left(c_k-\frac{B_k}{a_k}\right) \geq 0,$$ because the analysis proves $a_k\geq3B_k/4$ and uses $c_k\geq4$. Thus, the observed displacement $v_{k+1}-v_k$ absorbs the gap-dependent curvature without computing $F(y_k)$, performing line search, or solving an inner optimization problem. This is established in equations (31)–(35) of Appendix C. The correction creates a second difficulty because the corrected weight $a_k$ may decrease. We address it through the accepted-weight safeguard $$A_{k+1}=\max [A_0,a_k],$$ the corresponding averaging with $x^0$, and a normalized potential argument. The resulting analysis is not obtained by substituting an $(H_0,H_1)$ curvature bound into the existing AGMsDR proof. It derives a new one-step potential inequality, proves that the realized correction preserves $a_k\geq3B_k/4$, controls the possible decrease of the accepted weights through a normalized potential, and extends the same argument to randomized coordinate blocks. This unified analysis is the main technical contribution of Appendix C. Algorithm 4 and Appendix C show that this mechanism applies uniformly to the full-gradient, uniform-coordinate, and non-uniform-coordinate methods. This yields the single-loop guarantees in Theorems 5, 6, 9, and 12 using one gradient or partial-derivative query per iteration, without restarts, function-value queries, or segment minimization. The new lower bound in Theorem 7 further supports the significance of the resulting $H_1$ dependence. Proposition 10 and Examples 3–4 establish that the $(H_0,H_1)$ class strictly contains the $(L_0,L_1)$ class. Propositions 17 and 18 further show that the general $(H_0,H_1)$-smooth and $\ell$-smooth classes are incomparable. Section 7 explicitly acknowledges that the sufficient $(L_0,L_1)\to(H_0,H_1)$ conversion does not recover AGMsDR’s sharper specialized $L_1$ dependence. Recovering this dependence without segment search while retaining guarantees for the broader $(H_0,H_1)$ class is an important direction for future work. The benefit is also not restricted to functions outside the $(L_0,L_1)$ class. On the real-data problems in Section 6, our search-free method achieves the lowest total oracle count in all 10 tested initializations and the lowest runtime in 9 cases, despite AGMsDR having the sharper specialized $(L_0,L_1)$ guarantee. (Part 1/2)

Second, as a related point, it is unclear why Algorithm 1 (Restart Meta-Algorithm) is needed. I think at least the acceleration result of Section 4.1 can be proved without the need of double-loop structure, considering that it seems to share the same analytical backbone with AGMsDR. Is this not the case? Is Algorithm 1 genuinely necessary, and does that represent a new conceptual contribution of this work?

The restart meta-algorithm has been completely removed. Revised Algorithms 1–4 are single-loop methods. The new unified analysis in Appendix C proves Theorems 5, 6, 9, and 12 directly, without a double-loop structure. The key new mechanism is the realized-displacement correction of the acceleration weight together with the accepted-weight safeguard.

Finally, Algorithms 2 and 3 involve the computation of yk∈argmin⁡y∈[xk,vk]f(y)y_k\in\operatorname{argmin}_{y\in[x_k,v_k]}f(y), which can, of course, be computed efficiently but still is possible only up to a numerical error. The main paper does not explain how convergence analysis is affected by, or could control, the accumulation of those errors. The appendix seems to have a related explanation, but I think this is something that should be explained within the main paper.

This issue has been eliminated. The revised algorithms contain no inner optimization problem or line search. They use the explicit coupling point yk=Akxk+bkvkAk+bk.y_k=\frac{A_kx_k+b_kv_k}{A_k+b_k}. Therefore, no line-search errors accumulate, and every iteration requires only one full-gradient or partial-derivative query.

A side note here: The paper denotes the argmin operation as yk∈argmin⁡β∈[0,1]f(vk+β(xk−vk))y_k\in\operatorname{argmin}_{\beta\in[0,1]}f(v_k+\beta(x_k-v_k)), but this notation seems to require a fix because yky_k is not the minimizing β\beta itself.

Thank you for identifying this inconsistency. The argmin operation has been removed, and yky_k is now defined directly as a point in Rd\mathbb{R}^d by the explicit formula above.

Best regards,
The Authors

(Part 2/2)

I thank the authors for the detailed response and the revision. The revised framework with restart meta-algorithm and 1D minimization over line segment removed, if correct, would address my second and third main concerns. That said, this entirely replaces the original algorithm and analysis, substantially altering the technical contribution of the paper, and I am not sufficiently confident in providing a full assessment in limited time window within the short discussion period. I therefore believe the paper requires a fresh round of review process.

My concern about the significance of the contribution also remains. I do acknowledge the new technical ingredients, but I am not strongly persuaded by the rebuttal that the paper's advance over existing acceleration frameworks is significant enough. I am also aware that the (H0,H1)(H_0, H_1) class strictly contains the (L0,L1)(L_0, L_1) class, but the rebuttal rather acknowledges that their proposed analysis for the broader class worsens the parameter dependence on the (L0,L1)(L_0, L_1) subclass compared to prior work AGMsDR. It also does not address my concern that the (H0,H1)∖(L0,L1)(H_0, H_1) \setminus (L_0, L_1) class, where the theoretical benefit is confined to, seems narrow. Further, the authors claim that their experiments demonstrate the benefit is visible within the (L0,L1)(L_0, L_1) class, but as they only consider the two closely related generalized linear model settings, I believe this provides limited evidence.

Overall, I maintain my current score and encourage resubmission, so that the substantially redesigned theory can receive a full review.

Dear Reviewer SGQy,

Thank you for your thoughtful follow-up. We appreciate your acknowledgment that the updated framework addresses your concerns regarding restarts and segment minimization, and we understand the limited time available to examine the new analysis.

We would like to clarify several points that we believe are important for assessing the contribution.

First, the changes directly address the central questions raised in your original review. You questioned the necessity of the restart framework, the technical novelty beyond AGMsDR, and the accumulation of errors from segment minimization. Addressing these interconnected issues motivated the development of the search-free algorithms and their unified analysis.

Importantly, the central research question remains unchanged: obtaining accelerated full-gradient and coordinate guarantees for convex (H0,H1)(H_0,H_1)-smooth optimization. The original submission already established such guarantees; the updated framework addresses their algorithmic and practical limitations rather than introducing a different optimization problem.

Second, the new technical contribution is not merely an adaptation of AGMsDR with a different curvature bound. The realized-displacement correction controls the gap-dependent curvature contribution without evaluating f⋆f^\star, querying function values, or performing segment minimization. Combined with the accepted-weight safeguard and normalized potential analysis, it yields a common acceleration mechanism for full-gradient, uniform-coordinate, and non-uniform-coordinate methods. The new lower bounds also establish optimality of the polynomial H1H_1-dependence up to logarithmic factors.

Third, regarding significance, we agree that the sufficient conversion from (L0,L1)(L_0,L_1)- to (H0,H1)(H_0,H_1)-smoothness does not recover AGMsDR's sharper specialized L1L_1-dependence. However, the theoretical generality of the function class and the computational advantages of the algorithm are distinct contributions. In particular, the elimination of inner optimization problems is beneficial even within the (L0,L1)(L_0,L_1) subclass.

The real-data experiments directly examine this practical advantage. Using certified smoothness parameters and counting all oracle calls, the updated method achieves the lowest oracle complexity across all ten tested initializations and the lowest runtime in nine. We agree that two related generalized linear models cannot establish universal superiority; our empirical claim is limited to the evaluated settings. Nevertheless, these results demonstrate that the algorithmic improvements have practical consequences beyond the strict difference between the smoothness classes.

Finally, the ICLR 2027 guidelines explicitly permit revisions to the manuscript's content during the discussion period, while the Reviewer Guidelines call for new information and revisions to be considered in the final assessment. The changes were motivated by the concerns raised during review, and we have documented their technical details and supporting arguments.

We respect the need for careful verification of the updated proofs. At the same time, we respectfully hope that the scientific contributions already present in the original submission, together with the concrete improvements addressing your concerns, will receive due consideration in the final recommendation.

Thank you again for your constructive feedback and careful consideration.

Best regards,

The Authors

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

The paper studies the class of convex (H0,H1)(H_0, H_1)-smooth functions. The authors propose full-gradient and coordinate gradient accelerated methods in this setup, using Accelerated Gradient Method with Small-Dimensional Relaxation and restart technique. They establish accelerated convergence rates for the full-gradient method and coordinate methods with uniform and non-uniform sampling. Authors show that the class of convex (H0,H1)(H_0, H_1)-smooth functions is strictly broader than (L0,L1)(L_0, L_1)-smooth convex class and incomparable with the general ℓ\ell-smooth convex class.

Critical strengths
  1. The paper establishes accelerated convergence guarantees for the broader class of convex (H0,H1)(H_0, H_1)-smooth functions, extending existing results for generalized smoothness.
  2. The authors propose accelerated coordinate methods with both uniform and non-uniform sampling, which is an interesting theoretical contribution.
Critical weaknesses
  1. Application of the proposed theory:
  • It is not clear whether (H0,H1)(H_0, H_1)-class has any practical examples that lie outside (L0,L1)(L_0, L_1) or ℓ\ell smoothness. Motivating examples 3 and 4 are already covered by ℓ\ell smoothness, and the only example outside ℓ\ell-smoothness is construction of Proposition 19. While authors prove that (H0,H1)(H_0, H_1) smoothness assumption is weaker than (L0,L1)(L_0, L_1), the convergence guarantee for a full gradient method is weaker than AGMsDR on (L0,L1)(L_0, L_1) class. I think this should be explicitly discussed after Theorem 5. Moreover, it is also not clear whether the paper improves the convergence guarantees for functions in examples 3 and 4, as both of them are strongly convex, while Theorem 5 does not use strong convexity.
  • Full gradient algorithm requires 4 theoretical hyperparameters: H0,H1,f∗,R~H_0, H_1, f^\ast, \tilde{R}. While the authors show how to remove R~\tilde{R} from algorithm input by doubling the number of iterations in each restart phase, it still requires exact value of f∗f^\ast, which is a significant limitation. In general, the use of restarts and, moreover, doubling scheme raises further questions about practicality. See the next weakness, as these issues seem to affect the experimental performance.
  • The coordinate method involves full dimensional operations: line search and estimating F(yk)F(y_k). The iteration cost of coordinate algorithm is not discussed, and it is unclear why these full-dimensional updates do not destroy the attractive iteration cost of coordinate method.
  1. Experiments
  • The comparison with AGMsDR in Section 5 dos not seem fair. The authors set L0=LglobalL_0 = L_{global} and L1=0L_1 = 0 for AGMsDR. However, L1L_1 corresponds to the fast linear convergence, so one may want to choose L1L_1 as large as possible to obtain a smaller L0L_0. For their own method the authors use H1≠0H_1 \neq 0, which makes comparison unfair.
  • The experiment in Figure 2 in Appendix F shows that Frozen FGM outperforms the proposed method in both FO oracle calls and running time, which highlight the practicality issues of the proposed restarted scheme. No wall-clock comparision is performed with coordinate methods.
  • The experiments with coordinate methods only compare the proposed uniform and non-uniform sampling. There is no comparison with existing accelerated coordinate method
  1. The paper has sone typos and small issues:
  • In the abstract and intro F0,R~,RF_0, \tilde{R}, R and Hj,iH_{j, i} are used before being defined.
  • Line 202-203. Proposition B.1 of Alimisis et al (2025) holds only with ν=e−ν\nu = e^{-\nu}.
  • Line 3 of Algorithms 2-4, and line 1050. Argmin is taken over scalar βk\beta_k, so it is incorrect to write that yky_k belongs to this argmin.
  • Line 1040 “Equation equation”.
Questions for authors
  1. Why is equation (22) not enough to obtain the convergence guarantee without restarts?
  2. What is the iteration cost of Algorithm 3? Can the line-search in the line 3 be implemented at the cost of coordinate gradient update?
  3. Why is the line 5 needed in Algorithm 2? Why not just set Mk=M^kM_k = \hat{M}_k?
  4. Line 80. Why is the rate in lines 82-83 chosen as the goal of the paper? Is it optimal or somewhat expected?
  5. In standard analysis of GD step size is usually constrained from one side. In algorithms in the paper, MkM_k has to be bounded from both sides. Are they necessary for convergence?
4 comments

Dear Reviewer 3Jog,

Thank you for your careful and technically detailed review. Your questions about the scope of the theory, required parameters, iteration costs, and experimental baselines motivated substantial improvements to the paper. We provide detailed responses to your questions and comments below.

It is not clear whether (H0,H1)(H_0,H_1)-class has any practical examples that lie outside (L0,L1)(L_0,L_1) or ℓ\ell smoothness. Motivating examples 3 and 4 are already covered by ℓ\ell smoothness, and the only example outside ℓ\ell-smoothness is construction of Proposition 19. While authors prove that (H0,H1)(H_0,H_1) smoothness assumption is weaker than (L0,L1)(L_0,L_1), the convergence guarantee for a full gradient method is weaker than AGMsDR on (L0,L1)(L_0,L_1) class. I think this should be explicitly discussed after Theorem 5. Moreover, it is also not clear whether the paper improves the convergence guarantees for functions in examples 3 and 4, as both of them are strongly convex, while Theorem 5 does not use strong convexity.

Proposition 10 proves that every convex (L0,L1)(L_0,L_1)-smooth function is (H0,H1)(H_0,H_1)-smooth, while Examples 3 and 4 provide the reverse separation. Together, these results establish that (H0,H1)(H_0,H_1)-smoothness is strictly weaker than (L0,L1)(L_0,L_1)-smoothness. Proposition 16 shows that Examples 3 and 4 are also generally ℓ\ell-smooth. Their purpose is class separation, and we do not claim a strong-convexity-specific rate for them.

Propositions 17 and 18 establish both directions of incomparability with general ℓ\ell-smoothness. Proposition 17 gives an ℓ\ell-smooth function that is not (H0,H1)(H_0,H_1)-smooth, while Proposition 18 gives an (H0,H1)(H_0,H_1)-smooth function that is not ℓ\ell-smooth. Thus, neither general class contains the other.

Section 7 now explicitly states that the sufficient (L0,L1)→(H0,H1)(L_0,L_1)\to(H_0,H_1) conversion does not recover AGMsDR's sharper L1L_1 dependence. Recovering this dependence without segment search while retaining guarantees for the broader (H0,H1)(H_0,H_1) class is an important direction for future work.

Full gradient algorithm requires 4 theoretical hyperparameters: H0,H1,f∗,R~H_0,H_1,f^\ast,\widetilde{R}. While the authors show how to remove R~\widetilde{R} from algorithm input by doubling the number of iterations in each restart phase, it still requires exact value of f∗f^\ast, which is a significant limitation. In general, the use of restarts and, moreover, doubling scheme raises further questions about practicality.

This limitation has been removed. Revised Algorithms 1–4 are single-loop methods that require neither f∗f^\ast, restarts, nor a doubling scheme. They use upper bounds R≥∣∣x0−x∗∣∣R\geq||x^0-x^\ast|| and Δ0≥f(x0)−f∗\Delta_0\geq f(x^0)-f^\ast. By convexity, the computable choice $ \Delta_0=R||\nabla f(x^0)|| $ is valid without knowing f∗f^\ast. Theorem 5 gives

\sqrt{\frac{H_0 R^2}{\varepsilon}} + (1+\sqrt{H_1 R^2}) \left(1+\log\frac{\Delta_0}{\varepsilon}\right) \right)$$ full-gradient calls. For fixed $\Delta_0$, this preserves the asymptotic rate $$O\left( \sqrt{\frac{H_0 R^2}{\varepsilon}} + \sqrt{H_1 R^2}\log\frac{1}{\varepsilon} \right).$$ Moreover, the new lower bound in Theorem 7 shows that the polynomial dependence $\sqrt{H_1R^2}$ cannot be improved beyond logarithmic factors for the considered methods. > **The coordinate method involves full dimensional operations: line search and estimating $F(y_k)$. The iteration cost of coordinate algorithm is not discussed, and it is unclear why these full-dimensional updates do not destroy the attractive iteration cost of coordinate method.** Revised Algorithms 2 and 3 perform no line search and do not evaluate $F(y_k)$. Each iteration uses exactly one partial-derivative query. Thus, the expensive full-gradient and function-value queries are eliminated, while the remaining arithmetic cost is now stated explicitly. > **The comparison with AGMsDR in Section 5 dos not seem fair. The authors set $L_0=L_{\mathrm{global}}$ and $L_1=0$ for AGMsDR. However, $L_1$ corresponds to the fast linear convergence, so one may want to choose $L_1$ as large as possible to obtain a smaller $L_0$. For their own method the authors use $H_1\neq0$, which makes comparison unfair.** We agree and completely replaced this configuration. AGMsDR is now run with the certified nonzero parameters $(L_0,L_1)=(2.01,2)$, and every method receives its valid global constants. In Table 2, our method has the lowest total oracle count for all 10 initializations and the lowest wall-clock time for 9 of 10 initializations. (Part 1/2)

The experiment in Figure 2 in Appendix F shows that Frozen FGM outperforms the proposed method in both FO oracle calls and running time, which highlight the practicality issues of the proposed restarted scheme. No wall-clock comparision is performed with coordinate methods.

The revised method is single-loop and restart-free. In the new direct comparison on covtype.binary, it reaches the target using 51 oracle calls and 54.4 ms, compared with 111 calls and 100.8 ms for Frozen FGM (Table 3). Wall-clock coordinate comparisons are now reported in Tables 4 and 5.

The experiments with coordinate methods only compare the proposed uniform and non-uniform sampling. There is no comparison with existing accelerated coordinate method.

Appendix E.2 now compares both proposed variants with ACDM from Nesterov and Stich (2017). Tables 4 and 5 report coordinate-oracle calls and wall-clock time over seven random seeds. The proposed non-uniform method achieves the best oracle complexity and runtime in every reported configuration.

In the abstract and intro F0,R~,RF_0,\widetilde R,R and Hj,iH_{j,i} are used before being defined.

All quantities are now defined before their first use.

Line 202–203. Proposition B.1 of Alimisis et al. (2025) holds only with ν=e−ν\nu=e^{-\nu}.

Thank you for identifying this issue. We removed the incorrect substitution and replaced it with an independent proof based on the gradient self-bound. The corrected result is Proposition 10 in Appendix B.1.

Line 3 of Algorithms 2–4, and line 1050. Argmin is taken over scalar βk\beta_k, so it is incorrect to write that yky_k belongs to this argmin.

The segment minimization has been eliminated. The revised algorithms define the vector directly as yk=Akxk+bkvkAk+bk,y_k=\frac{A_kx_k+b_kv_k}{A_k+b_k}, so the scalar/vector inconsistency and the corresponding numerical subproblem no longer arise.

Line 1040 “Equation equation”.

Corrected. Thank you.

Why is equation (22) not enough to obtain the convergence guarantee without restarts?

In the revised paper, we propose a new algorithm together with a unified analysis that no longer relies on equation (22). The new framework requires neither restarts nor inner optimization problems and covers the full-gradient, uniform-coordinate, and non-uniform-coordinate methods. The corresponding guarantees are established directly in Theorems 5, 6, 9, and 12.

What is the iteration cost of Algorithm 3? Can the line-search in the line 3 be implemented at the cost of coordinate gradient update?

The revised Algorithm 3 has no line search. Each iteration requires one partial-derivative query. Therefore, its oracle cost is exactly one coordinate query per iteration.

Why is the line 5 needed in Algorithm 2? Why not just set Mk=M^kM_k=\widehat M_k?

For the former algorithm, setting Mk=M^kM_k=\widehat M_k was sufficient. The interval only permitted other admissible choices. The revised Algorithm 1 removes both quantities and adjusts the acceleration weight directly using the realized auxiliary displacement.

Line 80. Why is the rate in lines 82–83 chosen as the goal of the paper? Is it optimal or somewhat expected?

The target rate is motivated by the expected effect of acceleration on both curvature components. When H1=0H_1=0, the problem reduces to classical H0H_0-smooth convex optimization, for which the optimal accelerated term is $ O\left(\sqrt{\frac{H_0 R^2}{\varepsilon}}\right). $ For the H1H_1 component, the non-accelerated dependence is proportional to H1R2H_1R^2, so acceleration suggests the square-root dependence H1R2\sqrt{H_1R^2}, analogous to the square-root improvement of the condition-number term in strongly convex optimization. Our upper bound achieves $ O\left( R\sqrt{\frac{H_0}{\varepsilon}} + R\sqrt{H_1}\log\frac{\Delta_0}{\varepsilon} \right). $ The new lower bound in Theorem 7 confirms this expectation by showing that the polynomial dependence H1R2\sqrt{H_1R^2} cannot be improved beyond logarithmic factors for the considered oracle models.

In standard analysis of GD step size is usually constrained from one side. In algorithms in the paper, MkM_k has to be bounded from both sides. Are they necessary for convergence?

In the former analysis, the lower bound ensured validity of the local descent model, while the upper bound ensured sufficient growth of the acceleration weights and was needed for the stated accelerated rate, rather than for convergence alone. The revised algorithms eliminate MkM_k entirely and use a realized-displacement correction together with an accepted-weight safeguard.

Best regards,
The Authors

(Part 2/2)

Dear authors,

I appreciate your efforts to address my concerns, including removing the line search and restarts.

However, the revised manuscript is substantially different from the original submission. Six out of ten pages of the main text are highlighted in blue. The main algorithms have been replaced, and new proofs and lower bounds have been introduced.

I feel like I am reviewing a new paper. Thus, I recommend resubmission.

Dear Reviewer 3Jog,

Thank you for your follow-up and for acknowledging our efforts to address your concerns. We appreciate the limited time available to examine the updated analysis.

We would like to respectfully emphasize that the changes were introduced specifically to address the central weaknesses identified in your original review, rather than to pursue a different research direction.

In particular, your review questioned the necessity of restarts, the dependence on the unknown f⋆f^\star, the computational cost of coordinate iterations, and the practical limitations of segment minimization. These issues are closely interconnected, and addressing them together motivated the new single-loop algorithms and unified analysis. We also corrected the AGMsDR comparison and expanded the experiments in direct response to your comments.

Crucially, the central scientific contribution remains the same: obtaining accelerated full-gradient and coordinate guarantees for convex (H0,H1)(H_0,H_1)-smooth optimization. These guarantees were already established in the original submission and explicitly recognized among its strengths in your review. The updated framework addresses the identified limitations while preserving the central accelerated dependence on the smoothness parameters.

The ICLR 2027 Author Guidelines explicitly permit changes to the manuscript's content during the discussion period, and the Reviewer Guidelines call for new information and revisions to be considered when forming final recommendations.

We fully appreciate that verifying the updated proofs requires careful examination. Nevertheless, we respectfully hope that the changes made specifically to address the review will be evaluated in light of the original scientific contribution and the concerns they resolve, rather than primarily by the extent of the modifications.

Thank you again for your time and thoughtful consideration.

Best regards,

The Authors

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

This paper proposes accelerated algorithms for convex (H0,H1)(H_0, H_1)-smooth optimization where ∣∣∇2f(x)∣∣≤H0+H1(f(x)−f∗)||\nabla^2 f(x)||\leq H_0 + H_1(f(x) - f^*). A full-gradient method with iteration complexity O~(H0R~2/ε+H1R~2log⁡(F0/ε))\tilde{\mathcal O}(\sqrt{H_0 \tilde R^2/\varepsilon} +\sqrt{H_1 \tilde R^2} \log(F_0/\varepsilon) ) where R~:=sup⁡x:f(x)≤f(x0)∣∣x−x∗∣∣\tilde R:= \sup_{x: f(x)\leq f(x^0)}||x - x^*|| and F0:=f(x0)−f∗F_0:= f(x^0) - f^*. A randomized coordinate method use O~(dR~(H1/ε+H0log⁡(F0/ε)))\tilde{\mathcal O}(d\tilde R\left(\sqrt{H_1 /\varepsilon} +\sqrt{H_0 } \log(F_0/\varepsilon)\right) ) coordinate-gradient calls where dd denotes the problem size.

Critical strengths

The algorithm obtained the first accelerated complexity separating H0H_0 and H1H_1 for convex (H0,H1)(H_0, H_1)-smooth optimization. For the randomized coordinate method, the convergence rate is the coordinate analogue of the full-gradient accelerated rate.

Critical weaknesses

The algorithm requires the knowledge of f∗=min⁡f(x)f^* = \min f(x) which may not be accessible in general.

Questions for authors
  • Line 3 in Algorithm 2 and Algorithm 3 seems not correct. yky_k should be a point in Rd\mathbb{R}^d rather than a number in [0,1][0,1].

  • x∗,f∗,F0,F(x)x^*, f^*, F^0, F(x) are defined much later after first appearance; LlevL_{\rm{lev}} is defined but not used

3 comments

Dear Reviewer T6wr,

We sincerely thank you for your positive assessment, careful reading, and recognition of the theoretical contributions of our full-gradient and coordinate methods. Your comments helped us improve both the practical applicability and the presentation of the paper. We provide detailed responses to your questions and comments below.

The algorithm requires the knowledge of f∗=min⁡f(x)f^\ast=\min f(x) which may not be accessible in general.

We fully agree that requiring the exact value of f∗f^\ast would be a significant limitation. This requirement has been removed. Revised Algorithms 1–4 are single-loop methods that require neither f∗f^\ast, restarts, a doubling scheme, nor inner optimization problems.

The guarantees use upper bounds R≥∣∣x0−x∗∣∣R\geq||x^0-x^\ast|| and Δ0≥f(x0)−f∗\Delta_0\geq f(x^0)-f^\ast. By convexity, the computable choice $ \Delta_0=R||\nabla f(x^0)|| $ is valid without knowing f∗f^\ast. Theorem 5 gives

\sqrt{\frac{H_0 R^2}{\varepsilon}} + (1+\sqrt{H_1 R^2}) \left(1+\log\frac{\Delta_0}{\varepsilon}\right) \right)$$ full-gradient calls. For fixed $\Delta_0$, this preserves the asymptotic rate $$O\left( \sqrt{\frac{H_0 R^2}{\varepsilon}} + \sqrt{H_1 R^2}\log\frac{1}{\varepsilon} \right).$$ Moreover, the new lower bound in Theorem 7 shows that the polynomial dependence $\sqrt{H_1R^2}$ cannot be improved beyond logarithmic factors for the considered methods. > **Line 3 in Algorithm 2 and Algorithm 3 seems not correct. $y_k$ should be a point in $\mathbb{R}^d$ rather than a number in $[0,1]$.** Thank you for identifying this inconsistency. The segment minimization has been completely removed from the revised algorithms. The point is now defined explicitly as $$y_k=\frac{A_kx_k+b_kv_k}{A_k+b_k}\in\mathbb{R}^d.$$ Thus, the scalar/vector inconsistency and the corresponding inner optimization problem no longer arise. > **$x^\ast$, $f^\ast$, $F^0$, $F(x)$ are defined much later after first appearance; $L_{\rm lev}$ is defined but not used.** Thank you for drawing our attention to these presentation issues. All required quantities are now defined before their first use. The unused notation $L_{\rm lev}$ has been removed. Best regards, The Authors

Thank the authors for the response and revision. Removing requiring the exact value of f∗f^* enhance the practical value of the algorithm. However, the revised algorithm is significantly different from the original algorithm and the analysis seems substantially rewritten. My review was based on the original version of the paper. Given short time in the discussion period, I cannot provide a review for the current version of the paper. Therefore, I would encourage resubmission if focusing on this brand new version.

Dear Reviewer T6wr,

Thank you for your follow-up and for recognizing the practical improvement achieved by removing the dependence on f⋆f^\star.

We fully understand your concern about the limited time available to examine the updated algorithms and proofs, and we appreciate your careful assessment of the original submission.

We would only like to emphasize that the changes were motivated by the feedback received during the review process, particularly the dependence on f⋆f^\star identified in your review. Addressing this limitation, together with the related concerns raised by the other reviewers, led us to develop an alternative algorithmic mechanism and analysis.

The central research question remains unchanged: establishing accelerated full-gradient and coordinate guarantees for convex (H0,H1)(H_0,H_1)-smooth optimization. These theoretical contributions were already present in the original submission, while the updated framework aims to strengthen their practical applicability.

We fully appreciate the limited time available for examining the updated analysis. Nevertheless, we sincerely hope that the improvements introduced in response to the reviewers' concerns can be considered in light of the theoretical contributions already established in the original submission, particularly the accelerated full-gradient and coordinate guarantees that remain central to the updated manuscript.

Thank you again for your positive assessment of these original contributions and for your constructive feedback, which helped us strengthen the results and improve their practical applicability while preserving the central scientific objectives of the paper.

Best regards,

The Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to the Reviewers

We sincerely thank all reviewers for their careful reading, constructive feedback, and thoughtful assessment of our work. We particularly appreciate that each reviewer recognized the significance of the main theoretical contributions.

Reviewer T6wr highlighted that

“The algorithm obtained the first accelerated complexity separating H0H_0 and H1H_1 for convex (H0,H1)(H_0,H_1)-smooth optimization. For the randomized coordinate method, the convergence rate is the coordinate analogue of the full-gradient accelerated rate.”

Reviewer 3Jog emphasized that

“The authors propose accelerated coordinate methods with both uniform and non-uniform sampling, which is an interesting theoretical contribution.”

Reviewer SGQy noted that

“I have not seen a prior work claiming acceleration for (H0,H1)(H_0,H_1)-smooth optimization, so the paper's claim that they first achieve acceleration for this problem class is probably correct.”

Motivated by the reviewers’ comments, we have substantially strengthened the paper while preserving its original problem setting and overall structure. The principal changes are summarized below.

  1. We replaced the restart-based framework with new single-loop full-gradient, uniform-coordinate, and non-uniform-coordinate methods. The revised Algorithms 1–4 require neither restarts, a doubling scheme, segment minimization, nor other inner optimization problems. Each iteration uses one full-gradient or partial-derivative query and no algorithmic function-value evaluations.

  2. The new methods use upper bounds R≥∣∣x0−x∗∣∣R\geq||x^0-x^\ast|| and Δ0≥f(x0)−f∗\Delta_0\geq f(x^0)-f^\ast. By convexity, one can use the computable certificate $ \Delta_0=R|\nabla f(x^0)|, $ which does not require knowing f∗f^\ast.

  3. We developed a unified analysis for the new block method in Algorithm 4. The full-gradient and both coordinate methods follow as its special cases. Theorems 5, 6, 9, and 12 establish the corresponding guarantees directly, without restarts or inner optimization errors. In particular, Theorem 5 gives

    O(H0R2ε+(1+H1R2)(1+log⁡Δ0ε))O \left( \sqrt{\frac{H_0 R^2}{\varepsilon}} + (1+\sqrt{H_1 R^2}) \left(1+\log\frac{\Delta_0}{\varepsilon} \right) \right)

    full-gradient calls. For fixed Δ0\Delta_0, this preserves the asymptotic rate

    \right).$$
  4. Theorem 7 establishes lower bounds for the H1H_1-dependent term. They show that the polynomial dependence H1R2\sqrt{H_1R^2} cannot be improved beyond logarithmic factors for the considered oracle models.

  5. Proposition 10 provides a direct proof that every convex (L0,L1)(L_0,L_1)-smooth function is (H0,H1)(H_0,H_1)-smooth. Examples 3 and 4 establish that the reverse inclusion does not hold. Propositions 17 and 18 prove both directions of incomparability between the general (H0,H1)(H_0,H_1)-smooth and ℓ\ell-smooth classes. We also explicitly discuss why the sufficient (L0,L1)→(H0,H1)(L_0,L_1)\to(H_0,H_1) conversion does not recover AGMsDR’s sharper L1L_1 dependence and identify recovering this dependence without segment search as an important direction for future work.

  6. We added experiments on real-data Poisson and Gamma regression problems and now compare with AGMsDR, ℓ\ell-AGD, Accelerated GRAAL, Frozen FGM, and ACDM. AGMsDR is evaluated using certified non-zero (L0,L1)(L_0,L_1) parameters. Our full-gradient method achieves the lowest total oracle count for all 10 tested initializations and the lowest runtime for 9 of them. We also added direct oracle and wall-clock comparisons with Frozen FGM and coordinate comparisons with ACDM over seven random seeds.

  7. We moved all definitions before their first use, removed obsolete notation, corrected the scalar/vector inconsistency in the former segment minimization, and corrected the remaining typographical issues identified by the reviewers.

The overall structure and central objective of the paper remain unchanged. All additions and modifications in the revised manuscript are highlighted in blue for ease of review.

We again thank all reviewers for their valuable comments, which helped us significantly strengthen both the theoretical and experimental parts of the paper.

Best regards,
The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.