# A Parameterized Theory of PAC Learning

Cornelius Brand1, Robert Ganian1, Kirill Simonov2

###### Abstract

Probably Approximately Correct (i.e., PAC) learning is a core concept of
sample complexity theory, and efficient PAC learnability is often seen as a
natural counterpart to the class $\mathsf{P}$ in classical computational
complexity. But while the nascent theory of parameterized complexity has
allowed us to push beyond the $\mathsf{P}$-$\mathsf{NP}$ “dichotomy” in
classical computational complexity and identify the exact boundaries of
tractability for numerous problems, there is no analogue in the domain of
sample complexity that could push beyond efficient PAC learnability.

As our core contribution, we fill this gap by developing a theory of
parameterized PAC learning which allows us to shed new light on several recent
PAC learning results that incorporated elements of parameterized complexity.
Within the theory, we identify not one but two notions of fixed-parameter
learnability that both form distinct counterparts to the class
$\mathsf{FPT}$—the core concept at the center of the parameterized complexity
paradigm—and develop the machinery required to exclude fixed-parameter
learnability. We then showcase the applications of this theory to identify
refined boundaries of tractability for CNF and DNF learning as well as for a
range of learning problems on graphs.

##  1 Introduction

While a number of different models for sample complexity have by now been
considered in the literature, the fundamental concept of Probably
Approximately Correct (i.e., PAC) learning (Valiant 1984) remains a core
pillar which can theoretically capture and explain the success of learning
algorithms in a broad range of contexts. Intuitively, in the classical proper
PAC setting we ask whether it is possible to identify (or “learn”) a
hypothesis from a specified hypothesis space after drawing a certain number of
labeled samples111Formal definitions are provided in the Preliminaries.
according to an unknown distribution. As the best case scenario, one would
wish to have an algorithm that can learn a hypothesis with arbitrarily high
precision and with arbitrarily high probability after spending at most
polynomial time and using at most polynomially-many samples. These are called
_efficient_ PAC-learning algorithms, and the class of learning problems
admitting such algorithms forms a natural counterpart to the class
$\mathsf{P}$ in the classical complexity theory of computational problems.

In spite of this parallel, our understanding of the sample complexity of
learning problems remains significantly behind the vast amounts of knowledge
we have by now gathered about the time complexity of computational problems.
Indeed, while understanding the distinction between $\mathsf{NP}$-hard and
polynomially tractable classes of instances for computational problems remains
an important research direction, over the past two decades focus has gradually
shifted towards a more fine-grained analysis of the boundaries of tractability
for such problems. In particular, _parameterized complexity_ (Cygan et al.
2015; Downey and Fellows 2013) has emerged as a prominent paradigm that yields
a much deeper understanding of the limits of tractability than classical
complexity theory, and today we see research exploring the parameterized
complexity of relevant problems appear in a broad range of venues spanning
almost all areas of computer science. The main idea behind the parameterized
paradigm is to investigate the complexity of problems not only with respect to
the input size $n$, but also based on a numerical parameter $k$ that captures
some property of the input; the central notion is then that of _fixed-
parameter tractability_ (FPT), which means that the problem of interest can be
solved in time $f(k)\cdot n^{\mathcal{O}(1)}$ for some computable function
$f$.

Given its ubiquitous applications, it is natural to ask whether (and how) the
principles of parameterized complexity analysis can also be used to expand our
understanding of the foundations of sample complexity beyond what may be
possible through the lens of efficient PAC-learnability. In fact, there
already are a handful of papers (Li and Liang 2018; Arvind, Köbler, and
Lindner 2009; Alekhnovich et al. 2008; Gärtner and Garriga 2007) that have
hinted at the potential of this novel field by identifying learning algorithms
that seem to act as intuitive counterparts to the fixed-parameter algorithms
emblematic of parameterized complexity. However, the theoretical foundations
of a general parameterized extension to the PAC-learning framework have yet to
be formalized and developed, stifling further development of this unique
bridge between the two research communities.

Contribution. As our first conceptual contribution, we lay down the
foundations of a general parameterized extension to the PAC-learning
framework. Crucially, when defining the analogue of fixed-parameter
tractability in the sample complexity setting, we show that there are two
natural definitions which need to be considered: a parameterized learning
problem is

  1. 1.

_$\mathrm{fpt}$ -time learnable_ if a suitable PAC hypothesis can be learned
from polynomially-many samples using a fixed-parameter algorithm, and

  2. 2.

_$\mathrm{fpt}$ -sample learnable_ if a suitable PAC hypothesis can be learned
using a fixed-parameter algorithm.

Essentially, in the latter case the total number of samples used need not be
polynomial, but of course remains upper-bounded by the (fixed-parameter)
running time of the algorithm. An important feature of the framework is that
parameters are allowed to depend not only on the sought-after concept (as was
considered in prior work (Arvind, Köbler, and Lindner 2009)), but also on
properties of the distribution. This can be seen as analogy to how one
utilizes parameters in the classical parameterized complexity paradigm: they
can capture the properties we require on the output (such as the size of a
solution), but also restrictions we place on the input (such as structural
parameters of an input graph).

The parameterized PAC-learning framework proposed in this paper also includes
a machinery that can be used to obtain lower bounds which exclude the
existence of FPT-time and $\mathrm{fpt}$-sample learning algorithms; this is
done by building a bridge to the well-studied $\mathsf{W}$-hierarchy in
parameterized complexity theory. Moreover, we provide the sample-complexity
analogues to the complexity class $\mathsf{XP}$; similarly as in the fixed-
parameter case, it is necessary to distinguish whether we restrict only the
running time or the number of samples.

After laying down the foundations, we turn our attention to two major problem
settings with the aim of illustrating how these notions can expand our
knowledge of sample complexity. First, we study the boundaries of learnability
for the fundamental problem of learning DNF and CNF formulas, which are among
the most classical questions in PAC learning theory.

On one hand, $k$-CNF and $k$-DNF formulas are known to be efficiently PAC-
learnable for every fixed $k$, albeit the running time of the known algorithms
have the form $\mathcal{O}(n^{k})$. As our first result, we show that while
both of these learning problems are $\mathrm{xp}$-time learnable, under well-
established complexity assumptions they are neither $\mathrm{fpt}$-time nor
$\mathrm{fpt}$-sample learnable when parameterized by $k$. On the other hand,
for each $p>1$ it is well-known that $p$-term DNF and $p$-clause CNF formulas
are not efficiently PAC learnable (Pitt and Valiant 1988; Alekhnovich et al.
2008) unless $\mathsf{P}=\mathsf{NP}$, and here we ask the question whether a
suitable parameterization can be used to overcome this barrier to
tractability. We show that while learning $p$-term DNF and $p$-clause CNF
formulas remains intractable under the most natural parameterizations of the
target concept, one can learn such formulas by an $\mathrm{fpt}$-time
algorithm by exploiting a parameterization of the distribution. In particular,
it is not difficult to observe that the learning problem is tractable when
each sample contains at most one variable set to True, and we show that it is
possible to lift this to a non-trivial $\mathrm{fpt}$-time learning algorithm
when parameterized by the number of variables which are exempt from this
restriction (i.e., can always contain any value).

While CNF and DNF learning is fundamental for PAC learning, in the last part
of our study we turn towards a setting which has been extensively studied in
both the sample complexity and parameterized complexity paradigms: graph
problems. Indeed, fundamental graph problems such as vertex cover and subgraph
detection served as a testbed for the development of parameterized complexity
theory, and are also heavily studied in machine learning and sample complexity
contexts (Nguyen and Maehara 2020; Abasi and Bshouty 2019; Abasi, Bshouty, and
Mazzawi 2018; Damaschke and Muhammad 2010; Alon and Asodi 2005; Choi and Kim
2010). Here, we obtain a meta-theorem showing that a large class of graph
problems is $\mathrm{fpt}$-time learnable: in particular, we provide an
$\mathrm{fpt}$-time learning algorithm for finding a vertex deletion set to
$\mathcal{H}$, where $\mathcal{H}$ is an arbitrary graph class that can be
characterized by a finite class of forbidden induced subgraphs. As one special
case, this captures the problem of learning hidden vertex covers (Damaschke
and Muhammad 2010). We conclude by excluding a similar result for classes
$\mathcal{H}$ characterized by forbidden minors—hence, for instance hidden
feedback vertex sets are neither $\mathrm{fpt}$-time nor $\mathrm{fpt}$-sample
learnable when parameterized by their size.

##  2 Preliminaries

As basic notation and terminology, we set
$\\{0,1\\}^{\ast}=\bigcup_{m\in\mathbb{N}}\\{0,1\\}^{m}$. A _distribution_ on
$\\{0,1\\}^{n}$ is a mapping $\mathcal{D}:\\{0,1\\}^{n}\rightarrow[0,1]$ such
that $\sum_{x\in\\{0,1\\}^{n}}\mathcal{D}(x)=1$, and the _support_ of
$\mathcal{D}$ is the set
$\operatorname{supp}\mathcal{D}=\\{x\mid\mathcal{D}(x)>0\\}$. We first recall
the basics of both PAC-learning and parameterized complexity theory.

### PAC-Learning

Let us begin by formalizing the classical learning theory considered in this
article (Valiant 1984; Mohri, Rostamizadeh, and Talwalkar 2012).

######  Definition 2.1.

