It was proved in 1998 by Ben-David and Litman that a concept space has a sample compression scheme of size d if and only if every finite subspace has a sample compression scheme of size d. In the compactness theorem, measurability of the hypotheses of the created sample compression scheme is not guaranteed; at the same…
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 “sample compressibility”
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.
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.
We obtain the first positive results for bounded sample compression in the agnostic regression setting with the loss, where . We construct a generic approximate sample compression scheme for real-valued function classes exhibiting exponential size in the fat-shattering dimension but independen…
New method compresses large sample data for faster discriminant analysis.
problem Large sample sizes in discriminant analysis increase computational burden.
method Proposes a new compression approach for reducing training samples.
result Significant computational gains and superior predictive ability compared to random sub-sampling.
We establish a tight characterization of the worst-case rates for the excess risk of agnostic learning with sample compression schemes and for uniform convergence for agnostic sample compression schemes. In particular, we find that the optimal rates of convergence for size- agnostic sample compression schemes are of…
Optimized sampling scheme for compressed sensing combining randomness and determinism.
problem Improving compressed sensing performance with deterministic sampling.
method Optimized sampling scheme combining random and deterministic selection of rows.
result Measurable improvements in image compressed sensing for generative and sparse priors.
Conventional approaches of sampling signals follow the celebrated theorem of Nyquist and Shannon. Compressive sampling, introduced by Donoho, Romberg and Tao, is a new paradigm that goes against the conventional methods in data acquisition and provides a way of recovering signals using fewer samples than the traditiona…
Investigates principles of generalization in list learning, refutes sample compression conjecture.
problem Determining applicability of classical principles in list PAC learning.
method Examines uniform convergence and sample compression in list PAC learning.
result Sample compression fails in list PAC learning, refutes conjecture.
This paper introduces ASCAI, a novel adaptive sampling methodology that can learn how to effectively compress Deep Neural Networks (DNNs) for accelerated inference on resource-constrained platforms. Modern DNN compression techniques comprise various hyperparameters that require per-layer customization to ensure high ac…
CTT compresses samples to test distributions near-linearly, outperforming existing methods.
problem Efficiently testing distributions with high power and near-linear runtime.
method Sample compression followed by permutation testing.
result CTT achieves near-linear runtime while maintaining high statistical power.
The paper provides theoretical guarantees for optimized sampling in compressed sensing, showing error vanishes with more measurements.
problem Theoretical and practical improvements in compressed sensing with optimized sampling schemes.
method Theoretical analysis and empirical experiments with optimized sampling schemes for subsampled unitary matrices.
result The error caused by measurement noise vanishes with an increasing number of measurements for optimized sampling schemes, assuming Gaussian noise.
Clapping reduces memory usage in distributed optimization by reusing data samples.
problem Significant communication overhead and impractical memory overhead in pipeline-parallel distributed optimization.
method Lazy sampling strategy to reuse data samples across steps, supporting convergence without unbiased gradient assumptions.
result Clapping achieves convergence in few-epoch or online training regimes without sample-size memory overhead.
BDC compresses both sample size and dimensionality of large datasets.
problem Large datasets in both sample size and dimensionality.
method Two-stage framework using Decoded MMD, Reconstruction MMD, and Encoded MMD.
result BDC achieves comparable or superior performance with lower cost and higher compression rates.
Compressed imitation learning uses simplicity priors for efficient expert behavior copying.
problem Efficiently learn expert behaviors with minimal data.
method Utilizes policy simplicity as a prior for sample-efficient imitation learning.
result Significantly higher scores achieved with limited expert demonstrations.
Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbationsstat.ML
New findings show learnable distributions remain learnable even with noisy or adversarial perturbations.
problem Learning from perturbed samples in high-dimensional spaces.
method Developed a perturbation-quantization framework to analyze additive noise and adversarial corruption models.
result Sample compressible families remain learnable even under noisy or adversarial perturbations.
Compress++ speeds up distribution compression to near-linear time.
problem Accurately summarize a probability distribution using a small number of points efficiently.
method Introduces Compress++, a meta-procedure to speed up any thinning algorithm.
result Achieves points with integration error in time and space.
New SVM margin bound improves generalization in machine learning.
problem Improving SVM margin bounds for better generalization.
method Stable sample compression schemes to derive new data-dependent generalization bounds.
result Proves a new optimal SVM margin bound with a log factor improvement.
Bayesian Attention Networks compress data by focusing on key training samples.
problem Lossless data compression for efficiency.
method Bayesian Attention Networks with attention factors and latent space.
result Efficient prediction using a few correlated training samples.
Paper improves MIRACLE for faster, more robust neural network compression.
problem Efficiently compressing neural networks while maintaining performance.
method Introduces Mean-KL parameterization to constrain compression cost.
result Mean-KL parameterization leads to twice as fast convergence and more robust compression.
DACE estimates covariance from compressed data, improving accuracy.
problem Estimating covariance from large, distributed data.
method Data-aware weighted sampling for unbiased estimation.
result DACE provides more accurate covariance estimation under compression.
CTE improves explanation estimation with less data and faster computation.
problem Inefficient and inaccurate explanation estimation in machine learning models.
method Distribution compression through kernel thinning to reduce sample size.
result CTE significantly improves accuracy and stability of explanation estimation.
This paper introduces a new measure to identify model redundancy in compressed CNNs.
problem Identifying remaining model redundancy in compressed CNNs.
method Developed a statistical formulation of CNNs and compressed CNNs via tensor decomposition, revealing discrepancies in sample complexity and model redundancy.
result Introduced a new model redundancy measure, the ratio, for compressed CNNs.
On-device machine learning (ML) has brought about the accessibility to a tremendous amount of data from the users while keeping their local data private instead of storing it in a central entity. However, for privacy guarantee, it is inevitable at each device to compensate for the quality of data or learning performanc…
We give an algorithmically efficient version of the learner-to-compression scheme conversion in Moran and Yehudayoff (2016). In extending this technique to real-valued hypotheses, we also obtain an efficient regression-to-bounded sample compression converter. To our knowledge, this is the first general compressed regre…
VQ-DRAW compresses images and generates realistic samples.
problem Learning compact discrete representations of images.
method Sequential discrete VAE with vector quantization.
result VQ-DRAW effectively compresses and generates images.
A CAE improves DNN's outlier and adversary defense.
problem Improving DNN's robustness against outliers and adversaries.
method Proposes a classification-autoencoder (CAE) that compresses samples into disjoint spaces and uses a decoder to classify and defend against adversaries.
result The CAE achieves state-of-the-art outlier recognition and near-lossless classification of adversaries.
Profile entropy measures learnability and compressibility of discrete distributions.
problem Understanding the learnability and compressibility of discrete distributions.
method Investigates profile entropy, showing its role in estimation, inference, and compression.
result Profile entropy is a fundamental measure unifying estimation, inference, and compression.
The standard approach to compressive sampling considers recovering an unknown deterministic signal with certain known structure, and designing the sub-sampling pattern and recovery algorithm based on the known structure. This approach requires looking for a good representation that reveals the signal structure, and sol…
New method optimizes MRI sampling patterns for faster scans.
problem Accelerate MRI scans without sacrificing image quality.
method Joint learning of adaptive sampling patterns and model-based recovery.
result Improved MR image quality compared to other methods.
Paper proposes efficient GCN learning method for limited data.
problem Learning GCNs from data with extremely limited annotations.
method Adaptive sampling strategy and model compression.
result Cut down annotation requirement by 90% and compress parameters 6x.
Paper proposes ADC framework to reduce ViT SL training communication overhead.
problem Reducing communication overhead in ViT SL training.
method Two parallel compression strategies: class-agnostic merging and token discarding.
result Significantly reduces communication overhead without sacrificing accuracy.
We propose and study the problem of distribution-preserving lossy compression. Motivated by recent advances in extreme image compression which allow to maintain artifact-free reconstructions even at very low bitrates, we propose to optimize the rate-distortion tradeoff under the constraint that the reconstructed sample…
Posterior sampling estimator achieves near-optimal recovery guarantees for signals from any prior distribution.
problem Characterizing measurement complexity for signals from any prior distribution, including the entire space.
method Characterization of measurement complexity using posterior sampling estimator for Gaussian measurements and any prior distribution.
result Posterior sampling estimator achieves near-optimal recovery guarantees for signals from any prior distribution, robust to model mismatch.
This paper studies the problem of estimating the covariance of a collection of vectors using only highly compressed measurements of each vector. An estimator based on back-projections of these compressive samples is proposed and analyzed. A distribution-free analysis shows that by observing just a single linear measure…
We introduce and study the problem of Online Continual Compression, where one attempts to simultaneously learn to compress and store a representative dataset from a non i.i.d data stream, while only observing each sample once. A naive application of auto-encoders in this setting encounters a major challenge: representa…
Data-independent pruning method reduces neural network size with accuracy guarantees.
problem Limited computational and memory resources for neural networks.
method Structured pruning using coresets.
result First efficient algorithm with worst-case guarantees on compression and accuracy.
We initiate the rigorous study of classification in quasi-metric spaces. These are point sets endowed with a distance function that is non-negative and also satisfies the triangle inequality, but is asymmetric. We develop and refine a learning algorithm for quasi-metrics based on sample compression and nearest neighbor…
Private distribution learning with public data, leveraging sample compression schemes.
problem Private distribution learning with public and private samples under differential privacy constraints.
method Connection to sample compression schemes and list learning.
result At least d public samples are necessary for private learnability of Gaussians in R^d.
RFX accelerates and compresses Random Forests for large datasets.
problem Memory bottleneck in proximity matrices limits Random Forest analysis.
method QLORA compression, CPU TriBlock storage, GPU batch sizing, 3D MDS visualization.
result Proximity-based Random Forest analysis on larger datasets is feasible.
Model-based compression is an effective, facilitating, and expanded model of neural network models with limited computing and low power. However, conventional models of compression techniques utilize crafted features [2,3,12] and explore specialized areas for exploration and design of large spaces in terms of size, spe…
Reduces policy space complexity for reinforcement learning.
problem Efficiency in exploring vast policy spaces in reinforcement learning.
method Uses Rényi divergence and norm to determine sample size for accurate policy approximation.
result Established error bounds for sample size requirements in model-based and model-free settings.
Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Boundscs.LG
We present an efficient coresets-based neural network compression algorithm that sparsifies the parameters of a trained fully-connected neural network in a manner that provably approximates the network's output. Our approach is based on an importance sampling scheme that judiciously defines a sampling distribution over…
Algorithm estimates principal eigenvector with adaptive sensing, improving over non-adaptive methods.
problem Estimating principal eigenvector with limited scalar measurements.
method Compressed variant of Oja's algorithm using two adaptive measurements per sample.
result Convergence rate of after iterations, matching information-theoretic lower bound.
A new method for compressive classification using bridge regression.
problem Efficient pattern classification with compact representation.
method Proposed a deterministic bridge regression solution for compressive classification.
result Validation of the proposed solution through numerical studies on simulated and real-world data.
The goal of standard 1-bit compressive sensing is to accurately recover an unknown sparse vector from binary-valued measurements, each indicating the sign of a linear function of the vector. Motivated by recent advances in compressive sensing with generative models, where a generative modeling assumption replaces the u…
Improved sampling strategy reduces Fourier measurements for neural network signals.
problem Efficiently sampling signals from neural networks with random Fourier matrices.
method Model-adapted sampling strategy with improved sample complexity.
result Reduced sample complexity from O(kdnα∞²) to O(kdα²₂) measurements.
The Sample Compression Conjecture of Littlestone & Warmuth has remained unsolved for over two decades. This paper presents a systematic geometric investigation of the compression of finite maximum concept classes. Simple arrangements of hyperplanes in Hyperbolic space, and Piecewise-Linear hyperplane arrangements, are …