Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems

Sai Praneeth Reddy Karimireddy, Sebastian Stich, Martin Jaggi
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:1204-1213, 2018.

Abstract

First-order optimization methods comprise two important primitives: i) the computation of gradient information and ii) the computation of the update that leads to the next iterate. In practice there is often a wide mismatch between the time required for the two steps, leading to underutilization of resources. In this work, we propose a new framework, Approx Composite Minimization (ACM) that uses approximate update steps to ensure balance between the two operations. The accuracy is adaptively chosen in an online fashion to take advantage of changing conditions. Our unified analysis for approximate composite minimization generalizes and extends previous work to new settings. Numerical experiments on Lasso regression and SVMs demonstrate the effectiveness of the novel scheme.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-karimireddy18a, title = {Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems}, author = {Karimireddy, Sai Praneeth Reddy and Stich, Sebastian and Jaggi, Martin}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {1204--1213}, 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/karimireddy18a/karimireddy18a.pdf}, url = {https://proceedings.mlr.press/v84/karimireddy18a.html}, abstract = {First-order optimization methods comprise two important primitives: i) the computation of gradient information and ii) the computation of the update that leads to the next iterate. In practice there is often a wide mismatch between the time required for the two steps, leading to underutilization of resources. In this work, we propose a new framework, Approx Composite Minimization (ACM) that uses approximate update steps to ensure balance between the two operations. The accuracy is adaptively chosen in an online fashion to take advantage of changing conditions. Our unified analysis for approximate composite minimization generalizes and extends previous work to new settings. Numerical experiments on Lasso regression and SVMs demonstrate the effectiveness of the novel scheme.} }
Endnote
%0 Conference Paper %T Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems %A Sai Praneeth Reddy Karimireddy %A Sebastian Stich %A Martin Jaggi %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-karimireddy18a %I PMLR %P 1204--1213 %U https://proceedings.mlr.press/v84/karimireddy18a.html %V 84 %X First-order optimization methods comprise two important primitives: i) the computation of gradient information and ii) the computation of the update that leads to the next iterate. In practice there is often a wide mismatch between the time required for the two steps, leading to underutilization of resources. In this work, we propose a new framework, Approx Composite Minimization (ACM) that uses approximate update steps to ensure balance between the two operations. The accuracy is adaptively chosen in an online fashion to take advantage of changing conditions. Our unified analysis for approximate composite minimization generalizes and extends previous work to new settings. Numerical experiments on Lasso regression and SVMs demonstrate the effectiveness of the novel scheme.
APA
Karimireddy, S.P.R., Stich, S. & Jaggi, M.. (2018). Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:1204-1213 Available from https://proceedings.mlr.press/v84/karimireddy18a.html.

Related Material