- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies parameter-free second-order methods for convex optimization under generalized smoothness and inexact Hessians. It proposes three new algorithms that search for regularized Newton steps satisfying the Monteiro-Svaiter condition. The paper analyzes an adaptive regularized Newton method along with the two accelerated variants.
Critical strengths
The paper provides rigorous convergence bounds on adaptive second-order algorithms with inexact Hessians. Algorithm 3 is parameter-free and achieves the optimal convergence rate for convex second-order optimization with inexact Hessians under classical Lipschitz-Hessian smoothness. The authors develop a new convergence analysis that extends prior results to inexact Hessians and generalized Hessian smoothness.
The paper has an in-depth comparison of their proof techniques against similar work of Carmen et al. (2022) and Chen et al. (2026).
Critical weaknesses
The proposed accelerated parameter-free method is outperformed by the simpler non-accelerated method in the experiments. This raises questions about the practical benefits of the accelerated method, especially given its additional complexity. A comparison in terms of wall-clock time would also be useful to better understand the benefits of the proposed methods. More broadly, while achieving an optimal parameter-free convergence rate is theoretically meaningful, its practical significance is less convincing when the accelerated method does not outperform the simpler baseline.
A minor point: the algorithms still require an initial regularization parameter . Moreover, the experiments initialize this parameter using the local Hessian smoothness constant . While Appendix G.2 studies sensitivity to initialization for Algorithm 2, analogous experiments are missing for the main accelerated method (Algorithm 3).
Questions for authors
Can the authors provide any intuition on why the accelerated method is outperformed by the non-accelerated method in the logistic regression experiments?
Most practical ML algorithms use stochastic gradient information. Can the authors comment on whether the algorithms and analysis can be adapted to the stochastic setting?
4 comments
part 2
Weakness and Question 1 about Slow Optimal Acceleration
The proposed accelerated parameter-free method is outperformed by the simpler non-accelerated method in the experiments. This raises questions about the practical benefits of the accelerated method, especially given its additional complexity.
More broadly, while achieving an optimal parameter-free convergence rate is theoretically meaningful, its practical significance is less convincing when the accelerated method does not outperform the simpler baseline.
Can the authors provide any intuition on why the accelerated method is outperformed by the non-accelerated method in the logistic regression experiments?
Answer:
First, we would like to emphasize that the non-accelerated method (Algorithm 2) is also a contribution of this paper, not an existing baseline. While simpler than the accelerated method, it is based on several nontrivial ideas, which we explain in the new Appendix I.
The phenomenon of non-accelerated methods outperforming accelerated ones was also observed by Carmon et al. (2022), as discussed in Section 4 and the Limitations section of their paper. Moreover, our original submission already included experiments where acceleration outperforms non-accelerated methods (Appendix G.2 in original submission, in revised version its the first three columns in Figure 3 Appendix H.2).
We see two main reasons why the non-accelerated method is faster in Figure 1.
-
Local strong convexity. Logistic regression with a full-column-rank data matrix is strongly convex near the solution. It is well known, for both first- and second-order methods, that non-accelerated methods adapt to strong convexity automatically and switch to fast local convergence. For example, gradient descent with step size adapts to strong convexity automatically. Without any knowledge of , it converges linearly with iteration complexity . Accelerated methods do not have this property. If their parameters are chosen for the merely convex case, they guarantee only the sublinear rate (for Accelerated Gradient Method: ), so for small target accuracy they become slower than plain gradient descent. To reach the accelerated complexity , an accelerated method needs either an estimate of [1] or a restart strategy [2, 3, 4]. Adaptive restart schemes reset the momentum based on observed progress [2, 3]. The same idea is valid for second-order accelerations. This agrees with our theoretical results in Section 3.2.
-
Worst-case safeguards and memory. Accelerated methods are designed for the worst case. Their parameters, safeguards and accumulated memory (momentum) are chosen so that the convergence guarantee holds for every function in the class. When the function has a better structure than assumed, these safeguards can slow the method down in practice. Section 3 of [5] shows that this happens even for classical acceleration. Adaptive non-accelerated methods have no memory: each step depends only on local information at the current point, so they can immediately use a better local structure.
When acceleration helps. For convex functions without local strong convexity or other favorable structure, the accelerated methods can be faster than the non-accelerated ones. This can be seen in Figure 2c for the norm function and in Appendix H.2 for , , and . We have also added experiments on Nesterov’s second-order lower-bound function (Appendix H.3, Figures 4,5). There, the accelerated methods are faster for , which is the sublinear regime of the lower bound.
Practical significance. In practice one usually does not know in advance whether the problem has a favorable local structure. The accelerated method guarantees the optimal rate on hard instances without any parameter tuning, while the non-accelerated method is preferable when local strong convexity is expected.
We therefore see the two methods as complementary.
In summary:
- Adaptive accelerated methods are faster on the classes of functions for which the theory predicts acceleration.
- Adaptive non-accelerated methods can be faster when the function has a better local structure than assumed, for example local strong convexity.
part 3
Minor point
A minor point: the algorithms still require an initial regularization parameter . Moreover, the experiments initialize this parameter using the local Hessian smoothness constant . While Appendix G.2 studies sensitivity to initialization for Algorithm 2, analogous experiments are missing for the main accelerated method (Algorithm 3).
Answer:
Indeed, our methods require an initial regularization parameter but it can be chosen arbitrarily. Our theoretical convergence guarantees hold for any , without requiring knowledge of the smoothness constants or Hessian inexactness level.
In the experiments, we initialize using the local smoothness constant only to ensure a fair comparison, so that the methods start with comparable initial trial steps. This information is not required by our algorithms.
We have also extended the sensitivity experiments to accelerated methods in Appendix H.4 (Figures 6-7).
Question 2
Most practical ML algorithms use stochastic gradient information. Can the authors comment on whether the algorithms and analysis can be adapted to the stochastic setting?
Answer:
Incorporating stochastic gradients is indeed a practical and natural extension of our work.
One way to do this is by subsampling. In the revision (Section 3.1, Appendix D), we show that our basic method allows inexact gradients satisfying . This doesn't come for free: preserving the convergence rate of Theorem 3.1 requires an upper bound on the level-set radius, allowing us to set . Then, the required inexact gradient accuracy can be translated into a batch size via standard concentration inequalities, similarly to ([6], Section 4) or Agafonov et al. (2024a, Section 7).
A more interesting and ambitious goal is to exploit gradient unbiasedness to obtain a decreasing stochastic term , rather than the fixed error floor . Such guarantees have been achieved by Extra-Newton (Antonakopoulos et al., 2022) and ACSN (Agafonov et al., 2024b). Extending these results to our setting would require combining four ingredients: generalized Hessian smoothness, inexact Hessians, adaptivity, and stochastic gradients. This is nontrivial, as the MS backtracking decisions depend on noisy gradient estimates, while the generalized smoothness constant itself depends on the gradient norm. We leave this direction for future work.
—
References
[1] Yu. Nesterov. Gradient methods for minimizing composite functions. Mathematical Programming, 140(1):125–161, 2013.
[2] B. O’Donoghue and E. Candès. Adaptive restart for accelerated gradient schemes. Foundations of Computational Mathematics, 15(3):715–732, 2015.
[3] O. Fercoq and Z. Qu. Adaptive restart of accelerated gradient methods under local quadratic growth condition. IMA Journal of Numerical Analysis, 39(4):2069–2095, 2019.
[4] V. Roulet and A. d’Aspremont. Sharpness, restart and acceleration. In Advances in Neural Information Processing Systems 30 (NeurIPS), 2017.
[5] Kamzolov, Dmitry, et al. "Optami: Global superlinear convergence of high-order methods." International Conference on Learning Representations. Vol. 2025.
[6] Lucchi, Aurelien, and Jonas Kohler. "A Sub-sampled Tensor Method for Non-convex Optimization." arXiv preprint arXiv:1911.10367 (2019).
—
We hope that the additional experiments and the clarification on the relative performance of the accelerated and non-accelerated methods address the weaknesses raised and give a clearer picture of when acceleration is advantageous. If so, we would appreciate a reconsideration of the rating. We welcome further discussion if any questions remain.
Response
Dear Authors,
Thank you for the detailed responses. I have read the rebuttal and the updated manuscript.
I appreciate the additional insight into the accelerated vs. non-accelerated variant of your method. The additional experiments help clarify the empirical performance of the proposed methods.
Based on your response and your replies to the other reviewers, I have decided to increase my score accordingly.
part 1
Dear Reviewer,
We thank you for your time and effort in reviewing our paper. We address your comments below.
Weakness Wall-Clock
Answer:
For the experiments with exact Hessians, we added wall-clock time and oracle calls to Figure 1.
For inexact Hessians, our setup is motivated by distributed optimization, with the server’s local Hessian serving as an approximation. Each full gradient requires one communication round (workers compute local gradients in parallel and send them to the server), and the Hessian is computed by the server once per outer iteration of the method. Wall-clock time of a single-machine simulation would not reflect the cost of this setting. Thus, in Figure 1 we report communication rounds, as communication is typically the main bottleneck in this setting.
Note that the two axes in Figure 1 also measure the two kinds of computation: the number of outer iterations is the number of Hessian computations on the server, and the number of communication rounds is the number of local gradient computations on each worker.
Across all measures – iterations, oracle calls, wall-clock time, and communication rounds – the performance of our methods remains consistent, with the basic non-accelerated method performing best. Their wall-clock efficiency comes from solving only quadratic subproblems.