A Variational Formulation of Accelerated Optimization on Riemannian Manifolds
A Variational Formulation of Accelerated Optimization on Riemannian Manifolds
复制标题
DOI：
10.1137/21m1395648
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Valentin Duruisseaux;M. Leok
中科院分区：
文献类型：
--
作者：
Valentin Duruisseaux;M. Leok
它是最近由Su等人展示的。(2016)Nester ov的极小化光滑凸函数$f$的加速梯度法可以看作是二阶常微分方程的时间离散化，且$f(x(T))$沿该常微分方程的任意轨迹$x(T)$以数学式{O}(1/t^2)$的速度收敛到最优值。WiBisono等人引入了一个变分公式。(2016)，它允许在赋范向量空间中，对任意的$p>；0$，以$\数学{O}(1/t^p)$的速度加速收敛。这一框架在Duruisseaux等人中得到了利用。(2021)为辛加速优化设计高效的显式算法。在Alimisis等人中。(2020)，提出了一个二阶常微分方程组作为黎曼加速算法的连续时间限制，并证明了目标函数$f(x(T))$沿着该常微分方程组的解以数学上的{O}(1/t^2)$的速度收敛到最优值.本文证明了在黎曼流形上，通过考虑黎曼流形上的一族含时Bregman拉格朗日系统和哈密顿系统，f(x(T))$收敛到其最佳值的速度也可以加速到任意的收敛速度。这推广了WiBisono等人的结果。(2016)推广到黎曼流形，并为黎曼流形上的加速优化提供了变分框架。Duruisseaux等人利用Bregman、Lagrangian和Hamilton函数族的时间不变性，构造了一种非常有效的优化算法。(2021)，我们在黎曼环境下建立了类似的时不变性质。人们期望一个时间自适应的、保辛的和黎曼流形的几何数值积分器将在流形上产生一类有前途的优化算法。
It was shown recently by Su et al. (2016) that Nesterov's accelerated gradient method for minimizing a smooth convex function $f$ can be thought of as the time discretization of a second-order ODE, and that $f(x(t))$ converges to its optimal value at a rate of $\mathcal{O}(1/t^2)$ along any trajectory $x(t)$ of this ODE. A variational formulation was introduced in Wibisono et al. (2016) which allowed for accelerated convergence at a rate of $\mathcal{O}(1/t^p)$, for arbitrary $p>0$, in normed vector spaces. This framework was exploited in Duruisseaux et al. (2021) to design efficient explicit algorithms for symplectic accelerated optimization. In Alimisis et al. (2020), a second-order ODE was proposed as the continuous-time limit of a Riemannian accelerated algorithm, and it was shown that the objective function $f(x(t))$ converges to its optimal value at a rate of $\mathcal{O}(1/t^2)$ along solutions of this ODE. In this paper, we show that on Riemannian manifolds, the convergence rate of $f(x(t))$ to its optimal value can also be accelerated to an arbitrary convergence rate $\mathcal{O}(1/t^p)$, by considering a family of time-dependent Bregman Lagrangian and Hamiltonian systems on Riemannian manifolds. This generalizes the results of Wibisono et al. (2016) to Riemannian manifolds and also provides a variational framework for accelerated optimization on Riemannian manifolds. An approach based on the time-invariance property of the family of Bregman Lagrangians and Hamiltonians was used to construct very efficient optimization algorithms in Duruisseaux et al. (2021), and we establish a similar time-invariance property in the Riemannian setting. One expects that a geometric numerical integrator that is time-adaptive, symplectic, and Riemannian manifold preserving will yield a class of promising optimization algorithms on manifolds.