Timezone: »
We introduce a generic scheme for accelerating first-order optimization methods in the sense of Nesterov, which builds upon a new analysis of the accelerated proximal point algorithm. Our approach consists of minimizing a convex objective by approximately solving a sequence of well-chosen auxiliary problems, leading to faster convergence. This strategy applies to a large class of algorithms, including gradient descent, block coordinate descent, SAG, SAGA, SDCA, SVRG, Finito/MISO, and their proximal variants. For all of these methods, we provide acceleration and explicit support for non-strongly convex objectives. In addition to theoretical speed-up, we also show that acceleration is useful in practice, especially for ill-conditioned problems where we measure significant improvements.
Author Information
Hongzhou Lin (Inria)
Julien Mairal (INRIA)
Zaid Harchaoui (Inria)
More from the Same Authors
-
2021 : Discrete Schrödinger Bridges with Applications to Two-Sample Homogeneity Testing »
Zaid Harchaoui · Lang Liu · Soumik Pal -
2021 : Discrete Schrödinger Bridges with Applications to Two-Sample Homogeneity Testing »
Zaid Harchaoui · Lang Liu · Soumik Pal -
2021 : Discrete Schrödinger Bridges with Applications to Two-Sample Homogeneity Testing »
Zaid Harchaoui · Lang Liu · Soumik Pal -
2021 Poster: Stochastic optimization under time drift: iterate averaging, step-decay schedules, and high probability guarantees »
Joshua Cutler · Dmitriy Drusvyatskiy · Zaid Harchaoui -
2021 Poster: Divergence Frontiers for Generative Models: Sample Complexity, Quantization Effects, and Frontier Integrals »
Lang Liu · Krishna Pillutla · Sean Welleck · Sewoong Oh · Yejin Choi · Zaid Harchaoui -
2021 Poster: MAUVE: Measuring the Gap Between Neural Text and Human Text using Divergence Frontiers »
Krishna Pillutla · Swabha Swayamdipta · Rowan Zellers · John Thickstun · Sean Welleck · Yejin Choi · Zaid Harchaoui -
2021 Oral: MAUVE: Measuring the Gap Between Neural Text and Human Text using Divergence Frontiers »
Krishna Pillutla · Swabha Swayamdipta · Rowan Zellers · John Thickstun · Sean Welleck · Yejin Choi · Zaid Harchaoui -
2018 Poster: ResNet with one-neuron hidden layers is a Universal Approximator »
Hongzhou Lin · Stefanie Jegelka -
2018 Spotlight: ResNet with one-neuron hidden layers is a Universal Approximator »
Hongzhou Lin · Stefanie Jegelka -
2016 Poster: Structure-Blind Signal Recovery »
Dmitry Ostrovsky · Zaid Harchaoui · Anatoli Juditsky · Arkadi S Nemirovski -
2015 Poster: Semi-Proximal Mirror-Prox for Nonsmooth Composite Minimization »
Niao He · Zaid Harchaoui -
2014 Workshop: OPT2014: Optimization for Machine Learning »
Zaid Harchaoui · Suvrit Sra · Alekh Agarwal · Martin Jaggi · Miro Dudik · Aaditya Ramdas · Jean Lasserre · Yoshua Bengio · Amir Beck -
2014 Poster: Convolutional Kernel Networks »
Julien Mairal · Piotr Koniusz · Zaid Harchaoui · Cordelia Schmid -
2014 Spotlight: Convolutional Kernel Networks »
Julien Mairal · Piotr Koniusz · Zaid Harchaoui · Cordelia Schmid -
2013 Workshop: Greedy Algorithms, Frank-Wolfe and Friends - A modern perspective »
Martin Jaggi · Zaid Harchaoui · Federico Pierucci -
2009 Workshop: Temporal Segmentation: Perspectives from Statistics, Machine Learning, and Signal Processing »
Stephane Canu · Olivier Cappé · Arthur Gretton · Zaid Harchaoui · Alain Rakotomamonjy · Jean-Philippe Vert -
2009 Poster: A Fast, Consistent Kernel Two-Sample Test »
Arthur Gretton · Kenji Fukumizu · Zaid Harchaoui · Bharath Sriperumbudur -
2009 Spotlight: A Fast, Consistent Kernel Two-Sample Test »
Arthur Gretton · Kenji Fukumizu · Zaid Harchaoui · Bharath Sriperumbudur -
2008 Poster: Kernel Change-point Analysis »
Zaid Harchaoui · Francis Bach · Eric Moulines -
2007 Poster: Testing for Homogeneity with Kernel Fisher Discriminant Analysis »
Zaid Harchaoui · Francis Bach · Moulines Eric -
2007 Poster: DIFFRAC: a discriminative and flexible framework for clustering »
Francis Bach · Zaid Harchaoui -
2007 Poster: Catching Change-points with Lasso »
Zaid Harchaoui · Céline Lévy-Leduc