A _concept_ is an arbitrary Boolean function
$c:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$. An assignment $x\in\\{0,1\\}^{n}$ is
called a _positive sample_ for $c$ if $c(x)=1$, and a _negative sample_
otherwise. A _concept class_ $\mathcal{C}$ is a set of concepts. For every
$m\in\mathbb{N}$, we write $\mathcal{C}_{m}=\mathcal{C}\cap\mathcal{B}_{m}$,
where $\mathcal{B}_{m}$ is the set of all $m$-ary Boolean functions.

######  Definition 2.2.

Let $\mathcal{C}$ be a concept class. A surjective mapping
$\rho:\\{0,1\\}^{\ast}\rightarrow\mathcal{C}$ is called a _representation
scheme_ of $\mathcal{C}$. We call each $r$ with $\rho(r)=c$ a _representation_
of concept $c$.

In plain terms, while concepts may be arbitrary functions, representations are
what make these “tangible” and are what we typically expect as the output of
learning algorithms.

######  Definition 2.3.

A _learning problem_ is a pair $(\mathcal{C},\rho)$, where $\mathcal{C}$ is a
concept class and $\rho$ is a representation scheme for $\mathcal{C}$.

######  Definition 2.4.

A _learning algorithm_ for a learning problem $(\mathcal{C},\rho)$ is a
randomized algorithm such that:

  1. 1.

It obtains the values $n,\varepsilon,\delta$ as inputs, where $n$ is an
integer and $0<\varepsilon,\delta\leq 1$ are rational numbers.

  2. 2.

It has access to a hidden representation $r^{\ast}$ of some concept
$c^{\ast}=\rho(r^{\ast})$ and a hidden distribution $\mathcal{D}_{n}$ on
$\\{0,1\\}^{n}$ through an oracle that returns _labeled samples_
$(x,c^{\ast}(x))$, where $x\in\\{0,1\\}^{n}$ is drawn at random from
$\mathcal{D}_{n}$.

  3. 3.

The output of the algorithm is a representation of some concept, called its
_hypothesis_.

######  Remark 2.5.

Clearly, the algorithm can infer the value of $n$ from the samples that the
oracle returns. Still, $n$ is included in the input for the sake of being
explicit. We use $s=|r^{\ast}|$ to denote the size of the hidden
representation.

######  Definition 2.6.

Let $\mathcal{A}$ be a learning algorithm. Fix a hidden hypothesis $c^{\ast}$
and a distribution on $\\{0,1\\}^{n}$. Let $h$ be a hypothesis output by
$\mathcal{A}$ and $c=\rho(h)$ be the concept $h$ represents. We define

$\operatorname{err}_{h}=\mathbb{P}_{x\sim\mathcal{D}_{n}}(c(x)\neq
c^{\ast}(x))$

as the probability of the hypothesis and the hidden concept disagreeing on a
sample drawn from $\mathcal{D}_{n}$, the so-called _generalization error_ of
$h$ under $\mathcal{D}_{n}$.

The algorithm $\mathcal{A}$ is called _probably approximately correct (PAC)_
if it outputs a hypothesis $h$ such that
$\operatorname{err}_{h}\leq\varepsilon$ with probability at least $1-\delta.$

Usually, learning problems in this framework are regarded as tractable if they
are PAC-learnable within polynomial time bounds. More precisely, we say that a
learning problem $L$ is _efficiently_ PAC-learnable if there is a PAC
algorithm for $L$ that runs in time polynomial in $n,s,1/\varepsilon$ and
$1/\delta$.

### Parameterized Complexity

To extend the above concepts from learning theory to the parameterized
setting, we now introduce the parts of parameterized complexity theory that
will become important later. We follow the excellent exposition of the
textbook by Cygan et al. (2015) and define the following central notions:

######  Definition 2.7.

A _parameterized problem_ is a language
$L\subseteq\\{0,1\\}^{\ast}\times\mathbb{N}$. For a pair
$(x,k)\in\\{0,1\\}^{\ast}\times\mathbb{N}$, $k$ is called the _parameter_ of
the instance $(x,k)$. The encoding length of $(x,k)$ is called the _size_ of
the instance.

######  Remark 2.8.

The definition of parameterized decision problems can easily be extended to
search problems, where we are additionally required to output a witness in
case our algorithm outputs “yes.”

######  Definition 2.9.

A parameterized problem $L$ is _fixed-parameter tractable_ if there exists an
algorithm $\mathcal{A}$, a computable non-decreasing function
$f:\mathbb{N}\rightarrow\mathbb{N}$ and a polynomially bounded non-decreasing
function $p(\cdot,\cdot):\mathbb{N}^{2}\rightarrow\mathbb{N}$ such that
$\mathcal{A}$ correctly decides for an input $(x,k)$ whether or not $(x,k)\in
L$ holds in time $f(k)\cdot p(n,k)$. We denote the class of fixed-parameter
tractable problems by $\mathsf{FPT}$.

######  Remark 2.10.

While fixed-parameter tractability lies at the heart of parameterized
complexity theory, the class $\mathsf{XP}$ defined below captures a weaker
notion of tractability that is still desirable for parameterized problems
which are not believed to be in $\mathsf{FPT}$.

######  Definition 2.11.

A parameterized problem $L$ is in the complexity class $\mathsf{XP}$ if there
exists an algorithm $\mathcal{A}$, a computable non-decreasing function
$f:\mathbb{N}\rightarrow\mathbb{N}$ and a polynomially bounded non-decreasing
function $p(\cdot,\cdot):\mathbb{N}^{2}\rightarrow\mathbb{N}$ such that
$\mathcal{A}$ correctly decides for an input $(x,k)$ whether or not $(x,k)\in
L$ holds in time $p(n,k)^{f(k)}$.

######  Remark 2.12.

Less formally, $\mathsf{XP}$ is the class of problems that are solvable in
polynomial time for a constant parameter value. The difference to
$\mathsf{FPT}$ is that for $\mathsf{XP}$, we allow this polynomial (and in
particular, its degree) to depend on $k$, while it is fixed for all $k$ in the
definition of $\mathsf{FPT}$.

To prove our lower bounds, we will to recall the basics of parameterized
complexity theory, beginning with the usual notion for parameterized
reductions.

######  Definition 2.13.

Let $L,L^{\prime}$ be two parameterized problems. We say that an algorithm
$\mathcal{A}$ that takes an instance $(x,k)$ of $L$ and outputs an instance
$(x^{\prime},k^{\prime})$ of $L^{\prime}$ is a _parameterized reduction from
$L$ to $L^{\prime}$_ if

  1. 1.

$(x,k)\in L$ if and only if $(x^{\prime},k^{\prime})\in L^{\prime}$,

  2. 2.

$k^{\prime}\leq g(k)$ for some function $g:\mathbb{N}\rightarrow\mathbb{N}$,
and

  3. 3.

the running time of the algorithm is upper-bounded by $f(k)\cdot
n^{\mathcal{O}(1)}$ for some computable function
$f:\mathbb{N}\rightarrow\mathbb{N}$.

Using this definition, we can give an ad-hoc definition of the parameterized
complexity classes $\mathsf{W[1]}$ and $\mathsf{W[2]}$, which form rough
analogues to the usual class $\mathsf{NP}$. While we will only use
$\mathsf{W[2]}$ in this paper, we will give the definition for $\mathsf{W[1]}$
for completeness.

Let $k$-Clique be the problem of deciding, given a graph $G$ and a parameter
$k$, if $G$ has a clique of size at least $k$. Furthermore, we let $k$-Hitting
Set be the problem of deciding, given a pair $(U,\mathcal{F})$ and a parameter
$k$, where $U$ is some universe of the form $U=\\{1,\ldots,n\\}$ and
$\mathcal{F}$ is a set family $\\{F_{i}\\}_{i=1}^{m}$ over $U$, if there is a
set $H$ of size at most $k$ such that $F_{i}\cap H\neq\emptyset$ for all $i$.

######  Definition 2.14.

The class $\mathsf{W[1]}$ contains all parameterized problems $L$ such that
there is a parameterized reduction from $L$ to $k$-Clique. The class
$\mathsf{W[2]}$ contains all parameterized problems $L$ such that there is a
parameterized reduction from $L$ to $k$-Hitting Set. Furthermore, we call a
problem $L^{\prime}$ _$\mathsf{W[1]}$ -hard_ (resp. _$\mathsf{W[2]}$ -hard_)
if there is a parameterized reduction from $k$-Clique (resp. $k$-Hitting Set)
to $L^{\prime}$.

Establishing $\mathsf{W[1]}$\- or $\mathsf{W[2]}$-hardness for a problem rules
out its fixed-parameter tractability under well-established complexity
assumptions (Downey and Fellows 2013).

##  3 Parameterized PAC-Learning

As the first step towards defining a theory of parameterized PAC learning, we
need to consider the parameters that will be used. In the computational
setting we associated a parameter with each instance, but in the learning
setting this notion does not exist—instead, a learning algorithm needs to deal
with a hidden concept representation and a hidden distribution, and we allow
both of these to be tied to parameterizations.

######  Definition 3.1 (Parameterization of Representations).

