Timezone: »
We consider the problem of cardinality penalized optimization of a convex function over the probability simplex with additional convex constraints. It's well-known 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 k-means 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: Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update »
Michal Derezinski · Jonathan Lacotte · Mert Pilanci · Michael Mahoney -
2022 : On the Abilities of Sequence Extrapolation with Implicit Models »
Juliette Decugis · Alicia Tsai · Ashwin Ganesh · Max Emerling · Laurent El Ghaoui -
2022 : On the Abilities of Mathematical Extrapolation with Implicit Models »
Juliette Decugis · Max Emerling · Ashwin Ganesh · Alicia Tsai · Laurent El Ghaoui -
2021 Poster: Newton-LESS: Sparsification without Trade-offs 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 Log-Partition 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 Walk-Sum Analysis »
Venkat Chandrasekaran · Jason K Johnson · Alan S Willsky