Annealed Langevin dynamics reach the tensor PCA algorithmic threshold
Part II says spherical Langevin dynamics with annealing and averaging strongly recover from a random start.
Stories per day · 30 days
Relatedlanguage-models2markov-chains2algorithmic-threshold1asi1attention1communication-architecture1cs-cr1deep-learning1differential-privacy1expressivity1langevin-dynamics1learning-dynamics1neural-networks1noise1prompt-memory1recurrent-neural-networks1relu1representation-learning1
29 stories, newest first · one card per story
Stories tagged #theory
Theory: noise can shape what linear RNNs learn
In the rich regime, high noise can make a non-degenerate solution suboptimal when parameter scales are limited.
Paper outlines a five-level communication architecture for language-based ASI
The proposal separates systemic activity representations, situation schemas, narrative, full sense and text, arguing context alone cannot expose utterance foundations.
Any ReLU network can be exactly simulated with two hidden layers
The authors give a homological-algebra proof using fillings and a separate direct combinatorial proof.
Transformers forget prompts as generated context grows
Hidden-state distance between two prompts decays as a power law; trained models forget faster than untrained ones.
Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy
Researchers give near-optimal private bounds for learning Markov chain transition matrices.
KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling
Theory paper separates two KL measures for parallel sampling, with very different round costs.
Hitting-Time Bounds for Asynchronous Q-Learning
Asynchronous Q-learning reaches epsilon error with a quartic horizon term plus an additive hitting-time cost.
Finite-Sample Guarantees for Fully Discrete Conditional Diffusion Models
Paper proves finite-sample error bounds for conditional diffusion models using finite denoising steps.
Expected Sample Complexity in Multi-Armed Bandits
A new expected sample-complexity measure for stochastic bandits separates known and unknown suboptimality and rules out deterministic algorithms.
Optimal and Efficient Online Inverse Optimization
A deterministic polynomial-time algorithm achieves optimal O(sqrt d) regret for online inverse linear optimization.
On the Convergence of Success Conditioning for Policy Optimization
Paper proves success conditioning converges to optimal policies on broad MDP classes, with O(1/ε^p) iterations for discounted MDPs and O(log(1/ε)) for single-period settings.
Dynamics to decision: A mathematical theory of Lyapunov spectra and decision boundaries in deep classifiers
Paper ties finite-time Lyapunov exponents of deep classifiers to decision-boundary geometry.
Breakdown of Local Denoising as Semantic Speciation
Theory shows semantic correlations place generative models' nonlocality window inside the speciation window.
Achieving an $O(1/N)$ Optimality Gap in Average-Reward Weakly-Coupled MDPs
A new non-priority policy achieves an O(1/N) optimality gap for average-reward weakly-coupled MDPs.
Minimal-Norm Univariate Two-Layer ReLU Classification: Exact Solutions and Global Optimality with Skip Connections
Researchers characterize minimal-norm univariate two-layer ReLU classifiers and show skip connections make every KKT point globally optimal.
Minimax-Optimal Online Contract Design with Unrestricted Bounded Contracts
The paper proves minimax-optimal regret of order T^(m/(m+1)) for repeated online contract design with unrestricted bounded contracts and arbitrary agent action spaces.
Reachability, Not Observation: Containing Systems Whose Wiring Changes
Theoretical study shows snapshot-based containment vastly underestimates required blocks when wiring changes, proposing reachability-based declared capability maps instead.
Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging
Researchers prove off-policy evaluation under history-dependent logging requires exponentially many episodes, resolving a hardness question for model-based POMDP evaluation.
Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult
Lower bounds show heterogeneous asynchronous optimization cannot match homogeneous rates under standard similarity assumptions; strong interpolation plus local PL condition closes the gap.
Recurrent GraphNeural NetworkswithSet-BasedAggregation
Paper proves two-directional equivalence between recurrent GNNs with set-based aggregation and Boolean closure of reachability/safety properties in modal mu-calculus, checkable from weights.
Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start
Thin-shell stability proof along the Gaussian cooling path improves cold-start logconcave sampling complexity to near n^2.5 from n^2.75.
Generalized Agent Iteration: One Formal Framework for Iterative Policy Improvement and Recursive Self-Improvement
Generalized Agent Iteration formally unifies iterative policy improvement and recursive self-improvement, defining axes that distinguish anchored, goal-drifting, and self-referential agents.
On the Regularization Landscape for the Linear Recommendation Models
Study shows leading linear recommendation models reduce to nuclear-norm or Frobenius-norm regularization, with two new closed-form low-rank solutions proposed.