May, 2019

最小化平滑与非平滑函数之和的随机解耦方法

PDF
TL;DR本文提出了一种利用逐步学习非平滑函数 $g$ 的接近算子的降低三个凸函数之和的方法，可以有效地分离平滑部分和非平滑部分，同时证明了该方法的多个迭代复杂性结果，可以广泛应用于估计 $f$ 的梯度的策略，包括通过标准和方差减少的随机估计以及结合 SGD 或 SAGA 梯度估计用于经验风险最小化，还涵盖了多个现有算法，并得到在特定情况下的新算法。
发现论文，激发创造
  • 带逐步方差缩减的近端随机梯度下降法

    提出了一种多级方案来逐渐减少随机梯度方差的新的近端随机梯度方法，用于解决平滑组件函数的平均和简单近端映射的一般凸函数总和的极小化问题。

    Mar, 2014

  • 基于随机模型的弱凸函数最小化

    本文提出一族算法通过简单的随机模型样本和优化方法，成功的减少了目标函数。我们展示出，合理的近似质量和模型的正则性下，此类算法将自然的稳定度衡量推向 0，该衰减速度为 O (k^(-1/4))，基于此原理，我们为随机的近端子梯度法，近端次梯度法以及规则化的高斯牛顿法等提供了第一个复杂性保证。

    Mar, 2018

  • 随机条件梯度方法：从凸优化到子模最大化

    该论文提出了基于随机条件梯度方法的优化问题求解算法，用于解决大规模维度下的凸函数、连续子模型等多种问题，并证明了当问题维度高时，该方法较与传统的随机梯度下降法更加稳定，同时计算时间复杂度也得到了有效降低。

    Apr, 2018

  • 用于复合非强凸优化的快速随机镜像下降算法

    本篇论文提出了一种加速随机镜像下降法来解决平均函数和非强凸函数的问题，绕过了常见的小二次正则化降低性能的方法，可以更好地解决非强凸情况。

    May, 2016

  • 复合和弱凸优化问题的随机方法

    本研究考虑了具有随机性的凸函数和光滑函数组成并且是弱凸的函数式的最小化问题，开发了一系列随机算法，并通过实验验证了实际效果。

    Mar, 2017

  • 一种简单的近端随机梯度下降法用于非光滑非凸优化

    本文提出一种基于变量规约的 Proximal 随机梯度下降算法 (ProxSVRG+), 该算法在非凸性和非光滑性优化问题上具有更好的性能，并在收敛性分析方面比之前的算法更加全面和普适性更强。

    Feb, 2018

  • 非凸高维随机优化的非光滑和非欧几里德近端项随机一阶方法

    非凸优化中采用维度无关的随机一阶方法 (DISFOM) 来解决样本复杂度问题，使用小批量估计梯度以达到 ε- 稳定点的样本复杂度为 O ((log d) / ε^4)，进一步利用方差缩减可将该界限提高至 O ((log d)^(2/3) / ε^(10/3))，并提供了两种非平滑距离函数的选择，数值实验验证了所提框架的维度无关性。

    Jun, 2024

  • 优化复合目标的紧密复杂度界

    通过使用分量函数的梯度和 prox oracles 提供了最小化 m 个凸函数平均值的复杂性的严格上下界；我们表明决定性和随机优化之间存在显着差距。对于光滑函数，我们表明在确定性和随机设置中，加速梯度下降 (AGD) 和 SVRG 的加速变体分别是最优的，并且梯度 Orcale 足以获得最佳速率。对于非光滑函数，通过接入 prox oracles 可降低复杂度，因此，我们提出基于平滑的最优方法，以改进仅使用梯度访问的方法。

    May, 2016

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

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

    Feb, 2018

  • 凸函数和光滑映射最小化组合的效率

    本文研究了凸函数与唇希茨凸函数的平滑映射组合的最小化算法的全局效率，以及使用近端线性方法结合平滑、快速梯度方案等技术处理只能通过一阶方法解决的子问题时，如何获得高效率。

    Apr, 2016