Fetching the paper…

Reading the bibliography…

Curvature of Feasible Sets in Offline and Online Optimization · Around

2020

Curvature of Feasible Sets in Offline and Online Optimization

Molinaro, Marco

Original
PDF
Post on X

Understand

It is known that the curvature of the feasible set in convex optimization allows for algorithms with better convergence rates, and there has been renewed interest in this topic both for offline as well as online problems.

In this paper, leveraging results on geometry and convex analysis, we further our understanding of the role of curvature in optimization: - We first show the equivalence of two notions of curvature, namely strong convexity and gauge bodies, proving a conjecture of Abernethy et al.
As a consequence, this show that the Frank-Wolfe-type method of Wang and Abernethy has accelerated convergence rate $O(\frac{1}{t^2})$ over strongly convex feasible sets without additional assumptions on the (convex) objective function.
- In Online Linear Optimization, we identify two main properties that help explaining \emph{why/when} Follow the Leader (FTL) has only logarithmic regret over strongly convex sets.

Built on

J. Clarkson
1936
Earlier work this paper cites.
M. Frank and P. Wolfe
1956
Earlier work this paper cites.
W. J. Firey
1962
Earlier work this paper cites.
E. Levitin and B. Polyak
1966
Earlier work this paper cites.
B. T. Polyak
1966
Earlier work this paper cites.
V. Demyanov and A. Rubinov
1970
Earlier work this paper cites.
K. John and V. Zizler
1979
Earlier work this paper cites.
J.-P. Vial
1982
Earlier work this paper cites.
R. Deville, G. Godefroy, and V. Zizler
1993
Earlier work this paper cites.
M. Grötschel, L. Lovász, and A. Schrijver
1993
Earlier work this paper cites.
P.-J.-P. Azé, Dominique
1995
Earlier work this paper cites.
G. Ziegler
1995
Earlier work this paper cites.
E. S. Polovinkin
1996
Earlier work this paper cites.
J.-B. Hiriart-Urruty and C. Lemaréchal
2001
Earlier work this paper cites.
S. Boyd and L. Vandenberghe
2004
Earlier work this paper cites.

Similar

A. Kalai and S. Vempala
2005
Cited alongside, same era.
E. Hazan and N. Megiddo
2007
Cited alongside, same era.
M. V. Balashov and D. Repovš
2009
Cited alongside, same era.
M. Jaggi and M. Sulovský
2010
Cited alongside, same era.
N. Srebro, K. Sridharan, and A. Tewari
2011
Cited alongside, same era.
E. Lutwak, D. Yang, and G. Zhang
2012
Cited alongside, same era.
S. Shalev-Shwartz
2012
Cited alongside, same era.
M. Jaggi
2013

Then

Z. Harchaoui, A. Juditsky, and A. Nemirovski
2015
Later among the works it cites.
B. Li and S. Hoi
2015
Later among the works it cites.
E. Hazan
2016
Later among the works it cites.
C. Mu, Y. Zhang, J. Wright, and D. Goldfarb
2016
Later among the works it cites.
A. Osokin, J.-B. Alayrac, I. Lukasewitz, P. Dokania, and S. Lacoste-Julien
2016
Later among the works it cites.
O. Dekel, A. Flajolet, N. Haghtalab, and P. Jaillet
2017
Later among the works it cites.
D. J. Foster, S. Kale, M. Mohri, and K. Sridharan
2017
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Cited alongside, same era.

S. Lacoste-Julien, M. Jaggi, M. Schmidt, and P. Pletscher

2013

Cited alongside, same era.

J. Lindenstrauss and L. Tzafriri

2013

Cited alongside, same era.

A. Rakhlin and K. Sridharan

2013

Cited alongside, same era.

C. Zălinescu

2013

Cited alongside, same era.

R. Freund, P. Grigas, and R. Mazunder

2017

Later among the works it cites.

V. V. Goncharov and G. E. Ivanov

2017

Later among the works it cites.

R. Huang, T. Lattimore, A. György, and C. Szepesvári

2017

Later among the works it cites.

T. Liu, G. Lugosi, G. Neu, and D. Tao

2017

Later among the works it cites.

A. Rakhlin and K. Sridharan

2017

Later among the works it cites.

J. D. Abernethy, K. A. Lai, K. Y. Levy, and J. Wang

2018

Later among the works it cites.

( https://arxiv.org/pdf/1807.10455.pdf )

J. Wang and J. Abernethy · 2018

Later among the works it cites.