Sep, 2013

用于非光滑和随机优化的随机块镜像下降方法

PDF
TL;DR本篇论文介绍了一种新的随机算法 ——Stochastic Block Mirror Descent（SBMD）方法，用于解决大规模非光滑和随机优化问题，其通过加入块状坐标分解和增量式块状平均方案到经典（随机）镜像下降法中，以显著降低后者算法的每次迭代成本。我们建立了 SBMD 方法的收敛速率及其相关的大偏差结果，用于解决一般的非光滑和随机优化问题。此外，我们还介绍了此方法的不同变体，并建立了它们用于解决强凸，平滑，复合和某些非凸优化问题的收敛速率。据我们所知，所有这些 SBMD 方法的发展都是随机优化文献中的新成果。此外，我们的一些结果对于块状坐标下降方法中的确定性优化也是新的。
发现论文，激发创造
  • 随机镜像下降方法在非光滑非凸优化中的收敛速率

    该论文研究了随机镜像下降法在非凸优化中的非渐近稳态收敛性，特别关注了一类非凸非光滑的随机优化问题，其中目标函数可以分解为一个相对弱凸函数（可能是非 Lipschitz）和简单的非光滑凸规则化函数。论文证明，SMD 算法在收敛速率为 $O（1/√t）$ 的同时，无需使用小批量就能保证收敛到一个稳定点。

    Jun, 2018

  • 用广义的布雷格曼散度驯服非凸随机镜像下降

    该论文重新审视了当今非凸优化设置中随机镜像下降（Stochastic Mirror Descent，SMD）的收敛性。通过支持一般距离生成函数（distance generating function，DGF）的新的非凸 SMD 收敛分析，该论文克服了先前结果对于具有光滑连续的梯度的可微性 DGF 的限制，并仅依赖于标准假设。此外，该论文通过 Bregman 前向 - 后向包络建立了收敛性，该包络是比常用的梯度映射的平方范数更强的度量。进一步，该论文将结果扩展到在次高斯噪声下的高概率收敛和在广义 Bregman Proximal Polyak-Lojasiewicz 条件下的全局收敛。此外，通过利用非光滑 DGFs，我们展示了改进的 SMD 理论在各种非凸机器学习任务中的优势。值得注意的是，在非凸差分隐私（differentially private，DP）学习的背景下，我们的理论提供了一个（几乎）维度无关的效用界算法。对于训练线性神经网络的问题，我们开发了可证明收敛的随机算法。

    Feb, 2024

  • 块策略镜像下降

    本文提出了一种新的策略梯度方法，即基于块的策略镜像下降（BPMD）方法，用于解决一类带有（强）凸正则化器的强化学习（RL）问题，通过部分更新规则执行已采样状态上的策略更新，从而实现了每次迭代计算代价的降低，并且在分析多种采样方案时达到快速的线性收敛。

    Jan, 2022

  • 块随机梯度迭代用于凸和非凸优化

    本文介绍了一种将 Stochastic Gradient 和 Block Coordinate Descent 结合的方法，名为 Block Stochastic Gradient，它可以解决包含多个变量块的目标函数的优化问题，无论是凸优化问题还是非凸优化问题，并在多个模型上进行了测试。

    Aug, 2014

  • 超参数非线性模型的随机镜像下降：收敛性，隐式正则化和泛化

    本研究主要探讨过参数模型中采用 stochastic mirror descent 方法，在足够小的步长下，通过初始化接近全局最小值，其可以收敛和迭代到一种接近 Bregman 散度且具有更好泛化性能的解决方案，并探究该方法中不同的隐式正则化方式对结果表现的影响。

    Jun, 2019

  • 强凸优化的最优分布式随机镜像下降

    本文研究在多智能体网络中，基于 Bregman 散度作为距离测度函数，提出了两种高效的非欧几里德随机次梯度下降算法，用于求解非平滑和强凸函数的最小值，并在模拟实验中验证其收敛速度。

    Oct, 2016

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

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

    May, 2016

  • 关于正交约束无光滑组合优化问题的块坐标下降方法

    提出了一种新的基于块坐标下降（OBCD）的非光滑复合优化方法，该方法能够在正交约束下解决一般的非光滑复合问题，是具备收敛保证的可行方法。

    Apr, 2023

  • 非光滑非凸优化问题的并行逐次凸近似

    本论文提出了一种基于多核并行处理技术和凸逼近的近似并行块协调下降（BCD）方法，并研究了该方法的收敛性，结果表明在 Lasso 问题的特定情况下，循环块选择规则优于随机规则。

    Jun, 2014

  • 自适应镜像下降双层优化

    我们提出了一类基于镜像下降的高效自适应双层优化方法，用于求解非凸双层优化问题，其中上层问题可能是非凸的且具有非光滑正则化，而下层问题也是非凸的但满足 Polyak-Lojasiewicz 条件。我们提出了一种基于镜像下降的高效自适应投影梯度方法来解决确定性双层问题，并证明其在寻找非凸双层问题的 ε- 稳定解时具有已知最好的梯度复杂度 O (ε^(-1))。为了解决随机双层问题，我们提出了一种基于镜像下降和方差约减技术的高效自适应随机投影梯度方法，并证明其在寻找 ε- 稳定解时具有已知最好的梯度复杂度 O (ε^(-3/2))。由于 Polyak-Lojasiewicz 条件放宽了强凸性，我们的算法可以用于非凸强凸双层优化问题。从理论上讲，我们在一些温和条件下提供了有用的收敛性分析框架，并证明了我们的方法具有较快的收敛速度 O (1/T)，其中 T 表示迭代次数。

    Nov, 2023