Mathematical Analysis of High-Dimensional Algorithms and Models

Abstract

High-dimensional data and problems are ubiquitous in recent research in scientific computing, machine learning, and their applications. Although many algorithms and models have been proposed and examined as efficient in practice, mathematical theories supporting their reliability and efficiency are relatively scarce. In this dissertation, we establish theoretical foundations for three classes of high-dimensional algorithms and models, using analytical tools.(i) Randomized coordinate gradient descent algorithm displays some advantages in high dimensions due to the sparse update and larger stepsize. We prove under generic assumptions that the algorithm almost surely escapes from strict saddle points and converges to local minima for nonconvex optimization. The proof is based on viewing the randomized algorithm as a nonlinear random dynamical system and a quantitative finite block analysis of its linearization around saddle points. (ii) Neural-network-based methods have achieved great success in solving high-dimensional partial differential equations (PDEs) numerically. We establish an approximation theory of two-layer neural networks without the curse of dimensionality for general second-order elliptic PDEs and a regularity theory for static Schr\"odinger equations, via functional analysis in Barron spaces. (iii) Graph neural networks (GNNs) are considered as suitable for representing mixed-integer linear programs (MILPs) due to the permutation-invariant/equivariant property. We show that MILPs suffer from a fundamental limitation of GNNs in separation power, while linear programs (LPs) without integer constraints enjoy the universal approximation. Several remedies are proposed for MILPs.