Location
MC 6460
Candidate
Guilherme Henrique Macieira De Araujo| Applied Mathematics, University of Waterloo
Title
Parallel-in-iteration optimization using multigrid reduction-in-time
Abstract
Standard gradient-based iteration algorithms for optimization, such as gradient descent and its various proximal-based extensions to nonsmooth problems, are known to converge slowly for ill-conditioned problems, sometimes requiring many tens of thousands of iterations in practice. Since these iterations are computed sequentially, they may present a computational bottleneck in large-scale parallel simulations. In this thesis, we present a ``parallel-in-iteration'' framework that allows one to parallelize across these iterations using multiple processors with the objective of reducing the wall-clock time needed to solve the underlying optimization problem.
Our methodology is based on re-purposing parallel time integration algorithms for time-dependent differential equations, namely the parallel-in-time method of multigrid reduction-in-time (MGRIT), motivated by the fact that optimization algorithms often have interpretations as discretizations of time-dependent differential equations. We numerically demonstrate the efficacy of this parallel-in-iteration approach on two different model problems, including a standard convex quadratic problem and the nonsmooth elastic obstacle problem in one and two spatial dimensions. For our model problems, we observe fast MGRIT convergence analogous to its prototypical performance on partial differential equations of diffusion type. We present theoretical results to connect the convergence of MGRIT to the convergence of the underlying optimization algorithm; theoretically predicted parallel speedup results are also provided.
Having established our parallel-in-iteration framework, we develop an extension of this framework based on approximately computing multiple trajectories rather than computing the trajectory yielded by the underlying optimization method with high accuracy. These multiple trajectories are constructed by reinitializing our MGRIT parallel-in-iteration solve with updated initial guesses, assumed to be closer to the solution than then previous ones. Therefore, we may intepret our multiple-trajectory method as a restarting optimization algorithm. By truncating the time domain of the original MGRIT solve to a small fixed fraction of the original number of time points, our multiple-trajectories approach allows for a multiplicative increase in the estimated parallel speedup while simultaneously proportionally reducing the number of processors required for full parallelization. We present theoretical results on the asymptotic equivalence between standard and restarting MGRIT schemes, which support the strategy of restarting from an earlier time point employed by the truncated variant of the restarting scheme.