yusuke1997/dblp-id-title huggingface dataset:
Competitive Collaborative Learning
Universality of Computational Lower Bounds for Submatrix Detection
Statistical Estimation and Online Inference via Local SGD
Inference and Minimization of Hidden Markov Chains
Absolute Error Bounds for Learning Linear Functions Online
Learning Theories in a Subset of a Polyadic Logic
Proper Learning, Helly Number, and an Optimal SVM Bound
Random Coordinate Langevin Monte Carlo
Learning Atomic Formulas with Prescribed Properties
Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity
Generalized Notions of Mind Change Complexity
A Non-Adaptive Algorithm for the Quantitative Group Testing Problem
Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares
Approximation Algorithms for Socially Fair Clustering
Efficient Representations for Lifelong Learning and Autoencoding
Extensional Set Learning (extended abstract)
"All-Something-Nothing" Phase Transitions in Planted k-Factor Recovery (Extended Abstract)
Lower Bounds on the VC-Dimension of Smoothly Parametrized Function Classes
The power of an adversary in Glauber dynamics
Robust Online Convex Optimization in the Presence of Outliers
Combinatorial Bandits
Maximin Action Identification: A New Bandit Framework for Games
Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimality (extended abstract)
DNF Are Teachable in the Average Case
Learning sparse mixtures of permutations from noisy information
Nearly-tight VC-dimension bounds for piecewise linear neural networks
Effective Semisupervised Learning on Manifolds
Gradient Methods with Online Scaling
Weak Recovery Threshold for the Hypergraph Stochastic Block Model
Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise
A Robust Spectral Algorithm for Overcomplete Tensor Decomposition
Learning Programs with an Easy to Calculate Set of Errors
Second Order Methods for Bandit Optimization and Control
Learning Mixtures of Discrete Product Distributions using Spectral Decompositions
An Optimal-Control Application of Two Paradigms of On-Line Learning
Optimal Dynamic Regret in Exp-Concave Online Learning
Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals
The True Sample Complexity of Active Learning
An Apprentice Learning Model (extended abstract)
The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime
Randomized Approximate Aggregating Strategies and Their Applications to Prediction and Discrimination
Proper Losses, Moduli of Convexity, and Surrogate Regret Bounds
Bayes-Optimal Scorers for Bipartite Ranking
A Dichotomy Theorem for Learning Quantified Boolean Formulas
Sample Sizes for Sigmoidal Neural Networks
Polynomial Certificates for Propositional Classes
Sparse Recovery in Large Ensembles of Kernel Machines On-Line Learning and Bandits
Highly-Smooth Zero-th Order Online Optimization
A Geometric Approach to Threshold Circuit Complexity
Consistency of Robust Kernel Density Estimators
The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada
Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
Fast rates for online learning in Linearly Solvable Markov Decision Processes
Learning Coverage Functions and Private Release of Marginals
The Planted Spanning Tree Problems: Exact Overlap Characterization via Local Weak Convergence Extended Abstract
Open Problem: The landscape of the loss surfaces of multilayer networks
Martingale Boosting
An Experimental and Theoretical Comparison of Model Selection Methods
High probability guarantees for stochastic convex optimization
High-Dimensional Projection Pursuit: Outer Bounds and Applications to Interpolation in Neural Networks
Quantum Predictive Learning and Communication Complexity with Single Input
Consistent Partial Identification
Learning Read-Once Formulas over Fields and Extended Bases
Continuous Experts and the Binning Algorithm
Exponential Convergence of Testing Error for Stochastic Gradient Methods
Conference on Learning Theory, 2-5 July 2022, London, UK
Open Problem: Analyzing Ant Robot Coverage
Volumetric Spanners: an Efficient Exploration Basis for Learning
Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard
Sparse sketches with small inversion bias
Exponential Hardness of Reinforcement Learning with Linear Function Approximation
Stochastic block models with many communities and the Kesten-Stigum bound - extended abstract
Efficient Co-Training of Linear Separators under Weak Dependence
Learning and Parsing Stochastic Unification-Based Grammars
Sharp Constants in Uniformity Testing via the Huber Statistic
Private Matrix Approximation and Geometry of Unitary Orbits
Tracking the Best Regressor
From tree matching to sparse graph alignment
Moment Multicalibration for Uncertainty Estimation
Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA
An Analysis of the t-SNE Algorithm for Data Visualization
Spatial properties of Bayesian unsupervised trees
Some Weak Learning Results
On Learning Multiple Concepts in Parallel
The implicit bias of gradient descent on nonseparable data
Learning Monotone DNF with an Incomplete Membership Oracle
A Pretty Fast Algorithm for Adaptive Private Mean Estimation
Probably Almost Bayes Decisions
Zeroth-order Optimization with Weak Dimension Dependency
Learnability of Description Logics
Accelerating Stochastic Gradient Descent for Least Squares Regression
Learning in Matrix Games can be Arbitrarily Complex
Structured Logconcave Sampling with a Restricted Gaussian Oracle
VC Classes are Adversarially Robustly Learnable, but Only Improperly
Risk-Sensitive Online Algorithms (Extended Abstract)
Viewing all Models as "Probabilistic"
Learning shallow quantum circuits with many-qubit gates
Decision Tree Approximations of Boolean Functions
benefits of depth in neural networks
Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals
Logistic Regression: The Importance of Being Improper
A Brief Look at Some Machine Learning Problems in Genomics
FINite Learning Capabilities and Their Limits
Mercer's Theorem, Feature Maps, and Smoothing
Near Optimal Distributed Learning of Halfspaces with Two Parties
The Price of Selection in Differential Privacy
Learning from Collective Behavior
The Query Complexity of Local Search and Brouwer in Rounds
On the Consistency of Output Code Based Learning Algorithms for Multiclass Learning Problems
Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
Preface: Conference on Learning Theory (COLT), 2017
Optimistic Q-learning for average reward and episodic reinforcement learning extended abstract
Universal Online Learning: an Optimistically Universal Learning Rule
An O(n log log n ) Learning Algorithm for DNF Under the Uniform Distribution
Universality of Langevin Diffusion for Private Optimization, with Applications to Sampling from Rashomon Sets
Statistical Sufficiency for Classes in Empirical L 2 Spaces
The Dual DFA Learning Problem: Hardness Results for Programming by Demonstration and Learning First-Order Representations (Extended Abstract)
SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics
Linearization Algorithms for Fully Composite Optimization
Predicting with Distributions
Minimizing Dynamic Regret on Geodesic Metric Spaces
Predictive Complexity and Information
List Sample Compression and Uniform Convergence
Efficient Learning of Linear Separators under Bounded Noise
Provable Advantage in Quantum PAC Learning
Learning Changing Concepts by Exploiting the Structure of Change
Geometric & Topological Representations of Maximum Classes with Applications to Sample Compression
Learning One-Variable Pattern Languages in Linear Average Time
Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations
The Value of Agreement, a New Boosting Algorithm
On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA
Open Problem: Shifting Experts on Easy Data
Learning Rates for Q-Learning
Robust learning under clean-label attack
Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regret
Low-dimensional adaptation of diffusion models: Convergence in total variation (extended abstract)
Learning and Generalization.(Abstract)
Deterministic Nonsmooth Nonconvex Optimization
Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm
Testable Learning with Distribution Shift
Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
Density Estimation in Linear Time
Generalization Bounds for Decision Trees
Inductive Inference from Positive Data is Powerful
Significance and Recovery of Block Structures in Binary Matrices with Noise
A Consistent Strategy for Boosting Algorithms
Complexity of Injectivity and Verification of ReLU Neural Networks (Extended Abstract)
Language Learning from Stochastic Input
Classification with Asymmetric Label Noise: Consistency and Maximal Denoising
Probabilistic and Team PFIN-Type Learning: General Properties
Metric Clustering and MST with Strong and Weak Distance Oracles
Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions
Limits of Model Selection under Transfer Learning
On the Proper Learning of Axis Parallel Concepts
A Note on Learning Multivariate Polynomials Under the Uniform Distribution (Extended Abstract)
On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels
Detection of L ∞ Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion
The Online Loop-free Stochastic Shortest-Path Problem
Size-Independent Sample Complexity of Neural Networks
Regression NSS: An Alternative to Cross Validation
Balancing Gaussian vectors in high dimension
On the Sample Complexity of Learning Smooth Cuts on a Manifold
VC Dimension of an Integrate-and-Fire Neuron Model
Lower Bounds for PAC Learning with Queries
A PTAS for Agnostically Learning Halfspaces
Deterministic Apple Tasting
Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs
The Computational Complexity of Densest Region Detection
On the Computational Power of Online Gradient Descent
Inductive Inference of Functions on the Rationals
Efficient, Noise-Tolerant, and Private Learning via Boosting
Noisy Population Recovery from Unknown Noise
Learning Monotone DNF from a Teacher That Almost Does Not Answer Membership Queries
Being Taught can be Faster than Asking Questions
A Sharp Memory-Regret Trade-off for Multi-Pass Streaming Bandits
Regularization and Optimal Multiclass Learning
Efficient Distribution-Free Learning of Probabilistic Concepts (Abstract)
Learning from Uncertain Data
Exploiting Task Relatedness for Mulitple Task Learning
Learning with Maximum-Entropy Distributions
The Learning Power of Evolution
Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptions
A non-backtracking method for long matrix and tensor completion
Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
Adversarially-Robust Inference on Trees via Belief Propagation
Efficient Unsupervised Learning
Correlated Binomial Process
Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms
More Adaptive Algorithms for Adversarial Bandits
Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses
Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature
Inference under Information Constraints: Lower Bounds from Chi-Square Contraction
On Learning width Two Branching Programs (Extended Abstract)
Ignoring Is a Bliss: Learning with Large Noise Through Reweighting-Minimization
The complexity of learning according to two models of a drifting environment
The Weak Aggregating Algorithm and Weak Mixability
PAC Adaptive Control of Linear Systems
Empirical Risk Minimization for Stochastic Convex Optimization: $O(1/n)$- and $O(1/n^2)$-type of Risk Bounds
Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox
Basis Learning as an Algorithmic Primitive
Reinforcement Learning for Average Reward Zero-Sum Games
Highly smooth minimization of non-smooth problems
Finite Learning by a "Team"
Learning to Sample from Censored Markov Random Fields
On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
Separating Models of Learning from Correlated and Uncorrelated Data
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results
Single Trajectory Nonparametric Learning of Nonlinear Dynamics
Linear bandits with polylogarithmic minimax regret
Variable Selection is Hard
An Efficient Reduction of Ranking to Classification
Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms
Generalized Mixability via Entropic Duality
Online Learning with Predictable Sequences
Conference on Learning Theory 2020: Preface
Elicitation and Identification of Properties
Online Reinforcement Learning in Stochastic Continuous-Time Systems
Uniform Convergence of Adaptive Graph-Based Regularization
Implicit Regularization in ReLU Networks with the Square Loss
Injective Hilbert Space Embeddings of Probability Measures
On the Convergence of Spectral Clustering on Random Samples: The Normalized Case
Generalization error bound for denoising score matching under relaxed manifold assumption
Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique
Efficient Learning of Monotone Concepts via Quadratic Optimization
When Is There a Free Matrix Lunch?
Improper Multiclass Boosting
Active Learning with Simple Questions
Underdamped Langevin MCMC: A non-asymptotic analysis
Average-Case Complexity of Learning Polynomials
The Role of Environment Access in Agnostic Reinforcement Learning (Extended Abstract)
Sequence Prediction in Realizable and Non-realizable Cases
Testing Problems with Sub-Learning Sample Complexity
Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression
Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation
Moments, Random Walks, and Limits for Spectrum Approximation
Open Problem: Learning Quantum Circuits with Queries
PAC Learning With Generalized Samples and an Application to Stochastic Geometry
Occam's Hammer
Radial Basis Function Neural Networks Have Superlinear VC Dimension
Improved analysis for a proximal algorithm for sampling
Optimizing Optimizers: Regret-optimal gradient descent algorithms
Toward a Computational Theory of Data Acquisition and Truthing
Learning Unions of Boxes with Membership and Equivalence Queries
Depth Separations in Neural Networks: Separating the Dimension from the Accuracy
The Spectral Method for General Mixture Models
Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling
MadaBoost: A Modification of AdaBoost
A Light Touch for Heavily Constrained SGD
Geometric Methods in the Analysis of Glivenko-Cantelli Classes
Learning from Weakly Dependent Data under Dobrushin's Condition
Learning rates for Gaussian mixtures under group action
Exact Learning of Tree Patterns from Queries and Counterexamples
Statistical and Computational Limits for Tensor-on-Tensor Association Detection
Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent
Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions
Online Multitask Learning
Compressed Counting Meets Compressed Sensing
Faster online calibration without randomization: interval forecasts and the power of two choices
Adaptive Learning with Robust Generalization Guarantees
Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds
On-line Sequential Bin Packing
The Complexity of Improperly Learning Large Margin Halfspaces
Learning with Malicious Membership Queries and Exceptions (Extended Abstract)
Learning in the Presence of Inaccurate Information
Robust and Proper Learning for Mixtures of Gaussians via Systems of Polynomial Inequalities
Incentivizing Exploration by Heterogeneous Users
Detection limits in the high-dimensional spiked rectangular model
Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss
Stochastic Regret Minimization via Thompson Sampling
Rate of Approximation Results Motivated by Robust Neural Network Learning
Learning to Reason with a Restricted View
Learning Augmented Graph k-Clustering
Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
Regret Bounds for Robust Online Decision Making
Complexity Theoretic Lower Bounds for Sparse Principal Component Detection
Learning Pattern Languages from a Single Initial Example and from Queries
Active and passive learning of linear separators under log-concave distributions
Local Risk Bounds for Statistical Aggregation
Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits
Proofs as Explanations: Short Certificates for Reliable Predictions
A Game of Prediction with Expert Advice
Learning Monotone kµ DNF Formulas on Product Distributions
Open Problem: Adversarial Multiarmed Bandits with Limited Advice
On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems
On Probably Correct Classification of Concepts
Pessimism About Unknown Unknowns Inspires Conservatism
Optimal Learning of Mallows Block Model
On Learning and Logic
Scale-free Adversarial Reinforcement Learning
A Function Representation for Learning in Banach Spaces
Testing Identity of Multidimensional Histograms
Efficient Algorithms for Outlier-Robust Regression
Open Problem: How fast can a multiclass test set be overfit?
Private Convex Optimization via Exponential Mechanism
A Simple Algorithm for Learning O(log n)-Term DNF
Inferring Deterministic Linear Languages
Toward Attribute Efficient Learning of Decision Lists and Parities
Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem
Characterizations of Learnability for Classes of { O, ..., n }-Valued Functions
Recovering the Optimal Solution by Dual Random Projection
Learning Linear Dynamical Systems with Semi-Parametric Least Squares
On Avoiding the Union Bound When Answering Multiple Differentially Private Queries
Computational Limits for Matrix Completion
A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates
DiscQuant: A Quantization Method for Neural Networks Inspired by Discrepancy Theory
On Consistent Surrogate Risk Minimization and Property Elicitation
From Fairness to Infinity: Outcome-Indistinguishable (Omni)Prediction in Evolving Graphs
An Asymptotically Optimal Bandit Algorithm for Bounded Support Models
Redundant Noisy Attributes, Attribute Errors, and Linear-Threshold Learning Using Winnow
A Private and Computationally-Efficient Estimator for Unbounded Gaussians
Cryptographic Lower Bounds for Learnability of Boolean Functions on the Uniform Distribution
Learning with Rigorous Support Vector Machines
Quasi-Newton Steps for Efficient Online Exp-Concave Optimization
An $\widetilde\mathcalO(m/\varepsilon^3.5)$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints
Generalised Pinsker Inequalities
Space lower bounds for linear prediction in the streaming model
Boosting a Weak Learning Algorithm by Majority
Information Theory in Probability, Statistics, Learning, and Neural Nets (Abstract)
Efficiently Approximating Weighted Sums with Exponentially Many Terms
Memorize to generalize: on the necessity of interpolation in high dimensional linear regression
Honest Compressions and Their Application to Compression Schemes
Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
Learning Single-Index Models in Gaussian Space
Approachability in unknown games: Online learning meets multi-objective optimization
An Information Theoretic Framework for Multi-view Learning
SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians
On characterizations of learnability with computable learners
Near-Optimal Learning and Planning in Separated Latent MDPs
Monotone Learning
How Good Is a Kernel When Used as a Similarity Measure?
A Greedy Anytime Algorithm for Sparse PCA
Communication and Memory Efficient Testing of Discrete Distributions
Parameter-free Mirror Descent
Teaching a Smart Learner
Open problem: Direct Sums in Learning Theory
Hybrid Stochastic-Adversarial On-line Learning
When Random Play is Optimal Against an Adversary
Improved Bounds for Multi-task Learning with Trace Norm Regularization
Learning Random Log-Depth Decision Trees under the Uniform Distribution
On Boosting with Optimal Poly-Bounded Distributions
Experimental Design for Semiparametric Bandits
A Technique for Upper Bounding the Spectral Norm with Applications to Learning
Boosting as Entropy Projection
Prediction and Dimension
Universality of High-Dimensional Logistic Regression and a Novel CGMT under Dependence with Applications to Data Augmentation
Near optimal efficient decoding from pooled data
Results on Learnability and the Vapnick-Chervonenkis Dimension
On Threshold Circuits for Parity (Abstract)
Sample complexity of partition identification using multi-armed bandits
Learning DNF through Generalized Fourier Representations
Geometrical Concept Learning and Convex Polytopes
Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
A Lower Bound for Agnostically Learning Disjunctions
Leaving the Span
On Learning Read- k -Satisfy- j DNF
Improved Algorithms for Theory Revision with Queries
The Learning Complexity of Smooth Functions of a Single Variable
Fast Kernels for Inexact String Matching
Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency
Learning Conjunctions of Horn Clauses (Abstract)
On Learning Visual Concepts and DNF Formulae
Learning Acyclic Probabilistic Circuits Using Test Paths
Statistical Properties of Kernel Principal Component Analysis
Minimax Regret Under log Loss for General Classes of Experts
Johnson-Lindenstrauss Transforms with Best Confidence
Maximizing the Margin with Boosting
Size and Depth Separation in Approximating Benign Functions with Neural Networks
Online Density Estimation of Bradley-Terry Models
Approximate Nearest Neighbors in Limited Space
A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
Universal Rates for Multiclass Learning
On the Learnability of Infinitary Regular Sets
Open Problem: Optimal Rates for Stochastic Decision-Theoretic Online Learning Under Differentially Privacy
Open Problem: Learning sparse linear concepts by priming the features
Empirical Bernstein Bounds and Sample-Variance Penalization
Learning Hierarchical Rule Sets
Linear Relations between Square-Loss and Kolmogorov Complexity
Estimating the Optimal Margins of Embeddings in Euclidean Half Spaces
Learning Two-Tape Automata from Queries and Counterexamples
Optimal score estimation via empirical Bayes smoothing
Online Variance Minimization
Learning Tree Languages from Text
Efficiently Learning One-Hidden-Layer ReLU Networks via SchurPolynomials
SVM-Optimization and Steepest-Descent Line Search
Taking Advantage of Sparsity in Multi-Task Learning
Learning in Non-convex Games with an Optimization Oracle
Affine Invariant Covariance Estimation for Heavy-Tailed Distributions
On Efficient Agnostic Learning of Linear Combinations of Basis Functions
Computable Shell Decomposition Bounds
Learning from a Population of Hypotheses
Bounded Memory Active Learning through Enriched Queries
Classification with unknown class-conditional label noise on non-compact feature spaces