Abstract:
Modern optimization methods often encounter limited access to the values of the objective function, leading to the development of works dedicated to comparative oracles. This review provides an overview of contemporary algorithms for smooth, multivariate optimization that utilize only information about the order of the function values, rather than their numerical magnitudes. Both non-accelerated and accelerated methods are considered, including the latest advancements in optimization with comparative oracles. Special attention is paid to the diversity of approaches for designing algorithms that achieve convergence rates comparable to first-order methods (coordinate algorithms), as well as the first accelerated method within this oracle framework. Additionally, stochastic generalizations of the comparative oracle and their theoretical guarantees are discussed.
Keywords:comparative oracle, black box, smooth optimization problem, non-accelerated/accelerated algorithms.
