More Like this

1. Statistical Optimality and Computational Efficiency of Nystrom Kernel PCA

   Sterge, N; Sriperumbudur, Bharath K. (January 2022, Journal of machine learning research)

   Kernel methods provide an elegant framework for developing nonlinear learning algorithms from simple linear methods. Though these methods have superior empirical performance in several real data applications, their usefulness is inhibited by the significant computational burden incurred in large sample situations. Various approximation schemes have been proposed in the literature to alleviate these computational issues, and the approximate kernel machines are shown to retain the empirical performance. However, the theoretical properties of these approximate kernel machines are less well understood. In this work, we theoretically study the trade-off between computational complexity and statistical accuracy in Nystrom approximate kernel principal component analysis (KPCA), wherein we show that the Nystrom approximate KPCA matches the statistical performance of (non-approximate) KPCA while remaining computationally beneficial. Additionally, we show that Nystrom approximate KPCA outperforms the statistical behavior of another popular approximation scheme, the random feature approximation, when applied to KPCA. 

   more » « less
2. A Review of and Some Results for Ollivier–Ricci Network Curvature

   https://doi.org/10.3390/math8091416  

   Azarhooshang, Nazanin; Sengupta, Prithviraj; DasGupta, Bhaskar (September 2020, Mathematics)

   null (Ed.)

   Characterizing topological properties and anomalous behaviors of higher-dimensional topological spaces via notions of curvatures is by now quite common in mainstream physics and mathematics, and it is therefore natural to try to extend these notions from the non-network domains in a suitable way to the network science domain. In this article we discuss one such extension, namely Ollivier’s discretization of Ricci curvature. We first motivate, define and illustrate the Ollivier–Ricci Curvature. In the next section we provide some “not-previously-published” bounds on the exact and approximate computation of the curvature measure. In the penultimate section we review a method based on the linear sketching technique for efficient approximate computation of the Ollivier–Ricci network curvature. Finally in the last section we provide concluding remarks with pointers for further reading. 

   more » « less
3. Faster Kernel Matrix Algebra via Density Estimation

   Backurs, A; Indyk, P; Musco, C; Wagner, T (January 2021, International Conference on Machine Learning)

   null (Ed.)

   We study fast algorithms for computing basic properties of an n x n positive semidefinite kernel matrix K corresponding to n points x_1,...,x_n in R^d. In particular, we consider the estimating the sum of kernel matrix entries, along with its top eigenvalue and eigenvector. These are some of the most basic problems defined over kernel matrices. We show that the sum of matrix entries can be estimated up to a multiplicative factor of 1+epsilon in time sublinear in n and linear in d for many popular kernel functions, including the Gaussian, exponential, and rational quadratic kernels. For these kernels, we also show that the top eigenvalue (and a witnessing approximate eigenvector) can be approximated to a multiplicative factor of 1+epsilon in time sub-quadratic in n and linear in d. Our algorithms represent significant advances in the best known runtimes for these problems. They leverage the positive definiteness of the kernel matrix, along with a recent line of work on efficient kernel density estimation. 

   more » « less
4. A min-plus fundamental solution semigroup for a class of approximate infinite dimensional optimal control problems

   McEneaney, William M; Dower, Peter M. (July 2020, Proceedings of the American Control Conference)

   By exploiting min-plus linearity, semiconcavity, and semigroup properties of dynamic programming, a fundamental solution semigroup for a class of approximate finite horizon linear infinite dimensional optimal control problems is constructed. Elements of this fundamental solution semigroup are parameterized by the time horizon, and can be used to approximate the solution of the corresponding finite horizon optimal control problem for any terminal cost. They can also be composed to compute approximations on longer horizons. The value function approximation provided takes the form of a min-plus convolution of a kernel with the terminal cost. A general construction for this kernel is provided, along with a spectral representation for a restricted class of sub-problems. 

   more » « less
5. Faster Kernel Matrix Algebra via Density Estimation.

   Backurs, Arturs; Indyk, Piotr; Musco, Cameron; Wagner, Tal. (January 2021, International Conference on Machine Learning (ICML))

   We study fast algorithms for computing fundamental properties of a positive semidefinite kernel matrix K∈ R^{n*n} corresponding to n points x1,…,xn∈R^d. In particular, we consider estimating the sum of kernel matrix entries, along with its top eigenvalue and eigenvector. We show that the sum of matrix entries can be estimated to 1+ϵ relative error in time sublinear in n and linear in d for many popular kernels, including the Gaussian, exponential, and rational quadratic kernels. For these kernels, we also show that the top eigenvalue (and an approximate eigenvector) can be approximated to 1+ϵ relative error in time subquadratic in n and linear in d. Our algorithms represent significant advances in the best known runtimes for these problems. They leverage the positive definiteness of the kernel matrix, along with a recent line of work on efficient kernel density estimation. 

   more » « less