Oct, 2012

可变度量随机追踪

PDF
TL;DR研究在无梯度情况下，对光滑凸性目标函数进行无约束随机优化。Random Pursuit（RP）算法具有固定（F-RP）和可变度量（V-RP）两种。用于在随机选定的一维子空间上进行重复优化，并通过零阶信息计算近似解。对于严格凸函数，对 V-RP 的全局收敛性进行了分析，量化其所使用的度量需要多好才能实现最佳可能速率的情况，并通过数值实验进行了比较。
randomized optimizationconvex functionsrandom pursuit algorithmvariable metriczeroth-order information
发现论文，激发创造
  • 具有尖锐保证的凸规划的随机草图

    该研究探讨了使用随机投影进行维度降低的方法来近似解决具有凸性质的问题，在计算有限的情况下具有广泛的应用，同时还可以提高隐私保护和降低存储和计算成本。研究证明了该方法的近似比率可以用约束集合的几何特性来界定，对于一类广泛的随机投影，其投影结果数据矩阵的维度相对于原始问题的维度相对较小，该理论还与降噪、压缩感知等领域有关系。

    Apr, 2014

  • 泛用效用的强化学习变分策略梯度方法

    该研究通过引入泛函的方法，提出了一种新的策略梯度算法，用于解决马尔可夫决策问题中带通用上限效用函数的策略优化问题，并证明了其全局收敛性和收敛速度。

    Jul, 2020

  • 从随机搜索到度量空间中的强盗学习

    本文给出了随机搜索的理论解释，通过介绍散射维度的概念来描述底层函数的景观，证明了输出随机搜索以 $\widetilde {\mathcal {O}}(\left ( \frac {1}{T} \right)^{\frac {1}{d_s}})$ 的概率收敛于最佳值，提出了 BLiN-MOS 算法，用于在具有 Borel 度量的倍增度量空间中进行 Lipschitz bandits，表明在度量测量空间中，与度量空间的经典理论相比，Lipschitz bandits 的上界可以得到改善。

    May, 2023

  • 随机变量度量近端梯度算法及方差约减在非凸复合优化中的应用

    提出了 Perturbed Proximal Preconditioned SPIDER (3P-SPIDER) 算法，适用于解决有限和非凸复合优化问题，是随机变量度量前向 - 后向算法，提出了迷你批处理策略以减少方差并控制收敛，并通过逻辑回归模型的推理应用进行了数值比较。

    Jan, 2023

  • Riemannian SVRG：黎曼流形上快速随机优化

    本文介绍了一种新的用于优化 Riemann 流形中的逐点可微分函数的方差减少方法 RSVRG，并分析了其在几何凸和非凸函数上的性能，提供了非渐近性的复杂度分析，从而为 Riemannian 优化提供了一个新的视角。

    May, 2016

  • 变量度量过松弛混合近端额外梯度法的算法框架

    提出了一种新的 VMOR-HPE 算法框架，具有全局收敛保证，可用于最大单调操作符插入问题，该框架加速了一类原始和原始对偶算子分裂算法，其中包括 KKT 广义等式约束的多块组合凸优化问题的新算法 PADMM-EBB，有效地处理了非负对偶图正则化低秩表示问题。

    May, 2018

  • 一种最优随机增量梯度方法

    本文提出了一种新的随机算法来解决大规模的有限和凸优化问题，该算法可以在迭代次数上实现确定性最优，同时需要计算较少的梯度次数，这一算法通过引入新的博弈论解释方法提高了可行性。

    Jul, 2015

  • 变量度量随机逼近理论

    本文提出了可变度量随机逼近理论，其中包括了在线 BFGS 算法及其有限内存 LBFGS 变体，并讨论了这一结果对学习专家建议的影响。

    Aug, 2009

  • 平滑目标高效的私有 ERM

    本文综述了不同凸且光滑目标函数的梯度下降算法与输出扰动方法，不仅能达到近乎最优的效用，而且也提高了以前的隐私优化算法的运行时间。同时，对于非凸光滑目标函数，还提出了 RRPSGD 算法，并附上了隐私保障的收敛性证明。实验表明，我们的算法在效益和运行时间方面始终优于现有方法。

    Mar, 2017

  • 非凸随机复合优化问题的小批量随机逼近方法

    该论文提出了一种随机梯度下降算法（RSPG）来解决一类包含非可微凸函数和非光滑性质的随机优化问题，并且证明了该算法的收敛速度。

    Aug, 2013