Overview

Solving optimization problems with ultimately discretely solutions is becoming increasingly important in machine learning: At the core of statistical machine learning is to infer conclusions from data, and when the variables underlying the data are discrete, both the tasks of inferring the model from data, as well as performing predictions using the estimated model are discrete optimization problems. Many of the resulting optimization problems are NP-hard, and typically, as the problem size increases, standard off-the-shelf optimization procedures become intractable.

Fortunately, most discrete optimization problems that arise in machine learning have specific structure, which can be leveraged in order to develop tractable exact or approximate optimization procedures. For example, consider the case of a discrete graphical model over a set of random variables. For the task of prediction, a key structural object is the "marginal polytope," a convex bounded set characterized by the underlying graph of the graphical model. Properties of this polytope, as well as its approximations, have been successfully used to develop efficient algorithms for inference. For the task of model selection, a key structural object is the discrete graph itself. Another problem structure is sparsity: While estimating a high-dimensional model for regression from a limited amount of data is typically an ill-posed problem, it becomes solvable if it is known that many of the coefficients are zero. Another problem structure, submodularity, a discrete analog of convexity, has been shown to arise in many machine learning problems, including structure learning of probabilistic models, variable selection and clustering. One of the primary goals of this workshop is to investigate how to leverage such structures.

There are two major classes of approaches towards solving such discrete optimization problems machine learning: Combinatorial algorithms and continuous relaxations. In the first, the discrete optimization problems are solved directly in the discrete constraint space of the variables. Typically these take the form of search based procedures, where the discrete structure is exploited to limit the search space. In the other, the discrete problems are transformed into continuous, often tractable convex problems by relaxing the integrality constraints. The exact fractional solutions are then "rounded" back to the discrete domain. Another goal of this workshop is to bring researchers in these two communities together in order to discuss (a) tradeoffs and respective benefits of the existing approaches, and (b) problem structures suited to the respective approaches. For instance submodular problems can be tractably solved using combinatorial algorithms; similarly, in certain cases, the continuous relaxations yield discrete solutions that are either exact or with objective within a multiplicative factor of the true solution.

Schedule

7:30-7:40 Introduction by the organizers
7:40-8:15 Andreas Krause: Submodularity in Machine Learning
8:15-9:10 Vahab Mirrokni: Recent Developments in Submodular Maximization
9:10-9:30 BREAK
9:30-10:00 David Sontag: Polyhedral approaches to graphical model inference & structure learning
10:00-10:30 Ben Taskar: Polytopes arising in structured prediction problems
10:30-11:00 SPOTLIGHTS
11:00-3:10 BREAK (POSTERS)
3:10-3:30 Daniel Golovin: Online Optimization of submodular functions
3:30-4:05 Yoram Singer: Sparsify This, Sparsify That: Efficient Learning Algorithms for Learning Sparse Models from Voluminous Amounts of Data
4:05-4:40 Pawan Kumar: Relaxations and Moves for MAP Estimation in Discrete MRFs
4:40-5:00 Pradeep Ravikumar: Graphical model structure learning via l1 regularization
5:00-5:30 BREAK (POSTERS)
5:30-5:50 Alekh Agarwal: Graph-structured rounding schemes for graph-structured Linear Programs
5:50-6:10 Risi Kondor: A Fourier space algorithm for solving quadratic assignment problems
6:10-6:30 Nina Balcan: Learning submodular functions


Papers

  • Dhruv Batra, Tsuhan Chen. Dynamic Planar-Cuts: Efficient Computation of Min-Marginals for Outer-Planar Models [pdf]
  • Volkan Cevher, Andreas Krause. Greedy Dictionary Selection for Sparse Representation [pdf]
  • Stefanie Jegelka, Jeff Bilmes. Notes on graph cuts with submodular edge weights [pdf]
  • Luigi Malagò, Matteo Matteucci, Giovanni Pistone. Stochastic Relaxation as a Unifying Approach in 0/1 Programming [pdf]
  • Radu Marinescu, Rina Dechter. Advancing AND/OR Search for Optimization [pdf]
  • Julian McAuley, Tiberio Caetano. Exploiting Within-Clique Factorizations in Junction-Tree Algorithms [pdf]
  • Hai Nguyen, Katrin Franke, Slobodan Petrovic. Optimizing a Class of Feature Selection Measures [pdf]
  • Tianyi Zhou, Dacheng Tao. Fast Gradient Clustering [pdf]

Format

Broadly, this one-day workshop aims at exploring the current challenges in discrete optimization in machine learning. It will explore these topics in tutorials and invited talks. In addition, we will have a poster session with spotlight presentations to provide a platform for presenting new contributions.

Organizers

Other related workshops


The workshop is related to the workshops Optimization in Machine Learning and Algebraic and Combinatorial Methods in Machine Learning. It is also related to the Workshop on Graph Cuts and Related Discrete or Continuous Optimization Problems at the Institute for Pure and Applied Mathematics (IPAM), March 2008.  However, in contrast to these workshops, the focus is on exploiting structure in order to  solve discrete optimization problems, and applications of discrete optimization in machine learning.