Walid Krichene

A Lyapunov Approach to Accelerated First-Order Optimization in Continuous and Discrete Time

This page contains the videos corresponding to some of the figures of my M.A. thesis.

Figure 4.2: Solution trajectories of the accelerated mirror descent ODE on a finite time interval \(t \in [0, T]\), for simplex-constrained quadratic minimization, with different values of the parameter \(r\). Larger values of \(r\) result in more energy dissipation, and suppress oscillations, but because the time-horizon is finite, too much energy dissipation means that the trajectory does not make enough progress within \([0, T]\), as can be seen in plot (c). This example shows that the ‘‘best damping’’ is not necessarily obtained for smaller values of \(r\), as one could think from the bound of Theorem 2.

Figure 4.3: Vector field \(X \mapsto \nabla^2\psi^*(Z) \nabla f(X)\) for different values of \(Z\) (taken along a solution trajectory for an example problem with solution on the relative boundary of the simplex). As \(\nabla \psi^*(Z)\) approaches the relative boundary, the vector field changes in such a way that the component that is orthogonal to the boundary vanishes.

(a) Strongly convex quadratic
(b) Weakly convex quadratic

Figure 6.1: Accelerated mirror descent on the simplex, and restarting heuristics.

Figure 6.2: Effect of the parameter \(r\).

Figure 6.3: Effect of restarting when the solution is on the boundary.