Maria-Florina Balcan, Ph.D. - US grants

Over the years, Machine Learning has become a very broad discipline with important applications to many areas including computer vision, speech recognition, robotics, and bio-surveillance, to name just a few. Moreover, many of these application areas have faced a huge increase in the volume of available data of various kinds. In order to be able to use all this data a number of new learning approaches have been proposed. These approaches have been intensely explored in the machine learning community, with many heuristics and specific algorithms, as well as experimental results reported. Unfortunately, however, the standard theoretical models do not capture the key issues involved in these learning techniques, and it has become clear that for developing robust, versatile, and general algorithms in these settings a more fundamental understanding is necessary. This project will develop theoretical foundations for such learning paradigms which are of significant practical importance but are not explained by existing theoretical models. This project will also develop fundamental new connections between Machine Learning, Game Theory, and Combinatorial Optimization, that will aid in advancing and solving important problems in all three areas.

The key research directions of this project are:

1. Developing mathematical foundations and algorithms for important machine learning paradigms that are not captured well by standard models. This includes new analysis frameworks as well as new practical and theoretically justified algorithms both for semi-supervised learning and active learning, two important emerging approaches for incorporating unlabeled data and interaction in the learning process. This project will also explore a fundamentally new approach to analyzing clustering -- a classic central task in the analysis and exploration of data, for which the existing theory has been very brittle. This framework will enable practitioners to describe in a formal way the properties they believe to be true about their data, and then use these properties to choose or design the right algorithm for their needs.

2. Developing novel fundamental connections between Machine Learning and Algorithmic Game Theory in order to solve difficult problems in multi-agent systems that have resisted previous approaches. In particular, many multi-agent interactions have bad equilibria, and it is important to develop methods for helping agents in such bad states to move to better ones. This project will develop techniques for understanding and influencing the behavior of natural dynamics in games of this type, by using connections to important concepts in Machine Learning, such as learning from untrusted experts' advice.

3. Developing fundamental connections between Machine Learning and Combinatorial Optimization in order to advance both areas. These include new connections between approximation algorithms and learning-based objectives for clustering, and new algorithms and computational theory for learning submodular functions. Submodular functions, which describe laws of diminishing returns, are ubiquitous in economic optimization problems, and methods for learning them from observed data can aid in designing improved decision procedures.

Altogether, this project will advance Machine Learning, Algorithmic Game Theory, and Combinatorial Optimization, by developing and exploiting novel connections between these areas. The theory developed by this work will enable the next generation of powerful algorithms for machine learning and multi-agent systems. It will additionally impact a wide range of application areas including computer vision, robotics, bio-surveillance, and online auction design. More broadly, the research results of this project will have impact across a number of scientific, medical, and industrial fields. The PI's education plan further contributes to the project's impact. In addition to advising a diverse set of students on projects directly related to this project, the progress in this research will be used to influence the curriculum via special courses presenting the theoretical advances along with their applications. The PI will also contribute to increasing the participation of women in computational sciences.

The intersection of Computer Science and Economics has become increasingly important to the development of both fields. Today's software often must handle multiple individuals with their own interests in mind, bringing incentive issues to the forefront in algorithm design. Economic problems, especially in electronic commerce, increasingly involve large numbers of goods and buyers as well as unknown and complex market conditions, making algorithms and machine learning of key importance. This project aims to address fundamental questions at the heart of the intersection of these two fields. These include problems of modeling and influencing behavior in systems with large numbers of agents and components, problems of optimization under complex and changing preferences and constraints in electronic commerce, and problems of efficiently computing and estimating basic economic quantities.

This project specifically has three main thrusts. The first is development of algorithms and analysis techniques for positively influencing dynamics in systems with large numbers of interacting agents. For example, if behavior is currently at a poor-quality equilibrium, when can additional information or a few targeted incentives be used to "nudge" behavior towards a good equilibrium? This applies not only to self-interested agents but also to components in a distributed system acting on local information (such as sensors in a sensor network). The second thrust is development of algorithms for efficiently computing or estimating important economic quantities. This includes approximately computing Nash equilibria in large interactions, and learning submodular functions and other common valuation classes from observations of behavior or experimentation. The third thrust is developing mathematical frameworks for understanding and solving problems of pricing and resource allocation in settings with unknown and changing market conditions. These frameworks are crucial for next-generation markets for resources such as computing power and network bandwidth.