Let $\\{\mathcal{R}_{k}\\}_{k\in\mathbb{N}}$ with
$\mathcal{R}_{k}\subseteq\\{0,1\\}^{\ast}$ be a mapping assigning a set of
representations to every natural number $k$ such that for every
$r\in\\{0,1\\}^{\ast}$, there is some $k$ such that $r\in\mathcal{R}_{k}$,
that is, $\bigcup_{k}\mathcal{R}_{k}=\\{0,1\\}^{\ast}$. We call
$\\{\mathcal{R}_{k}\\}_{k\in\mathbb{N}}$ a _parameterization of
representations_. Given a parameterization of representations
$\\{\mathcal{R}_{k}\\}_{k\in\mathbb{N}}$, we associate a value
$\kappa_{\mathcal{R}}(r)$ to single representations $r\in\\{0,1\\}^{\ast}$ by
defining

$\kappa_{\mathcal{R}}(r)=\min\\{k\ :\ r\in\mathcal{R}_{k}\\}.$

######  Remark 3.2.

In line with the usual notion of parameterizations, we will assume
$\kappa_{\mathcal{R}}$ to be a computable function.

######  Example.

Let $\rho$ be the representation scheme taking a (binary representation of a)
$k$-term DNF formula to its underlying Boolean function. If we are interested
in learning $k$-term DNFs, we probably want to consider a $k^{\prime}$-term
DNF a $k$-term DNF for $k^{\prime}\leq k$, too. Therefore, we let
$\mathcal{R}_{k}$ be the set of all $k^{\prime}$-term DNFs for $k^{\prime}\leq
k$. The associated mapping $\kappa_{\mathcal{R}}$ then maps every $k$-term DNF
to the value of $k$.

######  Definition 3.3 (Parameterization of Distributions and Samples).

Let $\lambda$ be a mapping assigning a natural number to every distribution on
$\\{0,1\\}^{n}$ for each $n$, such that for every two distributions
$\mathcal{D},\mathcal{D^{\prime}}$ on $\\{0,1\\}^{n}$, if
$\operatorname{supp}\mathcal{D}\subseteq\operatorname{supp}\mathcal{D^{\prime}}$,
then $\lambda(\mathcal{D})\leq\lambda(\mathcal{D^{\prime}})$. In this case, we
call $\lambda$ a _parameterization of distributions_.

We extend every parameterization of distributions $\lambda$ to subsets
$X\subseteq\\{0,1\\}^{n}$ by defining its corresponding _parameterization of
sample sets_ via:

$\displaystyle\lambda(X)=\min_{\mathcal{D}\ :\ X\ =\
\operatorname{supp}\mathcal{D}}\lambda(\mathcal{D}).$ (3.1)

######  Remark 3.4.

Note that the definition implies that, equivalently,
$\lambda(X)=\min_{\mathcal{D}\ :\ X\ \subseteq\
\operatorname{supp}\mathcal{D}}\lambda(\mathcal{D})$; in other words,
$\lambda(X)$ is the lowest parameter that can be obtained from a distribution
that has $X$ as its support.

All parameterizations considered in our exposition depend solely on the
support; however, we do want to explicitly also allow more expressive
parameterizations that depend on the distribution. To build a theory allowing
such parameterizations, it is necessary to impose an additional technical
condition which ensures that the distributions minimizing the parameter values
for $\lambda$ are “well-behaved”.

######  Definition 3.5.

We say that a distribution $\mathcal{D}^{\ast}$ is called _typical for $X$
under $\lambda$_ if $\mathcal{D}^{\ast}$ attains the minimum in Eq. (3.1),
that is, $\lambda(X)=\lambda(\mathcal{D}^{\ast})$ and
$\operatorname{supp}\mathcal{D}^{\ast}=X$.

######  Definition 3.6 ($L$-Sampleable Parameterizations).

Let $\mathcal{A}$ be a randomized algorithm that receives input
$X\subseteq\\{0,1\\}^{n}$ and outputs a concept $c$ in time
$L(n,|X|,\lambda(X))$ for some non-decreasing function $L(\cdot,\cdot,\cdot)$.
We say that $\lambda$ is _$L$ -sampleable_ if the following holds true for the
random variable $C$ that corresponds to the output of $\mathcal{A}$ over all
random bits used by $\mathcal{A}$ to output $c$: There is some distribution
$\mathcal{D}^{\ast}$ that is typical for $X$ under $\lambda$ such that
$C\sim\mathcal{D}^{\ast}$ holds, i.e., $C$ has the same distribution as
$\mathcal{D}^{\ast}$.

######  Remark 3.7.

Every parameterization $\lambda$ that depends only on the support $X$ is
linear-time-sampleable, since the uniform distribution on $X$ will be typical
for $X$ under $\lambda$. More generally, we believe that every “reasonable”
parameterization is polynomial-time-sampleable.

######  Example.

For instance, a valid choice of $\lambda$ is the mapping that selects the
largest number $k$ such that there is a concept $x$ in the support of
$\mathcal{D}$ that has $k$ non-zero entries. This parameter can obviously be
computed on sets of concepts, as demanded by the condition, and is linear-time
sampleable (in the size of the input, $n\cdot t$).

######  Definition 3.8 (Parameterized Learning Problems).

A _parameterized learning problem_ is a learning problem $(\mathcal{C},\rho)$
together with a pair $(\\{\mathcal{R}_{k}\\}_{k\in\mathbb{N}},\lambda)$,
called its _parameters_ , where $\\{\mathcal{R}_{k}\\}_{k\in\mathbb{N}}$ is a
parameterization of representations and $\lambda$ is a parameterization of
distributions.

At this point, a note on the relation between the definitions presented above
and the formalism developed by Arvind, Köbler, and Lindner (2009) is in order.
While the latter is capable of expressing learning problems such as
$k$-juntas, where $k$ is the parameter, it cannot account for properties of
the sample space. For example, one might be interested in learning Boolean
formulas from samples that have a limited number of $k$ variables set to true.
Our framework captures this by including the distribution into the
parameterization. This can be likened on a conceptual level to the difference
that exists in ordinary parameterized complexity theory between
parameterizations by solution properties versus parameterizing by properties
of the input instance.

######  Definition 3.9 (Parameterized Learning Algorithm).

A _parameterized learning algorithm_ for a parameterized learning problem
$(\mathcal{C},\rho,\\{\mathcal{R}_{k}\\}_{k\in\mathbb{N}},\lambda)$ is a
learning algorithm for $(\mathcal{C},\rho)$ in the sense of Definition 2.4. In
addition to $n,\varepsilon,\delta$, a parameterized learning algorithm obtains
two inputs $k$ and $\ell$, which are promised to satisfy
$k=\kappa_{\mathcal{R}}(r^{\ast})$ as well as $\ell=\lambda(\mathcal{D}_{n})$,
and the algorithm is required to always output a hypothesis $h$ satisfying
$\kappa(h)\in\mathcal{R}_{k}$.

######  Remark 3.10.

By requiring the hidden hypothesis and the output hypothesis to adhere to the
same representation scheme, we limit ourselves to the setting of _proper_
learning. In principle, nothing speaks against extending our framework also to
the improper case, as is done in Arvind, Köbler, and Lindner (2009) for their
formalization. Since all our examples speak about proper learning, we restrict
our definitions to this case.

######  Remark 3.11.

As readers acquainted with parameterized complexity theory may find
noteworthy, parameterized learning problems as defined here depend on two
parameters, as opposed to a single parameter. For parameterized algorithms, it
is customary to combine multiple parameters $k,\ell$ into one via defining a
new parameter such as $k+\ell$ or $\max\\{k,\ell\\}$. Indeed, this leads to
less heavy notation, while sacrificing nothing in terms of expressive power of
the obtained theory.

We shall see towards the end of this section that for the purposes of this
article, it is more convenient to make do with two separate parameters, in
order to establish a meaningful link between ordinary parameterized algorithms
and parameterized learning algorithms.

Let $\mathrm{poly}(\cdot)$ denote the set of functions that can be bounded by
non-decreasing polynomial functions in their arguments. Furthermore,
$\mathrm{fpt}(x_{1},\ldots,x_{t};k_{1},\ldots,k_{t})$ and
$\mathrm{xp}(x_{1},\ldots,x_{t};k_{1},\ldots,k_{t})$ denote those functions
bounded by $f(k_{1},\ldots,k_{t})\cdot p(x_{1},\ldots,x_{t})$ and
$p(x_{1},\ldots,x_{t})^{f(k_{1},\ldots,k_{t})}$, respectively, for any non-
decreasing computable function $f$ in $k_{1},\ldots,k_{t}$ and
$p\in\mathrm{poly}(x_{1},\ldots,x_{t})$.

######  Definition 3.12 ($(T,S)$-PAC Learnability).

Let
$T(n,s,1/\varepsilon,1/\delta,k,\ell),S(n,s,1/\varepsilon,1/\delta,k,\ell)$ be
any two functions taking on integer values, and non-decreasing in all of their
arguments.

A parameterized learning problem
$\mathcal{L}=(\mathcal{C},\rho,\\{\mathcal{R}_{k}\\}_{k\in\mathbb{N}},\lambda)$
is _$(T,S)$ -PAC learnable_ if there is a PAC learning algorithm for
$\mathcal{L}$ that runs in time
$\mathcal{O}(T(n,s,1/\varepsilon,1/\delta,k,\ell))$ and queries the oracle at
most $\mathcal{O}(S(n,s,1/\varepsilon,1/\delta,k,\ell))$ times.

We denote the set of parameterized learning problems that are $(T,S)$-PAC
learnable by $\mathsf{PAC}[T,S]$. This is extended to sets of functions
$\mathbf{S},\mathbf{T}$ through setting
$\mathsf{PAC}[T,S]=\bigcup_{S\in\mathbf{S},\\\
T\in\mathbf{T}}\mathsf{PAC}[T,S]$.

