Reproducibility in Learning

• URL: http://arxiv.org/abs/2201.08430v2
• Date: Fri, 14 Apr 2023 14:57:31 GMT
• Title: Reproducibility in Learning
• Authors: Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell
• Abstract summary: A reproducible learning algorithm is resilient to variations in its samples. Despite strong demand, there are efficient reproducible algorithms for several fundamental problems in statistics and learning.
• Score: 8.386806623480156
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce the notion of a reproducible algorithm in the context of learning. A reproducible learning algorithm is resilient to variations in its samples -- with high probability, it returns the exact same output when run on two samples from the same underlying distribution. We begin by unpacking the definition, clarifying how randomness is instrumental in balancing accuracy and reproducibility. We initiate a theory of reproducible algorithms, showing how reproducibility implies desirable properties such as data reuse and efficient testability. Despite the exceedingly strong demand of reproducibility, there are efficient reproducible algorithms for several fundamental problems in statistics and learning. First, we show that any statistical query algorithm can be made reproducible with a modest increase in sample complexity, and we use this to construct reproducible algorithms for finding approximate heavy-hitters and medians. Using these ideas, we give the first reproducible algorithm for learning halfspaces via a reproducible weak learner and a reproducible boosting algorithm. Finally, we initiate the study of lower bounds and inherent tradeoffs for reproducible algorithms, giving nearly tight sample complexity upper and lower bounds for reproducible versus nonreproducible SQ algorithms.

Related papers

• Derandomizing Multi-Distribution Learning [28.514129340758938]
  Multi-distribution learning involves learning a single predictor that works well across multiple data distributions. Recent research has shown near-optimal sample complexity achieved with oracle efficient algorithms. This raises the question: can these algorithms be derandomized to produce a deterministic predictor for multiple distributions?
  arXiv  Detail & Related papers  (2024-09-26T06:28:56Z)
• Batch Bayesian Optimization for Replicable Experimental Design [56.64902148159355]
  Many real-world design problems evaluate multiple experimental conditions in parallel and replicate each condition multiple times due to large and heteroscedastic observation noise. We propose the Batch Thompson Sampling for Replicable Experimental Design framework, which encompasses three algorithms. We show the effectiveness of our algorithms in two practical real-world applications: precision agriculture and AutoML.
  arXiv  Detail & Related papers  (2023-11-02T12:46:03Z)
• Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luck [35.6883212537938]
  We consider offline sparse parity learning, a supervised classification problem which admits a statistical query lower bound for gradient-based training of a multilayer perceptron. We show, theoretically and experimentally, that sparse initialization and increasing network width yield significant improvements in sample efficiency in this setting. We also show that the synthetic sparse parity task can be useful as a proxy for real problems requiring axis-aligned feature learning.
  arXiv  Detail & Related papers  (2023-09-07T15:52:48Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• Replicable Reinforcement Learning [15.857503103543308]
  We provide a provably replicable algorithm for parallel value iteration, and a provably replicable version of R-max in the episodic setting. These are the first formal replicability results for control problems, which present different challenges for replication than batch learning settings.
  arXiv  Detail & Related papers  (2023-05-24T16:05:15Z)
• 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)
• A Simplicity Bubble Problem in Formal-Theoretic Learning Systems [1.7996150751268578]
  We show that current approaches to machine learning can always be deceived, naturally or artificially, by sufficiently large datasets. We discuss the framework and additional empirical conditions to be met in order to circumvent this deceptive phenomenon.
  arXiv  Detail & Related papers  (2021-12-22T23:44:47Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation [71.31905141672529]
  We study the widely adopted ancestral sampling algorithms for auto-regressive language models. We identify three key properties that are shared among them: entropy reduction, order preservation, and slope preservation. We find that the set of sampling algorithms that satisfies these properties performs on par with the existing sampling algorithms.
  arXiv  Detail & Related papers  (2020-09-15T17:28:42Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions [8.08640000394814]
  We develop a quantum algorithm for sampling from an optimized distribution over runtime features. Our algorithm achieves an exponential speedup in $D$ compared to any known classical algorithm for this sampling task.
  arXiv  Detail & Related papers  (2020-04-22T18:00:00Z)

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.