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.
169,291 papers · 148 categories
Trend · papers per month
48 results for “compressive sampling”
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.
New bounds found for agnostic learning with sample compression schemes.
problem Finding optimal rates of convergence for agnostic learning.
method Established tight characterization of worst-case rates for agnostic learning with sample compression schemes.
result Optimal rates of convergence for size- agnostic sample compression schemes are .
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.
Positive results for agnostic regression with various losses.
problem Agnostic regression with bounded sample compression.
method Generic and efficient sample compression schemes for real-valued functions.
result Exact and approximate compression schemes for specific losses.
Adaptive sampling method optimizes DNN compression for resource-constrained platforms.
problem Efficiently compressing DNNs for resource-constrained platforms with high accuracy.
method Adaptive sampling using genetic algorithm-inspired operations to optimize hyperparameters.
result Adaptive sampling outperforms rule-based and reinforcement learning methods in compression rate and accuracy.
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.
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.
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.
Study of classification in asymmetric quasi-metric spaces.
problem Classification in asymmetric quasi-metric spaces.
method Sample compression and nearest neighbor algorithm.
result Algorithm has favorable statistical properties.
Efficient algorithm for converting regression to compressed form.
problem Real-valued regression learning and compression.
method Extension of Moran and Yehudayoff's scheme to real-valued hypotheses.
result First general compressed regression result with uniform approximate reconstruction.
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.
Proposes a framework for private data augmentation in federated learning.
problem Privacy and performance issues in non-IID training datasets.
method Multi-hop federated augmentation with sample compression.
result Significantly improves privacy, transmission delay, and local training performance.
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.
Study 1-bit compressive sensing with generative models, improving recovery accuracy.
problem Accurately recover sparse vectors from binary measurements with generative models.
method Analyzes noiseless and noisy 1-bit measurements with i.i.d.~Gaussian and Lipschitz continuous generative priors, proving sample complexity bounds and stability properties.
result Proves sample complexity bounds and stability properties for 1-bit compressive sensing with generative models.
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.
Proposes lossy compression that preserves data distribution.
problem Distribution-preserving lossy compression of data.
method Optimizes rate-distortion tradeoff with distribution constraint.
result Smooth interpolation between generative model and perfect reconstruction.
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.
Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Boundscs.LG
Efficiently compress neural networks by discarding redundant parameters.
problem Compressing neural networks to reduce computational and storage costs.
method Data-dependent coresets using importance sampling and sensitivity analysis.
result Proves the accuracy and generalization bounds of the compressed network.
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.
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.
Adaptive Quantization Modules enable online continual compression of non-i.i.d data streams.
problem Learning to compress and store a dataset from a non-i.i.d data stream, only observing each sample once.
method Discrete auto-encoders and Adaptive Quantization Modules (AQM) to control compression ability.
result Significant gains on continual learning benchmarks with AQM replacing episodic memory.
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.
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…
This paper automates deep model compression using reinforcement learning.
problem Efficiently compressing deep neural networks without sacrificing accuracy.
method Reinforcement learning-based actor-critic structure for automated compression.
result 4-fold reduction in FLOP with 2.8% higher accuracy for VGG-16.
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.
New methods compress models without real data, reducing accuracy loss.
problem Compression requires real data, which is often unavailable or sensitive.
method Synthetic data generation from trained models for calibration and fine-tuning.
result Best method shows negligible accuracy loss compared to original training set.
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.
Efficiently recovers network accuracy with few samples.
problem Fine-tuning requires large training sets and time.
method Knowledge distillation from few samples to compressed networks.
result Recover accuracy in minutes with minimal data.
A new framework for efficient large-scale learning using sketching of moments.
problem Efficiently learning from large datasets with limited computational resources.
method Compressing the training data into a low-dimensional sketch and solving a nonlinear least squares problem.
result Sufficient sketch sizes to control the generalization error of the procedure.
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.
Distiller simplifies DNN compression research with a Python package.
problem Efficiently compressing deep neural networks.
method Open-source Python package with DNN compression algorithms.
result Facilitates new research and learning tasks in DNN compression.
New condition for big data recovery from sparse samples.
problem Accurate recovery of graph signals from limited data.
method Network Nullspace Property that combines network structure and sampling geometry.
result Efficient sampling strategies designed based on network topology.