######  Definition 3.13.

We define the following complexity classes:

$\displaystyle\mathsf{FPT}\text{-}\mathsf{PAC_{time}}$
$\displaystyle=\mathsf{PAC}[\mathrm{fpt},\mathrm{poly}],$ (3.2)
$\displaystyle\mathsf{FPT}\text{-}\mathsf{PAC}$
$\displaystyle=\mathsf{PAC}[\mathrm{fpt},\mathrm{fpt}],$ (3.3)
$\displaystyle\mathsf{XP}\text{-}\mathsf{PAC_{time}}$
$\displaystyle=\mathsf{PAC}[\mathrm{xp},\mathrm{poly}],$ (3.4)
$\displaystyle\mathsf{XP}\text{-}\mathsf{PAC}$
$\displaystyle=\mathsf{PAC}[\mathrm{xp},\mathrm{xp}],$ (3.5)

where we fixed

$\displaystyle\mathrm{poly}$
$\displaystyle=\mathrm{poly}(n,s,1/\varepsilon,1/\delta,k,\ell),$
$\displaystyle\mathrm{fpt}$
$\displaystyle=\mathrm{fpt}(n,s,1/\varepsilon,1/\delta;k,\ell),$
$\displaystyle\mathrm{xp}$
$\displaystyle=\mathrm{xp}(n,s,1/\varepsilon,1/\delta;k,\ell).$

######  Remark 3.14.

In addition to the complexity classes just defined, there is a fifth class
that may be considered here: $\mathsf{PAC}[\mathrm{xp},\mathrm{fpt}].$
However, this class does not play a role in any of the examples presented in
this work, and hence we leave its exploration to future works.

Figure 1 provides an overview of these complexity classes and their
relationships. As does $\mathsf{XP}$, the class
$\mathsf{XP}\text{-}\mathsf{PAC}$ in the learning setting contains precisely
those parameterized learning problems which become efficiently PAC-learnable
whenever the parameters are fixed to an arbitrary constant.

######  Example.

A problem that fits into the class $\mathsf{XP}\text{-}\mathsf{PAC}$ is
learning of $k$-CNF and $k$-DNF formulas, parameterized by $k$. On the other
hand, the upcoming Theorems 5.6 and 6.2 furnish the class
$\mathsf{FPT}\text{-}\mathsf{PAC_{time}}$. An example for the class
$\mathsf{FPT}\text{-}\mathsf{PAC}$ in spirit can be found in Li and Liang
(2018). Finally, an example of a learning problem in
$\mathsf{XP}\text{-}\mathsf{PAC_{time}}$ is provided in Observation 6.5.

$\mathsf{PAC}$$\mathsf{XP}\text{-}\mathsf{PAC}$$\mathsf{XP}\text{-}\mathsf{PAC_{time}}$$\mathsf{FPT}\text{-}\mathsf{PAC}$$\mathsf{FPT}\text{-}\mathsf{PAC_{time}}$$\mathsf{PAC}[\mathrm{poly},\mathrm{poly}]$
Figure 1: A schematic view of the parameterized learning classes defined in
Definition 3.13.

### Consistency Checking: A Link between Theories

With the basic complexity classes in place, we turn to establishing links
between the newly developed theory and the by now well-established
parameterized complexity paradigm for decision problems. Crucially, these
links will allow us to exploit algorithmic upper and lower bounds from the
latter also in the learning setting.

######  Definition 3.15 (Parameterized Consistency Checking).

With every parameterized learning problem
$\mathcal{L}=(\mathcal{C},\rho,\\{\mathcal{R}_{k}\\}_{k\in\mathbb{N}},\lambda)$
and every function $f(n,t,k,\ell)$ we associate a parameterized search problem
$f$-Consistency($\mathcal{L}$) as follows:

  1. 1.

Its input is a list of labeled samples $((x_{1},a_{1}),\ldots,(x_{t},a_{t}))$,
with $x_{i}\in\\{0,1\\}^{n}$ for all $i$ and $x_{i}$ pairwise distinct, as
well as $a_{i}\in\\{0,1\\}$.

  2. 2.

Its parameters are $k\in\mathbb{N}$, given as part of the input, and
$\ell=\lambda(\\{x_{1},\ldots,x_{t}\\})$.

  3. 3.

The task is to decide whether there is a representation $r$ that has
$\kappa(r)\in\mathcal{R}_{k}$ with $|r|\leq f(n,t,k,\ell)$ and for the concept
$c=\rho(r)$, it holds that $c(x_{i})=a_{i}$ for all $i$.

We call this parameterized problem the _parameterized consistency checking
problem_ associated with $\mathcal{L}$ and $f$.

Ignoring all parameters in Definition 3.15 gives the usual notion of
consistency checking problems (Pitt and Valiant 1988). The function $f$ is
required to provide an explicit upper-bound on the sought-after
representation; indeed, while each learning instance comes with a hidden
representation of a certain size, this is not the case with the consistency
checking problem and we need to allow the running time bounds to take the size
of the representation into consideration.

It is well-known that, under the assumption that the hypothesis space is not
too large, there is an equivalence between a learning problem being PAC-
learnable and the corresponding decision problem being solvable in randomized
polynomial time. We now observe that a similar equivalence holds also in the
parameterized setting.

######  Lemma 3.16.

Let
$\mathcal{L}=(\mathcal{C},\rho,\\{\mathcal{R}_{k}\\}_{k\in\mathbb{N}},\lambda)$
be a parameterized learning problem, and let $f(n,t,k,\ell)$ be a function. If
$\mathcal{L}$ is $(T,S)$-PAC learnable and $\lambda$ is $L$-sampleable, then
there exists a randomized algorithm that, upon input labeled samples
$\\{(x_{1},a_{1}),\ldots,(x_{t},a_{t})\\}$ and parameters $k,\ell$ with
$\lambda(\\{x_{1},\ldots,x_{t}\\})=\ell$, returns a consistent hypothesis
$h\in\mathcal{R}_{k}$ of size $|h|\leq s=f(n,t,k,\ell)$ with probability at
least $1-\delta$ if it exists, and runs in time
$\mathcal{O}(T(n,s,t,\delta,k,\ell)+L(n,t,\ell)\cdot S(n,s,t,\delta,k,\ell))$.

###### Proof.

Let $((x_{1},a_{1}),\ldots,(x_{t},a_{t})),k,\ell$ be some inputs to the
parameterized consistency problem associated with $\mathcal{L}$ such that
$\lambda(\\{x_{1},\ldots,x_{t}\\})=\ell$. We set $\varepsilon=\frac{1}{t+1}$,
and take $\delta$ as desired for the success probability.

We run the $(T,S)$-PAC algorithm with inputs $n=|x_{1}|=\ldots=|x_{t}|$,
$\varepsilon$ and $\delta$. During execution of this algorithm, we emulate the
oracle to a hidden distribution by calling the sampling algorithm guaranteed
to exist by $\lambda$.

By definition, the PAC-learning algorithm will return a hypothesis from
$\mathcal{R}_{k}$ inconsistent with at most a $1/(t+1)$-fraction of the
samples, and therefore consistent with all of them, with probability at least
$1-\delta$ (if it exists), which we output. Otherwise, we output some
arbitrary hypothesis. This gives a randomized algorithm for the parameterized
consistency checking problem satisfying the required bound on the success
probability.

As for the running time, note that we call the learning algorithm with the
parameters as in the statement of the Lemma, which takes
$T(n,s,t,\delta,k,\ell)$ steps, and for each of the $S(n,s,t,\delta,k,\ell)$
oracle calls the learning algorithm makes, we need to spend time $L(n,t,\ell)$
to produce a sample from the distribution. We note that, if the PAC algorithm
were to spend more than $T(n,s,t,k,\ell)$ steps (or draw more than
$S(n,s,t,k,\ell)$ samples), we may safely halt its execution and return an
arbitrary hypothesis222To be completely precise, the functions would have to
meet the criterion of being asymptotically equivalent to some time-
constructible function. Since this plays no role whatsoever in any natural
scenario, we chose to ignore these details.. ∎

######  Theorem 3.17.

Let
$\mathcal{L}=(\mathcal{C},\rho,\\{\mathcal{R}_{k}\\}_{k\in\mathbb{N}},\lambda)$
be a parameterized learning problem, and let $f(n,t,k,\ell)$ be a function.

If $\mathcal{L}$ is in $\mathsf{FPT}\text{-}\mathsf{PAC}$,
$f\in\mathrm{fpt}(n,t;k,\ell)$ and $\lambda$ is $S$-sampleable for some
$S\in\mathrm{fpt}(n,t;\ell)$, then the parameterized consistency checking
problem $f$-Consistency($\mathcal{L}$) associated with $\mathcal{L}$ and $f$
is in $\mathsf{FPT}$.

Similarly, if $\mathcal{L}$ is in $\mathsf{XP}\text{-}\mathsf{PAC}$,
$f\in\mathrm{xp}(n,t;k,\ell)$ and $\lambda$ is $S$-sampleable for some
$S\in\mathrm{xp}(n,t;\ell)$, then the parameterized consistency checking
problem $f$-Consistency($\mathcal{L}$) associated with $\mathcal{L}$ and $f$
is in $\mathsf{XP}$.

###### Proof.

