yusuke1997/dblp-id-title huggingface dataset:
Online Learning of Maximum p-Norm Margin Classifiers with Bias
Sparse Adaptive Dirichlet-Multinomial-like Processes
A Law of Robustness for Two-Layers Neural Networks
The Consistency of Greedy Algorithms for Classification
Two fundamental limits for uncertainty quantification in predictive inference
Sample Compression for Multi-label Concept Classes
Improved dimension dependence of a proximal algorithm for sampling
Statistical and Computational Phase Transitions in Group Testing
Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs
Convergence Analysis of Temporal-Difference Learning Algorithms with Linear Function Approximation
A Statistical Approach to Learning and Generalization in Layered Neural Networks
Passive Learning with Target Risk
Subpolynomial trace reconstruction for random strings \{and arbitrary deletion probability
How Good is SGD with Random Shuffling?
The Hidden Hubs Problem
Learning Compositional Functions with Transformers from Easy-to-Hard Data
On Learning Limiting Programs
Composite Geometric Concepts and Polynomial Predictability
Optimum Statistical Estimation with Strategic Data Sources
Extrapolating the profile of a finite population
Information-theoretic generalization bounds for learning from quantum data
Log-concave sampling: Metropolis-Hastings algorithms are fast!
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees
Learning Specialist Decision Lists
The Minimum L -Complexity Algorithm and its Applications to Learning Non-Parametric Rules
Efficient Algorithms for Learning from Coarse Labels
Efficient Learning of Simplices
On-Line Learning of Rectangles in Noisy Environments
Beyond Gaussians: Spectral Methods for Learning Mixtures of Heavy-Tailed Distributions
Minimax rates for memory-bounded sparse linear regression
PAC-MDL Bounds
Width is Less Important than Depth in ReLU Neural Networks
Minimizing Wide Range Regret with Time Selection Functions
Tight Bounds for Bandit Combinatorial Optimization
Online Learning of Noisy Data with Kernels
Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits
Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions
A Learning Criterion for Stochastic Rules
Pattern Languages are not Learnable
Asymptotic confidence sets for random linear programs
Multi-Pass Memory Lower Bounds for Learning Problems
Optimal Tensor Methods in Smooth Convex and Uniformly ConvexOptimization
Spectral Algorithms for Learning and Clustering
On Sequential Prediction of Individual Sequences Relative to a Set of Experts
Loss Bounds for Online Category Ranking
Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability
Discrete Prediction Games with Arbitrary Feedback and Loss
On Convergence of Emphatic Temporal-Difference Learning
On Graph Kernels: Hardness Results and Efficient Alternatives
Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract)
Learning via Queries and Oracles
COLT 2011 - The 24th Annual Conference on Learning Theory, June 9-11, 2011, Budapest, Hungary
A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
Co-Learning of Total Recursive Functions
Derandomizing Stochastic Prediction Strategies
Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo
PAC-Bayesian Model Averaging
A Theoretical Analysis of NDCG Type Ranking Measures
Low Rank Matrix Completion with Exponential Family Noise
Adaptive Bound Optimization for Online Convex Optimization
Provably manipulation-resistant reputation systems
Efficient Algorithms for Learning Monophonic Halfspaces in Graphs
Black-Box Reductions for Parameter-free Online Learning in Banach Spaces
Learning Theory, 18th Annual Conference on Learning Theory, COLT 2005, Bertinoro, Italy, June 27-30, 2005, Proceedings
Of Dice and Games: A Theory of Generalized Boosting
Case-Based Learning in Inductive Inference
Mirror Descent and the Information Ratio
Angluin's Theorem for Indexed Families of r.e. Sets and Applications
Optimal Multi-Distribution Learning
An Estimate Sequence for Geodesically Convex Optimization
Robust Distribution Learning with Local and Global Adversarial Corruptions (extended abstract)
Open Problem: Fast and Optimal Online Portfolio Selection
Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov Noise
MCMC Learning
Reduced-Rank Regression with Operator Norm Error
Finding Metric Structure in Information Theoretic Clustering
Entropy Numbers of Linear Function Classes
On Learning to Coordinate: Random Bits Help, Insightful Normal Forms, and Competency Isomorphisms
Learning Mixtures of Gaussians Using Diffusion Models
General Bounds on the Mutual Information Between a Parameter and n Conditionally Independent Observations
Small-loss bounds for online learning with partial information
Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary
When can we rank well from comparisons of \(O(n\log(n))\) non-actively chosen pairs?
Shortest Program Interpolation Learning
Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds
Differentially Private Nonparametric Regression Under a Growth Condition
Learning Fallible Finite State Automata
Mean-field analysis of polynomial-width two-layer neural network beyond finite time horizon
Gardner formula for Ising perceptron models at small densities
Data-driven confidence bands for distributed nonparametric regression
Quantifying Variational Approximation for Log-Partition Function
Competing with Stationary Prediction Strategies
Minimax Linear Regression under the Quantile Risk
On the Intrinsic Complexity of Language Identification
Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes
Exploration by Optimisation in Partial Monitoring
Safe Linear Bandits over Unknown Polytopes
Cortical Learning via Prediction
Learning Fixed-Dimension Linear Thresholds from Fragmented Data
How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
Improved Dynamic Regret for Online Frank-Wolfe
The Adaptive Complexity of Finding a Stationary Point
The Speed Prior: A New Simplicity Measure Yielding Near-Optimal Computable Predictions
Mitotic Classes
Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models
Minimax Regret on Patterns Using Kullback-Leibler Divergence Covering
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
Sparse Density Estimation with l 1 Penalties
Localized Rademacher Complexities
Learning and Testing Junta Distributions
Reducibility and Statistical-Computational Gaps from Secret Leakage
A Note on Learning with Integral Operators
Uniform-Distribution Attribute Noise Learnability
Multiclass Online Learning and Uniform Convergence
A Theory of Heuristic Learnability
Informed Parsimonious Inference of Prototypical Genetic Sequences
Are all models wrong? Fundamental limits in distribution-free empirical model falsification
Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation Extended Abstract
An Improved VC Dimension Bound for Sparse Polynomials
Learning with Restricted Focus of Attention
On Learning Ring-Sum-Expansions
A Unified Characterization of Private Learnability via Graph Theory
More or Less Efficient Agnostic Learning of Convex Polygons
Rademacher Margin Complexity
Private List Learnability vs. Online List Learnability
Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties
Learning Combinatorial Functions from Pairwise Comparisons
Dense Shattering and Teaching Dimensions for Differentiable Families (Extended Abstract)
Learning Talagrand DNF Formulas
A Mechanical Method of Successful Scientific Inquiry
Limits of Approximating the Median Treatment Effect
Resource-Bounded Information Gathering for Correlation Clustering
Better Guarantees for Sparsest Cut Clustering
A PAC-Style Model for Learning from Labeled and Unlabeled Data
ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single Algorithm
A near-optimal algorithm for finite partial-monitoring games against adversarial opponents
Reliable and Useful Learning
From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization
Fine-Grained Distribution-Dependent Learning Curves
Delay and Cooperation in Nonstochastic Bandits
The Light Bulb Problem
Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints
The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability
New Potential-Based Bounds for Prediction with Expert Advice
Prediction by Categorical Features: Generalization Properties and Application to Feature Ranking
Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA
A General Characterization of the Statistical Query Complexity
Generalization Bounds via Convex Analysis
Provable Memorization via Deep Neural Networks using Sub-linear Parameters
Metric Clustering and Graph Optimization Problems using Weak Comparison Oracles
Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions
Provably efficient reinforcement learning with linear function approximation
Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification (extended abstract)
How to Trap a Gradient Flow
Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers
Learning All Subfunctions of a Function
Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014
Testing Symmetric Markov Chains Without Hitting
On the Existence of a Complexity in Fixed Budget Bandit Identification
Aggregation by Exponential Weighting and Sharp Oracle Inequalities
A Training Algorithm for Optimal Margin Classifiers
The Isotron Algorithm: High-Dimensional Isotonic Regression
Hierarchical Label Queries with Data-Dependent Partitions
Improved sample upper and lower bounds for trace estimation of quantum state powers
Online Learning via Congregational Gradient Descent
Open Problem: Kernel methods on manifolds and metric spaces. What is the probability of a positive definite geodesic exponential kernel?
Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games
Mixing Implies Lower Bounds for Space Bounded Learning
Open Problem: Online Sabotaged Shortest Path
Open problem: log(n) factor in "Local Glivenko-Cantelli
Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
Improved Regret for Zeroth-Order Stochastic Convex Bandits
On-Line Learning with Linear Loss Constraints
Reductions for Learning via Queries
Statistical Query Lower Bounds for Learning Truncated Gaussians
Ten Steps of EM Suffice for Mixtures of Two Gaussians
Performance Guarantees for Regularized Maximum Entropy Density Estimation
Find a witness or shatter: the landscape of computable PAC learning
Approximation beats concentration? An approximation view on inference with smooth radial kernels
Smooth Boosting and Learning with Malicious Noise
The Dynamics of Riemannian Robbins-Monro Algorithms
Calibrated Surrogate Losses for Adversarially Robust Classification
Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
A PAC Analysis of a Bayesian Estimator
Stochastic block model entropy and broadcasting on trees with survey
Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
Linear Convergence of Diffusion Models Under the Manifold Hypothesis
On Learning Counting Functions with Queries
Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium
Space-Bounded Learning and the Vapnik-Chervonenkis Dimension
Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes
Regularization and Semi-supervised Learning on Large Graphs
Analysis of Perceptron-Based Active Learning
Stochastic Linear Optimization under Bandit Feedback
Shape Matters: Understanding the Implicit Bias of the Noise Covariance
Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making
Open Problem: Information Complexity of VC Learning
An explicit analysis of the entropic penalty in linear programming
A General Convergence Theorem for the Decomposition Method
Discriminative Learning Can Succeed Where Generative Learning Fails
Inferring Mixtures of Markov Chains
Beating Bandits in Gradually Evolving Worlds
Localized Boosting
Near-Optimal Herding
Towards Fair Representation: Clustering and Consensus
On Suboptimality of Least Squares with Application to Estimation of Convex Bodies
Batched Bandit Problems
Stochastic Approximation for Online Tensorial Independent Component Analysis
Learnability of a Subclass of Extended Pattern Languages
The Loss Rank Principle for Model Selection
Learning DNF Under the Uniform Distribution in Quasi-Polynomial Time
On the power of adaptivity in statistical adversaries
Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
What Makes Treatment Effects Identifiable? Characterizations and Estimators Beyond Unconfoundedness (Extended Abstract)
Corrigendum to Types of Noise in Data for Concept Learning
Alternating Regret for Online Convex Optimization
A Tensor Spectral Approach to Learning Mixed Membership Community Models
Learning With a Slowly Changing Distribution
Generalization Error Bounds Using Unlabeled Data
Rate-Preserving Reductions for Blackwell Approachability
Improved Lower Bounds for Learning Intersections of Halfspaces
Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration
Multiarmed Bandits With Limited Expert Advice
The Complexity of Markov Equilibrium in Stochastic Games
An Efficient Extension to Mixture Techniques for Prediction and Decision Trees
Some Problems of Learning with an Oracle
Learning Theory, 20th Annual Conference on Learning Theory, COLT 2007, San Diego, CA, USA, June 13-15, 2007, Proceedings
Divide and Conquer Kernel Ridge Regression
Learning and Testing Latent-Tree Ising Models Efficiently
On the Average Tractability of Binary Integer Programming and the Curious Transition to Perfect Generalization in Learning Majority Functions
The Star Number and Eluder Dimension: Elementary Observations About the Dimensions of Disagreement
Dual VC Dimension Obstructs Sample Compression by Embeddings
Homogeneous Multi-Instance Learning with Arbitrary Dependence
Choosing the p in Lp Loss: Adaptive Rates for Symmetric Mean Estimation
Robust Hierarchical Clustering
Potential-Based Algorithms in Online Prediction and Game Theory
Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT
Clustering with Queries under Semi-Random Noise
Limitations of Learning via Embeddings in Euclidean Half-Spaces
Computational Learning Theory, 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 16-19, 2001, Proceedings
Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-th Derivatives
Adaptive Subgradient Methods for Online Learning and Stochastic Optimization
Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
Q -Learning with Linear Function Approximation
Information Directed Sampling and Bandits with Heteroscedastic Noise
Bregman Deviations of Generic Exponential Families
Inclusion Problems in Parallel Learning and Games (Extended Abstract)
Fat-Shattering and the Learnability of Real-Valued Functions
A Corrective View of Neural Networks: Representation, Memorization and Learning
Competing with Wild Prediction Rules
Identification of mixtures of discrete product distributions in near-optimal sample and time complexity
From Local Pseudorandom Generators to Hardness of Learning
The Many Faces of Exponential Weights in Online Learning
Online Covariance Estimation in Nonsmooth Stochastic Approximation
Excess risk bounds for multitask learning with trace norm regularization
Learning Partitions with Optimal Query and Round Complexities
Dimension-Free Bounds for Chasing Convex Functions
Beyond propagation of chaos: A stochastic algorithm for mean field optimization
A General Dimension for Exact Learning
On-line Learning of Binary and n -ary Relations over Multi-dimensional Clusters
The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity
Open Problem: Regret Minimization in Heavy-Tailed Bandits with Unknown Distributional Parameters
On the Complexity of Learning from Counterexamples and Membership Queries (abstract)
Random Multivariate Search Trees
Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints
Multi-armed Bandit Problems with Strategic Arms
Polynomial Time Inductive Inference of Ordered Tree Patterns with Internal Structured Variables from Positive Data
Projection Learning
Rate of Convergence of Polynomial Networks to Gaussian Processes
Differentially Private and Lazy Online Convex Optimization
Sparsity-aware generalization theory for deep neural networks
On Learning Arithmetic Read-Once Formulas with Exponentiation (Extended Abstract)
Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs
Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space
On the Lower Bound of Minimizing Polyak-Łojasiewicz functions
Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons
Learning Simple Auctions
Polynomial Iniform Convergence and Polynomial-Sample Learnability
The Connection Between Approximation, Depth Separation and Learnability in Neural Networks
Universal Rates for Multiclass Learning with Bandit Feedback
Universal Portfolio Selection
Tracking Linear-Threshold Concepts with Winnow
Generalization Bounds for Learning the Kernel Problem
The k-Cap Process on Geometric Random Graphs
Best Arm Identification in Multi-Armed Bandits
Gaps in Support Vector Optimization
How to safely discard features based on aggregate SHAP values
Learning Probabilistic Automata with Variable Memory Length
Sharp Theoretical Analysis for Nonparametric Testing under Random Projection
No-Regret Prediction in Marginally Stable Systems
Robustness of Evolvability
Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient
Sorted Top-k in Rounds
Faster Acceleration for Steepest Descent
Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
Solving Convex-Concave Problems with 풪(ε -4/7 ) Second-Order Oracle Complexity
Lower Bounds for Locally Private Estimation via Communication Complexity
Bandit Learnability can be Undecidable
Can Entropic Regularization Be Replaced by Squared Euclidean Distance Plus Additional Linear Constraints
Proceedings of the Eleventh Annual Conference on Computational Learning Theory, COLT 1998, Madison, Wisconsin, USA, July 24-26, 1998
Some PAC-Bayesian Theorems
On PAC Learning Using Winnow, Perceptron, and a Perceptron-like Algorithm
Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
A General Approach to Multi-Armed Bandits Under Risk Criteria
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
Asymmetric Team Learning
Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods
Learning a Hidden Graph Using O(log n) Queries Per Edge
PAC Learning Intersections of Halfspaces with Membership Queries (Extended Abstract)
Computational Sample Complexity
Tight query complexity bounds for learning graph partitions
Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm
Elementary Formal System as a Unifying Framework for Language Learning
Restricted Eigenvalue from Stable Rank with Applications to Sparse Linear Regression
Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes
Open Problem: Model Selection for Contextual Bandits
The Implicit Bias of Batch Normalization in Linear Models and Two-layer Linear Convolutional Neural Networks
A second-order bound with excess losses
A Bayesian/Information Theoretic Model of Bias Learning
Capabilities of fallible FINite Learning
Efficiently learning and sampling multimodal distributions with data-based initialization
A Lower Bound for Linear and Kernel Regression with Adaptive Covariates
Polynomial Time Algorithms for Learning Neural Nets
Necessary and Sufficient Oracles: Toward a Computational Taxonomy for Reinforcement Learning
An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits
Bounded Degree Graph Inference from Walks
Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes
Parent Assignment Is Hard for the MDL, AIC, and NML Costs
Robust Learning Aided by Context
Covering Numbers for Support Vector Machines
Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization
Learning of Depth Two Neural Networks with Constant Fan-In at the Hidden Nodes (Extended Abstract)
From Nesterov's Estimate Sequence to Riemannian Acceleration
Weak learning convex sets under normal distributions
Sequential Information Maximization: When is Greedy Near-optimal?
Learning Rotations with Little Regret
PAC-Bayesian Bound for Gaussian Process Regression and Multiple Kernel Additive Model
Property Testing: A Learning Theory Perspective
The Aggregation-Heterogeneity Trade-off in Federated Learning
Trees and Learning
Predicting {0, 1}-Functions on Randomly Drawn Points
A Theory of Learning with Autoregressive Chain of Thought
Towards a Dimension-Free Understanding of Adaptive Linear Control
Linear Time Deterministic Learning of k -Term DNF
Multi-Agent Learning for Iterative Dominance Elimination: Formal Barriers and New Algorithms
Learning Narrow One-Hidden-Layer ReLU Networks
Sharp analysis of low-rank kernel matrix approximations
Resourceful Contextual Bandits
Exploring Learnability between Exact and PAC
On the Efficiency of Noise-Tolerant PAC Algorithms Derived from Statistical Queries
Open Problem: Tight Characterization of Instance-Optimal Identity Testing
Time Varying Undirected Graphs
Sample Complexity of Model-Based Search
Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms
Privately Learning Thresholds: Closing the Exponential Gap
Perceptron-Like Performance for Intersections of Halfspaces
An Improved Boosting Algorithm and Its Implications on Learning Complexity
Homotopy Analysis for Tensor PCA
The sample complexity of multi-distribution learning
Approachability, fast and slow
Testing Bayesian Networks
Chained generalisation bounds
Adaptive Strategies and Regret Minimization in Arbitrarily Varying Markov Environments
A faster and simpler algorithm for learning shallow networks
Learnability Gaps of Strategic Classification
On the Synthesis of Strategies Identifying Recursive Functions
Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions
On the Ability of Neural Nets to Express Distributions
Learning from Examples with Unspecified Attribute Values (Extended Abstract)
Nonstochastic Bandits with Composite Anonymous Feedback
PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes
Sharper Bounds for Uniformly Stable Algorithms
Minimax Games with Bandits
Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes
A Sober Look at Clustering Stability