Sasha Voitovych, Abhishek Shetty, Noah Golowich, Alexander Rakhlin
Even when data is strongly dependent, access to a simulator can recover the same learning guarantees (VC dimension-based error bounds) as with independent data, and a single algorithm that controls regret by time-bounded Kolmogorov complexity is presented.
The fundamental question in machine learning theory is understanding the minimal assumptions necessary for generalization. Most results rely heavily on independence (or some proxy) of the data-generating process, but results for strongly dependent data are very limited. This research aims to uncover conditions under which learning is possible even in processes with strong dependence.
The authors 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). Using this simulator, they show that the same learning guarantees (error bounds based on VC dimension) as in the independent data setting can be recovered. They also study the power of conditional sampling and demonstrate statistical and computational advantages in this setting. As a key result, they present a single algorithm that simultaneously learns any given VC class under all processes samplable in polynomial time, with regret controlled by the time-bounded Kolmogorov complexity of the process.
This research conceptually extends the classical PAC model, showing the possibility of generalization even in strongly dependent data environments. By leveraging access to a simulator, it proves that learning guarantees based on VC dimension can be achieved without independence assumptions, and demonstrates the statistical and computational advantages of conditional sampling. This provides a theoretical foundation for various real-world problems such as dependent time series data and reinforcement learning in complex environments.