# Efficient Online Linear Optimization with Approximation Algorithms

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Sep 2017.

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

- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022)
- [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (2022)
- [Multi-Receiver Online Bayesian Persuasion](https://mlsanity.com/paper/2106.06480/) (2021)
- [Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations](https://mlsanity.com/paper/2106.06712/) (2021)
- [BAGEL: Adversarially Constrained Online Convex Optimization under Separation Oracle Access](https://mlsanity.com/paper/2502.16744/) (2025)
- [Efficient Online Learning for Dynamic k-Clustering](https://mlsanity.com/paper/2106.04336/) (2021)
- [Learning with Posterior Sampling for Revenue Management under Time-varying Demand](https://mlsanity.com/paper/2405.04910/) (2024)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Tight Bounds for γ-Regret via the Decision-Estimation Coefficient](https://mlsanity.com/paper/2303.03327/) (2023)
- [Online Combinatorial Linear Optimization via a Frank-Wolfe-based Metarounding Algorithm](https://mlsanity.com/paper/2310.12629/) (2023)
- [Blackwell's Approachability with Approximation Algorithms](https://mlsanity.com/paper/2502.03919/) (2025)

## Abstract (arXiv)

We revisit the problem of textitonline linear optimization in case the set of feasible actions is accessible through an approximated linear optimization oracle with a factor α multiplicative approximation guarantee. This setting is in particular interesting since it captures natural online extensions of well-studied textitoffline linear optimization problems which are NP-hard, yet admit efficient approximation algorithms. The goal here is to minimize the αtextit-regret which is the natural extension of the standard textitregret in textitonline learning to this setting. We present new algorithms with significantly improved oracle complexity for both the full information and bandit variants of the problem. Mainly, for both variants, we present α-regret bounds of O(T-1/3), were T is the number of prediction rounds, using only O(logT) calls to the approximation oracle per iteration, on average. These are the first results to obtain both average oracle complexity of O(logT) (or even poly-logarithmic in T) and α-regret bound O(T-c) for a constant c>0, for both variants.