Michael Mahoney: Approximate computation and implicit regularization in large-scale data analysis
Channel: Stanford Computer Science Theory
Date: 2011-10-16

Michael Mahoney: Approximate computation and implicit regularization in large-scale data analysis

Traditional methods of worst-case analysis often fail to provide even qualitative guidance as to what algorithms are appropriate in many large-scale data analysis applications. This fact is usually blamed on the exclusive focus on running time for arbitrary input. A deeper reason is that most problems arising in modern data applications are intractable and since the relaxations and embeddings underlying most worst-case approximation algorithms are not "close enough" to the data to provide such qualitative guidance. Recent empirical work on very large social and information networks, however, has clearly demonstrated that by exploiting the geometric properties associated with these relaxations and embeddings, one can extract insight and perform inference from large, sparse, and noisy graphs in a scalable and robust way. Performing such inference is typically the domain of a statistical technique known as regularization, which usually involves modifying the original objective with a geometric constraint and then exactly optimizing the modified objective. Thus, these results demonstrate a manner in which approximate computation can implicitly lead to statistical regularization, i.e., in which the solutions from worst-case approximation algorithms are not only faster but also "better" for downstream applications than the solutions to their intractable counterparts. This will be illustrated in the context of using spectral versus flow-based approximation algorithms for the graph partitioning problem; and it will be explained in terms of how the geometric embeddings underlying spectral methods versus flow methods provide a form of capacity control to "smooth" or "regularize" the input graph in very different ways. The implications of these results for worst-case approximation algorithms more generally will be discussed.