Comparative learning combines realizable and agnostic settings for two hypothesis classes, reducing sample complexity.
problem Learning with two hypothesis classes in a more general setting than single hypothesis classes.
method Introduces comparative learning, defines mutual VC dimension and Littlestone dimension, and applies insights to multiaccuracy and multicalibration.
result Sample complexity of comparative learning is characterized by mutual VC dimension and Littlestone dimension.
Analyzes the complexity of linear hypothesis sets using Rademacher complexity.
problem Understanding the complexity of linear hypothesis sets for various norms.
method Tight analysis of empirical Rademacher complexity for linear hypothesis classes with bounded weights.
result Improved bounds on Rademacher complexity for linear hypothesis sets, matching or improving existing results.
Estimates neural network errors for classification problems.
problem Binary and multi-class classification problems.
method Rademacher complexity estimates and direct approximation theorems.
result A priori error estimates for regularized loss functionals.
Proposes a new approach to regression learning that addresses overfitting and underfitting.
problem Regression learning issues, including overfitting and underfitting.
method Introduces epsilon-Confidence Approximately Correct (epsilon CoAC) framework using Kullback Leibler divergence.
result Demonstrates improved learnability and accuracy compared to cross-validation.
New bounds explain modern machine learning algorithms' generalization.
problem Explaining generalization behavior of modern machine learning algorithms.
method Proposes a new complexity measure based on empirical Rademacher complexity of an algorithm- and data-dependent hypothesis class.
result Obtains novel bounds with finite fractal dimension, simplifies proofs, and recovers known results.
We provide a differentially private algorithm for hypothesis selection. Given samples from an unknown probability distribution P and a set of m probability distributions H, the goal is to output, in a ε-differentially private manner, a distribution from H whose total variation di…
We consider the problem of reinforcement learning over episodes of a finite-horizon deterministic system and as a solution propose optimistic constraint propagation (OCP), an algorithm designed to synthesize efficient exploration and value function generalization. We establish that when the true value function lies wit…
New algorithms for multitask learning with long-term memory.
problem Learning from tasks partitioned into unknown segments with associated hypotheses.
method Online multitask learning algorithms exploiting segmentation and hypothesis association.
result Regret bounds and efficient algorithms for various hypothesis classes.
SnapBoost uses random base hypothesis classes to improve gradient boosting performance.
problem Improving gradient boosting performance.
method Heterogeneous Newton Boosting Machine (HNBM) with variable base hypothesis classes.
result SnapBoost achieves better generalization loss than competing frameworks.
New algorithm reduces sample complexity for multi-distribution learning.
problem Achieving data-efficient multi-distribution learning with robustness and fairness.
method Proposes a novel algorithm with sample complexity (d+k)/varepsilon^2 for Vapnik-Chervonenkis (VC) dimension d, matching lower bounds.
result Algorithm matches best-known lower bound and resolves open problems in COLT 2023.
The paper solves open questions in computable PAC learning, providing a complete landscape.
problem Understanding the boundaries and capabilities of computable PAC learning.
method Analyzing and constructing decidable hypothesis classes with different sample complexities and Littlestone dimensions.
result A complete understanding of CPAC learnability, answering open questions and confirming conjectures.
New research determines the optimal sample complexity for multiclass and list learning.
problem Determining the optimal sample complexity for multiclass classification.
method Algebraic characterization of multiclass hypothesis classes in terms of their DS dimension.
result Proves a longstanding conjecture and determines the optimal dependence of sample complexity on DS dimension.
Learnable multiclass hypothesis classes don't always have a sample compression scheme of fixed size.
problem The limitation of sample compression schemes for multiclass hypothesis classes.
method Analysis of DS dimension and sample compression schemes.
result Learnable multiclass hypothesis classes do not always have a sample compression scheme of fixed size.
Establishes upper bounds on generalization error in active learning.
problem Improving query algorithms in active learning.
method Derives upper bounds on generalization error using informativeness and representativeness query strategies.
result Validates the use of regularization techniques to ensure bounds' validity.
Paper settles sample complexity for learning from multiple distributions.
problem Learning from multiple data distributions with a hypothesis class of bounded VC dimension.
method Introduced an algorithm with sample complexity of O((d+k)ε^-2)·(k/ε)^o(1).
result Algorithm matches lower bound up to sub-polynomial factor.
New approach to nonuniform learnability using measure theory.
problem Nonuniform learnability of hypotheses with varying sample sizes.
method Measure theoretic approach to redefine nonuniform learnability, introducing a new algorithm (Generalize Measure Learnability).
result Achieved statistical consistency in learning countable hypothesis classes.
Paper resolves open problems on sample complexity in binary hypothesis testing.
problem Open problems in distributed simple binary hypothesis testing under information constraints.
method One-shot lower bound on Bayes error, streamlined sample complexity formula, reverse data-processing inequality.
result Optimally tight sample complexity bounds for communication-constrained simple binary hypothesis testing.
We present a study of generalization for data-dependent hypothesis sets. We give a general learning guarantee for data-dependent hypothesis sets based on a notion of transductive Rademacher complexity. Our main result is a generalization bound for data-dependent hypothesis sets expressed in terms of a notion of hypothe…
In the supervised learning setting termed Multiple-Instance Learning (MIL), the examples are bags of instances, and the bag label is a function of the labels of its instances. Typically, this function is the Boolean OR. The learner observes a sample of bags and the bag labels, but not the instance labels that determine…
Study hypothesis testing under quantized samples with communication constraints, achieving near-optimal sample complexity.
problem Optimizing hypothesis testing with quantized samples and communication constraints.
method Developed a polynomial-time algorithm achieving near-optimal sample complexity under communication constraints.
result Achieved near-optimal sample complexity under communication constraints, with a logarithmic factor increase over unconstrained setting.
Develops bounds for deep learning risk via Hilbert coresets.
problem Risk estimation for complex deep learning models.
method Hilbert coreset approach for transductive risk bounds.
result Effective and meaningful bounds for deep neural networks.
The paper analyzes learning rates for non-irreducible Markov chains.
problem Real-world data often violates i.i.d. assumptions.
method Examines iterated random functions and contractive functions.
result Derives data-distribution dependent learning rates.
Paper develops a new generalization bound using PAC-Bayes theory and Gibbs distributions.
problem Limits of traditional generalization bounds due to complexity measures.
method Leverages PAC-Bayes bounds with Gibbs distributions to derive a flexible generalization bound.
result Derives a generalization bound that can adapt to both hypothesis class and task complexity.
We consider a problem of risk estimation for large-margin multi-class classifiers. We propose a novel risk bound for the multi-class classification problem. The bound involves the marginal distribution of the classifier and the Rademacher complexity of the hypothesis class. We prove that our bound is tight in the numbe…
New algorithms for model selection in linear bandits adapt to instance complexity.
problem Adapting to the instance-dependent complexity of the true model in linear bandits.
method Design of algorithms in fixed confidence and fixed budget settings, leveraging experimental design and selection-validation procedures.
result Near instance optimal guarantees for model selection in linear bandits.
Residual connections significantly boost the performance of deep neural networks. However, there are few theoretical results that address the influence of residuals on the hypothesis complexity and the generalization ability of deep neural networks. This paper studies the influence of residual connections on the hypoth…
We show two novel concentration inequalities for suprema of empirical processes when sampling without replacement, which both take the variance of the functions into account. While these inequalities may potentially have broad applications in learning theory in general, we exemplify their significance by studying the t…
Lower bounds and upper bounds on sample complexity for identifying linear dynamical systems.
problem Identifying an unknown linear dynamical system with limited data.
method Sample complexity lower and upper bounds, persistent excitation condition, active learning algorithm.
result Lower and upper bounds share the same dependency on key problem parameters.
Statistical learning theory has largely focused on learning and generalization given independent and identically distributed (i.i.d.) samples. Motivated by applications involving time-series data, there has been a growing literature on learning and generalization in settings where data is sampled from an ergodic proces…
New learning rule for quantum measurement classes overcomes uniform convergence issues.
problem Characterizing learnability of POVM hypothesis classes in quantum settings.
method Introduced a new learning rule called denoised ERM to address uniform convergence issues.
result Characterized learnability conditions and sample complexity bounds for POVM classes.
Formula derived for sample complexity in binary hypothesis testing.
problem Determine the minimum number of samples to distinguish between two distributions.
method Developed a formula for sample complexity in both prior-free and Bayesian settings, using Jensen-Shannon and Hellinger divergences.
result Formula characterizes sample complexity for a wide range of error parameters, up to multiplicative constants.
Boosting improves accuracy with fewer calls to weak learners for certain concept classes.
problem Improving accuracy of learning algorithms with limited weak learner calls.
method Combines boosting and list-decodable codes to achieve better performance for specific concept classes.
result A new boosting algorithm that achieves strong learning with fewer calls to weak learners and additional samples.
Study finds polynomial convergence rate for Farey sequences linked to Riemann hypothesis.
problem Understanding convergence rates of maximum mean discrepancies for Farey sequences.
method Identifying positive-semidefinite kernels and their polynomial convergence rates.
result Polynomial convergence rate of maximum mean discrepancies of Farey sequences is equivalent to the Riemann hypothesis.
The study explores whether model selection guarantees apply to contextual bandits.
problem Applying model selection guarantees to contextual bandits.
method Investigates whether similar guarantees for model selection in statistical learning can be extended to contextual bandit learning.
result Initial findings suggest that model selection guarantees may not directly apply to contextual bandits.
Boosting is a celebrated machine learning approach which is based on the idea of combining weak and moderately inaccurate hypotheses to a strong and accurate one. We study boosting under the assumption that the weak hypotheses belong to a class of bounded capacity. This assumption is inspired by the common convention t…
New bounds for private learning of high-dimensional Gaussian distributions.
problem Learning high-dimensional Gaussian distributions under differential privacy constraints.
method Analytic tools for constructing global covers from local covers, modified hypothesis selection techniques.
result Near-optimal sample complexity bounds for general Gaussians, conjectured to be near-optimal in the general case.
The existence of evasion attacks during the test phase of machine learning algorithms represents a significant challenge to both their deployment and understanding. These attacks can be carried out by adding imperceptible perturbations to inputs to generate adversarial examples and finding effective defenses and detect…
New framework for valid hypothesis testing in complex data settings.
problem Challenges in classical hypothesis testing frameworks.
method Add and subtract external noise to partition data, orthogonalize, and test hypotheses.
result Valid hypothesis tests can be conducted under minimal assumptions.
Optimal locally private hypothesis selection with interactive rounds.
problem Locally private hypothesis selection under i.i.d. samples.
method Developed an ε-LDP algorithm using critical queries for hypothesis selection.
result Achieved optimal sample complexity of Θ(k/α²ε²) for hypothesis selection.
We consider smoothings of a complex surface with singularities of class T and no nontrivial holomorphic vector field. Under an hypothesis of non degeneracy of the smoothing at each singular point, we prove that if the singular surface admits an extremal metric, then the smoothings also admit extremal metrics in nearby …
Active local learning uses fewer labels to predict near-optimal functions.
problem Efficiently predicting near-optimal functions with fewer labels.
method Active local learning algorithm for estimating functions with fewer labels.
result Algorithm makes significantly fewer label queries than traditional methods.
We propose a novel combination of optimization tools with learning theory bounds in order to analyze the sample complexity of optimal kernel sum classifiers. This contrasts the typical learning theoretic results which hold for all (potentially suboptimal) classifiers. Our work also justifies assumptions made in prior w…
New probabilistic complexity measures for linear and kernel methods.
problem Limitations of linear and kernel methods in machine learning.
method Introducing approximate notions of dimensional and margin complexity.
result Approximate complexity measures are both sufficient and necessary for learning.
Formalizes identifying information to answer key questions about machine learning from uncertain and novel observations.
problem Understanding and quantifying information from uncertain and novel observations in machine learning.
method Formalizes identifying information, defines hypothesis identification and sample complexity, and proves sample complexity properties for various data-generating processes.
result Proves the information theoretic characteristics of hypothesis identification and sample complexity, and shows how to compute identifying information and novel information.
Fisher width is a geometric measure of complexity on statistical manifolds.
problem Complexity measures on statistical manifolds
method Introducing Fisher width as a Fisher-geometric analogue of Gaussian width
result Fisher width retains key structural features of Gaussian width while capturing anisotropic geometric effects
Improved bounds on combining hypothesis classes for binary functions.
problem Understanding how to combine hypothesis classes for binary functions.
method Established upper bounds on Littlestone and threshold dimensions for combined classes.
result Upper bounds are nearly tight and give exponential improvements.
The paper tackles hypothesis testing for likelihood-free inference with a new kernel-based approach.
problem Testing hypotheses with limited labeled data in likelihood-free inference.
method Kernel-based tests using maximum mean discrepancy (MMD) for non-parametric density comparison.
result Existence of an asymmetric trade-off between labeled and unlabeled data samples.
In machine learning, Domain Adaptation (DA) arises when the distribution gen- erating the test (target) data differs from the one generating the learning (source) data. It is well known that DA is an hard task even under strong assumptions, among which the covariate-shift where the source and target distributions diver…