Abstract
In many real-world optimization scenarios, such as recommender systems and drug discovery, the underlying objective function is unknown and gradients are inaccessible. Instead, we must rely on preference feedback—comparisons between items. While traditional preference-based optimization focuses on pairwise comparisons, modern systems often allow for parallel or multi-item queries. This paper investigates the theoretical and practical speedups achievable when querying $m$ items simultaneously. We introduce algorithms for two feedback models: Batched Sign-Feedback and Battling (Multiwise-Winner) Feedback. Our results demonstrate that parallelization yields significant convergence gains, with the Batched model achieving a linear $1/m$ speedup and the Battling model achieving a $1/\log m$ speedup, both of which are shown to be information-theoretically optimal.
Introduction
Optimization typically assumes access to a function's numerical values or its gradient. However, in human-centric applications like search engines or movie recommendations, obtaining a precise numerical score for a single item is difficult and often inconsistent. Humans are far more adept at comparing items—stating that "Item A is better than Item B"—than they are at assigning absolute values. This has led to the rise of preference-based optimization, often framed as the "Dueling Bandit" problem.
While standard algorithms focus on duels between two items, modern computing environments and user interfaces naturally support multiway interactions. For instance, a search engine displays a list of results, and a user’s click indicates a "winner" among many candidates. This paper addresses a fundamental question: How much faster can we find the optimal item if we can compare $m$ items at once instead of just two?
Feedback Models and Methodology
To generalize standard pairwise comparisons, the authors propose two distinct feedback models:
1. Batched Sign-Feedback
In this model, the learner queries $m$ pairs of points in parallel. For each pair, the learner receives a binary comparison (the "sign" of the difference in function values). This model represents a scenario where multiple independent comparisons can be processed simultaneously, such as in parallel laboratory experiments.
2. Battling (Multiwise-Winner) Feedback
This model is more restrictive and realistic for user interfaces. The learner queries a set of $m$ points and receives only the identity of the "winner" (the point with the minimum function value). This provides only a single piece of information about the relative ranking of the $m$ items.
Aggregated Normalized Gradient Descent (NGD)
To optimize under these models, the authors propose Aggregated Normalized Gradient Descent (NGD).
- For the Batched case, the algorithm estimates the gradient direction by averaging the directions suggested by the $m$ parallel comparisons.
- For the Battling case, the authors employ a Structured Query Set. By arranging points in a specific geometric configuration based on a hypercube graph, they demonstrate how to extract $\log m$ independent pairwise comparisons from a single multiwise winner. This clever information extraction is the key to accelerating convergence in the more restrictive Battling model.
For functions that are strongly convex, the authors introduce an epoch-based "warm start" strategy. In this approach, the search space is iteratively pruned, allowing the algorithm to zoom in on the optimum with exponential efficiency.
Theoretical Insights and Results
The paper's primary contribution is the derivation of tight convergence rates and matching lower bounds, establishing the fundamental limits of multiway preference optimization.
- Linear vs. Logarithmic Gains: The degree of speedup depends heavily on the feedback structure. Parallelizing $m$ separate comparisons (Batched) provides a linear $1/m$ speedup. Conversely, receiving one winner from $m$ items (Battling) provides a $1/\log m$ speedup.
- Convergence Rates: For smooth functions, the Batched model achieves a rate of $\tilde{O}(\frac{d}{m\epsilon})$, while the Battling model achieves $\tilde{O}(\frac{d}{\log m \cdot \epsilon})$.
- Optimality: The authors prove that no algorithm can surpass these rates, meaning their NGD-based approaches are mathematically optimal for these feedback models.
- Strong Convexity: Under strong convexity assumptions, the convergence becomes exponential relative to the number of rounds, scaling as $\tilde{O}(\frac{d}{m\alpha} \log \frac{1}{\epsilon})$ for batched feedback.
Empirical Validation
The theoretical findings were corroborated through experiments on several synthetic benchmark functions, chosen to test different aspects of the algorithms:
- Quadratic functions: $f(x) = \|x\|_2^2$, serving as the standard convex baseline.
- Sum of Sines: $f(x) = 3 + \sum \sin(x_i)$, testing the algorithms on non-quadratic surfaces.
- L1-Regularized Quadratic: $f(x) = \|x\|_2^2 + \frac{1}{2}\|x\|_1$, testing performance with non-smooth regularization.
In these tests (conducted with dimension $d=32$ and batch size $m=6$), the $m$-Batched NGD demonstrated the fastest convergence, followed by the $m$-Battling (s-NGD). Both significantly outperformed the standard single-duel NGD, validating the advantage of multiway querying.
Discussion and Future Work
While this work provides a rigorous foundation for multiway preference optimization, several avenues for future research remain:
- Smoothness Constraints: The current algorithms require the objective function to be smooth (Lipschitz continuous gradient). Extending these optimal rates to arbitrary convex functions is a significant open challenge.
- Noise Robustness: While the paper addresses noisy feedback through resampling, this increases query complexity. More efficient, noise-tolerant query strategies could further improve practical performance.
- Dynamic Environments: The current model assumes a static objective function. In applications like social media feeds, user preferences evolve over time. Adapting these multiway strategies to "online" or non-stationary settings would be a valuable extension for real-world deployment.
Summary updated