Jesus Maria Sanz-Serna

We study the connections between ordinary differential equations and optimization algorithms in a non-Euclidean setting. We propose a novel accelerated algorithm for minimizing convex functions over a convex constrained set. This algorithm is a natural generalization of Nesterov’s accelerated gradient descent method to the non-Euclidean setting and can be interpreted as an additive Runge-Kutta algorithm. The algorithm can also be derived as a numerical discretization of the ODE suggested by Krichene et al. in 2015. We use Lyapunov functions to establish convergence rates for the ODE and show that the discretizations considered achieve acceleration beyond the setting studied by Krichene and his coworkers. Finally, we discuss how the proposed algorithm connects to various equations and algorithms in the literature.

We revisit the general framework introduced by Fazylab et al. [ SIAM J. Optim., 28 (2018), pp. 2654–2689] to construct Lyapunov functions for optimization algorithms in discrete and continuous time. For smooth, strongly convex objective functions, we relax the requirements necessary for such a construction. As a result, we are able to prove for Polyak’s ordinary differential equations and for a two-parameter family of Nesterov algorithms rates of convergence that improve on those available in the literature. We analyze the interpretation of Nesterov algorithms as discretizations of the Polyak equation. We show that the algorithms are instances of additive Runge–Kutta integrators and discuss the reasons why most discretizations of the differential equation do not result in optimization algorithms with acceleration. We also introduce a modification of Polyak’s equation and study its convergence properties. Finally, we extend the general framework to the stochastic scenario and consider an application to random algorithms with acceleration for overparameterized models; again we are able to prove convergence rates that improve on those in the literature.

Autoresonance is a phenomenon of physical interest that may take place when a nonlinear oscillator is forced at a frequency that varies slowly. The stroboscopic averaging method (SAM), which provides an efficient numerical technique for the integration of highly oscillatory systems, cannot be used directly to study autoresonance due to the slow changes of the forcing frequency. We study how to modify SAM to cater for such slow variations. Numerical experiments show the computational advantages of using SAM.

This paper presents a new accelerated proximal Markov chain Monte Carlo methodology to perform Bayesian inference in imaging inverse problems with an underlying convex geometry. The proposed strategy takes the form of a stochastic relaxed proximal-point iteration that admits two complementary interpretations. For models that are smooth or regularized by Moreau–Yosida smoothing, the algorithm is equivalent to an implicit midpoint discretization of an overdamped Langevin diffusion targeting the posterior distribution of interest. This discretization is asymptotically unbiased for Gaussian targets and shown to converge in an accelerated manner for any target that is [Formula: see text]-strongly log-concave (i.e., requiring in the order of [Formula: see text] iterations to converge, similar to accelerated optimization schemes), comparing favorably to Pereyra, Vargas Mieles, and Zygalakis [ SIAM J. Imaging Sci., 13 (2020), pp. 905–935], which is only provably accelerated for Gaussian targets and has bias. For models that are not smooth, the algorithm is equivalent to a Leimkuhler–Matthews discretization of a Langevin diffusion targeting a Moreau–Yosida approximation of the posterior distribution of interest and hence achieves a significantly lower bias than conventional unadjusted Langevin strategies based on the Euler–Maruyama discretization. For targets that are [Formula: see text]-strongly log-concave, the provided nonasymptotic convergence analysis also identifies the optimal time step, which maximizes the convergence speed. The proposed methodology is demonstrated through a range of experiments related to image deconvolution with Gaussian and Poisson noise with assumption-driven and data-driven convex priors. Source codes for the numerical experiments of this paper are available from https://github.com/MI2G/accelerated-langevin-imla .

For systems of the form [Formula: see text], [Formula: see text], common in many applications, we analyze splitting integrators based on the (linear/nonlinear) split systems [Formula: see text], [Formula: see text] and [Formula: see text], [Formula: see text]. We show that the well-known Strang splitting is optimally stable in the sense that, when applied to a relevant model problem, it has a larger stability region than alternative integrators. This generalizes a well-known property of the common Störmer/Verlet/leapfrog algorithm, which of course arises from Strang splitting based on the (kinetic/potential) split systems [Formula: see text], [Formula: see text] and [Formula: see text], [Formula: see text].

We construct integrators to be used in Hamiltonian (or Hybrid) Monte Carlo sampling. The new integrators are easily implementable and, for a given computational budget, may deliver five times as many accepted proposals as standard leapfrog/Verlet without impairing in any way the quality of the samples. They are based on a suitable modification of the processing technique first introduced by J.C. Butcher. The idea of modified processing may also be useful for other purposes, like the construction of high-order splitting integrators with positive coefficients.

The leapfrog integrator is routinely used within the Hamiltonian Monte Carlo method and its variants. We give strong numerical evidence that alternative, easy to implement algorithms yield fewer rejections with a given computational effort. When the dimensionality of the target distribution is high, the number of accepted proposals may be multiplied by a factor of three or more. This increase in the number of accepted proposals is not achieved by impairing any positive features of the sampling. We also establish new non-asymptotic and asymptotic results on the monotonic relationship between the expected acceptance rate and the expected energy error. These results further validate the derivation of one of the integrators we consider and are of independent interest.