Contextual Search for General Hypothesis Classes

Allen Liu, Renato Paes Leme, Jon SchneiderarXiv 2020 · arXiv · OpenReview

Abstract

In the contextual pricing problem, a seller repeatedly prices products described by adversarial feature vectors, observing only binary purchasing decisions from a buyer with an unknown linear valuation. We present a polynomial-time algorithm that achieves $O(d \log \log T + d \log d)$ regret, nearly matching the $\Omega(d \log \log T)$ lower bound. By extending this to symmetric loss, we obtain a nearly optimal regret of $O(d \log d)$. These results are powered by a novel "Multiscale Steiner Potential" based on integral geometry, which bounds the value of the Steiner polynomial of a convex region across multiple scales. We further generalize this to abstract hypothesis classes and noisy feedback models.

Introduction

Contextual search is a fundamental problem in online learning where an agent seeks to learn a hidden function $f$ from a hypothesis class $\mathcal{H}$ through sequential interactions. In the specific case of contextual pricing, a seller offers an item with features $x_t \in \mathbb{R}^d$ at price $p_t$. The buyer, having a secret valuation $v$, buys if $x_t \cdot v \ge p_t$. The seller's feedback is purely binary: "bought" or "not bought."

The primary challenge in high-dimensional contextual search is that binary feedback provides very little information per round. Previous approaches often suffered from high regret (e.g., $O(d^4)$) because the "version space"—the set of candidate valuations consistent with observations—could become extremely thin or geometrically complex, making it difficult to find a "central" point for the next query.

The Multiscale Steiner Potential

This work introduces a breakthrough geometric technique: the Multiscale Steiner Potential. Instead of measuring the raw volume of the version space, the algorithm tracks the volume of the version space after it has been "inflated" by a ball of radius $z$. This inflated volume is described by the Steiner polynomial, a degree-$d$ polynomial whose coefficients are the intrinsic volumes of the set.

The algorithm selects an appropriate scale $i$ based on whether the width of the current uncertainty set in the direction of the context vector exceeds a threshold.

As illustrated above, the algorithm operates across multiple scales. By evaluating the "width" of the uncertainty set in the direction of the current context vector, the learner can decide which scale $i$ is most appropriate for the current round. This multiscale approach ensures that the learner always makes progress, regardless of whether the uncertainty set is large and round or narrow and elongated.

Regularization via Inflation

The use of Steiner polynomials acts as a form of geometric regularization. By considering the Minkowski sum of the uncertainty set and a ball, the algorithm effectively smooths the search space. This prevents the cutting process—where the version space is halved based on feedback—from creating sets that are too difficult to navigate.

Geometric construction of the potential function, showing the uncertainty set (black) inflated by a ball (yellow halo) and a cutting plane $C$ used to refine the hypothesis.

In each round, the algorithm uses a randomized perturbation of the median value within the inflated set. This ensures that, in expectation, each query significantly reduces the Steiner potential, leading to rapid convergence toward the true valuation.

Key Results and Generalizations

The proposed framework yields several state-of-the-art results:

  • Contextual Pricing: Regret is reduced to $O(d \log \log T + d \log d)$, a significant improvement over the previous $O(d^4 \log \log T)$.
  • Symmetric Contextual Search: For symmetric loss, the algorithm achieves $O(d \log d)$ regret, nearly matching the $\Omega(d)$ lower bound.
  • General Hypothesis Classes: The geometric ideas are abstracted to any class with a finite covering dimension $d$, resulting in $O(d^2)$ regret. This applies to complex models like sparse linear functions or unit-demand buyers.
  • Noisy Feedback: The algorithm is robust to noise. Even if feedback is flipped with probability $p < 1/2$, the learner can achieve $O(\text{poly}(d))$ regret that does not grow with the number of rounds $T$.

Conclusion

By shifting the focus from raw volume to the more robust Steiner potential, this work provides a near-optimal solution to the contextual search problem. The multiscale geometric framework not only settles long-standing questions in contextual pricing but also provides a powerful toolkit for learning abstract hypothesis classes under thin, binary feedback.

Summary updated

Abstract

In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in $\mathbb{R}^d$ and only observes the purchasing decisions of a buyer with a fixed but unknown linear valuation over the products. The regret measures the difference between the revenue the seller could have obtained knowing the buyer valuation and what can be obtained by the learning algorithm. We give a poly-time algorithm for contextual pricing with $O(d \log \log T + d \log d)$ regret which matches the $\Omega(d \log \log T)$ lower bound up to the $d \log d$ additive factor. If we replace pricing loss by the symmetric loss, we obtain an algorithm with nearly optimal regret of $O(d \log d)$ matching the $\Omega(d)$ lower bound up to $\log d$. These algorithms are based on a novel technique of bounding the value of the Steiner polynomial of a convex region at various scales. The Steiner polynomial is a degree $d$ polynomial with intrinsic volumes as the coefficients. We also study a generalized version of contextual search where the hidden linear function over the Euclidean space is replaced by a hidden function $f : \mathcal{X} \rightarrow \mathcal{Y}$ in a certain hypothesis class $\mathcal{H}$. We provide a generic algorithm with $O(d^2)$ regret where $d$ is the covering dimension of this class. This leads in particular to a $\tilde{O}(s^2)$ regret algorithm for linear contextual search if the linear function is guaranteed to be $s$-sparse. Finally we also extend our results to the noisy feedback model, where each round our feedback is flipped with a fixed probability $p < 1/2$.
BibTeX
@misc{liu2020contextual,
  author = {Allen Liu and Renato Paes Leme and Jon Schneider},
  title = {{Contextual Search for General Hypothesis Classes}},
  year = {2020},
  eprint = {2003.01703},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2003.01703},
}
Figure