Comparisons Are All You Need for Optimizing Smooth Functions

The paper proposes algorithms for optimization where the learner only has access to comparisons between the function values at two points. Under this setting, the authors propose algorithms for both convex and non-convex settings that achieve order-optimal performance in terms of sample complexity.

The paper studies comparison-based optimization algorithms and prove the convergence.

The authors consider the gradient-free method to optimize functions without requiring function value evaluations, relying only on comparisons between function values. In particular, for convex optimization problems, an $\epsilon$-optimal solution can be found, using Theorem 2, in $\mathcal{O}(d/\epsilon)$ oracle queries, which matches the result of [Nesterov & Spokoiny, 2017] in terms of its dependence upon dimension $d$, at the same time, being worse in terms of its dependene upon $\epsilon$. The authors also suggest an algorithm with poly-logarithmic complexity based on cutting plane method. The key technical contribution is Theorem 1, that allows to construct an estimator of the direction of gradient.

The paper addresses optimization for scenarios where gradient computation is difficult or impossible. The authors focus on comparison-based methods, which leverage only the relative magnitudes of function values at different points, rather than their exact values or gradients. This approach is particularly relevant for cases like reinforcement learning from human feedback (RLHF) in training large language models, where only preferences, not precise rewards, are available. The key technical contribution is a gradient direction estimation algorithm using only comparisons, which underlies the proposed optimization methods. Their work advances comparison-based optimization, demonstrating that comparisons can achieve similar performance to zeroth-order methods that require function evaluations. Future directions include adapting accelerated gradient methods to comparison-based frameworks and extending the applicability of these methods to machine learning, particularly in preference-based RL contexts.

Motivation and possible applications in practical scenarios. Regarding your question about the motivation for our work, we agree that learning through preference-based feedback for RLHF arises from practical concerns. However, we also want to emphasize that this problem has been widely studied in RL theory since 2012 (see, for example, [8, 9]). From a theoretical perspective, optimization using comparison-based queries is a natural generalization of this setting. Furthermore, comparison-based optimization is of independent interest in optimization theory. Its ability to provide deeper insights into the underlying mathematical structure has led to the exploration of its variants within the context of direct search methods [10, 11].

Regarding the connection to LLMs, recent works such as [12] found out that LLMs whose parameters are taken from $\{-1, 0, 1\}$ match the full-precision (i.e., FP16 or BF16) Transformer LLM with the same model size and training tokens in terms of both perplexity and end-task performance. This suggests an interesting perspective for the optimization theory behind LLMs to be investigated in the future.

Given the purely theoretical nature of our work, it may be challenging to directly apply our methods to real-world scenarios and achieve advantages over existing approaches. Nevertheless, we hope our work can provide inspiration for future empirical studies. Additionally, we will provide numerical experiments in our final version to validate our theoretical claims.

References.

[1] El Houcine Bergou, Eduard Gorbunov, and Peter Richtárik. Stochastic three points method for unconstrained smooth minimization, 2020.

[2] Aadirupa Saha, Tomer Koren, and Yishay Mansour. Dueling convex optimization, 2021.

[3] Aadirupa Saha, Tomer Koren, and Yishay Mansour. Dueling convex optimization with general preferences, 2022.

[4] Mustafa O. Karabag, Cyrus Neary, and Ufuk Topcu. Smooth convex optimization using sub-zeroth-order oracles, 2021.

[5] Zeyuan Allen-Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles, 2018.

[6] Yi Xu, Rong Jin, and Tianbao Yang. First-order stochastic algorithms for escaping from saddle points in almost linear time, 2018.

[7] Chenyi Zhang and Tongyang Li. Escape saddle points by a simple gradient-descent based algorithm, 2021.

[8] Yuanhao Wang, Qinghua Liu, and Chi Jin. Is RLHF more difficult than standard RL? a theoretical perspective, 2023.

[9] Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem, 2012.

[10] Robert Michael Lewis, Virginia Torczon, and Michael W. Trosset. Direct search methods: then and now, 2000.

