Implementing regularization implicitly via approximate eigenvector computation

Details Implementing regularization implicitly via approximate eigenvector computation Implementing regularization implicitly via approximate eigenvector computation

2010-10-04

arxiv.org/abs/1010.0703v2

Computer Science

Data Structures and Algorithms

11 pages; a few clarifications

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Implementing regularization implicitly via approximate eigenvector computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Implementing regularization implicitly via approximate eigenvector computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implementing regularization implicitly via approximate eigenvector computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-85689