A unified framework for learning with nonlinear model classes from
  arbitrary linear samples
Ben Adcock Juan M. Cardenas Nick Dexter
This work considers the fundamental problem of learning an unknown object
from training data using a given model class. We introduce a unified framework
that allows for objects in arbitrary Hilbert spaces, general types of (random)
linear measurements as training data and general types of nonlinear model
classes. We establish a series of learning guarantees for this framework. These
guarantees provide explicit relations between the amount of training data and
properties of the model class to ensure near-best generalization bounds. In
doing so, we also introduce and develop the key notion of the variation of a
model class with respect to a distribution of sampling operators. To exhibit
the versatility of this framework, we show that it can accommodate many
different types of well-known problems of interest. We present examples such as
matrix sketching by random sampling, compressed sensing with isotropic vectors,
active learning in regression and compressed sensing with generative models. In
all cases, we show how known results become straightforward corollaries of our
general learning guarantees. For compressed sensing with generative models, we
also present a number of generalizations and improvements of recent results. In
summary, our work not only introduces a unified way to study learning unknown
objects from general types of data, but also establishes a series of general
theoretical guarantees which consolidate and improve various known results.