ICML 2021 accepted papers on Learning theory and algorithms
205 of the 1,184 papers accepted at ICML 2021 (17.3%) are on Learning theory and algorithms, compared with 20.2% at ICML 2020. They fall into 9 topics.
See ICML 2021 in the interactive map
Submitting to ICML? 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 · 42 papers
- Bilinear Classes: A Structural Framework for Provable Generalization in RL (19 citations)
- Learning from Noisy Labels with No Change to the Training Process (8 citations)
- Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning (8 citations)
- Online Unrelated Machine Load Balancing with Predictions Revisited (7 citations)
- Smooth $p$-Wasserstein Distance: Structure, Empirical Approximation, and Statistical Applications (7 citations)
- Besov Function Approximation and Binary Classification on Low-Dimensional Manifolds Using Convolutional Residual Networks (4 citations)
- First-Order Methods for Wasserstein Distributionally Robust MDP (4 citations)
- Near-Optimal Linear Regression under Distribution Shift (4 citations)
- PAC-Learning for Strategic Classification (4 citations)
- Robust Testing and Estimation under Manipulation Attacks (4 citations)
- Concentric mixtures of Mallows models for top-$k$ rankings: sampling and identifiability (3 citations)
- Improving Ultrametrics Embeddings Through Coresets (3 citations)
and 30 more in the interactive map.
Prediction and decision losses · 41 papers
- Model Distillation for Revenue Optimization: Interpretable Personalized Pricing (30 citations)
- On Linear Identifiability of Learned Representations (20 citations)
- Explanations for Monotonic Classifiers. (19 citations)
- Outside the Echo Chamber: Optimizing the Performative Risk (18 citations)
- Don’t Just Blame Over-parametrization for Over-confidence: Theoretical Analysis of Calibration in Binary Classification (16 citations)
- Conservative Objective Models for Effective Offline Model-Based Optimization (14 citations)
- DORO: Distributional and Outlier Robust Optimization (14 citations)
- How Important is the Train-Validation Split in Meta-Learning? (10 citations)
- Understanding and Mitigating Accuracy Disparity in Regression (10 citations)
- On Perceptual Lossy Compression: The Cost of Perceptual Reconstruction and An Optimal Training Framework (9 citations)
- Distribution-Free Calibration Guarantees for Histogram Binning without Sample Splitting (6 citations)
- Machine Unlearning for Random Forests (6 citations)
and 29 more in the interactive map.
Matrix and tensor methods · 31 papers
- A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups (25 citations)
- Dropout: Explicit Forms and Capacity Control (12 citations)
- A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples (7 citations)
- Analysis of stochastic Lanczos quadrature for spectrum approximation (5 citations)
- GBHT: Gradient Boosting Histogram Transform for Density Estimation (4 citations)
- Detection of Signal in the Spiked Rectangular Models (3 citations)
- HoroPCA: Hyperbolic Dimensionality Reduction via Horospherical Projections (3 citations)
- Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering (3 citations)
- Homomorphic Sensing: Sparsity and Noise (2 citations)
- Multiplying Matrices Without Multiplying (2 citations)
- Oblivious Sketching-based Central Path Method for Linear Programming (2 citations)
- Projection techniques to update the truncated SVD of evolving matrices with applications (2 citations)
and 19 more in the interactive map.
Kernels and regression theory · 29 papers
- Provable Meta-Learning of Linear Representations (49 citations)
- On the Inherent Regularization Effects of Noise Injection During Training (14 citations)
- Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning (14 citations)
- Provably Strict Generalisation Benefit for Equivariant Models (10 citations)
- Learning Curves for Analysis of Deep Networks (8 citations)
- Efficient Statistical Tests: A Neural Tangent Kernel Approach (7 citations)
- Tilting the playing field: Dynamical loss functions for machine learning (6 citations)
- Generalization Guarantees for Neural Architecture Search with Train-Validation Split (5 citations)
- A Precise Performance Analysis of Support Vector Regression (4 citations)
- Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models (4 citations)
- Relative Deviation Margin Bounds (3 citations)
- Fast Sketching of Polynomial Kernels of Polynomial Degree (2 citations)
and 17 more in the interactive map.
Submodular and game algorithms · 15 papers
- From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization (16 citations)
- Regularized Submodular Maximization at Scale (15 citations)
- Modelling Behavioural Diversity for Learning in Open-Ended Games (13 citations)
- Randomized Algorithms for Submodular Function Maximization with a $k$-System Constraint (7 citations)
- Follow-the-Regularized-Leader Routes to Chaos in Routing Games (6 citations)
- On Characterizing GAN Convergence Through Proximal Duality Gap (5 citations)
- Connecting Optimal Ex-Ante Collusion in Teams to Extensive-Form Correlation: Faster Algorithms and Positive Complexity Results (4 citations)
- Signatured Deep Fictitious Play for Mean Field Games with Common Noise (4 citations)
- The Power of Adaptivity for Stochastic Submodular Cover (4 citations)
- Network Inference and Influence Maximization from Samples (3 citations)
- A Novel Method to Solve Neural Knapsack Problems (1 citation)
- Instance Specific Approximations for Submodular Maximization (1 citation)
and 3 more in the interactive map.
Clustering · 15 papers
- One Pass Late Fusion Multi-view Clustering (14 citations)
- Near-Optimal Algorithms for Explainable k-Medians and k-Means (12 citations)
- Sharper Generalization Bounds for Clustering (11 citations)
- Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time (10 citations)
- Systematic Analysis of Cluster Similarity Indices: How to Validate Validation Measures (9 citations)
- Approximate Group Fairness for Clustering (4 citations)
- Correlation Clustering in Constant Many Parallel Rounds (3 citations)
- Local Correlation Clustering with Asymmetric Classification Errors (3 citations)
- Hierarchical Clustering of Data Streams: Scalable Algorithms and Approximation Guarantees (1 citation)
- A Scalable Deterministic Global Optimization Algorithm for Clustering Problems
- Feature Clustering for Support Identification in Extreme Regions
- On the price of explainability for some clustering problems
and 3 more in the interactive map.
Combinatorial and search optimization · 12 papers
- CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints (12 citations)
- Optimal Counterfactual Explanations in Tree Ensembles (8 citations)
- Beyond the Pareto Efficient Frontier: Constraint Active Search for Multiobjective Experimental Design (3 citations)
- Decomposable Submodular Function Minimization via Maximum Flow (3 citations)
- Efficient Message Passing for 0–1 ILPs with Binary Decision Diagrams (3 citations)
- An Integer Linear Programming Framework for Mining Constraints from Data (2 citations)
- Fast Algorithms for Stackelberg Prediction Game with Least Squares Loss (1 citation)
- Versatile Verification of Tree Ensembles (1 citation)
- An exact solver for the Weston-Watkins SVM subproblem
- Graph Cuts Always Find a Global Optimum for Potts Models (With a Catch)
- Householder Sketch for Accurate and Accelerated Least-Mean-Squares Solvers
- HyperHyperNetwork for the Design of Antenna Arrays
Optimal transport · 11 papers
- Unbalanced minibatch Optimal Transport; applications to Domain Adaptation (32 citations)
- Scalable Computations of Wasserstein Barycenter via Input Convex Neural Networks (18 citations)
- Outlier-Robust Optimal Transport (14 citations)
- A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance (13 citations)
- Optimal Transport Kernels for Sequential and Parallel Neural Architecture Search (10 citations)
- Projection Robust Wasserstein Barycenters (4 citations)
- Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More (3 citations)
- A Wasserstein Minimax Framework for Mixed Linear Regression
- Learning from Nested Data with Ornstein Auto-Encoders
- Low-Rank Sinkhorn Factorization
- Supervised Tree-Wasserstein Distance
Fairness · 9 papers
- Directional Bias Amplification (22 citations)
- Characterizing Fairness Over the Set of Good Models Under Selective Labels (13 citations)
- Fair Classification with Noisy Protected Attributes: A Framework with Provable Guarantees (8 citations)
- On the Problem of Underranking in Group-Fair Ranking (6 citations)
- Blind Pareto Fairness and Subgroup Robustness (3 citations)
- Collaborative Bayesian Optimization with Fair Regret (3 citations)
- Multi-group Agnostic PAC Learnability (2 citations)
- Testing Group Fairness via Optimal Transport Projections (2 citations)
- Fairness and Bias in Online Selection
