A Block-Coordinate Approach of Multi-level Optimization with an Application to Physics-Informed Neural Networks

Many numerical optimization problems of interest today are large dimensional, and techniques to solve them efficiently are thus an active field of research. A very powerful class of algorithms for the solution of large problems is that of multi-level methods. Originally, the concept of a method exploiting multiple levels, i.e., multiple resolutions of an underlying problem, was introduced for the solution of large scale systems arising from the discretization of partial differential equations (PDEs). In this context these methods are known as multigrid (MG) methods for the linear case or full approximation schemes (FAS) for the nonlinear one [3, 38]. These schemes were later extended to nonlinear optimization problems, in which context they are known as multi-level optimization techniques [27, 11, 12, 13, 5]. The central idea of all these approaches is to use the structure of the problem in order to significantly reduce the computational cost compared to standard approaches applied to the full unstructured problem. In this paper we introduce a new interpretation of multi-level methods as block coordinate descent (BCD) methods: iterations at coarse levels (i.e., low resolution) can be interpreted as the (possibly approximate) solution of a subproblem involving a set of variables smaller than that required to describe the fine level (high resolution). We propose a framework that allows us to encompass multi-level methods for several classes of problems as well as a unifying complexity analysis based on a generic block coordinate descent, which is simple yet comprehensive.