learning-theory

A unified framework for estimating the probability of data-dependent events, covering missing mass, adaptive data analysis, and test-error estimation, with new hybrid Good–Turing style estimators and bounds based on VC dimension and mutual information.

该论文研究了在无限混合可适当损失（mixable proper losses）类别下的 omniprediction 问题，证明了对所有有界适当损失无法实现次线性遗憾，但给出了对所有混合可适当损失的最优 O~(T^{1/3}(log|F|)^{2/3}) 遗憾界，并提出了一种同时兼顾有限损失类别的 best-of-all-worlds 算法。

A preprint proposing Verification Learning Theory (VLT), a formal process model of how AI-assisted claim checking affects retention of independent judgment, predicting that perceived assistant fallibility can improve delayed unaided performance through evidence checking.

该论文提出 Fiber Regulation Theory (FRT) 与 Fiber Acquisition Theory (FAT) 两个理论框架，刻画受保护的功能修复与可训练结构的形成/续期动力学，并在 Qwen2.5-32B 上通过受保护头修复与固定容量 LoRA 续期验证联合策略优于单独策略。

该论文研究极限下的语言生成问题，提出了比稳定性更强的可认证性概念，并引入了正确性、稳定性和可认证性三个层级的教学维度，给出了稳定生成的有限见证刻画，解决了文献中遗留的理论空白。

论文提出一种对抗鲁棒的广义编码计算（GCC）扩展框架，通过平滑正则化限制恶意worker输出的影响，并给出随对抗worker比例衰减的非渐近误差界，适用于分布式系统中的近似编码计算。

The paper analytically studies Dense Associative Memories trained on codewords of random expander LDPC codes, identifying a memorization-to-generalization transition reminiscent of grokking. It introduces a thresholding learning rule that achieves sample-efficient learning with only O(log n) training samples and enables the emergence of latent variable representations.

本文研究模型误设下的有界回归问题，分析了 sign-betting regression 估计器在 L1 度量下的高概率 oracle 不等式，并证明了 proper learning 的最优通用近似因子为 3。

Harvard researchers develop a statistical learning theory of size generalization, proving an exponential separation in sample complexity between in-domain and cross-size learning, along with dimension-free scaling laws and matching minimax lower bounds.

A discussion post asking for the strongest mechanistic and first-principles argument that next token prediction combined with reinforcement learning can yield open-ended general intelligence, rather than relying on trend extrapolation or appeals to future breakthroughs.

Paccagnan and Tirlea (Imperial College London) prove that state-of-the-art concentration bounds for preferent (stable) sample compressions are provably tight, using an explicit uniform-distribution/order-statistics construction, while also giving a much simpler elementary counting proof that avoids infinite-dimensional duality.

This paper improves the optimal expected mistake bound for randomized proper online learning, showing it is O(L(H) log T), which is optimal up to a universal constant for worst-case classes.

The paper presents a dynamical mean-field theory for learning-induced transitions in recurrent neural networks, showing how feedback-driven learning shifts network dynamics from chaos to stability.

This paper resolves whether Empirical Risk Minimization is relatively smart for binary classification, explores semi-supervised learning with quadratic blowup in unlabeled data, and proves intractability results for certain learners.

This paper introduces General Coded Computing (GCC), a learning-theoretic framework for mitigating stragglers in distributed computing systems, providing theoretical performance guarantees and experimental validation on deep neural networks.

This paper investigates the limits of proper learning and regularization in multiclass learning, resolving open problems by demonstrating that learning cannot always be reduced to proper learning and that regularization has structural constraints.

This paper presents a new logarithmic-free upper bound for the generalization gap in uniformly stable algorithms and constructs a deterministic learning problem that achieves optimal high-probability dependence, closing a gap in the literature.

This paper develops constructive approximation and learning guarantees for shallow neural models with infinite-dimensional inputs, separating errors into coordinate-truncation, network width, and sample size components for a unified theoretical analysis.

This paper presents KnowSim, an evaluation framework that models user knowledge states to assess information calibration in LLM assistants, validated against human judgments and outperforming baseline simulators.

This paper answers an open question from Hanneke, Moran, and Waknine by showing that the agnostic PAC learning curve of a direct sum is not determined solely by the single-instance learning curve and the number of factors, providing a rate separation.