Universal masking channels generalize hardcore lemma
Masking channels certify hardness of non-Boolean function learning via convex duality on fidelity.
Stories per day · 30 days
1 RSS
Relatedconcentration-inequalities1convex-duality1credit-assignment1gaussian1generalization1hardcore-lemma1hermite-tensors1masking-channels1multi-agent1neural-networks1non-iid1pac-learning1performative-prediction1pseudoentropy1regenerative-processes1relu1stability1stochastic-gradient1
22 stories, newest first · one card per story
Stories tagged #learning-theory
Intermittent noisy gradients can leave learning variance unbounded
Average dynamics may still reach the correct optimum while learning variance grows without bound.
Fully polynomial algorithm learns positive linear combinations of ReLUs
The method uses poly(d, k, 1/ε) samples and time under Gaussian inputs and L2 loss, without well-conditioned weight assumptions.
Bernstein bounds for regenerative data yield non-i.i.d. generalization guarantees
The bounds support agnostic classifiers from a first-order term and are minimax-optimal in sample size and expected regeneration time.
Paper finds a spectral threshold for multi-agent performative prediction
Stability fails when the spectral radius of the reflexivity matrix crosses one, with linear excess loss above it.
Prediction Is Not a Sufficient Memory State
Theory shows a fixed recurrent memory matching current predictions can still be insufficient for future learning.
Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate
Compression-based learning risk bounds match the law-of-large-numbers rate without a logarithmic penalty.
Why Forget-Only Unlearning Needs Memorization
A theory paper shows forget-only machine unlearning can require memorizing far more training data than ordinary learning keeps.
Private online learning and prediction for Littlestone classes
Differentially private online learning of Littlestone classes needs more mistakes than private prediction.
Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD
Paper proves a sharp Gaussian approximation for the stationary law of constant-stepsize SGD.
Learning Shuffle Ideals with Membership Queries and Contrastive Examples
Paper shows many shuffle ideals are not efficiently learnable from membership or contrastive queries.
Even Sharper Bounds for Transductive Learning and Its Applications
STLC matches inductive excess-risk rates for transductive learning without an extra logarithmic confidence factor.
Double descent is the principle of least action
A statistical mechanics analysis explains double descent: finite-time diffusion induces effective weight decay that regularizes models as parameters grow.
Fast Learning Rates for Physics-Informed Kernel Methods
Theoretical analysis proves finite-sample learning rates for physics-informed kernel estimators, showing differential observations can improve rates from n^-1/4 to n^-1/2.
Benign Loss Landscapes Can Coexist with Worst-Case Hardness
Theory paper shows tree tensor networks contain worst-case hard targets yet benign loss landscapes, with difficulty arising from degenerate saddles.
General Quantification of Covariate and Concept Shifts
Paper proposes γ*-concept shifts via entropic optimal transport, deriving estimable generalization bounds unifying covariate and concept shift under distribution shift.
A positive resolution of the gap-entropy conjecture
New proof resolves the gap-entropy conjecture for Gaussian bandits, bounding optimal best-arm identification samples by H(log(1/delta)+Ent(I)) up to constants.
Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarch
New work characterizes language generation in the limit via finite witnesses, proves a full separation-width hierarchy, and formalizes all results in Lean.
Algorithmic stability via ensembling
Theoretical work derives a general framework quantifying stability guarantees for averaging-based ensembles under arbitrary data perturbations via covariance operator norms.
Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks
Theory paper derives nearly tight Rademacher complexity bounds for sparsely activated one-hidden-layer ReLU networks.
A Generalization of Amari's Bayesian Duality
Paper generalizes Amari's Bayesian duality by connecting it to a convex duality of Bayes' rule.
A Theoretical Analysis of Generalization Dynamics in Neural Networks under Gradient Descent with Weight Decay
Theoretical framework bounds generalization for gradient descent with weight decay, deriving conditions that explain delayed generalization and grokking.