Stochastic Natural Thresholding Algorithms

• URL: http://arxiv.org/abs/2306.04730v1
• Date: Wed, 7 Jun 2023 18:49:19 GMT
• Title: Stochastic Natural Thresholding Algorithms
• Authors: Rachel Grotheer, Shuang Li, Anna Ma, Deanna Needell, and Jing Qin
• Abstract summary: Natural Thresholding (NT) has been proposed with improved computational efficiency. This paper proposes convergence guarantees for natural thresholding algorithms by extending the deterministic version with linear measurements.
• Score: 18.131412357510158
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sparse signal recovery is one of the most fundamental problems in various applications, including medical imaging and remote sensing. Many greedy algorithms based on the family of hard thresholding operators have been developed to solve the sparse signal recovery problem. More recently, Natural Thresholding (NT) has been proposed with improved computational efficiency. This paper proposes and discusses convergence guarantees for stochastic natural thresholding algorithms by extending the NT from the deterministic version with linear measurements to the stochastic version with a general objective function. We also conduct various numerical experiments on linear and nonlinear measurements to demonstrate the performance of StoNT.

Related papers

• Automated Design of Linear Bounding Functions for Sigmoidal Nonlinearities in Neural Networks [23.01933325606068]
  Existing complete verification techniques offer provable guarantees for all robustness queries but struggle to scale beyond small neural networks. We propose a novel parameter search method to improve the quality of these linear approximations. Specifically, we show that using a simple search method, carefully adapted to the given verification problem through state-of-the-art algorithm configuration techniques, improves the average global lower bound by 25% on average over the current state of the art.
  arXiv  Detail & Related papers  (2024-06-14T16:16:26Z)
• Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks [15.074950361970194]
  We provide a unified analysis for a family of algorithms that encompasses IRLS, the recently proposed linlin-RFM algorithm, and the alternating diagonal neural networks. We show that, with appropriately chosen reweighting policy, a handful of sparse structures can achieve favorable performance. We also show that leveraging this in the reweighting scheme provably improves test error compared to coordinate-wise reweighting.
  arXiv  Detail & Related papers  (2024-06-04T20:37:17Z)
• Embedding Trajectory for Out-of-Distribution Detection in Mathematical Reasoning [50.84938730450622]
  We propose a trajectory-based method TV score, which uses trajectory volatility for OOD detection in mathematical reasoning. Our method outperforms all traditional algorithms on GLMs under mathematical reasoning scenarios. Our method can be extended to more applications with high-density features in output spaces, such as multiple-choice questions.
  arXiv  Detail & Related papers  (2024-05-22T22:22:25Z)
• Bagged Regularized $k$-Distances for Anomaly Detection [9.899763598214122]
  We propose a new distance-based algorithm called bagged regularized $k$-distances for anomaly detection (BRDAD) Our BRDAD algorithm selects the weights by minimizing the surrogate risk, i.e., the finite sample bound of the empirical risk of the bagged weighted $k$-distances for density estimation (BWDDE) On the theoretical side, we establish fast convergence rates of the AUC regret of our algorithm and demonstrate that the bagging technique significantly reduces the computational complexity.
  arXiv  Detail & Related papers  (2023-12-02T07:00:46Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Robust lEarned Shrinkage-Thresholding (REST): Robust unrolling for sparse recover [87.28082715343896]
  We consider deep neural networks for solving inverse problems that are robust to forward model mis-specifications. We design a new robust deep neural network architecture by applying algorithm unfolding techniques to a robust version of the underlying recovery problem. The proposed REST network is shown to outperform state-of-the-art model-based and data-driven algorithms in both compressive sensing and radar imaging problems.
  arXiv  Detail & Related papers  (2021-10-20T06:15:45Z)
• Identification and Adaptation with Binary-Valued Observations under Non-Persistent Excitation Condition [1.6897716547971817]
  We propose an online projected Quasi-Newton type algorithm for estimation of parameter estimation of regression models with binary-valued observations. We establish the strong consistency of the estimation algorithm and provide the convergence rate. Convergence of adaptive predictors and their applications in adaptive control are also discussed.
  arXiv  Detail & Related papers  (2021-07-08T03:57:50Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Activation Relaxation: A Local Dynamical Approximation to Backpropagation in the Brain [62.997667081978825]
  Activation Relaxation (AR) is motivated by constructing the backpropagation gradient as the equilibrium point of a dynamical system. Our algorithm converges rapidly and robustly to the correct backpropagation gradients, requires only a single type of computational unit, and can operate on arbitrary computation graphs.
  arXiv  Detail & Related papers  (2020-09-11T11:56:34Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Taming neural networks with TUSLA: Non-convex learning via adaptive stochastic gradient Langevin algorithms [0.0]
  We offer on an appropriately constructed gradient algorithm based on problematic Lange dynamics (SGLD) We also provide nonasymptotic analysis of the use of new algorithm's convergence properties. The roots of the TUSLA algorithm are based on the taming processes with developed coefficients citettamed-euler.
  arXiv  Detail & Related papers  (2020-06-25T16:06:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.