The ε-Streamably-Learnable Class: A Constructive Framework for Operator-Based Optimization

We introduce the ε-Streamably-Learnable (ESL) class, a novel complexity class that bridges the theoretical gap between learnable and streamable optimization problems. ESL is defined as the closure of streamable problems under the uniform residual metric, capturing the empirical observation that even non-streamable problems can be approximated arbitrarily well by efficient low-rank operator surrogates. Building upon the established three-tier hierarchy of optimization problems, we prove that every learnable problem belongs to ESL, providing a constructive pathway from theoretical learnability to practical computational efficiency. Our main contributions include: (1) the formal definition and characterization of the ESL class with rigorous inclusion relationships and explicit mathematical foundations; (2) a constructive ESL-Convert algorithm that transforms any learnable problem into a streamable approximation with controllable error bounds and proven correctness guarantees; (3) detailed stability analysis for control applications with explicit contraction assumptions; (4) comprehensive case studies with complete reproducibility details for neural network training and federated learning scenarios. The ESL framework resolves the apparent contradiction between theoretical limitations of streamable optimization and the widespread practical success of low-rank methods. Numerical experiments across CNNs, transformers, and federated settings show up to 100× reductions in compute/communication with maintained convergence guarantees and explicit error bounds.