Follows by inserting the appropriate functions into $T,S$ and $L$ in Lemma
3.16. Note, in particular, that the dependency on $s=f(n,t,k,\ell)$ in $T$ and
$S$ is only allowed to be of the form
$g(k,\ell)\cdot\mathrm{poly}(n,s,1/\varepsilon,1/\delta)$ or
$\mathrm{poly}(n,s,1/\varepsilon,1/\delta)^{g(k,\ell)}$, by the respective
definitions of $\mathsf{FPT}\text{-}\mathsf{PAC}$ and
$\mathsf{XP}\text{-}\mathsf{PAC}$. Hence, if $f\in\mathrm{fpt}(n,t;k,\ell)$,
then $\mathrm{poly}(n,f(n,t;k,\ell),1/\varepsilon,1/\delta)$ is still bounded
by $g^{\prime}(k,\ell)\cdot\mathrm{poly}(n,t,1/\varepsilon,1/\delta)$, and
similarly for $f\in\mathrm{xp}(n,t;k,\ell)$. ∎

######  Lemma 3.18.

Let
$\mathcal{L}=(\mathcal{C},\rho,\\{\mathcal{R}_{k}\\}_{k\in\mathbb{N}},\lambda)$
be a parameterized learning problem, and let
$\mathcal{H}_{n,k}=\mathcal{R}_{k}\cap\rho^{-1}(\mathcal{C}_{n})$ be the set
of all representations under $\rho$ in $\mathcal{R}_{k}$ of concepts in
$\mathcal{C}_{n}$. Suppose there is a deterministic algorithm running in time
$T(n,t,\delta,k,\ell)$ for the consistency checking problem
$\log|\mathcal{H}_{n,k}|$-Consistency($\mathcal{L}$). Then, $\mathcal{L}$ is
$(T^{\prime},S)$-PAC learnable, where333The dependency on $s$ disappears
because $s$ itself is bounded by a function of $n$ and $k$.

$\displaystyle S(n,s,1/\varepsilon,1/\delta,k,\ell)$
$\displaystyle=\frac{1}{\varepsilon}(\log|\mathcal{H}_{n,k}|+\frac{1}{\delta})),$
$\displaystyle T^{\prime}(n,s,1/\varepsilon,1/\delta,k,\ell)$
$\displaystyle=T(n,s,\frac{1}{\varepsilon}(\log|\mathcal{H}_{n,k}|+\frac{1}{\delta}),k,\ell).$

###### Proof.

The learning algorithm proceeds by drawing
$t=\frac{1}{\varepsilon}(\log|\mathcal{H}_{n,k}|+\frac{1}{\delta})$ samples
$(x_{1},a_{1}),\ldots,(x_{t},a_{t})$ from the unknown distribution
$\mathcal{D}$, and calls the algorithm using these $t$ samples and the
parameter $k$. It outputs the hypothesis $h$ returned by the algorithm, which
is guaranteed to be in $\mathcal{R}_{k}$, and satisfies
$|h|\leq\log|H_{n,k}|$. By a standard argument via the union bound, the
resulting algorithm is indeed a parameterized PAC algorithm.

For this call to the algorithm, note that by definition,
$\lambda(\\{x_{1},\ldots,x_{t}\\})\leq\ell$. Recall from Definition 3.12 that
we assumed $T$ and $S$ to be non-decreasing. Hence, by assumption, this takes
time at most
$T(n,\frac{1}{\varepsilon}(\log|\mathcal{H}_{n,k}|+\frac{1}{\delta}),k,\ell),$
and uses $t=\frac{1}{\varepsilon}(\log|\mathcal{H}_{n,k}|+\frac{1}{\delta})$
samples. ∎

######  Theorem 3.19.

Let
$\mathcal{L}=(\mathcal{C},\rho,\\{\mathcal{R}_{k}\\}_{k\in\mathbb{N}},\lambda)$,
and denote the set of representations of $\mathcal{C}_{n}$ in
$\mathcal{R}_{k}$ under $\rho$ as $\mathcal{H}_{n,k}$.

If the parameterized consistency checking problem
$\log|\mathcal{H}_{n,k}|$-Consistency($\mathcal{L}$) is in $\mathsf{FPT}$ and
$\log|\mathcal{H}_{n,k}|\in\mathrm{fpt}(n;k)$, then $\mathcal{L}$ is in
$\mathsf{FPT}\text{-}\mathsf{PAC_{time}}$.

Similarly, if the parameterized consistency checking problem
$\log|\mathcal{H}_{n,k}|$-Consistency($\mathcal{L}$) is in $\mathsf{XP}$ and
$\log|\mathcal{H}_{n,k}|\in\mathrm{xp}(n;k)$, then $\mathcal{L}$ is in
$\mathsf{XP}\text{-}\mathsf{PAC_{time}}$.

###### Proof.

Follows from Lemma 3.18 by and then inserting the respective running time
functions and the bounds on $\mathcal{H}_{n,k}$, which in particular bound the
length of any potentially returned hypotesis. ∎

The significance of the previous theorems lies in transferring parameterized
algorithmic upper and lower bounds for consistency checking into upper and
lower bounds for parameterized learning problems, respectively.

To wit, Theorem 3.17 allows us to conclude from the fact that a parameterized
consistency checking problem is efficiently solvable by a parameterized
algorithm that also the parameterized learning problem it belongs to is
efficiently solvable. This will be exploited in Theorems 5.6, 6.2.

On the other hand, Theorem 3.19 tells us that an efficient algorithm for a
parameterized learning problem implies an efficient algorithm for the
corresponding paramerized consistency checking problem. Turning this around,
we see that lower bounds on consistency checking imply lower bounds for
learning. This will be exploited in Theorems 5.1, 6.4.

##  4 Previous Work on Parameterized Learning

After having introduced this new framework, we dedicate a separate section to
how it fits in with the few papers that have considered parameterized
approaches to learning theory, and how it differs from them.

Proceeding chronologically, the earliest link between parameterized complexity
theory and learning theory was established already by the pioneers of
paramerized complexity (Downey, Evans, and Fellows 1993). While they also
establish a parameterized learning model and link learning complexity with
well-studied graph problems, in contrast to our work, they study exact
learning by extended equivalence queries. Gärtner and Garriga (2007) study the
complexity of learning directed cuts in various learning models, including PAC
learning. While their respective result falls under the standard poly-time PAC
learning, it is notable that the improved learning bound they show is in terms
of a structural parameter of the graph. Better-than-trivial exponential
running-time bounds for learning $k$-term DNF formulas have been studied,
e.g., $n^{\tilde{\mathcal{O}}(\sqrt{n\log k})}$ (Alekhnovich et al. 2008). We
already compared our framework to the earlier work by Arvind, Köbler, and
Lindner (2009) in the previous section, which only identified the class
$\mathsf{FPT}\text{-}\mathsf{PAC}$.

The more recent work of Li and Liang (2018) on parameterized algorithms for
learning mixtures of linear regressions is not, strictly speaking, within our
framework of parameterized PAC learning, since their error parameter is the
distance to the hidden concept rather than the probability of mislabelling
under any distribution. However, their sample complexity bound is
$\mathsf{FPT}$, turning into infinite when the parameters are not bounded, and
it is also a notable example of a PAC-learning result that holds only for a
certain family of distributions (an approach which is also covered by our
framework; see the intuition behind Definition 3.6). Finally, van Bergerem,
Grohe, and Ritzert (2022) consider parameterized complexity of learning first-
order logic; they show hardness results via parameterized reductions as well
as $\mathsf{FPT}$-time learning via consistency checking, which aligns well
with our framework.

##  5 Parameterized DNF and CNF Learning

For the most of this section, we consider the problem of learning a hidden DNF
formula under various parameterizations, which are formally defined throughout
the section. We first observe that the problem of learning a CNF formula is
equivalent to learning a DNF formula under any parameterization that is
preserved under negation of the formula: indeed, by negating the input to a
DNF-learning algorithm and then negating the output formula we obtain a CNF-
learning algorithm, and vice versa. Thus our results hold for learning CNF
formulas as well, which we do not show explicitly below.

Let Learning DNF be the learning problem $(\mathcal{C},\rho)$ where
$\mathcal{C}$ is the set of boolean functions corresponding to formulas in
disjunctive normal form and $\rho$ is the straightforward representation of
the terms of the formula. To define a fundamental variant of the problem where
the number of terms in the target formula is bounded, let Learning $k$-term
DNF be the parameterized learning problem
$(\mathcal{C},\rho,\\{\mathcal{R}_{k}\\}_{k\in\mathbb{N}},\lambda)$ where
$\mathcal{C}$ and $\rho$ are as above, $\kappa$ maps the representation of the
formula to the number of terms in it, and $\lambda$ is any constant
parameterization. Alas, it is well-known that the consistency checking problem
for learning even $2$-term DNF is $\mathsf{NP}$-hard (Alekhnovich et al.
2008), and thus by a non-parameterized variant of Theorem 3.17, Learning
$k$-term DNF is not in $\mathsf{XP}\text{-}\mathsf{PAC_{time}}$ unless
$\mathsf{P}=\mathsf{NP}$. Thus, in this parameterization one should not expect
any tractability results.

