On Quasi-Convex Smooth Optimization Problems by a Comparison Oracle

A. V. Gasnikov ; M. S. Alkousa ; A. V. Lobanov ; Y. V. Dorn ; F. S. Stonyakin ; I. A. Kuruzov ; S. R. Singh

Russian journal of nonlinear dynamics, Tome 20 (2024) no. 5, pp. 813-825

Résumé

Frequently, when dealing with many machine learning models, optimization problems appear to be challenging due to a limited understanding of the constructions and characterizations of the objective functions in these problems. Therefore, major complications arise when dealing with first-order algorithms, in which gradient computations are challenging or even impossible in various scenarios. For this reason, we resort to derivative-free methods (zeroth-order methods). This paper is devoted to an approach to minimizing quasi-convex functions using a recently proposed (in [56]) comparison oracle only. This oracle compares function values at two points and tells which is larger, thus by the proposed approach, the comparisons are all we need to solve the optimization problem under consideration. The proposed algorithm to solve the considered problem is based on the technique of comparison-based gradient direction estimation and the comparison-based approximation normalized gradient descent. The normalized gradient descent algorithm is an adaptation of gradient descent, which updates according to the direction of the gradients, rather than the gradients themselves. We proved the convergence rate of the proposed algorithm when the objective function is smooth and strictly quasi-convex in $\mathbb{R}^n$, this algorithm needs $\mathcal{O}\left( \frac{n D^2}{\varepsilon^2} \log\left(\frac{n D}\varepsilon\right)\right)$ comparison queries to find an $\varepsilon$-approximate of the optimal solution, where $D$ is an upper bound of the distance between all generated iteration points and an optimal solution.

Détail

Keywords: quasi-convex function, gradient-free algorithm, smooth function, normalized gradient descent
Mots-clés : comparison oracle