Machine learning is a broad discipline with important application domains including computer vision, robotics, sustainability, and bio-surveillance. Its past successful evolution was heavily influenced by mathematical foundations developed for core problems of generalizing from labeled data. However, with the variety of applications of machine learning across science, engineering, and computing in the age of Big Data, re-examining the underlying foundations of the field has become imperative. This project aims to substantially advance the field of machine learning by developing foundations and algorithms for a number of important modern learning paradigms. These include interactive learning, where the algorithm and the domain expert engage in a two-way dialogue to facilitate more accurate learning from less data compared to the classic approach of passively observing labeled data; distributed learning, where a large dataset is distributed across multiple servers and the challenge lies in learning with limited communication; and multi-task learning, where the goal is to solve multiple related learning problems from less data by taking advantage of relationship among the learning tasks. The project also aims to develop new connections between machine learning and property testing, a flourishing area of theoretical computer science. In addition to solving fundamental questions in each of these directions, the project will highlight and leverage synergies between these topics.

More specifically, the key research directions of this project are: (1) Developing mathematical foundations for interactive learning by analyzing new forms of interactions between the learning algorithm and the domain expert that could lead to fast and efficient learning of difficult tasks by wisely exploiting the capabilities of domain experts. (2) Developing new algorithms for distributed learning, an important modern scenario where data is distributed among several locations. This project will develop protocols that trade off the various types of resources involved in such settings (computation, communication, and domain expertise). (3) Developing new algorithms with provable guarantees for learning multiple related tasks from limited amounts of labeled data and massive amounts of unlabeled data by wisely exploiting explicitly known or latent relationships between the given tasks. (4) Developing mathematical foundations for property testing, where the question is to quickly determine whether there exists a low-error rule of a desired form by using significantly less data than needed to actually find the rule itself. This project will specifically focus on active and distributed scenarios, with the goal of using testing as a way to improve learning efficiency itself.

Broader impacts include mentoring women in CS and actively organizing workshops and seminars in the interdisciplinary area.

Motivation.
Discrete optimization problems have been studied by both the optimization and computer science communities. This EAGER project proposes to develop new approaches by synthesizing the ideas from the two communities by interdisciplinary collaboration between computer scientists and optimization specialists in mathematics and engineering. The goal is to develop rigorous and systematic approaches to discrete optimization problems by combining insights and state-of-the-art methods from integer programming (e.g., cutting planes and branch-and-bound) and algorithmic ideas from computer science (including online algorithms and machine learning). To be able to evaluate and compare methods on real-world instances, PIs plan to develop a theory of "natural instances". This theory starts from the application side, tries to model properties of the instances that arise from that application and then give guarantees for algorithms on such instances. The project plans to incorporate machine learning into algorithms to solve integer programs. PIs propose a systematic development of an algorithmic theory of cutting planes to identify families of instances for which they are provably efficient and to take advantage of the computational benefits of sparse cutting planes.

Intellectual Merit. The ideas that are proposed here are novel and intellectually challenging. The notion of natural systems, insofar as known, has not been investigated previously. While machine learning algorithms currently use optimization technology, the reverse has not been systematically studied. Cutting planes are mainly used on an ad-hoc basis. There is no systematic theory regarding problems for which cutting plane algorithms are provably efficient. It is known that sparsity is needed in the linear algebra of cutting plane algorithms, but there is very little known about polyhedra that are defined by only sparse inequalities.

Broader Impact. This EAGER project is motivated by a range of optimization problems of high societal impact from transportation and supply chain logistics such as palletizing, package delivery, petro-chemical cargo routing, vehicle and mobile robot routing to energy production and distribution. The ultimate goal is to study algorithmic optimization methods which over the next decade could lead to more than a billion dollars in annual savings in energy production and distribution, a 50% reduction in fuel consumption in supply chains and elimination of energy shortages caused by extreme weather disturbances. This will be possible by the creation of optimization algorithms that are orders of magnitude faster, more robust and capable of dealing with massive and messy data. This EAGER will provide research training for both graduate and postgraduate students and intensive collaboration among multiple EAGERs, and will provide rapid dissemination of the research throughout the relevant communities by hosting a workshop at Georgia Tech.

