May, 2016

高平滑度的零阶在线优化

PDF
TL;DR本文探讨了利用仅包含部分和嘈杂信息的凸函数最小化问题，特别着重于高度平滑问题的凸优化问题，包括逻辑回归等。研究表明，相对于基于梯度的算法，高阶平滑性可用于改善估计速率，并精确地依赖于平滑度的程度，同时提出了此类算法可行性的上限。最后，作者还在在线优化设置中取得了类似的结果。
convex optimizationzero-order informationsmoothnessestimation ratesonline optimization
发现论文，激发创造
  • 强凸性和利普希茨 Hessian 下的随机零阶优化：极小 - 最大样本复杂度

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

    Jun, 2024

  • 非凸随机零阶优化：处理约束、高维度和鞍点

    本文提出了针对非凸和凸优化的零阶随机逼近算法，并关注解决约束优化、高维设置和避免鞍点等问题。我们探索了结构稀疏假设的优点，并提出了一种使用零阶信息的被截断随机梯度算法和一种避免鞍点的算法，并讨论了它们的收敛率。

    Sep, 2018

  • 高维随机零阶优化

    本文介绍了使用随机零阶查询优化高维凸函数的问题，提出了两种算法，并表明两种算法只依赖于问题的环境维度的对数收敛率。实证研究证明了理论发现，并表明我们设计的算法在高维场景中优于经典的零阶优化方法。

    Oct, 2017

  • 噪声凸型零阶优化的简化改进算法

    通过噪声、凸性和零阶优化等概念，研究在有界凸集合中的一类函数的优化问题，我们提出了一个基于质心方法的改进算法，证明其相对于最小值的差距的阶数小于 d^2/√n，且比现有文献中已知的 d^{2.5}/√n 的速度更快，并且更简化。

    Jun, 2024

  • 分布式非光滑非凸随机优化的一阶和零阶在线优化视角

    我们研究了非光滑非凸目标在分散随机优化中找到 ($\delta,\epsilon$)- 稳定点的有限时间分析。我们提出了一种称为 ME-DOL 的新算法，并在不同环境中建立了样本复杂性。我们证明了该算法在光滑非凸目标中恢复了最优收敛速度的在线至非凸技术，并扩展了分析到非光滑设置，建立在随机平滑和 Goldstein - 次微分集的属性上。我们在一阶设置中建立了 $O (\delta^{-1}\epsilon^{-3})$ 的样本复杂度，这是我们所知道的第一次对于分散非光滑非凸随机优化的有限时间保证（无弱凸性），与其最优集中对应。我们进一步证明了在不使用方差减少的零阶预言机设置时相同的速率。

    Jun, 2024

  • 无梯度的零阶方法高效避免鞍点

    本文研究了非凸优化中的无导数算法，利用有限差分器进行梯度逼近，最终提出了一种使用嘈杂的零阶方法来避免鞍点的算法，并在收敛速度上达到了与精确梯度接近的性能。

    Oct, 2019

  • 超越凸性和 Lipschitz 梯度连续性的一阶方法及其在二次逆问题中的应用

    利用可适应性光滑函数的概念和 Bregman 基础的近端梯度方法，在解决具有复杂目标函数的非凸、非光滑最小化问题时，实现全局收敛。

    Jun, 2017

  • 基于 Hessian 感知的零阶优化黑盒对抗攻击

    本文提出了一个基于 Hessian 矩阵的零阶优化算法 ZO-HessAware，用于黑盒对抗攻击，该算法的实验证明在结构化 Hessian 逼近的情况下，具有更好的零阶收敛率和查询复杂度。

    Dec, 2018

  • 信号处理和机器学习中零阶优化入门

    本文综述了零阶优化的方法，重点介绍了其优化思想、原则以及近年来的收敛分析进展。此外还介绍了零阶优化的一些应用，例如评估深度学习模型的鲁棒性、生成黑盒模型的解释以及在线传感器管理等。

    Jun, 2020

  • 一种具有近似评估和复杂度保证的非凸最小化随机算法

    非凸函数的最小化，利用近似正负曲率方向步长，相对不精确度度量梯度和 Hessian 矩阵，松弛一阶和二阶精度的耦合，通过马丁格尔分析和浓度不等式得到收敛性分析，并将算法应用于经验风险最小化问题。

    Oct, 2023