Direct nonlinear acceleration

Aritra Dutta, El Houcine Bergou*, Yunming Xiao, Marco Canini, Peter Richtárik

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Optimization acceleration techniques such as momentum play a key role in state-of-the-art machine learning algorithms. Recently, generic vector sequence extrapolation techniques, such as regularized nonlinear acceleration (RNA) of Scieur et al. [22], were proposed and shown to accelerate fixed point iterations. In contrast to RNA which computes extrapolation coefficients by (approximately) setting the gradient of the objective function to zero at the extrapolated point, we propose a more direct approach, which we call direct nonlinear acceleration (DNA). In DNA, we aim to minimize (an approximation of) the function value at the extrapolated point instead. We adopt a regularized approach with regularizers designed to prevent the model from entering a region in which the functional approximation is less precise. While the computational cost of DNA is comparable to that of RNA, our direct approach significantly outperforms RNA on both synthetic and real-world datasets. While the focus of this paper is on convex problems, we obtain very encouraging results in accelerating the training of neural networks.

Original languageEnglish (US)
Article number100047
JournalEURO Journal on Computational Optimization
StatePublished - Jan 2022

ASJC Scopus subject areas

  • Modeling and Simulation
  • Management Science and Operations Research
  • Control and Optimization
  • Computational Mathematics


Dive into the research topics of 'Direct nonlinear acceleration'. Together they form a unique fingerprint.

Cite this