Learning with Simulators: No Regret in a Computationally Bounded World

• URL: http://arxiv.org/abs/2606.13576v1
• Date: Thu, 11 Jun 2026 17:02:24 GMT
• Title: Learning with Simulators: No Regret in a Computationally Bounded World
• Abstract summary: We introduce the framework of simulatable processes, where the learner has access to a simulator that approximates the distribution generating the data.<n>We show that we can recover the same learning guarantees as in the classical setting with independent data, namely, error bounds that depend on the VC.
• Score: 65.78002253798827
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Understanding the minimal assumptions necessary for generalization is the fundamental question in learning theory. Unfortunately, most results rely heavily on independence (or some proxy thereof) of the data-generating process, while results for strongly dependent data are far more limited. Towards addressing this gap, we introduce the framework of simulatable processes, where the learner has access to a simulator that approximates the distribution generating the data (which may be an arbitrarily complex and dependent process). Surprisingly, given access to such a simulator, we show that we can recover the same learning guarantees as in the classical setting with independent data, namely, error bounds that depend on the VC dimension. Further, we use this framework to study the power of conditional sampling and show strict statistical and computational advantages in this setting. As a highlight of our framework, we exhibit a single algorithm that simultaneously learns any given VC class under all processes samplable in bounded polynomial time, with regret controlled by the time-bounded Kolmogorov complexity of the process. This provides a significant conceptual broadening of the classical PAC model.

Related papers

• Learning-Augmented Moment Estimation on Time-Decay Models [55.06256430461023]
  We use an oracle for the heavy-hitters of datasets to give learning-augmented algorithms for a number of fundamental problems.<n>We complement our theoretical results with a number of empirical evaluations that demonstrate the practical efficiency of our algorithms on real and synthetic datasets.
  arXiv  Detail & Related papers  (2026-03-03T00:42:34Z)
• Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
  We study sequential decision making under distributional adversaries that can adaptively choose data-generating distributions from a fixed family $U$.<n>We provide a near complete characterization of families $U$ that admit learnability in terms of a notion known as generalized smoothness.<n>We show that the generalized smoothness also characterizes private learnability under distributional constraints.
  arXiv  Detail & Related papers  (2026-02-24T06:15:59Z)
• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  Learning intersections of halfspaces is a central problem in Computational Learning Theory.<n>Even for just two halfspaces, it remains a major open question whether learning is possible in time.<n>We introduce a novel algorithm that provably circumvents the CSQ hardness barrier.
  arXiv  Detail & Related papers  (2025-11-13T00:28:24Z)
• Efficient Machine Unlearning via Influence Approximation [75.31015485113993]
  Influence-based unlearning has emerged as a prominent approach to estimate the impact of individual training samples on model parameters without retraining.<n>This paper establishes a theoretical link between memorizing (incremental learning) and forgetting (unlearning)<n>We introduce the Influence Approximation Unlearning algorithm for efficient machine unlearning from the incremental perspective.
  arXiv  Detail & Related papers  (2025-07-31T05:34:27Z)
• 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)
• Bootstrap aggregation and confidence measures to improve time series causal discovery [0.0]
  We introduce a novel bootstrap approach designed for time series causal discovery that preserves the temporal dependencies and lag structure. We combine this approach with the state-of-the-art conditional-independence-based algorithm PCMCI+.
  arXiv  Detail & Related papers  (2023-06-15T08:37:16Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  We study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length $m$. In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially. Our results show that a short-term memory suffices for reinforcement learning in these environments.
  arXiv  Detail & Related papers  (2022-02-08T16:39:57Z)
• Fully Homomorphically Encrypted Deep Learning as a Service [4.082216579462797]
  Fully Homomorphic Encryption (FHE) is a relatively recent advancement in the field of privacy-preserving technologies. This project investigates, derives, and proves how FHE with deep learning can be used at scale, with relatively low time complexity. We discuss how this could have an impact on the future of data privacy and how it can enable data sharing across various actors in the agri-food supply chain.
  arXiv  Detail & Related papers  (2021-07-26T20:17:48Z)
• A Theory of Universal Learning [26.51949485387526]
  We show that there are only three possible rates of universal learning. We show that the learning curves of any given concept class decay either at an exponential, or arbitrarily slow rates.
  arXiv  Detail & Related papers  (2020-11-09T15:10:32Z)
• Random thoughts about Complexity, Data and Models [0.0]
  Data Science and Machine learning have been growing strong for the past decade. We investigate the subtle relation between "data and models" Key issue for appraisal of relation between algorithmic complexity and algorithmic learning is to do with concepts of compressibility, determinism and predictability.
  arXiv  Detail & Related papers  (2020-04-16T14:27: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.