NeurIPS 2021 accepted papers on Learning theory and algorithms
367 of the 2,508 papers accepted at NeurIPS 2021 (14.6%) are on Learning theory and algorithms, compared with 19.1% at NeurIPS 2020. They fall into 9 topics.
See NeurIPS 2021 in the interactive map
Submitting to NeurIPS? Checklist →
Working on something in this area? Describe your idea in scime atlas to see the closest papers by meaning and how crowded the spot has become.
Topics and papers
Sample complexity · 88 papers
- Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space (23 citations)
- Distributed Saddle-Point Problems Under Data Similarity (14 citations)
- An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks (9 citations)
- Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning) (9 citations)
- Coresets for Classification – Simplified and Strengthened (9 citations)
- Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces (9 citations)
- Towards a Unified Information-Theoretic Framework for Generalization (9 citations)
- Nonuniform Negative Sampling and Log Odds Correction with Rare Events Data (8 citations)
- Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize (8 citations)
- On the Representation of Solutions to Elliptic PDEs in Barron Spaces (7 citations)
- A Theory of the Distortion-Perception Tradeoff in Wasserstein Space (6 citations)
- Concentration inequalities under sub-Gaussian and sub-exponential conditions (6 citations)
and 76 more in the interactive map.
Prediction and decision losses · 77 papers
- Contemporary Symbolic Regression Methods and their Relative Performance (143 citations)
- Neural Additive Models: Interpretable Machine Learning with Neural Nets (121 citations)
- Batch Active Learning at Scale (46 citations)
- Adaptive Machine Unlearning (43 citations)
- Towards Robust and Reliable Algorithmic Recourse (38 citations)
- Shapley Residuals: Quantifying the limits of the Shapley value for explanations (35 citations)
- Good Classification Measures and How to Find Them (32 citations)
- Universal Rate-Distortion-Perception Representations for Lossy Compression (22 citations)
- Meta-Adaptive Nonlinear Control: Theory and Algorithms (19 citations)
- Validation Free and Replication Robust Volume-based Data Valuation (19 citations)
- What’s a good imputation to predict with missing values? (19 citations)
- Synthetic Benchmarks for Scientific Research in Explainable Machine Learning (17 citations)
and 65 more in the interactive map.
Kernels and regression theory · 57 papers
- A Universal Law of Robustness via Isoperimetry (75 citations)
- The Inductive Bias of Quantum Kernels (44 citations)
- Tighter Expected Generalization Error Bounds via Wasserstein Distance (24 citations)
- Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime (18 citations)
- Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks (16 citations)
- An Exact Characterization of the Generalization Error for the Gibbs Algorithm (14 citations)
- Generalization Bounds For Meta-Learning: An Information-Theoretic Analysis (14 citations)
- Information-theoretic generalization bounds for black-box learning algorithms (14 citations)
- What can linearized neural networks actually say about generalization? (14 citations)
- Locality defeats the curse of dimensionality in convolutional teacher-student scenarios (13 citations)
- Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation (12 citations)
- Overparameterization Improves Robustness to Covariate Shift in High Dimensions (12 citations)
and 45 more in the interactive map.
Matrix and tensor methods · 49 papers
- Scalars are universal: Equivariant machine learning, structured like classical physics (30 citations)
- Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection (19 citations)
- PCA Initialization for Approximate Message Passing in Rotationally Invariant Models (13 citations)
- Iteratively Reweighted Least Squares for Basis Pursuit with Global Linear Convergence Rate (12 citations)
- Fast and accurate randomized algorithms for low-rank tensor decompositions (9 citations)
- Unlabeled Principal Component Analysis (8 citations)
- Robust Regression Revisited: Acceleration and Improved Estimation Rates (7 citations)
- Hessian Eigenspectra of More Realistic Nonlinear Models (6 citations)
- General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds (5 citations)
- Recovery Analysis for Plug-and-Play Priors using the Restricted Eigenvalue Condition (5 citations)
- Unique sparse decomposition of low rank matrices (5 citations)
- An Online Riemannian PCA for Stochastic Canonical Correlation Analysis (4 citations)
and 37 more in the interactive map.
Combinatorial and search optimization · 25 papers
- Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification (94 citations)
- Learning Hard Optimization Problems: A Data Generation Perspective (21 citations)
- Matrix encoding networks for neural combinatorial optimization (16 citations)
- Symbolic Regression via Deep Reinforcement Learning Enhanced Genetic Programming Seeding (15 citations)
- Partition-Based Formulations for Mixed-Integer Optimization of Trained ReLU Neural Networks (13 citations)
- Training Neural Networks is ER-complete (10 citations)
- Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond (7 citations)
- Hyperparameter Optimization Is Deceiving Us, and How to Stop It (5 citations)
- Synthetic Design: An Optimization Approach to Experimental Design with Synthetic Controls (5 citations)
- Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares (4 citations)
- Learning Optimal Predictive Checklists (3 citations)
- Learning to delegate for large-scale vehicle routing (2 citations)
and 13 more in the interactive map.
Submodular and game algorithms · 25 papers
- Proportional Participatory Budgeting with Additive Utilities (23 citations)
- Minimizing Polarization and Disagreement in Social Networks via Link Recommendation (17 citations)
- Optimality and Stability in Federated Learning: A Game-theoretic Approach (14 citations)
- Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization (10 citations)
- Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach (10 citations)
- PreferenceNet: Encoding Human Preferences in Auction Design with Deep Learning (8 citations)
- Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel (6 citations)
- Learning in Multi-Stage Decentralized Matching Markets (4 citations)
- Constrained Robust Submodular Partitioning (3 citations)
- Differentiable Equilibrium Computation with Decision Diagrams for Stackelberg Models of Combinatorial Congestion Games (3 citations)
- The Semi-Random Satisfaction of Voting Axioms (3 citations)
- Learning to Select Exogenous Events for Marked Temporal Point Process (2 citations)
and 13 more in the interactive map.
Clustering · 21 papers
- Refined Learning Bounds for Kernel and Approximate $k$-Means (7 citations)
- Nearly-Tight and Oblivious Algorithms for Explainable Clustering (6 citations)
- Better Algorithms for Individually Fair $k$-Clustering (5 citations)
- Coresets for Clustering with Missing Values (2 citations)
- Local Hyper-Flow Diffusion (2 citations)
- Parallel and Efficient Hierarchical k-Median Clustering (2 citations)
- Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems (2 citations)
- Robust Online Correlation Clustering (2 citations)
- Uniform Concentration Bounds toward a Unified Framework for Robust Clustering (2 citations)
- Fair Clustering Under a Bounded Cost (1 citation)
- Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem (1 citation)
- Fuzzy Clustering with Similarity Queries (1 citation)
and 9 more in the interactive map.
Fairness · 16 papers
- It's COMPASlicated: The Messy Relationship between RAI Datasets and Algorithmic Fairness Benchmarks (31 citations)
- Are My Deep Learning Systems Fair? An Empirical Study of Fixed-Seed Training (20 citations)
- Assessing Fairness in the Presence of Missing Data (11 citations)
- Fair Sortition Made Transparent (11 citations)
- Benchmarking Bias Mitigation Algorithms in Representation Learning through Fairness Metrics (10 citations)
- Fair Sequential Selection Using Supervised Learning Models (6 citations)
- Unintended Selection: Persistent Qualification Rate Disparities and Interventions (5 citations)
- An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning (4 citations)
- Scalable and Stable Surrogates for Flexible Classifiers with Fairness Constraints (4 citations)
- Post-processing for Individual Fairness (3 citations)
- Retiring Adult: New Datasets for Fair Machine Learning (3 citations)
- Fair Scheduling for Time-dependent Resources (2 citations)
and 4 more in the interactive map.
Optimal transport · 9 papers
- The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation (40 citations)
- Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projections (27 citations)
- Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark (10 citations)
- Measuring Generalization with Optimal Transport (5 citations)
- Score-based Generative Neural Networks for Large-Scale Optimal Transport (5 citations)
- Fast Approximation of the Sliced-Wasserstein Distance Using Concentration of Random Projections (4 citations)
- On Robust Optimal Transport: Computational Complexity and Barycenter Computation (4 citations)
- Unbalanced Optimal Transport through Non-negative Penalized Linear Regression (4 citations)
- A novel notion of barycenter for probability distributions based on optimal weak mass transport (1 citation)
