Nested Convex Bodies are Chaseable

Nikhil Bansal, Martin Böhm, Marek Eliás, Grigorios Koumoutsos, Seeun William Umboh

TL;DR

This paper introduces the first algorithm that can efficiently "chase" a sequence of nested convex bodies in high-dimensional space, achieving a competitive ratio that depends only on the dimension. This is a significant step towards solving a long-standing open problem in online algorithms and has implications for online linear programming.

What Problem Does This Paper Address?

Imagine you're trying to navigate a series of increasingly smaller rooms (convex bodies) in a high-dimensional space. At each step, you're given a new room and must move into it. Your goal is to minimize the total distance you travel. This is the "convex body chasing" problem, a fundamental challenge in online algorithms. A particularly difficult and important special case is when the rooms are "nested" – each new room is contained within the previous one. While a lower bound on the difficulty of this problem was known, no efficient algorithm existed that could guarantee a good performance based solely on the dimension of the space. This paper tackles this challenge by developing the first algorithm that achieves a dimension-dependent competitive ratio for nested convex body chasing.

Methods

The authors employ a clever reduction strategy. They first show that solving the general nested convex body chasing problem can be reduced to solving a "bounded chasing" problem. In the bounded version, all requested bodies are contained within a ball of a certain radius around the starting point. The key insight here is that bounding the absolute distance traveled in the bounded case simplifies the analysis compared to the relative distance (competitive ratio) required for the general case.

The core of their solution lies in a recursive algorithm for the bounded chasing problem. This algorithm works by breaking down the d-dimensional problem into d instances of a (d-1)-dimensional problem, each operating on a hyperplane. This recursive structure, combined with a "recentering" step that ensures progress by shrinking the search space, allows them to bound the total distance traveled. The analysis relies on geometric properties of convex bodies, including the minimum-volume enclosing ball and dimension reduction techniques.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Reduction to Bounded Chasing: The problem of achieving a dimension-dependent competitive ratio for general nested convex body chasing can be simplified by first solving a bounded version. This is a powerful technique for tackling online problems.
  • Recursive Hyperplane Decomposition: Breaking down a d-dimensional problem into d instances of a (d-1)-dimensional problem on hyperplanes is a key algorithmic strategy. This allows for a structured recursive solution.
  • Geometric Progress: The algorithm makes progress by ensuring that after a "recentering" step, the search space (represented by an enclosing ball) shrinks geometrically. This is crucial for bounding the total distance traveled.
  • Failure of Simple Heuristics: The paper demonstrates that intuitive approaches like moving to the centroid or the center of the minimum volume enclosing ellipsoid of a convex body can perform arbitrarily poorly in this setting, highlighting the inherent difficulty of the problem.

Key Results

The paper presents a novel algorithm for chasing nested convex bodies in $\mathbb{R}^d$ with a competitive ratio of $O(6d(d!)^2)$. This is the first algorithm to achieve a competitive ratio that depends only on the dimension $d$, resolving a long-standing open problem. The authors also provide lower bounds by showing that simple ellipsoid-based and centroid-based algorithms are not competitive.

Limitations and Future Work

The authors acknowledge that their algorithm's competitive ratio, while dimension-dependent, is polynomial in $d$. A major open question is whether a significantly better (e.g., exponential) dependency on $d$ is possible. Future work could explore extending these techniques to more general convex body chasing problems or investigating tighter bounds for the nested case. The paper also hints at connections to online linear programming, suggesting that this work could pave the way for more general online LP solvers.

Summary updated

Abstract

In the Convex Body Chasing problem, we are given an initial point $$v_0 \in \mathbb {R}^d$$ v0∈Rd and an online sequence of n convex bodies $$F_1, \ldots , F_n$$ F1,…,Fn. When we receive $$F_t$$ Ft, we are required to move inside $$F_t$$ Ft. Our goal is to minimize the total distance traveled. This fundamental online problem was first studied by Friedman and Linial (DCG 1993). They proved an $$\varOmega (\sqrt{d})$$ Ω(d) lower bound on the competitive ratio, and conjectured that a competitive ratio depending only on d is possible. However, despite much interest in the problem, the conjecture remains wide open. We consider the setting in which the convex bodies are nested: $$F_1 \supset \cdots \supset F_n$$ F1⊃⋯⊃Fn. The nested setting is closely related to extending the online LP framework of Buchbinder and Naor (ESA 2005) to arbitrary linear constraints. Moreover, this setting retains much of the difficulty of the general setting and captures an essential obstacle in resolving Friedman and Linial’s conjecture. In this work, we give a f(d)-competitive algorithm for chasing nested convex bodies in $$\mathbb {R}^d$$ Rd.
BibTeX
@inproceedings{bansal2018nested,
  author = {Nikhil Bansal and Martin Böhm and Marek Eliás and Grigorios Koumoutsos and Seeun William Umboh},
  title = {{Nested Convex Bodies are Chaseable}},
  booktitle = {Algorithmica},
  year = {2018},
  url = {https://openreview.net/forum?id=2S40Gt65lP},
}
Figure