可接受的对称约束下的全局最优性
该研究提出了一种称为测地凸性的新概念,将向量空间凸性推广到非线性度量空间,并在Hadamard流形上开发了迭代复杂度分析,为一些一阶算法提供了全局复杂度上限。研究结果还揭示了流形几何,尤其是分段曲率如何影响收敛速度。这是第一篇为一般g-凸优化的一阶算法提供全局复杂度分析的工作。
Feb, 2016
提出了一种用于研究具有对称结构的非凸优化景观的通用理论,基于不变群对目标函数的Hessian矩阵进行分析并应用于低秩矩阵分解问题,其中研究了所有驻点和全局最小值,将整个参数空间划分为三个区域,为常见迭代算法提供了强有力的全局收敛保证。
Dec, 2016
本文探讨了研究数据驱动最优化问题时遇到的非凸问题,这些问题可以通过对称性的角度来理解它们表现出的几何结构及其与目标函数构建的相关性,并讨论了未来研究的方向。
Jul, 2020
本论文提出了一种通用的理论框架和算法,通过利用简单的变形来解决多边际最优输运问题(MOT)在多项式时间内,尤其是解决了当前最流行的 Sinkhorn 算法对于 MOT 求解在多项式时间内所需要的额外结构,提供了新的精确且稀疏的算法,同时对于三种 MOT 成本结构提供了可充分利用标准算法技术的多项式时间算法。
Aug, 2020
本文研究了带有原子的集合中的有限轨系统的线性方程组,提出了一个适用于任何域(甚至可交换环)的可解决性决策过程,并将给定的有限轨系统约减为若干个有限系统;当输入系统的原子维度固定时,约减数量通常是指数级的,但是多项式数量。为了得到此过程,我们进一步推进了轨道有限集生成的向量空间理论,并展示了每个向量空间都拥有一个轨道有限基础,这个基础性质是我们开发中的关键工具,但也应该具有更广泛的兴趣。
Jan, 2022
本研究考虑了将一个实对称张量分解为一些一阶秩张量之和的非凸优化问题,并利用该张量的对称结构导出Puiseux序列表示的关键点族。最终得出了关键值和Hessian谱的精确分析估计,并发现一组纷繁复杂的鞍点和局部最小值的解析特性与对称结构的差异。另外,本文证明了随着目标函数值的增加,每个关键点的指数(即负Hessian特征值的数量)也随之增加,并使用Newton多面体论证明了固定对称性的所有关键点的完全列举。本研究的研究结果指出了各种地方性障碍的解析特征,并揭示了某些非全局极小值家族的出现与消失。
Jun, 2023
本文重点研究了自然界中对称模式的识别和分析,在物理学中导致了引力定律的制定和化学结构研究的进展。我们着眼于利用某些协同多智能体强化学习问题中固有的欧几里得对称性,该问题在许多应用中普遍存在。我们首先形式化地表征了一类具有对称最优值和策略存在性的马尔科夫博弈的子类。在这些属性的基础上,我们设计了具有对称约束的神经网络架构,作为多智能体演员-评论家方法的归纳偏见。这种归纳偏见在各种协同多智能体强化学习基准测试中表现出优越的性能,以及在具有重复对称模式的未见场景中进行的零样本学习和迁移学习等令人印象深刻的泛化能力。代码可在此 https URL 获取。
Aug, 2023
我们提出了利用输入数据的周期对称结构的新型快速最优传输算法,通过利用周期对称性和各种优化技术,将传输优化问题简化为具有更少变量的小型优化问题,从而更快地获得原始最优输运问题的最优解和目标函数值。在这篇论文中,我们主要关注两个关键的传输优化问题:线性规划传输优化问题(LOT)和强凸正则化传输优化问题,其中包括著名的熵正则化传输优化问题(EROT)。实验证明了我们的算法在具有严格/近似周期对称结构的合成/真实世界数据上的有效性。通过理论和实验结果,本文首次成功将对称性概念引入传输优化研究领域。
Nov, 2023
均场变分推断(VI)是找到相对熵意义下到给定的高维概率测度$\rho$最接近的分布(分解测度)的问题。本文证明了在对数凹密度$\rho$情况下,均场变分推断CAVI的收敛性。若附加条件$\log \rho$具有Lipschitz梯度,则收敛速度为线性,若$\rho$也是强对数凹的,则收敛速度为指数级。我们的分析始于观察到当$\rho$为对数凹时,均场VI在优化输运的意义下是凸的,从而使我们能够借鉴来自欧几里得空间上坐标下降算法的优化文献中的技术。
Apr, 2024