cs.LGSep 26, 2026

Structuring Relations Among Learning Paradigms via Protocol--Objective--Resource Reductions

Authors: Junwei Su, Changjie Wang, Dongyang Chang

Organizations: University of Science and Technology of China

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Modern machine learning spans supervised, transfer, continual, meta-learning, and related regimes that often reuse the same hypothesis classes, architectures, and optimizers but differ in information access, objectives, memory, adaptation, and sample accounting. This makes it difficult to determine whether one paradigm is genuinely distinct, a special case of another, or part of a broader structural hierarchy. We introduce a protocol-objective-resource (POR) framework that separates representational capacity from these design choices. A paradigm is specified by an environment class, observation protocol, admissible learners, performance functional, and resource accounting rule. POR reductions combine environment embeddings, learner compilers, threshold maps, and calibrated resource overheads. Our main theorem shows that such reductions imply worst-case complexity domination on embedded comparison classes, transferring upper bounds forward and lower bounds backward; under labeled-example accounting, this yields sample complexity domination. We also show that calibrated nontrivial accuracy regimes are necessary to avoid vacuous comparisons, and that strengthening the objective can strictly increase minimax sample complexity even with unchanged protocols and learner classes. Instantiating the framework for supervised, transfer, continual, and meta-learning yields canonical special-case relations: continual contains transfer, transfer contains supervised, and meta-learning contains supervised under aligned raw-example accounting. We further derive a non-exact episode-to-example reduction for episodic meta-learning and capture within-paradigm refinements such as replay memory and task identifiers. The framework thus provides a unified language for structuring learning paradigms and transferring complexity guarantees across them.

Figures & tables

ParadigmEnvironment classControlled performance
Supervisedsingle task distribution DDpopulation risk on DD
Transfer TransK\mathrm{Trans}_{K}(D1,…,DK;D⋆)(D_{1},\dots,D_{K};D_{\star})target risk after source-then-target interaction
Continual ContK+1\mathrm{Cont}_{K+1}ordered task stream (D1,…,DK,DK+1)(D_{1},\dots,D_{K},D_{K+1})risks on all tasks together with forgetting
Metatask distribution Π\Pirandom post-adaptation population risk
Table 1: Canonical instantiations of the four representative paradigms. The table suppresses algorithmic details and keeps only the ingredients needed for POR comparisons.
More in this topic

Statistical Learning Theory

Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.

See all 561 papers

Explore similar work

CardsList
Mar 24, 2026

General Machine Learning: Theory for Learning Under Variable Regimes

We study learning under regime variation, where the learner, its memory state, and the evaluative conditions may evolve over time. This paper is a foundational and structural contribution: its goal is to define the core learning-theoretic objects required for such settings and to establish their first theorem-supporting consequences. The paper develops a regime-varying framework centered on admissible transport, protected-core preservation, and evaluator-aware learning evolution. It records the immediate closure consequences of admissibility, develops a structural obstruction argument for faithful fixed-ontology reduction in genuinely multi-regime settings, and introduces a protected-stability template together with explicit numerical and symbolic witnesses on controlled subclasses, including convex and deductive settings. It also establishes theorem-layer results on evaluator factorization, morphisms, composition, and partial kernel-level alignment across semantically commensurable layers. A worked two-regime example makes the admissibility certificate, protected evaluative core, and regime-variation cost explicit on a controlled subclass. The symbolic component is deliberately restricted in scope: the paper establishes a first kernel-level compatibility result together with a controlled monotonic deductive witness. The manuscript should therefore be read as introducing a structured learning-theoretic framework for regime-varying learning together with its first theorem-supporting layer, not as a complete quantitative theory of all learning systems.

Aomar Osmani

INSA-Rouen, France

Statistical Learning TheoryAdaptive Learning
AskPDF
Jun 1, 2026

Provable Data Scaling Law for Meta Learning via Complexity Minimization

Pre-training has become a fundamental paradigm in modern machine learning, with one of its key empirical benefits being reduced downstream sample complexity as the scale of pre-training data increases. However, existing theoretical frameworks for pre-training do not fully explain this phenomenon. In this paper, we introduce complexity minimization, a novel meta-representation learning framework designed to enable theoretical analysis of this scaling behavior, which learns representations by evaluating the downstream model complexity best suited to each domain and minimizing the worst-case such complexity across source domains. Our end-to-end theoretical analysis, spanning pre-training through downstream regression, shows that this framework provably captures this scaling behavior; in particular, we show that the error rate of few-shot adaptation improves as the amount of meta-training data grows. Empirically, we demonstrate that incorporating complexity regularization into existing meta-learning methods consistently improves downstream sample efficiency.

Kazuto Fukuchi, Ryuichiro Hataya, Kota Matsui

University of Tsukuba, Japan · RIKEN AIP, Japan · SB Intuitions Corp., Japan +3

Meta-LearningFew-Shot LearningStatistical Learning TheoryData-Efficient Learning
AskPDF
Oct 12, 2026

Learning, Compression, and Meta-Complexity

The idea that learning is closely tied to compression has long served as both a powerful principle and, at times, an informal analogy across machine learning and learning theory. Here we focus on settings in which that intuition can be made mathematically precise, surveying formal connections among learning algorithms, data compression, and computational complexity theory, with an emphasis on recent progress and current frontiers. We describe how techniques from complexity theory can guide the design of both supervised and unsupervised learning algorithms with provable guarantees, and conversely, how learning algorithms can yield new insights and results in complexity theory. A central theme is the role of data compression as a bridge between learning and complexity, especially through an area called meta-complexity, which studies the computational difficulty of compression problems and time-bounded variants of Kolmogorov complexity.

Halley Goldberg, Mikito Nanashima, Igor C. Oliveira

Department of Computer Science, University of Oxford · School of Computing, Institute of Science Tokyo · Department of Computer Science, University of Warwick

Kolmogorov ComplexityStatistical Learning Theory
AskPDF