yusuke1997/dblp-id-title huggingface dataset:
A Blackbox Approach to Best of Both Worlds in Bandits and Beyond
Most Correlated Arms Identification
Assemblies of neurons learn to classify well-separated distributions
Oracle-Efficient Hybrid Online Learning with Unknown Distribution
Online Convex Optimization with a Separation Oracle
Parameter-Free Online Convex Optimization with Sub-Exponential Noise
On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis
Query complexity of least absolute deviation regression via robust uniform convergence
Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods
An Optimal High-Order Tensor Method for Convex Optimization
Online Learning with Feedback Graphs: Beyond Bandits
Distance-Based Classification with Lipschitz Functions
Optimizing Average Reward Using Discounted Rewards
Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
New Lower Bounds for Statistical Query Learning
Learning Unions of Two Rectangles in the Plane with Equivalence Queries
Causal Markov Condition for Submodular Information Measures
The Complexity of Making the Gradient Small in Stochastic Convex Optimization
Open Problem: Data Selection for Regression Tasks
Estimating stationary mass, frequency by frequency
Local Regularizers Are Not Transductive Learners
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, COLT 1994, New Brunswick, NJ, USA, July 12-15, 1994
Approximating a Gram Matrix for Improved Kernel-Based Learning
Accelerating Proximal Gradient Descent via Silver Stepsizes
Inductive Bias of Multi-Channel Linear Convolutional Networks with Bounded Weight Norm
Learning Probabilistically Consistent Linear Threshold Functions
PAC-Like Upper Bounds for the Sample Complexity of Leave-one-Out Cross-Validation
On Polynomial-Time Probably almost Discriminative Learnability
The price of bandit information in multiclass online classification
The Representation of Recursive Languages and Its Impact on the Efficiency of Learning
Learning Convex Combinations of Continuously Parameterized Basic Kernels
Semi-Random Sparse Recovery in Nearly-Linear Time
Prudence in Language Learning
Inapproximability of VC Dimension and Littlestone's Dimension
Synthesizing Enumeration Techniques for Language Learning
Label noise (stochastic) gradient descent implicitly solves the Lasso for quadratic parametrisation
Approximation and Estimation Bounds for Artificial Neural Networks
Is Efficient PAC Learning Possible with an Oracle That Responds "Yes" or "No"?
Learning to Create is as Hard as Learning to Appreciate
Beyond Catoni: Sharper Rates for Heavy-Tailed and Robust Mean Estimation
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
Distributed Signal Detection under Communication Constraints
Law of Large Numbers for Bayesian two-layer Neural Network trained with Variational Inference
Algorithmically Effective Differentially Private Synthetic Data
Improved Lower Bounds for Learning from Noisy Examples: An Information-Theoretic Approach
On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective
Exact tensor completion with sum-of-squares
Replacing Limit Learners with Equally Powerful One-Shot Query Learners
Errors are Robustly Tamed in Cumulative Knowledge Processes
Regret Bounds for Hierarchical Classification with Linear-Threshold Functions
Sparseness Versus Estimating Conditional Probabilities: Some Asymptotic Results
Optimal Online Bookmaking for Any Number of Outcomes
Omnipredictors for regression and the approximate rank of convex functions
Learning Binary Relations Using Weighted Majority Voting
Robust random graph matching in Gaussian models via vector approximate message passing
COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA
Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games
Testing Juntas and Junta Subclasses with Relative Error
Regret Bounds for Prediction Problems
Polynomial Learnability of Probabilistic Concepts with Respect to the Kullback-Leibler Divergence
The role of randomness in quantum state certification with unentangled measurements
A Randomized Online Learning Algorithm for Better Variance Control
Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information
Barrier Boosting
Induction from the General to the More General
On the Equivalence of Weak Learnability and Linear Separability: New Relaxations and Efficient Boosting Algorithms
Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions
Proceedings of the Second Annual Workshop on Computational Learning Theory, COLT 1989, Santa Cruz, CA, USA, July 31 - August 2, 1989
Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing
Convex Risk Minimization and Conditional Probability Estimation
Can Q-learning be Improved with Advice?
The "lob-pass" Problem and an On-line Learning Model of Rational Choice
Kernelizing Sorting, Permutation, and Alignment for Minimum Volume PCA
Identifiability and Estimation in High-Dimensional Nonparametric Latent Structure Models
Minimax Bounds on Stochastic Batched Convex Optimization
Inferring Answers to Queries
Learning to Model Sequences Generated by Switching Distributions
Learning Monotonic Linear Functions
Additive Models, Boosting, and Inference for Generalized Divergences
Multi-scale exploration of convex functions and bandit convex optimization
Private High-Dimensional Hypothesis Testing
Domain Adaptation: Learning Bounds and Algorithms
Stochastic Block Model and Community Detection in Sparse Graphs: A spectral algorithm with optimal rate of recovery
Reconstructing the Geometry of Random Geometric Graphs (Extended Abstract)
Contextual Dueling Bandits
Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier
Universal Rates of ERM for Agnostic Learning
Maximum Margin Algorithms with Boolean Kernels
Non-Gaussian Component Analysis via Lattice Basis Reduction
A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret
Estimating the Mixing Time of Ergodic Markov Chains
Quantum Channel Certification with Incoherent Measurements
Learning Functions of k Terms
Approximating the total variation distance between spin systems
Metalearning with Very Few Samples Per Task
Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Sampling
Open Problem: Monotonicity of Learning
Learning Decision Trees from Random Examples
Online learning over a finite action set with limited switching
Near-Optimal Entrywise Sampling of Numerically Sparse Matrices
Inductive Inference of Minimal Programs
Leveraging for Regression
First-order Methods for Geodesically Convex Optimization
A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions
A Comparison of New and Old Algorithms for a Mixture Estimation Problem
Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
Adaptivity in Adaptive Submodularity
Statistical Queries and Faulty PAC Oracles
Stability and List-Replicability for Agnostic Learners
Wasserstein GANs with Gradient Penalty Compute Congested Transport
The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication
The VC-Dimension vs. the Statistical Capacity for Two Layer Networks with Binary Weights
Multiple-output composite quantile regression through an optimal transport lens
Does Unlabeled Data Provably Help? Worst-case Analysis of the Sample Complexity of Semi-Supervised Learning
Black-Box k-to-1-PCA Reductions: Theory and Applications
The K-armed Dueling Bandits Problem
On the Impact of Forgetting on Learning Machines
Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm
Source Identification for Mixtures of Product Distributions
Identification of Unions of Languages Drawn from an Identifiable Class
Generalisation Error Bounds for Sparse Linear Classifiers
Correspondence retrieval
Escaping the Curse of Dimensionality with a Tree-based Regressor
Information-Directed Selection for Top-Two Algorithms
On the Approximation Power of Two-Layer Networks of Random ReLUs
Testing Mixtures of Discrete Distributions
The Catch-Up Phenomenon in Bayesian Inference
Universal Approximation with Deep Narrow Networks
Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models
Reliably Learning the ReLU in Polynomial Time
Lower Bounds on the Vapnik-Chervonenkis Dimension of Multi-Layer Threshold Networks
Adaptivity to Noise Parameters in Nonparametric Active Learning
Better Private Algorithms for Correlation Clustering
Learning Intersections of Halfspaces with a Margin
A Nearly Optimal Variant of the Perceptron Algorithm for the Uniform Distribution on the Unit Sphere
On the query complexity of sampling from non-log-concave distributions (extended abstract)
Differentially Private Feature Selection via Stability Arguments, and the Robustness of the Lasso
PAC Verification of Statistical Algorithms
Sparsity-Based Interpolation of External, Internal and Swap Regret
On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions
General Bounds on the Number of Examples Needed for Learning Probabilistic Concepts
Efficient Identification of Regular Expressions from Representative Examples
Finite-Sample Symmetric Mean Estimation with Fisher Information Rate
Efficient and robust algorithms for adversarial linear contextual bandits
Learning k-DNF with Noise in the Attributes
Lower and Upper Bounds on the Generalization of Stochastic Exponentially Concave Optimization
Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results
Kernel interpolation in Sobolev spaces is not consistent in low dimensions
Tracking the Best Hyperplane with a Simple Budget Perceptron
Vector-Valued Property Elicitation
Uniform-Distribution Learnability of Noisy Linear Threshold Functions with Restricted Focus of Attention
Online Nonconvex Optimization with Limited Instantaneous Oracle Feedback
Learning k µ Decision Trees on the Uniform Distribution
Thompson Sampling for Bandit Convex Optimisation
On the Convergence Rate of Good-Turing Estimators
Depth Separation in Norm-Bounded Infinite-Width Neural Networks
Online Learning with Variable Stage Duration
On Empirical Bayes Variational Autoencoder: An Excess Risk Bound
Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance
On the Margin Explanation of Boosting Algorithms
Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk
Learning Regular Languages From Counterexamples
Rigorous Guarantees for Tyler's M-Estimator via Quantum Expansion
The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints
A General Class of No-Regret Learning Algorithms and Game-Theoretic Equilibria
Capabilities of Probabilistic Learners with Bounded Mind Changes
Physics-informed machine learning as a kernel method
Derivatives and residual distribution of regularized M-estimators with application to adaptive tuning
The Optimal PAC Algorithm
Escaping From Saddle Points - Online Stochastic Gradient for Tensor Decomposition
Hardness of Maximum Likelihood Learning of DPPs
Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization
Gradient Descent Only Converges to Minimizers
Improved Guarantees for Learning via Similarity Functions
Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learning
Inductive Inference with Bounded Number of Mind Changes
Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
Bessel Smoothing and Multi-Distribution Property Estimation
The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint
Learning Over Compact Metric Spaces
Learning Nested Halfspaces and Uphill Decision Trees
New Lower Bounds for Non-Convex Stochastic Optimization through Divergence Decomposition
The Thirty Eighth Annual Conference on Learning Theory, 30-4 July 2025, Lyon, France
Optimal rates for total variation denoising
Learning by a Population of Perceptrons
Actively Avoiding Nonsense in Generative Models
Reinforcement Learning and Mistake Bounded Algorithms
Margin Based Active Learning
Learning a Hidden Hypergraph
Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
Learning Threshold Functions with Small Weights Using Membership Queries
Efficient Algorithms for General Active Learning
Thompson Sampling for the MNL-Bandit
Concentration Bounds for Unigrams Language Model
Toward Learning Gaussian Mixtures with Arbitrary Separation
A Query Algorithm for Agnostically Learning DNF?
Market Making without Regret
Sequential prediction under log-loss and misspecification
Thresholds for Reconstruction of Random Hypergraphs From Graph Projections
Testing Symmetric Markov Chains From a Single Trajectory
Sharp thresholds in inference of planted subgraphs
Agnostic Learning Nonconvex Function Classes
Open Problem: Do Good Algorithms Necessarily Query Bad Points?
A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal and Parameter-free
Understanding Riemannian Acceleration via a Proximal Extragradient Framework
Online Learning and Solving Infinite Games with an ERM Oracle
Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems
Boosting in the Presence of Massart Noise
Stochastic Composite Least-Squares Regression with Convergence Rate $O(1/n)$
Root-n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank
Computational Learning Theory, 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, 2002, Proceedings
Random Graph Matching in Geometric Models: the Case of Complete Graphs
On Learning from Exercises
Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
Theoretical Analysis of a Class of Randomized Regularization Methods
Improved Learning of AC 0 Functions
Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity
An Inequality with Applications to Structured Sparsity and Multitask Dictionary Learning
The Influence of Shape Constraints on the Thresholding Bandit Problem
Learning by Smoothing: A Morphological Approach
Learning Coordinate Gradients with Multi-Task Kernels
Learning Agents for Uncertain Environments (Extended Abstract)
Piecemeal Learning of an Unknown Environment
Proceedings of the Ninth Annual Conference on Computational Learning Theory, COLT 1996, Desenzano del Garda, Italy, June 28-July 1, 1996
Unsupervised Learning for Natural Language Processing
SGD Generalizes Better Than GD (And Regularization Doesn't Help)
Tsallis-INF for Decoupled Exploration and Exploitation in Multi-armed Bandits
A Competitive Approach to Game Learning
On-line Learning and the Metrical Task System Problem
Bagging is an Optimal PAC Learner
Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
Opportunistic Strategies for Generalized No-Regret Problems
Language Learning From Texts: Degrees of Instrinsic Complexity and Their Characterizations
Finite-Time Error Bounds For Linear Stochastic Approximation andTD Learning
Learning Low Degree Hypergraphs
Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
The Relative Complexity of Maximum Likelihood Estimation, MAP Estimation, and Sampling
On-line Evaluation and Prediction using Linear Functions
On the Minimal Error of Empirical Risk Minimization
Optimistic Rates for Learning from Label Proportions
Open Problem: Efficient Online Sparse Regression
Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process
Bounds for the Minimum Disagreement Problem with Applications to Learning Theory
Fast Identification of Geometric Objects with Membership Queries
Learning Curve Bounds for a Markov Decision Process with Undiscounted Rewards
Principal eigenstate classical shadows
Open Problem: A (missing) boosting-type convergence result for AdaBoost.MH with factorized multi-class classifiers
Robustly Learning Monotone Generalized Linear Models via Data Augmentation
Conference on Learning Theory 2018: Preface
The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India
Characterization of Linkage-based Clustering
Regret Minimization in Heavy-Tailed Bandits
Universal Rates for Regression: Separations between Cut-Off and Absolute Loss
Improved Margin Generalization Bounds for Voting Classifiers
Logarithmic regret of exploration in average reward Markov decision processes
On the Number of Examples and Stages Needed for Learning Decision Trees
Linear Classifiers are Nearly Optimal When Hidden Variables Have Diverse Effect
Dimension-free convergence rates for gradient Langevin dynamics in RKHS
On the Power of Polynomial Discriminators and Radial Basis Function Networks
Tensor principal component analysis via sum-of-square proofs
Data-Dependent Bounds for Multi-category Classification Based on Convex Losses
Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
Observational Learning in Random Networks
Consistency in Models for Communication Constrained Distributed Learning
Exact Learning of Unordered Tree Patterns from Queries
Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization
Projection-free Online Exp-concave Optimization
VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation
Cortical Computation via Iterative Constructions
Wasserstein Control of Mirror Langevin Monte Carlo
Robustly-reliable learners under poisoning attacks
Noise-Tolerant Parallel Learning of Geometric Concepts
Fitting a Putative Manifold to Noisy Data
Random Subclass Bounds
Costly Zero Order Oracles
How do infinite width bounded norm networks look in function space?
Self-Directed Linear Classification
Sequential PAC Learning
Can We Learn to Gamble Efficiently?
A Theory of Selective Prediction
Neural Networks and Efficient Associative Memory
Deterministic Calibration and Nash Equilibrium
On Classification-Calibration of Gamma-Phi Losses
Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity
Calibrating Noise to Variance in Adaptive Data Analysis
On-line Learning of Rectangles
Sample-Optimal Low-Rank Approximation of Distance Matrices
Trace norm regularization for multi-task learning with scarce data
Open Problem: Finding Good Cascade Sampling Processes for the Network Inference Problem
Exp-Concavity of Proper Composite Losses
A New Perspective on an Old Perceptron Algorithm
Computationally Efficient Robust Sparse Estimation in High Dimensions
On the Limits of Proper Learnability of Subclasses of DNF Formulas
Hierarchical Clustering: A 0.585 Revenue Approximation
Fundamental limits of symmetric low-rank matrix estimation
A Distributional-Lifting Theorem for PAC Learning
On the Learnability of Z n -DNF Formulas (Extended Abstract)
New Results for Random Walk Learning
Adaptive Submodular Maximization under Stochastic Item Costs
Forest Density Estimation
Resampling-Based Confidence Regions and Multiple Tests for a Correlated Random Vector
Pruning is Optimal for Learning Sparse Features in High-Dimensions
Online Newton Method for Bandit Convex Optimisation Extended Abstract
Learning with Global Cost in Stochastic Environments
Robust Algorithms for Recovering Planted r-Colorable Graphs
Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory
Minimax optimal testing by classification
Randomized partition trees for exact nearest neighbor search
Learning from a Mixture of Labeled and Unlabeled Examples with Parametric Side Information
The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria
Robustness of Spectral Methods for Community Detection
Learning Convex Bodies is Hard
Beating the Hold-Out: Bounds for K-fold and Progressive Cross-Validation
Individual Sequence Prediction - Upper Bounds and Application for Complexity
Kernelized Diffusion Maps
Learning via Queries to an Oracle
Settling the sample complexity of online reinforcement learning
Sketching Information Divergences
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise
Learning Correction Grammars
Learning with Unreliable Boundary Queries
Learning Over-Parametrized Two-Layer Neural Networks beyond NTK
Open Problems in Efficient Semi-supervised PAC Learning
Learning the Internet
Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models
Learning to Control Linear Systems can be Hard
Compute Inclusion Depth of a Pattern
Probably Almost Discriminative Learning
Regret Bounds for Sleeping Experts and Bandits
Simple, Efficient, and Neural Algorithms for Sparse Coding
Proceedings of the Thirteenth Annual Conference on Computational Learning Theory (COLT 2000), June 28 - July 1, 2000, Palo Alto, California, USA
Bhattacharyya Expected Likelihood Kernels
Hedging Structured Concepts
Accelerated Parameter-Free Stochastic Optimization
Learning Probabilistic Linear-Threshold Classifiers via Selective Sampling
Noisy Tensor Completion via the Sum-of-Squares Hierarchy
Can a calibration metric be both testable and actionable?
Composite Objective Mirror Descent
ZigZag: A New Approach to Adaptive Online Learning
Generation through the lens of learning theory
Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance
Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo
Complete Policy Regret Bounds for Tallying Bandits
Equivalence of Models for Polynomial Learnability
Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, COLT 1993, Santa Cruz, CA, USA, July 26-28, 1993
Proper Learning Algorithm for Functions of k Terms Under Smooth Distributions
Open Problem: Tight Convergence of SGD in Constant Dimension
The Computational Complexity of Finding Stationary Points in Non-Convex Optimization
Proceedings of the Twelfth Annual Conference on Computational Learning Theory, COLT 1999, Santa Cruz, CA, USA, July 7-9, 1999
Efficient Reinforcement Learning
Computational-Statistical Gap in Reinforcement Learning
Robust Efficient Conditional Probability Estimation
On Learning in the Presence of Unspecified Attribute Values
Performance Guarantees for Hierarchical Clustering
Learning Rational Stochastic Languages
Black-Box Control for Linear Dynamical Systems
On the Computational Complexity of Approximating Distributions by Probabilistic Automata
Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning
Exponential Weights Algorithms for Selective Learning
Evaluating the Performance of a Simple Inductive Procedure in the Presence of Overfitting Error
Open Problem: The Oracle Complexity of Smooth Convex Optimization in Nonstandard Settings
Functional Classification with Margin Conditions
Statistical curriculum learning: An elimination algorithm achieving an oracle risk
Combinatorial Algorithms for Optimal Design
Rank, Trace-Norm and Max-Norm
Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities
Partial and Exact Recovery of a Random Hypergraph from its Graph Projection
Approximation Algorithms for Clustering Problems
Group testing and local search: is there a computational-statistical gap?
Robust Multi-objective Learning with Mentor Feedback
Convergence of Kinetic Langevin Monte Carlo on Lie groups
Open Problem: What is the Complexity of Joint Differential Privacy in Linear Contextual Bandits?
Majority-of-Three: The Simplest Optimal Learner?
Higher-Order Regret Bounds with Switching Costs