An Algorithmic Theory of Robustness
Abstract
Most problems in machine learning are NP-hard or worse, but practitioners seem to solve them anyways. Recently there has been considerable progress in revisiting some of the classic problems in machine learning, and explainingwhy heuristics perform well and/or designing inherently new algorithmic approaches. This agenda has had a number of successes for problems like nonnegative matrix factorization, topic modeling, sparse coding, learningmixture models and tensor decomposition. But there is an important part of the picture that is not nearly as well understood: robustness | i.e. how sensitive are our algorithms to the modeling assumptions we make? In this proposal,we detail a multifaceted approach to robustness. We study strong notionsof robustness that allow an adversary to arbitrarily corrupt a large fraction of the samples. Building o - recent success, we revisit compressed sensing and linear inverse prblems and give a path toward designing algorithms that are provably fault tolerant. Taking inspiration from semi-random models from theoretical computer science, we study weaker models of robustness that allow us to probe whether or not classic algorithms are over-tuning to a particulardistributional assumption. We study matrix completion, community detection as well as nonparametric extensions of popular mixture models.Finally we propose that robustness can serve as a guiding principle in identifying what types of assumptions are reasonable in theoretical machine learning. We suggest that the notion of perturbation stability, which has been highly successful in the context of approximation algorithms, can be adapted to inference problems and serve as a starting point for analyzing complex iterative algorithms like Gibbs sampling that have thus far eluded theoretical analysis.Overall, this program has the potential to lead to inherently more robust algorithms for fundamental problems in machine learning, and is likely to have apractical impact on applications of interest to the O?ce of Naval Research, including designing intelligent systems, video analysis and sensor localization.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 26, 2018
- Source ID
- N000141812525
Entities
People
- Ankur Moitra
Organizations
- Massachusetts Institute of Technology
- Office of Naval Research
- United States Navy