mlsanityData to 7 Oct 2026

Chasing Convex Bodies with Linear Competitive Ratio

arXiv 1905.11877 ↗First posted 28 May 2019cs.DS math.MGcited by 15

Not on the map. Why?

Abstract (arXiv)

We study the problem of chasing convex bodies online: given a sequence of convex bodies Ktsubseteq ℝd the algorithm must respond with points xt∈ Kt in an online fashion (i.e., xt is chosen before Kt+1 is revealed). The objective is to minimize the sum of distances between successive points in this sequence. Bubeck et al. (STOC 2019) gave a 2O(d)-competitive algorithm for this problem. We give an algorithm that is O(min(d, √d log T))-competitive for any sequence of length T.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 4; 2023: 1; 2024: 0; 2025: 1; 2026: 6.

15 papers.

Sort:

  1. 2021Revisiting Smoothed Online Learningcited by 29
  2. 2022Chasing Convex Bodies and Functions with Black-Box Advicecited by 19
  3. 2021Contextual Recommendations and Low-Regret Cutting-Plane Algorithmscited by 14
  4. 2022Smoothed Online Optimization with Unreliable Predictionscited by 10
  5. 2023Sequential Strategic Screeningcited by 8
  6. 2022Movement Penalized Bayesian Optimization with Application to Wind Energy Systemscited by 7
  7. 2022Smoothed Online Convex Optimization Based on Discounted-Normal-Predictorcited by 6
  8. 2021Online Optimization with Feedback Delay and Nonlinear Switching Costcited by 5
  9. 2025Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimizationcited by 3
  10. 2026Convex Optimization with Nested Evolving Feasible Setscited by 3
  11. 2026Learning-Augmented Online Minimization with Dual Predictionscited by 1
  12. 2026SCaLE: Switching Cost aware Learning and Explorationcited by 0
3 more
  1. 2026Consistent Model Chasing Is Minimax Optimal: The Exact Value of Scalar Adversarial Adaptive Control under Large Parametric Uncertaintycited by 0
  2. 2026Constrained Online Learning with Noisy Constraint Valuescited by 0
  3. 2026Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functionscited by 0