- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies convex -smooth minimization, a problem class that generalizes the convex -smooth minimization. It develops a Nesterov-type accelerated scheme adjusted to local curvature bound for the -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
-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 -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 is adjusted so that the curvature control for -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 - to -smooth setting, and it is questionable whether that generalization is significant; the paper does explain that there are functions that belong to the class but not to the class, but what is the practical relevance of those functions? It is also notable that while the paper's result is applicable to -smooth problems with and , then it displays a rather worse dependence on the parameters and compared to the result of [1]. Hence, the benefit of this result seems to be really confined to the 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 , 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 , but this notation seems to require a fix because is not the minimizing itself.
[1] Daniil Vankov, Anton Rodomanov, Angelia Nedich, Lalitha Sankar and Sebastian U Stich. Optimizing -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
Part 2/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 , 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 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 , but this notation seems to require a fix because is not the minimizing itself.
Thank you for identifying this inconsistency. The argmin operation has been removed, and is now defined directly as a point in 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 class strictly contains the class, but the rebuttal rather acknowledges that their proposed analysis for the broader class worsens the parameter dependence on the subclass compared to prior work AGMsDR. It also does not address my concern that the class, where the theoretical benefit is confined to, seems narrow. Further, the authors claim that their experiments demonstrate the benefit is visible within the 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 -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 , 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 -dependence up to logarithmic factors.
Third, regarding significance, we agree that the sufficient conversion from - to -smoothness does not recover AGMsDR's sharper specialized -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 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
Part 1/2
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.
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 yk 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)