Hamilton-Jacobi PDEs and optimal control problems are widely used in many practical problems in control engineering, physics, financial mathematics, and machine learning. For instance, controlling an autonomous system is important in everyday modern life, and it requires a scalable, robust, efficient, and data-driven algorithm for solving optimal control problems. Traditional grid-based numerical methods cannot solve these high-dimensional problems, because they are not scalable and may suffer from the curse of dimensionality. To overcome the curse of dimensionality, we developed several neural network methods for solving high-dimensional Hamilton-Jacobi PDEs and optimal control problems. This talk will contain two parts. In the first part, I will talk about SympOCNet method for solving multi-agent path planning problems, which solves a 512-dimensional path planning problem with training time of less than 1.5 hours. In the second part, I will show several neural network architectures with solid theoretical guarantees for solving certain classes of high-dimensional Hamilton-Jacobi PDEs. By leveraging dedicated efficient hardware designed for neural networks, these methods have the potential for real-time applications in the future. These are joint works with Jerome Darbon, George Em Karniadakis, Peter M. Dower, Gabriel P. Langlois, and Zhen Zhang.

Community detection in the stochastic block model is one of the central problems of graph clustering. In this setup, spectral algorithms have been one of the most widely used frameworks for the design of clustering algorithms. However, despite the long history of study, there are still unsolved challenges. One of the main open problems is the design and analysis of ``simple'' spectral algorithms, especially when the number of communities is large. 

In this talk, I will discuss two algorithms. The first one is based on the power-iteration method. Our algorithm performs optimally (up to logarithmic factors) compared to the best known bounds in the dense graph regime by Van Vu (Combinatorics Probability and Computing, 2018). 

Then based on a connection between the powered adjacency matrix and eigenvectors, we provide a ``vanilla'' spectral algorithm for large number of communities in the balanced case. Our spectral algorithm is as simple as PCA (principal component analysis).

This talk is based on joint works with Chandra Sekhar Mukherjee. (https://arxiv.org/abs/2211.03939)

Despite the non-convex optimization landscape, over-parametrized shallow networks are able to achieve global convergence under gradient descent. The picture can be radically different for narrow networks, which tend to get stuck in badly-generalizing local minima. Here we investigate the cross-over between these two regimes in the high-dimensional setting, and in particular, investigate the connection between the so-called mean field/hydrodynamic regime and the seminal approach of Saad & Solla. Focusing on the case of Gaussian data, we study the interplay between the learning rate, the time scale, and the number of hidden units in the high-dimensional dynamics of stochastic gradient descent (SGD). Our work builds on a deterministic description of SGD in high-dimensions from statistical physics, which we extend and for which we provide rigorous convergence rates. https://arxiv.org/abs/2202.00293

In this talk, I will discuss the spectral properties of a two-layer neural network after one gradient step and their applications in random ridge regression. We consider the first gradient step in a two-layer randomly initialized neural network with the empirical MSE loss. In the proportional asymptotic limit, where all the dimensions go to infinity at the same rate, and an idealized student-teacher setting, we will show that the first gradient update contains a rank-1 ''spike'', which results in an alignment between the first-layer weights and the linear component of the teacher model. By verifying a Gaussian equivalent property, we can compute the prediction risk of ridge regression on the conjugate kernel after one gradient step. We will present two scalings of the first step learning rate. For a small learning rate, we compute the asymptotic risks for the ridge regression estimator on top of trained features which does not outperform the best linear model. Whereas for a sufficiently large learning rate, we prove that the ridge estimator on the trained features can go beyond this ``linear'' regime. Our analysis demonstrates that even one gradient step can lead to an advantage over the initial features. Our theoretical results are mainly based on random matrix theory and operator-valued free probability theory, which will be summarized in this talk. This is recent joint work with Jimmy Ba, Murat A. Erdogdu, Taiji Suzuki, Denny Wu, and Greg Yang.