Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets

Jarrid Rector-Brooks, Jun-Kun Wang, Barzan Mozafari

AAAI 2019 pp. 1576-1583

doi:10.1609/AAAI.V33I01.33011576 /aaai/2019/rectorbrooks2019aaai-revisiting/

Abstract

We revisit the Frank-Wolfe (FW) optimization under strongly convex constraint sets. We provide a faster convergence rate for FW without line search, showing that a previously overlooked variant of FW is indeed faster than the standard variant. With line search, we show that FW can converge to the global optimum, even for smooth functions that are not convex, but are quasi-convex and locally-Lipschitz. We also show that, for the general case of (smooth) non-convex functions, FW with line search converges with high probability to a stationary point at a rate of O(1/t), as long as the constraint set is strongly convex—one of the fastest convergence rates in non-convex optimization.

PDF AAAI Semantic Scholar

Cite

Text

Rector-Brooks et al. "Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33011576

Markdown

[Rector-Brooks et al. "Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/rectorbrooks2019aaai-revisiting/) doi:10.1609/AAAI.V33I01.33011576

BibTeX

@inproceedings{rectorbrooks2019aaai-revisiting,
  title     = {{Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets}},
  author    = {Rector-Brooks, Jarrid and Wang, Jun-Kun and Mozafari, Barzan},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {1576-1583},
  doi       = {10.1609/AAAI.V33I01.33011576},
  url       = {https://mlanthology.org/aaai/2019/rectorbrooks2019aaai-revisiting/}
}