Discrete Optimization in Machine Learning: Connecting Theory and Practice

Solving optimization problems with ultimately discrete solutions is becoming increasingly important in machine learning. At the core of statistical machine learning is to make inferences 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 inherently discrete optimization problems. Many of these optimization problems are notoriously hard. As a result, abundant and steadily increasing amounts of data -- despite being statistically beneficial -- quickly render standard off-the-shelf optimization procedures either intractable, or at the very least impractical.

However, while many problems are hard in the worst case, the problems of practical interest are often much more well-behaved, or are well modeled by assuming properties that make them so. Indeed, many discrete problems in machine learning can possess beneficial structure; such structure has been an important ingredient in many successful (approximate) solution strategies. Examples include the marginal polytope, which is determined by the graph structure of the model, or sparsity that makes it possible to handle high dimensions. Symmetry and exchangeability are further exploitable characteristics. In addition, functional properties such as submodularity, a discrete analog of convexity, are proving to be useful to an increasing number of machine learning problems.
One of the primary goals of this workshop is to provide a platform for exchange of ideas -- between machine learning, algorithms, discrete mathematics and combinatorics as well as application areas of computer vision, speech, NLP, biology and network analysis -- on how to discover, exploit, and deploy such structure.