📐 Learning Theory

🔬 ICLR2026 · 293 paper notes

📌 Same area in other venues: 🧪 ICML2026 (45) · 🤖 AAAI2026 (3) · 🧠 NeurIPS2025 (25) · 🧪 ICML2025 (16)

🔥 Top topics: Adversarial Robustness ×16 · Diffusion Models ×15 · Continual Learning ×5 · Alignment/RLHF ×4 · Image Restoration ×3

A Biologically Plausible Dense Associative Memory with Exponential Capacity

By replacing the "winner-take-all" activation in the hidden layer of a dual-layer associative memory with a thresholded step activation, hidden neurons can participate in multiple memories simultaneously (distributed representation). This increases storage capacity from "linear in the number of hidden neurons" to "exponential in the number of hidden neurons" (\(2^{N_h}\)). The model was validated on MNIST/CIFAR-10, demonstrating the ability to store tens of thousands of highly correlated images while maintaining biological plausibility.

A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyond

This paper proposes a general derandomization lemma based on \(\rho\)-SOSP, proving that under Gaussian inputs, smooth targets, and minimal weight regularization, second-order stationary points automatically suppress random linear components. This mechanism explains the low-rank structure discovery of first-layer weights in neural networks and extends to deterministic constructions for MAXCUT rounding and Johnson-Lindenstrauss embeddings.

A Faster Parameter-Free Regret Matching Algorithm

This paper proposes a parameter-free regret matching variant MI-SPRM+. By using a technique called "Adaptive Regret Domain (ARD)" to monotonically raise the lower bound of the cumulative regret's 1-norm, it preserves the parameter-free property while achieving an \(O(1/T)\) theoretical convergence rate in two-player zero-sum games—making it the first RM-type algorithm known to achieve both simultaneously.

A Generalized Geometric Theoretical Framework of Centroid Discriminant Analysis for Linear Classification of Multi-dimensional Data

This paper proposes a unified theoretical framework called Geometric Discriminant Analysis (GDA), which views a class of linear classifiers as a "connection between two class centroids (CDB0) + geometric corrections under different constraints." It proves that MDC and LDA are special cases of this framework. Based on this, a new classifier, CDA, is designed. Starting from CDB0, CDA performs "performance-driven rotations" on a series of 2D planes using Bayesian optimization. This approach reduces training complexity from cubic (LDA/SVM) to quadratic, achieving better performance, scalability, and stability than LDA/SVM/LR across 27 real-world datasets.

A Minimum Variance Path Principle for Accurate and Stable Score-Based Density Ratio Estimation

This paper identifies the root of the "theoretical path-invariance vs. practical path-sensitivity" paradox in score-based density ratio estimation as a neglected term—the path variance of the score function. The authors propose the Minimum Variance Path (MVP) principle to explicitly incorporate this term into the objective and use the Kumaraswamy Mixture Model to parametrize the path as a learnable function, achieving more accurate and stable density ratio estimation across multiple challenging benchmarks.

A Near-Optimal Best-of-Both-Worlds Algorithm for Federated Bandits

This paper proposes FEDFTRL—the first algorithm in federated multi-armed bandits to simultaneously achieve near-optimal individual regret bounds for both stochastic and adversarial environments. The core approach involves reinterpreting the "information delay induced by decentralized communication" as "delayed feedback bandits," and utilizing FTRL with a hybrid regularizer paired with a truncated loss estimator and a bias-recording communication scheme, reducing the adversarial regret from the previous SOTA \(O(T^{2/3})\) to \(O(T^{1/2})\).

A New Approach to Controlling Linear Dynamical Systems

This paper proposes Online Spectral Control (OSC): the control problem of linear dynamical systems under adversarial perturbations is transformed via convex relaxation using a set of system-independent "spectral filters" (eigenvectors of a specific Hankel matrix). While maintaining an optimal regret of \(\tilde O(\gamma^{-4}\sqrt T)\), it reduces the per-step runtime dependency on the stability margin \(\gamma\) from polynomial \(O(\gamma^{-1})\) to logarithmic \(O(\mathrm{polylog}(1/\gamma))\).

A New Initialization to Control Gradients in Sinusoidal Neural Networks

This paper derives a set of closed-form initialization parameters for the sinusoidal activation network SIREN. By simultaneously controlling the pre-activation distribution, inter-layer Jacobian variance, and spectral expansion, it reduces gradient explosion and spurious high-frequency noise in deep sinusoidal neural networks for tasks such as function fitting, image/audio/video reconstruction, and PINNs.

A Sharp KL Convergence Analysis for Diffusion Models under Minimal Assumptions

This paper provides a sharper KL divergence convergence analysis for diffusion models (DDPM samplers) under the minimal assumption of "only \(L^2\) accuracy of score estimation, without assuming any smoothness." By modeling the generation process as "one-step probability flow ODE + one small noise-addition step" and developing new proof techniques to handle the second-order spatial derivatives of the score (Laplacian), the iteration complexity required to achieve \(\varepsilon^2\)-KL is improved from the previous best \(\tilde O(d/\varepsilon^2)\) to \(\tilde O(d/\varepsilon)\). This reduces the dependence on accuracy \(\varepsilon\) from quadratic to linear while maintaining linear dependence on the dimension \(d\).

A Statistical Learning Perspective on Semi-dual Adversarial Neural Optimal Transport Solvers

This paper provides the missing statistical learning theory for a class of generative methods that use adversarial minimax solvers for quadratic optimal transport: it proves that the generalization error between the learned transport map and the true OT map can be decomposed into estimation error + approximation error. The estimation error is controlled solely by the Rademacher complexity of the network function classes, while the approximation error can be made arbitrarily small by choosing appropriate networks, thereby providing the first \(O(1/\sqrt{N})\) convergence guarantee.

A Statistical Theory of Overfitting for Imbalanced Classification

This paper establishes a statistical theory for high-dimensional imbalanced linear classification: under a two-class Gaussian Mixture Model (2-GMM), test logits follow \(N(0,1)\), while training logits converge to \(\max\{\kappa, N(0,1)\}\) (rectified Gaussian). A variational problem characterizes how this "truncation" occurs as a function of dimensionality, rigorously explaining why minority classes suffer more from overfitting, why margin rebalancing is effective, and how overfitting exacerbates confidence calibration.

A Theoretical Analysis of Mamba's Training Dynamics: Filtering Relevant Features for Generalization in State Space Models

This paper provides the first characterization of the Gradient Descent (GD) training dynamics of Mamba (a selective SSM with input-dependent gating) from a feature learning perspective. It proves that under two types of structured data, the gating vector \(w_\Delta\) automatically aligns with class-relevant features and suppresses irrelevant ones. The authors provide non-asymptotic sample complexity and convergence rate bounds, theoretically answering "when and why Mamba can learn and generalize efficiently."

A Unification of Discrete, Gaussian, and Simplicial Diffusion

This paper proves that three seemingly unrelated discrete sequence generation methods—discrete, Gaussian, and simplicial diffusion—are actually different parameterized limits of the Wright-Fisher model from population genetics. Using this unified theory, it stabilizes simplicial diffusion (which previously suffered from numerical divergence, achieving SOTA in conditional DNA generation) and allows a single network to switch between the three diffusion domains arbitrarily at test time.

Achieving Approximate Symmetry Is Exponentially Easier than Exact Symmetry

This paper defines a quantifiable cost for "forcing model symmetry"—averaging complexity—and proves an exponential separation: under standard conditions, forcing exact symmetry requires a number of queries linear in the group size \(|G|\), while forcing approximate symmetry requires only logarithmic queries \(O(\log|G|/\varepsilon)\). This provides the first theoretical explanation for "why approximate symmetry is often more cost-effective than exact symmetry in practice."

Adaptive Conformal Prediction via Mixture-of-Experts Gating Similarity

This paper proposes MoE-CP, which utilizes the gating probabilities of a Mixture-of-Experts (MoE) model as soft domain memberships. By weighting calibration residuals based on gating similarity, it allows prediction intervals to adaptively widen or narrow according to the noise and residual distributions of latent subgroups while maintaining marginal coverage guarantees for conformal prediction.

Adaptive Hopfield Network: Rethinking Similarities in Associative Memory

This paper redefines associative memory retrieval from "being sufficiently close to a stored pattern" to "finding the source memory most likely to have generated the current query." By constructing an adaptive Hopfield network (A-Hop) with a learnable similarity footprint, it significantly outperforms fixed-similarity Hopfield variants on tasks involving mixed noise, occlusion, bias, and multi-class classification.

Ads that Stick: Near-Optimal Ad Optimization through Psychological Behavior Models

This paper incorporates three psychological effects—"mere exposure," "hedonic adaptation," and "operant conditioning"—into a continuous-time ad reward model. It demonstrates that when the number of ads is fixed, the optimal schedule is determined solely by the decay loss of "operant conditioning." The authors provide a quasi-linear time, near-optimal scheduling algorithm with exponentially small error, revealing that common heuristics like "uniform spacing" are actually suboptimal in many scenarios.

Adversarially Pretrained Transformers May Be Universally Robust In-Context Learners

This paper provides the first theoretical analysis showing that a single-layer linear Transformer, adversarially pretrained on multiple classification tasks, can achieve adversarial robustness on unseen new classification tasks using only clean in-context learning (ICL) examples—without any additional adversarial training or adversarial examples, as the model learns to adaptively focus on "robust features."

Algorithmic Guarantees for Distilling Supervised and Offline RL Datasets

This paper provides the first set of provable algorithmic guarantees for dataset distillation without training models. For linear regression, it proves that convex loss matching using \(\tilde O(d^2)\) randomly sampled regressors yields a synthetic dataset that maintains nearly identical MSE for any bounded linear model, complemented by a matching \(\Omega(d^2)\) lower bound. The method is further extended to offline RL through Bellman loss matching, achieving similar guarantees and validation in toy RL environments.

Almost Bayesian: Dynamics of SGD Through Singular Learning Theory

This paper describes long-run SGD as diffusion in porous media on a singular loss landscape, characterizes the geometric complexity of reachable low-loss regions using the local learning coefficient, and derives that the steady-state distribution of SGD is approximately equal to a Bayesian posterior corrected by reachability temperature.

Alternating Diffusion for Proximal Sampling with Zeroth Order Queries

This paper replaces the "reverse denoising" step in proximal sampling—traditionally implemented via rejection sampling—with direct SDE simulation. By using a Gaussian mixture model (GMM) formed by the current particles as a surrogate distribution, it performs Monte Carlo score estimation using only function values (zeroth-order) of \(f\). The result is a sampler that requires no gradients, no rejection sampling, and no model training with a fixed runtime. Theoretically, it inherits the exponential convergence of proximal sampling under isoperimetric conditions, and experimentally, it is nearly an order of magnitude faster than RGO-based proximal sampling.

An Efficient, Provably Optimal Algorithm for the 0-1 Loss Linear Classification Problem

Proposes the Incremental Cell Enumeration (ICE) algorithm, the first standalone algorithm with a formal proof that can exactly solve the global optimum of the 0-1 loss linear classification problem in \(O(N^{D+1})\) time, with extensions to polynomial hypersurface classification.

SEINT: An Efficient SE(p)-Invariant Transport Metric Driven by Polar Transport Discrepancy-based Representation

This paper proposes SEINT, a distribution distance that is strictly invariant to translation and rotation (the Special Euclidean group \(SE(p)\)) and proven to be a true metric (satisfying the triangle inequality). It utilizes training-free "Polar Transport Discrepancy (PTD)" to encode high-dimensional distributions into 1D scalar features, then restores intrinsic geometric information using "Distance Convolutional PTD (DcPTD)." By computing the Wasserstein distance in 1D, the complexity is reduced from \(O(n^3)\sim O(n^4)\) of GW to \(O(n\log n)\sim O(n^2)\). Effectiveness is validated on point cloud classification (100% accuracy) and 3D molecule generation (SOTA stability).

An evolutionary perspective on modes of learning in Transformers

Borrowing the perspective of "phenotypic plasticity vs. genetic assimilation" from evolutionary biology, this paper explains the Transformer's selection between In-Context Learning (ICL) and In-Weight Learning (IWL) as a manifestation of learning dynamics determined by environmental stability, cue reliability, and the inherent learning costs of different strategies.

An Improved Model-free Decision-estimation Coefficient with Applications in Adversarial MDPs

This paper proposes Dig-DEC—a model-free Decision-Estimation Coefficient driven purely by information gain without optimism. It is consistently no larger than the existing optimistic DEC, enabling the first model-free learning for mixed MDPs (stochastic transitions + adversarial rewards) under bandit feedback, while tightening regret rates for online function estimation from \(T^{3/4}/T^{5/6}/T^{2/3}\) to \(T^{2/3}/T^{7/9}/\sqrt{T}\).

An Optimal Diffusion Approach to Quadratic Rate-Distortion Problems: New Solution and Approximation Methods

This paper reformulates the calculation of the Rate-Distortion (RD) function for continuous sources under MSE distortion as a "Terminal-Entropy Regulated Stochastic Control" problem. It proves that the rate-distortion tradeoff is equivalent to the control energy-terminal entropy tradeoff and identifies that under regularity conditions, the optimal control is precisely the Stein score of the solution to the backward heat equation. This yields new closed-form solutions for sources like Gaussian mixtures and introduces R2D2, a diffusion neural estimator free from rate upper bound constraints.

ATLAS: Alibaba Dataset and Benchmark for Learning-Augmented Scheduling

This paper cleans and performs feature engineering on the Alibaba PAI-2020 GPU cluster trace to create ATLAS, a "non-clairvoyant scheduling" dataset containing 730,000 jobs with ground-truth job duration labels. It introduces an end-to-end benchmark, LASched, which evaluates both prediction tasks (estimating job duration using features available at submission) and scheduling tasks (using predictions to optimize total completion time, max stretch, and makespan). This allows "algorithm + prediction" theories, previously confined to synthetic data, to be fairly reproduced and compared on real-world workloads.

Automata Learning and Identification of the Support of Language Models

This paper systematically characterizes the learnability of regular languages under "Next Symbol Prediction (NSP)" supervision. It proves that while NSP labels ensure identifiability, they cannot bypass computational hardness. Furthermore, it proposes the L*_nsp algorithm—leveraging a language model as a "teacher" to efficiently extract a DFA that approximately characterizes its generative support set.

Bandit Learning in Matching Markets Robust to Adversarial Corruptions

This paper investigates the decentralized bilateral matching market bandit learning problem under feedback corrupted by an adversary for the first time. It provides robust algorithms for cases where the total corruption \(C\) is known and unknown: for known \(C\), the confidence intervals of the classic ETGS are widened; for unknown \(C\), a "multi-layer ETGS racing + sub-phase level synchronization" approach is used to adaptively resist arbitrary corruption. The paper proves player-optimal stable regret upper bounds and a matching lower bound.

Bandits with Single-Peaked Preferences and Limited Resources

The paper introduces the "single-peaked preference" structure from social choice theory into online matching bandits with budget constraints. By bypassing the NP-hardness of the general case, it provides polynomial-time efficient algorithms with regrets of \(\tilde{O}(UK T^{2/3})\) (unknown structure) or \(\tilde{O}(U\sqrt{TK})\) (known structure).

Barriers for Learning in an Evolving World: Mathematical Understanding of Loss of Plasticity

This paper redefines "Loss of Plasticity (LoP)" from a dynamical systems perspective as gradient trajectories being trapped within invariant submanifolds of the parameter space. It proves that frozen and cloned units form such "trap manifolds" and presents a counter-intuitive conclusion: the very low-rank compression mechanisms that promote generalization in static tasks are what drive the network into these plasticity-depleted manifolds.

Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scaling

This paper formalizes LLM Pass@k inference (sampling \(N\) candidates, submitting at most \(k\), and evaluating the best one) as a regret minimization problem. It proves that both majority voting and Best-of-N are sub-optimal in this setting. The authors propose the Best-of-Majority (BoM) strategy—which "pre-screens by frequency and then selects top-\(k\) by reward"—and provide a regret upper bound of \(\tilde O(\epsilon_{\mathrm{opt}}+\sqrt{C^*\epsilon_{\mathrm{RM}}^2/k})\) with a matching lower bound, establishing the first minimax-optimal algorithm for Pass@k inference.

Best-of-N through the Smoothing Lens: KL Divergence and Regret Analysis

This paper analyzes the commonly used Best-of-N (BoN) inference-time alignment through a "softened" framework, Soft Best-of-N (SBoN). It provides KL divergence upper bounds relative to the reference policy and upper/lower regret bounds relative to the optimal policy. The authors prove that when the proxy reward model quality is poor and overoptimization occurs, a finite inverse temperature \(\beta\) makes the regret bound for SBoN tighter than that for BoN, thereby mitigating reward hacking.

Better Bounds for the Distributed Experts Problem

This paper investigates the distributed online prediction problem where "experts are distributed across multiple servers and losses are aggregated across servers according to the \(\ell_p\) norm." It proposes a suite of protocols based on exponential random variable embedding combined with geometric mean variance reduction. It is the first to handle general \(\ell_p\) losses in the coordinator (message-passing) model, achieving a communication complexity of \(\left(\tfrac{n+s}{R^2}\right)\cdot\max(s^{1-2/p},1)\cdot\mathrm{polylog}(nsT)\) bits for a target regret \(R\), outperforming prior work that was limited to \(\ell_1\).

Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion

This paper generalizes the previous "one representative per component" Metric Forest Completion (MFC) approximation algorithm into MultiRepMFC, which selects "a set of representatives per component." It provides an instance-specific \(\alpha\)-approximation bound using a cheaply computable cost function, while tightening worst-case approximation ratios from \(2.62\) (MFC) and \(2\gamma+1\) (Metric MST) to \(2\) and \(2\gamma\). The tightness of these bounds is proven, and the algorithm is shown to approach optimal spanning tree quality with minimal extra computation.

Beyond Spectra: Eigenvector Overlaps in Loss Geometry

