Research map / Bandits and online learning / Online convex optimization and games
Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
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.
Gives a deterministic Pareto-optimal and smooth threshold algorithm for learning-augmented one-max-search, proves its smoothness is optimal among Pareto-optimal algorithms, and extends the analysis to stochastic prices and predictions via optimal transport.
Problem
Learning-augmented one-max-search needs a consistency-robustness trade-off that is both Pareto-optimal and smooth (not brittle to small prediction errors), and an analysis for stochastic prices and predictions.
Approach
A family of threshold functions Phi^rho_r parametrised by rho in [0,1] that stays on the consistency-robustness Pareto front; rho=1 maximises smoothness, with a matching lower bound on the smoothness exponent, yielding a triple Pareto front. Smoothness is then used to bound expected performance under random prices and predictions, including via optimal transport couplings.
Key results
- The algorithm A^1_r achieves smoothness exponent s = max(1, ln(theta)/ln(r theta) - 2) under the multiplicative error, matching a lower bound for all Pareto-optimal deterministic algorithms when r is in [theta^-1, theta^-2/3].
- Under the additive error, the proposed threshold attains the optimal beta* smoothness constant among Pareto-optimal algorithms for all r in [theta^-1, theta^-1/2].
- On Bitcoin data, A^1_r degrades gradually as prediction error grows, whereas the prior algorithm A^0_r quickly drops to the robustness guarantee r.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed deterministic Pareto-optimal smooth algorithm A^1_r instead of A^0_r | one-max-search · synthetic worst-case instances | worst-case payoff ratio | Helped |
| Set ρ=1 instead of ρ=0 (ablation) | A^ρ_r · synthetic worst-case instances | worst-case payoff ratio | Helped |
| Set ρ=0.5 instead of ρ=0 (ablation) | A^ρ_r · synthetic worst-case instances | worst-case payoff ratio | Helped |
| Use A^1_r instead of A^0_r | one-max-search · Bitcoin price dataset | empirical expected worst-window payoff ratio | Helped |
| Set ρ=1 instead of ρ=0 (ablation) | A^ρ_r · Bitcoin price dataset | empirical expected worst-window payoff ratio | Helped |
| Use A^1_r with its proposed threshold family | deterministic one-max-search · one-max-search | smoothness exponent for additive prediction error | Helped |
| Use ρ=1 rather than ρ=0 in the threshold family (ablation) | A^ρ_r · one-max-search | smoothness exponent for multiplicative prediction error | Helped |
Surprising findings
- Randomization is not needed to achieve Pareto-optimality with smoothness, contrary to prior randomized approaches.
Limitations
- Smoothness guarantee for r in [theta^-2/3, theta^-1/2] may admit further improvement
- Experiments are small-scale (synthetic sequences and one Bitcoin dataset) and rely on a specific prediction model
Experimental setup
Datasets: Bitcoin USD minute-level prices 2020-2024 (synthetic price sequences also used)
Benchmarks: synthetic worst-case instances I_n(q) with theta=5 Bitcoin price windows (theta about 28)
Metrics: consistency robustness smoothness exponent worst-case ratio of expected payoff to max price
Baselines: Sun et al. 2021 threshold algorithm (rho=0) randomized one-way trading algorithm Pareto-optimal algorithm of Sun et al.
Builds on: one-max-search threshold algorithm (El-Yaniv et al.) Pareto-optimal learning-augmented one-max-search (Sun et al.) smooth one-way trading (Christianson et al.)
Closest papers by meaning
- Online Search with Best-Price and Query-Based Predictions (AAAI 2022 · similarity 0.91)
- Overcoming Brittleness in Pareto-Optimal Learning Augmented Algorithms (NeurIPS 2024 · similarity 0.89)
- Learning-Augmented Online Bidding in Stochastic Settings (NeurIPS 2025 · similarity 0.88)
- Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points (NeurIPS 2026 · similarity 0.86)
- AlphaPareto: Formulaic Alpha Discovery with LLM-Guided Multi-Objective Reinforcement Learning (NeurIPS 2026 · similarity 0.86)
- Learning Thresholds with Latent Values and Censored Feedback (ICLR 2024 · similarity 0.86)
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.