Agnostic Sample Compression Schemes for Regression

• URL: http://arxiv.org/abs/1810.01864v2
• Date: Sat, 3 Feb 2024 21:49:19 GMT
• Title: Agnostic Sample Compression Schemes for Regression
• Abstract summary: We show that for every other $ell_p$ loss, $pin (1,infty)$, there does not exist an exact compression scheme of bounded size. For $ell$ loss, does every function class admit an approximate compression scheme of size in the fat-shattering dimension?
• Score: 30.539063844697772
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We obtain the first positive results for bounded sample compression in the agnostic regression setting with the $\ell_p$ loss, where $p\in [1,\infty]$. We construct a generic approximate sample compression scheme for real-valued function classes exhibiting exponential size in the fat-shattering dimension but independent of the sample size. Notably, for linear regression, an approximate compression of size linear in the dimension is constructed. Moreover, for $\ell_1$ and $\ell_\infty$ losses, we can even exhibit an efficient exact sample compression scheme of size linear in the dimension. We further show that for every other $\ell_p$ loss, $p\in (1,\infty)$, there does not exist an exact agnostic compression scheme of bounded size. This refines and generalizes a negative result of David, Moran, and Yehudayoff for the $\ell_2$ loss. We close by posing general open questions: for agnostic regression with $\ell_1$ loss, does every function class admits an exact compression scheme of size equal to its pseudo-dimension? For the $\ell_2$ loss, does every function class admit an approximate compression scheme of polynomial size in the fat-shattering dimension? These questions generalize Warmuth's classic sample compression conjecture for realizable-case classification.

Related papers

• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale [54.65053906803857]
  We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability.<n>Our main result establishes a scale-sensitive generalization of the fundamental theorem of PAC learning.<n>We also highlight several open questions on quantitative sample complexity and evaluability.
  arXiv  Detail & Related papers  (2026-05-13T15:41:30Z)
• Sample Compression Scheme Reductions [17.389446817000945]
  We present novel reductions from sample compression schemes in multiclass classification, regression, and adversarially robust learning settings. We establish similar results for adversarially robust learning and also provide an example of a concept class that is robustly learnable but has no bounded-size compression scheme.
  arXiv  Detail & Related papers  (2024-10-16T20:14:02Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
  Existing theories on deep nonparametric regression have shown that when the input data lie on a low-dimensional manifold, deep neural networks can adapt to intrinsic data structures. This paper introduces a relaxed assumption that input data are concentrated around a subset of $mathbbRd$ denoted by $mathcalS$, and the intrinsic dimension $mathcalS$ can be characterized by a new complexity notation -- effective Minkowski dimension.
  arXiv  Detail & Related papers  (2023-06-26T17:13:31Z)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  We study oblivious sketching for $k$-sparse linear regression under various loss functions such as an $ell_p$ norm, or from a broad class of hinge-like loss functions. We show that for sparse $ell$vareps regression, there is an oblivious distribution over sketches with $Theta(klog(d/k)/varepsilon2)$ rows, which is tight up to a constant factor. We also show that sketching $O(mu2 klog(mu n d/varepsilon)/var
  arXiv  Detail & Related papers  (2023-04-05T07:24:19Z)
• The Geometry of Mixability [8.873449722727026]
  We provide a simple geometric characterization of mixability for the binary and multi-class cases. Our approach provides a way to treat some concepts concerning loss functions in a ''coordinate-free'' manner.
  arXiv  Detail & Related papers  (2023-02-23T10:25:38Z)
• A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension [6.522952386973185]
  This paper presents a construction of a proper and stable labelled sample compression scheme of size $O(VCD2)$ for any finite concept class.
  arXiv  Detail & Related papers  (2022-12-24T01:56:02Z)
• Private Isotonic Regression [54.32252900997422]
  We consider the problem of isotonic regression over a partially ordered set (poset) $mathcalX$ and for any Lipschitz loss function. We obtain a pure-DP algorithm that has an expected excess empirical risk of roughly $mathrmwidth(mathcalX) cdot log|mathcalX| / n$, where $mathrmwidth(mathcalX)$ is the width of the poset. We show that the bounds above are essentially the best that can be
  arXiv  Detail & Related papers  (2022-10-27T05:08:07Z)
• Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes [16.684376456880642]
  We show that all classes of VC dimension $d$ admit unlabelled compression schemes of size $O(d)$. We also prove that all intersection-closed classes with VC dimension $d$ admit unlabelled compression schemes of size at most $11d$.
  arXiv  Detail & Related papers  (2022-10-11T13:54:41Z)
• Sample compression schemes for balls in graphs [0.049932093784950796]
  One of the open problems in machine learning is whether any set-family of VC-dimension $d$ admits a sample compression scheme of size $O(d)$. In this paper, we study this problem for balls in graphs. For balls of arbitrary radius $r$, we design proper labeled sample compression schemes of size $2$ for trees, of size $3$ for cycles, of size $4$ for interval graphs, of size $6$ for trees of cycles, and of size $22$ for cube-free median graphs.
  arXiv  Detail & Related papers  (2022-06-27T12:39:36Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  We study active sampling algorithms for linear regression, which aim to query only a small number of entries of a target vector. We show that this dependence on $d$ is optimal, up to logarithmic factors. We also provide the first total sensitivity upper bound $O(dmax1,p/2log2 n)$ for loss functions with at most degree $p$ growth.
  arXiv  Detail & Related papers  (2021-11-09T00:20:01Z)
• Learning Scalable $\ell_\infty$-constrained Near-lossless Image Compression via Joint Lossy Image and Residual Compression [118.89112502350177]
  We propose a novel framework for learning $ell_infty$-constrained near-lossless image compression. We derive the probability model of the quantized residual by quantizing the learned probability model of the original residual.
  arXiv  Detail & Related papers  (2021-03-31T11:53:36Z)
• On Biased Compression for Distributed Learning [55.89300593805943]
  We show for the first time that biased compressors can lead to linear convergence rates both in the single node and distributed settings. We propose several new biased compressors with promising theoretical guarantees and practical performance.
  arXiv  Detail & Related papers  (2020-02-27T19:52:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.