On the Computational Landscape of Replicable Learning

• URL: http://arxiv.org/abs/2405.15599v2
• Date: Sat, 30 Nov 2024 15:22:26 GMT
• Title: On the Computational Landscape of Replicable Learning
• Authors: Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas, Felix Zhou,
• Abstract summary: We study computational aspects of algorithmic replicability, a notion of stability introduced by Impagliazzo, Lei, Pitassi, and Sorrell. Motivated by a recent line of work that established strong statistical connections between replicability and other notions of learnability, we aim to understand better the computational connections between replicability and these learning paradigms.
• Score: 40.274579987732416
• License:
• Abstract: We study computational aspects of algorithmic replicability, a notion of stability introduced by Impagliazzo, Lei, Pitassi, and Sorrell [2022]. Motivated by a recent line of work that established strong statistical connections between replicability and other notions of learnability such as online learning, private learning, and SQ learning, we aim to understand better the computational connections between replicability and these learning paradigms. Our first result shows that there is a concept class that is efficiently replicably PAC learnable, but, under standard cryptographic assumptions, no efficient online learner exists for this class. Subsequently, we design an efficient replicable learner for PAC learning parities when the marginal distribution is far from uniform, making progress on a question posed by Impagliazzo et al. [2022]. To obtain this result, we design a replicable lifting framework inspired by Blanc, Lange, Malik, and Tan [2023] that transforms in a black-box manner efficient replicable PAC learners under the uniform marginal distribution over the Boolean hypercube to replicable PAC learners under any marginal distribution, with sample and time complexity that depends on a certain measure of the complexity of the distribution. Finally, we show that any pure DP learner can be transformed to a replicable one in time polynomial in the accuracy, confidence parameters and exponential in the representation dimension of the underlying hypothesis class.

Related papers

• Replicable Online Learning [12.14234796585091]
  We investigate the concept of algorithmic replicability introduced by Impagliazzo and Ghazi. In our model, the input sequence received by the online learner is generated from time-varying distributions chosen by an adversary. Our objective is to design low-regret online algorithms that, with high probability, produce the exact same sequence of actions when run on two independently sampled input sequences.
  arXiv  Detail & Related papers  (2024-11-20T22:10:37Z)
• Near-Optimal Learning and Planning in Separated Latent MDPs [70.88315649628251]
  We study computational and statistical aspects of learning Latent Markov Decision Processes (LMDPs) In this model, the learner interacts with an MDP drawn at the beginning of each epoch from an unknown mixture of MDPs.
  arXiv  Detail & Related papers  (2024-06-12T06:41:47Z)
• Replicability in High Dimensional Statistics [18.543059748500358]
  We study the computational and statistical cost of replicability for several fundamental high dimensional statistical tasks. Our main contribution establishes a computational and statistical equivalence between optimal replicable algorithms and high dimensional isoperimetrics.
  arXiv  Detail & Related papers  (2024-06-04T00:06:42Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  We study a variant of Collaborative PAC Learning, in which we aim to learn an accurate classifier for each of the $n$ data distributions. We show that, when the data distributions satisfy a weaker realizability assumption, sample-efficient learning is still feasible.
  arXiv  Detail & Related papers  (2024-02-16T04:32:22Z)
• Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
  We aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. We first introduce a minimax instance optimal learner for realizable regression and propose a novel dimension that both qualitatively and quantitatively characterizes which classes of real-valued predictors are learnable. In the context of online learning we provide a dimension that characterizes the minimax optimal instance optimal cumulative loss up to a constant factor and design an optimal online learner for realizable regression.
  arXiv  Detail & Related papers  (2023-07-07T21:39:25Z)
• 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)
• A Parameterized Theory of PAC Learning [19.686465068713467]
  Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory. We develop a theory of parameterized PAC learning which allows us to shed new light on several recent PAC learning results that incorporated elements of parameterized complexity.
  arXiv  Detail & Related papers  (2023-04-27T09:39:30Z)
• Contrastive UCB: Provably Efficient Contrastive Self-Supervised Learning in Online Reinforcement Learning [92.18524491615548]
  Contrastive self-supervised learning has been successfully integrated into the practice of (deep) reinforcement learning (RL) We study how RL can be empowered by contrastive learning in a class of Markov decision processes (MDPs) and Markov games (MGs) with low-rank transitions. Under the online setting, we propose novel upper confidence bound (UCB)-type algorithms that incorporate such a contrastive loss with online RL algorithms for MDPs or MGs.
  arXiv  Detail & Related papers  (2022-07-29T17:29:08Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation. We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
  arXiv  Detail & Related papers  (2022-06-01T23:26:51Z)
• Network Classifiers Based on Social Learning [71.86764107527812]
  We propose a new way of combining independently trained classifiers over space and time. The proposed architecture is able to improve prediction performance over time with unlabeled data. We show that this strategy results in consistent learning with high probability, and it yields a robust structure against poorly trained classifiers.
  arXiv  Detail & Related papers  (2020-10-23T11:18:20Z)

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.