The local loss geometry of machine learning is essentially a "two-operator" problem: the training loss and the test loss each have a Hessian. Analyzing their respective spectra (eigenvalues) alone is insufficient; what truly determines generalization is the alignment (eigenvector overlap) between the two Hessian eigenspaces. This paper establishes a universal fluctuation law, a noise propagation law, and provides a scalable overlap estimation algorithm for ResNet.

Bi-Criteria Metric Distortion

This paper generalizes the "metric distortion" framework from "selecting a single winner" to "committees of \(k\) candidates compared against the optimal single candidate." It proves that on a 1D line, only 2 candidates (for the sum objective) or 4 candidates (for the maximum objective) are sufficient to eliminate distortion (1-distortion = 1). In contrast, this is unachievable in 2D Euclidean or tree metrics even with \(m-1\) candidates, revealing a sharp divide between line metrics and higher-dimensional metrics.

Bi-Lipschitz Autoencoder With Injectivity Guarantee

This paper identifies "encoder non-injectivity" as the root cause of regularized autoencoders falling into poor local optima. It proposes an injectivity regularizer based on the \((\delta,\epsilon)\)-separation criterion and replaces the rigid isometric constraint with a Bi-Lipschitz regularizer acting on the decoder's Jacobian singular values. The resulting BLAE preserves geometric structure with high fidelity on multiple manifold datasets and remains robust to sparse sampling and distribution shifts.

Boosting for Predictive Sufficiency

This paper introduces the information-theoretic concept of \(\alpha\)-predictive sufficiency. It theoretically demonstrates that boosting outperforms specialized methods in tabular OOD tasks under hidden confounding shifts because it implicitly partitions data into "reference classes/environments" aligned with hidden confounders, maximizing predictive information within each environment.

Bound by Semanticity: Universal Laws Governing the Generalization-Identification Tradeoff

This paper demonstrates a fundamental contradiction between "broad generalization" and "precise identification": any system with finite semantic resolution \(\varepsilon\) in its similarity computation (ranging from small ReLU networks to VLMs to the human brain) must reside on a universal Pareto frontier and exhibits a \(1/n\) collapse in identification capacity as the number of co-occurring objects \(n\) increases.

Bounds of Chain-of-Thought Robustness: Reasoning Steps, Embed Norms, and Beyond

This paper establishes the first set of theoretical upper bounds for the robustness of Chain-of-Thought (CoT) against input perturbations. Under the Lipschitz continuity assumption, it is proven that "more reasoning steps result in a smaller upper bound for output fluctuation, yet perturbations cannot be eliminated even with infinite steps." Taking Linear Self-Attention (LSA) as a case study, the work demonstrates that the "tolerable input perturbation radius is negatively correlated with the norms of input embeddings and hidden state vectors," with experimental curves across 4 mainstream LLMs and 3 reasoning datasets aligning with the theory.

Branch and Bound Search for Exact MAP Inference in Credal Networks

This paper designs the first depth-first branch-and-bound algorithm for exact MAP inference in credal networks. By formalizing the problem into maximax and maximin MAP tasks, it utilizes problem decomposition within an AND/OR search space and employs a mini-bucket heuristic with cost-shifting for pruning. The approach solves large-scale instances with over 3,000 variables while guaranteeing optimality, outperforming OR search and local search by several orders of magnitude.

Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set

This paper investigates heteroscedastic stochastic linear bandits with a fixed action set, demonstrating that the traditional total variance \(\Lambda=\sum_{t=1}^T \sigma_t^2\) fails to characterize information gain from low-noise rounds. It introduces two variance-adaptive exploration algorithms, VAEE and VAGD, providing sharp simple regret upper and lower bounds that depend on the harmonic mean variance.

Can Transformers Really Do It All? On the Compatibility of Inductive Biases Across Tasks

This paper replaces the most critical nonlinear modules in Transformers with learnable spline functions and uses a two-stage training process to find suitable architectural biases for specific datasets. The authors discover that algorithmic tasks require highly specialized biases, whereas the bias compatibility between language and code modeling is significantly higher.

Characterizing Pattern Matching and Its Limits on Compositional Task Structures

This paper strictly formalizes "pattern matching" in LLMs as functional equivalence—where a model safely substitutes between two input fragments only if they are repeatedly observed to produce identical outputs in the same context. Based on this, it defines a decidable and falsifiable coverage boundary. It proves data scaling laws for compositional tasks and reveals a structural failure mode called "path ambiguity," drawing a precise line between what pattern matching can and cannot achieve.

Characterizing the Discrete Geometry of ReLU Networks

This paper abstracts the polyhedral complex partitioned by fully connected ReLU networks in the input space into a "connectivity graph" (where regions are nodes and adjacent regions share edges). It proves that the average degree of this graph is universally upper-bounded by \(2d\) (twice the input dimension), independent of network width and depth. It also provides an upper bound for the graph diameter \(O(m^\ell)\) that is independent of the input dimension. Theoretical bounds are verified using synthetic data and datasets like MNIST/CIFAR10, revealing that "training data tends to reside in regions with higher connectivity."

CLEAR: Calibrated Learning for Epistemic and Aleatoric Risk

CLEAR proposes a dual-parameter calibration framework that combines aleatoric and epistemic uncertainty in regression prediction intervals according to data-adaptive proportions. This approach significantly narrows intervals and improves conditional coverage while maintaining nominal coverage levels.

Closed-form \(\ell_r\) norm scaling with data for overparameterized linear regression and diagonal linear networks under \(\ell_p\) bias

For overparameterized linear regression (isotropic Gaussian design, minimal \(\ell_p\) interpolation, \(p\in(1,2]\)), this paper utilizes a simple "dual ray" analysis to provide a closed-form high-probability characterization of the scaling of the entire family of parameter norms \(\{\|\hat w_p\|_r\}_{r\in[1,p]}\) with sample size \(n\). It identifies a data-dependent transition point \(n^\star\) ("elbow point") and a universal threshold \(r^\star=2(p-1)\) that separates norms that saturate with \(n\) from those that continue to grow. These laws are further transferred to Diagonal Linear Networks (DLN) trained by gradient descent.

Combinatorial Rising Bandits

This paper proposes the Combinatorial Rising Bandit framework to characterize online learning problems where combinatorial actions consist of base arms that strengthen with use. It introduces the CRUCB algorithm, which utilizes Future-UCB at the base arm level to estimate long-term potential. Theoretical analysis provides regret guarantees close to the lower bound, and experiments show superior performance over existing bandit methods in synthetic shortest path and AntMaze hierarchical reinforcement learning tasks.

Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and Beyond

This paper provides the first non-asymptotic oracle complexity bounds for estimating the normalizing constant \(Z\) via Jarzynski Equality (JE) and Annealed Importance Sampling (AIS). It replaces isoperimetric inequalities with the "action of the curve" to characterize difficulty, demonstrates that geometric interpolation suffers from exponential action on multimodal distributions, and proposes a new algorithm based on reverse diffusion sampling.

Computational Bottlenecks for Denoising Diffusions

This paper proves that if the denoising problem corresponding to a distribution \(\mu\) exhibits an "information-computation gap," denoising diffusion sampling will inevitably fail even if direct sampling from \(\mu\) is easy. Specifically, there exist drifts that are nearly optimal for score matching yet lead to completely erroneous sampling trajectories, and all Lipschitz polynomial-time drifts with near-optimal score matching also fail. Theoretical and numerical evidence is provided using the toy example of sparse low-rank matrices.

Computing Equilibrium beyond Unilateral Deviation

Addressing the blind spot where Nash/Correlated Equilibria only prevent "unilateral deviation" but fail against "multilateral coalition deviation," this paper proposes a guaranteed-to-exist solution concept called MASE (Minimum Average-Strong Equilibrium, which minimizes the maximum average utility any coalition can gain). It proves the computational complexity is determined by the treewidth of the "Utility Dependency Graph" (NP-hard + exponential lower bound under SETH) and provides an algorithm with a runtime perfectly matching this lower bound.

Conformal Prediction for Long-Tailed Classification

To address the dilemma in long-tailed classification where prediction sets are either small but miss rare classes or have good coverage but are excessively large, this paper proposes two conformal prediction methods that maintain marginal coverage guarantees: a new scoring function, PAS (Prevalence-Adjusted Softmax, which optimally trades off set size and macro-coverage), and a new procedure, INTERP-Q (Linearly interpolating Classwise and Standard quantile thresholds to slide along the trade-off). These methods significantly improve the trade-off between set size and class-conditional coverage on Pl@ntNet-300K (1081 classes) and iNaturalist-2018 (8142 classes).

Conformal Prediction with Corrupted Labels: Uncertain Imputation and Robust Re-weighting

Aiming at scenarios where training labels are corrupted by noise or missing and key features are unavailable at test time (privileged information), this paper first proves the precise conditions under which existing Privileged Conformal Prediction (PCP) remains valid despite inaccurate weight estimation. It then proposes a new method, UI, that relies on "backfilling labels with uncertainty" instead of weights. Finally, it takes the union of Naive CP, PCP, and UI to obtain a TriplyRobust calibration scheme that is valid as long as one of the underlying assumptions holds.

Conformalized Decision Risk Assessment

CREDO transforms the question "how likely is a candidate decision to be sub-optimal" into "the probability that the true outcome falls outside the inverse feasible set of that decision." By using generative conformal prediction to construct an inner approximation set of the inverse feasible set, it provides a distribution-free, statistically guaranteed risk upper bound, allowing human experts to perform auditable risk assessments on any decision (whether from algorithms or empirical intuition).

Contextual Multi-Armed Bandits with Minimum Aggregated Revenue Constraints

This paper studies a new setting of "Contextual Bandits + Minimum Aggregated Revenue Constraints per arm" (MAB-ARC). It characterizes the optimal allocation using linear programming (LP), proposes two algorithms—Optimistic (OLP) and Optimistic-Pessimistic (OPLP)—and proves via lower bounds that once contexts are introduced, the "free exploration" property relied upon in prior work fails, reactivating the exploration-exploitation tradeoff.

Continuum Transformers Perform In-Context Learning by Operator Gradient Descent

This paper provides the first theoretical characterization of the In-Context Learning (ICL) phenomenon in "Continuum Transformers" (Transformer variants that handle infinite-dimensional function inputs for PDE surrogate modeling). It proves that forward propagation is equivalent to performing gradient descent in an operator RKHS. In the limit of infinite depth, the model recovers the Bayesian optimal predictor, and the parameters implementing this gradient descent are shown to be stationary points of the pre-training objective.

Convergence Analysis of Tsetlin Machines under Noise-Free and Noisy Training Conditions: From 2 Bits to k Bits

This paper advances the convergence theory of Tsetlin Machines (TM) from existing 1-bit and 2-bit XOR cases to 2-bit AND/OR, noisy training, and general \(k\)-bit scenarios. It proves that TM almost surely converges to the correct logical operators under noise-free conditions/irrelevant variables. While it does not converge under mislabeling noise, it remains efficiently learnable. The work also reveals the unique mechanism where the hyperparameter \(T\) allows a single clause to jointly represent multiple sub-patterns of the OR operator.

Convergence Dynamics of Over-Parameterized Score Matching for a Single Gaussian

This paper theoretically analyzes the convergence dynamics of gradient descent on the score matching objective when learning a single Gaussian distribution using an over-parameterized student model (\(n \ge 2\) learnable means). It proves global convergence under large noise scales and reveals two distinct phase transitions at small noise scales: "all parameters converge" vs. "one parameter converges while others diverge to infinity, yet loss vanishes at \(O(1/\tau)\)". A nearly matching lower bound is also provided.

Covariate-Guided Clusterwise Linear Regression for Generalization to Unseen Data

Targeting regression tasks where tabular data is only locally linear, this paper proposes CG-CLR: it uses a proxy network to generate local coefficients for each sample, then routes them via hard vector quantization to one of \(K\) shared linear regressors. This allows simultaneous learning of "how to allocate new samples" and "linear models for each cluster" within a single gradient loop, supported by convergence proofs, PAC generalization bounds, and an F-test method for selecting the number of clusters \(K\).

Critical Attention Scaling in Long-Context Transformers

This paper demonstrates, using an analytically simplified attention model, that attention behavior undergoes a phase transition as the context length \(n\) increases, driven by the scaling factor \(\beta_n = \gamma \log n\). The critical point occurs precisely at \(\beta_n \asymp \log n\) (specifically \(\gamma_c = \tfrac{1}{1-\rho}\)), providing the first rigorous theoretical justification for the logarithmic scaling used in methods like YaRN and Qwen.

Curse of Slicing: Why Sliced Mutual Information is a Deceptive Measure of Statistical Dependence

This paper systematically deconstructs the reliability of Sliced Mutual Information (SMI) as a scalable alternative to Mutual Information (MI). Through closed-form solutions, counter-examples, and extensive synthetic experiments, it demonstrates that SMI saturates prematurely, favors information redundancy over information content, and decays to zero in high dimensions. In some cases, it performs worse than simple correlation coefficients, leading to systematically misleading conclusions when used to measure statistical dependence.

DAK-UCB: Diversity-Aware Prompt Routing for LLMs and Generative Models

This paper proposes DAK-UCB, an online model selection algorithm that explicitly incorporates "diversity" into Kernelized UCB contextual bandits. By using joint kernel scores (JKD / I-JRKE) that can be decomposed into two-sample expectations as diversity rewards, it balances fidelity and diversity when routing generative models for a stream of prompts, providing regret bound guarantees.

Data-Aware and Scalable Sensitivity Analysis for Decision Tree Ensembles

This paper researches the formal verification problem of "whether a decision tree ensemble is sensitive to certain (e.g., protected) features," proving the problem is NP-hard even for tree ensembles of depth \(1\), and proposes a set of MILP/SMT encoding ENSENSE with new optimizations, which not only improves verification speed by approximately \(5\times\) (binary classification) / \(15\times\) (multi-class) over the previous SOTA, but also for the first time lets counterexample pairs fall near the training data distribution, thereby giving more meaningful evidence of sensitivity.

Data-to-Energy Stochastic Dynamics

This paper proposes the first "data-to-energy" Schrödinger Bridge (SB) solver: when the target distribution is only given as an unnormalized density (energy function) and no samples are available, the classic Iterative Proportional Fitting (IPF) is generalized to the data-free setting. By replacing the maximum likelihood step—which traditionally requires samples—with an off-policy reinforcement learning loss (log-variance loss) from diffusion samplers, the method learns optimal stochastic dynamics between two distributions and is implemented as an "unpaired image-to-image translation" method.

Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms

This paper introduces "distance measures" and "risk measures" from decision theory into the analysis of online algorithms with predictions. By using a quantifiable metric relative to an "ideal algorithm," it identifies the "globally best" algorithm from a family of otherwise incomparable Pareto-optimal/smooth algorithms. It provides computable optimal thresholds for three classical problems: ski rental, unimodal search, and contract scheduling.

Decision Aggregation under Quantal Response

This paper investigates the aggregation of binary decisions from \(n\) experts under bounded rationality characterized by quantal response. It proves that when collective rationality is below a threshold \(g(n)\) dependent on the group size, naive majority voting is the minimax optimal robust aggregator. Furthermore, groups with bounded rationality can unexpectedly outperform fully rational groups because randomness in decision-making encodes weak signals that are lost in deterministic behavior; this phenomenon is empirically validated using the temperature parameter of LLMs as a natural "rationality knob."

Deep FlexQP: Accelerated Nonlinear Programming via Deep Unfolding

FlexQP is proposed—an "always feasible" convex Quadratic Programming (QP) solver based on \(\ell_1\) elastic relaxation. It is combined with deep unfolding to learn LSTM feedback policies for accelerated convergence, resulting in Deep FlexQP. When used as a sub-module in an SQP framework, it solves nonlinear trajectory optimization 4-16× faster than OSQP, while reducing safety violations in predictive safety filters by over 70% and increasing task completion rates by 43%.

Deep Learning with Learnable Product-Structured Activations

This paper introduces LRNN (deep low-rank separated neural networks), which replaces the fixed scalar non-linearity of each neuron with a "product of multiple learnable univariate functions." This allows neurons to naturally capture high-order multiplicative interactions and adaptively adjust spectral bias, achieving state-of-the-art accuracy with fewer parameters in tasks such as image/audio representation, PDEs, and sparse-view CT.

DeepWeightFlow: Re-Basined Flow Matching for Generating Neural Network Weights

DeepWeightFlow utilizes a simple MLP-based flow matching model to directly learn a velocity field in the "weight space," mapping Gaussian noise to trained full network weights in a single pass. It first normalizes the training set networks using Git Re-Basin or TransFusion (eliminating permutation symmetries) and employs PCA to compress dimensions to a trainable scale. This allows the generation of hundreds of high-precision, ready-to-use networks (covering MLP, ResNet, ViT, and BERT, up to O(100M) parameters) within minutes without fine-tuning, significantly faster than diffusion-based approaches.

Differentially Private Equilibrium Finding in Polymatrix Games

This paper characterizes the boundaries of distributed equilibrium finding in polymatrix games that simultaneously satisfy high accuracy and low differential privacy budgets. It proves that this is impossible if an adversary monitors all channels or if accuracy is measured by Euclidean distance. However, by replacing the distance metric with exploitability and assuming the adversary monitors limited channels, the authors propose an adaptive regularization algorithm where the Nash gap and privacy budget both vanish as the number of players increases.

Diffusion and Flow-based Copulas: Forgetting and Remembering Dependencies

This paper applies diffusion and flow concepts to copula modeling by designing two forward stochastic processes that "forget dependencies between variables while preserving univariate marginal distributions." By training models to "remember" these forgotten dependencies, the authors enable copulas to scale to high-dimensional (\(d > 1000\)) and multimodal structures (e.g., images) for the first time, outperforming classical and existing deep copulas on scientific and image data.

Diffusion Bridge Variational Inference for Deep Gaussian Processes

Aiming at posterior inference for inducing variables in Deep Gaussian Processes (DGP), this paper transforms the "reverse diffusion from a fixed Gaussian prior" in DDVI (Denoising Diffusion Variational Inference) into a "diffusion bridge starting from a learnable, data-dependent initial distribution." By leveraging the Doob h-transform while maintaining the Girsanov-ELBO mathematical framework, it shortens the inference trajectory, achieving faster convergence and more accurate posteriors than DDVI in regression, classification, and image reconstruction tasks.

