# Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Sets

arXiv: https://arxiv.org/abs/2303.05037 · HTML: https://mlsanity.com/paper/2303.05037/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 62 references that are in the map.
- First posted on arXiv 9 Mar 2023.

## Builds on (most cited first, 26 of 26)

- [Efficiency of minimizing compositions of convex functions and smooth maps](https://mlsanity.com/paper/1605.00125/) (2016)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradient](https://mlsanity.com/paper/1803.06573/) (2018)
- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [Faster Rates for Convex-Concave Games](https://mlsanity.com/paper/1805.06792/) (2018)
- [Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity](https://mlsanity.com/paper/1712.04104/) (2017)
- [Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimization](https://mlsanity.com/paper/1309.5547/) (2013)
- [A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methods](https://mlsanity.com/paper/1803.00151/) (2018)
- [Projection-free Adaptive Regret with Membership Oracles](https://mlsanity.com/paper/2211.12638/) (2022)
- [Curvature of Feasible Sets in Offline and Online Optimization](https://mlsanity.com/paper/2002.03213/) (2020)
- [Optimal Convergence Rates for the Proximal Bundle Method](https://mlsanity.com/paper/2105.07874/) (2021)
- [COSMO: A conic operator splitting method for convex conic problems](https://mlsanity.com/paper/1901.10887/) (2019)
- [A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes](https://mlsanity.com/paper/2003.11457/) (2020)
- [Gauge optimization and duality](https://mlsanity.com/paper/1310.2639/) (2013)
- ["Efficient" Subgradient Methods for General Convex Optimization](https://mlsanity.com/paper/1605.08712/) (2016)
- [Radial Subgradient Method](https://mlsanity.com/paper/1703.09280/) (2017)
- [Level-set methods for convex optimization](https://mlsanity.com/paper/1602.01506/) (2016)
- [Rate of Convergence of the Bundle Method](https://mlsanity.com/paper/1609.00842/) (2016)
- [Radial Duality Part II: Applications and Algorithms](https://mlsanity.com/paper/2104.11185/) (2021)
- [Survey Descent: A Multipoint Generalization of Gradient Descent for Nonsmooth Optimization](https://mlsanity.com/paper/2111.15645/) (2021)
- [Accelerated First-Order Methods for Hyperbolic Programming](https://mlsanity.com/paper/1512.07569/) (2015)
- [Radial Duality Part I: Foundations](https://mlsanity.com/paper/2104.11179/) (2021)
- [Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding](https://mlsanity.com/paper/1312.3039/) (2013)
- [Foundations of gauge and perspective duality](https://mlsanity.com/paper/1702.08649/) (2017)
- [An Adaptive Parameter-free and Projection-free Restarting Level Set Method for Constrained Convex Optimization Under the Error Bound Condition](https://mlsanity.com/paper/2010.15267/) (2020)
- [Affine invariant convergence rates of the conditional gradient method](https://mlsanity.com/paper/2112.06727/) (2021)

## Built on by (most cited first, 2 of 2)

- [Projection-Free Online Convex Optimization via Efficient Newton Iterations](https://mlsanity.com/paper/2306.11121/) (2023)
- [Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization](https://mlsanity.com/paper/2305.17323/) (2023)

## Abstract (arXiv)

We consider feasibility and constrained optimization problems defined over smooth and/or strongly convex sets. These notions mirror their popular function counterparts but are much less explored in the first-order optimization literature. We propose new scalable, projection-free, accelerated first-order methods in these settings. Our methods avoid linear optimization or projection oracles, only using cheap one-dimensional linesearches and normal vector computations. Despite this, we derive optimal accelerated convergence guarantees of O(1/T) for strongly convex problems, O(1/T2) for smooth problems, and accelerated linear convergence given both. Our algorithms and analysis are based on novel characterizations of the Minkowski gauge of smooth and/or strongly convex sets, which may be of independent interest: although the gauge is neither smooth nor strongly convex, we show the gauge squared inherits any structure present in the set.