Georgia Institute of Technology College of Sciences

Kernel principal component analysis (KPCA) is a popular non-linear dimensionality reduction technique, which generalizes classical linear PCA by finding functions in a reproducing kernel Hilbert space (RKHS) such that the function evaluation at a random variable $X$ has a maximum variance. Despite its popularity, kernel PCA suffers from poor scalability in big data scenarios as it involves solving a $n \times  n$ eigensystem leading to the computational complexity of $O(n^3)$ with $n$ being the number of samples. To address this issue, in this work, we consider a random feature approximation to kernel PCA which requires solving an $m \times m$ eigenvalue problem and therefore has a computational complexity of $O(m^3+nm^2)$, implying that the approximate method is computationally efficient if $m$ < $n$ with $m$ being the number of random features. The goal of this work is to investigate the trade-off between computational and statistical behaviors of approximate KPCA, i.e., whether the computational gain is achieved at the cost of statistical efficiency. We show that the approximate KPCA is both computationally and statistically efficient compared to KPCA in terms of the error associated with reconstructing a kernel function based on its projection onto the corresponding eigenspaces.

Link to Cisco Webex meeting: https://gatech.webex.com/gatech/j.php?MTID=mdd4512d3d11623149a0bd46d9fc086c8

The talk considers the Popularity Adjusted Block model (PABM) introduced by Sengupta and Chen (2018). We argue that the main appeal of the PABM is the flexibility of the spectral properties of the graph which makes the PABM an attractive choice for modeling networks that appear in, for example, biological sciences. In addition, to the best of our knowledge, the PABM is the only stochastic block model that allows to treat the network sparsity as the structural sparsity that describes community patterns, rather than being an attribute of the network as a whole.

Link to Zoom meeting: https://ucf.zoom.us/j/92646603521?pwd=TnRGSVo1WXo2bjE4Y3JEVGRPSmNWQT09

The pure spherical p-spin model is a Gaussian random polynomial H of degree p on an N-dimensional sphere, with N large. The sphere is viewed as the state space of a physical system with many degrees of freedom, and the random function H is interpreted as a smooth assignment of energy to each state, i.e. as an energy landscape. 

In 2012, Auffinger, Ben Arous and Cerny used the Kac-Rice formula to count the average number of critical points of H having a given index, and with energy below a given value. This number is exponentially large in N for p > 2, and the rate of growth itself is a function of the index chosen and of the energy cutoff. This function, called the complexity, reveals interesting topological information about the landscape H: it was shown that below an energy threshold marking the bottom of the landscape, all critical points are local minima or saddles with an index not diverging with N. It was shown that these finite-index saddles have an interesting nested structure, despite their number being exponentially dominated by minima up to the energy threshold. The total complexity (considering critical points of any index) was shown to be positive at energies close to the lowest. Thus, at least from the perspective of the average number of critical points, these random landscapes are very non-convex. The high-dimensional and rugged aspects of these landscapes make them relevant to the folding of large molecules and the performance of neural nets. 

Subag made a remarkable contribution in 2017, when he used a second-moment approach to show that the total number of critical points concentrates around its mean. In light of the above, when considering critical points near the bottom of the landscape, we can view Subag's result as a statement about the concentration of the number of local minima. His result demonstrated that the typical behavior of the minima reflects their average behavior. We complete the picture for the bottom of the landscape by showing that the number of critical points of any finite index concentrates around its mean. This information is important to studying associated dynamics, for instance navigation between local minima. Joint work with Antonio Auffinger and Yi Gu at Northwestern.