Strong Convexity of Feasible Sets in Off-line and Online Optimization

Marco Molinaro ()
Additional contact information
Marco Molinaro: Computer Science Department, Pontifical Catholic University of Rio de Janeiro, Rio de Janeiro, RJ 22451, Brazil

Mathematics of Operations Research, 2023, vol. 48, issue 2, 865-884

Abstract: It is known that the curvature of the feasible set in convex optimization allows for algorithms with better convergence rates, and there is renewed interest in this topic for both off-line and 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 shows that the Frank–Wolfe–type method of Wang and Abernethy has accelerated convergence rate O ( 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 why/when follow the leader (FTL) has only logarithmic regret over strongly convex sets. This allows one to directly recover and slightly extend a recent result of Huang et al., and to show that FTL has logarithmic regret over strongly convex sets whenever the gain vectors are nonnegative. We provide an efficient procedure for approximating convex bodies by strongly convex ones while smoothly trading off approximation error and curvature. This allows one to extend the improved algorithms over strongly convex sets to general convex sets. As a concrete application, we extend results on online linear optimization with hints to general convex sets.

Keywords: Primary: 52A21; secondary: 90C25; strongly convex sets; online learning; online linear optimization; convex geometry; uniform convexity; follow the leader; convex optimization (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1285 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:2:p:865-884

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().