Diffusion Language Models are Provably Optimal Parallel Samplers

This paper establishes a rigorous theory using the language of circuit complexity to explain why "Diffusion Language Models (DLMs) are faster": it proves that DLMs equipped with polynomial-length CoT can simulate any parallel sampling algorithm using the optimal serial steps (equal to circuit depth rather than size). Furthermore, by adding remasking or revision, they can simultaneously achieve optimal space complexity. The paper also provides a parity sampling task to prove that revision/remasking makes DLMs strictly more expressive.

Dimension-Free Decision Calibration for Nonlinear Loss Functions

When downstream decision-makers utilize model predictions for decision-making, "decision calibration" requires predictions to be unbiased with respect to decision-relevant events. This paper extends this concept from linear to nonlinear loss functions. It proves that auditing calibration under deterministic optimal response inevitably requires \(\Omega(\sqrt{m})\) samples (where \(m\) is the feature dimension). However, by adopting smoothed quantal response, the authors provide auditing and post-processing algorithms with sample complexity \(\mathrm{poly}(|A|,1/\epsilon)\) that is completely independent of dimension \(m\), covering a wide range of loss classes including piecewise linear, Cobb–Douglas, and any Lipschitz differentiable functions.

Discounted Online Convex Optimization: Uniform Regret Across a Continuous Interval

Addressing the open problem of the unknown discount factor \(\lambda\) in Online Convex Optimization (OCO), this paper proves that Smoothed OGD (SOGD) achieves a uniform discounted regret bound of \(O(\sqrt{\log T/(1-\lambda)})\) across a continuous interval for all \(\lambda\) simultaneously, without prior knowledge of the true discount factor.

Distribution-informed Online Conformal Prediction

This paper proposes COP (Conformal Optimistic Prediction), which adds an "optimistic correction" step beyond the traditional reactive updates in online conformal prediction. By using the estimated CDF of non-conformity scores as a "hint" for the next step, the method produces narrower prediction intervals when predictable patterns exist in the data. Meanwhile, it maintains distribution-free finite-sample coverage guarantees, ensuring that long-term coverage is not compromised even if the CDF estimation is inaccurate.

Diversified Multinomial Logit Contextual Bandits

This paper directly embeds "combinatorial diversity" into the selection probabilities of the Multinomial Logit (MNL) model. It proposes the DMNL contextual bandit model and designs OFU-DMNL, a white-box UCB algorithm that eliminates the need for a black-box optimization oracle. By constructing assortments through item-wise greedy selection with \(O(NK)\) per-round overhead, the authors prove a \((1-\frac{1}{e+1})\)-approximate regret bound of \(\tilde{O}(d\sqrt{T/K})\).

Does the Data Processing Inequality Reflect Practice? On the Utility of Low-Level Tasks

This paper employs an analytically tractable Gaussian Mixture Model (GMM) binary classification framework to prove that, despite the Data Processing Inequality (DPI) stating "preprocessing does not increase information," for practical classifiers with finite training samples, there exists a dimensionality reduction preprocessing that strictly reduces classification error rate. It further characterizes how SNR, sample size, and class imbalance influence this gain.

Does Weak-to-strong Generalization Happen under Spurious Correlations?

This paper provides the first precise theoretical characterization of Weak-to-Strong (W2S) generalization on downstream tasks with spurious correlations. It demonstrates that W2S inevitably occurs when the minority group proportions in the weak teacher's labeled data and the unlabeled data are equal (\(\eta_u=\eta_\ell\)); otherwise, the W2S gain decays by \((\eta_u-\eta_\ell)^2\) or even fails. Based on this, a simple remedy algorithm named "High-confidence Subset + Generalized Cross-Entropy Retraining" is proposed, which consistently improves W2S across 10 teacher-student pairs without requiring group labels.

Dynamical properties of dense associative memory

This paper provides the first asymptotically exact solution for the dynamics of dense associative memory (modern Hopfield networks) in the large system limit using Generating Functional Analysis (GFA). It quantitatively characterizes convergence time and the size of the basin of attraction during the recall process, revealing that for activation non-linearity order \(n \ge 3\), recall no longer injects additional noise into itself—identifying the root cause of why modern Hopfield networks are more robust than classical models.

Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits

This paper proposes the first best-of-both-worlds (BOBW) algorithm for contextual combinatorial semi-bandits. By employing entropy-regularized FTRL with Matrix-Geometric-Resampling (MGR), the algorithm achieves \(\tilde O(\sqrt T)\) regret in adversarial regimes and \(\tilde O(\ln T)\) regret in corrupted stochastic regimes simultaneously. It further accelerates the high-dimensional projection in each round into a one-dimensional bisection root-finding problem using KKT conditions.

Efficient Credal Prediction through Decalibration

This paper proposes decalibration: starting from a single pre-trained model, by simply adding a global bias vector to logits and perturbing probabilities inversely within a "relative likelihood budget," it calculates a "plausible probability interval" for each class. This constructs credal sets expressing epistemic uncertainty without retraining or ensembles, marking the first application of credal prediction to foundation models like TabPFN and CLIP that cannot be easily retrained.

Efficient Testing for Correlation Clustering: Improved Algorithms and Optimal Bounds

Ours introduces a new analysis framework combining "subgraph sampling + Janson's inequality" to reduce the query complexity for testing whether a signed complete graph is (approximately) perfectly clusterable from \(\tilde{O}(1/\varepsilon^7)\) to \(O(1/\varepsilon^2)\). It provides the first \(O(1/\varepsilon^4)\) tester for fixed \(k\)-clustering and a tight bound of \(\Theta(1/\varepsilon)\) for structural balance (\(k=2\)).

Efficient Turing Machine Simulation with Transformers

This paper demonstrates that constant-bit Transformers can simulate any multi-tape Turing Machine (TM) within an optimal \(O(s(n))\) context window, utilizing only \(O(s(n)^c)\) Chain-of-Thought (CoT) steps per TM step (where \(c\) can be arbitrarily small). This effectively eliminates the \(\Omega(s(n))\) overhead per step inherent in prior constructions and suggests that sparse attention with fixed geometric offsets is sufficient to support efficient universal computation.

Enabling Fine-Tuning of Direct Feedback Alignment via Feedback-Weight Matching

This paper proposes feedback-weight matching: reconstructing DFA feedback matrices from backpropagation (BP) pre-trained weights and then re-initializing the weights using these matrices. This ensures DFA begins fine-tuning in a "strong weight alignment" state, enabling reliable fine-tuning of FCNs and Transformers for the first time (improving image classification by 7.97% over standard DFA and increasing NLP correlation from 0.10 to 0.76).

Epistemic Uncertainty Quantification To Improve Decisions From Black-Box Models

This paper proposes a set of bin-free, asymptotically consistent, and sample-efficient estimators to quantify the epistemic uncertainty remaining beyond black-box model calibration—specifically grouping loss and per-sample excess decision risk. These estimators are used to audit the confidence reliability of 27 open-source LLMs and to construct LLM cascades triggered by epistemic risk, achieving higher accuracy at a lower cost.

Escaping Model Collapse via Synthetic Data Verification: Near-term Improvements and Long-term Convergence

Starting from the classic theoretical setting of linear regression, this paper proves that model collapse can be avoided by introducing an external "verifier" to filter and retrain on self-generated synthetic data. The model achieves near-term improvements via a bias-variance tradeoff and converges long-term to the verifier's "knowledge center" \(\theta_c\) (rather than the ground truth) because the verifier constitutes a contraction mapping. This is empirically validated on VAE and LLM.

Expressive Power of Implicit Models: Rich Equilibria and Test-Time Scaling

This paper characterizes the expressive power of implicit models (fixed-point/DEQ style) from a non-parametric perspective in function space. It proves that "a simple (globally Lipschitz) update operator \(G\) can express any complex locally Lipschitz mapping via fixed-point iteration." This provides a theoretical explanation for the empirical phenomenon where implicit models match or exceed larger explicit networks by increasing test-time iterations. The paper validates that "iterations \(\uparrow \to\) mapping complexity (empirical Lipschitz constant) \(\uparrow\) and accuracy improves synchronously" across imaging, scientific computing, operations research, and LLM reasoning.

FACT: a first-principles alternative to the Neural Feature Ansatz for how networks learn representations

This paper derives FACT (Features at Convergence Theorem) using first-order optimality conditions at training convergence. For networks with weight decay, it establishes a self-consistent formula \(W^\top W = -\frac{1}{n\lambda}\sum_i (\nabla_h \ell_i) h(x_i)^\top\) at convergence points. This replaces the purely empirical Neural Feature Ansatz (NFA), providing a better fit to converged features and explaining why NFA typically holds and in which degenerate scenarios it fails.

Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Data

This paper provides the first rigorous characterization of learning dynamics for anisotropic (power-law covariance) non-linear regression (phase retrieval). It proves that the training trajectory consists of three phases: "fast escape from mediocrity—slow convergence—learning the spectral tail," and explicitly derives the MSE scaling law from the spectral decay index \(a\).

Feature Compression is the Root Cause of Adversarial Fragility in Neural Networks

This paper provides a "feature compression" explanation for adversarial fragility using random matrix theory: neural networks classify using only a compressed subset of features, resulting in a worst-case robustness that may be only \(1/\sqrt{d}\) of the optimal classifier's, validated on ImageNet.

Finite-Time Convergence Analysis of ODE-based Generative Models for Stochastic Interpolants

This paper presents the first finite-time convergence analysis for numerical ODE solvers within the stochastic interpolant framework. It establishes discrete-time TV error bounds and iteration complexities (\(O(\varepsilon^{-1}d^2)\) and \(O(\varepsilon^{-1/2}d^{3/2})\)) for first-order forward Euler and second-order Heun methods. When reduced to diffusion models, the results surpass existing literature in terms of smoothness assumptions and dimensionality dependence.

FlowNIB: An Information Bottleneck Analysis of Bidirectional vs. Unidirectional Language Models

This paper explains "why bidirectional language models understand context better than unidirectional models" through the lens of the Information Bottleneck—bidirectional layers retain more mutual information on both the input and label sides. It proposes FlowNIB, a lightweight posterior framework that aligns two mutual information estimations onto a single optimization trajectory, making layer-wise and cross-model mutual information comparable to empirically validate this theoretical judgment.

From Markov to Laplace: How Mamba In-Context Learns Markov Chains

This work employs "in-context learning on random Markov chains" as a microscope to prove and empirically demonstrate that even a single-layer, single-head Mamba (Selective SSM) can learn an add-\(\beta\) (Laplacian smoothing) count estimator that is both Bayes and minimax optimal. The decisive component is convolution rather than gating or nonlinearity. The authors further provide a constructive proof for exactly reproducing this estimator, alongside an \(\Omega(2^k)\) lower bound for the hidden state dimension that any recurrent architecture cannot escape.

From Neural Networks to Logical Theories: The Correspondence between Fibring Modal Logics and Fibring Neural Networks

This paper establishes a precise correspondence between fibring neural networks (where pre-activations of a parent network are fed into a fibring function to generate weights and inputs for a sub-network, which then injects its output back) and fibring modal logics for the first time. Based on this, it unifies GNNs, GATs, and Transformer encoders as fragments of fibred modal logic formulas and provides their non-uniform logical expressivity results.

From Predictors to Samplers via the Training Trajectory

Without training any additional generative models, this work directly reuses the sequence of checkpoints left by a trained predictor during its training process to perform "trajectory annealing" MCMC. Early checkpoints provide coarse-to-fine smoothing that enables fast mixing, while late checkpoints refine details, effectively reducing exponential MCMC mixing times on rugged/needle-type landscapes to near-linear.

Gradient Descent Dynamics of Rank-One Matrix Denoising

This paper provides a closed-form deterministic approximation of the gradient descent learning trajectory in the rectangular (Wishart) rank-one matrix denoising problem using high-dimensional random matrix theory. It proves the almost sure convergence of the inner product between the estimate and the ground truth, revealing an asymptotic limit corresponding to a signed BBP transition.

Heads Collapse, Features Stay: Why Replay Needs Big Buffers

Ours decouples "deep forgetting (feature space)" from "shallow forgetting (classification head)" and proves via Neural Collapse theory that any non-zero replay ratio asymptotically preserves the linear separability of old task features. However, small buffers cause the classification head to fall into "underdetermined optimization," resulting in covariance rank deficiency and class mean expansion, thus requiring much larger buffers to fix output-layer alignment—a phenomenon termed the "replay efficiency gap."

High-Dimensional Analysis of Single-Layer Attention for Sparse-Token Classification

The authors provide a precise high-dimensional theory of single-layer attention on a "sparse-weak-rare" signal classification model: at the representation level, attention requires only \(\theta=\Theta(\log L)\) signal strength for perfect classification (whereas linear classifiers require \(\sqrt{L}\)); at the learnability level, it is proven that two gradient steps are sufficient for the query weight \(q\) to align with the hidden signal, providing exact asymptotic expressions for post-training test error and capacity.

High-dimensional Analysis of Synthetic Data Selection

The study characterizes the test error of joint training with "training data + synthetic data" using high-dimensional ridgeless regression theory. It proves that only covariance shift affects generalization, while mean shift surprisingly does not, and derives an extremely simple synthetic data selection criterion—covariance matching—that matches or exceeds all recent CLIP-based screening methods in real-world image/text classification.

How hard is learning to cut? Trade-offs and sample complexity

This paper provides the first lower bound on sample complexity for "learning-to-cut." It proves that for both branch-and-cut (B&C) tree size and gap closed scoring functions, the number of samples required to learn a mapping to cuts is at least equivalent (up to a constant factor) to fitting a general target function using the same function class. The lower bounds closely match known upper bounds, suggesting both scores are comparable in learnability. Experiments using GNNs further corroborate that gap closed serves as a robust proxy for tree size.

How Reinforcement Learning after Next-Token Prediction Facilitates Learning

This paper uses a provable toy model of "parity + a mixed distribution of long/short Chain-of-Thought" to rigorously characterize, for the first time from an optimization theory perspective, why "next-token pre-training followed by RL post-training" enables learning difficult tasks that pure pre-training cannot, while explaining the mechanism behind increasing response lengths during RL.

How to Square Tensor Networks and Circuits Without Squaring Them

By unifying "orthogonality" in tensor network canonical forms and "determinism" in circuits into a new family of structural properties (orthogonality/unitarity), the normalization and marginalization of squared probabilistic circuits (squared PC) are reduced from \(O(|c|^2)\) to \(O(|c|)\). This enables efficient marginalization of "non-structurally decomposable" squared circuits for the first time—without actually materializing the squared circuit expansion.

Identifiability Challenges in Sparse Linear Ordinary Differential Equations

This paper revisits the classical conclusion that "linear ODEs can almost always be identified from a single trajectory," pointing out that this conclusion only covers dense matrix cases. In sparse linear ODEs that are closer to biological networks, social networks, and physical interaction systems, systems are unidentifiable with positive probability. This theoretical unidentifiability manifests as structural recovery failure in practical estimators such as SINDy and Neural ODEs.

Implicit bias produces neural scaling laws in learning curves, from perceptrons to deep networks

The authors propose a new perspective that plots learning curves throughout the training process as a function of the model norm \(\lambda(t)\). Within a perceptron, two dynamic scaling laws are analytically derived using statistical mechanics, proving their product reproduces the classic "test error vs. dataset size" endpoint scaling law; these patterns also hold for CNN / ResNet / ViT, rooted in the implicit bias of gradient training.

Implicit Regularisation in Diffusion Models: An Algorithm-Dependent Generalisation Analysis

This paper proposes "score stability," an algorithm-dependent generalization analysis framework that directly translates the sensitivity of a diffusion model to a single training sample into an upper bound on the generalization gap. Using this framework, the authors reveal three previously overlooked sources of implicit regularization: the denoising objective itself, the coarse-grained discretization of the sampler, and the gradient noise of SGD.

Improved High-Dimensional Estimation with Langevin Dynamics and Stochastic Weight Averaging

This paper proves that combining spherical Langevin dynamics with iterative time averaging can recover the hidden direction \(\theta^\star\) of single-index models / Tensor PCA using only \(n \gtrsim d^{\lceil k^\star/2 \rceil}\) samples. Noise injection plus averaging spontaneously simulates the effect of "landscape smoothing" without requiring explicit smoothing operations.

In-Context Algorithm Emulation in Fixed-Weight Transformers

The authors provide a constructive proof demonstrating that a fixed-weight minimalist softmax Transformer can emulate a broad class of algorithms solely by modifying the prompt. A single-head single-layer attention can approximate algorithms in the form of \(f(w^\top x-y)x\) (e.g., gradient descent, linear/ridge regression), while a fixed two-layer attention module further encodes target algorithm weights into tokens. This enables "switching algorithms by changing prompts" without any parameter updates.

Infinite Horizon Markov Economies

This paper proposes the Markov Pseudo-Game (MPG) as a unified framework that integrates "dynamic uncertainty" (Markov games) and "action-dependent feasibility" (pseudo-games). It proves the existence of equilibria and provides a polynomial-time first-order algorithm. Consequently, it establishes the existence of Recursive Radner Equilibrium in generalized infinite-horizon incomplete market economies for the first time and computes the equilibrium using Generative Adversarial Policy Networks (GAPNet).

InfoBridge: Mutual Information Estimation via Bridge Matching

The paper reformulates Mutual Information (MI) estimation between two random variables as a "domain translation" problem: expressing MI as the difference between the drift terms of a pair of diffusion bridges (one connecting the joint distribution and one connecting the product of marginals), resulting in InfoBridge—an estimator that is theoretically unbiased and significantly outperforms existing methods in high-dimensional or high-MI scenarios.

Information Estimation with Discrete Diffusion