Another natural way to parameterize Learning DNF would be to bound the maximum
length of a term. Specifically, let Learning $k$-DNF be the parameterized
learning problem
$(\mathcal{C},\rho,\\{\mathcal{R}_{k}\\}_{k\in\mathbb{N}},\lambda)$ where
$\mathcal{C}$ and $\rho$ are as in Learning DNF, $\kappa=\kappa_{\mathcal{R}}$
maps the representation of the formula to the maximum length of a term in it,
and $\lambda$ is trivial. It is well-known that, for every fixed $k$, Learning
$k$-DNF is efficiently PAC-learnable by a brute-force argument and hence the
problem is immediately in $\mathsf{XP}\text{-}\mathsf{PAC_{time}}$
parameterized by $k$ (Mohri, Rostamizadeh, and Talwalkar 2012, Example 2.9).
On the other hand, we show that under standard parameterized complexity
assumptions this learning result is tight, extending the hardness reduction of
Arvind et al. (Arvind, Köbler, and Lindner 2009) for $k$-juntas and
–monomials.

######  Theorem 5.1.

Assuming $\mathsf{W[2]}\neq\mathsf{FPT}$, Learning $k$-DNF and Learning
$k$-CNF are not in $\mathsf{FPT}\text{-}\mathsf{PAC_{time}}$.

###### Proof.

We show the result for Learning $k$-CNF. Assume the contrary, then by Theorem
3.17 there is an $\mathsf{FPT}$ algorithm for the consistency checking
problem. We now show that there is a parameterized reduction from $k$-Hitting
Set to the consistency checking problem for Learning $k$-CNF even for $f$
linear in $n$ and $k$, reaching a contradiction.

Consider an instance $(U,\mathcal{F})$ of $k$-Hitting Set. Set $n=|U|$,
$t=|\mathcal{F}|+1$, for each $i\in[t-1]$, $x_{i}[j]=1$ iff $j$-th element of
the universe belongs to the $i$-th set of $\mathcal{F}$, and $a_{i}=1$.
Finally, set $x_{t}$ to be a zero vector and $a_{t}=0$.

First, consider a $k$-hitting set $S\in U$. Consider a one-clause $k$-CNF
formula $\varphi$ that contains positive literals corresponding to the set
$S$. For each $i\in[t-1]$, $\varphi(x_{i})=1=a_{i}$ since $S$ intersects the
$i$-th set of $\mathcal{F}$, and the corresponding element of $x_{i}$ is set
to $1$. Moreover, $\varphi(x_{t})=0=a_{t}$ since $\varphi$ contains no
negative literals.

In the other direction, consider a $k$-CNF formula $\varphi$ that labels all
the samples correctly. Since $\varphi(x_{t})=a_{t}=0$, there exists a clause
$C$ in $\varphi$ that only contains positive literals. For each $i\in[t-1]$,
$\varphi(x_{i})=a_{i}=1$, and so $C(x_{i})=1$, thus there exists a positive
literal in $C$ which variable corresponds to an element of the $i$-th set of
$\mathcal{F}$. Thus the set $S$ consisting of elements corresponding to
variables in $C$ is a $k$-hitting set of $\mathcal{F}$. ∎

The above covers the two most natural parameterizations of the hypothesis
class — the number of terms and the maximum size of a term in the target
formula — however, we did not yet touch parameterizations of the sample space.
As a simple step, observe that solving the consistency problem is easy when
each assignment assigns at most one variable to “true”; a one-term DNF can
always be produced in this case. On the other hand, the previously-known
coloring reduction (Pitt and Valiant 1988) shows that even when each
assignment has at most two variables assigned to “true”, the problem becomes
$\mathsf{NP}$-hard. In the following, we analyze the tractability of learning
$k$-term DNF “between” these two cases, and show the following positive result
based on parameterizing by a notion of “backdoor to triviality” (Gaspers and
Szeider 2012; Semenov et al. 2018).

######  Lemma 5.2.

Learning $k$-Term DNF is $\mathsf{FPT}\text{-}\mathsf{PAC_{time}}$
parameterized by $k+s$, where $s$ is the minimum size of a set $S$ of
variables such that the support of the distribution satisfies the following:

  * •

each assignment assigns at most one variable outside of $S$ to “true”, and

  * •

each of the remaining variables, at most one assignment assigns it to “true”.

###### Proof.

By Theorem 3.19, it is enough to provide an $\mathsf{FPT}$ algorithm for the
consistency checking problem with $f=\mathrm{fpt}(n;k+s)$; in particular, it
suffices to argue that we can bound the length of all possible hypotheses by
such an $f$.

Partition the given set of labelled samples $(x_{1},a_{1})$, …,
$(x_{t},a_{t})$ into $b$ classes where all assignments in the same class agree
on $S$:
$\\{(x_{i},a_{i})\\}_{i\in[t]}=\\{(x_{i}^{1},a_{i}^{1})\\}_{i\in[t_{1}]}\cup\cdots\cup\\{(x_{i}^{b},a_{i}^{b})\\}_{i\in[t_{b}]}$,
where for each $i,i^{\prime}\in[t_{j}]$,
$\left.x_{i}^{j}\right|_{S}=\left.x_{i^{\prime}}^{j}\right|_{S}$. We now show
that the instance can always be reduced to a smaller one, unless each class is
of size at most $k$. The next two claims provide the exact reduction rules,
the first one shows that when there are too many yes-instances in the same
class, one of them can be safely removed.

######  Claim 5.3.

Let $x_{1}$, …, $x_{t}$ be the assignments of $[n]$, and $a_{1}$, …, $a_{t}$
be the respective labels. Let $t\geq k+2$, $S\subset[n]\setminus[k+2]$, and
for each $i\in[k+2]$, $a_{i}=1$, $x_{i}$ assigns $i$ to “true” and all other
variables in $[n]\setminus S$ to “false”. Let no assignment from $x_{1}$, …,
$x_{t}$ except for $x_{1}$ assign $1$ to “true”. If there exists a $k$-term
DNF formula $\varphi$ agreeing with $(x_{i},a_{i})_{i=2}^{t}$, then there
exists also a $k$-term DNF formula $\psi$ agreeing with
$(x_{i},a_{i})_{i=1}^{t}$.

######  Proof.

W.l.o.g. let $\varphi=T_{1}\lor\cdots\lor T_{k}$. If each of $T_{1}$, …,
$T_{k}$ contains a positive literal, by the pigeonhole principle there exists
an assignment $x_{i}$ out of $x_{2}$, …, $x_{k+2}$ that does not satisfy
$\varphi$. Therefore, there exists a conjunction $T_{j}$ that only contains
negative literals. If $T_{j}$ does not contain the negation of variable $1$,
$\varphi(x_{1})=1=\lambda_{1}$, so setting $\psi=\varphi$ concludes the proof.
Otherwise, take $\psi$ to be $\varphi$ where the negation of variable $1$ is
removed from the term $T_{j}$. It is easy to see that that
$\psi(a_{1})=1=\lambda_{1}$. Moreover, none of $a_{2}$, …, $a_{t}$ changes the
value of the assignment, since yes-instances cannot be unsatisfied by making
the term $T_{j}$ smaller, and no no-instance become satisfied as only $x_{1}$
assigns $1$ to “true”. ∎

The next claim allows us to simplify the negative samples.

######  Claim 5.4.

Let $x_{1}$, …, $x_{t}$ be the assignments of $[n]$, and $a_{1}$, …, $a_{t}$
be the respective labels. Let $t\geq 2$, $S\subset[n]\setminus\\{1\\}$, and
let $a_{i}=0$, $x_{1}$ assigns the variable $1$ to “true” and all other
variables in $[n]\setminus S$ to “false”. Let no assignment from $x_{1}$, …,
$x_{t}$ except for $x_{1}$ assign $1$ to “true”. If there exists a $k$-term
DNF formula $\varphi$ agreeing with $(x_{i},a_{i})_{i=2}^{t}$, then there
exists also a $k$-term DNF formula $\psi$ agreeing with
$(x_{i},a_{i})_{i=1}^{t}$.

######  Proof.

Let $\psi$ be the formula obtained from $\varphi$ by appending the negation of
the variable $1$ to each term. For each $i\in[t]\setminus\\{1\\}$, the
assignment $x_{i}$ keeps its value since it assigns $1$ to “false”. The
assignment $a_{t+1}$, on the other hand, clearly does not satisfy the
constructed formula. ∎

Finally, while the previous two claims reduce the number of samples to
consider, the next one reduces the number of variables by removing those that
are assigned identically.

######  Claim 5.5.

Let $x_{1}$, …, $x_{t}$ be the assignments of $[n]$, and $a_{1}$, …, $a_{t}$
be the respective labels. Let variables $1$ and $2$ be assigned identically in
the assignments $x_{1}$, …, $x_{t}$. There exists a $k$-term DNF formula
$\varphi$ in variables $2$, …, $n$ agreeing with $(x_{i},a_{i})_{i=1}^{t}$, if
and only if there exists a $k$-term DNF formula $\psi$ in variables $1$, …,
$n$ agreeing with $(x_{i},a_{i})_{i=1}^{t}$.

######  Proof.

In one direction, setting $\psi=\varphi$ clearly satisfies the claim. In the
other direction, let $\varphi$ be the formula $\psi$ where in every term a
literal of the variable $1$ is replaced with the same literal of the variable
$2$. Since no assignment in $x_{1}$, …, $x_{t}$ differentiates between $1$ and
$2$, $\psi(x_{i})=\varphi(x_{i})$ for each $i\in[t]$. ∎

