Research map / Bandits and online learning / Online convex optimization and games
Overcoming Brittleness in Pareto-Optimal Learning Augmented Algorithms
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.
Shows that Pareto-optimal learning-augmented one-way trading algorithms are brittle to small prediction errors, and proposes profile-based threshold algorithms (with a feasibility test) plus an adaptive Pareto-optimal algorithm that dominates prior Pareto-optimal ones.
Problem
Pareto-optimal consistency/robustness tradeoffs for learning-augmented online algorithms are brittle: tiny prediction errors can force performance equal to worst-case robustness. Also, existing Pareto-optimal one-way trading algorithms are tailored to pessimistic worst-case inputs.
Approach
Introduces user-specified performance profiles that map prediction error intervals to performance ratio bounds, an O(l) algorithm to decide profile feasibility and build a threshold function that respects it, and an adaptive threshold algorithm (Ada-PO) that is Pareto-optimal and lexicographically dominates other Pareto-optimal algorithms.
Key results
- Profile-based algorithm achieves a constant performance ratio t2 across the interval [0.9p̂,1.1p̂] where PO degrades to robustness r=4, while remaining r-robust.
- On 100 random worst-case sequences, Profile improves upon PO by 20% to 50% when p*<p̂, is worse by 10% to 20% when p*>p̂, with 22% average improvement.
- Ada-PO outperforms PO for every observed maximum rate above the prediction on Bitcoin sequences, at the cost of increased brittleness.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the profile-based algorithm instead of PO when p* < p̂ | One-way trading on randomly defined worst-case sequences · 100 randomly defined worst-case sequences, p* < p̂ | relative performance improvement over PO: 20% to 50% | Helped |
| Use the profile-based algorithm instead of PO when p* > p̂ | One-way trading on randomly defined worst-case sequences · 100 randomly defined worst-case sequences, p* > p̂ | relative performance difference from PO: 10% to 20% | Hurt |
| Use the profile-based algorithm instead of PO across the sampled prediction errors | One-way trading on randomly defined worst-case sequences · 100 randomly defined worst-case sequences | average relative performance improvement over PO: 22% | Helped |
| Use Ada-PO instead of PO on sequences with observed rates above the prediction | One-way trading on Bitcoin exchange-rate sequences · Bitcoin exchange rates, observed maximum rate greater than p̂ | performance ratio | Helped |
Surprising findings
- Pareto-optimal max-rate predictions are brittle: an arbitrarily small prediction error can force a Pareto-optimal algorithm to achieve its full robustness ratio.
Limitations
- Analysis restricted to one-way trading with max-rate prediction; extension to other problems (contract scheduling, two-way trading) is only sketched.
- Profile-based algorithm is worse than PO when the maximum rate exceeds the prediction (by 10-20%).
Experimental setup
Datasets: Bitcoin to USD daily exchange rates (last 1000 days, ending May 20, 2024) synthetic worst-case sequences
Benchmarks: synthetic worst-case one-way trading sequences Bitcoin daily exchange rate sequences
Metrics: performance ratio (OPT/ALG) relative performance improvement over PO
Baselines: PO (state-of-the-art Pareto-optimal OTA)
Builds on: Pareto-optimal one-way trading with predictions (Lorenz/El-Yaniv style OTA) game against a lenient adversary threat-based policies
Closest papers by meaning
- Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search (ICML 2025 · similarity 0.89)
- Learning-Augmented Algorithms with Explicit Predictors (NeurIPS 2024 · similarity 0.86)
- Gradient-Variation Online Learning under Generalized Smoothness (NeurIPS 2024 · similarity 0.86)
- Learning-Augmented Online Bidding in Stochastic Settings (NeurIPS 2025 · similarity 0.86)
- Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems (ICML 2025 · similarity 0.85)
- Online Learning under Budget and ROI Constraints via Weak Adaptivity (ICML 2024 · similarity 0.85)
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.