# Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2019.

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

- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Contextual Decision-Making with Knapsacks Beyond the Worst Case](https://mlsanity.com/paper/2211.13952/) (2022)
- [Online Linear Programming with Batching](https://mlsanity.com/paper/2408.00310/) (2024)
- [Non-Stationary Online Resource Allocation: Learning from a Single Sample](https://mlsanity.com/paper/2602.18114/) (2026)
- [A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming](https://mlsanity.com/paper/2603.14673/) (2026)
- [Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates](https://mlsanity.com/paper/2607.02150/) (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)

I study how the shadow prices of a linear program that allocates an endowment of nβ ∈ ℝm resources to n customers behave as n rightarrow ∞. I show the shadow prices (i) adhere to a concentration of measure, (ii) converge to a multivariate normal under central-limit-theorem scaling, and (iii) have a variance that decreases like Theta(1/n). I use these results to prove that the expected regret in citesLi2019b online linear program is Theta(log n), both when the customer variable distribution is known upfront and must be learned on the fly. I thus tighten citeauthorsLi2019b upper bound from O(log n log log n) to O(log n), and extend citesLueker1995 Omega(log n) lower bound to the multi-dimensional setting. I illustrate my new techniques with a simple analysis of citesArlotto2019 multisecretary problem.