The paper proposes INFO-SEDD, which connects the score function of discrete diffusion (Continuous-Time Markov Chains) to the Dynkin's formula. This allows for the direct estimation of KL divergence, mutual information, and entropy on discrete data, bypassing the conventional "embedding into continuous space" approach. It is significantly more accurate and stable in high-dimensional and high-mutual information scenarios.

Interactive Learning of Single-Index Models via Stochastic Gradient Descent

This paper proves that when learning single-index models in an interactive (bandit) environment, a naive normalized SGD equipped with appropriate learning rate and exploration intensity schedules achieves near-optimal sample complexity and regret bounds in both "burn-in" and "learning" phases, without requiring zero-order exploration algorithms customized for specific link functions.

Intrinsic Entropy of Context Length Scaling in LLMs

This paper decomposes the total loss of language modeling into two terms: "Bayes risk, which decreases as context length increases" and "approximation loss, which increases as context length increases." By introducing Intrinsic Entropy, the Bayes risk is strictly linked to context length, explaining the counter-intuitive phenomenon that "longer context is not necessarily better" and deriving an optimal context length determined by the training data volume.

Know When to Abstain: Optimal Selective Classification with Likelihood Ratios

This paper reframes the decision of "whether a model should abstain" as a likelihood ratio test using the classical Neyman–Pearson lemma. It proves that existing scorers such as MSP and RLog are essentially approximations of this likelihood ratio. Based on this, the authors design two distance-based scorers, \(\Delta\)-MDS and \(\Delta\)-KNN, which model "correct" and "incorrect" predictions separately, significantly reducing selective risk under covariate shift.

Language Identification in the Limit with Computational Trace

