Research map / Bandits and online learning / Online convex optimization and games
Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods
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 decoupling learning and decision-making in first-order online linear programming by running a learning path and a decision path with a one-time restart, achieving O(T^{1/3}) regret and constraint violation under continuous-support assumptions, beating the O(√T) barrier.
Problem
First-order online linear programming (online resource allocation) typically achieves only O(√T) regret, while LP-based methods reach O(log T); it is open whether first-order methods can go beyond O(√T) under continuous distributions.
Approach
Use two separate first-order paths: a decision path (subgradient with stepsize αe then αp) and a learning path (a convergent dual learner such as SGD with 1/(µt) stepsize, ASSG, or SADAGRAD). After an exploration phase, the decision path restarts from the learner's estimate of the dual optimum and continues with a smaller stepsize, avoiding the learning/adaptivity dilemma.
Key results
- Theory: two-path two-phase algorithm with SGD 1/(µt) learner achieves E[r+v] = O(T^{1/3}), beating the O(√T) barrier of prior first-order OLP methods.
- Experiments: M2 shows up to 5x improvement over the single-path baseline M0 in regret (e.g., T=1e3: 4.18 vs 12.37 average regret).
- Compared with LP-based MLP, M2 at T=1e5 runs in 0.064 s versus 4742.9 s, though MLP has lower regret (5.91 vs 24.00).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Decouple learning and decision-making using M2 | Online resource allocation, first distribution · T=103 | regret: 12.37 -> 4.18; 3.82 | Mixed |
| Decouple learning and decision-making using M2 | Online resource allocation, first distribution · T=104 | regret: 38.24 -> 13.83; 4.12 | Mixed |
| Decouple learning and decision-making using M2 | Online resource allocation, first distribution · T=105 | regret: 123.03 -> 24.00; 5.91 | Mixed |
| Use M2 instead of MLP | Online resource allocation, first distribution · T=105 | running time: 4742.9 -> 6.4 × 10−2 | Helped |
| Use M2 instead of MLP | Online resource allocation, first distribution · T=105 | regret: 5.91 -> 24.00 | Hurt |
| Replace no exploration (M0) with M2's exploration and learning restart (ablation) | Online resource allocation, first distribution · T=105 | regret: 123.03 -> 24.00 | Helped |
| Use SGD with O(1/(µt)) for learning instead of fixed-step SGD (ablation) | Decoupled online LP algorithm · Online linear programming under A1–A6 | regret and constraint violation: O(T 2/5) -> O(T 1/3) | Helped |
| Use ASSG or SADAGRAD instead of SGD with O(1/(µt)) for learning (ablation) | Decoupled online LP algorithm · Online linear programming under A1–A6 | regret and constraint violation: O(T 1/3) -> O(T 1/3 log T) | Hurt |
| Set exploitation stepsize to T −2/3 (ablation) | M2 · Online resource allocation, stepsize validation | regret and constraint violation | Helped |
Surprising findings
- Knowing the distribution P (so that y* is known) alone does not beat O(√T) for the plain subgradient method, and first-order methods that learn y* better (SGD with known µ, ASSG, SADAGRAD) still suffer O(√T) regret due to slow adaptivity.
Limitations
- Regret bound O(T^{1/3}) is still worse than the O(log T) achieved by LP-based methods under the same assumptions.
- Analysis relies on a strong growth (quadratic growth) condition and non-degeneracy assumptions A1-A6, and the best rates require knowing or upper-bounding the growth parameter µ.
- The restart strategy is one-time and simple; multi-stage variants are only mentioned as possibilities.
Experimental setup
Datasets: synthetic distributions satisfying assumptions A1-A6 synthetic distributions violating assumptions (normal, discrete finite support)
Benchmarks: synthetic online linear programming instances (T from 1e2 to 1e6)
Metrics: regret plus constraint violation r(x)+v(x) dual solution convergence running time
Baselines: M0 (single-path subgradient with αp = T^{-1/2}) LP-based OLP algorithm (Li and Ye Algorithm 3) SGD with fixed stepsize
Builds on: LP-resolving (Li and Ye 2019/2021) subgradient dual method (Agrawal and Devanur 2014 / Balseiro et al.) parameter-free ASSG SADAGRAD
Closest papers by meaning
- Wait-Less Offline Tuning and Re-solving for Online Decision Making (ICML 2025 · similarity 0.94)
- Online Resource Allocation With General Constraints (NeurIPS 2026 · similarity 0.88)
- Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound (NeurIPS 2025 · similarity 0.88)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.87)
- Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability (ICML 2025 · similarity 0.87)
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 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.