Optimization of convex functions under stochastic zeroth-order feedback has
been a major and challenging question in online learning. In this work, we
consider the problem of optimizing second-order smooth and strongly convex
functions where the algorithm is only accessible to noisy evaluations of the
objective function it queries. We provide the first tight characterization for
the rate of the minimax simple regret by developing matching upper and lower
bounds. We propose an algorithm that features a combination of a bootstrapping
stage and a mirror-descent stage. Our main technical innovation consists of a
sharp characterization for the spherical-sampling gradient estimator under
higher-order smoothness conditions, which allows the algorithm to optimally
balance the bias-variance tradeoff, and a new iterative method for the
bootstrapping stage, which maintains the performance for unbounded Hessian.

在在线学习中，优化随机零阶反馈下的凸函数一直是一个主要而具有挑战性的问题。本文考虑了仅能对目标函数进行噪声评估的情况下，对二阶平滑和强凸函数进行优化的问题；通过提出匹配的上下界，第一次对最小化最大简单后悔的速率进行了紧密的刻画。我们提出了一种算法，结合了启动阶段和镜像下降阶段。我们的主要技术创新包括对高阶平滑性条件下球形采样梯度估计器的尖锐刻画，从而使算法能够在偏差 - 方差权衡方面达到最优平衡，以及一种用于启动阶段的新的迭代方法，它能够保持无界 Hessian 的性能。

强凸性和利普希茨 Hessian 下的随机零阶优化：极小 - 最大样本复杂度

Stochastic Zeroth-Order Optimization under Strongly Convexity and  Lipschitz Hessian: Minimax Sample Complexity

Sign-based stochastic methods have gained attention due to their ability to
achieve robust performance despite using only the sign information for
parameter updates. However, the current convergence analysis of sign-based
methods relies on the strong assumptions of first-order gradient Lipschitz and
second-order gradient Lipschitz, which may not hold in practical tasks like
deep neural network training that involve high non-smoothness. In this paper,
we revisit sign-based methods and analyze their convergence under more
realistic assumptions of first- and second-order smoothness. We first establish
the convergence of the sign-based method under weak first-order Lipschitz.
Motivated by the weak first-order Lipschitz, we propose a relaxed second-order
condition that still allows for nonconvex acceleration in sign-based methods.
Based on our theoretical results, we gain insights into the computational
advantages of the recently developed LION algorithm. In distributed settings,
we prove that this nonconvex acceleration persists with linear speedup in the
number of nodes, when utilizing fast communication compression gossip
protocols. The novelty of our theoretical results lies in that they are derived
under much weaker assumptions, thereby expanding the provable applicability of
sign-based algorithms to a wider range of problems.

基于信号的方法是一种能够在参数更新时只使用符号信息而实现稳健性能的方法。本文重新审视了基于信号的方法，并在更现实的一阶和二阶平滑性的假设下分析了其收敛性。基于我们的理论结果，我们对最近开发的 LION 算法的计算优势有了深入的了解。在分布式环境中，我们证明了当利用快速通信压缩传播协议时，这种非凸加速度随着节点数量的线性加速性仍然存在。我们的理论结果的新颖之处在于它们是在更弱的假设下得出的，从而扩展了基于信号算法可适用于更广泛问题范围的可证明应用性。