# Optimal Regularized Online Allocation by Adaptive Re-Solving

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 62 references that are in the map.
- First posted on arXiv 1 Sep 2022.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent](https://mlsanity.com/paper/1905.11261/) (2019)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [Fast Rates for Contextual Linear Optimization](https://mlsanity.com/paper/2011.03030/) (2020)
- [Fast Algorithms for Online Stochastic Convex Programming](https://mlsanity.com/paper/1410.7596/) (2014)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits](https://mlsanity.com/paper/1504.06937/) (2015)
- [Regularized Online Allocation Problems: Fairness and Beyond](https://mlsanity.com/paper/2007.00514/) (2020)
- [Uniformly bounded regret in the multi-secretary problem](https://mlsanity.com/paper/1710.07719/) (2017)
- [A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management](https://mlsanity.com/paper/1802.06192/) (2018)
- [Real Time Bid Optimization with Smooth Budget Delivery in Online Advertising](https://mlsanity.com/paper/1305.3011/) (2013)
- [The Bayesian Prophet: A Low-Regret Framework for Online Decision Making](https://mlsanity.com/paper/1901.05028/) (2019)
- [The Parity Ray Regularizer for Pacing in Auction Markets](https://mlsanity.com/paper/2106.09503/) (2021)
- [Greedy Algorithm for Multiway Matching with Bounded Regret](https://mlsanity.com/paper/2112.04622/) (2021)
- [Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems](https://mlsanity.com/paper/1903.03944/) (2019)

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

- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025)
- [High-dimensional Linear Bandits with Knapsacks](https://mlsanity.com/paper/2311.01327/) (2023)
- [Wait-Less Offline Tuning and Re-solving for Online Decision Making](https://mlsanity.com/paper/2412.09594/) (2024)
- [Fairness-Regularized Online Optimization with Switching Costs](https://mlsanity.com/paper/2512.11131/) (2025)
- [CLASP: An online learning algorithm for Convex Losses And Squared Penalties](https://mlsanity.com/paper/2601.16072/) (2026)
- [A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret](https://mlsanity.com/paper/2609.05895/) (2026)
- [Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving](https://mlsanity.com/paper/2609.28263/) (2026)

## Abstract (arXiv)

This paper introduces a dual-based algorithm framework for solving the regularized online resource allocation problems, which have potentially non-concave cumulative rewards, hard resource constraints, and a non-separable regularizer. Under a strategy of adaptively updating the resource constraints, the proposed framework only requests approximate solutions to the empirical dual problems up to a certain accuracy and yet delivers an optimal logarithmic regret under a locally second-order growth condition. Surprisingly, a delicate analysis of the dual objective function enables us to eliminate the notorious log-log factor in regret bound. The flexible framework renders renowned and computationally fast algorithms immediately applicable, e.g., dual stochastic gradient descent. Additionally, an infrequent re-solving scheme is proposed, which significantly reduces computational demands without compromising the optimal regret performance. A worst-case square-root regret lower bound is established if the resource constraints are not adaptively updated during dual optimization, which underscores the critical role of adaptive dual variable update. Comprehensive numerical experiments demonstrate the merits of the proposed algorithm framework.