We study first-order optimization algorithms for computing the barycenter of Gaussian distributions with respect to the optimal transport metric. Although the objective is geodesically non-convex, Riemannian GD empirically converges rapidly, in fact faster than off-the-shelf methods such as Euclidean GD and SDP solvers. This stands in stark contrast to the best-known theoretical results for Riemannian GD, which depend exponentially on the dimension. In this work, we prove new geodesic convexity results which provide stronger control of the iterates, yielding a dimension-free convergence rate. Our techniques also enable the analysis of two related notions of averaging, the entropically-regularized barycenter and the geometric median, providing the first convergence guarantees for Riemannian GD for these problems.


翻译:我们研究了用于计算高斯分布的重心的一阶优化算法,其中度量采用最优传输度量。虽然目标在测地意义下是非凸的,但实践表明Riemannian GD的收敛速度比Euclidean GD和SDP求解器等现成的方法更快。这与Riemannian GD的最佳已知理论结果形成了鲜明对比,后者在维数上有着指数级的依赖关系。在本文中,我们证明了新的测地凸性结果,提供了更强的控制迭代的方式,从而获得了无维收敛率。我们的技术还使得能够分析两个相关的平均值概念,即熵正则化的重心和几何中位数,为Riemannian GD首次提供了这些问题的收敛保证。

0
下载
关闭预览

相关内容

通用动力公司(General Dynamics)是一家美国的国防企业集团。2008年时通用动力是世界第五大国防工业承包商。由于近年来不断的扩充和并购其他公司,通用动力现今的组成与面貌已与冷战时期时大不相同。现今通用动力包含三大业务集团:海洋、作战系统和资讯科技集团。
干货书!基于单调算子的大规模凸优化,348页pdf
专知会员服务
48+阅读 · 2022年7月24日
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
73+阅读 · 2022年6月28日
【干货书】计算机科学家的数学,153页pdf
专知会员服务
170+阅读 · 2021年7月27日
专知会员服务
41+阅读 · 2021年4月2日
专知会员服务
50+阅读 · 2020年12月14日
【Google】梯度下降,48页ppt
专知会员服务
80+阅读 · 2020年12月5日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
深度卷积神经网络中的降采样
极市平台
12+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年6月5日
VIP会员
相关VIP内容
干货书!基于单调算子的大规模凸优化,348页pdf
专知会员服务
48+阅读 · 2022年7月24日
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
73+阅读 · 2022年6月28日
【干货书】计算机科学家的数学,153页pdf
专知会员服务
170+阅读 · 2021年7月27日
专知会员服务
41+阅读 · 2021年4月2日
专知会员服务
50+阅读 · 2020年12月14日
【Google】梯度下降,48页ppt
专知会员服务
80+阅读 · 2020年12月5日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员