pith. sign in

arxiv: 2606.13576 · v1 · pith:HCLHACISnew · submitted 2026-06-11 · 💻 cs.LG · cs.CC· cs.DS· stat.ML

Learning with Simulators: No Regret in a Computationally Bounded World

Sasha Voitovych , Abhishek Shetty , Noah Golowich , Alexander Rakhlin This is my paper

Pith reviewed 2026-06-27 07:20 UTC · model grok-4.3

classification 💻 cs.LG cs.CCcs.DSstat.ML
keywords simulatable processesVC dimensiondependent dataKolmogorov complexityPAC learningno-regret learningconditional samplinggeneralization bounds
0
0 comments X

The pith

Access to a simulator approximating the data process restores VC-dimension error bounds even for arbitrarily dependent data.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces simulatable processes, a framework in which the learner receives a simulator that approximates the data-generating distribution even when that distribution is complex and dependent. With this simulator, the work shows that standard generalization bounds depending only on the VC dimension of the hypothesis class can be recovered, matching the guarantees that classically require independent samples. It further gives a single algorithm that simultaneously learns any fixed VC class over every data process samplable in bounded polynomial time, with the algorithm's regret bounded by the time-bounded Kolmogorov complexity of the process. This construction supplies a uniform method that works across an entire class of computationally bounded but statistically dependent environments.

Core claim

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 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.

What carries the argument

The simulatable processes framework, in which an approximating simulator is supplied to the learner so that VC-dimension arguments apply directly to dependent data.

If this is right

  • Error bounds depend only on VC dimension and hold without any independence assumption on the data.
  • One algorithm suffices for every process that can be sampled in bounded polynomial time.
  • Regret scales with the time-bounded Kolmogorov complexity of the underlying process.
  • Conditional sampling yields both statistical and computational advantages inside the same framework.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach suggests that providing an explicit simulator could replace the need for independence assumptions in many practical sequential or spatial data settings.
  • It raises the question of whether approximate simulators can be learned or verified from limited observations without circularity.
  • The uniform algorithm may extend naturally to settings such as reinforcement learning where simulators are already available by design.

Load-bearing premise

The simulator must approximate the data-generating distribution closely enough that classical VC-dimension arguments carry through unchanged.

What would settle it

An explicit construction of a low-VC class and a dependent process samplable in polynomial time for which the single algorithm's excess risk exceeds the VC bound or the stated Kolmogorov-complexity term even when an accurate simulator is provided.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper introduces the framework of simulatable processes, in which the learner is granted access to a simulator that approximates the (possibly arbitrarily complex and dependent) data-generating distribution. It claims that this access recovers the classical VC-dimension-dependent generalization bounds of the i.i.d. PAC setting. The paper further exhibits a single algorithm that simultaneously learns any fixed VC class for every process samplable in bounded polynomial time, with regret bounded by the time-bounded Kolmogorov complexity of the process, and uses the framework to derive statistical and computational advantages for conditional sampling.

Significance. If the central claims are established with rigorous error accounting, the work would constitute a meaningful conceptual extension of the PAC model to dependent data via an explicit simulator assumption, while linking regret to computational boundedness measures. The universal algorithm and conditional-sampling results would be notable if they avoid circularity or hidden dependence on the simulator's fidelity.

major comments (2)
  1. [Abstract / Introduction] Abstract and introduction: the claim that simulator access 'recovers the same learning guarantees ... error bounds that depend on the VC dimension' is stated without any indication of how non-zero approximation error (e.g., total-variation distance between simulator and true process) is absorbed into the uniform-convergence argument. Standard VC proofs require exact samples; an additive error term would ordinarily appear unless the paper supplies a modified concentration or coupling argument that cancels it exactly.
  2. [Abstract] The universal algorithm result (regret controlled solely by time-bounded Kolmogorov complexity) appears to rest on the simulator being sufficiently accurate for every bounded-polynomial-time process. No section or theorem sketch in the provided abstract quantifies the required simulator fidelity or shows that the regret bound remains independent of that fidelity parameter.
