Theory

Learning theory, optimisation theory, generalisation, mathematical analysis of models

91 articles · page 2 of 2

Theory

Polynomial-time algorithms face fundamental limits in online convex optimization with switching experts

Assos et al. study the problem of competing with a comparator that switches among a small set of experts in online convex optimization. They prove that under standard hardness assumptions, polynomial-time algorithms cannot achieve the information-theoretic lower bound of O(k) regret, instead suffering at least (k√d)^{1-o(1)} regret. This establishes a separation between what is possible in principle and what is computationally feasible.

·3 min
Theory

Transformer text generation may never converge, but temperature ensures it

The authors study the asymptotic behavior of autoregressive transformers generating text indefinitely. They show that even a minimal three-token single-layer attention-only transformer can fail to converge. For a rich class of transformers including normalization, MLPs, and RoPE, they prove that above a model-specific softmax temperature, the empirical token distribution converges almost surely to a unique limit, independent of initial prompt. However, there is no universal temperature that forces convergence across all transformers—the required temperature can be arbitrarily high.

·3 min
Theory

Near-linear time random Fourier features with strong concentration guarantees

The authors revisit the Fastfood random feature map for shift-invariant kernels, known to be computable in near-linear time but previously thought to give weak concentration. Using Brascamp-Lieb inequalities and the Schoenberg representation for radial kernels, they prove that Fastfood features yield near-subgaussian concentration for the Gaussian kernel and other radial kernels, closing a long-standing gap between structured and standard random Fourier features.

·3 min
Theory

Reinforcement learning adapts diffusion models to large routing problems

The authors present ResizeCO, a method that uses reinforcement learning to adapt a diffusion model trained on small routing instances to solve large ones. Fine-tuning with GRPO on large TSP and CVRP instances (up to 10,000 nodes) yields solutions that dominate learned solvers on the Pareto front of quality versus runtime. The approach sets a new state of the art for short run times, outperforming both learned and fast non-learned heuristics.

·2 min
Theory

No standard optimizer preserves training equivalence under Transformer reparameterization

Kim shows that rescaling paired weight matrices in Transformers (e.g., query and key) preserves the model's function but changes gradient scales, causing standard optimizers like AdamW to break equivalence after an update. Even transforming optimizer moment estimates does not correct the mismatch under a shared learning rate. The author introduces SAGGS, a periodic rebalancing procedure that restores equivalence and improves perplexity in experiments.

·3 min
Theory

Training spikes in language models replicated by simple quadratic models with heavy-tailed data

The authors introduce Power-Law Random Feature (PLRF) models—simple quadratic models with heavy-tailed, power-law distributed inputs—that exhibit the same intermittent training spikes seen in large language model (LLM) pre-training. They develop a layer-wise simulation algorithm that predicts when spikes will occur in deep neural networks, and in a case study on a Transformer trained with Adam, they derive a beta2 hyperparameter schedule that avoids spikes and improves performance.

·3 min
Theory

Canonical correlations can be recovered from unpaired data alone

The authors present Unpaired CCA (UCCA), the first extension of canonical correlation analysis that learns maximally correlated projections when no paired samples are available. They prove a connection to the Quadratic Assignment Problem, derive a practical algorithm from it, and show on real-world multimodal datasets that UCCA outperforms existing unpaired alignment baselines and approaches the accuracy of paired CCA.

·2 min
Theory

First polynomial parallel-round lower bounds for diffusion sampling with approximate scores.

Yiwen Kou and Yimeng Wang establish the first polynomial lower bounds on the number of sequential rounds required for diffusion sampling when only approximate scores are available. For smooth near-isotropic Gaussian mixtures in d dimensions they prove a Ω̃(d^{1/3}) lower bound, and for anisotropic axis-aligned boxes inside the unit ball they prove a tight Ω(d) lower bound, both holding for arbitrary randomized algorithms with polynomially many queries per round and inverse-polynomial score error.

·3 min
Theory

Optimizer rankings reverse across batch sizes; scaling rules fail

The authors compare Adam, Lion, Muon, SOAP, and Shampoo across batch sizes in language model pretraining, independently tuning each optimizer at every batch size. They find that optimizer rankings reverse: SOAP performs best at small batch sizes, while Shampoo performs best at the largest batch size tested. They also show that for Muon, no theoretically derived hyperparameter scaling rule consistently preserves performance across tasks or batch sizes.

·3 min
Theory

Deterministic algorithm achieves optimal regret for online inverse optimization

The authors provide a deterministic algorithm for online inverse linear optimization that achieves the optimal O(sqrt(d)) regret for any horizon T, and runs in time polynomial in the dimension d and T. This resolves an open question from Sakaue, who obtained the same regret but with a randomized, improper algorithm requiring exponential time per round. The new algorithm is a variant of variable-metric methods with careful metric revocation.

·3 min
Theory

Learned activations reshape spectral tuning in neural fields

The authors introduce learnable spectral activations (LSA), which replace fixed nonlinearities in implicit neural representations (INRs) with a layer-wise truncated Fourier series whose harmonic amplitudes are learned alongside network weights. This decouples feature selection from spectral shaping, concentrating target-signal energy in top eigenmodes of the neural tangent kernel and improving reconstruction across audio, image, and neural field tasks.

·3 min
Theory

