ICLR 2025 accepted papers on Learning theory and algorithms

Prediction and decision losses · 45 papers

• Imputation for prediction: beware of diminishing returns. (3 citations)
• Provably Accurate Shapley Value Estimation via Leverage Score Sampling (3 citations)
• A Generic Framework for Conformal Fairness (1 citation)
• Boosting Methods for Interval-censored Data with Regression and Classification (1 citation)
• Conformal Prediction Sets Can Cause Disparate Impact (1 citation)
• Conformal Structured Prediction (1 citation)
• Data Shapley in One Training Run (1 citation)
• Leave-One-Out Stable Conformal Prediction (1 citation)
• On the Relation between Trainability and Dequantization of Variational Quantum Learning Models (1 citation)
• A Deep Generative Learning Approach for Two-stage Adaptive Robust Optimization
• A Differentiable Rank-Based Objective for Better Feature Learning
• Binary Losses for Density Ratio Estimation

and 33 more in the interactive map.

Combinatorial and search optimization · 27 papers

• Towards Foundation Models for Mixed Integer Linear Programming (3 citations)
• Approximation algorithms for combinatorial optimization with predictions (1 citation)
• Learning-Augmented Search Data Structures (1 citation)
• Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling (1 citation)
• PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization (1 citation)
• System 1.x: Learning to Balance Fast and Slow Planning with Language Models (1 citation)
• Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming
• Deep Distributed Optimization for Large-Scale Quadratic Programming
• Few for Many: Tchebycheff Set Scalarization for Many-Objective Optimization
• Many-Objective Multi-Solution Transport
• Pareto Low-Rank Adapters: Efficient Multi-Task Learning with Preferences
• ParetoFlow: Guided Flows in Multi-Objective Optimization

and 15 more in the interactive map.

Sample complexity · 23 papers

• Generalization Bounds and Model Complexity for Kolmogorov–Arnold Networks (2 citations)
• Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
• Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model
• Computational Explorations of Total Variation Distance
• Decomposition Polyhedra of Piecewise Linear Functions
• Efficient and Accurate Explanation Estimation with Distribution Compression
• Estimating the Probabilities of Rare Outputs in Language Models
• Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel
• Global Well-posedness and Convergence Analysis of Score-based Generative Models via Sharp Lipschitz Estimates
• How Much is Unseen Depends Chiefly on Information About the Seen
• How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions
• Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics

and 11 more in the interactive map.

Kernels and regression theory · 21 papers

• How Feature Learning Can Improve Neural Scaling Laws (2 citations)
• How many samples are needed to train a deep neural network? (1 citation)
• Extending Mercer's expansion to indefinite and asymmetric kernels
• Fast Summation of Radial Kernels via QMC Slicing
• Generalization and Distributed Learning of GFlowNets
• Generalization in VAE and Diffusion Models: A Unified Information-Theoretic Analysis
• How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning
• Leveraging Flatness to Improve Information-Theoretic Generalization Bounds for SGD
• Optimal Learning of Kernel Logistic Regression for Complex Classification Scenarios
• Optimality and Adaptivity of Deep Neural Features for Instrumental Variable Regression
• Prediction Risk and Estimation Risk of the Ridgeless Least Squares Estimator under General Assumptions on Regression Errors
• The Breakdown of Gaussian Universality in Classification of High-dimensional Linear Factor Mixtures

and 9 more in the interactive map.

Optimal transport · 19 papers

• Learning stochastic dynamics from snapshots through regularized unbalanced optimal transport (3 citations)
• SAVA: Scalable Learning-Agnostic Data Valuation (2 citations)
• Comparing noisy neural population dynamics using optimal transport distances (1 citation)
• A Truncated Newton Method for Optimal Transport
• Distance-Based Tree-Sliced Wasserstein Distance
• Expected Sliced Transport Plans
• Fast unsupervised ground metric learning with tree-Wasserstein distance
• Feedback Schrödinger Bridge Matching
• Fourier Sliced-Wasserstein Embedding for Multisets and Measures
• Improving Neural Optimal Transport via Displacement Interpolation
• Learning Structured Representations by Embedding Class Hierarchy with Fast Optimal Transport
• Linear Partial Gromov-Wasserstein Embedding

and 7 more in the interactive map.

Matrix and tensor methods · 13 papers

• Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation (1 citation)
• Matrix Product Sketching via Coordinated Sampling (1 citation)
• Singular Subspace Perturbation Bounds via Rectangular Random Matrix Diffusions (1 citation)
• Understanding Matrix Function Normalizations in Covariance Pooling through the Lens of Riemannian Geometry (1 citation)
• A New Perspective on Shampoo's Preconditioner
• Efficient Sparse PCA via Block-Diagonalization
• Faster Algorithms for Structured Linear and Kernel Support Vector Machines
• Fitting Networks with a Cancellation Trick
• Global Identifiability of Overcomplete Dictionary Learning via L1 and Volume Minimization
• Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
• Neural networks on Symmetric Spaces of Noncompact Type
• Probabilistic Geometric Principal Component Analysis with application to neural data

and 1 more in the interactive map.

Clustering · 12 papers

• Breaking the Reclustering Barrier in Centroid-based Deep Clustering
• Exact Community Recovery under Side Information: Optimality of Spectral Algorithms
• FairDen: Fair Density-Based Clustering
• Quantum (Inspired) $D^2$-sampling with Applications
• Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems
• COPER: Correlation-based Permutations for Multi-View Clustering
• Coreset Spectral Clustering
• DLEFT-MKC: Dynamic Late Fusion Multiple Kernel Clustering with Robust Tensor Learning via Min-Max Optimization
• Fair Clustering in the Sliding Window Model
• New Algorithms for the Learning-Augmented k-means Problem
• Online Clustering with Nearly Optimal Consistency
• Simple yet Effective Incomplete Multi-view Clustering: Similarity-level Imputation and Intra-view Hybrid-group Prototype Construction

Fairness · 8 papers

• First-Person Fairness in Chatbots (3 citations)
• Rethinking Fair Representation Learning for Performance-Sensitive Tasks (1 citation)
• A Causal Lens for Learning Long-term Fair Policies
• Bridging Jensen Gap for Max-Min Group Fairness Optimization in Recommendation
• Fair Submodular Cover
• No Location Left Behind: Measuring and Improving the Fairness of Implicit Representations for Earth Data
• Towards counterfactual fairness through auxiliary variables
• Balancing Bias in Two-sided Markets for Fair Stable Matchings

Submodular and game algorithms · 7 papers

• Can Reinforcement Learning Solve Asymmetric Combinatorial-Continuous Zero-Sum Games?
• The Complexity of Two-Team Polymatrix Games with Independent Adversaries
• Difference-of-submodular Bregman Divergence
• Divergence-Regularized Discounted Aggregation: Equilibrium Finding in Multiplayer Partially Observable Stochastic Games
• Efficient Online Pruning and Abstraction for Imperfect Information Extensive-Form Games
• Improved Approximation Algorithms for $k$-Submodular Maximization via Multilinear Extension
• Rethinking Shapley Value for Negative Interactions in Non-convex Games