This paper explains double descent using VC theory.
problem Understanding the generalization of overfitting neural networks.
method VC-theoretical analysis of double descent.
result Double descent can be explained by classical VC-generalization bounds.
Develops higher arity VC theory and characterizes PAC learning in product spaces.
problem Characterizing PAC learning in multi-dimensional product spaces.
method Introduces higher arity VC dimension, generalizes Haussler packing lemma, and develops hypergraph regularity lemma.
result Characterizes higher arity PAC learning in n-fold product spaces.
New neural network class reduces VC dimension, leading to better generalization.
problem VC theory struggles with explaining small generalization errors in overparametrized neural networks.
method Developed hyperplane arrangement neural networks (HANNs) and used sample compression analysis.
result HANNs can have significantly smaller VC dimension than the number of weights, yet remain highly expressive.
One of the earliest conjectures in computational learning theory-the Sample Compression conjecture-asserts that concept classes (equivalently set systems) admit compression schemes of size linear in their VC dimension. To-date this statement is known to be true for maximum classes---those that possess maximum cardinali…
The paper connects GNNs to VC dimension theory to study their generalization performance.
problem Understanding GNNs' ability to make meaningful predictions beyond the training set.
method Using Vapnik-Chervonenkis (VC) dimension theory in two settings: no upper bound on graph order and known upper bound.
result Tight connections between GNNs' bitlength, number of colors, and VC dimension in different settings.
Investigates the impact of finite VC dimension on neural network approximation and learning.
problem The influence of VC dimension on neural network approximation and learning from samples.
method Analysis of high-dimensional geometry and statistical learning theory, focusing on VC dimension.
result Finite VC dimension is beneficial for uniform convergence of empirical errors but not for approximation of functions from a probability distribution.
Study extends GNN VC dimension bounds to Pfaffian activation functions.
problem Bounding GNN VC dimension for new activation functions.
method Pfaffian function theory applied to GNNs with sigmoid and hyperbolic tangent activations.
result Bounds on GNN VC dimension for various architectures and graph properties.
VC dimensions of group CNNs are infinite for certain kernels and groups.
problem Estimating the generalization capacity of group convolutional neural networks.
method Identifying precise VC dimension estimates for simple sets of group CNNs.
result Two-parameter families of convolutional neural networks have an infinite VC dimension for infinite groups and certain kernels.
FastVoiceGrad speeds up VC to one step, matching or surpassing quality.
problem Slow inference in multi-step diffusion-based VC.
method Adversarial Conditional Diffusion Distillation (ACDD) for one-step diffusion.
result One-shot VC with superior or comparable performance to multi-step methods.
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.
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.
We will establish that the VC dimension of the class of d-dimensional ellipsoids is (d^2+3d)/2, and that maximum likelihood estimate with N-component d-dimensional Gaussian mixture models induces a geometric class having VC dimension at least N(d^2+3d)/2. Keywords: VC dimension; finite dimensional ellipsoid; Gaussian m…
Study on VC dimension of GCNNs with input resolution effects.
problem Understanding the generalization capabilities of GCNNs.
method Derived upper and lower bounds for VC dimension, analyzed factors affecting it.
result Extended previous results on VC dimension of GCNNs, providing insights into input resolution dependence.
Lower bounds on Bayes risk for realizable models derived using information theory.
problem Deriving lower bounds on Bayes risk for realizable machine learning models.
method Information-theoretic analysis using rate-distortion theory and mutual information.
result Lower bounds on Bayes risk for realizable models, matching known bounds up to logarithmic factors.
Paper extends learning theory to dependent data with uniform risk bounds.
problem Learning with dependent data sequences.
method Derives uniform risk bounds for dependent data using VC-dimension and Rademacher complexity.
result Standard classification risk bounds hold for dependent data, same as for independent data.
The paper explores learning from label proportions, showing differences in efficiency between LLP and PAC learning.
problem Learning from label proportions (LLP) in unlabeled data with given label proportions.
method Formal definition and computational complexity analysis of LLP learning.
result LLP learning is more restrictive than PAC learning for finite VC classes, and some classes are uncharacterizable.
We information-theoretically reformulate two measures of capacity from statistical learning theory: empirical VC-entropy and empirical Rademacher complexity. We show these capacity measures count the number of hypotheses about a dataset that a learning algorithm falsifies when it finds the classifier in its repertoire …
We show that the sets in a family with finite VC dimension can be uniformly approximated within a given error by a finite partition. Immediate corollaries include the fact that VC classes have finite bracketing numbers, satisfy uniform laws of averages under strong dependence, and exhibit uniform mixing. Our results ar…
Although voice conversion (VC) algorithms have achieved remarkable success along with the development of machine learning, superior performance is still difficult to achieve when using nonparallel data. In this paper, we propose using a cycle-consistent adversarial network (CycleGAN) for nonparallel data-based VC train…
Contradiction graphs reveal VC dimension threshold.
problem Determining VC dimension of concept classes.
method Study contradiction graphs of binary concept classes.
result Single contradiction graph Gm(H) determines VC dimension. New method learns robustly with less data, bridging theory and practice.
problem Adversarial robust learning with metric perturbation.
method Tolerant adversarial PAC-learning with perturb-and-smooth approach and compression-based algorithm.
result First PAC-type guarantees for popular adversarial learning techniques.
Graph neural networks generalize well under certain conditions, explained by learning theory.
problem Understanding why graph neural networks generalize well in transductive inference.
method Analysis of transductive Rademacher complexity to explain generalization properties of graph convolutional networks.
result Transductive Rademacher complexity can explain the generalization of graph convolutional networks for node classification in stochastic block models.
For any family of measurable sets in a probability space, we show that either (i) the family has infinite Vapnik-Chervonenkis (VC) dimension or (ii) for every epsilon > 0 there is a finite partition pi such the pi-boundary of each set has measure at most epsilon. Immediate corollaries include the fact that a family wit…
Vapnik-Chervonenkis (VC) dimension is a fundamental measure of the generalization capacity of learning algorithms. However, apart from a few special cases, it is hard or impossible to calculate analytically. Vapnik et al. [10] proposed a technique for estimating the VC dimension empirically. While their approach behave…
Most of the existing studies on voice conversion (VC) are conducted in acoustically matched conditions between source and target signal. However, the robustness of VC methods in presence of mismatch remains unknown. In this paper, we report a comparative analysis of different VC techniques under mismatched conditions. …
MaskCycleGAN-VC improves voice conversion without parallel data.
problem Limited ability to convert mel-spectrogram data without parallel data.
method Integrates a novel auxiliary task called filling in frames (FIF) to learn time-frequency structures.
result MaskCycleGAN-VC outperforms existing methods with similar model size.
CycleGAN-VC3 improves CycleGAN-VCs for mel-spectrogram conversion.
problem Ambiguity in CycleGAN-VC/VC2 effectiveness for mel-spectrogram conversion.
method Proposes CycleGAN-VC3 with time-frequency adaptive normalization (TFAN).
result CycleGAN-VC3 outperforms or matches CycleGAN-VC2 for mel-spectrogram conversion.
Model selection is difficult to analyse yet theoretically and empirically important, especially for high-dimensional data analysis. Recently the least absolute shrinkage and selection operator (Lasso) has been applied in the statistical and econometric literature. Consis- tency of Lasso has been established under vario…
This paper describes a method based on a sequence-to-sequence learning (Seq2Seq) with attention and context preservation mechanism for voice conversion (VC) tasks. Seq2Seq has been outstanding at numerous tasks involving sequence modeling such as speech synthesis and recognition, machine translation, and image captioni…
Improved multi-group learning with group-realizable concepts.
problem Enhancing multi-group learning efficiency.
method Empirical risk minimization over group-realizable concepts.
result Improved sample complexity in group-realizable settings.
We study the question of learning an adversarially robust predictor. We show that any hypothesis class H with finite VC dimension is robustly PAC learnable with an improper learning rule. The requirement of being improper is necessary as we exhibit examples of hypothesis classes H with finite VC…
A theory for approximating complex concepts with simple decision trees.
problem Approximating complex concepts with simple decision trees.
method Introducing interpretable approximations, studying binary concept approximation by decision trees.
result A trichotomy of cases for approximating a binary concept by decision trees based on a simple class.
Study uniform learnability of binary classification networks with communication.
problem Learning a network with communication between vertices from uniform ergodic Random Graph Process.
method Introduced structural Rademacher complexity and used martingale method and Marton's coupling.
result Uniform learnability as worst-case theoretical limits for binary classification problems.
FasterVoiceGrad speeds up VC by 6-7x with novel distillation.
problem Slow iterative sampling in diffusion-based VC models.
method Adversarial diffusion conversion distillation (ADCD) to create a faster one-step model.
result 6.6-6.9 and 1.8x faster on GPU and CPU, respectively.
Study on proper learning under relaxed worst-case robust loss for VC classes.
problem Proper adversarially robust PAC learning under relaxed worst-case robust loss.
method Introduced a family of robust loss relaxations and showed their effectiveness for proper learnability.
result VC classes are properly PAC learnable with sample complexity close to standard PAC learning setup.
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…
Non-parallel voice conversion (VC) is a technique for learning the mapping from source to target speech without relying on parallel data. This is an important task, but it has been challenging due to the disadvantages of the training conditions. Recently, CycleGAN-VC has provided a breakthrough and performed comparably…
Simulators enable learning with generalization guarantees in computationally bounded worlds.
problem Generalization in learning theory
method Simulatable processes
result Recovery of PAC learning guarantees with VC dimension
Adversarial robust learning improved for transductive setting.
problem Adversarial robust learning in transductive setting.
method Simple transductive learner for bounded VC dimension classes.
result Robust error rate linear in VC dimension, adaptive to perturbation complexity.
In Statistical Learning, the Vapnik-Chervonenkis (VC) dimension is an important combinatorial property of classifiers. To our knowledge, no theoretical results yet exist for the VC dimension of edited nearest-neighbour (1NN) classifiers with reference set of fixed size. Related theoretical results are scattered in the …
New insights into learning from distributional adversaries and private data.
problem Understanding minimal assumptions for learning and generalization under distributional constraints.
method Generalized smoothness as a characterization of learnability and privacy under distributional adversaries.
result Near complete characterization of families that admit learnability and privacy under distributional adversaries.
New bounds on learning from multiple distributions for VC classes.
problem Understanding the sample complexity of learning from multiple data distributions.
method Analyzing the gap between known upper and lower bounds for PAC-learnable classes.
result Recent progress on sample complexity for VC dimension d classes on k distributions.
Algorithm learns without knowing distribution, reducing error.
problem Sequential prediction with adversarial injections and abstentions.
method Boosting procedure of weak learners for general VC classes.
result Sublinear error guarantees for general VC classes.
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…
Study uses LLMs to optimize VC exit timing after IPO.
problem Optimal exit timing after IPO is crucial but not well studied.
method Uses LLMs to analyze financial data and market signals.
result LLMs can improve VC exit timing and generate better returns.
We consider solutions to the complex Trkalian equation,~$ \vec{\nabla} \times \vc = \vc ,$ where~$\vc$ is a 3 component vector function with each component in the complex field, and may be expressed in the form~$ \vc = e^{ig} \vec{\nabla} F, $ with~g real and~F complex. We find, there are precisely two classes of s…
Paper generalizes strategic classification framework and introduces SVC for PAC-learning.
problem Strategic manipulation of testing data to fool classifiers.
method Unified framework for strategic classification, strategic VC-dimension (SVC).
result Characterizes the learnability and computational tractability of linear classifiers.
The paper explores how to reduce classification tasks to optimization problems in Euclidean space.
problem Understanding the minimum dimension needed for reducing classification tasks to optimization problems.
method Developed a generalization of the Borsuk-Ulam Theorem to analyze the expressivity of reductions.
result The minimum Euclidean dimension required can be exponentially larger than the VC dimension, even for slightly non-trivial reductions.