Search ResultsShowing 1-6 of 6
-
arXiv:2411.11722 (Published 2024-11-18)
Solving convex QPs with structured sparsity under indicator conditions
We study convex optimization problems where disjoint blocks of variables are controlled by binary indicator variables that are also subject to conditions, e.g., cardinality. Several classes of important examples can be formulated in such a way that both the objective and the constraints are separable convex quadratics. We describe a family of polynomial-time approximation algorithms and negative complexity results.
-
arXiv:2308.08852 (Published 2023-08-17)
Learning the hub graphical Lasso model with the structured sparsity via an efficient algorithm
Comments: 28 pages,3 figuresGraphical models have exhibited their performance in numerous tasks ranging from biological analysis to recommender systems. However, graphical models with hub nodes are computationally difficult to fit, particularly when the dimension of the data is large. To efficiently estimate the hub graphical models, we introduce a two-phase algorithm. The proposed algorithm first generates a good initial point via a dual alternating direction method of multipliers (ADMM), and then warm starts a semismooth Newton (SSN) based augmented Lagrangian method (ALM) to compute a solution that is accurate enough for practical tasks. The sparsity structure of the generalized Jacobian ensures that the algorithm can obtain a nice solution very efficiently. Comprehensive experiments on both synthetic data and real data show that it obviously outperforms the existing state-of-the-art algorithms. In particular, in some high dimensional tasks, it can save more than 70\% of the execution time, meanwhile still achieves a high-quality estimation.
-
arXiv:1507.05367 (Published 2015-07-20)
Structured Sparsity: Discrete and Convex approaches
Comments: 30 pages, 18 figuresCompressive sensing (CS) exploits sparsity to recover sparse or compressible signals from dimensionality reducing, non-adaptive sensing mechanisms. Sparsity is also used to enhance interpretability in machine learning and statistics applications: While the ambient dimension is vast in modern data analysis problems, the relevant information therein typically resides in a much lower dimensional space. However, many solutions proposed nowadays do not leverage the true underlying structure. Recent results in CS extend the simple sparsity idea to more sophisticated {\em structured} sparsity models, which describe the interdependency between the nonzero components of a signal, allowing to increase the interpretability of the results and lead to better recovery performance. In order to better understand the impact of structured sparsity, in this chapter we analyze the connections between the discrete models and their convex relaxations, highlighting their relative advantages. We start with the general group sparse model and then elaborate on two important special cases: the dispersive and the hierarchical models. For each, we present the models in their discrete nature, discuss how to solve the ensuing discrete problems and then describe convex relaxations. We also consider more general structures as defined by set functions and present their convex proxies. Further, we discuss efficient optimization solutions for structured sparsity problems and illustrate structured sparsity in action via three applications.
-
Structured Sparsity via Alternating Direction Methods
Journal: Journal of Machine Learning Research 13 (2012) 1435-1468Keywords: alternating direction methods, structured sparsity, adopted sparsity-inducing regularization terms, high dimensional feature spaceTags: journal articleWe consider a class of sparse learning problems in high dimensional feature space regularized by a structured sparsity-inducing norm which incorporates prior knowledge of the group structure of the features. Such problems often pose a considerable challenge to optimization algorithms due to the non-smoothness and non-separability of the regularization term. In this paper, we focus on two commonly adopted sparsity-inducing regularization terms, the overlapping Group Lasso penalty $l_1/l_2$-norm and the $l_1/l_\infty$-norm. We propose a unified framework based on the augmented Lagrangian method, under which problems with both types of regularization and their variants can be efficiently solved. As the core building-block of this framework, we develop new algorithms using an alternating partial-linearization/splitting technique, and we prove that the accelerated versions of these algorithms require $O(\frac{1}{\sqrt{\epsilon}})$ iterations to obtain an $\epsilon$-optimal solution. To demonstrate the efficiency and relevance of our algorithms, we test them on a collection of data sets and apply them to two real-world problems to compare the relative merits of the two norms.
-
Convex and Network Flow Optimization for Structured Sparsity
Comments: to appear in the Journal of Machine Learning Research (JMLR)Journal: Journal of Machine Learning Research 12 (2011) 2681?2720Keywords: network flow optimization, structured sparsity, quadratic min-cost flow problem, cur matrix factorization, accelerated proximal gradient methodsTags: journal articleWe consider a class of learning problems regularized by a structured sparsity-inducing norm defined as the sum of l_2- or l_infinity-norms over groups of variables. Whereas much effort has been put in developing fast optimization techniques when the groups are disjoint or embedded in a hierarchy, we address here the case of general overlapping groups. To this end, we present two different strategies: On the one hand, we show that the proximal operator associated with a sum of l_infinity-norms can be computed exactly in polynomial time by solving a quadratic min-cost flow problem, allowing the use of accelerated proximal gradient methods. On the other hand, we use proximal splitting techniques, and address an equivalent formulation with non-overlapping groups, but in higher dimension and with additional constraints. We propose efficient and scalable algorithms exploiting these two strategies, which are significantly faster than alternative approaches. We illustrate these methods with several problems such as CUR matrix factorization, multi-task learning of tree-structured dictionaries, background subtraction in video sequences, image denoising with wavelets, and topographic dictionary learning of natural image patches.
-
arXiv:math/0611498 (Published 2006-11-16)
A note on the representation of positive polynomials with structured sparsity
Comments: 4 pagesWe consider real polynomials in finitely many variables. Let the variables consist of finitely many blocks that are allowed to overlap in a certain way. Let the solution set of a finite system of polynomial inequalities be given where each inequality involves only variables of one block. We investigate polynomials that are positive on such a set and sparse in the sense that each monomial involves only variables of one block. In particular, we derive a short and direct proof for Lasserre's theorem of the existence of sums of squares certificates respecting the block structure. The motivation for the results can be found in the literature and stems from numerical methods using semidefinite programming to simulate or control discrete-time behaviour of systems.