FLAG n’ FLARE: Fast Linearly-Coupled Adaptive Gradient Methods

Xiang Cheng, Fred Roosta, Stefan Palombo, Peter Bartlett, Michael Mahoney
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:404-414, 2018.

Abstract

We consider first order gradient methods for effectively optimizing a composite objective in the form of a sum of smooth and, potentially, non-smooth functions. We present accelerated and adaptive gradient methods, called FLAG and FLARE, which can offer the best of both worlds. They can achieve the optimal convergence rate by attaining the optimal first-order oracle complexity for smooth convex optimization. Additionally, they can adaptively and non-uniformly re-scale the gradient direction to adapt to the limited curvature available and conform to the geometry of the domain. We show theoretically and empirically that, through the compounding effects of acceleration and adaptivity, FLAG and FLARE can be highly effective for many data fitting and machine learning applications.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-cheng18b, title = {FLAG n’ FLARE: Fast Linearly-Coupled Adaptive Gradient Methods}, author = {Cheng, Xiang and Roosta, Fred and Palombo, Stefan and Bartlett, Peter and Mahoney, Michael}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {404--414}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/cheng18b/cheng18b.pdf}, url = {https://proceedings.mlr.press/v84/cheng18b.html}, abstract = {We consider first order gradient methods for effectively optimizing a composite objective in the form of a sum of smooth and, potentially, non-smooth functions. We present accelerated and adaptive gradient methods, called FLAG and FLARE, which can offer the best of both worlds. They can achieve the optimal convergence rate by attaining the optimal first-order oracle complexity for smooth convex optimization. Additionally, they can adaptively and non-uniformly re-scale the gradient direction to adapt to the limited curvature available and conform to the geometry of the domain. We show theoretically and empirically that, through the compounding effects of acceleration and adaptivity, FLAG and FLARE can be highly effective for many data fitting and machine learning applications.} }
Endnote
%0 Conference Paper %T FLAG n’ FLARE: Fast Linearly-Coupled Adaptive Gradient Methods %A Xiang Cheng %A Fred Roosta %A Stefan Palombo %A Peter Bartlett %A Michael Mahoney %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-cheng18b %I PMLR %P 404--414 %U https://proceedings.mlr.press/v84/cheng18b.html %V 84 %X We consider first order gradient methods for effectively optimizing a composite objective in the form of a sum of smooth and, potentially, non-smooth functions. We present accelerated and adaptive gradient methods, called FLAG and FLARE, which can offer the best of both worlds. They can achieve the optimal convergence rate by attaining the optimal first-order oracle complexity for smooth convex optimization. Additionally, they can adaptively and non-uniformly re-scale the gradient direction to adapt to the limited curvature available and conform to the geometry of the domain. We show theoretically and empirically that, through the compounding effects of acceleration and adaptivity, FLAG and FLARE can be highly effective for many data fitting and machine learning applications.
APA
Cheng, X., Roosta, F., Palombo, S., Bartlett, P. & Mahoney, M.. (2018). FLAG n’ FLARE: Fast Linearly-Coupled Adaptive Gradient Methods. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:404-414 Available from https://proceedings.mlr.press/v84/cheng18b.html.

Related Material