Journal of Nonlinear and Variational Analysis

Full Text: PDF
DOI: 10.23952/jnva.10.2026.3.03

Volume 10, Issue 3, 1 June 2026, Pages 523-553

 

Abstract. One of the major early-career contributions to numerical optimization by Yurii Nesterov is the development of Nesterov’s acceleration and the corresponding Fast Gradient Method (FGM). Accelerated first-order methods are very important in large-scale optimization and have applications in different fields of engineering and science. Such methods are devised in the context of the estimating sequences framework, which was also developed by Nesterov, but much later than FGM, and exhibit desirable properties such as fast convergence rate and low per-iteration complexity. In this paper, we devise new generalized estimating sequences with an objective of pushing acceleration to its limit and show how they can be used to construct accelerated first-order methods. We start our summary by considering the case of minimizing smooth convex objective functions. For this class of problems, we present a class of generalized estimating sequences, constructed by exploiting the history of the estimating functions that are obtained during the minimization process. Using these generalized estimating sequences, we devise an accelerated gradient method and prove that it converges to a tolerated neighborhood of the optimal solution faster than FGM and other first-order methods. We then consider a more general class of optimization problems, namely composite objectives. For this class of problems, we introduce the class of composite estimating sequences, which are obtained by making use of the gradient mapping framework and a tight lower bound on the function that should be minimized. Using these composite estimating sequences, we devise a composite objective accelerated multi-step estimating sequence technique and prove its accelerated convergence rate. Last, embedding the memory term coming from the previous iterates into the composite estimating sequences, we obtain the generalized composite estimating sequences. Using these estimating sequences, we construct another accelerated gradient method and prove its accelerated convergence rate.

 

How to Cite this Article:
E. Dosti, S. A. Vorobyov, T. Charalambous, Nesterov’s acceleration at the Limit: First-order schemes, J. Nonlinear Var. Anal. 10 (2026), 523-553.