# Projection-Free Online Convex Optimization via Efficient Newton Iterations

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 40 references that are in the map.
- First posted on arXiv 19 Jun 2023.

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

- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020)
- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022)
- [Faster Rates for Convex-Concave Games](https://mlsanity.com/paper/1805.06792/) (2018)
- [Solving Tall Dense Linear Programs in Nearly Linear Time](https://mlsanity.com/paper/2002.02304/) (2020)
- [Revisiting Projection-free Online Learning: the Strongly Convex Case](https://mlsanity.com/paper/2010.07572/) (2020)
- [Efficient Online Portfolio with Logarithmic Regret](https://mlsanity.com/paper/1805.07430/) (2018)
- [Solving Linear Programs with Sqrt(rank) Linear System Solves](https://mlsanity.com/paper/1910.08033/) (2019)
- [Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum States](https://mlsanity.com/paper/2202.02765/) (2022)
- [Efficient Inverse Maintenance and Faster Algorithms for Linear Programming](https://mlsanity.com/paper/1503.01752/) (2015)
- [Linearly Convergent Frank-Wolfe with Backtracking Line-Search](https://mlsanity.com/paper/1806.05123/) (2018)
- [Efficient and Near-Optimal Online Portfolio Selection](https://mlsanity.com/paper/2209.13932/) (2022)
- [Projection-free Adaptive Regret with Membership Oracles](https://mlsanity.com/paper/2211.12638/) (2022)
- [Sequential Probability Assignment with Binary Alphabets and Large Classes of Experts](https://mlsanity.com/paper/1501.07340/) (2015)
- [Soft-Bayes: Prod for Mixtures of Experts with Log-Loss](https://mlsanity.com/paper/1901.02230/) (2019)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [Quasi-Newton Steps for Efficient Online Exp-Concave Optimization](https://mlsanity.com/paper/2211.01357/) (2022)
- [Damped Online Newton Step for Portfolio Selection](https://mlsanity.com/paper/2202.07574/) (2022)
- [Computing Lewis Weights to High Precision](https://mlsanity.com/paper/2110.15563/) (2021)
- [Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Sets](https://mlsanity.com/paper/2303.05037/) (2023)

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

- [Fully Unconstrained Online Learning](https://mlsanity.com/paper/2405.20540/) (2024)
- [Revisiting Projection-Free Online Learning with Time-Varying Constraints](https://mlsanity.com/paper/2501.16046/) (2025)
- [Nonsmooth Projection-Free Optimization with Functional Constraints](https://mlsanity.com/paper/2311.11180/) (2023)
- [ASTRA: ADMM-Accelerated Topology Reconfiguration for Dynamic Satellite Constellations](https://mlsanity.com/paper/2609.33993/) (2026)

## Abstract (arXiv)

This paper presents new projection-free algorithms for Online Convex Optimization (OCO) over a convex domain K subset ℝd. Classical OCO algorithms (such as Online Gradient Descent) typically need to perform Euclidean projections onto the convex set cK to ensure feasibility of their iterates. Alternative algorithms, such as those based on the Frank-Wolfe method, swap potentially-expensive Euclidean projections onto K for linear optimization over K. However, such algorithms have a sub-optimal regret in OCO compared to projection-based algorithms. In this paper, we look at a third type of algorithms that output approximate Newton iterates using a self-concordant barrier for the set of interest. The use of a self-concordant barrier automatically ensures feasibility without the need for projections. However, the computation of the Newton iterates requires a matrix inverse, which can still be expensive. As our main contribution, we show how the stability of the Newton iterates can be leveraged to compute the inverse Hessian only a vanishing fraction of the rounds, leading to a new efficient projection-free OCO algorithm with a state-of-the-art regret bound.