minor comments (1)
  1. Notation for the simulator and the approximation metric (total variation, statistical distance, etc.) should be introduced explicitly in the first section that defines simulatable processes.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. Below we address each major comment point-by-point, clarifying the technical arguments in the full manuscript and indicating revisions for improved exposition.

read point-by-point responses

  1. Referee: [Abstract / Introduction] Abstract and introduction: the claim that simulator access 'recovers the same learning guarantees ... error bounds that depend on the VC dimension' is stated without any indication of how non-zero approximation error (e.g., total-variation distance between simulator and true process) is absorbed into the uniform-convergence argument. Standard VC proofs require exact samples; an additive error term would ordinarily appear unless the paper supplies a modified concentration or coupling argument that cancels it exactly.

    Authors: We agree the abstract and introduction would benefit from explicit mention of the error handling. Theorem 3.1 and its proof in Section 3.2 employ a coupling between simulator draws and the true process: the total-variation distance δ contributes an additive O(δ) term to the uniform-convergence bound, which is absorbed into the overall error rate by selecting a simulator with δ smaller than the target accuracy. The leading term remains the standard VC-dimension dependence. We will revise the abstract and introduction to note this coupling argument and the resulting additive term. revision: yes

  2. Referee: [Abstract] The universal algorithm result (regret controlled solely by time-bounded Kolmogorov complexity) appears to rest on the simulator being sufficiently accurate for every bounded-polynomial-time process. No section or theorem sketch in the provided abstract quantifies the required simulator fidelity or shows that the regret bound remains independent of that fidelity parameter.

    Authors: Section 4 presents the universal algorithm (Theorem 4.3). For any process samplable in time t(n), a simulator with inverse-polynomial fidelity suffices; the regret is bounded by the time-bounded Kolmogorov complexity K_t of the process description and does not depend on the precise fidelity value once it meets the inverse-polynomial threshold. The proof constructs the algorithm by using the simulator to generate trajectories and applies a standard no-regret template whose analysis is invariant to the fidelity parameter beyond that threshold. We will add a brief theorem sketch to the abstract and introduction to quantify the fidelity requirement and independence. revision: yes

Circularity Check

0 steps flagged

No circularity; claims derive from new simulator-access assumption

full rationale

The paper introduces the simulatable processes framework as a modeling assumption and derives VC-dimension bounds and a single algorithm for time-bounded processes directly from that assumption. No self-definitional reductions, fitted parameters renamed as predictions, or load-bearing self-citations appear in the abstract or described results. The derivation chain is self-contained against the stated simulator model rather than reducing to its own outputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Only the abstract is available. The central modeling choice is the existence of an approximating simulator; no numerical free parameters are mentioned. The main added entity is the simulatable-process concept itself.

axioms (1)
  • standard math Standard VC-dimension generalization bounds hold when samples are drawn from the simulator distribution
    The paper states that simulator access recovers the classical VC bounds.
invented entities (1)
  • simulatable processes no independent evidence
    purpose: Model data-generating distributions that may be dependent yet admit a simulator approximating them
    New framework introduced to address the gap in learning from strongly dependent data.

pith-pipeline@v0.9.1-grok · 5730 in / 1292 out tokens · 31041 ms · 2026-06-27T07:20:23.121624+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

