用广义的布雷格曼散度驯服非凸随机镜像下降
内容提要
本文综述随机镜像下降法在非凸优化中的研究进展，涵盖非凸非光滑问题的稳态收敛、过参数模型的隐式正则化、多智能体非欧算法、OMD收敛性、SBMD大规模优化、去中心化在线优化、变分推断、SGD统一分析、SBPG神经网络训练及同伦策略镜像下降等方向。
延伸解读
非凸非光滑优化的收敛保证
文章指出，对于目标函数可分解为相对弱凸函数（可能非Lipschitz）和简单非光滑凸正则项的非凸非光滑随机优化问题，随机镜像下降法（SMD）在无需小批量的情况下，能以O(1/√t)的速率收敛到稳定点。这一结果扩展了SMD在非凸设定下的理论保证，为处理非光滑问题提供了实用收敛依据。
过参数模型的隐式正则化
在过参数模型中，采用随机镜像下降法，当步长足够小且初始化接近全局最小值时，算法可收敛到接近Bregman散度且泛化性能更好的解。研究还探讨了不同隐式正则化方式对结果的影响，这有助于理解过参数神经网络中优化算法如何隐式控制模型复杂度。
多智能体与去中心化优化
文章涵盖多智能体网络中基于Bregman散度的非欧几里德随机次梯度下降算法，用于非平滑强凸函数最小化，以及去中心化在线非凸优化中结合梯度跟踪的GT-DSGD。后者在Polyak-Lojasiewics条件下具有线性收敛性，并达到最优全局亚线性收敛速度，为分布式优化提供了高效方案。
算法变体与统一分析
文章综述了多种随机镜像下降变体，如随机块镜像下降（SBMD）通过块坐标分解降低每次迭代成本，随机Bregman近端梯度法（SBPG）处理非Lipschitz梯度，以及同伦策略镜像下降（HPMD）用于强化学习。此外，还提出了SGD变体的统一收敛分析框架，涵盖分布式和联邦优化方法。
Q&A
随机镜像下降法在非凸非光滑优化中的收敛速率是多少？
论文证明，SMD算法在收敛速率为O(1/√t)的同时，无需使用小批量就能保证收敛到一个稳定点。
过参数模型中随机镜像下降如何实现隐式正则化？
在足够小的步长下，通过初始化接近全局最小值，随机镜像下降可以收敛和迭代到一种接近Bregman散度且具有更好泛化性能的解决方案，并探究了不同的隐式正则化方式对结果表现的影响。
多智能体网络中基于Bregman散度的非欧几里德随机次梯度下降算法是什么？
本文提出了两种高效的非欧几里德随机次梯度下降算法，用于求解非平滑和强凸函数的最小值，并在模拟实验中验证其收敛速度。
优化镜像下降法（OMD）在非单调问题中的收敛性如何？
分析表明，OMD可以解决具有一致性属性的非单调问题并推广了先前的结果，为建立凸凹博弈以外的收敛性提供了具体进展。在一系列GAN模型上的数值实验结果验证了分析的可行性。
Stochastic Block Mirror Descent (SBMD)方法如何降低大规模优化的迭代成本？
SBMD通过加入块状坐标分解和增量式块状平均方案到经典（随机）镜像下降法中，以显著降低后者算法的每次迭代成本。我们建立了SBMD方法的收敛速率及其相关的大偏差结果，并介绍了不同变体及其用于解决强凸、平滑、复合和某些非凸优化问题的收敛速率。
去中心化在线随机非凸优化中GT-DSGD的收敛性如何？
通过将梯度跟踪技术集成到去中心化随机梯度下降中，对于满足Polyak-Lojasiewics条件的全局非凸函数，GT-DSGD具有线性收敛性，并且在几乎每条路径上具有最优的全局亚线性收敛速度。
基于随机梯度方法的变分推断新方法有什么特点？
该方法不仅利用变分参数空间的几何性质，而且即使对于非共轭模型也可以产生简单的闭合式更新，并具有收敛速率分析，即使用于非凸目标的随机镜像下降。在多种问题上，实验证明新算法可以导致最先进的结果。
SGD变体在平滑非凸情况下的统一收敛分析是什么？
本文提出了一种通用的假设模型来精确建模随机梯度的二阶矩，并给出了所有满足统一假设的方法的单一收敛分析。此外，提出了两种新的通用算法框架来处理分布式/联邦非凸优化问题，并说明这些方法均满足统一假设，因此统一收敛分析也包括了许多利用压缩通讯的分布式方法。最后，提供了一种在PL条件下获得更快线性收敛速度的统一分析。
随机Bregman近端梯度法（SBPG）在神经网络训练中的收敛性如何？
SBPG及其动量版本（MSBPG）在非凸优化问题中有很好的收敛性，提出了MSBPG解决大规模优化中随机梯度下降法的一些不足。
同伦策略镜像下降（HPMD）方法在MDPs中有什么计算性质？
HPMD在全局和局部上均具有收敛性，并且能够在一定条件下证明和表征极限策略。同时，使用该方法可同时获得非渐近最优策略和极大信息熵的极限策略，在不同Bregman散度之间进行扩展，以及是一些常见Bregman散度的有限时间精确收敛。
