An official website of the United States government
We explore the connection between outlier-robust high-dimensional statistics and non-convex optimization in the presence of sparsity constraints, with a focus on the fundamental tasks of robust sparse mean estimation and robust sparse PCA. We develop novel and simple optimization formulations for these problems such that any approximate stationary point of the associated optimization problem yields a near-optimal solution for the underlying robust estimation task. As a corollary, we obtain that any first-order method that efficiently converges to stationarity yields an efficient algorithm for these tasks. The obtained algorithms are simple, practical, and succeed under broader distributional assumptions compared to prior work.
more »
« less
A Generalized Formulation for Group Selection via ADMM
Abstract This paper studies a statistical learning model where the model coefficients have a pre-determined non-overlapping group sparsity structure. We consider a combination of a loss function and a regularizer to recover the desired group sparsity patterns, which can embrace many existing works. We analyze directional stationary solutions of the proposed formulation, obtaining a sufficient condition for a directional stationary solution to achieve optimality and establishing a bound of the distance from the solution to a reference point. We develop an efficient algorithm that adopts an alternating direction method of multiplier (ADMM), showing that the iterates converge to a directional stationary solution under certain conditions. In the numerical experiment, we implement the algorithm for generalized linear models with convex and nonconvex group regularizers to evaluate the model performance on various data types, noise levels, and sparsity settings.
more »
« less
- PAR ID:
- 10511155
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Journal of Scientific Computing
- Volume:
- 100
- Issue:
- 1
- ISSN:
- 0885-7474
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We explore the connection between outlier-robust high-dimensional statistics and non-convex optimization in the presence of sparsity constraints, with a focus on the fundamental tasks of robust sparse mean estimation and robust sparse PCA. We develop novel and simple optimization formulations for these problems such that any approximate stationary point of the associated optimization problem yields a near-optimal solution for the underlying robust estimation task. As a corollary, we obtain that any first-order method that efficiently converges to stationarity yields an efficient algorithm for these tasks.1 The obtained algorithms are simple, practical, and succeed under broader distributional assumptions compared to prior work.more » « less
-
We explore the connection between outlier-robust high-dimensional statistics and non-convex optimization in the presence of sparsity constraints, with a focus on the fundamental tasks of robust sparse mean estimation and robust sparse PCA. We develop novel and simple optimization formulations for these problems such that any approximate stationary point of the associated optimization problem yields a near-optimal solution for the underlying robust estimation task. As a corollary, we obtain that any first-order method that efficiently converges to stationarity yields an efficient algorithm for these tasks. The obtained algorithms are simple, practical, and succeed under broader distributional assumptions compared to prior work.more » « less
-
Abstract This paper introduces new solvers for efficiently computing solutions to large-scale inverse problems with group sparsity regularization, including both non-overlapping and overlapping groups. Group sparsity regularization refers to a type of structured sparsity regularization, where the goal is to impose additional structure in the regularization process by assigning variables to predefined groups that may represent graph or network structures. Special cases of group sparsity regularization includeℓ1and isotropic total variation regularization. In this work, we develop hybrid projection methods based on flexible Krylov subspaces, where we first recast the group sparsity regularization term as a sequence of 2-norm penalization terms using adaptive regularization matrices in an iterative reweighted norm fashion. Then we exploit flexible preconditioning techniques to efficiently incorporate the weight updates. The main advantages of these methods are that they are computationally efficient (leveraging the advantages of flexible methods), they are general (and therefore very easily adaptable to new regularization term choices), and they are able to select the regularization parameters automatically and adaptively (exploiting the advantages of hybrid methods). Extensions to multiple regularization terms and solution decomposition frameworks (e.g. for anomaly detection) are described, and a variety of numerical examples demonstrate both the efficiency and accuracy of the proposed approaches compared to existing solvers.more » « less
-
Abstract This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the “$$\ell _0$$ -path” where the discontinuous$$\ell _0$$ -function provides the exact sparsity count; the “$$\ell _1$$ -path” where the$$\ell _1$$ -function provides a convex surrogate of sparsity count; and the “capped$$\ell _1$$ -path” where the nonconvex nondifferentiable capped$$\ell _1$$ -function aims to enhance the$$\ell _1$$ -approximation. Serving different purposes, each of these three formulations is different from each other, both analytically and computationally. Our results deepen the understanding of (old and new) properties of the associated paths, highlight the pros, cons, and tradeoffs of these sparse optimization models, and provide numerical evidence to support the practical superiority of the capped$$\ell _1$$ -path. Our study of the capped$$\ell _1$$ -path is interesting in its own right as the path pertains to computable directionally stationary (= strongly locally minimizing in this context, as opposed to globally optimal) solutions of a parametric nonconvex nondifferentiable optimization problem. Motivated by classical parametric quadratic programming theory and reinforced by modern statistical learning studies, both casting an exponential perspective in fully describing such solution paths, we also aim to address the question of whether some of them can be fully traced in strongly polynomial time in the problem dimensions. A major conclusion of this paper is that a path of directional stationary solutions of the capped$$\ell _1$$ -regularized problem offers interesting theoretical properties and practical compromise between the$$\ell _0$$ -path and the$$\ell _1$$ -path. Indeed, while the$$\ell _0$$ -path is computationally prohibitive and greatly handicapped by the repeated solution of mixed-integer nonlinear programs, the quality of$$\ell _1$$ -path, in terms of the two criteria—loss and sparsity—in the estimation objective, is inferior to the capped$$\ell _1$$ -path; the latter can be obtained efficiently by a combination of a parametric pivoting-like scheme supplemented by an algorithm that takes advantage of the Z-matrix structure of the loss function.more » « less
