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…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “VC learning”
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.
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 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 with finite VC…
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.
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.
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.
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.
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…
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…
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.
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…
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 …
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.
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 VC-dimension of a set system is a way to capture its complexity and has been a key parameter studied extensively in machine learning and geometry communities. In this paper, we resolve two longstanding open problems on bounding the VC-dimension of two fundamental set systems: -fold unions/intersections of half-s…
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.
AttS2S-VC: Sequence-to-Sequence Voice Conversion with Attention and Context Preservation Mechanismseess.AS
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…
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.
VC dimension of ellipsoidsmath.CO
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…
Automated video conferencing system improves user experience with ASD and VC.
problem Improve remote video conferencing experience through automated speaker detection and virtual cinematography.
method Uses 4K wide-FOV camera, depth camera, and microphone array to extract features and train machine learning models for ASD and VC.
result System performs within 0.3 MOS of an expert cinematographer, as rated by users.
Non-parallel multi-domain voice conversion (VC) is a technique for learning mappings among multiple domains without relying on parallel data. This is important but challenging owing to the requirement of learning multiple mappings and the non-availability of explicit supervision. Recently, StarGAN-VC has garnered atten…
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.
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…
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…
Algorithm learns from both labeled and arbitrary test examples, giving guarantees for bounded VC dimension classes.
problem Learning from arbitrary test examples, not just perturbations.
method Selective transductive learning algorithm that outputs abstaining predictions.
result Nontrivial guarantees for bounded VC dimension classes with arbitrary train and test distributions.
New method reduces sample complexity for robust learning.
problem Developing simple, sample-efficient learning algorithms for robust classification.
method Tolerant empirical risk minimization (RERM) for robust learning.
result Tolerant RERM requires only O(VC(H)dlog(D/γδ)/ε^2) samples for robustness regions of diameter D.
In response to a 1997 problem of M. Vidyasagar, we state a criterion for PAC learnability of a concept class 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…
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.
The recently proposed Minimal Complexity Machine (MCM) finds a hyperplane classifier by minimizing an exact bound on the Vapnik-Chervonenkis (VC) dimension. The VC dimension measures the capacity of a learning machine, and a smaller VC dimension leads to improved generalization. On many benchmark datasets, the MCM gene…
The Vapnik-Chervonenkis (VC) dimension of a collection of subsets of a set is an important combinatorial concept in settings such as discrete geometry and machine learning. In this paper we prove that the VC dimension of the family of -dimensional cubes in is .
Convolutional neural networks (CNNs) are one of the driving forces for the advancement of computer vision. Despite their promising performances on many tasks, CNNs still face major obstacles on the road to achieving ideal machine intelligence. One is that CNNs are complex and hard to interpret. Another is that standard…
We explore in some detail the notion of algorithmic stability as a viable framework for analyzing the generalization error of learning algorithms. We introduce the new notion of training stability of a learning algorithm and show that, in a general setting, it is sufficient for good bounds on generalization error. In t…
Reduces multiclass and regression compression schemes to binary ones.
problem Developing efficient learning algorithms for multiclass and regression problems.
method Reduces sample compression schemes for binary classes to multiclass and regression settings.
result Establishes new compression schemes for multiclass and regression problems.
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 determines VC dimension.
VPFD uses vocoder features for adversarial training in VC.
problem Adversarial training on waveform data is time-consuming and memory-intensive.
method VPFD employs vocoder features for adversarial training.
result VPFD achieves VC performance comparable to waveform discriminators with reduced training time and memory.
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…
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.
New findings on null measurability in symmetrization interface of VC learning.
problem Null measurability issues in symmetrization interface of VC learning.
method Formalized in Lean 4, using Choquet capacitability and patching properties.
result Null-measurable bad event not Borel measurable, separating regularity levels.
Recently, voice conversion (VC) without parallel data has been successfully adapted to multi-target scenario in which a single model is trained to convert the input voice to many different speakers. However, such model suffers from the limitation that it can only convert the voice to the speakers in the training data, …
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. …
WL meet VCcs.LG
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.
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.
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.
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.
Adversarial attacks during the testing phase of neural networks pose a challenge for the deployment of neural networks in security critical settings. These attacks can be performed by adding noise that is imperceptible to humans on top of the original data. By doing so, an attacker can create an adversarial sample, whi…
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.