The aim of this project is to develop mathematical models, analysis, and algorithms that will advance both the design and understanding of large-scale machine learning systems. In recent years, machine learning has come into widespread use across a range of applications, and we have also seen significant advances in the theoretical understanding of learning processes. Yet despite these successes, there remains a gulf between theory and application. For example, applications often demonstrate success on problems that theory tells us are intractable in the worst case. Furthermore, as modern machine learning applications scale up from learning of single tasks to learning many tasks simultaneously, new theory is needed to analyze these larger scale multi-task learning settings. This project aims to bridge this gap by developing and applying theory targeted toward realistic-case analysis of learning problems, which capture the structures that enable applications to succeed even when theoretical analyses show the impossibility of doing so in the worst case. This work will be guided by problems at the core of NELL and InMind, two current learning systems that address large-scale multi-task machine learning problems, for reading the web and providing highly personalized electronic assistants to hundreds of interconnected mobile phone users.

More specifically, this project has three main components:

(1) To develop computationally efficient algorithms for clustering, constrained optimization, and related optimization tasks crucial to large-scale machine learning, with provable guarantees under natural, realistic non-worst-case analysis models.

(2) To develop foundations and practical algorithms for multi-task and life-long learning that exploit explicit and implicit structure to minimize key resources including computation time and human labeling effort, as well as address key constraints such as privacy.

(3) To apply the algorithms developed to solve key challenges in two current large-scale learning systems, NELL and InMind.

The proposed work will aid the development of large-scale machine learning applications, as well as create important connections between multiple areas of significant importance in modern machine learning and theoretical computer science. In addition to advising students on topics connected to this project, research progress (on multi-task learning, life-long learning, and clustering) will be integrated in the curricula of several courses at CMU and course materials will be made available on the world wide web. Course projects based on this research will be available to students in the introductory machine learning course at CMU, which enrolls over 600 students each year. In addition, students seeking topics for undergraduate thesis or independent study may also pursue research affiliated with this project.

Practical privacy-preserving machine learning methods are currently of critical importance in medical, financial and consumer applications, among others. The aim of this project is to develop practical private machine learning algorithms that can be easily implemented by practitioners in any field that holds sensitive data, while keeping robust privacy guarantees. The proposed research will extend the existing rigorous theoretical guarantees of differential privacy to reach the requirements of modern machine learning algorithms in concrete practical settings. The generated intellectual merit therefore spans all the way from the theory to practical algorithms. The resulting methods have the potential to benefit existing real-world applications in many high impact domains. The PIs have several ongoing and successful collaborations with medical practitioners and researchers and will evaluate the resulting algorithms on real patient data in high impact medical applications. All algorithms will be made publicly available as open source. Both PIs are dedicated towards actively hiring minorities and involving undergraduate students in research.

Differential privacy (DP) is now recognized as one of the most rigorous and potentially usable notions of statistical privacy, and has become a full-fledged research field. The aim of this research is to provide reliable privacy guarantees for practical machine learning algorithms, which is invaluable to protect individuals who volunteer their sensitive data for research purposes. We identify several areas with high impact potential and propose four concrete research thrusts. (1) Private Causal Inference. Causal inference is one of the most promising new directions in machine learning, that recently has become practical. Some of the most interesting causal questions deal however with medical or government policy data, which are inherently sensitive. We propose to unite the recent breakthroughs in both fields (causal inference and DP) and derive a practical and theoretically sound method to ensure differentially private causal inference. (2) Privacy for Bayesian Global Optimization. The success of deep learning has created a surge in popularity for Bayesian Global Optimization (BGO) for hyper-parameter tuning. Simultaneously, recent publications have tied the stability properties of differential privacy to generalization in adaptive data analysis. We propose to unite these recent developments and improve the generalization of BGO using insights from DP. Here, we are not protecting individuals from privacy leaks, but algorithms from overfitting-allowing for fine trade-offs of "privacy" vs. efficacy. (3) Private Communication-Efficient Distributed Learning. In response to the growth of data distributed over multiple machines, we aim to design practical private and communication-efficient algorithms for supervised and unsupervised learning problems. This work will build off our recent work on distributed learning and clustering algorithms. (4) Practical Private Active Learning. In the age of big data, there has been tremendous interest both in machine learning and its application areas on designing active learning algorithms that most efficiently utilize the available data, while minimizing the need for human intervention. Recently there have been exciting results on understanding statistical and computational principles (including work by the PIs). This research will develop new foundations and new practical well-founded active learning algorithms that are not only statistically and computationally efficient, but also differentially private.

