Iterative hard clustering of features

Vincent Roulet (1) , Fajwel Fogel (2) , Alexandre d'Aspremont (2) , Francis Bach (2, 1)

1 SIERRA - Statistical Machine Learning and Parsimony
2 LIENS - Laboratoire d'informatique de l'école normale supérieure

We seek to group features in supervised learning problems by constraining the prediction vector coefficients to take only a small number of values. This problem includes non-convex constraints and is solved using projected gradient descent. We prove exact recovery results using restricted eigenvalue conditions. We then extend these results to combine sparsity and grouping constraints, and develop an efficient projection algorithm on the set of grouped and sparse vectors. Numerical experiments illustrate the performance of our algorithms on both synthetic and real data sets.

Domaines: Optimisation et contrôle [math.OC]; Intelligence artificielle [cs.AI]

Vincent Roulet, Fajwel Fogel, Alexandre d'Aspremont, Francis Bach. Iterative hard clustering of features. 2017. ⟨hal-01664964⟩