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.

Figure 6.2: Effect of the parameter $$r$$.