Minimax Regret for Bandit Convex Optimisation of Ridge Functions

Tor LattimorearXiv 2021 · arXiv

Abstract

This paper establishes a new, nearly optimal minimax regret bound of $O(d\sqrt{n} \text{ polylog}(n))$ for adversarial bandit convex optimization (BCO) when the loss functions are restricted to "ridge functions"—functions that vary only along a single, fixed (but unknown) direction. By leveraging an information-theoretic framework, the work demonstrates that the $O(\sqrt{n})$ regret rate is achievable with a linear dependence on the dimension $d$, significantly narrowing the gap in our understanding of structured bandit problems.

Introduction

Bandit Convex Optimization (BCO) is a fundamental problem in online learning where a learner repeatedly selects a point $x_t$ from a convex set $\mathcal{K}$ and incurs a loss $f_t(x_t)$. In the bandit setting, the learner only observes the scalar value $f_t(x_t)$ rather than the full function or its gradient. While general adversarial BCO has known regret bounds of $O(d^{2.5}\sqrt{n})$, these are often considered loose or computationally impractical.

This work focuses on Ridge Functions, defined as $f_t(x) = g_t(\langle x, \theta \rangle)$. Here, the function depends on the input $x$ only through its projection onto a single direction $\theta$. While the scalar functions $g_t$ can change arbitrarily over time, the direction $\theta$ is unknown but remains constant. This structure is common in high-dimensional statistics and generalized linear models. The central question addressed is whether this specific geometry can be exploited to achieve better regret bounds.

The scalar function $g$ and its relationship to the ridge direction analysis.

Methodology: Information-Theoretic Analysis

The paper employs an information-theoretic analysis based on the "Information Ratio" framework. This framework relates the expected regret in a given round to the "information gained" about the unknown parameter $\theta$.

Key technical components include:

  1. Information Ratio Bound: A version of the information ratio is used to quantify the trade-off between immediate regret and learning about the hidden ridge direction.
  2. Exploration Distributions: The proof relies on the existence of probability distributions over the constraint set $\mathcal{K}$ that maintain "high projected variance" in every direction, ensuring the learner can efficiently learn about $\theta$.
  3. Level Set Perturbations: The author introduces perturbed versions of the loss function and analyzes their level sets to construct a sequence of exploration policies.
  4. Minimax Duality: Like many recent breakthroughs in BCO, the proof uses minimax duality to show the existence of a good strategy. This is particularly important because the class of ridge functions is not closed under convex combinations, which complicates standard information-theoretic machinery.
Geometry of the constraint set $\mathcal{K}$ and the level sets $\mathcal{L}_k$ used for constructing exploration policies.

Key Insights

  • Fixed Direction Persistence: The most critical insight is that while the functions $g_t$ vary adversarially, the fixed nature of $\theta$ allows the learner to accumulate information about the problem's geometry across rounds.
  • Linear Dimensionality: The result shows a regret bound that scales linearly with $d$. In the stochastic linear setting, the lower bound is $\Omega(d\sqrt{n})$; this paper shows that for ridge functions, we can get very close to this lower bound even in the adversarial setting.
  • Information-Regret Trade-off: The analysis demonstrates that for any convex ridge function, there exists a sampling distribution such that the learner either suffers low regret or learns a significant amount about the hidden direction $\theta$.

Main Results

The primary contribution is Theorem 2, which states that if the constraint set $\mathcal{K}$ contains the unit sphere, the minimax regret $R_n$ satisfies: $$R_n \leq C \cdot d\sqrt{n} \log(n \cdot \text{diam}(\mathcal{K}))$$ where $C$ is a universal constant.

This result is significant because it achieves the $O(\sqrt{n})$ rate typical of "easy" bandit problems and provides a major improvement in dimensional dependence compared to the general BCO literature.

Limitations and Future Work

The proof is non-constructive, demonstrating the existence of a strategy without providing a computationally efficient algorithm. Additionally, the analysis requires the ridge direction $\theta$ to remain constant over time; extending this to time-varying directions remains an open and difficult challenge. Future work may also focus on improving logarithmic factors and relaxing the geometric assumptions on the constraint set $\mathcal{K}$.

Summary updated

Abstract

We analyse adversarial bandit convex optimisation with an adversary that is restricted to playing functions of the form $f_t(x) = g_t(\langle x, θ\rangle)$ for convex $g_t : \mathbb R \to \mathbb R$ and unknown $θ\in \mathbb R^d$ that is homogeneous over time. We provide a short information-theoretic proof that the minimax regret is at most $O(d \sqrt{n} \log(n \operatorname{diam}(\mathcal K)))$ where $n$ is the number of interactions, $d$ the dimension and $\operatorname{diam}(\mathcal K)$ is the diameter of the constraint set.
BibTeX
@misc{lattimore2021minimax,
  author = {Tor Lattimore},
  title = {{Minimax Regret for Bandit Convex Optimisation of Ridge Functions}},
  year = {2021},
  eprint = {2106.00444},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.00444},
}
Figure