Research map / Bandits and online learning / Online convex optimization and games
Cumulative Regret Analysis of the Piyavskii–Shubert Algorithm and Its Variants for Global Optimization
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.
Analyzes cumulative regret of the Piyavskii-Shubert algorithm and simpler variants for univariate global optimization under Lipschitz, Lipschitz-smooth, Holder, convex/concave extrema-regularity conditions, plus extensions to noise, unknown regularity and multivariate domains.
Problem
Global optimization of univariate (and multivariate) black-box functions with regularity; prior work only analyzed simple regret, leaving cumulative regret of Piyavskii-Shubert-type algorithms unanalyzed.
Approach
Introduces cumulative regret for Piyavskii-Shubert variants and derives bounds via recursive relations on regret upper bounds under an extrema-only regularity condition |f(x)-f(x_E)| <= d(|x-x_E|); also proposes a simpler variant that queries interval midpoints with scores min(f_l,f_r)-d(half-width), giving bounds for convex/concave regularities.
Key results
- For L-Lipschitz functions the traditional Piyavskii-Shubert variant has cumulative regret R_T <= 2L log(4T), and for L-Lipschitz smooth functions R_T <= H (constant in T).
- The simpler midpoint variant achieves R_T <= L(2 log T + 3) for Lipschitz functions and R_T <= 2.5H for Lipschitz smooth functions.
- Lower bound argument shows minimax cumulative regret optimal up to logarithmic factors for convex or concave regularities.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Choose the interval midpoint as the candidate instead of the lowest possible-value point (ablation) | Piyavskii–Shubert algorithm · Lipschitz continuous and Lipschitz smooth functions | cumulative regret | No clear effect |
| Use repeated samples per query and average their evaluations | Piyavskii–Shubert with noisy evaluations · i.i.d. Gaussian sample noise | expected cumulative regret: O(\sigma T\sqrt{\log T}) | Helped |
Surprising findings
- Cumulative regret of grid search is linear in T despite its minimax-optimal simple regret, motivating the cumulative metric.
Experimental setup
Metrics: cumulative regret simple regret
Baselines: Piyavskii-Shubert algorithm LIPO grid search
Builds on: Piyavskii-Shubert algorithm LIPO
Closest papers by meaning
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.90)
- Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points (NeurIPS 2026 · similarity 0.89)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.89)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.89)
- No Internal Regret with Non-convex Loss Functions (AAAI 2024 · similarity 0.87)
- Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · 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.