Single-pass backpropagation learns Pareto front at cost of standard training

The authors introduce MOSEL, a framework that learns a set of Pareto stationary solutions from a single forward-backward pass. It leverages bilevel optimization and Stackelberg game theory to decouple representation learning from preference alignment. Empirically, MOSEL recovers diverse Pareto frontiers in strongly conflicting tasks and converges closer to the utopia point in weakly conflicting settings, matching the efficiency of single-objective training.

·2 min
Theory

Discrete diffusion model guarantees E(2)-invariant solving for Euclidean optimization

Chen and Han introduce EDISCO, the first discrete diffusion model for Euclidean combinatorial optimization problems (ECOPs) that guarantees exact E(2)-invariance of the generative distribution over solutions. The model consistently outperforms prior learning-based solvers on synthetic TSP and CVRP benchmarks, using fewer training instances, and generalizes better under spatial distribution and constraint shifts.

·2 min
Theory

Flow matching avoids the curse of dimensionality by adapting to intrinsic data dimension

Chakraborty et al. derive finite-sample generalization bounds for flow-matching generative models. They show that the Wasserstein-p distance between the learned and true distribution scales as n^{-1/d} where d is the intrinsic dimension of the data, not the much larger ambient dimension. This result explains why flow matching succeeds on high-dimensional data that lie on low-dimensional manifolds.

·2 min
Theory

Memorization in diffusion models measured by persistence across noise scales

López Amado et al. reinterpret diffusion models as families of deterministic dynamical systems indexed by noise level. They define the critical scale σ_c, the largest noise at which an example remains an attractor of the fixed-scale denoiser, as a measure of memorization. Experiments on CIFAR-10 and Stable Diffusion show σ_c reliably identifies memorization from duplication, overfitting, and outliers, and provides interpretable signals about caption-image interactions and spatial location of memorized content.

·2 min
Theory

Neural network precision floor follows a depth law predicted by amplification

The authors define the precision floor of a neural network as the perturbation level or bit-width at which test accuracy falls halfway from full precision to chance. They show that this floor is given by η_c = Λ / G, where G is the predictive amplification, and that G² grows linearly with depth. Across MLPs, CNNs, Vision Transformers and nine pretrained language models, the depth exponents of the floor and amplification agree within 95% intervals in twelve of thirteen trained architectures. They also report a quantization-aware training (QAT) paradox: noise-aware training roughly doubles tolerable noise in shallow networks, but the gain decays with depth, steepening the depth law.

·3 min
Theory

Principal component regression dominates monotone spectral filters

Kim et al. theoretically compare principal component regression (PCR), gradient descent, ridge regression and a broader family of spectral estimators on individual linear-regression problems. They show that optimally tuned PCR never incurs more than a constant-factor larger risk than any monotone spectral filter under Gaussian designs, while outperforming common non-step filters by polynomial factors on selected instances.

·2 min
Theory

Polylogarithmic Nash regret achieved for any finite matrix game

The authors study Nash regret minimization in unknown finite matrix games with bandit payoff feedback and observed opponent actions. They develop Optimistic Payoff Balancing (OPB), which achieves instance-dependent O(log^2 T) Nash regret against arbitrary adaptive opponents, including games with nonunique equilibria. This resolves the open problem posed by Maiti et al. (2025), extending their polylogarithmic guarantee from 2x2 games to arbitrary finite dimensions.

·2 min
Theory

Unmodified posterior sampling achieves minimax regret in reinforcement learning

Goo and Hong prove that exact vanilla posterior sampling for reinforcement learning (PSRL) is minimax optimal in leading-order Bayesian regret for finite-horizon time-inhomogeneous tabular MDPs with unknown stochastic rewards, achieving the rate Õ(√(SAH³K)). They extend the same proof principle to linear-mixture MDPs, obtaining Õ(d√(H³K)). The key technical advance is a method to decouple the posterior-sampled model from its own continuation value using a common empirical transition reference and a Bellman-based variance argument.

·3 min
Theory

Muon Splits Loss Stability From Update Reversal During LLM Pretraining

Chen and colleagues examine whether the classical edge-of-stability picture for gradient descent also describes language models trained with Muon, an optimizer that replaces matrix gradients with approximately semi-orthogonal directions. Their theory and experiments indicate that Muon separates two behaviors that coincide under gradient descent: short-term loss balance and reversal between successive update directions.

·2 min
Theory

Cyclical monotonicity enforces efficient adversarial transport in robust learning

The authors reformulate distributionally robust optimization (DRO) as a problem over transport maps and prove that optimal maps are cyclically monotone. They show standard adversarial training violates this property, wasting transport cost. They propose multi-start particle ascent and input-convex neural network parametrizations that enforce cyclical monotonicity, achieving improved robustness on regression, image classification, and control tasks.

·3 min
Theory

Frozen agent states can retain causal mechanisms beyond task performance

Zhang et al. define causal retention: whether a frozen learned state can answer mechanism-probe queries (action, context, target, value, delay) independent of training. They prove a Bayes optimal error bound and introduce Causal Core, a method achieving perfect recall under local edits while accepting only 5.6% of readout candidates in a language model and recovering effect-sign accuracy from 0.057 to 0.948 in TD-MPC2 without degrading stable responses.

·3 min