Unsupervised Learning with Provable Guarantees
Abstract
Statement of Work:Many algorithms currently used in machine learning lack provable guarantees on one or more of the following metrics: solution quality, sample complexity, running time. Thus technically speaking, these algorithms are heuristics. The underlying goal in this project is to provide algorithms with such performance guarantees. This can involve designing fundamentally new algorithms, or proving such guarantees for existing algorithms. The difficulty is that most naturalproblems in machine learning are NP-hard. Thus provable algorithms must leverage special structure of inputs to evade worst-case complexity. The work will span unsupervised learning, deep learning, nonnegative matrix factorization, and natural language processing.Objective:The project will attack several important open questions in unsupervised learning. (a) Design new generative model approaches to deep learning, especially using the theory that real-life deep nets (at least the fully connected ones) are random-like. (b) Design error-resilient versions of recent theoretical (yet practical) algorithms for Nonnegative Matrix Factorization and topic modeling. (c) Improve current word embedding methods to account for polysemy, the phenomenon whereby a word has multiple meanings. In other words, what inner structure of word embeddings corresponds to polysemy? (d) Improve recent provable algorithms to dictionary learning/sparse coding, so that theywork for more general matrices.Approach:An important part of the approach is to develop new theory that is based upon empirical data. The empirics are used to identify mathematical assumptions satisfied by the data, and then these mathematical assumptions are used to design new algorithms. These mathematical assumptions are typically in the form of a generative model, as well as more "deterministic" properties of the model parameters such as condition number, incoherence, separability, etc. The proposed methods involve an eclectic mix of algebra (especially linear algebraic methods), convex and nonconvex optimization, and bayesian reasoning.Overall Merit and ONR Mission/Relevance:This project has the potential to yield radically new approaches to designing machine learning algorithms, and also yield new insights into when machine learning algorithms work correctly and efficiently. Nonconvex optimization, of the type used in Bayesian approaches as well as deep learning approaches, is currently believed to be very hard to approach with any theory. The project will also yield new mathematical insights into the structure of data in a variety of applications. All of these will be directly of interest to ONR s ongoing research and development programs.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 08, 2016
- Source ID
- N000141612329
Entities
People
- Sanjeev Arora
Organizations
- Office of Naval Research
- Trustees of Princeton University
- United States Navy