Dynamic Sparse Training finds efficient sparse networks from scratch.
problem Finding efficient sparse neural networks.
method Jointly optimizes network parameters and sparsity with trainable thresholds.
result Achieves state-of-the-art performance with minimal performance loss.
We introduce a new algorithm, called adaptive sparse backfitting algorithm, for solving high dimensional Sparse Additive Model (SpAM) utilizing symmetric, non-negative definite smoothers. Unlike the previous sparse backfitting algorithm, our method is essentially a block coordinate descent algorithm that guarantees to …
Novel algorithm recovers sparse parameters in high-dimensional data with constant corruption.
problem Sparse regression with high dimensionality and constant fraction of corruptions.
method Robust Iterative Hard Thresholding, filtering algorithm for outlier removal.
result Near information-theoretically optimal error guarantee with sub-linear sample complexity.
New algorithm reduces runtime for robust sparse mean estimation.
problem Efficiently estimating mean from corrupted data with sparse constraints.
method Subquadratic time algorithm using poly(k, log d, 1/ε) samples.
result First subquadratic time algorithm for robust sparse mean estimation.
New combinatorial method for sparse PCA works beyond spiked identity model.
problem Sparse PCA under general covariance matrices.
method Combinatorial truncated power method with global convergence guarantee.
result First combinatorial sparse PCA method provably successful for general covariance matrices.
New method connects Sparse PCA and Sparse Linear Regression.
problem Sparse Principal Component Analysis and Sparse Linear Regression.
method Transforming a solver for Sparse Linear Regression into an algorithm for Sparse Principal Component Analysis.
result The derived SPCA algorithm achieves near state-of-the-art guarantees for testing and support recovery.
This paper proposes a new algorithm for multiple sparse regression in high dimensions, where the task is to estimate the support and values of several (typically related) sparse vectors from a few noisy linear measurements. Our algorithm is a "forward-backward" greedy procedure that -- uniquely -- operates on two disti…
New algorithms recover sparse tensor principal components efficiently.
problem Recovering sparse tensor principal components from noisy data.
method Family of algorithms interpolating between polynomial-time and exhaustive search, tailored for sparse and highly sparse regimes.
result Our algorithms recover sparse vectors for signal-to-noise ratios beyond previous limits, with time complexity ildeO(np+t). Rotation invariant algorithms fail on sparse problems even with noise.
problem Rotation invariant algorithms' suboptimality in sparse linear problems with noise.
method Lower bounds and trajectory analysis of optimization algorithms.
result Rotation invariant algorithms are suboptimal even with noise and many examples.
Four algorithms improve sparse tensor BR1Approx with theoretical guarantees.
problem Sparse tensor best rank-1 approximation.
method Four approximation algorithms exploiting multilinearity and sparsity.
result Theoretical worst-case approximation lower bounds for all algorithms.
Efficient algorithm for sparse PCA reduces data complexity.
problem Sparse PCA for high-dimensional data with non-convex optimization issues.
method Convex FPS formulation, gradient-based optimization, online learning extension.
result Explicit bounds on optimization error and statistical accuracy.
We propose a parallelizable sparse inverse formulation Gaussian process (SpInGP) for temporal models. It uses a sparse precision GP formulation and sparse matrix routines to speed up the computations. Due to the state-space formulation used in the algorithm, the time complexity of the basic SpInGP is linear, and becaus…
New algorithm recovers sparse measures in polynomial time.
problem Recovering sparse measures from Fourier moments.
method Polynomial-time recovery method inspired by mean-field theory.
result Improves upon convex relaxation methods in specific parameter regime.
Robustly estimates sparse data with corrupted outliers.
problem Adversarial corruption in high-dimensional sparse data.
method Iterative filtering using spectral techniques.
result Achieves near-optimal robustness guarantees.
We consider the high-dimensional sparse linear regression problem of accurately estimating a sparse vector using a small number of linear measurements that are contaminated by noise. It is well known that the standard cadre of computationally tractable sparse regression algorithms---such as the Lasso, Orthogonal Matchi…
Paper proposes a new method for sparse phase retrieval with fewer measurements.
problem Sparse phase retrieval in various fields.
method Stochastic alternating minimizing method (StormSpar) with HTP algorithm.
result The method recovers sparse signals from fewer measurements than existing methods.
Sparse coding is a basic task in many fields including signal processing, neuroscience and machine learning where the goal is to learn a basis that enables a sparse representation of a given set of data, if one exists. Its standard formulation is as a non-convex optimization problem which is solved in practice by heuri…
Sparse PCA algorithm improves upon existing methods with better guarantees.
problem Recovering sparse vectors from Gaussian samples with adversarial perturbations.
method New algorithm running in polynomial time with improved β threshold.
result Better guarantees than Covariance Thresholding for large t.
A new NMF variant tackles underdetermined problems with sparse and separable assumptions.
problem Underdetermined blind source separation, especially multispectral image unmixing.
method Sparse Separable Nonnegative Matrix Factorization (SSNMF) combining separability and sparsity assumptions. Algorithm based on SNPA and sparse nonnegative least squares.
result In noiseless settings, the algorithm recovers true underlying sources.
New algorithm clusters sparse data effectively.
problem Challenges in clustering sparse data.
method Deterministic Information Bottleneck framework for joint feature weighting and clustering.
result Demonstrated effectiveness on real-world genomics data.
TSN improves sparse signal recovery with less complexity.
problem Sparse regression problem of recovering sparse signals from measurements.
method Tree search algorithm driven by deep neural network with pruning.
result TSN outperforms conventional methods in various sensing matrices.
In this paper, we address the challenging problem of selecting tuning parameters for high-dimensional sparse regression. We propose a simple and computationally efficient method, called path thresholding (PaTh), that transforms any tuning parameter-dependent sparse regression algorithm into an asymptotically tuning-fre…
Efficiently approximates Sparse PCA with significant speedups and minor error.
problem Sparse Principal Component Analysis (Sparse PCA) is NP-hard and computationally expensive.
method Approximates the covariance matrix with block-diagonal form, solves sub-problems in each block, and reconstructs the solution.
result Significant computational speedups with minor additive error.
New algorithm improves sparse-view tomography without needing ground-truth data.
problem Poor image reconstructions with sparse projections and non-uniform sensors.
method Unsupervised deep learning with CNN and STN modules.
result Significantly outperforms filtered backprojection in sparse-view scenarios.
ProSper learns data components with non-standard priors and superpositions.
problem Learning complex data components with non-standard priors and superpositions.
method Probabilistic algorithms for sparse coding with non-standard priors and superpositions.
result Library supports scalable and parallelizable dictionary learning for large-scale applications.
Paper studies Frank-Wolfe algorithm for solving sparse reconstruction problems.
problem Sparse reconstruction problem
method Frank-Wolfe algorithm applied to quasi-incoherent dictionaries
result Algorithm converges exponentially fast for quasi-incoherent dictionaries
Regression algorithm uses quantum annealer for sparse inference in lattice QCD simulations.
problem Improving prediction accuracy in lattice QCD simulations.
method Proposes a regression algorithm that combines sparse inference with a D-Wave quantum annealer.
result Quantum annealer improves prediction performance in lattice QCD simulations.
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…
msPCA solves sparse PCA for multiple components efficiently.
problem Sparse principal component analysis with multiple components.
method Alternating maximization algorithm for sparse loading vectors, with orthogonality or zero correlation constraints.
result Achieves high variance explained with sparse components and controlled feasibility violations.
Sparse optimization refers to an optimization problem involving the zero-norm in objective or constraints. In this paper, nonconvex approximation approaches for sparse optimization have been studied with a unifying point of view in DC (Difference of Convex functions) programming framework. Considering a common DC appro…
In this paper we formally analyse the use of sparse filtering algorithms to perform covariate shift adaptation. We provide a theoretical analysis of sparse filtering by evaluating the conditions required to perform covariate shift adaptation. We prove that sparse filtering can perform adaptation only if the conditional…
Efficient algorithm solves sparse nonconvex regression problems.
problem Sparse nonconvex square-root-loss regression problems.
method Proximal majorization-minimization (PMM) algorithm with sparse semismooth Newton method.
result Converges to a d-stationary point with Kurdyka-Łojasiewicz property.
New algorithm reduces sample complexity for sparse linear regression.
problem Sparse linear regression with correlated covariates and approximate dependencies.
method Polynomial-time algorithm that adapts the Lasso to tolerate approximate dependencies.
result Achieves near-optimal sample complexity for constant sparsity and ill-conditioned covariates.
Develops a privacy-preserving algorithm for sparse robust regression.
problem Privacy-preserving machine learning for sparse robust regression.
method Develops FRAPPE algorithm for non-smooth loss under differential privacy.
result Achieves better privacy and statistical accuracy trade-off.
Paper discusses new stochastic algorithms for sparse signal recovery.
problem Sparse signal recovery in medical imaging and remote sensing.
method Proposes and analyzes stochastic natural thresholding algorithms.
result Demonstrates improved performance of StoNT algorithms.
Study shows inefficiency of sparse linear regression learning with fewer than Ω(k^2) samples.
problem Efficiency of sparse linear regression learning with minimal samples.
method Reduction to sparse PCA problems and lower bounds.
result Efficient algorithms for sparse linear regression require at least Ω(k^2) samples.
Sparse GCA finds linear relationships in multiple datasets, using gradient descent.
problem Finding linear relationships across multiple datasets with sparse loading vectors.
method Formulated as generalized eigenvalue problems, used a thresholded gradient descent algorithm.
result Proposed algorithm yields tight estimation error bounds and demonstrates effectiveness on synthetic datasets.
DeepMP improves non-negative sparse recovery performance.
problem Recovering non-negative sparse signals with high coherence.
method Reformulated non-negative matching pursuit as a deep neural network.
result DeepMP yields significant improvement in exact recovery performance.
Proposes a Monte-Carlo method for sparse signal reconstruction.
problem Reconstructing sparse signals in high-dimensional settings.
method Greedy Monte-Carlo (GMC) search algorithm.
result GMC can achieve perfect reconstruction in undersampling situations.
Spectral clustering with edge counting detects communities in sparse models.
problem Detecting communities in sparse latent space models.
method Spectral clustering followed by edge counting.
result Algorithm achieves consistency and optimality for a broad class of models.
Faster, better sparse model estimation for large datasets.
problem Sparse model estimation for large datasets with millions of samples and features.
method Coordinate descent, working sets, Anderson acceleration.
result Significantly faster and more efficient than state-of-the-art algorithms.
We study a data model in which the data matrix D can be expressed as D = L + S + C, where L is a low rank matrix, S an element-wise sparse matrix and C a matrix whose non-zero columns are outlying data points. To date, robust PCA algorithms have solely considered models with either S or C, but not both. As such, existi…
Solves community detection in sparse hypergraphs above a threshold.
problem Community detection in sparse hypergraphs.
method Generalization of Massoulié's method for sparse random graphs to random hypergraphs.
result Above the threshold, a spectral algorithm constructs a partition correlated with the true partition.
Sparse learning speeds up neural network training without sacrificing accuracy.
problem Training deep neural networks efficiently while maintaining performance.
method Sparse momentum algorithm that redistributes and grows weights based on momentum magnitude.
result State-of-the-art sparse performance on various datasets with up to 5.61x faster training.
A fast randomized PCA for sparse data, up to 9.1X faster.
problem Processing large sparse data efficiently for dimension reduction.
method Fast randomized PCA algorithm optimized for sparse data.
result Up to 9.1X faster than basic rPCA algorithm without accuracy loss.
The performance of sparse signal recovery from noise corrupted, underdetermined measurements can be improved if both sparsity and correlation structure of signals are exploited. One typical correlation structure is the intra-block correlation in block sparse signals. To exploit this structure, a framework, called block…
The paper provides entrywise bounds for Sparse PCA, improving upon previous results.
problem Sparse Principal Component Analysis (PCA) recovery error characterization in spectral or Frobenius norms.
method Entrywise ℓ2,∞ bounds for Sparse PCA under general high-dimensional subgaussian design, using sparsistent algorithms. result Improved entrywise bounds for Sparse PCA, finer characterization of estimation error.
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.