Dec, 2013

零阶凸优化的最优速率：两个函数评估的效能

PDF
TL;DR该研究探讨了使用函数值而不是梯度的无导数算法在随机和非随机凸优化问题中的应用，同时关注其收敛速率，经实验表明使用随机扰动的梯度估算方法具有比传统随机梯度方法更快的收敛速率，尤其在光滑和非光滑情况下，且可以扩展到多次评估的情况。
发现论文，激发创造
  • 无梯度的零阶方法高效避免鞍点

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

    Oct, 2019

  • 零阶非光滑非凸随机优化的最优维度依赖算法

    研究非光滑、非凸的 Lipschitz 目标函数在具有噪声函数评估的条件下生成 $(\delta,\epsilon)$- 稳定点的复杂性，提出的算法具有 $O (d\delta^{-1}\epsilon^{-3})$ 的复杂度和最优收敛速率。

    Jul, 2023

  • 带两点反馈的赌博机和零阶凸优化的最优算法

    本文介绍了一种基于梯度估计器的简单算法，可以在 convex Lipschitz 函数方面实现带有两个反馈信息的 bandit convex optimization 和带有两个函数评估的 zero-order stochastic convex optimization 问题的最优解，同时在比之前的算法更加简单的前提下可以扩展到非欧几里得问题。

    Jul, 2015

  • 一种用于无导数平滑随机凸优化的加速方法

    本文研究优化问题中目标函数存在不确定的噪声干扰，提出了基于导数的无导数算法，考虑了稀疏向量情况下使用 1 范数正则化的优化模型。

    Feb, 2018

  • 高维随机零阶优化

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

    Oct, 2017

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

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

    Jun, 2024

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

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

    Oct, 2023

  • 非强凸平稳随机逼近，收敛速率 O (1/n)

    本篇论文研究了关于随机逼近问题的现有算法，提出了两种新型随机梯度算法，并在回归和逻辑分类两种经典的监督学习问题上进行了测试，得到了较好的优化效果。

    Jun, 2013

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

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

    Jun, 2024

  • 高平滑度的零阶在线优化

    本文探讨了利用仅包含部分和嘈杂信息的凸函数最小化问题，特别着重于高度平滑问题的凸优化问题，包括逻辑回归等。研究表明，相对于基于梯度的算法，高阶平滑性可用于改善估计速率，并精确地依赖于平滑度的程度，同时提出了此类算法可行性的上限。最后，作者还在在线优化设置中取得了类似的结果。

    May, 2016