Хачатрян Рафик Агасиевич, доктор физико-математических наук, профессор кафедры численного анализа и математического моделирования
0025, г. Ереван, ул. Алек Манукян, 1
Rafik A. Khachatryan, Doctor of Physical and Mathematical Sciences, Professor of the Numerical Analysis and Mathematical Modeling Department
1 Alex Manukyan St., Yerevan 0025
В данной работе исследуются методы стохастического приближения на основе конечных разностей для задачи минимизации квазивыпуклых функций. Традиционные подходы к задачам выпуклой оптимизации в основном опираются на использование точных или стохастических субградиентов. Однако во многих практических ситуациях доступна только зашумленная информация о значениях функции. В таких случаях рассматриваются стохастические квазиградиентные схемы, построенные на основе рандомизированных конечно-разностных оценок. В частности, изучаются пакетные двухточечные схемы, которые дают несмещенные приближения градиента сглаженной целевой функции. Для данных схем устанавливаются оценки дисперсии, что позволяет провести анализ сходимости проективных стохастических методов спуска.
В работе рассматривается задача минимизации функций вида $f(x)=\max_{i \in I} f_i(x),$ где каждая функция $f_i(x),$ $i \in I,$ является квазивыпуклой и имеет липшицев градиент на выпуклом компактном множестве. Основным результатом работы является получение оценок скорости сходимости стохастических конечно-разностных методов в случае квазивыпуклых функций. Показано, что ожидаемая субоптимальность убывает со скоростью $O\!\left(\frac{1}{\sqrt{k}}\right).$ Полученные результаты существенно расширяют область применения стохастических конечно-разностных методов к негладким задачам квазивыпуклой оптимизации и обеспечивают строгое теоретическое обоснование алгоритма в условиях «черного ящика», когда доступны только зашумленные оценки функции.
This paper investigates stochastic approximation methods based on finite differences for the minimization of quasiconvex functions. Traditional approaches to convex optimization problems primarily rely on exact or stochastic subgradients. However, in many practical situations, only noisy information about function values is available. In such cases, stochastic quasi-gradient schemes constructed using randomized finite-difference estimators are considered. In particular, we study batch two-point schemes that provide unbiased approximations of the gradient of a smoothed objective function. Variance bounds are established for these estimators, which enable a rigorous convergence analysis of projected stochastic descent methods.
The paper considers the minimization problem of functions of the form $f(x) = \max_{i \in I} f_i(x),$ where each function $f_i(x),$ $i \in I,$ is quasiconvex and has a Lipschitz-continuous gradient on a convex compact set. The main result of the paper is the derivation of convergence rate estimates for stochastic finite-difference methods in the quasiconvex setting. It is shown that the expected suboptimality decreases at the rate $O\!\left(1/\sqrt{k}\right).$ The obtained results significantly broaden the applicability of stochastic finite-difference methods to nonsmooth quasiconvex optimization problems and provide a rigorous theoretical justification of the algorithm in black-box settings where only noisy function evaluations are available.
The authors declare that there are no conflicts of interest present.