Do Proportionate Algorithms Exploit Sparsity?

• URL: http://arxiv.org/abs/2108.06846v1
• Date: Mon, 16 Aug 2021 00:56:00 GMT
• Title: Do Proportionate Algorithms Exploit Sparsity?
• Authors: Markus V. S. Lima, Gabriel S. Chaves, Tadeu N. Ferreira, and Paulo S. R. Diniz
• Abstract summary: This paper addresses the unexplored drawbacks and limitations of using proportionate-type algorithms. Our findings include the theoretical justification for the poor performance of these algorithms in several sparse scenarios, and also when dealing with non-stationary and compressible systems.
• Score: 13.303007365477862
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Adaptive filters exploiting sparsity have been a very active research field, among which the algorithms that follow the "proportional-update principle", the so-called proportionate-type algorithms, are very popular. Indeed, there are hundreds of works on proportionate-type algorithms and, therefore, their advantages are widely known. This paper addresses the unexplored drawbacks and limitations of using proportional updates and their practical impacts. Our findings include the theoretical justification for the poor performance of these algorithms in several sparse scenarios, and also when dealing with non-stationary and compressible systems. Simulation results corroborating the theory are presented.

Related papers

• Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits [6.907555940790131]
  Thompson sampling and Greedy demonstrate promising empirical performance, yet this contrasts with their pessimistic theoretical regret bounds. We propose a new data-driven technique that tracks the geometric properties of the uncertainty ellipsoid. We identify and course-correct" problem instances in which the base algorithms perform poorly.
  arXiv  Detail & Related papers  (2023-06-26T17:38:45Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  We propose a new learning framework for neural networks, namely Cascaded Forward (CaFo) algorithm, which does not rely on BP optimization as that in FF. Unlike FF, our framework directly outputs label distributions at each cascaded block, which does not require generation of additional negative samples. In our framework each block can be trained independently, so it can be easily deployed into parallel acceleration systems.
  arXiv  Detail & Related papers  (2023-03-17T02:01:11Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  We improve the theoretical and empirical performance of neural-network(NN)-based active learning algorithms for the non-parametric streaming setting. We introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work.
  arXiv  Detail & Related papers  (2022-10-02T05:03:38Z)
• An Operator Theoretic Perspective on Pruning Deep Neural Networks [2.624902795082451]
  We make use of recent advances in dynamical systems theory to define a new class of theoretically motivated pruning algorithms. We show that these algorithms can be equivalent to magnitude and gradient based pruning, unifying these seemingly disparate methods.
  arXiv  Detail & Related papers  (2021-10-28T02:33:50Z)
• Performance Analysis of Fractional Learning Algorithms [32.21539962359158]
  It is unclear whether the proclaimed superiority over conventional algorithms is well-grounded or is a myth as their performance has never been extensively analyzed. In this article, a rigorous analysis of fractional variants of the least mean squares and steepest descent algorithms is performed. Their origins and consequences on the performance of the learning algorithms are discussed and swift ready-witted remedies are proposed.
  arXiv  Detail & Related papers  (2021-10-11T12:06:44Z)
• Discrepancy-Based Active Learning for Domain Adaptation [7.283533791778357]
  The goal of the paper is to design active learning strategies which lead to domain adaptation under an assumption of domain shift. We derive bounds for such active learning strategies in terms of Rademacher average and localized discrepancy for general loss functions. We provide improved versions of the algorithms to address the case of large data sets.
  arXiv  Detail & Related papers  (2021-03-05T15:36:48Z)
• Nonparametric adaptive active learning under local smoothness condition [0.76146285961466]
  This paper adresses the problem of adaptive active learning in a nonparametric setting with minimal assumptions. We present a novel algorithm that is valid under more general assumptions than the previously known algorithms. Our algorithm achieves a minimax rate of convergence, and therefore performs almost as well as the best known non-adaptive algorithms.
  arXiv  Detail & Related papers  (2021-02-22T14:47:21Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Variance-Reduced Off-Policy Memory-Efficient Policy Search [61.23789485979057]
  Off-policy policy optimization is a challenging problem in reinforcement learning. Off-policy algorithms are memory-efficient and capable of learning from off-policy samples.
  arXiv  Detail & Related papers  (2020-09-14T16:22:46Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics. Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis. We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
  arXiv  Detail & Related papers  (2020-06-23T04:25:36Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  Adaptivity is an important yet under-studied property in modern optimization theory. Our algorithm is proved to achieve the best-available convergence for non-PL objectives simultaneously while outperforming existing algorithms for PL objectives.
  arXiv  Detail & Related papers  (2020-02-13T05:42:27Z)

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.