Sampling Theorems for Learning from Incomplete Measurements

• URL: http://arxiv.org/abs/2201.12151v2
• Date: Mon, 31 Jan 2022 09:31:11 GMT
• Title: Sampling Theorems for Learning from Incomplete Measurements
• Authors: Juli\'an Tachella, Dongdong Chen and Mike Davies
• Abstract summary: In many real-world settings, only incomplete measurement data are available which can pose a problem for learning. We show that generically unsupervised learning is possible if each operator obtains at least $m>k+n/G$ measurements. Our results have implications in a wide range of practical algorithms, from low-rank matrix recovery to deep neural networks.
• Score: 11.54982866872911
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many real-world settings, only incomplete measurement data are available which can pose a problem for learning. Unsupervised learning of the signal model using a fixed incomplete measurement process is impossible in general, as there is no information in the nullspace of the measurement operator. This limitation can be overcome by using measurements from multiple operators. While this idea has been successfully applied in various applications, a precise characterization of the conditions for learning is still lacking. In this paper, we fill this gap by presenting necessary and sufficient conditions for learning the signal model which indicate the interplay between the number of distinct measurement operators $G$, the number of measurements per operator $m$, the dimension of the model $k$ and the dimension of the signals $n$. In particular, we show that generically unsupervised learning is possible if each operator obtains at least $m>k+n/G$ measurements. Our results are agnostic of the learning algorithm and have implications in a wide range of practical algorithms, from low-rank matrix recovery to deep neural networks.

Related papers

• Probably Approximately Precision and Recall Learning [62.912015491907994]
  Precision and Recall are foundational metrics in machine learning. One-sided feedback--where only positive examples are observed during training--is inherent in many practical problems. We introduce a PAC learning framework where each hypothesis is represented by a graph, with edges indicating positive interactions.
  arXiv  Detail & Related papers  (2024-11-20T04:21:07Z)
• MUSE: Machine Unlearning Six-Way Evaluation for Language Models [109.76505405962783]
  Language models (LMs) are trained on vast amounts of text data, which may include private and copyrighted content. We propose MUSE, a comprehensive machine unlearning evaluation benchmark. We benchmark how effectively eight popular unlearning algorithms can unlearn Harry Potter books and news articles.
  arXiv  Detail & Related papers  (2024-07-08T23:47:29Z)
• Self-Supervised Scalable Deep Compressed Sensing [24.854496459622787]
  Compressed sensing is a promising tool for reducing sampling costs. Current deep neural network (NN)-based CS methods face the challenges of collecting labeled measurement-ground truth (GT) data. This paper proposes a novel $mathbfS$elf-supervised s$mathbfC$alable deep CS method.
  arXiv  Detail & Related papers  (2023-08-26T06:03:06Z)
• Multi-Dimensional Ability Diagnosis for Machine Learning Algorithms [88.93372675846123]
  We propose a task-agnostic evaluation framework Camilla for evaluating machine learning algorithms. We use cognitive diagnosis assumptions and neural networks to learn the complex interactions among algorithms, samples and the skills of each sample. In our experiments, Camilla outperforms state-of-the-art baselines on the metric reliability, rank consistency and rank stability.
  arXiv  Detail & Related papers  (2023-07-14T03:15:56Z)
• High-dimensional Measurement Error Models for Lipschitz Loss [2.6415509201394283]
  We develop high-dimensional measurement error models for a class of Lipschitz loss functions. Our estimator is designed to minimize the $L_1$ norm among all estimators belonging to suitable feasible sets. We derive theoretical guarantees in terms of finite sample statistical error bounds and sign consistency, even when the dimensionality increases exponentially with the sample size.
  arXiv  Detail & Related papers  (2022-10-26T20:06:05Z)
• Sampling Theorems for Unsupervised Learning in Linear Inverse Problems [11.54982866872911]
  This paper presents necessary and sufficient sampling conditions for learning the signal model from partial measurements. As our results are agnostic of the learning algorithm, they shed light into the fundamental limitations of learning from incomplete data.
  arXiv  Detail & Related papers  (2022-03-23T16:17:22Z)
• Provable Lifelong Learning of Representations [21.440845049501778]
  We propose a provable lifelong learning algorithm that maintains and refines the internal feature representation. We prove that for any desired accuracy on all tasks, the dimension of the representation remains close to that of the underlying representation.
  arXiv  Detail & Related papers  (2021-10-27T00:41:23Z)
• Sample Efficient Linear Meta-Learning by Alternating Minimization [74.40553081646995]
  We study a simple alternating minimization method (MLLAM) which alternately learns the low-dimensional subspace and the regressors. We show that for a constant subspace dimension MLLAM obtains nearly-optimal estimation error, despite requiring only $Omega(log d)$ samples per task. We propose a novel task subset selection scheme that ensures the same strong statistical guarantee as MLLAM.
  arXiv  Detail & Related papers  (2021-05-18T06:46:48Z)
• A Theoretical-Empirical Approach to Estimating Sample Complexity of DNNs [11.152761263415046]
  This paper focuses on understanding how the generalization error scales with the amount of the training data for deep neural networks (DNNs) We derive estimates of the generalization error that hold for deep networks and do not rely on unattainable capacity measures.
  arXiv  Detail & Related papers  (2021-05-05T05:14:08Z)
• Neural Complexity Measures [96.06344259626127]
  We propose Neural Complexity (NC), a meta-learning framework for predicting generalization. Our model learns a scalar complexity measure through interactions with many heterogeneous tasks in a data-driven way.
  arXiv  Detail & Related papers  (2020-08-07T02:12:10Z)
• The Generalized Lasso with Nonlinear Observations and Generative Priors [63.541900026673055]
  We make the assumption of sub-Gaussian measurements, which is satisfied by a wide range of measurement models. We show that our result can be extended to the uniform recovery guarantee under the assumption of a so-called local embedding property.
  arXiv  Detail & Related papers  (2020-06-22T16:43:35Z)

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.