NeurIPS 2025 accepted papers on Learning theory and algorithms
405 of the 5,812 papers accepted at NeurIPS 2025 (7.0%) are on Learning theory and algorithms, compared with 8.8% at NeurIPS 2024. They fall into 9 topics.
See NeurIPS 2025 in the interactive map
Working on something in this area? Describe your idea in scime atlas to see the closest accepted papers by meaning and how crowded the spot has become.
Topics and papers
Prediction and decision losses · 102 papers
- SHAP values via sparse Fourier representation (2 citations)
- What Does It Take to Build a Performant Selective Classifier? (2 citations)
- Why Popular MOEAs are Popular: Proven Advantages in Approximating the Pareto Front (2 citations)
- A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding (1 citation)
- A Reliable Cryptographic Framework for Empirical Machine Unlearning Evaluation (1 citation)
- Beyond Prediction: Managing the Repercussions of Machine Learning Applications (1 citation)
- Distributionally Robust Performative Optimization (1 citation)
- ElliCE: Efficient and Provably Robust Algorithmic Recourse via the Rashomon Sets (1 citation)
- Maximizing the Value of Predictions in Control: Accuracy Is Not Enough (1 citation)
- Neural Rule Lists: Learning Discretizations, Rules, and Order in One Go (1 citation)
- Quantifying Uncertainty in Error Consistency: Towards Reliable Behavioral Comparison of Classifiers (1 citation)
- Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values (1 citation)
and 90 more in the interactive map.
Sample complexity · 89 papers
- In-context Learning of Linear Dynamical Systems with Transformers: Approximation Bounds and Depth-separation (1 citation)
- Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means (1 citation)
- A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation
- A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging
- A Geometric Analysis of PCA
- Absorb and Converge: Provable Convergence Guarantee for Absorbing Discrete Diffusion Models
- Agnostic Active Learning Is Always Better Than Passive Learning
- Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness
- Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models
- An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
- Approximation and Generalization Abilities of Score-based Neural Network Generative Models for Sub-Gaussian Distributions
- Approximation theory for 1-Lipschitz ResNets
and 77 more in the interactive map.
Kernels and regression theory · 48 papers
- Subsampled Ensemble Can Improve Generalization Tail Exponentially (2 citations)
- Learning Linear Attention in Polynomial Time (1 citation)
- Neural Collapse in Cumulative Link Models for Ordinal Regression: An Analysis with Unconstrained Feature Model (1 citation)
- Regularized least squares learning with heavy-tailed noise is minimax optimal (1 citation)
- Thumb on the Scale: Optimal Loss Weighting in Last Layer Retraining (1 citation)
- Adaptive Data Analysis for Growing Data
- Algorithm- and Data-Dependent Generalization Bounds for Diffusion Models
- Anchor-based Maximum Discrepancy for Relative Similarity Testing
- Are Greedy Task Orderings Better Than Random in Continual Linear Regression?
- Bayes optimal learning of attention-indexed models
- Beyond Benign Overfitting in Nadaraya-Watson Interpolators
- Beyond Least Squares: Uniform Approximation and the Hidden Cost of Misspecification
and 36 more in the interactive map.
Combinatorial and search optimization · 38 papers
- Differentiation Through Black-Box Quadratic Programming Solvers (1 citation)
- Enforcing Hard Linear Constraints in Deep Learning Models with Decision Rules (1 citation)
- Fast Computation and Optimization for Opinion-Based Quantities of Friedkin-Johnsen Model (1 citation)
- Neural Combinatorial Optimization for Time Dependent Traveling Salesman Problem (1 citation)
- Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computation (1 citation)
- Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees (1 citation)
- A learnability analysis on neuro-symbolic learning
- A Learning-Augmented Dynamic Programming Approach for Orienteering Problem with Time Windows
- A machine learning approach that beats Rubik's cubes
- A Partition Cover Approach to Tokenization
- An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks
- BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks
and 26 more in the interactive map.
Submodular and game algorithms · 34 papers
- Scaling Laws For Scalable Oversight (3 citations)
- Collective Bargaining in the Information Economy Can Address AI-Driven Power Concentration (2 citations)
- Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems (1 citation)
- \(\varepsilon\)-Optimally Solving Two-Player Zero-Sum POSGs
- A Learning-Augmented Approach to Online Allocation Problems
- A Unified Approach to Submodular Maximization Under Noise
- Beyond Last-Click: An Optimal Mechanism for Ad Attribution
- Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies
- Does Representation Guarantee Welfare?
- Efficient Kernelized Learning in Polyhedral Games beyond Full Information: From Colonel Blotto to Congestion Games
- Evolutionary Prediction Games
- GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
and 22 more in the interactive map.
Matrix and tensor methods · 34 papers
- Learning Cocoercive Conservative Denoisers via Helmholtz Decomposition for Poisson Imaging Inverse Problems (1 citation)
- PoLAR: Polar-Decomposed Low-Rank Adapter Representation (1 citation)
- Purifying Shampoo: Investigating Shampoo's Heuristics by Decomposing its Preconditioner (1 citation)
- STNet: Spectral Transformation Network for Solving Operator Eigenvalue Problem (1 citation)
- Bivariate Matrix-valued Linear Regression (BMLR): Finite-sample performance under Identifiability and Sparsity Assumptions
- Efficient $k$-Sparse Band–Limited Interpolation with Improved Approximation Ratio
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach
- Faster Algorithms for Structured John Ellipsoid Computation
- Foundations of Top-$k$ Decoding for Language Models
- Gaussian Regression-Driven Tensorized Incomplete Multi-View Clustering with Dual Manifold Regularization
- Guarantees for Alternating Least Squares in Overparameterized Tensor Decompositions
- Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry
and 22 more in the interactive map.
Clustering · 24 papers
- Clustering via Hedonic Games: New Concepts and Algorithms (2 citations)
- Accelerating data-driven algorithm selection for combinatorial partitioning problems (1 citation)
- Hypergraph-Enhanced Contrastive Learning for Multi-View Clustering with Hyper-Laplacian Regularization (1 citation)
- Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering (1 citation)
- A Beyond-Worst-Case Analysis of Greedy k-means++
- A Single-Swap Local Search Algorithm for k-Means of Lines
- AF-UMC: An Alignment-Free Fusion Framework for Unaligned Multi-View Clustering
- Bit-swapping Oriented Twin-memory Multi-view Clustering in Lifelong Incomplete Scenarios
- Dynamic Algorithm for Explainable $k$-medians Clustering under $\ell_p$ Norm
- Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
- Fast Local Search Algorithms for Clustering with Adaptive Sampling and Bandit Strategies
- Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach
and 12 more in the interactive map.
Fairness · 22 papers
- Efficient Fairness-Performance Pareto Front Computation (1 citation)
- Fairness under Competition (1 citation)
- Secure and Confidential Certificates of Online Fairness (1 citation)
- Selective Omniprediction and Fair Abstention (1 citation)
- Size-adaptive Hypothesis Testing for Fairness (1 citation)
- Audits Under Resource, Data, and Access Constraints: Scaling Laws For Less Discriminatory Alternatives
- Fair Continuous Resource Allocation with Equality of Impact
- Fair Matroid Selection
- Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity
- Fair Representation Learning with Controllable High Confidence Guarantees via Adversarial Inference
- Fairness-aware Bayes Optimal Functional Classification
- Improved Algorithms for Fair Matroid Submodular Maximization
and 10 more in the interactive map.
Optimal transport · 14 papers
- Bootstrap Your Uncertainty: Adaptive Robust Classification Driven by Optimal-Transport
- Differentiable Generalized Sliced Wasserstein Plans
- Distances for Markov chains from sample streams
- Efficient Algorithms for Robust and Partial Semi-Discrete Optimal Transport
- Estimation of Stochastic Optimal Transport Maps
- Exponential Convergence Guarantees for Iterative Markovian Fitting
- Sample and Map from a Single Convex Potential: Generation using Conjugate Moment Measures
- Schrödinger Bridge Matching for Tree-Structured Costs and Entropic Wasserstein Barycentres
- Solving Discrete (Semi) Unbalanced Optimal Transport with Equivalent Transformation Mechanism and KKT-Multiplier Regularization
- Stability and Oracle Inequalities for Optimal Transport Maps between General Distributions
- Tree-Sliced Entropy Partial Transport
- Unbalanced Optimal Total Variation Transport: A Theoretical Approach to Spatial Resource Allocation Problems
and 2 more in the interactive map.