simulatable-process-learning-theory

name	simulatable-process-learning-theory
description	Simulatable Processes framework for learning under dependent data with access to a simulator. Recovers PAC-style VC-dimension bounds for arbitrarily complex dependent processes, with regret controlled by time-bounded Kolmogorov complexity. COLT 2026 paper. arXiv: 2606.13576

Context

Classical learning theory (PAC learning, VC theory) relies heavily on the assumption that data samples are independent (or weakly dependent). Real-world data often exhibits strong temporal or structural dependencies, making standard generalization bounds inapplicable. The Simulatable Processes framework addresses this by introducing a new model: the learner has access to a simulator that can approximately sample from the data-generating distribution.

Core Methodology

The Simulatable Process Model

1. Setup: Data is generated by an unknown process P that may have arbitrary temporal dependencies (Markov, mixing, adversarial, etc.).

2. Simulator Access: The learner has access to a simulator S that produces samples approximately distributed according to P. The simulator need not be perfect — it only needs to be computable in bounded polynomial time.

3. Key Insight: Given simulator access, the learner can recover the same learning guarantees as classical PAC learning with independent data — error bounds depend only on the VC dimension of the hypothesis class, regardless of data dependence structure.

Main Results

1. VC-Dimension Recovery: For any VC class C, the sample complexity for learning under a simulatable process is O(VC(C)/epsilon^2), matching the classical i.i.d. bound.

2. Single Universal Algorithm: There exists 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.

3. Conditional Sampling Advantage: The framework reveals strict statistical and computational advantages when conditional sampling access is available, beyond what is possible with standard sampling.

4. PAC Model Broadening: This provides a significant conceptual extension of the classical PAC model — the independence assumption is replaced by simulator availability, which is often more realistic in practice.

Algorithm Framework

Input:
  - Hypothesis class C with VC dimension d
  - Access to simulator S for process P
  - Training data {(x_t, y_t)} from process P (dependent)
  - Accuracy epsilon, confidence delta

Algorithm:
  1. Use simulator S to generate synthetic samples
  2. Combine real and synthetic data for empirical risk minimization
  3. Output hypothesis h with generalization error bounded by O(sqrt(d/m))
     where m is effective sample size

Output: Hypothesis h with generalization guarantee matching i.i.d. bounds

Kolmogorov Complexity Regret

The regret of the universal algorithm is bounded by:

Regret <= O(sqrt(K_t(P) * VC(C) / m))

where K_t(P) is the time-bounded Kolmogorov complexity of the process P. This means simpler processes (lower Kolmogorov complexity) yield tighter bounds.

Implementation Steps

Step 1: Simulator Construction

class SimulatableProcess:
    def __init__(self, simulator, vc_class):
        self.simulator = simulator  # Callable that generates samples
        self.vc_class = vc_class     # Hypothesis class with known VC dim
    
    def generate_synthetic_data(self, n_samples):
        """Generate n_samples from the simulator"""
        return [self.simulator() for _ in range(n_samples)]

Step 2: Combined Learning

def learn_with_simulator(real_data, simulator, vc_class, epsilon):
    """
    Learn a hypothesis with i.i.d.-style guarantees
    using simulator-augmented training.
    """
    # Generate synthetic data from simulator
    n_synthetic = compute_required_synthetic_samples(vc_class.vc_dim, epsilon)
    synthetic_data = [simulator() for _ in range(n_synthetic)]
    
    # Combine real and synthetic data
    combined_data = real_data + synthetic_data
    
    # Empirical risk minimization on combined data
    hypothesis = erm(vc_class, combined_data)
    
    return hypothesis

Step 3: Conditional Sampling Enhancement

When conditional sampling is available:

def conditional_sampling_advantage(simulator, query_distribution):
    """
    Exploit conditional sampling for improved sample efficiency.
    Query simulator for P(X|Y=y) for specific values of y.
    """
    # This provides strict advantages over unconditional sampling
    # Both statistically (fewer samples needed) and computationally
    pass

Step 4: Universal Algorithm Implementation

def universal_vc_learner(vc_class, simulator, m):
    """
    Single algorithm that works for ALL simulatable processes.
    Regret bounded by time-bounded Kolmogorov complexity of process.
    """
    # Algorithm adapts to process complexity automatically
    # Simpler processes → tighter bounds
    # Complex processes → valid but looser bounds
    pass

Pitfalls

• Simulator Quality: The simulator must produce samples that are close enough to the true process distribution. If simulator bias is large, generalization guarantees degrade. Fix: Quantify simulator accuracy and incorporate into bounds.
• Computational Boundedness: The framework assumes the simulator runs in bounded polynomial time. For processes requiring exponential-time simulation, the framework does not apply. Fix: Use approximate simulators with provable approximation guarantees.
• VC Class Selection: The framework applies to VC classes. For non-VC classes (infinite VC dimension, e.g., neural networks without capacity control), alternative complexity measures (Rademacher complexity, PAC-Bayes) are needed. Fix: Extend framework using appropriate complexity measures.
• Regret vs. Accuracy: The Kolmogorov-complexity-controlled regret bound is worst-case. For specific processes, actual performance may be much better. Fix: Use process-specific analysis when process structure is known.
• Practical Simulator Design: Constructing a good simulator for real-world dependent processes is itself a hard problem. Fix: Use generative models (GANs, VAEs, diffusion models) as simulators, with validation on held-out data.

Verification

1. VC-Dimension Recovery: Verify that sample complexity matches O(VC(C)/epsilon^2) for known VC classes under dependent processes.
2. Simulator Bias Sensitivity: Test how generalization error degrades as simulator accuracy decreases.
3. Kolmogorov Complexity Correlation: Verify that processes with lower time-bounded Kolmogorov complexity achieve tighter regret bounds.
4. Conditional Sampling Advantage: Demonstrate the statistical advantage of conditional sampling over unconditional sampling on a concrete example.
5. Universal Algorithm: Test the universal algorithm across multiple process types (Markov, ARMA, adversarial) and verify consistent performance.

Activation

simulatable processes, learning with simulators, dependent data learning, VC dimension generalization, time-bounded Kolmogorov complexity, conditional sampling advantage, PAC learning extension, COLT 2026, no regret learning, bounded polynomial time simulation