BAD'16 Poster

Bristol Algorithms Days 2016
Workshop on Efficient Algorithms and Lower Bounds

2 - 3 February 2016

  •    •    •  

Learning with submodular functions: Models, algorithms, and applications

Alina Ene

Many applications in machine learning involve huge amounts of data with a very rich structure. The scale and complexity of the data makes learning very challenging from a computational and modeling perspective; to learn the most from our data, we need both powerful models and efficient algorithms for those models, and it is not a priori clear that these two competing goals can be reconciled.

In this talk, we explore some of the modeling and algorithmic challenges arising in applications. We present three research vignettes that address these challenges by modeling and exploiting the structure present in applications.

In the first example, we consider learning tasks with a rich combinatorial structure that can be modeled as constrained submodular maximization problems, and we design distributed algorithms for these problems with provable guarantees. In the second example, we give very efficient algorithms for a rich class of submodular minimization problems arising in applications. In the third example, we introduce a model that captures allocation problems with submodular costs and we give a generic approach for designing algorithms for problems in this model.


  The University of Bristol   EPSRC