Error Analysis on Graph Laplacian Regularized Estimator

Abstract

We provide a theoretical analysis of the representation learning problem aimed at learning the latent variables (design matrix) $\Theta$ of observations $Y$ with the knowledge of the coefficient matrix $X$. The design matrix is learned under the assumption that the latent variables $\Theta$ are smooth with respect to a (known) topological structure $\mathcal{G}$. To learn such latent variables, we study a graph Laplacian regularized estimator, which is the penalized least squares estimator with penalty term proportional to a Laplacian quadratic form. This type of estimators has recently received considerable attention due to its capability in incorporating underlying topological graph structure of variables into the learning process. While the estimation problem can be solved efficiently by state-of-the-art optimization techniques, its statistical consistency properties have been largely overlooked. In this work, we develop a non-asymptotic bound of estimation error under the classical statistical setting, where sample size is larger than the ambient dimension of the latent variables. This bound illustrates theoretically the impact of the alignment between the data and the graph structure as well as the graph spectrum on the estimation accuracy. It also provides theoretical evidence of the advantage, in terms of convergence rate, of the graph Laplacian regularized estimator over classical ones (that ignore the graph structure) in case of a smoothness prior. Finally, we provide empirical results of the estimation error to corroborate the theoretical analysis.

References in corpus (8)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Learning with Structured Sparsity
• Graph Laplacian Regularization for Image Denoising: Analysis in the Continuous Domain
• Consistency of trace norm minimization
• Matrix Completion on Graphs
• Graph-based regularization for regression problems with alignment and highly-correlated designs
• Learning Latent Features with Pairwise Penalties in Low-Rank Matrix Completion
• Alternating Linear Bandits for Online Matrix-Factorization Recommendation