We now use Claims 5.3, 5.4, and 5.5 to construct an instance equivalent to the
original with at most $2^{s}\cdot(k+2)$ assignment-label pairs on at most
$s+2^{s}\cdot(k+2)+1$ variables. The algorithm simply applies Claims 5.3, 5.4,
and 5.5 until none is applicable, possible renumerating the assignments and
the variables. We first claim that afterwards no class contains more than
$(k+2)$ assignments. If not, either there is a negatively labelled assignment
in the class that assigns some variable outside of $S$ to “true”, and Claim
5.4 is applicable, or there are at least $(k+2)$ positive assignments in the
class, and Claim 5.3 is applicable, which is a contradiction. Thus, in the
constructed instance there are at most $2^{s}\cdot(k+2)$ assignments, as
desired.

Regarding the variables, observe that outside of $S$, each assignment assigns
at most one variable to “true”. Thus at most $s+2^{s}\cdot(k+2)$ variables
assign at least one variable to “true”, meaning that all other variables are
only assigned to “false”. Since Claim 5.5 is not applicable, there can be at
most one such variable.

Now, the algorithm tries all possible terms on the remaining variables, and
checks whether each term does not satisfy any negatively-labelled assignment.
The algorithm then tries all $k$-term DNF formulas consisting of such terms,
and sees if any of them satisfies all positively-labelled assignments.

Regarding the running time, the applications of Claims 5.3, 5.4, and 5.5 are
clearly poly-time. In the reduced instance, there are at most
$s+2^{s}\cdot(k+2)+1$ variables, so at most $3^{s+2^{s}\cdot(k+2)+1}$ possible
terms and at most $3^{k\cdot(s+2^{s}\cdot(k+2)+1)}$ different $k$-term DNF
formulas on them. This bounds the size of the hypothesis space by
$\mathrm{fpt}(n;k+s)$. ∎

By applying the aforementioned standard transformation from DNF to CNF, we can
obtain an analogoue statement but with every occurrence of “true” inverted to
“false”. Another standard transformation which simply negates each assignment
in every sample and each literal in the hidden hypothesis then allows us to
obtain the same result for all four possible combinations of problems and
notions of triviality.

######  Theorem 5.6.

Learning $k$-Clause CNF and Learning $k$-Term DNF are both
$\mathsf{FPT}\text{-}\mathsf{PAC_{time}}$ parameterized by $k+s$, where $s$ is
the minimum size of a set $S$ of variables such that the support of the
distribution satisfies the following:

  * •

each assignment assigns at most one variable outside of $S$ to “false”
(respectively “true”), and

  * •

each of the remaining variables, at most one assignment assigns it to “false”
(respectively “true”).

##  6 Learning on Graphs

Let $H_{1}$, …, $H_{p}$ be a fixed family of graphs. Let $\mathcal{H}$ be a
class of graphs that do not contain any of $H_{1}$, …, $H_{p}$ as an induced
subgraph. In a classical $\mathcal{H}$-Vertex Deletion problem the task is,
given a graph $G$ and a parameter $k$, to determine whether there exist a
subset of vertices $S\subset V(G)$ of size at most $k$ such that $G-S$ belongs
to $\mathcal{H}$. Produced in the standard fashion, the consistency version of
this problem receives as input a sequence of graphs $G_{1}$, …, $G_{t}$ over
the same vertex set $V$, together with the sequence of labels $\lambda_{1}$,
…, $\lambda_{t}$, and the task is to find a subset $S\subset V$ of size at
most $k$ such that $G_{i}-S\in\mathcal{H}$ if and only if $\lambda_{i}=1$. Let
us call the respective learning problem Learning $\mathcal{H}$-Deletion Set.

In particular, when the forbidden family consists of a single graph $K_{2}$,
$\mathcal{H}$ is a class of empty graphs, and $\mathcal{H}$-Vertex Deletion is
equivalent to Vertex Cover. If the family is $P_{3}$, the problem becomes
Cluster Vertex Deletion — find a subset of vertices to delete so that the
graph turns into a cluster graph, i.e., a disjoint union of cliques. Learning
$\mathcal{H}$-Deletion Set thus generalizes both Learning Vertex Cover and
Learning Cluster Deletion Set, where the task is to learn a hidden vertex
cover and deletion set to a cluster graph, respectively.

Let us tie this explicitly to the formal framework of parameterized learning
developed above. In this context, we interpret an element $x\in\\{0,1\\}^{n}$
as the adjacency matrix of a graph on $N$ vertices, where $n=N^{2}$. A concept
$c:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is represented by a subset $S$ of the
$N$ vertices. The value $c(x)$ indicates whether or not $S$ is an
$\mathcal{H}$-Deletion set for the graph with adjacency matrix $x$. As noted,
the representation scheme of $c$ takes the subset $S$ to $c$ as just
described. Hence, $\mathcal{C}_{n}$ corresponds to all $\mathcal{H}$-Deletion
sets on $N$-vertex graphs. We parameterize by taking $\mathcal{R}_{k}$ to be
the set of all vertex subsets of size at most $k$, and let the distributions
carry the trivial constant parameterization $\lambda(\mathcal{D})=1$.

Note that, for graph problems, the length of hypotheses is always naturally
bounded linearly in $n$, so we will omit explicit references to $f$ for
consistency checking.

Next, we show that the well-known $\mathrm{fpt}$-time algorithm (Cygan et al.
2015) for $\mathcal{H}$-Vertex Deletion extends to the respective consistency
problem, implying that the wide class of problems characterized by finite
family of forbidden induced subgraphs is $\mathrm{fpt}$-time learnable.

######  Lemma 6.1.

Let $\mathcal{H}$ be a class of graphs forbidding induced $H_{1}$, …, $H_{p}$.
Then, the parameterized consistency checking problem associated with Learning
$\mathcal{H}$-Deletion Set is fixed-parameter tractable.

###### Proof.

Let $(x_{1},a_{1}),\ldots,(x_{t},a_{t})$ and $k$ be given, and let
$G_{1},\ldots,G_{t}$ be the corresponding graphs with $N$ vertices each.
Denote with $\mathcal{Y}$ be the set of $G_{i}$ such that $a_{i}=1$, and with
$\mathcal{N}$ those where $a_{i}=0$. We need to find a subset $S$ of at most
$k$ vertices such that $G-S\in\mathcal{H}$ for all $G\in\mathcal{Y}$, and
$G-S\notin\mathcal{H}$ for all $G\in\mathcal{N}$. First, note that since
$\mathcal{H}$ is defined through forbidden induced subgraphs, replacing $S$
with subset of $S$ that still satisfies the first condition will always also
still satisfy the second condition. It therefore suffices to look only for
inclusion-wise minimal subsets that satisfy $G-S\in\mathcal{H}$ for all
$G\in\mathcal{Y}$, and then check if $G-S\notin\mathcal{H}$ does indeed hold
true for all $G\in\mathcal{N}$.

In order to produce such a minimal set $S$ of size at most $k$, we will in
fact enumerate all of them in fixed-parameter time, by extending the usual
bounded search-tree based approach for enumerating minimal vertex covers.
Starting with an empty solution $S=\emptyset$, we iterate over the graphs in
$\mathcal{Y}$.

By brute force enumeration, we check if there is an induced copy of any of the
$H_{i}$ in any of them. Recall that there are a constant number $p$ of graphs
$H_{i}$ of constant size each, say, $q=\max_{i}|V(H_{i})|$, so that this can
be done in time $O(pN^{q})$, which is polynomial in $N$.

If this procedure uncovers an induced copy of $H_{i}$, then any
$\mathcal{H}$-deletion set must remove one of the at most $q$ vertices that
the induced copy of $H_{i}$ occupies in $G$ (if $|S|=k$ at this point, then we
discard $S$). Our enumeration algorithm branches on which of these $q$ choices
is made, and adds the respective vertex to $S$

If, on the other hand, there was no induced copy of any $H_{i}$, then $S$ is a
minimal $\mathcal{H}$-deletion set for all of the $G\in\mathcal{Y}$, so we
check if $G-S\notin\mathcal{H}$ holds true; if so, we output $S$.

As argued, this approach is correct. As for its running time, note that we
build up a search-tree of bounded depth $k$ with branching factor at most $q$,
and spend at most $O(pN^{q})$ time at each step of the recursion, leading to
an overall running time of at most $O(q^{k}pN^{q})$, which is in fixed-
parameter tractable in $k$. ∎

######  Theorem 6.2.

Let $\mathcal{H}$ be a class of graphs forbidding induced $H_{1}$, …, $H_{p}$.
Learning $\mathcal{H}$-Deletion Set is $\mathrm{fpt}$-time PAC-learnable
parameterized by the size of the deletion set.

###### Proof.

This follows from Lemma 6.1 together with Theorem 3.19. ∎

In contrast, we now show that another well-studied family of deletion problems
does most likely not admit a positive result similar to the above. Namely, for
a graph $H$, let $\mathcal{H}$ be a class of graphs that are $H$-minor-free.
In particular, when $H=K_{3}$, $\mathcal{H}$-Vertex Deletion is equivalent to
Feedback Vertex Set. This problem is well-known to admit $\mathrm{fpt}$-time
algorithms when parameterized by the size of the vertex set to delete (Cygan
et al. 2015), however we show that the consistency checking problem associated
with Learning Feedback Vertex Set is $\mathsf{W[2]}$-hard. That is, unless the
two parameterized complexity classes $\mathsf{FPT}$ and $\mathsf{W[2]}$
coincide, the consistency problem is not in $\mathsf{FPT}$. The consequence
$\mathsf{FPT}=\mathsf{W[2]}$ is a parameterized analogue to
$\mathsf{P}=\mathsf{NP}$, and considered highly unlikely.

