Randomized Sketching for Approximate Gradients : Applications to PDE Constrained Optimization
2019-07-24, 17:05–17:15, Room 349

Randomized sketching algorithms are a powerful tool for on-the-fly compression of matrices. In this talk we show how sketching can be used for approximate gradient and hessian-times-vector computations that are storage optimal.
This approach gives cutting-edge low memory algorithms to address the challenge of expensive storage in optimization problems with PDE constraints.
We also discuss implications for efficient adjoint computation/back-propagation.

This work is motivated by the challenge of expensive storage in optimization problems with PDE constraints e.g. optimal flow control, full waveform inversion, optical tomography etc.
These optimization problems are characterized by PDE constraints that uniquely determine the state of a physical system for a given control. The state matrix is typically much more expensive to store than the control matrix.

The optimization algorithms effects changes in the control that move a physical system towards optimal behavior. Any first or second order algorithm requires gradient computation. As a first step we have to solve the PDE and store its solution and this is a storage bottleneck.

Recently randomized algorithms have been developed for matrix approximation and Sketching is a high-performance algorithm for on-the-fly compression of matrices. We demonstrate how sketching can be used to compute approximate gradients and hessian-times-vector quantities while avoiding the storage bottleneck caused by the PDE solution.

This cutting-edge algorithmic recipe has been applied successfully for linear parabolic boundary control and optimal fluid flow. We also explore its implications for efficient adjoint computation or back-propagation.


Drew Kouri, Madeleine Udell