Machine learning studies the design of automatic methods for extracting information from data. It is a highly successful technique that has transformed several fields including computer vision and information retrieval, and it holds great promise to transform many other areas across science and technology. This project aims to substantially advance machine learning by providing new theoretical foundations and algorithms that are required both for new applications and to cope with the current massive amounts of available data. This includes developing well founded techniques for learning more complex objects (than classic techniques that are often limited to prediction), learning from very small amounts of annotated training data, and efficient transfer (of representations and other useful information) among tasks in order to aid more efficient learning of future tasks. These topics are of significant practical importance and expose fundamental statistical and computational issues. This project will impact not only theory of computing and machine learning, but also many application areas where machine learning is used. In addition to advising both graduate and undergraduate students on topics connected to this project, research progress will be integrated in the curricula of several courses at Carnegie Mellow University and course materials will be made available on the web worldwide.

The key research directions of this project are:

(1)Providing formal guarantees and algorithms for transferring internal representations (such as a portion of a deep network) learned while solving an earlier task to new related tasks, in ways that can significantly reduce both data requirements and run-time for solving the new tasks. This project will analyze both a direct transfer of a learned representation, and additional fine-tuning steps using a small amount of data from the new task.

(2)Developing foundations and algorithms for transfer learning in unsupervised and partially supervised learning scenarios, in order to reduce reliance on difficult-to-verify assumptions in cases where labeled data is scarce.

(3)Developing new algorithms for online learning of complex, non-convex functions, which do not satisfy standard conditions such as convexity or Lipschitzness. This project will consider online learning of such functions under various forms of feedback, including full information, bandit, and semi-bandit settings, and will also explore implications of these techniques to transfer learning in partially supervised scenarios.

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.

AI and optimization are used in a wide range of scientific and business applications. Much of AI and optimization in turn are powered by search techniques such as branch and bound. These search techniques are used to intelligently explore a large number of possible solutions to a problem in order to come up with the best solution for the problem at hand. Unfortunately, in the worst case, their running time can be exponential, and much effort goes into the design of adjustable search strategies that can have a large effect on runtime, solution quality, or both. Tuning these strategies is typically done manually by experts. Recently there has been work on automated tuning of some variations of search, but these methods have not come with performance guarantees, and in general there is little theoretical understanding of what kinds of guarantees one might hope to achieve. The goal of this project is to provide new machine learning approaches with strong provable guarantees for customizing search techniques and automatically determining a nearly optimal search strategy for any given problem domain. This project aims to provide formal guarantees for its procedures as well as techniques that scale up to larger and more complex problems than currently possible. The algorithms and models developed in this research will be driven by, and applied to, optimization problems at the core of important real-world applications including kidney exchange and combinatorial auction design. These are domains where improved optimization procedures have significant impact.

Specific goals in this project include: (1) Developing effective tree search strategies (including branch-and-bound methods) via machine learning that are widely applicable, scalable, and have strong provable guarantees. (2) Learning branching and node selection strategies together, and learning admissible heuristics for informed search techniques including A* search. (3) Applying algorithms developed to solve key challenges in two important application domains: Kidney Exchange and Automated Mechanism Design. (4) Learning how to branch in the context of decision-tree learning, an important machine learning paradigm, and in particular in the design of heuristics for top-down decision-tree induction. The project will impact artificial intelligence, optimization, machine learning, theory of computing, as well as many areas that require repeatedly solving hard optimization problems from a given domain. This includes kidney exchange and mechanism design which can have a broad impact across society and commerce. In addition to advising both graduate and undergraduate students on topics connected to this project, research progress will be integrated in the curricula of several courses at Carnegie-Mellon University and course materials will be made available on the web worldwide.

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.