This paper extends the classic Gold 1967 paradigm of "identification in the limit" to "identification in the limit with computational trace (CoT)". It proves that if the learner is provided with the machine execution trace for each positive example, all Turing-recognizable languages can be identified in the limit (contrasting sharply with Gold's famous negative result where even regular languages are unidentifiable). Furthermore, it characterizes the upper bounds of tolerable noise when traces are adversarially corrupted for DFA, DPDA, and TM language classes, establishing a clean "trichotomy".

Laplacian Kernelized Bandit

This paper reduces the multi-user, nonlinear reward Gang-of-Bandits problem on graphs to learning a single "lifted function" in a unified multi-user RKHS. The reproducing kernel elegantly fuses the graph Laplacian and the arm kernel as \(K((x,u),(x',u'))=[L_\rho^{-1}]_{u,u'}K_x(x,x')\), leading to the design of LK-GP-UCB / LK-GP-TS algorithms with theoretical regret guarantees.

Larger Datasets Can Be Repeated More: A Theoretical Analysis of Multi-Epoch Scaling in Linear Regression

Under the analytically tractable setting of linear regression with multi-epoch SGD, this paper defines and characterizes the "effective reuse rate" \(E(K,N)\)—the ratio of equivalent one-pass data size to the actual \(N\) samples trained over \(K\) epochs. It proves that \(E(K,N)\) depends not only on the number of epochs \(K\) but also increases with the dataset size \(N\) (saturation point at \(\Theta(\log N)\) for strongly convex data and powers of \(N\) for Zipf data). This refines the implicit assumption in Muennighoff et al. (2023) that \(E(K,N)\approx K\) is independent of \(N\), revealing that "larger datasets can be repeated more."

Learning-Augmented Moment Estimation on Time-Decay Models

This paper introduces "ML-predicted heavy-hitter oracles" into time-decaying stream models (including polynomial decay, exponential decay, and sliding windows). By employing a suffix-compatible oracle that only predicts heavy elements in "stream suffixes" combined with a smoothness reduction, existing learning-augmented streaming \(F_p\) moment estimation algorithms are ported to time-decay scenarios almost losslessly, resulting in space-near-optimal, implementable, and formally guaranteed algorithms.

Learning a Game by Paying the Agents

By observing only the behavior of no-regret learning agents in repeated games and actively intervening through "payments + signaling," a principal can learn all agents' utility functions (up to strategic equivalence) to any precision \(\varepsilon\) within polynomial rounds. This enables the first implementation of "steering arbitrary no-regret learners to optimal equilibria" without prior knowledge of agent utilities.

Learning Admissible Heuristics for A*: Theory and Practice

The paper formalizes "learning A* heuristic functions" as a constrained optimization problem. It proposes the Cross-Entropy Admissibility (CEA) loss to enforce admissibility (never overestimate) during training and provides a generalization sample complexity bound using pseudo-dimension that depends on network size rather than graph size. On Rubik's Cube, the learned heuristics are nearly perfectly admissible and stronger than compressed PDBs of the same size.

Learning Correlated Reward Models: Statistical Barriers and Opportunities

This paper demonstrates that mainstream pairwise preference data in RLHF cannot learn the correlation between user utilities, while best-of-three (ranking one out of three) data is both necessary and sufficient. Based on this, it provides the first identifiability results for the correlated probit model and a near-optimal polynomial-time estimator.

Learning from Label Proportions via Proportional Value Classification

This paper reformulates the "bag-level mean prediction matching" in Learning from Label Proportions (LLP) as a proportional value classification task. Through invertible instance posterior aggregation and FFT-accelerated computation, the model learns sharper instance-level classifiers using only label proportions, significantly outperforming existing LLP methods across various bag construction strategies.

Learning Shrinks the Hard Tail: Training-Dependent Inference Scaling in a Solvable Linear Model

This paper uses an analytically solvable "Latent Instance Difficulty (LID)" linear fine-tuning model to prove that the power-law exponent \(\beta_{\text{eff}}(N)\) of the pass@k failure rate is training-dependent. It increases with the training sample size \(N\) and eventually saturates at an intrinsic upper bound \(\beta\) determined by the tail of the difficulty distribution, thereby unifying training-side and inference-side scaling laws within a closed-form framework.

Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample

This paper investigates how to estimate the inverse temperature parameter of an Ising model using only a single sample under a known bounded-degree graph and a k-SAT hard constraint truncated set. It proves that a projected gradient algorithm based on Maximum Pseudo-Likelihood Estimation (MPLE) achieves a consistency error of \(O(\Delta^3 / \sqrt{n})\) in near-linear time.

Learning to Adapt: In-Context Learning Beyond Stationarity

This paper provides the first theoretical characterization of In-Context Learning (ICL) under non-stationary (time-varying) regression. It proves that Gated Linear Attention (GLA) implements a "learnable recency bias" through a forgetting factor \(\lambda\). When regression weights drift according to a first-order autoregressive process, both training and test errors are strictly lower than standard linear attention, with the optimal \(\lambda < 1\).

Learning to Answer from Correct Demonstrations

This paper formalizes SFT for LLMs as "imitation learning from optimal demonstrations in contextual bandits." It proves that it is sufficient for the reward model (which answers are correct) to belong to a low-complexity class, rather than the demonstrator's strategy—a much weaker assumption. The authors demonstrate that Maximum Likelihood Estimation (MLE)/SFT fails under this assumption and propose a single-pass online algorithm with sample complexity logarithmic in the reward class size, achieving an "optimistic rate" of \(1/\varepsilon\) when demonstrations are optimal.

Learning under Quantization for High-Dimensional Linear Regression

This paper provides the first systematic theoretical framework characterizing "how quantization affects learning performance." Under high-dimensional linear regression and finite-step SGD, the authors derive precise excess risk upper bounds for five quantization targets: data, labels, parameters, activations, and gradients. They demonstrate that additive quantization (corresponding to INT) contaminates the data spectrum, whereas multiplicative quantization (corresponding to FP) preserves spectral structure, thus performing better in high-dimensional settings.

Lipschitz Bandits with Stochastic Delayed Feedback

This paper presents the first systematic study of the learning problem for Lipschitz bandits in continuous arm spaces under stochastic delayed feedback. It proposes the Delayed Zooming algorithm for bounded delays (maintaining a sub-optimality gap bound of \(\Delta(x) \leq 6r_t(x)\) via a lazy update mechanism) and the DLPP phased pruning strategy for unbounded delays (where regret is linked to the delay quantile \(Q(p)\)). Furthermore, it establishes an instance-dependent lower bound proving that DLPP is near-optimal.

\(\mathbf{Li_2}\): A Theoretical Framework Characterizing Feature Emergence and Delayed Generalization Dynamics

This paper proposes the \(\mathbf{Li_2}\) framework. Starting from the first principles of gradient dynamics in two-layer nonlinear networks, it decomposes grokking (delayed generalization) into three stages: "lazy learning → independent feature learning → interactive feature learning." It proves that the independent stage is precisely a gradient ascent on an energy function \(E\), where local maxima correspond to emergent features, thereby deriving provable scaling laws for the memory/generalization boundary.

Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms

The paper resolves two open problems regarding "coarsened Gaussian mean estimation" under convex partitions—providing a geometric characterization of identifiability (unidentifiable \(\Longleftrightarrow\) almost all partition sets are "slabs" in the same direction) and offering the first polynomial-time algorithm that matches the optimal sample complexity.

Memorizing Long-tail Data Can Help Generalization Through Composition

This paper proves in an overparameterized linear model that memorizing long-tail features appearing only once, combined with the model's inherent "compositional" ability, enables correct predictions on novel combinations of long-tail features never seen during training. This intuition is validated on modified MNIST/Omniglot datasets, showing that compositional capability depends on network architecture.

Memory-Statistics Tradeoff in Continual Learning with Structural Regularization

Under a random design for two-task linear regression, this paper provides matching upper and lower bounds for excess risk for the "generalized \(\ell_2\) structural regularization based on previous task Hessian" algorithm. It reveals for the first time theoretically that a provable tradeoff exists in continual learning between memory complexity (rank/number of vectors of the regularization matrix) and statistical efficiency: using more vectors to remember the old task curvature allows approaching joint training accuracy, while using fewer leads to catastrophic forgetting.

Metric \(k\)-Clustering using only Weak Comparison Oracles

Using only a noisy "quadruplet comparison oracle" (answering "is A closer to B, or C closer to D?") without any real distances, this work constructs a constant-approximation Coreset+ for \(k\)-median/\(k\)-means with \(O(nk\,\mathrm{polylog}\,n)\) queries. The approximation ratio is further improved to \(1+\varepsilon\) under bounded doubling dimension.

Minimax-Optimal Aggregation for Density Ratio Estimation

Addressing the extreme sensitivity of Density Ratio Estimation (DRE) to hyperparameters, this paper proposes an algorithm that linearly aggregates models trained with various hyperparameters. By minimizing an analytical upper bound of the Bregman divergence, the method achieves minimax-optimal convergence rates without prior knowledge of the density ratio smoothness, outperforming cross-validation and model averaging in DRE benchmarks and large-scale domain adaptation tasks.

Minimax Rates for Learning Pairwise Interactions in Attention-Style Models

This paper models single-layer attention as an inverse problem for Interacting Particle Systems (IPS). It proves that the minimax rate for learning the pairwise interaction function \(g^\star(x,y)=\phi^\star(x^\top A^\star y)\) from aggregated outputs is \(M^{-\frac{2\beta}{2\beta+1}}\). Under low-rank conditions, this rate is independent of the embedding dimension \(d\), the number of tokens \(N\), and the matrix rank \(r\), providing a statistical explanation for how attention mechanisms avoid the curse of dimensionality.

Minimax Sample Complexity of Graph Neural Networks: Lower Bounds and Structural Effects

This paper establishes two minimax lower bounds for ReLU message-passing GNNs: on arbitrary graphs, the error is no faster than the classic \(\sqrt{\log d / n}\). However, under "strong homophily + weak spectral expansion" (spectral-homophily), the transductive node prediction error is as slow as \(d/\log n\)—revealing that the sample complexity of real-world graph tasks is primarily dictated by graph topology rather than neural architecture.

Mitigating the Curse of Detail: Scaling Arguments for Feature Learning and Sample Complexity

This paper employs the "scaling analysis" approach from statistical physics to approximate Bayesian Neural Networks (BNNs)—no longer solving exact high-dimensional nonlinear equations, but instead using pencil-and-paper level energy comparisons. It predicts what feature learning (FL) modes (Specialization, GFL, etc.) emerge at specific data/width scales and determines the scaling exponent of the minimum learnable sample size \(P^*\).

Multi-Condition Conformal Selection

The authors generalize conformal selection, which originally handled only single-threshold conditions y > c, to multi-condition scenarios such as "conjunctions \(c_1 < y < c_2\)" and "disjunctions \(y < c_1 \text{ or } y > c_2\)". By designing region-monotone non-conformity scores and a global BH procedure, they achieve strict FDR control under finite samples.

Multi-Synaptic Cooperation: A Bio-Inspired Framework for Robust and Scalable Continual Learning

Inspired by the biological observation that multiple parallel synapses exist between a single axon-dendrite pair, this paper proposes MSCN. It enhances representation capacity within a fixed network structure by using multiple parallel synapses and modulates synaptic plasticity via local activity based on eligibility traces. This approach alleviates catastrophic forgetting without dynamic expansion and significantly improves robustness to task order.

Multiple-Prediction-Powered Inference

MultiPPI formalizes the task of "efficiently estimating a mean using multiple predictors of varying costs/qualities under a fixed budget" as a convex optimization problem (specifically, a Second-Order Cone Program (SOCP) under a single constraint). It automatically determines which subsets of models to query, the number of queries for each, and their corresponding weights. Theoretically, it is minimax optimal when the covariance is known. Experimentally, it consistently achieves lower error than existing PPI baselines across three types of LLM evaluation tasks.

Navigating the Latent Space Dynamics of Neural Models

This paper interprets autoencoders as dynamical systems acting on a latent manifold: repeatedly executing \(f(z)=E(D(z))\) induces a latent vector field whose attractors and trajectories explain the model's memorization-generalization state, probe prior information in pre-trained weights without data, and facilitate out-of-distribution (OOD) detection.

Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs

This paper provides the first near minimax-optimal sample complexity upper and lower bounds for learning \(\varepsilon\)-optimal policies in Constrained Average-Reward MDPs (CAMDPs) under a generative model: \(\tilde O\big(SA(B+H)/\varepsilon^2\big)\) for the relaxed feasibility setting and \(\tilde O\big(SA(B+H)/(\varepsilon^2\zeta^2)\big)\) for the strict feasibility setting. These results, complemented by matching lower bounds, characterize how long-term constraints affect learning difficulty.

Near Optimal Robust Federated Learning Against Data Poisoning Attack

Addressing the "low data per worker, high number of workers" data poisoning scenario in Federated Learning, this paper first provides the minimax lower bound of attack loss and then designs a two-stage mechanism involving "training a discriminator to assign reliability weights" to workers. This ensures that the upper bound asymptotically matches the lower bound as \(m\to\infty\), and the attack loss depends only on the task's VC dimension \(d\) rather than the gradient dimension.

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams

This paper presents nearly space-optimal algorithms for graph and hypergraph spectral sparsification in insertion-only streams. It reduces the space complexity of graph spectral sparsifiers from the previous \(O(\frac{n}{\varepsilon^2}\log^2 n)\) bits to \(O(\frac{n}{\varepsilon^2}\log n\cdot\text{poly}(\log\log n))\) and introduces the first streaming hypergraph sparsifier with factors exceeding offline results by only poly-iterated-log terms relative to \(m\). It simultaneously addresses online, sliding window, and adversarial robustness settings.

Neural Collapse in Multi-Task Learning

This paper generalizes "Neural Collapse" (NC) theory from single-task to multi-task learning (MTL) for the first time. It characterizes the geometric structures of task-specific classifiers and features at the terminal phase of training (TPT) under both single-source and multi-source MTL settings (e.g., task-specific Simplex ETF, cross-task orthogonality, and shared features being the sum of task-specific features). Through rigorous proofs using the Unconstrained Feature Model (UFM), the authors reveal an inductive bias where task correlation reshapes classifier geometry and promotes feature alignment.

Neural Posterior Estimation with Latent Basis Expansions

The variational family of Neural Posterior Estimation (NPE) is reformulated as "log-density = linear combination of latent basis functions"—an exponential family parameterized by neural networks. This approach maintains high expressivity for low-dimensional posterior projections while ensuring the optimization is (marginally) convex, stably outperforming Gaussian Mixture Models and Normalizing Flows.

Neyman-Pearson Classification under Both Null and Alternative Distributions Shift

This paper proposes the first Neyman-Pearson (NP) transfer learning process for scenarios where both class-conditional distributions \(\mu_0, \mu_1\) shift between source and target domains. This method ensures improved Type-I/Type-II errors when the source is useful, avoids negative transfer by falling back to target-only data when it is not, and provides polynomial-time computational guarantees by reducing the problem to a sequence of convex programs.

Noise Tolerance of Distributionally Robust Learning

This paper reveals that mainstream Wasserstein Distributionally Robust Learning (WDRL) provides no robustness gain against global additive noise when the regression function is non-convex or non-Lipschitz. Consequently, it proposes Wasserstein Batch Matching (WBM), which is independent of model architecture. WBM performs optimal transport matching between the predicted distribution and the response distribution within a batch. Theoretically, this suppresses the linear sensitivity of the loss to noise into cubic decay. Experiments on PDE operator learning and power grid time-series forecasting show that WBM outperforms MSE and various DRO methods with approximately 10x lower computational cost.

"Noisier" Noise Contrastive Estimation is (Almost) Maximum Likelihood

By artificially magnifying the noise distribution by a factor \(M\), the gradient of the NCE objective gradually converges to the Maximum Likelihood (MLE) gradient. This enables fast and stable density ratio estimation even under the classic "density-chasm" challenge—where the target and noise distributions differ significantly—with almost zero additional cost.

Non-Asymptotic Analysis of (Sticky) Track-and-Stop

This paper provides the first non-asymptotic (finite-confidence) sample complexity upper bounds for two classic algorithms in the pure exploration field: Track-and-Stop (TAS) and Sticky Track-and-Stop (S-TAS). It fills the theoretical gap where these algorithms were proven optimal only as \(\delta\to0\), with unknown performance for finite \(\delta\).

Nonparametric Contextual Online Bilateral Trade

Under the most stringent setting where buyer and seller valuations are arbitrary Lipschitz functions of the context, feedback is restricted to a single bit ("whether the trade occurred"), and strong budget balance is required, this paper proposes a pricing algorithm based on hierarchical tree partitioning. It achieves an \(\tilde{O}(T^{(d-1)/d})\) regret bound and provides a matching lower bound to prove its optimality.

On Coreset for LASSO Regression Problem with Sensitivity Sampling

This paper provides the first sensitivity sampling-based coreset construction for standard LASSO regression (objective \(\|Ax-b\|_2^2+\lambda\|x\|_1\)). By localized decomposition of the complex function space induced by the \(\ell_1\) penalty into a residual space and an \(\ell_1\) penalty space, the authors tighten the coreset size from the original \(\tilde O(Gd/\epsilon^2)\) to \(\tilde O\!\big(\epsilon^{-2}d(\log^3 d\cdot\min\{1,\log d/\lambda^2\}+\log(1/\delta))\big)\), and provide a near-matching lower bound. Experimentally, it is 4–18 times faster than solving LASSO directly, processing an 8-million-sample dataset in just 15 minutes.

On learning linear dynamical systems in context with attention layers

This paper provides the explicit optimal weight solution for single-layer linear attention in the In-Context Learning (ICL) task of "noisy Linear Dynamical Systems (LDS)". It proves that under a first-order autoregressive approximation (AR(1)), the attention layer is equivalent to performing a single step of gradient descent on the autoregressive least squares loss. Through experiments, it connects the optimal solution structure of AR(s) (\(s \ge 2\)) with Preconditioned Conjugate Gradient (PCG) methods, providing a theoretical explanation for the empirical phenomenon where Transformer prediction accuracy matches the Kalman filter.

On Powerful Ways to Generate: Autoregression, Diffusion, and Beyond

This paper rigorously characterizes the capability boundaries of "Autoregressive Models (ARM) vs. Masked Diffusion Models (MDM)" using computability theory. It proves that while MDM's parallelism offers exponential speedups, its "any-order" flexibility does not allow it to solve more problems than ARM. Thus, the authors propose any-process generation (adding remask, insert, and delete operations beyond unmasking), proving theoretically and experimentally that it can solve harder reasoning and structured generation tasks that both ARM and standard MDM fail to handle.

On Smoothness Bounds for Non-Clairvoyant Scheduling with Predictions

This paper redefines the "smoothness" metric in algorithms with predictions by measuring the competitive ratio only on subsets of instances where the "prediction actually provides additional information," thereby preventing the old definition from being contaminated by uninformative instances. Under this new metric, the paper provides tighter lower bounds and matching algorithms for three types of non-clairvoyant scheduling problems (single-machine total completion time: \(\eta\) lower bound + \(\eta^2\) algorithm; identical parallel machine makespan: \(2-O(\eta^{-2})\) lower bound + \(O(\eta^2)\) algorithm; related machine makespan: tight \(\lceil\log\eta\rceil\) bound).

On the Bayes Inconsistency of Disagreement Discrepancy Surrogates

This paper proves that existing surrogate losses used for "disagreement discrepancy" are not Bayes consistent in multiclass (\(K>2\)) settings—optimizing the surrogate does not necessarily optimize the true objective. Accordingly, it designs a new disagreement loss \(-\log(1-\sigma(s)_y)\), which, combined with cross-entropy, yields the first provably Bayes consistent surrogate. This surrogate is more reliable for downstream tasks like error bound estimation and harmful shift detection.

On the Benefits of Weight Normalization for Overparameterized Matrix Sensing

This paper provides the first theoretical characterization of Weight Normalization (WN) in overparameterized matrix sensing. By decoupling matrix variables into "direction (Stiefel manifold) + magnitude (symmetric matrix)" and applying Riemannian Gradient Descent, the method achieves linear convergence under finite samples (an exponential acceleration compared to the sublinear lower bound of standard GD). Notably, as the degree of overparameterization increases, both iteration complexity and sample complexity decrease polynomially.

On the Computational Limits of AI4S-RL: A Unified \(\varepsilon\)-\(N\) Analysis

When using AI surrogate models (neural operators) as RL simulation environments to replace expensive PDE solvers, this paper proposes a unified \(\varepsilon\)-\(N\) theoretical framework. By putting the surrogate discretization accuracy, RL agent grid resolution, and policy learning quality into a single probabilistic language, it derives the minimum computational cost \(N^*(\varepsilon)\) required for unbiased value function estimation under a given precision \(\varepsilon\) and confidence \(1-\delta\). It also provides closed-form optimal allocation ratios \(K^*\) for "surrogate accuracy vs. RL accuracy" across different physical systems.

On the Convergence of Two-Layer Kolmogorov-Arnold Networks with First-Layer Training

This paper proves that under the overparameterized setting with training restricted to the first-layer coefficients, two-layer KANs using gradient descent converge to the global optimum (zero training error). It provides a fine-grained convergence rate determined by the "projection of labels onto the eigenstructure of the KAN Tangent Kernel" and demonstrates that KANs require only \(m=O(n^2)\) hidden layer width to guarantee convergence—a polynomial improvement over the \(m=O(n^6)\) required for classic ReLU two-layer networks.

On the Expressiveness of State Space Models via Temporal Logics

This paper characterizes a hierarchy of expressivity lower bounds for State Space Models (SSMs) with different gating mechanisms (diagonal S6, time-invariant S4, mixed gating) and arithmetic precisions (fixed-width vs. logarithmic) using Pure Past Linear Temporal Logic over finite traces (PLTLf) and its counting/modular extensions. It proves several hard inexpressibility results (e.g., fixed-width diagonal SSMs cannot recognize \((aa)^*\)) and aligns these results with the known logic characterizations of Transformers.

On the Interpolation Effect of Score Smoothing in Diffusion Models

This paper demonstrates through analytical derivations and numerical experiments that diffusion models can "create" new samples not present in the training set because neural networks learn a smoothed version of the empirical score function (ESF). This smoothing directly drives denoising trajectories to generate samples that interpolate between training data points, thereby avoiding the memorization inevitably caused by an exact ESF.

On the Spectral Differences Between NTK and CNTK and Their Implications for Point Cloud Recognition

Under the assumption of tensor data in arbitrary dimensions, this paper provides two distribution-independent spectral difference theorems for NTK and CNTK (NTK eigenvalues have a larger mean and a more concentrated spectrum). Based on these, it defines a "Convolutional Suitability" metric to measure "how suitable data is for convolution" and infers that point clouds depend more on convolutional structures than images. Finally, a hybrid CNTK-NTK kernel (PointNTK) significantly outperforms the NTK baseline in few-shot point cloud recognition.

On the Wasserstein Geodesic Principal Component Analysis of probability measures

This paper advances Principal Component Analysis (PCA) on sets of probability measures from tangent space approximations to true Wasserstein geodesic optimization. For Gaussian measures, it utilizes Bures-Wasserstein geometry lifted to the space of invertible matrices; for general absolutely continuous measures, it employs Otto parametrization and neural networks to learn principal geodesics, demonstrating a superior capability to characterize distribution variation patterns in curved spaces compared to Tangent PCA (TPCA).

On Universality of Deep Equivariant Networks

This paper establishes the theorem of "universality under separation constraints" for deep invariant/equivariant networks, identifying depth and readout layers as the decisive mechanisms for achieving universality. It introduces a finer "entry-wise separability" criterion for the equivariant case than standard separation, unifying and generalizing previous conclusions limited to shallow or specific architectures.

Online Conformal Prediction with Adversarial Semi-bandit Feedback via Regret Minimization

This paper reformulates the online conformal prediction problem—where the true label is revealed only if it falls within the prediction set—as an adversarial multi-armed bandit problem by treating threshold candidates as arms. By designing a specialized loss function that explicitly links regret to the miscoverage rate and adapting the EXP3.P algorithm into OCP-Unlock+, the authors provide the first long-term coverage guarantee under adversarial data streams without relying on i.i.d. assumptions.

Online Decision-Focused Learning

This paper generalizes Decision-Focused Learning (DFL) from the i.i.d. batch setting to an online setting where objective functions vary over time. By employing two strategies—regularizing the inner problem for differentiability and utilizing approximate oracles with perturbations to handle non-convexity—the authors propose DF-FTPL and DF-OGD algorithms, providing provable static and dynamic regret upper bounds, respectively.

Online Decision Making with Generative Action Sets

This paper investigates a class of online decision problems where action sets can be "generated at a cost and reused permanently." It proposes a "Double Optimism" algorithm that uses LCB to select existing actions and UCB to decide whether to generate a new action. It proves that the algorithm achieves an optimal regret of \(O(T^{\frac{d}{d+2}}d^{\frac{d}{d+2}} + d\sqrt{T\log T})\), providing the first sublinear regret bound for scenarios with dynamically expanding action spaces.

Online Inventory Optimization in Non-Stationary Environment

This paper proposes a "two-stage projection + doubling trick" algorithm for Online Inventory Optimization (OIO) under non-stationary demand. By transforming the inventory carry-over constraint into a switching cost proportional to the sell-out period, the authors reduce OIO to Smoothed Online Convex Optimization (SOCO). They provide the first near-optimal dynamic regret bound of \(\tilde{O}(\sqrt{L_{\max}T(1+P_T)})\) along with a matching lower bound of \(\Omega(\sqrt{L_{\max}T})\).

Online Learning and Equilibrium Computation with Ranking Feedback

This paper generalizes the classic "numerical utility feedback" online learning to scenarios where only action rankings are observed. It first proves when sublinear regret is impossible in adversarial environments under pure ranking feedback, then constructs a modular algorithm that "estimates utility from rankings + feeds into an arbitrary black-box no-regret algorithm." Under the assumption of limited utility variation, it achieves sublinear regret and further guarantees convergence to an approximate Coarse Correlated Equilibrium (CCE) in multi-player repeated games. Finally, it validates the approach with an online LLM routing experiment.

Online Rounding and Learning Augmented Algorithms for Facility Location

This paper provides the first online rounding algorithms for the metric facility location problem—rounding an online maintained fractional solution on the fly into an integer solution. For the uniform opening cost case, a deterministic algorithm incurs only an \(O(1)\) constant factor loss; for the non-uniform case, a randomized algorithm incurs an expected \(O(\log\log\Delta)\) factor loss (\(\Delta\) is the aspect ratio of the metric). This yields the first integer algorithm for learning-augmented facility location under multiple predictions, pushing the consistency/robustness bounds to near-tight results that match the fractional version.

Optimizing Data Augmentation through Bayesian Model Selection

This paper proposes OPTIMA, which treats data augmentation (DA) parameters as model hyperparameters and reformulates the "augmentation strategy selection" as a Bayesian model selection problem. By utilizing a tractable augmented ELBO, it jointly optimizes augmentation parameters and model parameters within a single training loop, eliminating the expensive cost of repeated training required by grid search or Bayesian optimization while simultaneously improving generalization, calibration, and OOD robustness across vision and NLP tasks.

Oracle-Efficient Hybrid Online Learning with Constrained Adversaries

This paper investigates the "i.i.d. features, adversarial labels" hybrid online learning problem. By imposing a structural constraint on the adversary—requiring label functions to be chosen from a fixed function class \(R\)—the authors design an algorithm that runs using only a linear optimization oracle. The regret scales with the Rademacher complexity of the composite class \(\ell\circ(H\times R)\), marking the first instance of simultaneously achieving statistical near-optimality and computational efficiency in this specific setting.

Overparametrization bends the landscape: BBP transitions at initialization in simple Neural Networks

By generalizing classical phase retrieval to a "two-layer quadratic activation teacher-student network with arbitrary width," this work uses field-theoretic methods to analytically calculate the Hessian spectrum of the loss at initialization. It discovers that the BBP transition threshold \(\alpha_{\text{BBP}}\), where outlier eigenvalues (carrying teacher signal information) emerge from the bulk, decreases with overparametrization. As the student becomes wider, less data is required for the signal to emerge within the curvature of the random initial point, even reaching the information-theoretic weak recovery lower bound \(p^*/2\) in the limit.

PAC-Bayes Bounds for Cumulative Loss in Continual Learning

This paper generalizes existing online and time-uniform offline PAC-Bayes bounds to the continual learning setting, providing the first cumulative loss (learning plasticity) bounds applicable to arbitrary task distributions and learning algorithms, and verifies non-vacuous risk certificates on visual continual learning tasks.

Parameterized Hardness of Zonotope Containment and Neural Network Verification

This paper proves that a series of verification-related problems, including the positivity/surjectivity of 2-layer ReLU networks, zonotope non-containment, and Lipschitz constant computation, are all W[1]-hard when the input dimension \(d\) is taken as the parameter. This rules out fixed-parameter tractability under the Exponential Time Hypothesis (ETH) and demonstrates that naive "linear region enumeration" algorithms are essentially optimal in their dependence on \(d\).

Persistence Spheres: Bi-Continuous Representations of Persistence Diagrams

This paper proposes Persistence Spheres (PS): by constructing a "lift zonoid" from a weighted persistence diagram and taking its support function on the unit sphere \(S^2\), a functional representation is obtained that is Lipschitz continuous with respect to the 1-Wasserstein distance and possesses a continuous inverse on its image. This "bi-continuity" is extremely rare in persistence diagram vectorization methods. Experimentally, it matches or outperforms baselines like persistence images, landscapes, and sliced Wasserstein kernels in clustering, regression, and classification tasks.

Physics-informed learning under mixing: How physical knowledge speeds up learning

Ours derives high-probability and expectation bounds for excess risk of "empirical risk minimization with physics-informed regularization" under non-i.i.d. (dependent/mixing) data. It proves that as long as the physical prior is "aligned" with the ground truth (\(\|D(f^\star)\|_{L^2}^2\simeq 0\)), the learning rate accelerates from the slow Sobolev minimax rate \(O(T^{-d})\) to the \(O(1/T)\) rate consistent with the i.i.d. optimal rate, without losing effective sample size due to data dependence.

Poisson Midpoint Method for Log-Concave Sampling: Beyond the Strong Error Lower Bounds

This paper provides a sharp \(W_2\) convergence analysis for Poisson Midpoint Discretization (PLMC) in strongly log-concave sampling. It proves that PLMC further compresses the precision \(\epsilon\) dependency from \(\tilde O(\epsilon^{-2/3})\) to \(\tilde O(\epsilon^{-1/3})\) under both overdamped and underdamped Langevin dynamics—an order of magnitude faster than the previously assumed optimal randomized midpoint method. This work also signifies the first proof that \(W_2\) weak error complexity can be lower than the \(L^2\) strong error complexity lower bound established in the literature.

Poly-attention: a general scheme for higher-order self-attention

This paper proposes poly-attention—a class of higher-order self-attention mechanisms unified by an "attention polynomial" \(h\) (where self-attention, tensor attention, and Strassen attention are special cases). It provides tight characterizations of the time complexity for exact/approximate computation and the expressivity of each mechanism. Consequently, it identifies a new mechanism, tree-attention, which performs arbitrary \(r\)-fold function composition in quadratic time, whereas all previous mechanisms capable of composition required super-quadratic time.

Polynomial Convergence of Riemannian Diffusion Models

This work proves that Riemannian Score-based Generative Models (RSGMs) on manifolds require only polynomial-scale step counts to achieve accurate sampling under Total Variation (TV) distance. It relaxes the restrictive guarantees of De Bortoli et al. (2022)—which previously required "exponentially small steps + \(L_\infty\) score precision + smooth strictly positive data distribution"—to "polynomial steps + \(L_2\) score precision + arbitrary data distribution."

Practical Estimation of the Optimal Classification Error with Soft Labels and Calibration

This paper makes two contributions to binary Bayes error (optimal error rate) estimation: first, it provides a much tighter bias bound that adaptively accelerates based on the "separability" of the two class distributions; second, it proposes applying isotonic calibration before the estimation formula when soft labels are contaminated, achieving statistical consistency as long as the "order" of soft labels remains intact.

Prediction with Expert Advice under Local Differential Privacy

This paper investigates the online learning problem of "Prediction with Expert Advice" under Local Differential Privacy (LDP) constraints. It first notes that the classic random walk algorithm RW-FTPL naturally satisfies LDP. Building on this, it introduces two improvements: RW-AdaBatch, which utilizes the "few switches" property for adaptive batching to achieve privacy amplification with minimal utility loss when data is "simple"; and RW-Meta, which uses a shared-noise mechanism to privately select from a set of data-dependent learning experts at zero additional privacy cost. RW-Meta outperforms classic baselines and SOTA centralized DP algorithms by 1.5–3 times on real COVID-19 hospital data.

Pretrain–Test Task Alignment Governs Generalization in In-Context Learning

This paper uses a solvable linear attention model for in-context linear regression to derive an exact high-dimensional formula for ICL generalization error under arbitrary mismatch between the pretraining task covariance \(C_{\text{train}}\) and the test task covariance \(C_{\text{test}}\). From this, a "task alignment metric" is extracted, which accurately predicts ICL performance not only in solvable models but also in nonlinear Transformers, revealing a specialization-generalization tradeoff where "increased pretraining task diversity is not always better."

Preventing Model Collapse Under Overparametrization: Optimal Mixing Ratios for Interpolation Learning and Ridge Regression

This paper provides exact generalization error formulas for an iterative training scheme under overparametrized linear regression (\(p/n \to \gamma > 1\)), where fresh real labels and synthetic labels generated by the previous model are mixed by ratio \(w\). It proves that the optimal real data proportion for minimum \(\ell_2\)-norm interpolators converges to the inverse golden ratio \(\varphi^{-1} \approx 0.618\), while for ridge regression, the optimal ratio is always \(\ge 1/2\), theoretically characterizing when model collapse can be prevented and when it is inevitable.

Price of Quality: Sufficient Conditions for Sparse Recovery using Mixed-Quality Data

This work investigates the sufficient conditions for the sample size required for sparse signal support recovery when observations originate from two heteroscedastic noise sources ("small amount of high-quality + large amount of low-quality" data). It proposes a quantitative metric, "Price of Quality" \(\gamma\) (representing how many low-quality samples a single high-quality sample is worth), and reveals a counter-intuitive contrast: information-theoretic thresholds change sensitively with the data quality structure, whereas the LASSO algorithmic threshold depends only on the average noise and is surprisingly robust to data heterogeneity.

Probability Distributions Computed by Autoregressive Transformers

This paper extends research on Transformer expressivity from the traditional "classifier" setting (accept/reject strings) to the "autoregressive probabilistic language model" setting. It demonstrates that the shifts to "autoregression" and "real-valued weights (probabilities)" alter or even break existing equivalence results—sometimes making Transformers stronger, and sometimes making classifiers and autoregressors incomparable.

Proper Velocity Neural Networks

This paper introduces the "Proper Velocity (PV)" space, originating from special relativity, into machine learning. It completes the full Riemannian toolbox for PV (closed-form solutions for exponential/logarithmic maps, parallel transport, and geodesic distance) and constructs core layers including MLR, fully connected, convolutional, activation, and batch normalization. The resulting Proper Velocity Neural Network (PVNN) is numerically stable and outperforms Poincaré and Hyperboloid (Lorentz) models on strongly hyperbolic data.

Provable Separations between Memorization and Generalization in Diffusion Models

This paper proves from two complementary perspectives, "statistical estimation" and "network approximation," that memorization in diffusion models (reproducing training samples rather than generalizing) fundamentally stems from two provable "separations" between the true score function and the empirical score function: the true score does not minimize the denoising score matching loss, and the empirical score requires a network that scales with the number of samples to approximate. Based on this, a pruning mitigation method for DiT is proposed.

Pseudo-Non-Linear Data Augmentation: A Constrained Energy Minimization Viewpoint

Starting from information geometry and energy models, this paper embeds data onto a dually flat statistical manifold and mimics an autoencoder via "forward projection encoding + backward projection decoding." It proposes PNL, a training-free, controllable, and cross-modal data augmentation method that achieves comparable or superior accuracy to generative/classical augmentation on multiple downstream classification tasks while significantly reducing variance.

Quantitative Bounds for Length Generalization in Transformers

This paper provides the first quantitative upper bound on the minimum training sequence length required for "length generalization" (LG)—where a Transformer trained on short sequences maintains performance on arbitrarily long ones. The core argument is a simulation: as long as the internal behavior of a Transformer on a long sequence can be "simulated" by a short sequence of bounded length, LG occurs. This "short sequence upper bound \(N\)" grows polynomially (or exponentially) with the parameter norm, positional period \(\Delta\), locality \(\tau\), vocabulary size \(|\Sigma|\), and inverse error \(\varepsilon^{-1}\).

Quantum Machine Learning Advantages Beyond Hardness of Evaluation

This paper provides the first proof that for data labeled by quantum functions (\(\mathsf{BQP}\)-complete), classical algorithms cannot even "identify" the labeling function itself, even without the requirement to "evaluate" new samples, unless \(\mathsf{BQP}\) falls into the lower levels of the polynomial hierarchy (a collapse widely believed to be false). This shifts the quantum machine learning advantage from "hardness of evaluation" to "hardness of the learning process itself."

Quasi-Equivariant Metanetworks

To address the issue that "metanetworks become sparse and limited in expressivity when strictly equivariant," this paper proposes quasi-equivariance: relaxing the requirement "output follows the same group transformation as the input" to "output follows a data-dependent group transformation," thereby liberating expressivity while strictly preserving functional equivalence. This is implemented as a learnable group-valued scaling layer \(\alpha(\theta)\) layered on an existing equivariant backbone \(\beta(\theta)\). With only 3–5% additional parameters, it achieves consistent performance gains on benchmarks such as CNN/Transformer generalization prediction and INR classification.

Queue Length Regret Bounds for Contextual Queueing Bandits

This paper proposes the "Contextual Queueing Bandits" framework—scheduling tasks with heterogeneous contextual features while learning unknown service rates online. By employing a "policy-switching queue + coupling" argument, it decomposes queue length regret and proves that the algorithm CQB-ε achieves a decaying regret of \(\tilde{O}(T^{-1/4})\) under stochastic contexts, while CQB-Opt achieves polylogarithmic regret of \(O(\log^2 T)\) under adversarial contexts.

Quotient-Space Diffusion Models

This paper proposes "Quotient-Space Diffusion Models," which project traditional equivariant diffusion processes onto a quotient space to eliminate symmetric redundancy and then horizontally lift them back to the original space. This allows the model output within equivalence classes to be arbitrary (reducing learning difficulty) while ensuring the sampling restores the correct symmetric target distribution via a curvature compensation term. It consistently outperforms equivariant diffusion and alignment-based simplification methods in molecular conformation and protein backbone generation.

Random-Projection Ensemble Dimension Reduction

This paper proposes RPEDR—a high-dimensional regression dimension reduction framework based on random projection ensembles. It divides a large number of low-dimensional random projections into disjoint groups, retains the best projection per group based on empirical regression error, and then aggregates these selected projections via SVD. Theoretically, the estimation error decreases with the number of groups \(L\) at a rate no slower than \(L^{-1/2}\). Experimentally, it achieves the best performance in 15 out of 18 simulation settings.

Random Label Prediction Heads for Studying Memorization in Deep Neural Networks

A "random label prediction head" (RLP-head) is attached in parallel to the original task head to predict randomly assigned labels for each sample. The accuracy of this head serves as an empirical proxy for Rademacher complexity to measure memorization. Based on this, a regularization term is designed to suppress memorization. Results show that "reducing memorization" improves generalization on sufficiently sampled datasets but hurts it on under-sampled ones, directly challenging the traditional assumption that "overfitting equals memorization."

Random Spiking Neural Networks are Stable and Spectrally Simple

This paper treats discrete-time LIF Spiking Neural Network (SNN) classifiers as compositions of boolean functions. Using the analysis of boolean functions, it proves that wide SNNs at random initialization are "stable on average"—outputting the same prediction with high probability when input perturbations affect \(O(\sqrt{n})\) coordinates. Based on this, the authors propose the concept of "spectral simplicity," proving that random SNNs are biased toward simple functions with Fourier spectra concentrated in low frequencies. Experiments further show that training enhances this stability.

Reducing Symmetry Increase in Equivariant Neural Networks

This paper systematically characterizes the degenerative phenomenon where the "output symmetry is amplified and directional information is lost" when equivariant neural networks process symmetric inputs. It proves that the amplified symmetry has a symmetry infimum uniquely determined by the feature space structure and provides a computable algorithm and feature design guidelines to predict and avoid harmful symmetry increase.

Reshaping Reasoning in LLMs: A Theoretical Analysis of RL Training Dynamics through Pattern Selection

This paper abstracts LLM reasoning into a two-stage process \(q\to r\to a\) ("selecting a reasoning pattern \(r\), then deriving an answer \(a\) based on it"). It uses a tabular policy and gradient flow to characterize the training dynamics of RLVR and RLIF. The study proves that RLVR stably converges to the reasoning pattern with the highest success rate (strong base models converge quickly, while weak ones undergo an "entanglement phase"), whereas RLIF improves initially but has a 50% probability of converging to the worst pattern during long-term training, theoretically explaining the observed differences in their empirical curves.

Residual Feature Integration is Sufficient to Prevent Negative Transfer

This paper proposes REFINE: concatenating frozen pre-trained source features \(f_{rep}(x)\) with a residual encoder \(h(x)\) trained on the target domain, followed by a shallow adapter. Theoretically analyzed through non-parametric regression, this minimalist architecture provably prevents negative transfer—the worst-case performance is no worse than training from scratch, while the convergence rate smoothly approaches near-parametric rates when source features are useful. Its robustness is validated on image, text, and tabular benchmarks, as well as cross-modal tasks in single-cell spatial omics.

Resurfacing the Instance-only Dependent Label Noise Model through Loss Correction

This paper re-enables the "instance-only dependent, label-independent" noise model (IDN). Based on risk consistency, it designs an instance-aware corrected loss \(\tilde{\ell}\) for any classification-calibrated loss. This approach strictly bridges "Empirical Risk Minimization (ERM) on noisy labels" to "True Risk Minimization on clean labels." Unlike prior methods, it only requires estimating a scalar flip rate \(\rho_x\) per sample instead of a full transition matrix. Generalization capabilities are validated across image, audio, and tabular data using both neural networks and Gradient Boosted Trees.

Revenue Maximization under Sequential Price Competition via the Estimation of s-Concave Demand Functions

This paper investigates the competition among multiple sellers repeatedly setting prices over \(T\) periods. By employing a "semi-parametric least squares + shape constraint" approach to estimate each seller's unknown non-linear demand function, the authors propose the SPE-BR strategy. They prove that prices converge to the Nash Equilibrium at a rate of \(\tilde O(N^{3/4}T^{-1/7})\) with an individual regret of \(\tilde O(N^{3/2}T^{5/7})\), while unifying the existence of equilibrium under the shape constraint of s-concavity.

Revisiting Active Sequential Prediction-Powered Mean Estimation

This paper revisits "active sequential prediction-powered mean estimation": it provides non-asymptotic, anytime-valid, data-dependent confidence bounds for an estimator that previously only had asymptotic guarantees. By employing Follow-the-Regularized-Leader (FTRL) online learning to select query probabilities per round, the theory and experiments jointly demonstrate that when query probabilities are blind to current covariates, the optimal strategy is simply to have the query probability converge to the budget upper bound \(T_b/T\), while sophisticated uncertainty weighting yields negligible additional gain.

Revisiting Nonstationary Kernel Design for Multi-Output Gaussian Processes

This paper revisits nonstationary kernel design for multi-output Gaussian processes (MOGPs) from the spectral domain. It proposes a more general multi-output spectral-kernel duality and constructs the MO-LRN kernel using a low-rank matrix-valued spectral density. This approach significantly improves performance in regression, interpolation, and missing data imputation while maintaining linear parameter scaling.

Revisiting Tree-Sliced Wasserstein Distance through the Lens of the Fermat–Weber Problem

This paper identifies that the true advantage of Tree-Sliced Wasserstein (TSW) over Sliced Wasserstein (SW) lies in its sampling encoding "positional" information, which existing TSW variants (centering Gaussian on data mean) fail to exploit. Leveraging the classic Fermat–Weber problem, the authors use the geometric median as the sampling center for the tree system's intersection, proposing FW-TSW / FW-TSW*. This approach improves gradient flow, topic modeling, and diffusion model training with negligible computational overhead.

Risk Phase Transitions in Spiked Regression: Alignment Driven Benign and Catastrophic Overfitting

This paper provides a closed-form generalization risk formula for the minimum-norm interpolation solution in rank-one spiked covariance linear regression. It demonstrates that spike intensity, alignment between the target and spike direction, model misspecification, and covariate shift collectively trigger phase transitions from benign to catastrophic overfitting.

Robust Amortized Bayesian Inference with Self-Consistency Losses on Unlabeled Data

To address the catastrophic failure of Amortized Bayesian Inference (ABI) on real observations not covered by training simulations, this paper reformulates Bayesian self-consistency (the marginal likelihood identity of Bayes' rule) into a strictly proper loss that does not require ground-truth parameter labels. This allows semi-supervised training on unlabeled real data, where only 4 unlabeled samples can yield accurate, unbiased posteriors even far from the training distribution.

Robust Decision Making with Partially Calibrated Forecasts

When a predictor satisfies only "partial calibration" (weaker than full calibration), this paper characterizes the optimal decision rule through a minimax robust lens. The optimal rule is an optimal response to the "worst-case distribution allowed by the calibration constraints." Furthermore, it proves that once calibration strength reaches "decision calibration"—a computable weak condition—the optimal robust rule collapses into "trust the prediction and play the direct optimal response," perfectly aligning with the semantics of full calibration.

Robust Generalized Schrödinger Bridge via Sparse Variational Gaussian Processes

To address the issue of noisy stage costs in Generalized Schrödinger Bridge (GSB), this paper transforms the deterministic "pinned marginal path" optimization in GSBM into Bayesian inference. By imposing Gaussian Process (GP) priors on the mean and standard deviation functions of the path and treating the CondSOC objective as a (noisy) likelihood, the posterior path is inferred via sparse variational free energy. This approach yields solutions more robust than GSBM in noisy crowd navigation and image translation tasks.

Robustness of Probabilistic Models to Low-Quality Data: A Multi-Perspective Analysis

This paper discovers through controlled noise experiments that robustness to low-quality data varies significantly across probabilistic models (autoregressive LMs are nearly immune, class-conditional diffusion models collapse catastrophically, and classifiers sit in the middle, strengthening with data scale). These differences are unified via information theory, PAC learning, and gradient dynamics into two principles: Richness of Conditional Information and Absolute Information Volume of training data.

Rényi Sharpness: A Novel Sharpness That Strongly Correlates with Generalization

This paper identifies that the true determinant of generalization is the "average dispersion/unevenness" of the Hessian spectrum. It defines Rényi sharpness (the negative Rényi entropy of the normalized Hessian spectrum) using information theory and demonstrates its strong correlation with generalization across various scenarios (Kendall’s \(\tau\) typically between 0.6–0.9, significantly outperforming older metrics like trace, SAM, and PAC-Bayes). Based on this, it derives generalization bounds and a competitive RSAM training regularization algorithm.

Saddle-To-Saddle Dynamics in Deep ReLU Networks: Low-Rank Bias in the First Saddle Escape

Starting from the local dynamics of deep ReLU networks near the origin saddle point under small initialization, this paper characterizes the optimal direction of the first gradient descent escape. It proves that deep weights and activations develop an approximate rank-one bias that strengthens with depth. It further uses a counterexample to show that the first layer of a ReLU network does not strictly require a rank-one structure, unlike deep linear networks.

Sample Complexity and Representation Ability of Test-time Scaling Paradigms

This paper theoretically characterizes the efficiency of three test-time scaling strategies: it proves that self-consistency requires \(\Theta(1/\Delta^2)\) samples while best-of-n requires only \(\Theta(1/\Delta)\) samples (\(\Delta\) being the probability gap between the correct and sub-optimal answers). It also constructively proves that self-correction with verifier feedback allows a single Transformer to simulate "online learning over multiple experts" at test time, extending Transformer expressivity theory from single-task to multi-task settings.

Sampling Complexity of TD and PPO in RKHS

In the unified function space of Reproducing Kernel Hilbert Spaces (RKHS), this paper decouples and analyzes policy evaluation (kernelized TD critic) and policy improvement (KL-regularized proximal/natural gradient updates). It provides non-asymptotic, instance-adaptive convergence bounds dependent on RKHS entropy and derives per-iteration sampling rules required to guarantee \(O(k^{-1/2})\) convergence, validating the theoretically predicted step-size scheduling on CartPole, Acrobot, and HalfCheetah.

Scalable Random Wavelet Features: Efficient Non-Stationary Kernel Approximation with Convergence Guarantees

The paper proposes Random Wavelet Features (RWF), which construct scalable non-stationary kernel approximations by randomly sampling from wavelet families. This approach retains the linear time complexity of random features while providing guarantees for positive definiteness, unbiasedness, and uniform convergence.

Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regime

This paper precisely maps the Empirical Risk Minimization (ERM) problem of two-layer neural networks (diagonal and quadratic) under weight decay training to LASSO and low-rank matrix compressed sensing. This mapping allows for the first analytical characterization of a complete excess risk phase diagram (8 phases, including benign/harmful overfitting and interpolation peaks) in a regime where "true feature learning occurs." Furthermore, it establishes a first-principles correspondence between each scaling law phase and the post-training weight spectrum (bulk / spike / heavy-tail), explaining the empirical observation that "heavy-tailed weight spectra \(\leftrightarrow\) better generalization."

Score-Based Density Estimation from Pairwise Comparisons

This paper proves an exact pointwise collinear relationship between the "score of the target belief density" and the "score of the observable winner marginal density." They are connected by a position-dependent "tempering field" \(\tau(x)\). This transforms the difficult problem of learning density from sparse pairwise comparisons \(x \succ x'\) into a solvable workflow: learning the winner density with a score model, estimating a tempering field, and "de-tempering." The method learns complex multi-modal belief densities using only hundreds to thousands of pairwise comparisons.

Semi-Parametric Contextual Pricing with General Smoothness

For the dynamic pricing problem with "context + unknown noise distribution," this paper combines "local polynomial regression + constrained least squares + sub-linear forced exploration" to construct a unified algorithm, LPSP, that holds for any smoothness \(\beta \ge 1\). It achieves a regret upper bound of \(\tilde O(T^{\frac{\beta+1}{2\beta+1}})\), unifying and improving upon previously isolated results of \(\tilde O(T^{2/3})\) for \(\beta=1\) and \(\tilde O(T^{3/5})\) for \(\beta=2\).

Separable Neural Networks: Approximation Theory, NTK Regime, and Preconditioned Gradient Descent

The paper systematically establishes the theoretical foundation for Separable Neural Networks (SepNN): it proves that CP/TT/Tucker-type SepNNs possess universal approximation capabilities, derives their NTK regimes under infinite-width/infinite-rank and fixed-rank settings, and proposes SepPGD. This method utilizes low-dimensional separable preconditioning matrices to adjust the NTK spectrum, accelerating training convergence in grid-coordinate tasks such as Implicit Neural Representations (INR) and Physics-Informed Neural Networks (PINN).

Sharp Asymptotic Theory for Q-Learning with LD2Z Learning Rate and Its Generalization

This paper provides the first complete set of asymptotic theories for Q-learning using "Linear Decay to Zero" (LD2Z, \(\eta_{t,n}=\eta(1-t/n)\)) and its power-law generalization (PD2Z-\(\nu\), \(\eta_{t,n}=\eta(1-t/n)^\nu\)). This includes sharp non-asymptotic error bounds, a Central Limit Theorem (CLT) for tail Polyak-Ruppert averaging estimators, and a strong invariance principle (time-consistent Gaussian approximation) for partial sum processes. It theoretically explains why this "two-stage" step size enjoys both the fast forgetting of initial values from constant step sizes and the asymptotic convergence guarantees of polynomial step sizes.

Singleton-Optimized Conformal Prediction

To address the pain point where conformal prediction sets are often too large and require manual intervention, this paper proposes SOCOP, a nonconformity score that directly optimizes the probability of singleton sets (rather than mean length). By geometrizing the per-sample Lagrangian subproblem as finding the "lower convex hull of \(K\) points in 2D," the scores are computed in \(O(K)\) time. This approach reduces the non-singleton rate by up to 20% in image classification and LLM multiple-choice tasks with almost no increase in mean set size.

Slicing Wasserstein over Wasserstein via Functional Optimal Transport

This paper proposes the Double-Sliced Wasserstein (DSW) distance, which efficiently approximates the costly Wasserstein over Wasserstein (WoW) distance using a two-layered slicing approach: "spherical domain slicing + \(L^2\) Gaussian process slicing of quantile functions." It proves that minimizing DSW is equivalent to minimizing WoW on discrete meta-measures, avoiding the numerical instabilities of existing sliced methods that rely on high-order moments. It serves as a scalable alternative for WoW in comparing datasets, shapes, and images.

Smooth Calibration Error: Uniform Convergence and Functional Gradient Analysis

This paper establishes a finite-sample theory for smooth calibration error (smooth CE). It first proves that the population smooth CE can be controlled by "training smooth CE + generalization gap" via uniform convergence. It then demonstrates that the training smooth CE is upper-bounded by the functional gradient norm of the loss. Consequently, it provides the first provable guarantees for "calibration + accuracy" for gradient boosted trees, kernel boosting, and two-layer neural networks simultaneously.

Softmax is not Enough (for Adaptive Conformal Classification)

This paper points out that adaptive conformal classification relying solely on softmax probabilities inherits the overconfidence issues of deep classifiers. It proposes using Helmholtz free energy in the logit space for sample-level reweighting of non-conformity scores, enhancing the distinctness of prediction sets for easy, hard, and OOD inputs while maintaining conformal coverage guarantees.

Softmax Transformers are Turing-Complete

This paper provides the first proof that softmax attention Transformers with Chain-of-Thought (CoT) are Turing-complete. This construction inherits length generalization guarantees by simulating a Minsky counter machine through the intrinsic "counting" capability of softmax (via C-RASP), rather than hard-coding Turing machine tape heads. It utilizes a task-agnostic Relative Position Encoding (RPE) to encode arbitrary inputs into numerical values.

Some Neural Networks Inherently Preserve Subspace Clustering Structure

This paper uses perturbation theory to prove that when data possesses a "union-of-subspaces (UoS)" structure, single-layer (and even multi-layer) networks with activations such as ReLU preserve this clustering structure exactly, provided a spectral gap condition is met. Furthermore, networks spontaneously learn weights \(W\) satisfying this condition during standard training without any explicit regularization—implying that such networks are effectively "performing clustering via a closed-form solution."

Splat Regression Models

This paper proposes Splat Regression Models—a class of function approximators that represent output as a weighted mixture of "heterogeneous, anisotropic bump functions (splats)," optimized via Wasserstein-Fisher-Rao gradient flow in measure space. The framework incorporates the popular 3D Gaussian Splatting as a special case and outperforms KAN/MLP by \(10\sim100\times\) in terms of error across low-dimensional approximation, regression, and physics-informed fitting tasks using significantly fewer parameters.

Stable Coresets: Unleashing the Power of Uniform Sampling

This paper introduces the new concept of "stable coresets" positioned between weak and strong coresets. It proves that uniform sampling alone (a sample of size \(O(\epsilon^{-2}\log d)\)) can construct a stable coreset for the 1-median problem under the \(\ell_1\) metric. This elevates uniform sampling from a "cheap, data-oblivious, and streamable/distributed" heuristic to a tool with rigorous guarantees that transfer to all sub-metrics embeddable in \(\ell_1\) (e.g., Kendall-tau, Jaccard).

Statistical and Structural Identifiability in Representation Learning

This paper decomposes "representation stability" into two independent concepts: statistical identifiability (consistent representations across multiple retraining sessions) and structural identifiability (representations aligned to true generative factors). It proposes a "near-identifiability" definition with error tolerance \(\epsilon\) and proves statistical \(\epsilon\)-near-identifiability for a class of models with non-linear decoders (e.g., MAE, supervised learners, GPT intermediate layers). It indicates that using linear ICA to post-process the latent space eliminates residual linear uncertainty, yielding a minimalist "recipe" for disentanglement. This approach achieves SOTA on synthetic disentanglement benchmarks using a vanilla autoencoder and separates biological variation from batch effects in biological foundation models.

Stop Guessing: Choosing the Optimization-Consistent Uncertainty Measurement for Evidential Deep Learning

This paper revisits Evidential Deep Learning (EDL) from an optimization perspective, proving that training EDL with UCE loss is equivalent to implicitly maximizing inter-class margins (isomorphic to the Crammer–Singer multiclass SVM). Based on this, it proposes the "Optimization Consistency Principle" as a criterion for selecting uncertainty measurements and designs a simple, interpretable new metric, MPU (Margin-aware Predictive Uncertainty), which significantly outperforms traditional metrics in OOD and misclassification detection.

Strong Correlations Induce Cause Only Predictions in Transformer Training

This paper identifies and characterizes a new phenomenon in Transformer training termed Correlation Crowding-Out (CCO): when a causal feature in the data has a correlation with the target strong enough to dominate all spurious features, gradient descent (GD) spontaneously filters out spurious cues without any invariance regularization or multi-environment labels. The model converges to a predictor relying almost exclusively on causal features. This is supported by theoretical proofs of a "Occupation-Crowding-Out" two-stage mechanism and validated through vision and language experiments.

Sublinear Spectral Clustering Oracle with Little Memory

This paper designs the first "small-memory" sublinear spectral clustering oracle for clusterable graphs. By using a new subroutine that estimates random walk collision probabilities in batches, it reduces the space required to construct the data structure from the previous \(\Omega(\sqrt{n})\) to potentially below \(n^{0.01}\). This achieves a space-time trade-off curve of \(S \cdot T = \tilde{O}(n)\) and proves that this curve is nearly optimal for a natural class of methods.

Subquadratic Algorithms and Hardness for Attention with Any Temperature

This paper answers the fundamental question of whether attention can be computed efficiently at any temperature. For head dimension \(d=O(1)\), it provides the first true subquadratic algorithm \(\tilde{O}(n^{2-1/d}\cdot\mathrm{polylog}(B/\varepsilon))\) with only logarithmic dependence on the entry bound \(B\). Furthermore, it uses Max-IP / OV reductions to prove that the standard algorithm is essentially optimal in the ranges \(d=2^{\Omega(\log^* n)}\) and \(d=\mathrm{poly}(n)\), nearly completing the complexity landscape of attention computation.

Subspace Kernel Learning on Tensor Sequences

This paper proposes UKTL (Uncertainty-driven Kernel Tensor Learning), which unfolds high-order tensors into subspaces along each mode, constructs learnable "sum-product" kernels on Grassmann manifolds to compare tensor sequences, utilizes Nyström approximation with soft k-means dynamic pivots for scalability, and adaptively down-weights noisy dimensions via mode-wise uncertainty. Trained end-to-end, it outperforms Graph Convolutional Networks (GCN), Hypergraphs, and Transformer-based methods on three skeleton action recognition benchmarks.

SVD Provably Denoises Nearest Neighbor Data

Under the semi-random model of "low-dimensional signal + high-dimensional Gaussian noise," this paper proves that performing SVD twice on noisy data and projecting points onto the top-\(k\) singular subspace allows for accurate recovery of the noise-free nearest neighbors within a noise level \(\sigma = O(1/k^{1/4})\), an interval significantly wider than previous work. It also provides a matching information-theoretic impossibility lower bound of \(\sigma \gg 1/k^{1/4}\).

T-Tamer: Provably Taming Trade-offs in ML Serving

The trade-offs in cascaded/early-exit inference—specifically "when to exit and which sub-model to invoke"—are unified as a costly exploration problem on a DAG. It is proven that "recall" (the ability to revisit and select a previously examined model) is a necessary and sufficient condition for provable optimality: recall-free strategies cannot achieve even a constant approximation ratio, whereas a dynamic indexing strategy with recall achieves online optimality in polynomial time.

TESSAR: Geometry-Aware Active Regression via Dynamic Voronoi Tessellation

For active learning in regression tasks, this paper proposes using the geometric structure of Voronoi tessellation to select samples. The core is VLDM (Voronoi-based Least Disagree Metric), which measures how easily a sample's "Voronoi cell membership" flips after perturbing labeled sites, thereby locating high-variance interior regions. By compounding this with a distance term (covering the periphery) and a density term (reflecting representativeness), the three factors form the TESSAR acquisition score, which achieves or exceeds current state-of-the-art results on 14 tabular regression benchmarks.

Test-Time Verification via Optimal Transport: Coverage, ROC, & Sub-Optimality

This paper reformulates "test-time scaling with verifiers" as an Optimal Transport (sampling) problem. It provides a unified framework to precisely characterize the geometric relationship between generator coverage, verifier ROC, and sampling algorithm sub-optimality. It reveals a three-regime nature of the sub-optimality-coverage curve (transport / policy improvement / saturation) and designs and analyzes sequential (SRS, SMC) and batch (BRS) sampling algorithms accordingly.

Testing Fourier Sparsity via Implicit Sensing

This paper investigates the property testing problem of whether a Boolean function is Fourier sparse. Given query access to \(f:\mathbb{F}_2^n\to\{-1,+1\}\), the goal is to determine if \(f\) is \(s\)-Fourier sparse or far from any \(s\)-sparse function in Hamming distance. The authors provide a non-adaptive tester with query complexity \(\tilde O(s^4)\) (independent of dimension \(n\)) and prove a lower bound of \(\Omega(s)\). Both results significantly improve the \(\tilde O(s^{14})\) upper bound and \(\Omega(\sqrt s)\) lower bound established by Gopalan et al. (2011).

Testing Most Influential Sets

Addressing the phenomenon where "a few samples can overturn model conclusions," this paper derives an exact closed-form formula for subset influence in linear least squares and characterizes the asymptotic distribution of the "maximum influence" using extreme value theory (heavy-tailed Fréchet for fixed-size subsets and light-tailed Gumbel for growing subsets). This transforms empirical heuristics about whether "this influence is too outrageous" into a rigorous hypothesis test with p-values.

The Coverage Principle: How Pre-Training Enables Post-Training

This paper theoretically answers "what pre-training actually leaves for post-training (RL / test-time scaling)"—the answer is not cross-entropy, but a quantity called coverage profile. The authors prove that next-token prediction implicitly optimizes coverage, and that coverage generalizes faster than cross-entropy without being hindered by sequence length, thereby explaining the anomaly of "why models with lower cross-entropy can have worse Best-of-N performance."

The Effect of Attention Head Count on Transformer Approximation

This paper proves from an approximation theory perspective that the number of attention heads in a Transformer is not merely an engineering hyperparameter. When the head count \(h\) reaches the intrinsic task dimension \(D\), generalized retrieval functions can be efficiently approximated. However, when \(h < D\), the parameter count must deteriorate exponentially with the sequence length \(T\). These phase transition phenomena are observed in synthetic retrieval, MS MARCO, and CIFAR-10 experiments.

The Expressive Limits of Diagonal SSMs for State-Tracking

This work establishes a complete characterization of the expressive power of input-dependent complex diagonal (DCD) SSMs on group state-tracking tasks: a single layer cannot track any non-abelian group, whereas \(k\) layers can track a group \(G\) if and only if \(G\) admits a subnormal series of length \(k\) with abelian factors—precisely defining the strict benefit of depth for expressivity. Furthermore, experiments reveal a significant gap between theoretical expressivity and learnability.

The Lie of the Average: How Class Incremental Learning Evaluation Deceives You?

This paper points out that the common "randomly sample 3-5 class sequences and report mean/variance" evaluation method in Class-Incremental Learning (CIL) systematically overestimates the mean and severely underestimates the variance, fundamentally missing extreme sequences. The authors theoretically prove the infeasibility of random sampling and propose the EDGE protocol—utilizing CLIP text encoders to calculate inter-class semantic similarity and constructing "Hardest/Easiest/Median" extreme sequences to approximate the true performance distribution, thereby providing more reliable model selection and robustness assessment.

The Logical Expressiveness of Topological Neural Networks

This paper establishes the first "algorithm–logic–game" tripartite characterization for Topological Neural Networks (TNNs). It proposes the \(k\)-CCWL, a higher-order WL test on combinatorial complexes; the topological counting logic \(\text{TC}_k\) with pairwise counting quantifiers; and the topological \((k{+}2)\)-pebble game. The authors strictly prove the equivalence: \(k\text{-CCWL} \equiv \text{TC}_{k+2} \equiv\) topological \((k{+}2)\)-pebble game, thereby precisely defining the binary classifiers that TNNs can represent.

The Price of Robustness: Stable Classifiers Need Overparameterization

The authors establish stability-generalization bounds for discontinuous classifiers, proving a "law of robustness cost" in classification tasks: any interpolating classifier with parameter count \(p \approx n\) must be unstable; achieving high stability requires overparameterization of magnitude \(p \approx nd\).

The Serial Scaling Hypothesis

This is a position + theoretical paper: the authors use computational complexity (the TC circuit class) to categorize machine learning problems into "efficiently parallelizable" and "inherently serial." They argue that key tasks such as reasoning, decision-making, and physical simulation belong to the latter. They prove for the first time that even if a diffusion model samples for thousands of steps, its computational depth remains constant, rendering it unable to solve inherently serial problems. Therefore, merely stacking parallel compute (wider networks, more GPUs) is destined to plateau; progress must rely on scaling serial computation.

The Softmax Bottleneck Does Not Limit the Probabilities of the Most Likely Tokens

This paper theoretically revisits the "softmax bottleneck": it proves that even randomly initialized output projection matrices can assign arbitrarily accurate probabilities to a significant number of top tokens (approx. 26 for GPT-2 scale, 95 in practice, and over 1000 for Llama2), questioning whether the softmax bottleneck significantly limits LLM capabilities in realistic scenarios.

Theoretical Analysis of Contrastive Learning under Imbalanced Data: From Training Dynamics to a Pruning Solution

This paper provides a training dynamics theory for contrastive learning under imbalanced data. Analyzing a "Transformer-MLP + sparse coding data model," the authors prove that neuron weights undergo a three-stage evolution where minority features are learned more weakly and with more interference due to low frequency. The study theoretically demonstrates that magnitude pruning amplifies gradient updates in minority feature directions, thereby restoring representation quality compromised by imbalance (validated by linear probe experiments on CIFAR-LT / ImageNet-LT).

Theoretical Modeling of Large Language Model Self-Improvement Training Dynamics Through Solver-Verifier Gap

This paper models the training process of LLM "self-improvement" as a set of coupled differential equations inspired by physical potential energy. The gap between "solver capability" and "verifier capability" drives the exponential convergence of both throughout training iterations. This model can fit real training curves, quantify the upper bound of self-improvement, and further analyze the optimal allocation of external data in "cross-improvement" scenarios.

Theory of Scaling Laws for In-Context Regression: Depth, Width, Context and Time

This paper provides a solvable theoretical model for deep linear self-attention in in-context linear regression (ICL). By analyzing the joint limit where data dimension, context length, and residual stream width scale proportionally, the authors precisely determine the asymptotic behavior of risk. They reveal that "when depth is useful" depends entirely on the covariance structure of pre-training tasks, deriving a Chinchilla-style scaling law encompassing width, depth, time, and context length with a compute-optimal shape of \(L \propto N^\nu\).

Tight Bounds for Schrödinger Potential Estimation in Unpaired Data Translation

This paper provides the first non-asymptotic high-probability generalization error bound for the Empirical Risk Minimization (ERM) estimator of the Schrödinger potential. Using only i.i.d. samples from the source and target distributions and employing the Ornstein-Uhlenbeck (OU) process as the reference dynamics, the KL divergence between the estimated coupling and the optimal coupling is bounded at a fast rate of \(O(\log^3 n / n)\), significantly improving upon the previous \(O(1/\sqrt{n})\) results.

To Augment or Not to Augment? Diagnosing Distributional Symmetry Breaking

This paper proposes a "two-sample classifier test" metric \(m(p_X)\) to quantify the distributional symmetry breaking of a dataset (i.e., the degree to which \(x\) and its transformation \(gx\) appear with unequal probabilities). Combined with a task-relevance metric \(t(p_{X,Y})\) and a ridge regression theory, it systematically answers "when should data augmentation/equivariant methods be used, and when are they harmful?" It reveals that common point cloud benchmarks like QM9 and ModelNet40 are actually highly "canonicalized," and the benefits of augmentation depend strongly on the dataset.

To Infinity and Beyond: Tool-Use Unlocks Length Generalization in State Space Models

This paper theoretically proves that fixed-memory State Space Models (SSMs) cannot solve "true long-form generation tasks" regardless of the chain-of-thought (CoT) length. However, by enabling interactive calls to external memory tools, SSMs can achieve infinite length generalization for any computable long-form task—e.g., training on 5-digit addition and correctly performing 1000-digit addition.

Tokenisation over Bounded Alphabets is Hard

While finding an "optimal tokeniser" was previously proven to be NP-complete, those proofs assumed an infinite alphabet (unrealistic). This paper restricts tokenisation to finite, even binary or unary alphabets, proving it remains NP-complete and APX-hard (precluding polynomial-time approximation schemes unless P=NP). This establishes the theoretical necessity of heuristic algorithms like BPE and UnigramLM.

Toward Practical Equilibrium Propagation: Brain-Inspired Recurrent Neural Network with Feedback Regulation and Residual Connections

Addressing the long-standing issues of slow training and instability in Equilibrium Propagation (EP), this paper proposes FRE-RNN, a brain-inspired recurrent network with feedback regulation and residual connections. By scaling only the feedback path intensity with a small coefficient \(\beta_i\), the RNN convergence is accelerated, while residual connections mitigate the resulting vanishing gradients. This approach makes EP training one to two orders of magnitude faster than existing implementations while achieving accuracy comparable to Backpropagation (BP) on MNIST/CIFAR-10.

Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Bandits

This paper provides the weakest data coverage conditions required for offline \(f\)-divergence regularized contextual bandits to achieve an \(\widetilde{\Theta}(\epsilon^{-1})\) sample complexity under a regularized objective. For the most commonly used inverse KL regularization, a new pessimistic estimation analysis achieves \(\widetilde{O}(\epsilon^{-1})\) under single-policy concentrability for the first time, accompanied by nearly matching lower bounds. For divergences with a strongly convex \(f\), it is proven that an \(\widetilde{\Theta}(\epsilon^{-1})\) rate can be achieved without any pessimistic estimation or coverage conditions.

Towards a Theoretical Understanding of In-Context Learning: Stability and Non-i.i.d. Generalisation

Under realistic conditions without assuming token orthogonality or i.i.d. sampling, this paper employs "algorithmic stability + discrepancy measure" to derive generalization error bounds for non-linear Transformers in the context of ICL next-token prediction. It reveals how optimization configurations and loss smoothness collectively determine stability, how training/test distribution alignment dictates generalizability, and proves that unconstrained autoregressive prediction length leads to error accumulation and generalization collapse.

Towards Persistent Noise-Tolerant Active Learning of Regular Languages with Class Query

This paper proposes the pMAT (Probabilistic Minimally Adequate Teacher) formal framework to capture the scenario where an LLM serves as a persistent noisy Membership Query (MQ) Oracle and a simulator/checker serves as an exact Equivalence Query (EQ) Oracle. It introduces the CAPAL algorithm—which replaces blind trust in single MQ labels with statistical "homomorphical class queries" and uses discrimination trees to compress the set of distinguishing suffixes—enabling the provable learning of correct DFAs under persistent noise while significantly reducing LLM calls (requiring only a single call for code-based oracles).

Towards Safe and Optimal Online Bidding: A Modular Look-Ahead Lyapunov Framework

This paper proposes L2FOB, a modular framework for online bidding under simultaneous budget and ROI constraints. By employing optimistic reward/pessimistic cost estimation, look-ahead virtual queues, and multipliers shaped by convex potential functions, the framework provides adaptive regret and anytime ROI violation bounds without relying on the Slater condition. It achieves or exceeds state-of-the-art results across various auction and feedback settings.

Towards Sampling Data Structures for Tensor Products in Turnstile Streams

This paper formalizes the identification of "important coordinates" in attention matrices as a streaming sampling problem. It proves that softmax/exponential sampling inevitably encounters a quadratic space barrier in general turnstile streams, while providing \(\ell_2\) samplers for polynomial attention and specialized data structures for tensor products.

Tractability via Low Dimensionality: The Parameterized Complexity of Training Quantized Neural Networks

This paper systematically investigates the (parameterized) complexity of "training fully quantized ReLU networks" for the first time. It proves that training is NP-hard even under extremely simplified architectures such as binary quantization, single output, and no hidden layers. However, by treating the input dimension \(\alpha\) combined with network width (or more generally, treewidth) and either the output dimension \(\omega\) or the error bound \(\ell\) as parameters, the problem becomes Fixed-Parameter Tractable (FPT). The core conclusion is that "the hardness lies in high data dimensionality, rather than architectural complexity."

Trained on Tokens, Calibrated on Concepts: The Emergence of Semantic Calibration in LLMs

This paper discovers that base LLMs trained solely on next-token prediction are also well-calibrated at the semantic level (the confidence in the "meaning" of their answers matches the actual accuracy). It provides a theoretical mechanism based on the equivalence between "calibration and local loss optimality" to explain this emergence, predicting that instruction-tuning and chain-of-thought (CoT) disrupt this calibration—all three predictions are empirically verified.

Training-Free Determination of Network Width via Neural Tangent Kernel

This paper uses the minimum eigenvalue \(\mu_{\min}\) of the Neural Tangent Kernel (NTK) to theoretically bound the test error of infinite and finite-width networks. Based on this, it proposes a training-free metric: scanning \(\mu_{\min}\) at different widths during initialization to find the inflection point where growth saturates, defined as the "cardinal width"—the point beyond which further widening yields no additional generalization benefit.

Transfer Learning in Infinite Width Feature Learning Networks

Under mean-field/µP parameterization, the authors use Dynamical Mean-Field Theory (DMFT) to derive a transfer learning theory for infinite-width MLPs trained with gradient flow. They quantify the utility of pre-training as closed-form functions of source/target task alignment \(\alpha_s\), data sizes \(\nu_1, \nu_2\), and feature learning strengths \(\gamma_1, \gamma_2\), while providing a phase diagram for positive and negative transfer.

Transformers Are Inherently Succinct

This paper evaluates Transformer capabilities using a different metric: instead of asking "which languages it can recognize," it asks "how concisely it can describe a language." The results prove that fixed-precision Transformers (UHAT) are extremely "succinct," describing certain languages exponentially more concisely than LTL and RNNs, and doubly-exponentially more than finite automata. The trade-off is that its emptiness/equivalence verification problem is EXPSPACE-complete (impossible to solve efficiently in the worst case).

Transformers as Measure-Theoretic Associative Memory: A Statistical Perspective and Minimax Optimality

This paper re-models the "associative memory" of Transformers at the level of probability measures—where the context is a mixture of token distributions and attention is an integral operator acting on measures. It proves that a shallow (depth 2) "Measure-theoretic Transformer + MLP" trained via Empirical Risk Minimization (ERM) can learn the mapping of "recalling the distribution of relevant components and then predicting scalars." The generalization error converges at a sub-polynomial rate of \(\exp(-\Theta((\log n)^{\alpha/(\alpha+1)}))\), and a minimax lower bound with a matching exponential term is provided, demonstrating that this convergence order is optimal.

Transformers as Unsupervised Learning Algorithms: A study on Gaussian Mixtures

This paper uses meta-learning to train a shared transformer (TGMM) to simultaneously estimate parameters for Gaussian Mixture Models (GMM) with varying numbers of components. Experimentally, it overcomes the respective weaknesses of EM and spectral methods. Theoretically, it is the first to prove that transformers can approximate both the EM algorithm and the core of spectral methods—third-order tensor power iteration.

Transformers Learn Latent Mixture Models In-Context via Mirror Descent

This paper proposes an in-context learning task based on the "Mixture of Transition Distributions (MTD)," requiring a transformer to infer the causal importance (mixture weight \(\lambda\)) of each historical token within the context. The authors provide an explicit construction of a three-layer disentangled transformer and prove that it precisely implements one-step Mirror Descent (MD), with this one-step estimator being a first-order approximation of the Bayes-optimal predictor. Transformers trained from scratch align closely with this construction in terms of predictive distributions, attention patterns, and learned transition matrices.

Transformers Trained via Gradient Descent Can Provably Learn a Class of Teacher Models

This paper proves that a one-layer Transformer with position-only attention, when trained via gradient descent on population risk, can learn a large class of teacher models sharing a bilinear structure at a tight \(\Theta(1/T)\) rate and inherits the teacher's out-of-distribution (OOD) generalization under mild second-moment conditions.

Transformers with Endogenous In-Context Learning: Bias Characterization and Mitigation

This work introduces Endogenous In-Context Learning (EICL), a setting where label noise \(\epsilon\) correlates with features \(X\) due to hidden confounding. It theoretically proves that Transformers pretrained on such data exhibit ICL prediction bias proportional to the confounding strength and proposes Double-Debiasing (DDbias): a fine-tuning-free method that "prompts the model twice" (once for the original label and once for the residual) using a few unconfounded samples to correct the bias.

Tree-sliced Sobolev IPM

This paper replaces the 1-Wasserstein—which only has a closed-form solution for \(p=1\)—within the Tree-Sliced Wasserstein (TSW) kernel with a "regularized Sobolev IPM solvable in closed-form on trees." This yields TS-Sobolev: a family of tree-sliced metrics efficiently computable for any order \(p \ge 1\). When \(p=1\), it reduces exactly to TSW; for \(p>1\), its computational complexity remains identical to \(p=1\) TSW. It comprehensively outperforms the SW/TSW series in downstream tasks such as gradient flow, diffusion models, self-supervised learning, and topic modeling.

Tversky Neural Networks: Psychologically Plausible Deep Learning with Differentiable Tversky Similarity

This paper reformulates Tversky's "common features + distinctive features" psychological similarity theory into a neural network layer trainable via gradient descent. By replacing linear projections with Tversky Projections, it demonstrates stronger expressivity, parameter efficiency, and improved interpretability across GPT-2 language modeling and ResNet-50 image classification.

Two-Layer Convolutional Autoencoders Trained on Normal Data Provably Detect Unseen Anomalies

Utilizing feature learning tools, this paper provides the first provable theoretical explanation for why a two-layer convolutional autoencoder can detect unseen anomalies when trained only on normal data: during training, convolutional kernels are absorbed by a "cone set" of normal features and align with these feature directions; consequently, they show almost no response to signals where patches are replaced by anomalies, leading to significantly higher reconstruction errors for anomalies compared to normal data.

Two Failure Modes of Deep Transformers and How to Avoid Them: A Unified Theory of Signal Propagation at Initialisation

This paper leverages the Random Energy Model (REM) from statistical physics to provide an asymptotically exact theory of signal propagation in deep Transformers at initialization. It unifies "rank collapse" and "entropy collapse" as a single phase transition controlled by the query/key initialization variance \(\beta\). Based on this, it derives an algorithm to generate "trainability maps," guiding practitioners on selecting residual strength and initial weights to ensure trainability in deep models.

Two (narrow) heads are better than (an arbitrarily wide) one

Using the Endpoint Selection Problem, this paper proves that a single-head attention-only Transformer of arbitrary width and precision cannot perform endpoint selection on cyclic directed graphs, whereas two narrow heads can solve it with zero error on all directed graphs, providing a clear separation in the expressivity of multi-head attention.

Understanding and Relaxing the Limitations of Transformers for Linear Algebra

This paper systematically reveals three acute failures of "using Transformers for matrix operations"—exploding computational overhead, catastrophic failure on out-of-distribution (OOD) matrices (even identity matrices), and the realization that models perform statistical interpolation rather than learning algorithms. Through four interventions—learnable projections, linear attention, recurrence, and structured training distributions—the authors propose RangeFormer, scaling Transformer matrix operations to \(1000\times1000\) for the first time and successfully applying them to downstream iterative tasks like Gaussian Processes and randomized SVD.

Understanding In-Context Learning on Structured Manifolds: Bridging Attention to Kernel Methods

This paper establishes the first theoretical framework for In-Context Learning (ICL) of Hölder function regression on manifolds. It proves that the attention mechanism of transformers essentially performs Gaussian kernel regression (Nadaraya–Watson estimation) and derives generalization error bounds revealing that the error decay rate depends solely on the intrinsic dimension \(d\) of the data rather than the ambient dimension \(D\).

Understanding the Dynamics of Forgetting and Generalization in Continual Learning via the Neural Tangent Kernel

This paper characterizes the dynamic upper and lower bounds of forgetting and generalization error "during training" (rather than after convergence) under the NTK paradigm. It proves that lowering the Lipschitz constant of the loss with respect to predictions and minimizing the cross-task kernel to zero simultaneously mitigate forgetting and improve generalization. Based on this, OGD+ and OPGD algorithms are designed and validated on Permuted/Rotated MNIST and Split CIFAR-100.

Understanding the Mechanisms of Fast Hyperparameter Transfer

This paper establishes a conceptual framework for the empirical phenomenon where hyperparameters (especially learning rates) in µP can be rapidly transferred from small to large models. The authors strictly distinguish between "weak," "fast," and "useful" transfer via convergence rates. They propose a top-k loss decomposition linearized along EMA trajectories, splitting the final loss into "width-stable top-k components that determine optimal hyperparameters" and "residual components that continuously reduce loss with width but barely affect hyperparameter selection." This mechanism is validated in synthetic cases and LLM pre-training.

UniCon: Unified Framework for Efficient Contrastive Alignment via Kernels

UniCon reformulates contrastive learning objectives, such as CLIP and InfoNCE, into a spectral problem driven by a contrastive similarity weight matrix \(S(\gamma)\). By extending this to non-linear encoders via kernel methods, it replaces prolonged SGD training with closed-form spectral updates, delivering order-of-magnitude acceleration while maintaining or enhancing performance in multimodal retrieval.

Unlearning During Training: Domain-Specific Gradient Ascent for Domain Generalization

This paper proposes Identify and Unlearn (IU): a model-agnostic "in-training unlearning" module. After each epoch, influence functions are used to identify training samples that "increase model complexity while contributing little to generalization," and Inter-Domain Variance (IDV) is employed to precisely locate channels capturing domain-specific features. Domain-Specific Gradient Ascent (DSGA) is then performed on these channels using the identified samples to erase domain-specific dependencies while preserving domain-invariant features, achieving an average gain of up to 3.0% across 7 benchmarks and 15+ DG baselines.

Unveiling the Basin-like Loss Landscape in Large Language Models

This paper discovers that the loss landscape of LLMs presents "basins" as model scale increases—any perturbation of parameters within the basin preserves performance, while moving outside leads to a sudden collapse. Based on this, randomized smoothing is used to prove that performance degradation from arbitrary fine-tuning or jailbreaking is bounded by the basin radius. A GO optimizer is proposed to actively enlarge these basins to mitigate catastrophic forgetting.

Variance-Dependent Regret Lower Bounds for Contextual Bandits

This paper establishes the first lower bound for "variance-dependent regret" in linear contextual bandits that matches the upper bound (up to logarithmic factors) at \(\Omega\!\big(d\sqrt{\sum_k \sigma_k^2}\big)\). This result covers any pre-determined variance sequence as well as adaptive weak adversary sequences. Furthermore, it demonstrates through a counter-example that such lower bounds cannot hold once an adversary can select variances after observing the decision sets.

Variational Deep Learning via Implicit Regularization

This paper proposes Implicit Bias VI (IBVI): when training a variational distribution over weights, it directly discards the KL regularization term in the ELBO, relying solely on SGD's implicit bias to "select" the distribution. It rigorously proves that in overparameterized linear models, this implicit bias is equivalent to generalized variational inference regularized by the 2-Wasserstein distance (rather than KL). This approach preserves the generalization capabilities of standard neural networks while providing well-calibrated uncertainty for free, with almost no additional computational overhead.

Variational Inference for Cyclic Learning

This paper treats intermediate data points in cyclic learning as latent variables and formulates cross-domain mappings as conditional probabilities. By doing so, it derives the "cycle-consistency" objective as an Evidence Lower Bound (ELBO) using variational inference. Based on this, two general training strategies are proposed: single-step joint optimization and EM-based alternating optimization. This framework not only provides a theoretical explanation for CycleGAN (introducing CycleGN as a GAN-free alternative) but also achieves SOTA performance in unsupervised tracking with CycleTrack / CycleTrack-EM.

Weak Correlations as the Underlying Principle for Linearization of Gradient-Based Learning Systems

This paper proposes that "weak derivative correlations" are the fundamental criterion for parameter-space linearization in gradient-based learning systems. As long as the correlation between first-order and higher-order derivatives at initialization decays with width, the training dynamics will approach the Neural Tangent Kernel (NTK) linear model. Furthermore, this deviation can be bounded by a width-dependent upper limit during SGD training.

When Bias Meets Trainability: Connecting Theories of Initialization

This work demonstrates a rigorous mathematical equivalence between the core quantities of two independent theories characterizing randomly initialized wide networks: Mean-Field (MF) theory, which analyzes gradient stability/trainability, and Initial Guessing Bias (IGB) theory, which analyzes initial prediction preferences. It derives the counter-intuitive conclusion that the "Edge of Chaos" initialization, which makes networks most trainable, corresponds precisely to the most biased (rather than neutral) state, where this bias is rapidly absorbed during early training.

Why Ask One When You Can Ask k? Learning-to-Defer to the Top-k Experts

This paper generalizes the Learning-to-Defer (L2D) framework from "deferring to a single expert" to "consulting the \(k\) most cost-effective entities." It introduces a k-independent surrogate loss that can be trained once and switched to any \(k\) during deployment, proving its Bayes / H-consistency for both one-stage and two-stage paradigms. Furthermore, an adaptive cardinality function Top-k(x) is proposed based on sample difficulty, outperforming traditional single-expert methods in precision–cost trade-offs.

Why High-Rank Neural Networks Also Generalize?: An Algebraic Framework Based on RKHS

Ours uses Koopman operators, group representations, and Reproducing Kernel Hilbert Spaces (RKHS) to formulate deep networks as an algebraic "product of operators," deriving a new Rademacher complexity bound. The denominator features the determinant of the weight matrix \(\det(W_l^*W_l)^{1/4}\), theoretically explaining the empirical phenomenon that "high-rank weight matrices with large singular values generalize well." This work also extends Koopman theory to non-smooth activations (like tanh, sigmoid, Leaky ReLU) and bounded data spaces for the first time.

Why Less is More (Sometimes): A Theory of Data Curation

This paper utilizes high-dimensional binary classification and Random Matrix Theory (RMT) to derive precise test error scaling curves for data curation strategies such as "keep hard samples," "keep easy samples," and "full training." It proves that the "less is more" phenomenon (where a small subset of high-quality data is superior) only occurs in the quadrant of "abundant data + sufficiently strong generator," providing a unified theoretical explanation for why methods like LIMO and s1 are effective yet fail on the most difficult tasks.

Why We Need New Benchmarks for Local Intrinsic Dimension Estimation

This paper argues that current neural LID estimators evaluate themselves on outdated benchmarks: either overly simple synthetic data or real data with unknown LID, which masks true performance. The authors propose a principled benchmark construction toolbox (mapping the same manifold to multiple domain representations, designing harder variants for key manifold properties, and controlled transformations with known LID changes for stress testing). They systematically prove that high precision on simple manifolds "does not transfer"; almost all SOTA methods reveal clear failure modes under targeted stress tests.