May, 2016

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

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

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

    May, 2019

  • 有限和优化问题的下限复杂度：结果与构造

    本文研究了有限和优化问题的下限复杂度界限，并基于分组的新方法构造了硬实例，从而建立了有限和最大最小优化问题的下限复杂度界限。

    Mar, 2021

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

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

    May, 2016

  • 几乎必然受限凸优化

    我们提出了一种随机梯度框架，用于解决具有（可能）无限数量的线性包含约束条件的随机复合凸优化问题，而这些约束条件需要几乎确定。我们使用平滑和同伦技术处理约束条件，无需矩阵投影，并且通过数值实验表明，我们的算法实现了最先进的实用性能。

    Jan, 2019

  • 关于平滑和强凸优化问题的下限和上限

    我们开发了一个新的框架来研究光滑和强凸优化算法，特别是针对二次函数，我们能够将优化算法作为线性运算的递归应用程序来检查，这揭示了一种强大的联系，即一类优化算法与多项式的分析理论之间的联系，从而导出了新的下界和上界，同时我们还以多项式相关的最优解的形式表达它，从而对 Nesterov 著名的加速梯度下降方法进行了新的系统推导。

    Mar, 2015

  • 复合凸极小化的近端梯度法的最恶情况收敛速率

    本文研究了求解由平滑强凸函数和可得到其 Proximal 算子的非光滑凸函数组成的函数和的最优收敛速度，并利用半定规划等工具，建立了 Proximal 梯度算法的准确最坏情况收敛速度，同时提出可将强凸性等条件放宽以保证相应的收敛速度，得到了三种性能度量的同一步长最优的证明。

    May, 2017

  • 针对复合凸光滑优化的随机梯度方法统一分析

    本文为最小化平滑和凸损失加上凸正则化的随机梯度算法提供了一致的收敛性分析定理，并探讨了特定算法的最优小批量大小。

    Jun, 2020

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

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

    Mar, 2018

  • 带逐步方差缩减的近端随机梯度下降法

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

    Mar, 2014

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

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

    Apr, 2016