Author name cluster

Laurent Ghaoui

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

1 author row

NeurIPS Conference 2012 Conference Paper

Recovery of Sparse Probability Measures via Convex Programming

Mert Pilanci
Laurent Ghaoui
Venkat Chandrasekaran

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.

PDF Details

NeurIPS Conference 2011 Conference Paper

Large-Scale Sparse Principal Component Analysis with Application to Text Data

Youwei Zhang
Laurent Ghaoui

Sparse PCA provides a linear combination of small number of features that maximizes variance across data. Although Sparse PCA has apparent advantages compared to PCA, such as better interpretability, it is generally thought to be computationally much more expensive. In this paper, we demonstrate the surprising fact that sparse PCA can be easier than PCA in practice, and that it can be reliably applied to very large data sets. This comes from a rigorous feature elimination pre-processing result, coupled with the favorable fact that features in real-life data typically have exponentially decreasing variances, which allows for many features to be eliminated. We introduce a fast block coordinate ascent algorithm with much better computational complexity than the existing first-order ones. We provide experimental results obtained on text corpora involving millions of documents and hundreds of thousands of features. These results illustrate how Sparse PCA can help organize a large corpus of text data in a user-interpretable way, providing an attractive alternative approach to topic models.

PDF Details

NeurIPS Conference 2008 Conference Paper

A Convex Upper Bound on the Log-Partition Function for Binary Distributions

Laurent Ghaoui
Assane Gueye

We consider the problem of bounding from above the log-partition function corresponding to second-order Ising models for binary distributions. We introduce a new bound, the cardinality bound, which can be computed via convex optimization. The corresponding error on the logpartition function is bounded above by twice the distance, in model parameter space, to a class of "standard" Ising models, for which variable inter-dependence is described via a simple mean field term. In the context of maximum-likelihood, using the new bound instead of the exact log-partition function, while constraining the distance to the class of standard Ising models, leads not only to a good approximation to the log-partition function, but also to a model that is parsimonious, and easily interpretable. We compare our bound with the log-determinant bound introduced by Wainwright and Jordan (2006), and show that when the l1 -norm of the model parameter vector is small enough, the latter is outperformed by the new bound.

PDF Details

NeurIPS Conference 2008 Conference Paper

An Homotopy Algorithm for the Lasso with Online Observations

Pierre Garrigues
Laurent Ghaoui

It has been shown that the problem of $\ell_1$-penalized least-square regression commonly referred to as the Lasso or Basis Pursuit DeNoising leads to solutions that are sparse and therefore achieves model selection. We propose in this paper an algorithm to solve the Lasso with online observations. We introduce an optimization problem that allows us to compute an homotopy from the current solution to the solution after observing a new data point. We compare our method to Lars and present an application to compressed sensing with sequential observations. Our approach can also be easily extended to compute an homotopy from the current solution to the solution after removing a data point, which leads to an efficient algorithm for leave-one-out cross-validation.

PDF Details

NeurIPS Conference 2004 Conference Paper

A Direct Formulation for Sparse PCA Using Semidefinite Programming

Alexandre d'Aspremont
Laurent Ghaoui
Michael Jordan
Gert Lanckriet

We examine the problem of approximating, in the Frobenius-norm sense, a positive, semidefinite symmetric matrix by a rank-one matrix, with an upper bound on the cardinality of its eigenvector. The problem arises in the decomposition of a covariance matrix into sparse factors, and has wide applications ranging from biology to finance. We use a modifica- tion of the classical variational representation of the largest eigenvalue of a symmetric matrix, where cardinality is constrained, and derive a semidefinite programming based relaxation for our problem.

PDF Details

NeurIPS Conference 2003 Conference Paper

Robustness in Markov Decision Problems with Uncertain Transition Matrices

Arnab Nilim
Laurent Ghaoui

Optimal solutions to Markov Decision Problems (MDPs) are very sen- sitive with respect to the state transition probabilities. In many practi- cal problems, the estimation of those probabilities is far from accurate. Hence, estimation errors are limiting factors in applying MDPs to real- world problems. We propose an algorithm for solving ﬁnite-state and ﬁnite-action MDPs, where the solution is guaranteed to be robust with respect to estimation errors on the state transition probabilities. Our al- gorithm involves a statistically accurate yet numerically efﬁcient repre- sentation of uncertainty, via Kullback-Leibler divergence bounds. The worst-case complexity of the robust algorithm is the same as the origi- nal Bellman recursion. Hence, robustness can be added at practically no extra computing cost.

PDF Details

NeurIPS Conference 2002 Conference Paper

Robust Novelty Detection with Single-Class MPM

Laurent Ghaoui
Michael Jordan
Gert Lanckriet

the "single-class minimax probabil(cid: 173) In this paper we consider the problem of novelty detection, pre(cid: 173) senting an algorithm that aims to find a minimal region in input space containing a fraction 0: of the probability mass underlying a data set. This algorithm- ity machine (MPM)" - is built on a distribution-free methodology that minimizes the worst-case probability of a data point falling outside of a convex set, given only the mean and covariance matrix of the distribution and making no further distributional assump(cid: 173) tions. We present a robust approach to estimating the mean and covariance matrix within the general two-class MPM setting, and show how this approach specializes to the single-class problem. We provide empirical results comparing the single-class MPM to the single-class SVM and a two-class SVM method.

PDF Details

NeurIPS Conference 2001 Conference Paper

Minimax Probability Machine

Gert Lanckriet
Laurent Ghaoui
Chiranjib Bhattacharyya
Michael Jordan

When constructing a classifier, the probability of correct classifi(cid: 173) cation of future data points should be maximized. In the current paper this desideratum is translated in a very direct way into an optimization problem, which is solved using methods from con(cid: 173) vex optimization. We also show how to exploit Mercer kernels in this setting to obtain nonlinear decision boundaries. A worst-case bound on the probability of misclassification of future data is ob(cid: 173) tained explicitly.

PDF Details