Iterative thresholding algorithms seek to optimize a differentiable objective function over a sparsity or rank constraint by alternating between gradient steps that reduce the objective, and thresholding steps that enforce the constraint. This work examines the choice of the thresholding operator, and asks whether it i…
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,695 papers · 148 categories
Trend · papers per month
48 results for “Iterative Hard Thresholding”
Guarantees sparse recovery for neural networks with iterative hard thresholding.
problem Recovering sparse network weights in neural networks.
method Structural properties of sparse network weights and iterative hard thresholding algorithm.
result Simple iterative hard thresholding algorithm recovers sparse network weights exactly using linear memory.
Improved iterative hard thresholding for faster, sparser solutions.
problem Finding sparser solutions without sacrificing runtime.
method Adaptive regularization framework applied to iterative hard thresholding.
result Returns solutions with sparsity , improving over existing methods.
New algorithm resists contamination in high-dimensional regression with optimal performance.
problem Adversarial and measurement errors in high-dimensional data.
method Adversarial Contamination-resistant Iterative Hard Thresholding (AC-IHT) algorithm.
result Achieves minimax near-optimal estimation and signal-adaptive support recovery.
Hard Thresholding Pursuit (HTP) is an iterative greedy selection procedure for finding sparse solutions of underdetermined linear systems. This method has been shown to have strong theoretical guarantee and impressive numerical performance. In this paper, we generalize HTP from compressive sensing to a generic problem …
AIHT improves online high-dimensional quantile regression by separating support discovery and refinement.
problem Online high-dimensional quantile regression with structural sparsity.
method Adaptive Iterative Hard Thresholding (AIHT) alternates stochastic updates with adaptive hard-thresholding steps.
result AIHT achieves logarithmic regret for the sliding-window objective in high-dimensional settings.
The use of M-estimators in generalized linear regression models in high dimensional settings requires risk minimization with hard constraints. Of the known methods, the class of projected gradient descent (also known as iterative hard thresholding (IHT)) methods is known to offer the fastest and most scalable sol…
We study --both in theory and practice-- the use of momentum motions in classic iterative hard thresholding (IHT) methods. By simply modifying plain IHT, we investigate its convergence behavior on convex optimization criteria with non-convex constraints, under standard assumptions. In diverse scenaria, we observe that …
Iterative hard thresholding (IHT) is a projected gradient descent algorithm, known to achieve state of the art performance for a wide range of structured estimation problems, such as sparse inference. In this work, we consider IHT as a solution to the problem of learning sparse discrete distributions. We study the hard…
Paper develops algorithms to maximize AUC in imbalanced classification.
problem Maximizing AUC in imbalanced classification problems.
method Developed stochastic hard thresholding algorithms to reformulate U-statistics as ERM.
result Proposed algorithm achieves linear convergence rate.
In this paper we consider regularized convex cone programming problems. In particular, we first propose an iterative hard thresholding (IHT) method and its variant for solving regularized box constrained convex programming. We show that the sequence generated by these methods converges to a local minimizer.…
Large-scale non-convex sparsity-constrained problems have recently gained extensive attention. Most existing deterministic optimization methods (e.g., GraSP) are not suitable for large-scale and high-dimensional problems, and thus stochastic optimization methods with hard thresholding (e.g., SVRGHT) become more attract…
Paper analyzes BIHT for noisy 1-bit CS, improving results with up to τ-fraction of incorrect measurements.
problem Estimating sparse vectors from noisy sign measurements in 1-bit compressed sensing.
method Binary Iterative Hard Thresholding (BIHT) algorithm, using Gaussian matrices and high-dimensional geometry analysis.
result BIHT provides estimates within ε+τ error with τ-fraction of incorrect measurements, maintaining universality of measurements.
In this paper, we consider the problem of compressed sensing where the goal is to recover almost all the sparse vectors using a small number of fixed linear measurements. For this problem, we propose a novel partial hard-thresholding operator that leads to a general family of iterative algorithms. While one extreme of …
On the Role of Normalization in Binary Iterative Hard Thresholding for 1-bit Compressed Sensingcs.IT
This paper resolves BIHT convergence, showing normalization is not necessary in noiseless settings but crucial for robustness.
problem Analyzing convergence and robustness of BIHT for 1-bit compressed sensing.
method Characterizes BIHT convergence and robustness, proving necessity of normalization for robustness under sign corruptions.
result Per-iteration normalization is not necessary for optimal recovery in noiseless settings but is crucial for robustness under sign corruptions.
Learning sparse generalized linear models with binary outcomes via iterative hard thresholdingmath.ST
New algorithm learns sparse GLMs for binary outcomes efficiently.
problem Sparse modeling of binary outcomes in high-dimensional data.
method Iterative hard thresholding algorithm (BIHT) for sparse GLMs.
result BIHT achieves statistical optimality for logistic regression.
Paper analyzes IHT's performance in sparse recovery problems.
problem Generalization performance of Iterative Hard Thresholding (IHT).
method Sparse generalization theory under algorithmic stability.
result IHT achieves convergence rates in sparse excess risk.
The robust PCA problem, wherein, given an input data matrix that is the superposition of a low-rank matrix and a sparse matrix, we aim to separate out the low-rank and sparse components, is a well-studied problem in machine learning. One natural question that arises is that, as in the inductive setting, if features are…
This paper is concerned with the hard thresholding operator which sets all but the largest absolute elements of a vector to zero. We establish a {\em tight} bound to quantitatively characterize the deviation of the thresholded solution from a given signal. Our theoretical result is universal in the sense that it ho…
Recovery of low-rank matrices from a small number of linear measurements is now well-known to be possible under various model assumptions on the measurements. Such results demonstrate robustness and are backed with provable theoretical guarantees. However, extensions to tensor recovery have only recently began to be st…
Novel active learning framework using sparse approximation for efficient model training.
problem Efficient model training with limited labeled data.
method Formulates batch active learning as sparsity-constrained discontinuous optimization problems, using greedy or proximal iterative hard thresholding algorithms.
result Achieves competitive performance with lower computational complexity across different settings.
Iterative Hard Thresholding (IHT) is a class of projected gradient descent methods for optimizing sparsity-constrained minimization models, with the best known efficiency and scalability in practice. As far as we know, the existing IHT-style methods are designed for sparse minimization in primal form. It remains open t…
In this paper we study the performance of the Projected Gradient Descent(PGD) algorithm for -constrained least squares problems that arise in the framework of Compressed Sensing. Relying on the Restricted Isometry Property, we provide convergence guarantees for this algorithm for the entire range of $0\leq p\…
Developed a new thresholding method that connects soft and hard thresholding.
problem Connecting soft and hard thresholding methods in data analysis.
method Scaled soft thresholding method with empirical scaling values.
result Found two sources of over-fitting in the scaled soft thresholding method.
Paper proposes a new sparse group k-max regularization for sparsity constraints.
problem Linear inverse problems with sparsity constraints are NP-hard.
method Sparse group k-max regularization, iterative soft thresholding algorithm.
result Approximates l0 norm more closely and enhances group-wise and in-group sparsity.
The problem of recovering a low -rank tensor is an extension of sparse recovery problem from the low dimensional space (matrix space) to the high dimensional space (tensor space) and has many applications in computer vision and graphics such as image inpainting and video inpainting. In this paper, we consider a new …
Iterative Log Thresholdingstat.ML
Sparse reconstruction approaches using the re-weighted l1-penalty have been shown, both empirically and theoretically, to provide a significant improvement in recovering sparse signals in comparison to the l1-relaxation. However, numerical optimization of such penalties involves solving problems with l1-norms in the ob…
ARHT algorithm improves sparsity guarantees in convex optimization.
problem Optimizing convex functions with sparsity constraints.
method Adaptively Regularized Hard Thresholding (ARHT) algorithm.
result ARHT achieves sparsity bound of γ=O(κ), matching theoretical limits.
Quadratic regression involves modeling the response as a (generalized) linear function of not only the features but also of quadratic terms . The inclusion of such higher-order "interaction terms" in regression often provides an easy way to increase accuracy in already-high-dimensional problem…
Binary Iterative Hard Thresholding converges with optimal number of 1-bit measurements.
problem Recovering sparse signals from 1-bit compressed measurements.
method Binary Iterative Hard Thresholding (BIHT) algorithm.
result BIHT converges with only O(k/ε) measurements, optimal for recovery.
We develop new stochastic gradient methods for efficiently solving sparse linear regression in a partial attribute observation setting, where learners are only allowed to observe a fixed number of actively chosen attributes per example at training and prediction times. It is shown that the methods achieve essentially a…
Modern scientific instruments produce vast amounts of data, which can overwhelm the processing ability of computer systems. Lossy compression of data is an intriguing solution, but comes with its own drawbacks, such as potential signal loss, and the need for careful optimization of the compression ratio. In this work, …
The most common method for DNN pruning is hard thresholding of network weights, followed by retraining to recover any lost accuracy. Recently developed smart pruning algorithms use the DNN response over the training set for a variety of cost functions to determine redundant network weights, leading to less accuracy deg…
Noise makes learning linear thresholds hard, but algorithms can still learn near-optimal thresholds.
problem Learning linear thresholds in noisy data.
method Exploiting natural assumptions on data-generating process.
result Efficient learning of near-optimal linear thresholds is still possible with small data even in the presence of noise.
A genome-wide association study (GWAS) correlates marker variation with trait variation in a sample of individuals. Each study subject is genotyped at a multitude of SNPs (single nucleotide polymorphisms) spanning the genome. Here we assume that subjects are unrelated and collected at random and that trait values are n…
This work interprets GELU and related activations via a first-order loss function.
problem Understanding and optimizing activation functions in neural networks.
method Complementary interpretation using the Gaussian first-order loss function.
result Calibrated or learned uniform-threshold gates are competitive and often outperform GELU, ReLU, and SiLU/Swish.
We develop mask iterative hard thresholding algorithms (mask IHT and mask DORE) for sparse image reconstruction of objects with known contour. The measurements follow a noisy underdetermined linear model common in the compressive sampling literature. Assuming that the contour of the object that we wish to reconstruct i…
We investigate an existing distributed algorithm for learning sparse signals or data over networks. The algorithm is iterative and exchanges intermediate estimates of a sparse signal over a network. This learning strategy using exchange of intermediate estimates over the network requires a limited communication overhea…
Self-paced learning and hard example mining re-weight training instances to improve learning accuracy. This paper presents two improved alternatives based on lightweight estimates of sample uncertainty in stochastic gradient descent (SGD): the variance in predicted probability of the correct class across iterations of …
Iterative shrinkage/thresholding algorithm (ISTA) is a well-studied method for finding sparse solutions to ill-posed inverse problems. In this letter, we present a data-driven scheme for learning optimal thresholding functions for ISTA. The proposed scheme is obtained by relating iterations of ISTA to layers of a simpl…
We study the problem of robust linear regression with response variable corruptions. We consider the oblivious adversary model, where the adversary corrupts a fraction of the responses in complete ignorance of the data. We provide a nearly linear time estimator which consistently estimates the true regression vector, e…
Stochastic optimization algorithms update models with cheap per-iteration costs sequentially, which makes them amenable for large-scale data analysis. Such algorithms have been widely studied for structured sparse models where the sparsity information is very specific, e.g., convex sparsity-inducing norms or -n…
New PSDMF algorithms derived from PR and ARM methods.
problem Positive semidefinite matrix factorization (PSDMF) challenges.
method Design PSDMF algorithms based on phase retrieval (PR) and affine rank minimization (ARM) methods.
result New PSDMF algorithms inherit numerical properties from PR and ARM methods.
Variational Inference: Posterior Threshold Improves Network Clustering Accuracy in Sparse Regimesstat.ML
Paper proposes a method to improve variational inference for sparse networks.
problem Variational inference struggles with sparse networks, leading to inaccurate community detection.
method The method involves hard thresholding the posterior of community assignment after each iteration.
result The proposed method accurately recovers true community labels in sparse networks.
New methods solve graph sparsity optimization problems faster.
problem Complex graph sparsity optimization problems in disease outbreak monitoring and social network analysis.
method Stochastic variance-reduced gradient-based methods GraphSVRG-IHT and GraphSCSG-IHT.
result Our methods achieve linear convergence speed.
SCOPE iteratively optimizes sparsity-constrained problems without tuning hyperparameters.
problem Optimizing sparsity-constrained problems in signal processing, statistics, and machine learning.
method SCOPE (Sparsity-Constrained Optimization via sPlicing itEration) replaces gradient steps with a splicing operation guided by the objective value.
result SCOPE achieves linear convergence and superior support recovery performance.
Variable selection in linear models plays a pivotal role in modern statistics. Hard-thresholding methods such as regularization are theoretically ideal but computationally infeasible. In this paper, we propose a new approach, called the LAGS, short for "least absulute gradient selector", to this challenging yet i…
New algorithm robustly estimates sparse models in high dimensions with corrupted data.
problem Estimating latent variable models with arbitrarily corrupted samples in high dimensional space.
method Trimmed (Gradient) Expectation Maximization with trimming gradients and hard thresholding steps.
result The algorithm converges to near optimal statistical rate geometrically under certain conditions.