[11] Robert Hooke, and Terry A. Jeeves. Direct Search Solution of Numerical and Statistical Problems, 1961.

[12] Shuming Ma, Hongyu Wang, Lingxiao Ma, Lei Wang, Wenhui Wang, Shaohan Huang, Li Dong, Ruiping Wang, Jilong Xue, Furu Wei. The Era of 1-bit LLMs: All Large Language Models are in 1.58 Bits, 2024.

Thank you to the reviewers for their thoughtful consideration of our paper. We appreciate your positive recognition of our contributions and helpful suggestions for improvement. Here we address some common questions that arose in multiple reviews. (More specific questions of individual reviewers are provided in each individual response.)

Novelty and technical contribution. Regarding the novelty and technical contribution of our work, we agree with reviewers that our techniques and their analysis share a fair amount of similarities with previous works on Stochastic Three Point method (STP) [1] and dueling convex optimization [2, 3]. However, our approach is fundamentally deterministic, more succinct, and therefore easier to analyze and extend. Notably, our results in Theorem 2 and Theorem 4 match the query complexities achieved in [1, 2, 3] using deterministic algorithms. Furthermore, we establish Theorem 3, which addresses the high-precision regime and achieves an $n^2$ speedup compared to the previous state-of-the-art result [4].

Moreover, while we agree with the reviewers that the techniques underlying the aforementioned results are not excessively complex, we would like to draw your attention to Theorem 5 in Section 4.2, which addresses escaping saddle points using comparison queries -- this constitutes the main technical contribution of our work. Specifically, we provide the first provable guarantee for finding an $\epsilon$-SOSP of a nonconvex function using comparison-based methods. The corresponding algorithms (Algorithm 5 and Algorithm 6) and their analysis are fundamentally different from existing approaches.

Previously, there was no clear intuition about whether finding an $\epsilon$-SOSP using only comparison queries was even feasible. On the other hand, among existing results using comparison-based queries, [1] can only find a first-order stationary point (FOSP) of a nonconvex smooth function, and [2, 3] only applies to convex functions. On the other hand, existing first-order methods [5, 6, 7] rely on a critical subroutine that approximates the Hessian-vector product by computing the difference of gradients at nearby points. This approach inherently depends on access to both the gradient's direction and its norm, making it incompatible with comparison-based methods.

To address this issue, we develop a novel subroutine Comparison-NCD (Algorithm 6) that approximates the direction of the Hessian-vector product. Although Comparison-NCD has a clear geometric intuition, its analysis is surprisingly difficult, given that the procedure of approximating a Hessian-vector product using gradient queries is already a delicate procedure that is vulnerable to errors, and estimating gradient directions using comparison queries is an intrinsically numerical instable task when the gradient has a small norm. Hence, we design and combine two specialized subroutines, each tailored to handle a distinct hard case. The error analysis for both subroutines is technically involved with contributions on its own.

Presentation and Comparison with previous works. We appreciate the reviewers' suggestion for a more thorough discussion on the advantages of our approach compared to prior works. To address this, we will expand the literature review on page 2 in the final version to provide a clearer context for our contributions, and integrate some of the arguments from the above ''novelty and technical contribution'' bullet point. Additionally, we will include a table summarizing the complexities of our algorithms alongside those of prior works.

This paper proposes new optimization methods without querying any gradient or even function value, but just querying comparisons---which one of the two queried points has a larger function value. This paper provides a comprehensive set of solutions for the newly proposed questions on convex, nonconvex (finding stationary point) and even escaping the saddle points. The dimension dependency of the proposed methods are also sharp matching the best existing zero-th order methods. While this is an overall solid work, there are concerns on the technical novelty of this paper---while addressing a new problem, the techniques are rather similar to a line of prior works including Stochastic Three Point method (STP) and dueling convex optimization. There is also concerns regarding the practical justification of the newly proposed problem, while there is connection to RLHF, the connection is weak/loose and the authors were not able to convince the practical importance of the proposed problems. We recommend rejection at the current form of the paper, and suggest authors to address the aforementioned issues as well as revise title to more accurately reflect the content, and then try a future venue.

Reject