Infrequent Resolving Algorithm for Online Linear Programming

arXiv:2408.00465 · cs.DS, cs.LG, math.OC · Submitted 2024-08-01 · Read on arXiv

cs.DS, cs.LG, math.OC

Submitted: 2024-08-01

Updated: 2026-09-21

Comments: With very few resolvings, we can achieve constant regret (even without the non-degeneracy assumption) for OLP and NRM problems

Project page: https://www.statista.com/statistics/1388573/top-travel-tourism-websites-by-monthly-visits

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Regret — 182× in this paper · explained in 3 episodes
• Degeneracy — 27× in this paper · explained in 3 episodes
• Benchmark — 16× in this paper · explained in 2 episodes
• Argmax with Infrequent Resolving — 4× in this paper
• Decoupling — 3× in this paper · explained in 2 episodes
• Decoupling Learning and Decision — 3× in this paper
• Resource Constraints — 3× in this paper · explained in 3 episodes
• Argmax with Frequent Resolving — 2× in this paper
• Budget-Updating Fast — 2× in this paper
• Contextual Bandits — 2× in this paper · explained in 3 episodes
• Core — 2× in this paper · explained in 2 episodes
• Non-stationarity — 1× in this paper · explained in 2 episodes
• PID Controller — 1× in this paper · explained in 2 episodes
• Trace — 1× in this paper · explained in 2 episodes

Sources

• Analysis of Dual-Based PID Controllers through Convolutional Mirror Descent
• Sequential Batch Learning in Finite-Action Linear Contextual Bandits
• On the absolute constants in the Berry-Esseen type inequalities for identically distributed summands
• Near-Optimal Primal-Dual Algorithms for Quantity-Based Network Revenue Management

Related papers

• Cascaded Learned Bloom Filter for Optimizing Model-Filter Size Balance and Fast Rejection
• Edge-Private Matching Kernels Through Local Decoding
• Local Node Differential Privacy
• Cheaper by the Batch: Shared Traversal for Genotype Graph Editing
• Scalable Algorithms for Approximate DNF Model Counting
• On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions