Sanjeev Arora - US grants

The classical theory of NP-completeness shows that many optimization problems of practical interest are hard to solve: i.e., NP-hard problems that have no polynomial-time algorithms (assuming P is not equal to NP). A popular method for dealing with such an NP-complete problem is to try to compute approximate solutions: i.e., solutions whose cost is within some multiplicative factor of the cost of the exact solution. The focus of this project is to demonstrate that computing approximate solutions for NP-hard problems is no easier than computing exact solutions. The underlying idea which is exploited, is that of a new probabilistic definition of the NP complexity class, a definition based on probabilistically checkable proofs (PCP's). Some of the major goals of the project include: (1) To better understand the approximability of NP-hard optimization problems (including cataloging the hardness of approximation of many problems, improving existing results about the hardness of approximation, and understanding the limitation of these techniques); (2) To develop further connections between the theory of PCP's and cryptography; (3) To improve existing ways of representing data by error-correcting codes; (4) To simplify the techniques used in the proof of this new definition of NP. The Educational Component of this CAREER Grant includes: (a) Development of CORE undergraduate computer science courses (including Theory of Computation and Applied Discrete Mathematics); (b) Development of a graduate computer science course and a corresponding text dealing with PCP's and (approximate) complexity theory.

hepatitis C; epidemiology; disease /disorder proneness /risk; chronic disease /disorder; clinical research; human subject;

Approximation of NP-hard problems: Algorithms and Complexity
Sanjeev Arora
Princeton University

The broad goal of the project is a study of the approximation properties of
NP-hard problems. NP-hard problems are those that do not have any efficient
algorithms if the classes P and NP are different, as is widely-believed. They arise in a variety
of application areas in science and technology, including scheduling, VLSI
design, artificial intelligence, design of optimum networks, etc.
Since we do not expect to solve these problems optimally, there is a need to
design efficient approximation algorithms for them: algorithms that compute a
solution whose cost is within a small factor of the optimum. The PI has been
involved in designing approximation algorithms during the past decade. He has
also been part of an ongoing research program that shows that for many of these problems,
computing approximate solutions is no easier than computing optimum
solutions. (In other words, approximation is also NP-hard.) These
inapproximability results shed important light on the problems as well.

The project takes a two-pronged approach, combining a search for good
approximation algorithms with a search ---using the theory of probabilistically
checkable proofs (PCPs)--- for inapproximability results. The project focusses
on a collection of important algorithmic problems, including: learning mixtures
of distributions (a problem important in AI and data mining/analysis),
learning bayes nets and markov random fields (useful in speech recognition,
machine vision, medical diagnoses systems etc.), lattice problems (useful in
cryptography and cryptanalysis), and graph coloring (a central problem in complexity theory).
Progress, especially algorithmic progress, on any of these problems has
important consequences.

New directions in clustering and learning

Faced with ever-larger amounts of data, researchers, government
institutions, corporations and even the general public seek tools that help them deal
with large bodies of information, identify patterns in it, learn what these
patterns mean, and act upon that information in a timely fashion.
Developing such tools involves a novel and interesting blend of algorithms,
statistics, AI, and machine learning. The project assembles a team of experts (four
from academia and two from industry) in these areas to attack an interesting
and meaningful subset of such problems which have the general flavor of
clustering or learning.

The defining philosophy of this proposal is that no clear boundary
Separates the twin notions of clustering and learning. Clustering is usually driven
by the end goal of learning, but can also be viewed as a learning task
in itself since it results in a more compact description of the data.
By the same token all learning involves clustering of some sort, and
in fact this viewpoint is implicit in recent papers in the learning
literature. The project takes an integrated view of the entire problem of learning
patterns in data, starting from streaming computations that might produce
representative sketches of the data as it streams by, to problems of
clustering data into meaninful patterns (with attendant problems of outlier removal,
multiobjective optimization etc.), to learning algorithms that fit
sophisticated models (SVMs, bayesian nets, gaussian mixtures etc.) for
inference and reasoning tasks.

The investigators believe that all these disparate algorithmic efforts have
unifying ideas. Furthermore, their synergistic approach throws up several
interesting ideas of its own that could lead to significant advances.
Examples: include using coding theoretic ideas in disparate applications such as
Multiclass learning (a broad class of learning problems including text and speech
categorization, part-of-speech tagging, gesture recognition etc.) and shape recognition
in vision; the use of clustering ideas to do dimension reduction (offering
an alternative to popular SVD based approaches), and using ideas from
approximation algorithms and clustering to do near-optimal model fitting
for models such as bayesian nets.

The project also includes a management and educational plan that involves
dissemination of the ideas of this research through development of new
courses and also pieces of learning software that will be placed in the public domain.
Algorithms developed in as part of this project will be tested on large
datasets, including those obtained from Google Inc. Some algorithmic ideas will
also be implemented in industry (including Google).

Geometry has become a central notion in algorithm design, in fields
as diverse as bioinformatics and graph partitioning.
This research is a concerted and unified attack on a large subset of the
underlying mathematical problems, which often have to do with
geometric embeddings of finite metric spaces.
The concrete applications range from clustering and learning to
compact representation of data to graph partitioning to
nearest neighbor searching. Since the research spans a
a variety of fields, the assembled team is multidisciplinary,
involving analysts (Johnson and Naor), a geometer (Gromov),
a discrete mathematician and combinatorialist (Linial)
and algorithm designers (Arora and Charikar).

The research area emerging from the ongoing geometrization of
algorithms is an exciting new frontier for both mathematics and
computer science. For example, deep mathematical results such as
Lipschitz extension may turn out to have applications
to the practical problem of compactly representing computer sounds.
In turn, algorithmic settings provide a fertile new ground for
mathematical theory. The investigators study geometric representations
for data and low disortion mappings into structured spaces. Metrics that
arise in the design of approximation algorithms for NP-hard problems are
studied, especially to understand their local versus global properties.
The research develops new understanding for practically
important metrics such as earth mover and edit distance
metrics, which are defined in terms of computational effort and have
thus not been studied in mathematics.

Many optimization problems are NP-hard, and computing approximate solutions is an attractive way
to cope with NP-hardness. The effort to understand the approximation properties of NP problems has
occupied the center stage of theoretical computer science in the past decade. Despite many successes in this field, the status of some of the basic problems ---- metric tsp, vertex cover, graph coloring, sparsest cut etc.---is still open. The project consists of designing new approaches for computing approximate solutions to these problems. Any results for these central problems should generalize to many other problems.
The tools used involve sophisticated geometric arguments, and "lift and project" technique from polyhedral combinatorics. Another goal is to develop a comprehensive framework for designing approximation algorithms without relying on semidefinite programming (SDP). Many recent approximation algorithms
use SDP, which is not particularly efficient in practice. The goal in this project is to replace SDP with simpler algorithms based upon eigenvalue computations. Another aspect of the project is to prove lowerbounds to complement any new algorithms, or to rule out the existence of some of the above algorithms. The lowerbounds attempted would be both for all polynomial-time algorithms ---this would
use PCPs---and for specific algorithms arising from lift and project methods. (The latter consists of
viewing lift and project methods as a weak computational model.)

Broader impact of this project include dissemination efforts such as new innovative courses in graduate and
undergraduate education, new text book, and survey articles on current research.

Expeditions in Computing: Understanding, Coping with, and Benefiting from Intractability
Computational intractability imposes a limit on the ability to understand nature and design systems. Intractability is a stumbling block for postmen, travelling salesmen, map colorers, and millions of others who would like to complete their tasks as efficiently as possible, yet it is the foundation of 21st century cryptography, which in turn is a pillar of electronic commerce. In order to understand, manage, and exploit intractability it is imperative that progress be made on proving intractability in many forms and computational models, and on unraveling the interconnections among different forms and uses of intractability. This Expedition will explore an array of diverse but interrelated topics in computational intractability including algorithms, complexity, cryptography, analysis, geometry, combinatorics, and quantum mechanics. A "Center for Intractability," the first of its kind, will be based at Princeton. Addressing some of the deepest and hardest theoretical problems standing in the way of significant advancements in computer science, this Expedition involves a high degree of collegial interactivity through collaborations among geographically local participating institutions. Outreach includes an active "Women in Theory" program as well as programs targeting undergraduate and high-school students.

Computing approximate solutions to NP-hard optimization problems is an idea that is attractive both in theory and practice. Semidefinite programming (SDP) has become an indispensable tool in this area. It has led to new and better algorithms, and recently, thanks in part to the PI's prior work, more combinatorial algorithms that actually avoid SDP. The connections of SDP to high-dimensional geometry, metric embeddings, fourier transforms, and probabilistically checkable proofs are also at the center of some of the exciting work in theoretical computer science in recent years.

The project will work on ideas to (a) apply SDP to design new approximation algorithms for a host of problems, such as graph coloring, metric traveling salesman, graph partitioning, vertex cover; (b) use insights from SDP to design efficient combinatorial algorithms; (c) apply SDP insights (and a ``constructive'' version of SDP duality discovered recently by the PI and his student) to new settings such as decoding error-correcting codes, compressed sensing, and analysing network algorithms and swarm algorithms; (d) explore connections between SDPs, high-dimensional geometry, fourier transforms, and probabilistically checkable proofs.

SDP-inspired primal-dual approaches are an important new extension of traditional approaches based upon linear-programming duality, and developing their uses promises to have transformative impact. Development of new approximation algorithms for central problems like graph partitioning and metric TSP may also transform the field.

During this project new courses will be designed at the undergraduate and graduate level to teach these new ideas in an accessible way.

Graph expansion refers to the problem of partitioning a graph into two (or more) large pieces while minimizing the size of the "interface" between them. Graph partitions or separators are central objects of study in the theory of Markov chains, geometric embeddings, etc., and are a natural algorithmic primitive in numerous settings. Exact computation is NP-hard, so we are interested in approximate solutions. Despite much work, the status of most expansion-type problems is still open, in contrast to better-understood problems such as MAX-3SAT. In recent years it has become clearer that expansion-like problems hold the key to many of the remaining mysteries of approximation, such as the unique games conjecture or UGC (formulated by Khot when he was the PI's graduate student) and the Small-set expansion conjecture (formulated recently by Raghavendra and Steuerer, and part of Steurer's 2010 dissertation supervised by the PI).

A principal goal of this award is to apply new spectral (as in eigenvalues/eigenvectors) ideas to study graph expansion. These ideas were introduced in the PI's recent coauthored work with Barak and Steurer on subexponential algorithms for Unique Games problem.

This award may result in transformative outcomes such as resolution of the unique games conjecture, or new algorithms for graph partitioning based upon the full spectrum (as opposed to algorithms using just the second eigenvector whose limitations are well-known).

Many areas of machine learning (ML) currently rely on heuristic algorithms with no performance guarantees, and, in fact, the underlying problems are computationally intractable. The proposed project will lead to new machine learning algorithms with provable guarantees. The PIs will leverage theoretical ideas from average case analysis, semi-random models, approximation, solution stability, and approximate linear algebra, and develop new tools and techniques. Benefits from this endeavor will occur across fields. Theoretical computer science will benefit by gaining new problems and research agendas, and further development of algorithmic and mathematical tools. Machine learning will benefit by gaining new models (hopefully, more tractable than the ones currently in use), new modes of thinking, and new algorithms. The task of proving bounds on algorithms will provide insight into when they do or do not work, as well as suggest modifications to existing heuristics.

The project will involve training a new generation of graduate students and postdocs who will be fluent both in theoretical algorithms and machine learning. The PIs gained experience in delivering this kind of training and mentoring during the past couple of years and will continue this, including working with the undergraduate students. The PIs will disseminate the ideas of this project by lecturing, teaching, and creating new course materials, including videos. One specialized workshop will also be organized, devoted to the topics of study. Open-source software implementation will be released based upon any new learning algorithms that are discovered.

For various statistical procedures, mostly involving searching for a sparse structure in a high-dimensional parameter space, a gap between the performance attained by computationally efficient procedures and optimal ones has been observed. Examples include sparse regression, sparse principal component analysis, community detection, clustering, network analysis and matrix completion. This observation hints at the existence of an inherent statistical price to pay for using computationally efficient methods. The investigators study how large this price can be by drawing new bridges between theoretical computer science and statistical learning theory. Practically, this agenda requires shifting the current notion of statistical optimality to have more relevance under limited computational power and developing new algorithms that achieve said optimality.

The recent establishment of big-data as the new norm is causing a paradigm shift in statistics: computational power is the new bottleneck, not the lack of observations. The investigators lay theoretical foundations to study this new tradeoff between statistical and computational performance. A direct benefit of this research is to help statisticians and practitioners navigate the ocean of available heuristics and avoid the common pitfalls associated with using them.

Many areas of unsupervised learning (i.e, learning with data that has not been labeled by humans) currently rely on heuristic algorithms that lack provable guarantees on solution quality or running time. In fact the underlying problems - as currently formulated - are often known to be computationally intractable (NP-hard, to use a technical term). This proposal identifies a big set of these problems that can be seen as twists - involving constraints such as nonnegativity and sparsity - on classical linear algebra problems like solving linear systems, rank computation, and eigenvalues/eigenvectors. The PI has proposed calling this set of problems collectively as Linear Algebra++. The project will seek to develop algorithms with provable guarantees for these problems. The methodology will be to make suitable assumptions about the structure of realistic inputs. The algorithms will be applied to problems in unsupervised learning, in areas such as topic modeling, natural language processing, semantic embeddings, sparse principle components analysis (PCA), deep nets, etc.

The work will lead to new and more efficient algorithms for big data processing that will come with provable guarantees of quality. It will bring new rigorous approaches to machine learning. (Some recent work of the PI shows that the new rigorous approaches can be quite practical.) It will advance the state of art in theoretical computer science by expanding its range and its standard toolkit of algorithms. It will contribute fundamentally new primitives to classical linear algebra and applied mathematics.

The project will train a new breed of graduate students who will be fluent both in theoretical algorithms and machine learning. The PI has a track record in this kind of work and training during the past few years and will continue this including working with undergrads and Research Experiences for Undergraduates (REU) students. Any new algorithms discovered as part of this project will be released as open source code. The PI also plans a series of other outreach activities in the next few years including (a) A workshop. (b) A special semester or year at the Simons Institute in 2016-17 on provable bounds in machine learning which he will coorganize. (c) A new book on graduate algorithms based upon his new grad course, which tries to re-orient algorithms training for today's computer science problems. (d) A series of talks aimed at broad audiences, of which he gives several each year.

The techniques will build upon recent progress by the PI and others on problems such as nonnegative matrix factorization, sparse coding, alternating minimization etc. They involve average case analysis, classical linear algebra, convex optimization, numerical analysis, etc., as well involve completely new ideas. They could have a transformative effect on machine learning and algorithms.

Artificial Intelligence along with Machine Learning are perhaps the most dominant research themes of our times - with far reaching implications for society and our current life style. While the possibilities are many, there are also doubts about how far these methods will go - and what new theoretical foundations may be required to take them to the next level overcoming possible hurdles. Recently, machine learning has undergone a paradigm shift with increasing reliance on stochastic optimization to train highly non-convex models -- including but not limited to deep nets. Theoretical understanding has lagged behind, primarily because most problems in question are provably intractable on worst-case instances. Furthermore, traditional machine learning theory is mostly concerned with classification, whereas much practical success is driven by unsupervised learning and representation learning. Most past theory of representation learning was focused on simple models such as k-means clustering and PCA, whereas practical work uses vastly more complicated models like autoencoders, restricted Boltzmann machines and deep generative models. The proposal presents an ambitious agenda for extending theory to embrace and support these practical trends, with hope of influencing practice. Theoretical foundations will be provided for the next generation of machine learning methods and optimization algorithms.

The project may end up having significant impact on practical machine learning, and even cause a cultural change in the field -- theory as well as practice -- with long-term ramifications. Given the ubiquity as well as economic and scientific implications of machine learning today, such impact will extend into other disciplines, especially in (ongoing) collaborations with researchers in neuroscience. The project will train a new generation of machine learning researchers, through an active teaching and mentoring plan at all levels, from undergrad to postdoc. This new generation will be at ease combining cutting edge theory and applications. There is a pressing need for such people today, and the senior PIs played a role in training/mentoring several existing ones.

Technical contributions will include new theoretical models of knowledge representation and semantics, and also frameworks for proving convergence of nonconvex optimization routines. Theory will be developed to explain and exploit the interplay between representation learning and supervised learning that has proved so empirically successful in deep learning, and seems to underlie new learning paradigms such as domain adaptation, transfer learning, and interactive learning. Attempts will be made to replace neural models with models with more "interpretable" attributes and performance curves. All PIs have a track record of combining theory with practice. They are also devoted to a heterodox research approach, borrowing from all the past phases of machine learning: interpretable representations from the earlier phases (which relied on logical representations, or probabilistic models), provable guarantees from the middle phase (convex optimization, kernels etc.), and an embrace of nonconvex methods from the latest deep net phase. Such eclecticism is uncommon in machine learning, and may give rise to new paradigms and new kinds of science.

Large language models (LLMs) have achieved unprecedented success in natural language processing (NLP). Since language models are being seen as a cornerstone of artificial intelligence in the near future, there is a need to be able to understand them, and to convey that understanding to regulators as well as the general public. These models are based on deep neural networks that are trained from vast quantities of text and have been demonstrated to be highly useful in performing tasks such as question answering, text classification, machine translation and summarization. Despite the huge empirical success, there is little understanding about their inner workings. This project seeks to bridge the gap by developing conceptual and mathematical understanding about training and using LLMs. The project will advance such understanding. The project will also seek to develop and disseminate instructional materials and draw on ideas from the project to impact ongoing programs at their institution to help increase participation in computing by individuals from underrepresented groups. <br/><br/>The project has three components. (1) We will first build simplified generative models that capture the intrinsic structures of text, and analyze language models that are trained on texts from such generative models. (2) We then analyze why the learned language models can encode useful information that helps a wide range of downstream tasks. (3) Finally, we analyze and design new adaptation methods for downstream tasks with quantitative sample and computational efficiency guarantees. Education and outreach plans are integrated into this project: the investigators will develop a new introductory course in machine learning and disseminate instructional materials, mentor graduate and undergraduate students from underrepresented groups (through Princeton Freshman Scholars Institute, Stanford Summer Teacher Research Program, REU’s) and organize research workshops to promote conversations between the theoretical machine learning and NLP community.<br/><br/>This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.