Tag
This paper investigates scenarios where adding correctly labeled data can harm model performance, introducing insertion-stability and examining the limits of dimension-based theory in machine learning generalization.
This paper extends PAC-Bayes theory by decomposing its complexity measure using behavioral equivalence, introducing PAC-Bayes Z-information and exact structural decomposition beyond parameter space.
This theoretical paper studies atomic concept learning through the geometry of hypercubes and hyperplanes, showing that complexity collapses uniformly on most hyperplanes except the full diagonal, where it grows without bound. It provides a taxonomy of hyperplane behavior and a worked binary and ternary case analysis.
This paper studies swap-agnostic learning of proper losses, showing that prediction-level comparisons can be controlled jointly via second-order multicalibration, achieving tight rates for finite hypothesis classes and families of losses.
This paper introduces the notion of publicly-verifiable certificates of statistical validity (pvCSVs) for statistical algorithms, enabling distributionally-robust certification of learning results without interaction. The authors construct pvCSVs for adaptive Statistical Query algorithms with sample complexity scaling logarithmically in the number of queries.
An essay critiquing the common conflation of optimization and learning in neural network research, arguing that training should be understood as inverse reconstruction and studied through the evolving homology of weight-defined piecewise manifolds.
This paper addresses open questions in the Gold-Angluin model of language identification in the limit, showing that computational traces using only a small alphabet and defined directly from the language enable identification in the limit, without requiring an underlying machine model.
This paper introduces a formal definition of 'machine-learnable sets' based on bounded-complexity Boolean autoencoders that fix set elements, with experiments using Boolean threshold networks to demonstrate learnability for Rorschach patterns and wild sets.
This paper develops a precise theoretical characterization of the empirical risk landscape for multi-index models in high dimensions, proposing an incremental approximate message passing (IAMP) algorithm that achieves near-optimal performance among polynomial-time methods, using concepts from statistical physics such as replica symmetry breaking.
This paper proves that EML trees, which represent elementary functions through composition, are universal approximators for continuous functions and other functional spaces. The proof constructs EML representations of basic operations and uses them as building blocks.
This paper introduces Bernstein–Schur kernels, a class of nonstationary kernels between shift-invariant and dot-product templates, and provides a random feature construction by sketching the finite modulation and randomizing the completely monotone radial factor. The method yields unbiased estimators with operator-norm bounds controlled by intrinsic dimensions, and experiments validate the approach on a biased kernel example.
This paper studies nonconvex stochastic optimization under Blum-Gladyshev noise, where gradient variance grows with distance from initialization. It proves convergence guarantees for normalized SGD with momentum and a variance-reduced STORM method, achieving minimax optimal rates under certain conditions.
This paper derives tight theoretical bounds for human-AI teams, proving when confidence-based aggregation leads to complementarity and establishing impossibility results under specific error correlations.
This arXiv preprint proposes a unified measure-theoretic framework for understanding diffusion, score-based, and flow matching generative models. It establishes connections between these methods via continuity/Fokker-Planck equations and analyzes their sampling schemes and theoretical guarantees.
This paper proposes a unified framework for energy-based generative models by casting density transport as a nonlinear control problem with KL divergence as a Lyapunov function. It derives finite-step stopping criteria and demonstrates how nonlinear control theory tools can be applied to static scalar energy models.
This article explains how incorporating Shannon entropy into reinforcement learning objectives creates more robust agents capable of handling unexpected or adversarial changes in rewards and dynamics.
This paper extends the study of computational hardness in learning robust classifiers, showing that efficient robust classification can be impossible even when unbounded robust classifiers exist, and establishing a win-win result: either an efficient robust classifier can be learned, or new cryptographic primitives can be constructed.