Timezone: »
We consider the problem of cardinality penalized optimization of a convex function over the probability simplex with additional convex constraints. It's wellknown that the classical L1 regularizer fails to promote sparsity on the probability simplex since L1 norm on the probability simplex is trivially constant. We propose a direct relaxation of the minimum cardinality problem and show that it can be efficiently solved using convex programming. As a first application we consider recovering a sparse probability measure given moment constraints, in which our formulation becomes linear programming, hence can be solved very efficiently. A sufficient condition for exact recovery of the minimum cardinality solution is derived for arbitrary affine constraints. We then develop a penalized version for the noisy setting which can be solved using second order cone programs. The proposed method outperforms known heuristics based on L1 norm. As a second application we consider convex clustering using a sparse Gaussian mixture and compare our results with the well known soft kmeans algorithm.
Author Information
Mert Pilanci (Stan)
Laurent El Ghaoui (University of California at Berkeley)
Venkat Chandrasekaran (California Institute of Technology)
More from the Same Authors

2021 Spotlight: NewtonLESS: Sparsification without Tradeoffs for the Sketched Newton Update »
Michal Derezinski · Jonathan Lacotte · Mert Pilanci · Michael Mahoney 
2021 Poster: NewtonLESS: Sparsification without Tradeoffs for the Sketched Newton Update »
Michal Derezinski · Jonathan Lacotte · Mert Pilanci · Michael Mahoney 
2019 : Learning Regularizers from Data »
Venkat Chandrasekaran 
2008 Poster: A Convex Upper Bound on the LogPartition Function »
Laurent El Ghaoui · Assane Gueye 
2008 Poster: An Homotopy Algorithm for the Lasso with Online Observations »
Pierre Garrigues · Laurent El Ghaoui 
2007 Poster: Adaptive Embedded Subgraph Algorithms using WalkSum Analysis »
Venkat Chandrasekaran · Jason K Johnson · Alan S Willsky