Greed is Great ICML'15 Workshop

ICML 2015 Workshop

Date: Friday, July 10, 2015, Lille, France


Over the past few years, many problems from machine learning and signal processing have aimed at automatically learning sparse representations from data and a very popular strategy has been to state the mentioned problems as convex optimization problems. However, aiming at sparsity actually involves an l0 "norm" regularization/constraint, and the convex opti- mization way is essentially a proxy to induce sparsity—through, e.g., the recourse to an l1 norm, which itself is a proxy to l0. Greedy methods constitute another strategy to tackle the combi- natorial optimization problems posed by the issue of learning sparse representations/predictors. Yet, this family of methods has been much less investigated than the convex relaxation approach by the ICML community. This is precisely the purpose of this workshop to give a central place to greedy methods for machine learning and discuss the blessings of such methods from the computational and generalization perspectives. 


Key dates

Submission deadline May 1, 2015 
Notification of acceptanceMay 10, 2015
Camera-ready May 24, 2015
Workshop July 10, 2015

Topics of interest

The program of this workshop will critically build upon a) the wealth of work on greedy algorithms in fields of theoretical computer science such as discrete algorithms or graph theory and b) the existence of machine learning, signal processing, and statistical modeling contributions that show it is possible to take advantage of properties of greedy algorithms that go beyond their mere computational merits.

The workshop will build around invited talks of renowned researchers that have contributed to the field of greedy methods and their use for machine learning. It will also devote time for contributed talks revolving around (but not limited to):

  • (kernel) matching pursuit procedures and variants 􏰔 matroid theory
  • submodular optimization
  • greedy (discrete) optimization
  • spark, coherence, exact recovery
  • compressed sensing
  • ...

Invited Speakers

  • Aurélien Bellet, Post-doctoral Researcher, Statistics and Applications Group, LTCI, CNRS, Télécom ParisTech
  • Kveton Branislav, Researcher, Adobe, San Jose, USA
  • Cédric Herzet, Researcher, INRIA Rennes, France
  • Guy Lever, Research Associate, UCL Dept. of Computer Science London, UK
  • John Shawe-Taylor, Prof., Centre for Computational Statistics and Machine Learning, UCL, London, UK
  • Ke Wei, post-doctoral Researcher, Dept. of Mathematics, Hong-Kong University of Science and Technology

Program (The Room ARTOIS)

08:30-08:35    Introduction 
08:35-09:20    John Shawe-Taylor "Sparsity Based Bounds on Learners and their Applications"
09:20-09:40    Yuxin Chen  "Sequential Information Maximization: When is Greedy Near-optimal?"
09:40-10:00    Assaf Hallak  "Off-policy Model-based Learning under Unknown Factored Dynamics"

10:30-11:15    Kveton Branislav "Learning to Act Greedily: Matroid and Polymatroid Bandits"
11:15-12:00    Aurélien Bellet "The Frank-Wolfe Algorithm: Recent Results and Applications to High-Dimensional Similarity Learning and Distributed Optimization"

14:00-14:45    Ke Wei "Conjugate Gradient Iterative Hard Thresholding for Compressed Sensing and Matrix Completion" 
14:45-15:30    Guy Lever "Sparse-greedy methods for efficient non-parametric policy search"
15:30-15:50    Alexandre Drouin  "Greedy Biomarker Discovery in the Genome with Applications to Antimicrobial Resistance"

15:50-16:30   poster sessions

16:30-16:50    Yash Sastangi "Exploiting Submodular Value Functions for Faster Dynamic Sensor Selection"
16:50-17:35    Cédric Herzet "Beyond Uniform Analysis: Exploiting the Decay of Sparse Vectors"
17:35       Wrap-up

Format and submissions

The workshop follows the traditional format of invited talks (see the corresponding section) and contributed talks with poster sessions. The contributions should come in the form of short papers, not exceeding 4 pages, references excluded, and should be formatted as per the main conference guidelines, available at The papers should include authors names and affiliation. We also welcome papers that have been accepted in recent editions of machine learning and signal processing conferences and journals, such as ICML (including the current edition), NIPS, ECML, ALT and COLT. All the accepted papers will be featured in the poster sessions and a selected few will also be presented as contributed talks and featured in spotlight sessions. Submissions should be made via e-mail at

Accepted papers will be made available at the workshop’s webpage.


Scientific committee

  • Sandrine Anthoine, CNRS, University of Aix-Marseille, France
  • Liva Ralaivola, CNRS, University of Aix-Marseille, France
  • Alain Rakotomamonjy, Université de Rouen, France
  • Thomas Blumensath, University of Oxford, UK
  • Charles Soussen, Université de Lorraine, France
Organizing committee
  • Sokol Koço, Université de Rouen, France
  • Gilles Gasso, INSA Rouen, France
  • Clothilde Melot, CNRS, University of Aix-Marseille, France
  • François-Xavier Dupé, CNRS, University of Aix-Marseille, France
  • Maxime Bérar, Université de Rouen, France
Subpages (1): Abstracts of the talks