This paper addresses the problem of sparsity penalized least squares for applications in sparse signal processing, e.g. sparse deconvolution. This paper aims to induce sparsity more strongly than L1 norm regularization, while avoiding non-convex optimization. For this purpose, this paper describes the design and use of…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “sparse convex optimization”
Convex optimization with sparsity-promoting convex regularization is a standard approach for estimating sparse signals in noise. In order to promote sparsity more strongly than convex regularization, it is also standard practice to employ non-convex optimization. In this paper, we take a third approach. We utilize a no…
New methods solve sparse estimation robustly, even with outliers.
problem Sparse estimation in high-dimensional data with outliers.
method Non-convex optimization formulations for robust sparse mean estimation and PCA.
result Any approximate stationary point yields near-optimal solutions.
New guarantees for Group LASSO in sparse convex optimization.
problem Sparse convex optimization with vector-valued features.
method Group LASSO regularization and analysis of gradient norms.
result Group LASSO selects the same features as Orthogonal Matching Pursuit.
Paper proposes a working set algorithm for non-convex sparse regression with provable convergence.
problem Estimating sparse linear models from high-dimensional data using non-convex regularizers.
method FireWorks algorithm based on non-convex reformulation and leveraging residual geometry.
result Convergence to a stationary point of the full problem with provable guarantees.
The popular Lasso approach for sparse estimation can be derived via marginalization of a joint density associated with a particular stochastic model. A different marginalization of the same probabilistic model leads to a different non-convex estimator where hyperparameters are optimized. Extending these arguments to pr…
New DP optimization methods for sparse gradients, improving on existing algorithms.
problem Differentially private optimization with sparse gradients in high-dimensional settings.
method Improved bounds for mean estimation, pure- and approximate-DP algorithms for stochastic convex optimization.
result First nearly dimension-independent rates for DP optimization with sparse gradients.
Sparse regression models are increasingly prevalent due to their ease of interpretability and superior out-of-sample performance. However, the exact model of sparse regression with an constraint restricting the support of the estimators is a challenging (\NP-hard) non-convex optimization problem. In this paper…
In this work we propose to fit a sparse logistic regression model by a weakly convex regularized nonconvex optimization problem. The idea is based on the finding that a weakly convex function as an approximation of the pseudo norm is able to better induce sparsity than the commonly used norm. For a cl…
Efficiently finds sparse solutions to max-plus equations for convex regression.
problem Finding sparse solutions to max-plus equations for convex multivariate regression.
method Polynomial-time algorithm for sparse approximate solutions.
result Optimal piecewise-linear fitting with minimum number of regions.
Sparse matrices are favorable objects in machine learning and optimization. When such matrices are used, in place of dense ones, the overall complexity requirements in optimization can be significantly reduced in practice, both in terms of space and run-time. Prompted by this observation, we study a convex optimization…
In this letter, we address sparse signal recovery using spike and slab priors. In particular, we focus on a Bayesian framework where sparsity is enforced on reconstruction coefficients via probabilistic priors. The optimization resulting from spike and slab prior maximization is known to be a hard non-convex problem, a…
Sparse Convex Biclusteringstat.ML
Sparse Convex Biclustering improves accuracy and robustness in high-dimensional datasets.
problem Challenges in clustering rows and columns of large-scale datasets due to noise and computational complexity.
method Sparse Convex Biclustering (SpaCoBi) using convex optimization and stability-based tuning.
result Significantly outperforms state-of-the-art methods in accuracy for high-dimensional datasets.
Paper reveals hidden convexities in deep learning models using sparse signal processing.
problem Non-convex loss functions in deep learning models complicate optimization and theoretical understanding.
method Developed convex equivalences of ReLU NNs and their connections to sparse signal processing models.
result Recent research has uncovered hidden convexities in certain NN architectures, notably two-layer ReLU networks and other architectures.
Convex Codingcs.LG
Inspired by recent work on convex formulations of clustering (Lashkari & Golland, 2008; Nowozin & Bakir, 2008) we investigate a new formulation of the Sparse Coding Problem (Olshausen & Field, 1997). In sparse coding we attempt to simultaneously represent a sequence of data-vectors sparsely (i.e. sparse approximation (…
Novel approximation hierarchy for sparse quadratic programs.
problem Sparse Quadratic Programs with Cardinality Constraints.
method Exploits rank-dominating eigenvectors for min-max optimization over binary variables.
result Efficient screening of nonzero elements with scalable optimization algorithms.
The paper shows that g-convex functions on manifolds are sparse.
problem Characterizing and understanding the sparseness of g-convex functions.
method Established criteria for g-convexity and used them to prove sparseness results.
result Most g-convex functions on compact manifolds have few critical points.
We propose a DC proximal Newton algorithm for solving nonconvex regularized sparse learning problems in high dimensions. Our proposed algorithm integrates the proximal Newton algorithm with multi-stage convex relaxation based on the difference of convex (DC) programming, and enjoys both strong computational and statist…
Signal processing is rich in inherently continuous and often nonlinear applications, such as spectral estimation, optical imaging, and super-resolution microscopy, in which sparsity plays a key role in obtaining state-of-the-art results. Coping with the infinite dimensionality and non-convexity of these problems typica…
Most learning methods with rank or sparsity constraints use convex relaxations, which lead to optimization with the nuclear norm or the -norm. However, several important learning applications cannot benefit from this approach as they feature these convex norms as constraints in addition to the non-convex rank a…
A fast sketching algorithm solves regularized least squares problems efficiently.
problem Solving large-scale optimization problems with convex or nonconvex regularization.
method Sketching for Regularized Optimization (SRO) algorithm that generates a sketch of the original data matrix and solves the sketched problem.
result General theoretical results for the approximation error between the original and sketched problems, including minimax rates for sparse signal estimation.
Unified method for simultaneous denoising and clustering.
problem Clustering noisy signals.
method Sparse convex wavelet clustering with fusion and group-sparse penalties.
result Unified approach that denoises and clusters simultaneously.
Sparse principal component analysis (PCA) is an important technique for dimensionality reduction of high-dimensional data. However, most existing sparse PCA algorithms are based on non-convex optimization, which provide little guarantee on the global convergence. Sparse PCA algorithms based on a convex formulation, for…
Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descenteess.SP
Paper studies early-stopped mirror descent for noisy sparse phase retrieval.
problem Recovering a sparse signal from noisy quadratic measurements.
method Early-stopped mirror descent with hyperbolic entropy mirror map.
result Achieves nearly minimax-optimal rate of convergence for -sparse signals.
Many high dimensional sparse learning problems are formulated as nonconvex optimization. A popular approach to solve these nonconvex optimization problems is through convex relaxations such as linear and semidefinite programming. In this paper, we study the statistical limits of convex relaxations. Particularly, we con…
Convex optimization refines neural network training, improving model performance and reducing hyperparameter sensitivity.
problem Training deep neural networks using non-convex optimization methods often leads to suboptimal solutions and requires extensive tuning.
method Formulate neural network training as convex programs with regularization terms, leveraging sparse recovery models and semi-infinite programming theory.
result Convex models can achieve global optima and outperform traditional non-convex methods, with improved robustness to hyperparameters.
Study iterative regularization for linear models with convex bias, improving robust sparse recovery.
problem Improving robust sparse recovery with iterative regularization for linear models.
method Primal-dual gradient approach, analyzing convergence in presence of noise, combining regularization and optimization.
result Theoretical results show state-of-the-art performances with computational speed-ups.
Paper tackles non-convex optimization for higher moments in portfolio management.
problem Complexity of higher moments in optimization problems.
method Method of successive convex approximation.
result Solves mean-variance-skewness problem using non-convex optimization.
Proposes differentiable and sparse top-k operators for neural networks.
problem Discontinuity of top-k operator makes it unsuitable for end-to-end training with backpropagation.
method Formulates top-k as a linear program over permutahedron, introduces p-norm regularization, and uses isotonic optimization.
result Successfully applied to neural network pruning, fine-tuning, and routing.
Multi-task sparse feature learning aims to improve the generalization performance by exploiting the shared features among tasks. It has been successfully applied to many applications including computer vision and biomedical informatics. Most of the existing multi-task sparse feature learning algorithms are formulated a…
We study sparse approximate solutions to convex optimization problems. It is known that in many engineering applications researchers are interested in an approximate solution of an optimization problem as a linear combination of elements from a given system of elements. There is an increasing interest in building such …
New FGSPCA method captures grouping and sparse structures in PCA without prior info.
problem Capture grouping and sparse structures in PCA without prior info.
method Truncated regularization with alternating algorithm.
result FGSPCA method reduces model complexity and increases interpretability.
Paper solves high-order portfolio optimization with cardinality constraint.
problem Solving non-convex cardinality constrained high-order portfolio optimization.
method Transformed cardinality constraint into penalty term, proposed pDCA, pDCAe, and SCA algorithms.
result Proposed algorithms achieve high utility and sparse solutions efficiently.
This paper is a follow up to the previous author's paper on convex optimization. In that paper we began the process of adjusting greedy-type algorithms from nonlinear approximation for finding sparse solutions of convex optimization problems. We modified there three the most popular in nonlinear approximation in Banach…
This paper investigates the problem of recovering missing samples using methods based on sparse representation adapted especially for image signals. Instead of -norm or Mean Square Error (MSE), a new perceptual quality measure is used as the similarity criterion between the original and the reconstructed images. T…
The CUR decomposition provides an approximation of a matrix that has low reconstruction error and that is sparse in the sense that the resulting approximation lies in the span of only a few columns of . In this regard, it appears to be similar to many sparse PCA methods. However, CUR takes a randomized algorithm…
RO-TD learns sparse value functions efficiently.
problem Learning sparse value functions efficiently.
method RO-TD integrates off-policy convergent gradient TD methods and online convex regularization.
result RO-TD learns sparse value functions with low computational complexity.
A variety of representation learning approaches have been investigated for reinforcement learning; much less attention, however, has been given to investigating the utility of sparse coding. Outside of reinforcement learning, sparse coding representations have been widely used, with non-convex objectives that result in…
Sparse Convex Clusteringstat.ME
Convex clustering, a convex relaxation of k-means clustering and hierarchical clustering, has drawn recent attentions since it nicely addresses the instability issue of traditional nonconvex clustering methods. Although its computational and statistical properties have been recently studied, the performance of convex c…
PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Banditsstat.ML
PopArt efficiently solves sparse linear bandits with tighter recovery guarantees.
problem Sparse linear bandits where rewards depend on a few covariates.
method PopArt: a simple, computationally efficient sparse linear estimation method.
result Improved regret bounds compared to state-of-the-art algorithms.
Paper proposes a new method to separate low rank and sparse matrices without bias.
problem Recovering low rank and sparse matrices from measurements.
method Uses nonconvex regularizers and alternating proximal gradient descent.
result Error bounds for the algorithm applied to sparse optimization, matrix completion, and robust PCA.
New method for sparse kernel selection improves prediction accuracy.
problem Sparse Multiple Kernel Learning for binary classification.
method Alternating best response algorithm with semidefinite relaxations.
result Method outperforms state-of-the-art MKL approaches in prediction accuracy.
Sparse generalized eigenvalue problem (GEP) plays a pivotal role in a large family of high-dimensional statistical models, including sparse Fisher's discriminant analysis, canonical correlation analysis, and sufficient dimension reduction. Sparse GEP involves solving a non-convex optimization problem. Most existing met…
Recently, there has been focus on penalized log-likelihood covariance estimation for sparse inverse covariance (precision) matrices. The penalty is responsible for inducing sparsity, and a very common choice is the convex norm. However, the best estimator performance is not always achieved with this penalty. The …
New method smooths optimization for sparse regularization.
problem Non-smooth, non-convex optimization problems for sparsity.
method Overparameterization and smooth surrogate penalties.
result Surrogate objective has identical global and local minima.
Non-convex sparsity-inducing penalties have recently received considerable attentions in sparse learning. Recent theoretical investigations have demonstrated their superiority over the convex counterparts in several sparse learning settings. However, solving the non-convex optimization problems associated with non-conv…
New method improves structure learning on sparse graphs.
problem Structure learning on sparse directed acyclic graphs (DAGs).
method Bregman proximal gradient method to address non-convex, high-curvature problem.
result Significantly improved convergence and efficiency.
Picasso is a new library for sparse learning problems in R and Python.
problem Sparse learning problems in high-dimensional data analysis.
method Unified framework of pathwise coordinate optimization with efficient active set selection strategies.
result picasso can efficiently handle large-scale problems.