Published on Mon Oct 04 2010

Implementing regularization implicitly via approximate eigenvector computation

Michael W. Mahoney, Lorenzo Orecchia

Regularization is a powerful technique for extracting useful information from noisy data. It is usually implemented by adding some sort of norm constraint to an objective function and then exactly optimizing the modified objective function. This procedure often leads to optimization problems that are computationally more expensive than the original problem.

0
0
0
Abstract

Regularization is a powerful technique for extracting useful information from noisy data. Typically, it is implemented by adding some sort of norm constraint to an objective function and then exactly optimizing the modified objective function. This procedure often leads to optimization problems that are computationally more expensive than the original problem, a fact that is clearly problematic if one is interested in large-scale applications. On the other hand, a large body of empirical work has demonstrated that heuristics, and in some cases approximation algorithms, developed to speed up computations sometimes have the side-effect of performing regularization implicitly. Thus, we consider the question: What is the regularized optimization objective that an approximation algorithm is exactly optimizing? We address this question in the context of computing approximations to the smallest nontrivial eigenvector of a graph Laplacian; and we consider three random-walk-based procedures: one based on the heat kernel of the graph, one based on computing the the PageRank vector associated with the graph, and one based on a truncated lazy random walk. In each case, we provide a precise characterization of the manner in which the approximation method can be viewed as implicitly computing the exact solution to a regularized problem. Interestingly, the regularization is not on the usual vector form of the optimization problem, but instead it is on a related semidefinite program.

Sat Oct 08 2011
Machine Learning
Regularized Laplacian Estimation and Fast Eigenvector Approximation
Mahoney and Orecchia demonstrated that popular diffusion-based algorithms to compute a quick approximation to a data graph Laplacian solve certain regularized Semi-Definite Programs (SDPs) We provide a statistical interpretation of their approximation procedure.
0
0
0
Tue Dec 17 2013
Machine Learning
The Matrix Ridge Approximation: Algorithms and Applications
Matrix ridge approximation is an incomplete matrix factorization plus a ridge term. The idea behind the latent variable model leads us to an efficient EM iterative method for handling the matrix ridge approximation.
0
0
0
Fri Oct 14 2016
Machine Learning
Spectral Inference Methods on Sparse Graphs: Theory and Applications
The idea is to create a network of nodes that can be connected to each other. The idea is based on the idea that all nodes in a network are connected. The goal of the network is to make it possible to connect all nodes.
0
0
0
Sat Feb 22 2020
Machine Learning
Constructing fast approximate eigenspaces with application to the fast graph Fourier transforms
The eigenspaces are factored into a fixed number of fundamental components that can be efficiently manipulated. The number of these components controls the computational complexity of projecting on them. We show results on random matrices and an application on the approximation of graph Fourier transforms.
0
0
0
Tue Feb 11 2020
Machine Learning
Asymptotic errors for convex penalized linear regression beyond Gaussian matrices
We consider the problem of learning a coefficient vector in from noisy linear observations. The proof is based on a rigorous convergence analysis of an oracle version of vector approximate message-passing (oracle-VAMP)
0
0
0
Thu Oct 29 2015
Machine Learning
The Singular Value Decomposition, Applications and Beyond
singular value decomposition (SVD) is not only a classical theory inMatrix computation and analysis, but also is a powerful tool in machine learning and modern data analysis. In this tutorial we first study the basic notion of SVD and then show the central role of SVA in
0
0
0