Multi-Trajectory Parallel-in-Iteration Optimization
math.NA, cs.NA, math.OC
Submitted: 2026-11-02
Updated: 2026-11-02
Comments: 26 pages, 8 figures, 6 tables
License: http://creativecommons.org/licenses/by/4.0/
The gist: Previously, we developed a ``parallel-in-iteration'' optimization framework that uses multigrid reduction-in-time (MGRIT) to parallelize slowly converging optimization methods…
Abstract
Previously, we developed a ``parallel-in-iteration'' optimization framework that uses multigrid reduction-in-time (MGRIT) to parallelize slowly converging optimization methods, such as gradient descent. Unlike time-dependent evolution problems, optimization requires only a final point with a sufficiently small gradient, rather than an accurate approximation of the entire trajectory of iterates. This motivates a different use of MGRIT: instead of repeatedly improving the approximation of a single long trajectory, we introduce restarted MGRIT (R-MGRIT), which performs one MGRIT iteration on a trajectory, takes the approximate final point as a new initial guess, and repeats the process on a new trajectory. Each restart thus defines a new all-at-once system, allowing progress toward the solution without accurately approximating the preceding trajectory. Moreover, we find that these trajectories can be shortened without increasing the number of restarts needed for convergence. We provide theoretical results comparing MGRIT and R-MGRIT for linear problems and demonstrate the convergence behavior of the shortened trajectories numerically for both linear and nonlinear problems. Shortening the trajectories increases the estimated parallel speedup while reducing the number of processors required.
Related papers
- Do physics-informed neural networks (PINNs) need to be deep? Shallow PINNs using the Levenberg-Marquardt algorithm
- A Neural-preconditioned Poisson Solver for Mixed Dirichlet and Neumann Boundary Conditions
- Advanced Linear Algebra with Applications - Part I (Numerical linear algebra for PDEs, machine learning, and data assimilation)
- Operator learning meets inverse problems: A probabilistic perspective
- Second-order consistency for learning chaotic dynamics via randomized Jacobian matching
- Windowed thinning and query complexity for the bouncy particle and Zigzag samplers