Faster Convergence with MultiWay Preferences

Aadirupa Saha, Vitaly Feldman, Yishay Mansour, Tomer Koren

Abstract

We address the problem of convex optimization with preference feedback, where the goal is to minimize a convex function given a weaker form of comparison queries. Each query consists of two points and the dueling feedback returns a (noisy) single-bit binary comparison of the function values of the two queried points. Here we consider the sign-function-based comparison feedback model and analyze the convergence rates with batched and multiway (argmin of a set queried points) comparisons. Our main goal is to understand the improved convergence rates owing to parallelization in sign-feedback-based optimization problems. Our work is the first to study the problem of convex optimization with multiway preferences and analyze the optimal convergence rates. Our first contribution lies in designing efficient algorithms with a convergence rate of $\smash{\widetilde O}(\frac{d}{\min\{m,d\} \epsilon})$ for $m$-batched preference feedback where the learner can query $m$-pairs in parallel. We next study a $m$-multiway comparison (‘battling’) feedback, where the learner can get to see the argmin feedback of $m$-subset of queried points and show a convergence rate of $\smash{\widetilde O}(\frac{d}{ \min\{\log m,d\}\epsilon })$. We show further improved convergence rates with an additional assumption of strong convexity. Finally, we also study the convergence lower bounds for batched preferences and multiway feedback optimization showing the optimality of our convergence rates w.r.t. $m$.

Introduction

In many real-world applications, such as recommender systems, search engines, or drug testing, traditional first-order (gradient) or zeroth-order (function value) oracles are often unavailable. Instead, we must rely on preference feedback, where a user indicates a preference for one item over another without providing numerical values. While pairwise comparisons (dueling bandits) are well-studied, they often suffer from slow convergence in continuous decision spaces. This research investigates the potential for accelerated convergence through multiway preferences, where a learner can query multiple items or pairs simultaneously.

Methodology

The study introduces two primary feedback models and corresponding algorithms based on Projected Normalized Gradient Descent (P-NGD):

  1. Batched Sign-Feedback: The learner queries $m$ pairs of points simultaneously. The Batched-NGD algorithm estimates the gradient direction by aggregating $m$ random unit directions weighted by their comparison results.
  2. Battling (Multiwise-Winner) Feedback: The learner queries a set of $m$ points and receives the "winner" (the argmin). To extract maximum information, the authors utilize a Structured Query Set. By arranging points in a geometric pattern inspired by hypercubes, the algorithm can derive $\log m$ independent pairwise comparisons from a single $m$-way battle.
Structured query set for multiway feedback, illustrating the hypercube-inspired arrangement of points.

The algorithms were evaluated using synthetic convex objective functions, including quadratic sphere functions and non-quadratic smooth functions, in a 32-dimensional space ($d=32$) to validate theoretical convergence rates.

Key Insights and Theoretical Results

  • Linear Speedup in Batched Feedback: Querying $m$ pairs allows for a more stable gradient estimate. The authors prove a convergence rate of $O(1/m)$, demonstrating a speedup that is perfectly linear with the batch size (up to dimension $d$).
  • Logarithmic Speedup in Battling Feedback: When only the winner of $m$ items is observed, the information gain is lower than in the batched case. The optimal speedup is proven to be $1/\log m$.
  • Geometric Structure: Achieving the $1/\log m$ speedup requires structured queries rather than random sampling, allowing the winner's identity to reveal information about multiple directional derivatives simultaneously.
  • Optimality: The authors provide matching lower bounds, proving that their algorithms achieve the best possible convergence rates for these feedback models.

Empirical Validation

Experiments confirmed the theoretical predictions. Batched-NGD demonstrated the fastest convergence, followed by Battling-NGD, with both significantly outperforming standard single-pair NGD.

Empirical convergence rates showing the $1/m$ speedup for batched feedback (left) and the $1/\log m$ speedup for argmin (battling) feedback (right).

Under the assumption of $\alpha$-strong convexity, the error was shown to decrease exponentially with the number of queries, resulting in a $\log(1/\epsilon)$ dependence.

Conclusion and Future Work

This work establishes the first optimal convergence rates for convex optimization with multiway preferences. Key limitations include the reliance on function smoothness and the focus on noiseless feedback. Future research directions include extending these methods to non-smooth functions, developing more robust handling of stochastic preferences, and exploring non-stationary settings where user preferences may evolve over time.

Summary updated

Abstract

We address the problem of convex optimization with preference feedback, where the goal is to minimize a convex function given a weaker form of comparison queries. Each query consists of two points and the dueling feedback returns a (noisy) single-bit binary comparison of the function values of the two queried points. Here we consider the sign-function-based comparison feedback model and analyze the convergence rates with batched and multiway (argmin of a set queried points) comparisons. Our main goal is to understand the improved convergence rates owing to parallelization in sign-feedback-based optimization problems. Our work is the first to study the problem of convex optimization with multiway preferences and analyze the optimal convergence rates. Our first contribution lies in designing efficient algorithms with a convergence rate of $\smash{\widetilde O}(\frac{d}{\min\{m,d\} \epsilon})$ for $m$-batched preference feedback where the learner can query $m$-pairs in parallel. We next study a $m$-multiway comparison (‘battling’) feedback, where the learner can get to see the argmin feedback of $m$-subset of queried points and show a convergence rate of $\smash{\widetilde O}(\frac{d}{ \min\{\log m,d\}\epsilon })$. We show further improved convergence rates with an additional assumption of strong convexity. Finally, we also study the convergence lower bounds for batched preferences and multiway feedback optimization showing the optimality of our convergence rates w.r.t. $m$.
BibTeX
@inproceedings{saha2024faster,
  author = {Aadirupa Saha and Vitaly Feldman and Yishay Mansour and Tomer Koren},
  title = {{Faster Convergence with MultiWay Preferences}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=9liDYdv6Ir},
}
Figure