Convex Optimization with Applications in Sparse Multivariate Statistics

The main focus of this thesis is to build sparse statistical models central to several machine learning tasks. Parsimonious modeling in statistics seeks to balance the tradeoff between solution accuracy and the curse of dimensionality. From an optimization perspective, challenges emanate from the inherent non-convexity in these problems and the computational bottlenecks in traditional algorithms.;We first focus on capturing dependence relationships between variables in as sparse a manner as possible. Covariance selection seeks to estimate a covariance matrix by maximum likelihood while restricting the number of nonzero inverse covariance matrix coefficients. A single penalty parameter usually controls the tradeoff between log likelihood and sparsity in the inverse matrix. We describe an efficient algorithm for computing a full regularization path of solutions to this problem.;We next derive a semidefinite relaxation for the problem of computing generalized eigenvalues with a constraint on the cardinality of the corresponding eigenvector. We first use this result to produce a sparse variant of linear discriminant analysis and compare classification performance with greedy and thresholding approaches. We then use this relaxation to produce lower performance bounds on the subset selection problem.;Finally, we derive approximation algorithms for the nonnegative matrix factorization problem, i.e. the problem of factorizing a matrix as the product of two matrices with nonnegative coefficients. We form convex approximations of this problem which can be solved efficiently via first-order algorithms.