######  Lemma 6.3.

The consistency checking problem for Learning Feedback Vertex Set is
$\mathsf{W[2]}$-hard, even with only yes-instances in the input.

###### Proof.

We reduce from $k$-Hitting Set. Again, the input is a pair $(U,\mathcal{F})$,
where $\mathcal{F}$ is a family $\mathcal{F}$ of subsets
$\\{F_{i}\\}_{i=1}^{m}$ such that $F_{i}\subseteq U$ for all $i$, and
$U=\\{1,\ldots,n\\}$. The task is to produce a set
$H\subseteq\\{1,\ldots,n\\}$ of size at most $k$ such that $F_{i}\cap
H\neq\emptyset$ for all $i$, where $k$ is the parameter. This problem is known
to be $\mathsf{W[2]}$-hard (Downey and Fellows 1999).

We construct an instance of the consistency checking problem for Feedback
Vertex Set as follows: The instances $(x_{i},a_{i})$ with $i=1,\ldots,m$ have
$a_{i}=1$ for all $i$, and every $x_{i}$ is a graph $G_{i}$ on vertices
$\\{1,\ldots,n\\}$, which edges that form a cycle on the vertex set $F_{i}$.
Every subset of vertices on $\\{1,\ldots,n\\}$ of size $k$ that is a
simultaneous feedback vertex set for all $G_{i}$ must hit each $F_{i}$ at
least once, and is hence a hitting set of size at most $k$. Conversely, every
simultaneous feedback vertex set for all of the $G_{i}$ must destroy every
cycle, and hence contain at least one element of $F_{i}$ for all $i$.

Therefore, there is a feedback vertex set of size at most $k$ consistent with
all samples if and only if there is a hitting set of size at most $k$ in the
original instance, and hence, consistency checking Feedback Vertex Set is
$\mathsf{W[2]}$-hard. ∎

######  Theorem 6.4.

Unless $\mathsf{FPT}=\mathsf{W[2]}$, the learning problem Learning Feedback
Vertex Set is not in $\mathsf{FPT}\text{-}\mathsf{PAC}$.

###### Proof.

Follows from Lemma 6.3 and Theorem 3.17. ∎

On the other hand, the consistency checking problem for Learning Feedback
Vertex Set is trivially in $\mathsf{XP}$. Since $\log|\mathcal{H}_{n,k}|$ is
trivially upper-bounded by $\mathcal{O}(n)$, by Theorem 3.19 we immediately
obtain:

######  Observation 6.5.

Learning Feedback Vertex Set is in $\mathsf{XP}\text{-}\mathsf{PAC_{time}}$.

The same argument can be made for learning many other graph structures, such
as dominating and independent sets.

##  7 Conclusion

Over the last two decades, the parameterized complexity paradigm has arguably
revolutionized our understanding of computational problems throughout computer
science. We firmly believe that applying a more fine-grained, parameterized
lens on learning problems can similarly reveal a wealth of research questions
and potential breakthroughs that have remained hidden up to now. This article
provides researchers with the tools and concepts they need to begin a rigorous
exploration of this novel research direction, while also laying the
foundations of a bridge that will connect the research communities surrounding
learning theory and time complexity. It is perhaps worth noting that these
communities have so far remained fairly isolated from each other, with their
few interactions occurring at venues dedicated to AI research.

Unlike in typical complexity-theoretic papers, we view the greatest
contribution of this article to be the theory-building part, i.e., Section 3.
Indeed, while the specific algorithms and lower bounds that we use to showcase
the theory are non-trivial and interesting in their own right, ensuring that
the theoretical foundations fit together, are broad enough to capture
potential future parameterizations, but also can support the crucial link to
the parameterized consistency checking problem was a highly challenging task.

The introduced parameterized PAC learning framework opens many avenues for
future study. For instance, there are interesting and non-trivial examples of
parameterized learning problems in the class
$\mathsf{PAC}[\mathrm{xp},\mathrm{fpt}]$?

## Acknowledgements

The authors acknowledge support from the Austrian Science Foundation (FWF,
project Y 1329 START-Programm).

## References

  * Abasi and Bshouty (2019) Abasi, H.; and Bshouty, N. H. 2019.  On Learning Graphs with Edge-Detecting Queries.  In Garivier, A.; and Kale, S., eds., _Algorithmic Learning Theory, ALT 2019, 22-24 March 2019, Chicago, Illinois, USA_ , volume 98 of _Proceedings of Machine Learning Research_ , 3–30. PMLR.
  * Abasi, Bshouty, and Mazzawi (2018) Abasi, H.; Bshouty, N. H.; and Mazzawi, H. 2018.  Non-adaptive learning of a hidden hypergraph.  _Theor. Comput. Sci._ , 716: 15–27.
  * Alekhnovich et al. (2008) Alekhnovich, M.; Braverman, M.; Feldman, V.; Klivans, A. R.; and Pitassi, T. 2008\.  The complexity of properly learning simple concept classes.  _J. Comput. Syst. Sci._ , 74(1): 16–34.
  * Alon and Asodi (2005) Alon, N.; and Asodi, V. 2005.  Learning a Hidden Subgraph.  _SIAM J. Discret. Math._ , 18(4): 697–712.
  * Arvind, Köbler, and Lindner (2009) Arvind, V.; Köbler, J.; and Lindner, W. 2009.  Parameterized learnability of juntas.  _Theor. Comput. Sci._ , 410(47-49): 4928–4936.
  * Choi and Kim (2010) Choi, S.; and Kim, J. H. 2010.  Optimal query complexity bounds for finding graphs.  _Artif. Intell._ , 174(9-10): 551–569.
  * Cygan et al. (2015) Cygan, M.; Fomin, F. V.; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; and Saurabh, S. 2015.  _Parameterized Algorithms_.  Springer.  ISBN 978-3-319-21274-6.
  * Damaschke and Muhammad (2010) Damaschke, P.; and Muhammad, A. S. 2010.  Competitive Group Testing and Learning Hidden Vertex Covers with Minimum Adaptivity.  _Discret. Math. Algorithms Appl._ , 2(3): 291–312.
  * Downey, Evans, and Fellows (1993) Downey, R. G.; Evans, P. A.; and Fellows, M. R. 1993.  Parameterized Learning Complexity.  In Pitt, L., ed., _Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, COLT 1993, Santa Cruz, CA, USA, July 26-28, 1993_ , 51–57. ACM.
  * Downey and Fellows (1999) Downey, R. G.; and Fellows, M. R. 1999.  _Parameterized Complexity_.  Monographs in Computer Science. Springer.  ISBN 978-1-4612-6798-0.
  * Downey and Fellows (2013) Downey, R. G.; and Fellows, M. R. 2013.  _Fundamentals of Parameterized Complexity_.  Texts in Computer Science. Springer.  ISBN 978-1-4471-5558-4.
  * Gärtner and Garriga (2007) Gärtner, T.; and Garriga, G. C. 2007.  The Cost of Learning Directed Cuts.  In Kok, J. N.; Koronacki, J.; de Mántaras, R. L.; Matwin, S.; Mladenic, D.; and Skowron, A., eds., _Machine Learning: ECML 2007, 18th European Conference on Machine Learning, Warsaw, Poland, September 17-21, 2007, Proceedings_ , volume 4701 of _Lecture Notes in Computer Science_ , 152–163. Springer.
  * Gaspers and Szeider (2012) Gaspers, S.; and Szeider, S. 2012.  Backdoors to Satisfaction.  In Bodlaender, H. L.; Downey, R.; Fomin, F. V.; and Marx, D., eds., _The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday_ , volume 7370 of _Lecture Notes in Computer Science_ , 287–317. Springer.
  * Li and Liang (2018) Li, Y.; and Liang, Y. 2018.  Learning Mixtures of Linear Regressions with Nearly Optimal Complexity.  In Bubeck, S.; Perchet, V.; and Rigollet, P., eds., _Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018_ , volume 75 of _Proceedings of Machine Learning Research_ , 1125–1144. PMLR.
  * Mohri, Rostamizadeh, and Talwalkar (2012) Mohri, M.; Rostamizadeh, A.; and Talwalkar, A. 2012.  _Foundations of Machine Learning_.  Adaptive computation and machine learning. MIT Press.  ISBN 978-0-262-01825-8.
  * Nguyen and Maehara (2020) Nguyen, H.; and Maehara, T. 2020.  Graph Homomorphism Convolution.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , 7306–7316. PMLR.
  * Pitt and Valiant (1988) Pitt, L.; and Valiant, L. G. 1988.  Computational limitations on learning from examples.  _J. ACM_ , 35(4): 965–984.
  * Semenov et al. (2018) Semenov, A. A.; Zaikin, O.; Otpuschennikov, I. V.; Kochemazov, S.; and Ignatiev, A. 2018.  On Cryptographic Attacks Using Backdoors for SAT.  In McIlraith, S. A.; and Weinberger, K. Q., eds., _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018_ , 6641–6648. AAAI Press.
  * Valiant (1984) Valiant, L. G. 1984.  A Theory of the Learnable.  _Commun. ACM_ , 27(11): 1134–1142.
  * van Bergerem, Grohe, and Ritzert (2022) van Bergerem, S.; Grohe, M.; and Ritzert, M. 2022.  On the Parameterized Complexity of Learning First-Order Logic.  In _Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_ , PODS ’22, 337–346. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450392600.