Research map / Bandits and online learning / Online convex optimization and games
Wait-Less Offline Tuning and Re-solving for Online Decision Making
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a parallel multi-phase online linear programming algorithm that re-solves the LP every f steps offline while running first-order subgradient updates in the first and last batches and fine-tuning between re-solves, achieving O(log(T/f)+sqrt(f)) regret with no decision delay.
Problem
Online linear programming for resource allocation under stochastic inputs: LP-based methods have low regret but are computationally expensive and cause decision delays, while first-order methods are fast but have weaker regret (O(sqrt T) or O(T^{1/3})).
Approach
Decouple online learning from decision-making: re-solve the LP periodically at frequency f in a parallel offline path, and make immediate decisions using the latest dual prices, with first-order subgradient fine-tuning between re-solves; a unified regret decomposition (dual convergence, constraint violation, leftover resources) enables a combined analysis yielding a spectrum between LP-based and f
Key results
- placeholder
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase re-solving frequency (ablation) | Algorithm 1 · Input I and Input II, T from 10^3 to 10^6 | regret | Helped |
| use the proposed periodic LP re-solving and first-order framework instead of the classic first-order method | OLP · Input I and Input II, T from 10^3 to 10^6 | regret | Helped |
| add intermediate first-order updates between LP re-solves (ablation) | Enhanced Multi-Start OLP Algorithm · OLP experiments | regret | Helped |
Limitations
- Analysis assumes finite known horizon T and i.i.d. inputs with continuous support and non-degeneracy assumptions.
- Unknown horizon is not handled; sublinear regret may be impossible in that setting.
- Warm-start improvement to O(log(T/f)+f^{1/3}) requires additional conditions.
Experimental setup
Benchmarks: simulated OLP instances with uniform and normal inputs
Metrics: regret constraint violation running time
Baselines: LP-based re-solving method first-order mirror descent O(sqrt T) method restart first-order method O(T^{1/3}) infrequent re-solving method
Builds on: LP-based online dual algorithm (Li and Ye style re-solving) first-order online subgradient method for OLP restart first-order OLP algorithm
Closest papers by meaning
- Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods (ICML 2024 · similarity 0.94)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.87)
- Online Resource Allocation With General Constraints (NeurIPS 2026 · similarity 0.87)
- On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning (ICML 2025 · similarity 0.87)
- Dynamic Regret in Online Convex Optimization with Indicator Switching Costs (NeurIPS 2026 · similarity 0.87)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.