Learning with Simulators: No Regret in a Computationally Bounded World

2026-06-12 · Source: stat.ML updates on arXiv.org · Field: Science & Research — Mathematics & Computational Sciences, Artificial Intelligence & Machine Learning, Research Methodology & Innovation · Depth: Expert, extended

Summary

A new framework, "simulatable processes," addresses generalization in learning theory for strongly dependent data, a gap where most results rely on data independence. This framework assumes learner access to a simulator approximating the data-generating distribution. Surprisingly, it recovers classical learning guarantees, with error bounds dependent on VC dimension. The research highlights a single algorithm that learns any VC class under processes samplable in bounded polynomial time, with regret controlled by time-bounded Kolmogorov complexity. Furthermore, the framework demonstrates strict statistical and computational advantages with conditional sampling, enabling agnostic learning and efficient algorithms for processes like Linear Dynamical Systems and Glauber dynamics, even without mixing assumptions.

Key takeaway

For research scientists developing learning algorithms for real-world, dependent data, this work suggests a paradigm shift. You should explore integrating approximate simulators, especially conditional ones, into your models. This approach can recover strong statistical and computational guarantees, even for complex processes where traditional independence assumptions fail. Consider the trade-off between unconditional and conditional simulator access based on your specific problem's structure and computational constraints.

Key insights

Simulators enable classical learning guarantees for complex, dependent data, broadening the PAC model.

Principles

• Learning with simulators recovers VC dimension-based error bounds.
• Conditional sampling offers statistical and computational advantages.
• A universal algorithm learns VC classes under polynomial-time samplable processes.

Method

The framework uses a multi-scale algorithm (MultiCover) for unconditional simulators and a Log-MGF relaxation with epoching for conditional simulators to control regret.

In practice

• Generative models (LLMs, diffusion models) can serve as accurate simulators.
• Apply conditional simulators to learn non-mixing Markov chains like LDS or Glauber dynamics.

Topics

• Simulatable Processes
• VC Dimension
• Online Learning
• Conditional Sampling
• Kolmogorov Complexity
• Kullback–Leibler Divergence

Best for: AI Scientist, Research Scientist

Related on AIssential

• Kernel-based guarantees for nonlinear parametric models in Bayesian optimization — A kernel-based framework provides theoretical guarantees for nonlinear parametric models in adaptive optimization.
• 2 Years of My Research Explained in 13 Minutes — Discrete representations enhance learning efficiency and adaptation in reinforcement learning, especially under capacity constraints or dynamic environments.
• I got frustrated teaching ML to scientists, so I started building domain-specific workshops – would love your thoughts — Standard ML education often fails to address the unique data constraints and uncertainty requirements of scientific research.
• Partial Causal Structure Learning for Valid Selective Conformal Inference under Interventions — Selective conformal prediction under interventions can be robustly maintained by learning partial causal structures.
• Robust Simulation-Based Inference Under Missing Data via Neural Processes — RISE jointly learns data imputation and parameter inference in SBI to robustly handle missing data and prevent biased posteriors.
• The Power of Test-Time Training for Approximate Sampling — Test-Time Training (TTT) for approximate sampling is formalized, revealing that its query complexity can be circumvented by bounding the distribution class size.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.