Thresholds of descending algorithms in inference problems

• URL: http://arxiv.org/abs/2001.00479v2
• Date: Sat, 4 Jan 2020 08:53:20 GMT
• Title: Thresholds of descending algorithms in inference problems
• Authors: Stefano Sarao Mannelli and Lenka Zdeborova
• Abstract summary: We review recent works on analyzing the dynamics of gradient-based algorithms in a statistical inference problem. Using methods and insights from the physics of glassy systems, these works showed how to understand quantitatively and qualitatively the performance of gradient-based algorithms.
• Score: 4.594159253008448
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We review recent works on analyzing the dynamics of gradient-based algorithms in a prototypical statistical inference problem. Using methods and insights from the physics of glassy systems, these works showed how to understand quantitatively and qualitatively the performance of gradient-based algorithms. Here we review the key results and their interpretation in non-technical terms accessible to a wide audience of physicists in the context of related works.

Related papers

• Quantum Linear System Solvers: A Survey of Algorithms and Applications [2.9648284018500033]
  We summarize and analyze the main ideas behind some of the algorithms for the quantum linear systems problem in the literature. We focus on the post-HHL enhancements which have paved the way towards optimal lower bounds with respect to error tolerance and condition number. We discuss the potential applications of these algorithms in differential equations, quantum machine learning, and many-body physics.
  arXiv  Detail & Related papers  (2024-11-04T19:03:25Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• 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)
• 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)
• Interpretable Deep Learning: Interpretations, Interpretability, Trustworthiness, and Beyond [49.93153180169685]
  We introduce and clarify two basic concepts-interpretations and interpretability-that people usually get confused. We elaborate the design of several recent interpretation algorithms, from different perspectives, through proposing a new taxonomy. We summarize the existing work in evaluating models' interpretability using "trustworthy" interpretation algorithms.
  arXiv  Detail & Related papers  (2021-03-19T08:40:30Z)
• Inverse Reinforcement Learning with Explicit Policy Estimates [19.159290496678004]
  Various methods for solving the inverse reinforcement learning problem have been developed independently in machine learning and economics. We show that they all belong to a class of optimization problems, characterized by a common form of gradient, the associated policy and the objective. Using insights which emerge from our study of this class of optimization problems, we identify various problem scenarios and investigate each method's suitability for these problems.
  arXiv  Detail & Related papers  (2021-03-04T07:00:58Z)
• Tunable Tradeoff between Quantum and Classical Computation via Nonunitary Zeno-like Dynamics [0.5249805590164902]
  We show that the algorithm scales similarly to the pure quantum version by deriving tight analytical lower bounds on its efficiency. We also study the behavior of the algorithm subject to noise, and find that under certain oracle and operational errors our measurement-based algorithm outperforms the standard algorithm.
  arXiv  Detail & Related papers  (2020-11-22T00:57:17Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)
• A Brief Look at Generalization in Visual Meta-Reinforcement Learning [56.50123642237106]
  We evaluate the generalization performance of meta-reinforcement learning algorithms. We find that these algorithms can display strong overfitting when they are evaluated on challenging tasks.
  arXiv  Detail & Related papers  (2020-06-12T15:17:17Z)

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.