NeurIPS 2021poster13 citations
Information-constrained optimization: can adaptive processing of gradients help?
Jayadev Acharya, Clement Louis Canonne, Prathamesh Mayekar, Himanshu Tyagi
Abstract
We revisit first-order optimization under local information constraints such as local privacy, gradient quantization, and computational constraints limiting access to a few coordinates of the gradient. In this setting, the optimization algorithm is not allowed to directly access the complete output of the gradient oracle, but only gets limited information about it subject to the local information constraints. We study the role of adaptivity in processing the gradient output to obtain this limited information from it, and obtain tight or nearly tight bounds for both convex and strongly convex optimization when adaptive gradient processing is allowed.
optimizationconvex optimizationadaptivityinformation constraintslocal privacycommunication constraintslower boundsrandom coordinate descent
BibTeX
@inproceedings{
acharya2021informationconstrained,
title={Information-constrained optimization: can adaptive processing of gradients help?},
author={Jayadev Acharya and Clement Louis Canonne and Prathamesh Mayekar and Himanshu Tyagi},
booktitle={Advances in Neural Information Processing Systems},
editor={A. Beygelzimer and Y. Dauphin and P. Liang and J. Wortman Vaughan},
year={2021},
url={https://openreview.net/forum?id=h7aSBWbX7S4}
}