针对重尾噪声下的非凸非光滑优化，提出高效零阶算法。
Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise
- 通过裁剪两点梯度估计改进在线转非凸框架。
- 达到最优维度依赖与精度依赖的零阶复杂度。
- 适合存在异常值的机器学习优化场景。
本文研究目标函数为Lipschitz连续的非凸非光滑优化问题，在随机设置下，算法仅能获取带有重尾噪声的函数值评估，该情形广泛存在于各类机器学习应用中。提出一种改进的零阶随机算法，通过裁剪两点梯度估计，完善在线转非凸转换框架。理论分析表明，该算法可找到$(δ, ε)$-Goldstein平稳点，其零阶预言机复杂度为${\mathcal O}(d^{\frac{p}{2(p-1)}}δ^{-1}ε^{-\frac{2p-1}{p-1}})$，其中$d$为问题维数，$p\in(1,2]$为有界矩的阶数。该复杂度在维数依赖上达到现有零阶随机优化最优水平，且对精度参数$δ$和$ε$的依赖与最优一阶随机算法一致。最后通过数值实验验证了方法的有效性。
原文摘要 · Abstract (English)
This paper considers the nonconvex nonsmooth problem in which the objective function is Lipschitz continuous. We focus on the stochastic setting where the algorithm can access stochastic function value evaluations with heavy-tailed noise, which is prevalent in many popular machine learning applications. We propose a stochastic zeroth-order algorithm that refines the framework of online-to-nonconvex conversion by clipping the two-point gradient estimator. The theoretical analysis shows that our algorithm can find a $(δ, ε)$-Goldstein stationary point with zeroth-order oracle complexity of ${\mathcal O}(d^{\frac{p}{2(p-1)}}δ^{-1}ε^{-\frac{2p-1}{p-1}})$, where $d$ is the problem dimension and $p\in(1,2]$ is the order of bounded moments. Note that our dependence on dimension $d$ matches the best-known results of stochastic zeroth-order optimization for finding the sub-optimal solution of a stochastic convex nonsmooth problem. In addition, our dependence on accuracy parameters $δ$ and $ε$ is consistent with that of the best-known stochastic first-order algorithms for stochastic nonconvex nonsmooth problems. Finally, we conduct numerical experiments to demonstrate the effectiveness of the proposed method.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。