mlsanityData to 7 Oct 2026

Pool-based Active Learning as Noisy Lossy Compression: Characterizing Label Complexity via Finite Blocklength Analysis

arXiv 2602.05333 ↗First posted 5 Feb 2026cs.LG cs.IT math.ITcited by 0

Not on the map. Why?

Abstract (arXiv)

This paper proposes an information-theoretic framework for analyzing the theoretical limits of pool-based active learning (AL), in which a subset of instances is selectively labeled. The proposed framework reformulates pool-based AL as a noisy lossy compression problem by mapping pool observations to noisy symbol observations, data selection to compression, and learning to decoding. This correspondence enables a unified information-theoretic analysis of data selection and learning in pool-based AL. Applying finite blocklength analysis of noisy lossy compression, we derive information-theoretic lower bounds on label complexity and generalization error that serve as theoretical limits for a given learning algorithm under its associated optimal data selection strategy. Specifically, our bounds include terms that reflect overfitting induced by the learning algorithm and the discrepancy between its inductive bias and the target task, and are closely related to established information-theoretic bounds and stability theory, which have not been previously applied to the analysis of pool-based AL. These properties yield a new theoretical perspective on pool-based AL.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 22 of its 41 references that are in the map. First posted on arXiv 5 Feb 2026.

Builds on

22 of 41 references.

References · 22

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  3. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  4. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  5. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  6. 2020Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networkscited by 166
  7. 2021Batch Active Learning at Scalecited by 127
  8. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  9. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  10. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 79
  11. 2014Minimax Analysis of Active Learningcited by 61
  12. 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
10 more
  1. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  2. 2022Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problemscited by 25
  3. 2021Exponential Savings in Agnostic Active Learning through Abstentioncited by 23
  4. 2014Beyond Disagreement-based Agnostic Active Learningcited by 21
  5. 2022Fast Rates in Pool-Based Batch Active Learningcited by 15
  6. 2023Time-Independent Information-Theoretic Generalization Bounds for SGLDcited by 12
  7. 2017Diameter-Based Active Learningcited by 7
  8. 2023Model-agnostic Measure of Generalization Difficultycited by 7
  9. 2024Towards Exact Computation of Inductive Biascited by 5
  10. 2020Generalization Error Bounds via mth Central Moments of the Information Densitycited by 4

Built on by

Not cited yet.