Implementing regularization implicitly via approximate eigenvector computation

Understand

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.