High-probability bounds for robust stochastic Frank-Wolfe algorithm
Tongyi Tang, Krishna Balasubramanian, Thomas Chun Man Lee
Abstract
We develop and analyze robust Stochastic Frank-Wolfe type algorithms for projection-free stochastic convex optimization problems with heavy-tailed stochastic gradients. Existing works on the oracle complexity of such algorithms require a uniformly bounded variance assumption, and hold only in expectation. We develop tight high-probability bounds for robust versions of Stochastic Frank-Wolfe type algorithm under heavy-tailed assumptions, including infinite variance, on the stochastic gradient. Our methodological construction of the robust Stochastic Frank-Wolfe type algorithms leverage techniques from the robust statistic literature. Our theoretical analysis highlights the need to utilize robust versions of Stochastic Frank-Wolfe type algorithm for dealing with heavy-tailed data arising in practice.
BibTeX
@InProceedings{pmlr-v180-tang22a,
title = {High-probability bounds for robust stochastic Frank-Wolfe algorithm},
author = {Tang, Tongyi and Balasubramanian, Krishna and Chun Man Lee, Thomas},
booktitle = {Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence},
pages = {1917--1927},
year = {2022},
editor = {Cussens, James and Zhang, Kun},
volume = {180},
series = {Proceedings of Machine Learning Research},
month = {01--05 Aug},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v180/tang22a/tang22a.pdf},
url = {https://proceedings.mlr.press/v180/tang22a.html},
abstract = {We develop and analyze robust Stochastic Frank-Wolfe type algorithms for projection-free stochastic convex optimization problems with heavy-tailed stochastic gradients. Existing works on the oracle complexity of such algorithms require a uniformly bounded variance assumption, and hold only in expectation. We develop tight high-probability bounds for robust versions of Stochastic Frank-Wolfe type algorithm under heavy-tailed assumptions, including infinite variance, on the stochastic gradient. Our methodological construction of the robust Stochastic Frank-Wolfe type algorithms leverage techniques from the robust statistic literature. Our theoretical analysis highlights the need to utilize robust versions of Stochastic Frank-Wolfe type algorithm for dealing with heavy-tailed data arising in practice.}
}