Adaptive Balancing of Gradient and Update Computation Times Using Global Geometry and Approximate Subproblems
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
Text
Karimireddy et al. "Adaptive Balancing of Gradient and Update Computation Times Using Global Geometry and Approximate Subproblems." International Conference on Artificial Intelligence and Statistics, 2018.Markdown
[Karimireddy et al. "Adaptive Balancing of Gradient and Update Computation Times Using Global Geometry and Approximate Subproblems." International Conference on Artificial Intelligence and Statistics, 2018.](https://mlanthology.org/aistats/2018/karimireddy2018aistats-adaptive/)BibTeX
@inproceedings{karimireddy2018aistats-adaptive,
title = {{Adaptive Balancing of Gradient and Update Computation Times Using Global Geometry and Approximate Subproblems}},
author = {Karimireddy, Sai Praneeth Reddy and Stich, Sebastian U. and Jaggi, Martin},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2018},
pages = {1204-1213},
url = {https://mlanthology.org/aistats/2018/karimireddy2018aistats-adaptive/}
}