107 extracted references · 4 linked inside Pith

  1. [1]

    Regret bounds for the adaptive control of linear quadratic systems

    Yasin Abbasi-Yadkori and Csaba Szepesv´ ari. Regret bounds for the adaptive control of linear quadratic systems. InProceedings of the 24th Annual Conference on Learning Theory, pages 1–26, 2011

    2011

  2. [2]

    Majority-of-three: The simplest optimal learner? InThe Thirty Seventh Annual Conference on Learning Theory, pages 22–45

    Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen, and Nikita Zhivotovskiy. Majority-of-three: The simplest optimal learner? InThe Thirty Seventh Annual Conference on Learning Theory, pages 22–45. PMLR, 2024

    2024

  3. [3]

    A markovian extension of valiant’s learning model.In- formation and Computation, 117(2):181–186, 1995

    David Aldous and Umesh Vazirani. A markovian extension of valiant’s learning model.In- formation and Computation, 117(2):181–186, 1995. 21

    1995

  4. [4]

    Resolving the mixing time of the langevin algorithm to its stationary distribution for log-concave sampling.arXiv preprint arXiv:2210.08448, 2022

    Jason M Altschuler and Kunal Talwar. Resolving the mixing time of the langevin algorithm to its stationary distribution for log-concave sampling.arXiv preprint arXiv:2210.08448, 2022

    arXiv 2022

  5. [5]

    Worst-case running times for average-case algorithms

    Luis Antunes and Lance Fortnow. Worst-case running times for average-case algorithms. In 2009 24th Annual IEEE Conference on Computational Complexity, pages 298–303. IEEE, 2009

    2009

  6. [6]

    Com- putational depth: concept and applications.Theoretical Computer Science, 354(3):391–404, 2006

    Luis Antunes, Lance Fortnow, Dieter Van Melkebeek, and N Variyam Vinodchandran. Com- putational depth: concept and applications.Theoretical Computer Science, 354(3):391–404, 2006

    2006

  7. [7]

    The multiplicative weights update method: a meta-algorithm and applications.Theory of Computing, 8(1):121–164, 2012

    Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications.Theory of Computing, 8(1):121–164, 2012

    2012

  8. [8]

    Agnostically learning juntas from random walks.arXiv preprint arXiv:0806.4210, 2008

    Jan Arpe and Elchanan Mossel. Agnostically learning juntas from random walks.arXiv preprint arXiv:0806.4210, 2008

    Pith/arXiv arXiv 2008

  9. [9]

    The asymptotic redundancy of bayes rules for markov chains.IEEE Trans- actions on Information Theory, 45(6):2104–2109, 1999

    Kevin Atteson. The asymptotic redundancy of bayes rules for markov chains.IEEE Trans- actions on Information Theory, 45(6):2104–2109, 1999

    1999

  10. [10]

    Exploiting random walks for learning

    Peter L Bartlett, Paul Fischer, and Klaus-Uwe H¨ offgen. Exploiting random walks for learning. InProceedings of the Seventh Annual Conference on Computational Learning Theory, pages 318–327, 1994

    1994

  11. [11]

    Approximate Bayesian computa- tion in population genetics.Genetics, 162(4):2025–2035, 2002

    Mark A Beaumont, Wenyang Zhang, and David J Balding. Approximate Bayesian computa- tion in population genetics.Genetics, 162(4):2025–2035, 2002

    2025

  12. [12]

    Online learning versus offline learn- ing.Machine Learning, 29(1):45–63, 1997

    Shai Ben-David, Eyal Kushilevitz, and Yishay Mansour. Online learning versus offline learn- ing.Machine Learning, 29(1):45–63, 1997

    1997

  13. [13]

    Agnostic online learning

    Shai Ben-David, D´ avid P´ al, and Shai Shalev-Shwartz. Agnostic online learning. InConference on Learning Theory, volume 3, page 1, 2009

    2009

  14. [14]

    Online learning with imperfect hints

    Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online learning with imperfect hints. InInternational Conference on Machine Learning, pages 822–831. PMLR, 2020

    2020

  15. [15]

    Smoothed analysis of sequential probability assignment.Advances in Neural Information Processing Systems, 36:79808–79831, 2023

    Alankrita Bhatt, Nika Haghtalab, and Abhishek Shetty. Smoothed analysis of sequential probability assignment.Advances in Neural Information Processing Systems, 36:79808–79831, 2023

    2023

  16. [16]

    Agnostic smoothed online learning

    Mo¨ ıse Blanchard. Agnostic smoothed online learning. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1997–2006, 2025

    1997

  17. [17]

    The sample complexity of approximate rejection sampling with applications to smoothed online learning

    Adam Block and Yury Polyanskiy. The sample complexity of approximate rejection sampling with applications to smoothed online learning. InThe Thirty Sixth Annual Conference on Learning Theory, pages 228–273. PMLR, 2023

    2023

  18. [18]

    Smoothed online learning is as easy as statistical learning

    Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. InConference on Learning Theory, pages 1716–1786. PMLR, 2022. 22

    2022

  19. [19]

    On the performance of empirical risk minimization with smoothed data

    Adam Block, Alexander Rakhlin, and Abhishek Shetty. On the performance of empirical risk minimization with smoothed data. InThe Thirty Seventh Annual Conference on Learning Theory, pages 596–629. PMLR, 2024

    2024

  20. [20]

    Learnabil- ity and the vapnik-chervonenkis dimension.Journal of the ACM (JACM), 36(4):929–965, 1989

    Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnabil- ity and the vapnik-chervonenkis dimension.Journal of the ACM (JACM), 36(4):929–965, 1989

    1989

  21. [21]

    Learning graphical models from the glauber dynamics.IEEE Transactions on Information Theory, 64(6):4072–4080, 2017

    Guy Bresler, David Gamarnik, and Devavrat Shah. Learning graphical models from the glauber dynamics.IEEE Transactions on Information Theory, 64(6):4072–4080, 2017

    2017

  22. [22]

    Language mod- els are few-shot learners.Advances in Neural Information Processing Systems, 33:1877–1901, 2020

    Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language mod- els are few-shot learners.Advances in Neural Information Processing Systems, 33:1877–1901, 2020

    1901

  23. [23]

    Learning dnf from random walks.Journal of Computer and System Sciences, 71(3):250–265, 2005

    Nader H Bshouty, Elchanan Mossel, Ryan O’Donnell, and Rocco A Servedio. Learning dnf from random walks.Journal of Computer and System Sciences, 71(3):250–265, 2005

    2005

  24. [24]

    Cambridge univer- sity press, 2006

    Nicolo Cesa-Bianchi and G´ abor Lugosi.Prediction, learning, and games. Cambridge univer- sity press, 2006

    2006

  25. [25]

    LearningAC 0 under graphical models.arXiv preprint arXiv:2604.06109, 2026

    Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra, and Arsen Vasilyan. LearningAC 0 under graphical models.arXiv preprint arXiv:2604.06109, 2026

    Pith/arXiv arXiv 2026

  26. [26]

    Log-concave sampling.Book draft, available athttps: // chewisinho

    Sinho Chewi. Log-concave sampling.Book draft, available athttps: // chewisinho. github. io, 2024

    2024

  27. [27]

    Online optimization with gradual variations

    Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. InConference on Learning Theory, pages 6.1–6.20. JMLR Workshop and Conference Proceedings, 2012

    2012

  28. [28]

    Palm: Scaling language modeling with pathways.Journal of Machine Learning Re- search, 24(240):1–113, 2023

    Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways.Journal of Machine Learning Re- search, 24(240):1–113, 2023

    2023

  29. [29]

    Online linear quadratic control

    Alon Cohen, Avinatan Hassidim, Tomer Koren, Nevena Lazic, Yishay Mansour, and Kunal Talwar. Online linear quadratic control. InInternational Conference on Machine Learning, pages 1029–1038. PMLR, 2018

    2018

  30. [30]

    Jack Copeland

    B. Jack Copeland. The Church-Turing Thesis. In Edward N. Zalta and Uri Nodelman, editors, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Spring 2026 edition, 2026

    2026

  31. [31]

    The benefits of temporal corre- lations: Sgd learns k-juntas from random walks efficiently.arXiv preprint arXiv:2605.10237, 2026

    Elisabetta Cornacchia, Dan Mikulincer, and Elchanan Mossel. The benefits of temporal corre- lations: Sgd learns k-juntas from random walks efficiently.arXiv preprint arXiv:2605.10237, 2026

    Pith/arXiv arXiv 2026

  32. [32]

    The frontier of simulation-based infer- ence.Proceedings of the National Academy of Sciences, 117(48):30055–30062, 2020

    Kyle Cranmer, Johann Brehmer, and Gilles Louppe. The frontier of simulation-based infer- ence.Proceedings of the National Academy of Sciences, 117(48):30055–30062, 2020. 23

    2020

  33. [33]

    Learning from weakly dependent data under dobrushin’s condition

    Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Siddhartha Jayanti. Learning from weakly dependent data under dobrushin’s condition. InConference on Learning Theory, pages 914–928. PMLR, 2019

    2019

  34. [34]

    Simulation-based inference: A practical guide.arXiv preprint arXiv:2508.12939, 2025

    Michael Deistler, Jan Boelts, Peter Steinbach, Guy Moss, Thomas Moreau, Manuel Gloeckler, Pedro LC Rodrigues, Julia Linhart, Janne K Lappalainen, Benjamin Kurt Miller, et al. Simulation-based inference: A practical guide.arXiv preprint arXiv:2508.12939, 2025

    arXiv 2025

  35. [35]

    Quantum theory, the church–turing principle and the universal quantum com- puter.Proceedings of the Royal Society of London

    David Deutsch. Quantum theory, the church–turing principle and the universal quantum com- puter.Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 400(1818):97–117, 1985

    1985

  36. [36]

    Finite time identification in unstable linear systems.Automatica, 96:342–353, 2018

    Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Finite time identification in unstable linear systems.Automatica, 96:342–353, 2018

    2018

  37. [37]

    A unified approach to learning ising models: Beyond independence and bounded width

    Jason Gaitonde and Elchanan Mossel. A unified approach to learning ising models: Beyond independence and bounded width. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 503–514, 2024

    2024

  38. [38]

    Better models and algorithms for learning Ising models from dynamics.arXiv preprint arXiv:2507.15173, 2025

    Jason Gaitonde, Ankur Moitra, and Elchanan Mossel. Better models and algorithms for learning Ising models from dynamics.arXiv preprint arXiv:2507.15173, 2025

    arXiv 2025

  39. [39]

    Extension of the pac framework to finite and countable markov chains

    David Gamarnik. Extension of the pac framework to finite and countable markov chains. In Proceedings of the twelfth annual conference on Computational learning theory, pages 308– 317, 1999

    1999

  40. [40]

    Time-dependent statistics of the Ising model.Journal of Mathematical Physics, 4(2):294–307, 1963

    Roy J Glauber. Time-dependent statistics of the Ising model.Journal of Mathematical Physics, 4(2):294–307, 1963

    1963

  41. [41]

    Adversarial resilience in sequential prediction via abstention

    Surbhi Goel, Steve Hanneke, Shay Moran, and Abhishek Shetty. Adversarial resilience in sequential prediction via abstention. InAdvances in Neural Information Processing Systems, volume 36, pages 8027–8047, 2023

    2023

  42. [42]

    Probabilistic kol- mogorov complexity with applications to average-case complexity

    Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C Oliveira. Probabilistic kol- mogorov complexity with applications to average-case complexity. In37th Computational Complexity Conference (CCC 2022), pages 16.1–16.60. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2022

    2022

  43. [43]

    Automatic posterior transfor- mation for likelihood-free inference

    David Greenberg, Marcel Nonnenmacher, and Jakob Macke. Automatic posterior transfor- mation for likelihood-free inference. InInternational Conference on Machine Learning, pages 2404–2414. PMLR, 2019

    2019

  44. [44]

    Smoothed analysis of online and differentially private learning.Advances in Neural Information Processing Systems, 33:9203– 9215, 2020

    Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differentially private learning.Advances in Neural Information Processing Systems, 33:9203– 9215, 2020

    2020

  45. [45]

    Oracle-efficient online learning for beyond worst-case adversaries.arXiv preprint arXiv:2202.08549, 2022

    Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. Oracle-efficient online learning for beyond worst-case adversaries.arXiv preprint arXiv:2202.08549, 2022

    arXiv 2022

  46. [46]

    Smoothed analysis with adaptive adversaries.Journal of the ACM, 71(3):1–34, 2024

    Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adversaries.Journal of the ACM, 71(3):1–34, 2024. 24

    2024

  47. [47]

    Accelerating scientific discovery with AI.https://www.youtube.com/ watch?v=UX8uIW9oIZk, 2024

    Demis Hassabis. Accelerating scientific discovery with AI.https://www.youtube.com/ watch?v=UX8uIW9oIZk, 2024

    2024

  48. [48]

    Future of AI, simulating reality, physics and video games.https://www

    Demis Hassabis. Future of AI, simulating reality, physics and video games.https://www. youtube.com/watch?v=-HzgcbRXUK8, 2025

    2025

  49. [49]

    The computational power of optimization in online learning

    Elad Hazan and Tomer Koren. The computational power of optimization in online learning. InProceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 128–141, 2016

    2016

  50. [50]

    Learning linear dynamical systems via spectral filtering

    Elad Hazan, Karan Singh, and Cyril Zhang. Learning linear dynamical systems via spectral filtering. InAdvances in Neural Information Processing Systems, pages 6702–6712, 2017

    2017

  51. [51]

    Spectral filtering for general linear dynamical systems

    Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang. Spectral filtering for general linear dynamical systems. InAdvances in Neural Information Processing Systems, pages 4639–4648, 2018

    2018

  52. [52]

    Likelihood-free MCMC with amortized approximate ratio estimators

    Joeri Hermans, Volodimir Begy, and Gilles Louppe. Likelihood-free MCMC with amortized approximate ratio estimators. InInternational Conference on Machine Learning, pages 4239–

  53. [53]

    Learning in pessiland via inductive inference

    Shuichi Hirahara and Mikito Nanashima. Learning in pessiland via inductive inference. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 447–457. IEEE, 2023

    2023

  54. [54]

    Denoising diffusion probabilistic models.Ad- vances in Neural Information Processing Systems, 33:6840–6851, 2020

    Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models.Ad- vances in Neural Information Processing Systems, 33:6840–6851, 2020

    2020

  55. [55]

    Cambridge university press, 2012

    Roger A Horn and Charles R Johnson.Matrix analysis. Cambridge university press, 2012

    2012

  56. [56]

    Chapman and Hall/CRC, 2024

    Marcus Hutter, David Quarel, and Elliot Catt.An introduction to universal artificial intel- ligence. Chapman and Hall/CRC, 2024

    2024

  57. [57]

    No better ways to generate hard np instances than picking uniformly at random

    Russell Impagliazzo and Leonid A Levin. No better ways to generate hard np instances than picking uniformly at random. InFOCS, 1990

    1990

  58. [58]

    Princeton university press, 2008

    Matthew O Jackson.Social and economic networks. Princeton university press, 2008

    2008

  59. [59]

    Online op- timization: Competing with dynamic comparators

    Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online op- timization: Competing with dynamic comparators. InInternational Conference on Artificial Intelligence and Statistics, pages 398–406. PMLR, 2015

    2015

  60. [60]

    From batch to transductive online learning.Advances in Neural Information Processing Systems, 18, 2005

    Sham Kakade and Adam T Kalai. From batch to transductive online learning.Advances in Neural Information Processing Systems, 18, 2005

    2005

  61. [61]

    MCMC learning

    Varun Kanade and Elchanan Mossel. MCMC learning. InConference on Learning Theory, pages 1101–1128. PMLR, 2015

    2015

  62. [62]

    Generalization bounds for non-stationary mixing processes.Machine Learning, 106(1):93–117, 2017

    Vitaly Kuznetsov and Mehryar Mohri. Generalization bounds for non-stationary mixing processes.Machine Learning, 106(1):93–117, 2017

    2017

  63. [63]

    Universal sequential search problems.Problems of Information Transmission, 9(3):265–266, 1973

    Leonid A Levin. Universal sequential search problems.Problems of Information Transmission, 9(3):265–266, 1973. 25

    1973

  64. [64]

    Randomness conservation inequalities; information and independence in mathematical theories.Information and Control, 61(1):15–37, 1984

    Leonid A Levin. Randomness conservation inequalities; information and independence in mathematical theories.Information and Control, 61(1):15–37, 1984

    1984

  65. [65]

    Texts in Computer Science

    Ming Li and Paul Vit´ anyi.An Introduction to Kolmogorov Complexity and Its Applications. Texts in Computer Science. Springer, 4th edition, 2019

    2019

  66. [66]

    Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.Machine Learning, 2(4):285–318, 1988

    Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.Machine Learning, 2(4):285–318, 1988

    1988

  67. [67]

    On one-way functions and Kolmogorov complexity

    Yanyi Liu and Rafael Pass. On one-way functions and Kolmogorov complexity. In2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1243–

  68. [68]

    Optimal coding theorems in time-bounded Kolmogorov complexity.arXiv preprint arXiv:2204.08312, 2022

    Zhenjian Lu, Igor C Oliveira, and Marius Zimand. Optimal coding theorems in time-bounded Kolmogorov complexity.arXiv preprint arXiv:2204.08312, 2022

    arXiv 2022

  69. [69]

    Flexible statistical inference for mechanistic models of neural dynamics

    Jan-Matthis Lueckmann, Pedro J Goncalves, Giacomo Bassetto, Kaan ¨Ocal, Marcel Nonnen- macher, and Jakob H Macke. Flexible statistical inference for mechanistic models of neural dynamics. InAdvances in Neural Information Processing Systems, volume 30, 2017

    2017

  70. [70]

    Achieving all with no parameters: AdaNormalHedge

    Haipeng Luo and Robert E Schapire. Achieving all with no parameters: AdaNormalHedge. InConference on Learning Theory, pages 1286–1304. PMLR, 2015

    2015

  71. [71]

    Competitive caching with machine learned advice

    Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1–25, 2021

    2021

  72. [72]

    Approximate Bayesian computational methods.Statistics and Computing, 22(6):1167–1180, 2012

    Jean-Michel Marin, Pierre Pudlo, Christian P Robert, and Robin J Ryder. Approximate Bayesian computational methods.Statistics and Computing, 22(6):1167–1180, 2012

    2012

  73. [73]

    Markov chain Monte Carlo without likelihoods.Proceedings of the National Academy of Sciences, 100(26):15324– 15328, 2003

    Paul Marjoram, John Molitor, Vincent Plagnol, and Simon Tavar´ e. Markov chain Monte Carlo without likelihoods.Proceedings of the National Academy of Sciences, 100(26):15324– 15328, 2003

    2003

  74. [74]

    Equation of state calculations by fast computing machines.The Journal of Chemical Physics, 21(6):1087–1092, 1953

    Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller. Equation of state calculations by fast computing machines.The Journal of Chemical Physics, 21(6):1087–1092, 1953

    1953

  75. [75]

    Algorithms with predictions.Communications of the ACM, 65(7):33–35, 2022

    Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions.Communications of the ACM, 65(7):33–35, 2022

    2022

  76. [76]

    Stability bounds for stationaryφ-mixing and β-mixing processes.Journal of Machine Learning Research, 11:789–814, 2010

    Mehryar Mohri and Afshin Rostamizadeh. Stability bounds for stationaryφ-mixing and β-mixing processes.Journal of Machine Learning Research, 11:789–814, 2010

    2010

  77. [77]

    Beyond worst-case online clas- sification: Vc-based regret bounds for relaxed benchmarks

    Omar Montasser, Abhishek Shetty, and Nikita Zhivotovskiy. Beyond worst-case online clas- sification: Vc-based regret bounds for relaxed benchmarks. InThe Thirty Eighth Annual Conference on Learning Theory, pages 4168–4202. PMLR, 2025

    2025

  78. [78]

    Fastε-free inference of simulation models with Bayesian conditional density estimation

    George Papamakarios and Iain Murray. Fastε-free inference of simulation models with Bayesian conditional density estimation. InAdvances in Neural Information Processing Sys- tems, volume 29, 2016

    2016

  79. [79]

    Cambridge university press, 2025

    Yury Polyanskiy and Yihong Wu.Information theory: From coding to learning. Cambridge university press, 2025. 26

    2025

  80. [80]

    Improving online algorithms via ML predictions

    Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. InAdvances in Neural Information Processing Systems, volume 31, 2018

    2018

Showing first 80 references.