Improved uniform convergence bound with fat-shattering dimension reduces sample complexity gap.
problem Gap between upper and lower bounds on sample complexity for fat-shattering dimension.
method Provided an improved uniform convergence bound.
result Closed the gap between existing upper and lower bounds on sample complexity.
Estimates fat-shattering dimension of aggregated function classes.
problem Understanding the complexity of aggregated function classes.
method Analyzes fat-shattering dimension of k-fold aggregations of real-valued function classes. result Provides upper and lower bounds on fat-shattering dimension for linear and affine function classes.
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.
Study robust regression learning under adversarial attacks.
problem Understanding which function classes are learnable in the presence of adversarial attacks.
method Introduced a novel agnostic sample compression scheme and used fat-shattering dimension to construct adversarially robust sample compression schemes.
result Finite fat-shattering dimension classes are learnable in both realizable and agnostic settings.
The study provides a sample complexity estimate for multi-category classifiers with bounded variation.
problem Controlling the deviation between empirical and generalization performances of multi-category classifiers.
method Using the empirical L1-norm covering number and fat-shattering dimension, the study derives a sample size estimate for classifiers of bounded variation.
result The sample size estimate is sufficient for the performances to be close with high probability, improving the dependency on the number of classes.
We obtain the first positive results for bounded sample compression in the agnostic regression setting with the ℓp loss, where p∈[1,∞]. We construct a generic approximate sample compression scheme for real-valued function classes exhibiting exponential size in the fat-shattering dimension but independen…
Characterizes statistical complexity of realizable regression in PAC and online learning.
problem Understanding the statistical complexity of realizable regression in both PAC and online learning settings.
method Introduces minimax instance optimal learners, novel and combinatorial dimensions to characterize learnability.
result Characterizes which classes of real-valued predictors are learnable and provides necessary conditions for learnability.
New algorithms achieve near-optimal cumulative loss in nonparametric online learning and games.
problem Fast rates of convergence in nonparametric online regression and classification.
method Randomized proper learning algorithms, hierarchical aggregation, multi-scale extension, stability proof.
result Achieved near-optimal cumulative loss bounds for real-valued and binary games.
New algorithm for learning functions with bounds on error and sample complexity.
problem Learning [0,1]-valued functions in a prediction model. method General-purpose algorithm with upper and lower bounds on expected error and sample complexity.
result Improved bounds on sample complexity and agnostic learning conditions.
General lower bounds on neural network approximation in L^p norm.
problem Fundamental limits of neural network expressivity.
method General lower bound proof on approximation in L^p norm, applied to feed-forward neural networks.
result Neural networks can't approximate certain functions as well as previously thought.
New algorithm learns regression models privately under growth condition.
problem Private learning of nonparametric regression models.
method Novel filtering procedure to output stable hypotheses for nonparametric function classes.
result Established first nonparametric private learnability guarantee for diverging fat shattering dimensions.
Characterizes the sample complexity of list regression tasks.
problem Understanding the sample complexity of list learning tasks in regression.
method Introducing two combinatorial dimensions: k-OIG dimension and k-fat-shattering dimension.
result These dimensions characterize realizable and agnostic k-list regression.
New findings on neural networks with non-negative weights and low training error.
problem Does a low training error imply a small outer norm for two-layer neural networks?
method Covering number argument and fat-shattering dimension analysis.
result For non-negative output weights, low training error guarantees a well-controlled outer norm.
Study shows how many domains are needed for generalization, using a new measure called domain shattering dimension.
problem How many domains are needed for domain generalization?
method Introduced a new combinatorial measure called the domain shattering dimension to model domain sample complexity.
result Established a tight quantitative relationship between domain shattering dimension and classic VC dimension.
Characterizes sample complexity for outcome indistinguishability in machine learning.
problem Outcome indistinguishability in machine learning, focusing on distinguishers and predictors.
method Sample complexity characterized by metric entropy of predictor and distinguisher classes, using dual Minkowski norms.
result Equivalence and tightness of sample complexity characterizations in distribution-specific and distribution-free settings.
This article deals with the generalization performance of margin multi-category classifiers, when minimal learnability hypotheses are made. In that context, the derivation of a guaranteed risk is based on the handling of capacity measures belonging to three main families: Rademacher/Gaussian complexities, metric entrop…
Let F be a family of Borel measurable functions on a complete separable metric space. The gap (or fat-shattering) dimension of F is a combinatorial quantity that measures the extent to which functions f in F can separate finite sets of points at a predefined resolution gamma > 0. We establish a connection between the g…
Framework for private, noise-tolerant, and efficient learning algorithms.
problem Private and efficient learning of large-margin halfspaces in noisy environments.
method Simple framework using differential privacy and noise tolerance conditions.
result Noise-tolerant and private PAC learners for large-margin halfspaces with sample complexity independent of dimension.
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.
Recent advances in large-margin classification of data residing in general metric spaces (rather than Hilbert spaces) enable classification under various natural metrics, such as string edit and earthmover distance. A general framework developed for this purpose by von Luxburg and Bousquet [JMLR, 2004] left open the qu…
In response to a 1997 problem of M. Vidyasagar, we state a criterion for PAC learnability of a concept class C under the family of all non-atomic (diffuse) measures on the domain Ω. The uniform Glivenko--Cantelli property with respect to non-atomic measures is no longer a necessary condition, and consisten…
Paper combines RL with policy regularization for inventory policies.
problem Optimizing inventory policies using RL and dynamic programming.
method Hybrid approach combining RL with policy regularization.
result Generalization guarantees for inventory policies using VC theory.
Positive definite kernels and their associated Reproducing Kernel Hilbert Spaces provide a mathematically compelling and practically competitive framework for learning from data. In this paper we take the approximation theory point of view to explore various aspects of smooth kernels related to their inferential proper…
New results show flat minima in neural networks suffer from high dimensionality.
problem Flat minima in neural networks generalize poorly in high dimensions.
method Theoretical analysis of two-layer ReLU networks with multivariate inputs.
result Flat minima lead to exponentially slower convergence in high dimensions.
Study online learning with set-valued feedback, showing differences between deterministic and randomized approaches.
problem Online learning with set-valued feedback, where labels are sets rather than single labels.
method Introduced new combinatorial dimensions (Set Littlestone and Measure Shattering) to characterize learnability.
result Characterized deterministic and randomized online learnability, and established bounds for various learning settings.
New algorithm reduces online learning error for unknown feature distributions.
problem Oracle-efficient hybrid online learning with unknown feature and label distributions.
method Computational efficient online predictor using ERM oracle for finite-VC and fat-shattering classes.
result Oracle-efficient sublinear regret bounds for hybrid online learning with unknown feature generation.
Quantum machine learning has received significant attention in recent years, and promising progress has been made in the development of quantum algorithms to speed up traditional machine learning tasks. In this work, however, we focus on investigating the information-theoretic upper bounds of sample complexity - how ma…
New protocol for online learning with partial feedback, extending classical methods.
problem Learning with partial feedback where only one acceptable label is observed per round.
method Introducing a collection version space to address the lack of direct extension of classical methods.
result Characterization of learnability in set-realizable regime using Partial-Feedback Littlestone dimension and Partial-Feedback Measure Shattering dimension.
New algorithm reduces prediction error in online learning without knowing base measure.
problem Smoothed online learning without knowledge of base measure.
method R-Cover algorithm based on recursive coverings.
result First algorithm to guarantee sublinear regret for agnostic smoothed online learning without prior knowledge of base measure.
We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L2 regularization: We introduce the margin-adapted dimension, which is a simple function of the second order statistics of the data distribution, and show distribution-specific upper and lower bounds on…
A long-standing obstacle to progress in deep learning is the problem of vanishing and exploding gradients. Although, the problem has largely been overcome via carefully constructed initializations and batch normalization, architectures incorporating skip-connections such as highway and resnets perform much better than …
The h-principle fails for prelegendrians in fat distributions of corank 2.
problem Investigating the h-principle for fat distributions of corank 2.
method Developed the theory of prelegendrians, including front projection and pseudoholomorphic curve invariants.
result Found an infinite family of non-prelegendrian isotopic tori in the standard fat distribution.
The Statistical Learning Theory (SLT) provides the foundation to ensure that a supervised algorithm generalizes the mapping f:X→Y given f is selected from its search space bias F. SLT depends on the Shattering coefficient function N(F,n) to upper bound the …
Study public-data assisted private stochastic optimization with labeled or unlabeled public data.
problem Limits and capability of public-data assisted differentially private (PA-DP) algorithms in stochastic convex optimization.
method Lower bounds for PA-DP mean estimation and novel methods for leveraging public data in private supervised learning.
result Achieved dimension independent rate for GLM with unlabeled public data, showing optimality.
The Statistical Learning Theory (SLT) provides the theoretical guarantees for supervised machine learning based on the Empirical Risk Minimization Principle (ERMP). Such principle defines an upper bound to ensure the uniform convergence of the empirical risk Remp(f), i.e., the error measured on a given data sample, to …
Graphs with fat minors have a limited large-scale structure.
problem Understanding the large-scale structure of graphs excluding certain minors.
method Introduced the concept of Baker-treewidth and used it to prove asymptotic dimension bounds.
result Every hereditary class of bounded-degree graphs excluding some graph as a fat minor has asymptotic dimension at most 2.
We consider a model of robust learning in an adversarial environment. The learner gets uncorrupted training data with access to possible corruptions that may be affected by the adversary during testing. The learner's goal is to build a robust classifier, which will be tested on future adversarial examples. The adversar…
New algorithm tackles multiclass transductive online learning with unbounded labels.
problem Characterizing optimal mistake bound for unbounded label spaces.
method Introducing new combinatorial dimensions (Level-constrained Littlestone and Branching dimensions) to characterize online learnability.
result Established trichotomy of possible minimax rates for unbounded label spaces: Θ(T), Θ(logT), or Θ(1). The paper explores how data geometry influences generalization in neural networks.
problem Understanding generalization in overparameterized neural networks.
method Theoretical exploration of overparametrized two-layer ReLU networks trained below the edge of stability.
result Generalization bounds adapt to the intrinsic dimension of data distributions and deteriorate as data concentrates towards the unit sphere.
Paper classifies fibers of fat Riemannian submersions with non-negative curvature.
problem Understanding fat bundles in Riemannian submersions.
method Structural analysis of fat Riemannian submersions with non-negative sectional curvature.
result Classification of fibers as symmetric spaces, isometric correspondence of foliations, rigidity of dual foliations.
The study constructs metrics with positive 2nd Ricci curvature on various manifolds.
problem Constructing metrics with positive 2nd Ricci curvature on closed manifolds.
method Generalization of the concept of fatness to ensure the existence of metrics with positive 2nd Ricci curvature on certain homogeneous bundles.
result Infinitely many examples of manifolds with positive 2nd Ricci curvature, including non-simply connected spaces.
Constructs fat, shellable 3-spheres with specific f-vectors.
problem Defines and constructs fat 3-spheres.
method Constructs strongly regular CW 3-spheres that are both shellable and dual shellable.
result Constructs arbitrarily fat, shellable and dual shellable 3-spheres with specific f-vectors. Paper introduces fat CW complexes including all closed manifolds.
problem No specific problem stated, focuses on introducing new CW complexes.
method Introduces a new smooth version of CW complexes called fat CW complexes.
result Fat CW complexes include all closed manifolds and have desirable properties.
Introduces fat Lie theory for Lie groupoids and algebroids.
problem Representation theory of Lie groupoids and algebroids.
method Introduces fat extensions and abstract 2-term representations up to homotopy (ruths). Establishes correspondences and equivalences.
result One-to-one correspondence between fat extensions and abstract 2-term representations up to homotopy.
New rigidity result for fat bundles with equal vertical curvatures.
problem Equalizing vertical curvatures in fat bundles with specific constraints.
method Rigidity result for fat Riemannian foliations with bounded holonomy and curvature constraint.
result Established a rigidity result for fat fiber bundles with compact structure groups.
The article proves the existence of horizontal immersions into fat distributions and contact structures.
problem Proving the existence of horizontal immersions in fat distributions and contact structures.
method Gromov's sheaf theoretic and analytic techniques of h-principle. result Existence of horizontal immersions of an arbitrary manifold into degree 2 fat distributions and quaternionic contact structures.
A classic problem in physics is the origin of fat tailed distributions generated by complex systems. We study the distributions of stock returns measured over different time lags τ. We find that destroying all correlations without changing the τ=1 d distribution, by shuffling the order of the daily returns, causes…
This work is devoted to new constructions of symplectically fat fiber bundles. The latter are constructed in two ways: using the Kirwan map and expressing the fatness condition in terms of the isotropy representation related to the G-structure over some homogeneous spaces.