Theory

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

8 articles

All Agents Language models Reinforcement learning Vision Generative media Speech & audio Robotics & embodied AI Safety & security Evaluation & benchmarks Efficiency & systems Code & software AI for science & health Theory

Viewgrid list compact

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.

3 Oct·2 min

Theory

Finite probe sets identify neural networks, but hidden activations make them far more informative

Sarangi et al. study when finite probe evaluations of a neural network suffice for learning neural functionals. They prove identification and universality results, show hidden-layer probes are strictly more informative than final-output probes, and introduce HiddenProbe, which achieves state-of-the-art performance on MLP and Transformer benchmarks.

3 Oct·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 Oct·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.

3 Oct·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 Oct·3 min

Theory

LLMs generate generalized plans with machine-checked completeness proofs

Stein et al. convert planning domains from PDDL into Lean, then use GPT-5.6-Sol to generate both a generalized plan and a formal proof of its completeness. Lean's kernel accepted proofs for 12 of 13 benchmark domains, replacing finite test coverage or manual inspection with machine-checked guarantees relative to the formal specification.

30 Sept·2 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.

29 Sept·3 min

Theory

Shared output errors can saturate networks trained with random feedback

Reddy, Sabatini and Safaai analyze why direct feedback alignment, which trains hidden layers using fixed random projections of output errors, can stall near constant-predictor performance. They show that an error component shared across inputs pushes tanh units toward saturation, while calibrating the readout or subtracting the batch-mean teaching signal can suppress the collapse and accelerate learning.

29 Sept·2 min