# Multiclass Learnability Does Not Imply Sample Compression

Chirag Pabbaraju Stanford University. Email<EMAIL_ADDRESS>
###### Abstract

A hypothesis class admits a sample compression scheme, if for every sample
labeled by a hypothesis from the class, it is possible to retain only a small
subsample, using which the labels on the entire sample can be inferred. The
size of the compression scheme is an upper bound on the size of the subsample
produced. Every learnable binary hypothesis class (which must necessarily have
finite VC dimension) admits a sample compression scheme of size only a finite
function of its VC dimension, independent of the sample size. For multiclass
hypothesis classes, the analog of VC dimension is the DS dimension. We show
that the analogous statement pertaining to sample compression is not true for
multiclass hypothesis classes: every learnable multiclass hypothesis class,
which must necessarily have finite DS dimension, does not admit a sample
compression scheme of size only a finite function of its DS dimension.

##  1 Introduction

Sample compression is a widely studied paradigm in learning theory. At a high
level, the main question that sample compression asks is: given a labeled
training dataset, is it possible to get by working only with a small fraction
of the dataset? A valid sample compression scheme gets rid of all the
uninformative points in the dataset, and compresses the sample to a much
smaller subsample, such that there exists an algorithm that can reconstruct
all the labels on the original sample correctly just from the compressed
sample. A classical example of sample compression is exhibited by support
vector machines for the task of classifying linearly separable data. Here, the
compressor may only send the support vectors in the data to the reconstructor.
The reconstructor goes on to build a hyperplane that maximally separates the
support vectors with the largest possible margin; this, in turn, also recovers
correct labels on the non-support-vector points. In the language of learning
theory, if such compression-reconstruction is possible for every sample
realizable by a hypothesis class $\overline{\mathcal{H}}$, we say that the
class $\overline{\mathcal{H}}$ admits a sample compression scheme. In this
case, the size of the compression scheme is the size $k(m)$ that a sample of
size $m$ gets compressed down to.

In fact, sample compression is intrinsically tied up with the learnability of
binary hypothesis classes (where the label space is $\\{0,1\\}$). Formally,
[LW86] showed that every binary class $\overline{\mathcal{H}}$ that admits a
sample compression scheme of size $k(m)$ also defines a PAC (Probably-
Approximately-Correct) [Val84] learning algorithm for the class having sample
complexity $O(k(m))$. Thus, compression implies learnability in the case of
binary classes. In their work, [LW86] also asked the converse: does
learnability imply compression? Since the PAC learnability of a binary class
$\overline{\mathcal{H}}$ is completely characterized by the finiteness of its
VC dimension $\mathrm{VC}(\overline{\mathcal{H}})$ [VC74, VC15, BEHW89], this
question is equivalent to asking: does every binary class
$\overline{\mathcal{H}}$ having finite VC dimension
$\mathrm{VC}(\overline{\mathcal{H}})$ admit a sample compression scheme of
size only a finite function of $\mathrm{VC}(\overline{\mathcal{H}})$?

A long line of insightful works on this question culminated with [MY16]
answering it in the affirmative. For any binary class $\overline{\mathcal{H}}$
having VC dimension $d_{\mathrm{VC}}$, [MY16] constructed a sample compression
scheme of size $O(d_{\mathrm{VC}}\cdot 2^{d_{\mathrm{VC}}})$. Prior to their
work, existing sample compression schemes had a dependence either on the
sample size $m$ (e.g., compression of size $O(d_{\mathrm{VC}}\cdot\log(m))$
via boosting due to [Fre95, FS97]), or on the size of $\overline{\mathcal{H}}$
(e.g., compression of size
$O(2^{d_{\mathrm{VC}}}\cdot\log\log|\overline{\mathcal{H}}|)$ due to
[MSWY17]).111For a detailed and exhaustive list of other prior compression
schemes, we refer the reader to Section 1.2.2 in [MY16]. The work of [MY16]
gets rid of both these dependencies and obtains a compression scheme of size
only a function of the VC dimension, thus establishing the equivalence of
learnability and sample compression for binary hypothesis classes. It is worth
mentioning that constructing sample compression schemes of size even sub-
exponential in $d_{\mathrm{VC}}$ is still open, and has been a longstanding
famous problem in learning theory [War03]!

For essentially the same reasons that compression implies learnability in the
binary case, compression also implies learnability in the multiclass case
(where the label space is not just $\\{0,1\\}$ but much larger, possibly
infinite too), as was observed by [DMY16]. Here too, we can ask the
counterpart of [LW86]’s question: does multiclass learnability imply sample
compression? In fact, the notion of what learnability means in the multiclass
setting was only fully established in a recent seminal work by [BCD+22], who
equated PAC learnability of the class with finiteness of its DS dimension
[DSS14]. Concretely, while finiteness of the DS dimension was known to be
necessary for learnability, [BCD+22] also constructed an algorithm that
successfully learns classes having finite DS dimension. Thus, the natural
question to ask is: does every multiclass hypothesis class
$\overline{\mathcal{H}}$ having finite DS dimension
$\mathrm{DS}(\overline{\mathcal{H}})$ admit a sample compression scheme of
size only a finite function of $\mathrm{DS}(\overline{\mathcal{H}})$?

Interestingly, the route that [BCD+22] take to construct a learning algorithm
for hypothesis classes having finite DS dimension is via sample compression.
Concretely, for any sample of size $m$ realizable by a hypothesis class of DS
dimension $d_{\mathrm{DS}}$, they construct a sample compression scheme of
size $\tilde{O}(d_{\mathrm{DS}}^{1.5}\cdot\mathrm{polylog}(m))$. This
$\mathrm{polylog}(m)$ dependence on the size of the compression scheme is
indeed reminiscent of the analogous dependence in the boosting-based
compression scheme of [Fre95, FS97] for binary classes. Given that this
dependence was ultimately removed in the work of [MY16], could it also be
altogether gotten rid of in the multiclass case?

We answer this question in the negative, and show that a dependence on the
sample size $m$ is indeed necessary in the compression size for any valid
sample compression scheme in the multiclass setting. Our main result is the
following:

######  Theorem 1 (Multiclass Learnability $\not\Rightarrow$ Compression).

There exists a hypothesis class $\overline{\mathcal{H}}$ mapping a domain
$\mathcal{X}$ to $\mathcal{Y}=\\{0,1,2,\dots\\}$ that satisfies:

  1. (1)

$d_{\mathrm{DS}}(\overline{\mathcal{H}})=1$.

  2. (2)

Any sample compression scheme for $\overline{\mathcal{H}}$ that compresses
labeled samples of size $m$ to a subsample of size $k(m)$ must satisfy
$k(m)=\Omega((\log(m))^{1-o(1)})$, where the $o(1)$ term goes to 0 as
$m\to\infty$.

This result means that unlike the binary case, we cannot hope to obtain a
sample compression scheme in the multiclass setting where the size of the
scheme is a finite function of only the DS dimension of the hypothesis class.
Instead, the size of any compression scheme must necessarily depend on the
sample size. Note again that (1) above implies that $\overline{\mathcal{H}}$
is learnable. Therefore, while compression implies learnability, learnability
does not imply sample compression in the multiclass case, thus exhibiting a
separation amongst the two paradigms in the binary and multiclass case. The
rest of the paper is devoted to establishing Theorem 1 and discussing the
result.

##  2 Preliminaries and Background

The input data domain is denoted as $\mathcal{X}$ and the label space as
$\mathcal{Y}$. Concepts and hypotheses are interchangeably used to mean the
same object. To prove our result, we will require dealing with partial concept
classes $(\mathcal{X}\to\\{\mathcal{Y}\cup\\{\star\\}\\})$, where $\star$ is a
special symbol, and hence we will denote the otherwise standard total concept
classes $(\mathcal{X}\to\mathcal{Y})$ with symbols having a bar on top (e.g.,
$\overline{\mathcal{H}}$) and partial classes without a bar (e.g.,
$\mathcal{H}$). When we are thinking of partial classes and want the label
space to additionally also include the special symbol $\star$, we will be
explicit and use $\\{\mathcal{Y}\cup\\{\star\\}\\}$ — otherwise, $\mathcal{Y}$
should be assumed to not include $\star$. For a sequence
$S\in\mathcal{X}^{d}$, we denote the restriction of a class $\mathcal{H}$ on
$S$ (all the different ways in which members of $\mathcal{H}$ can label $S$)
by $\mathcal{H}|_{S}$.

###  2.1 Partial Concept Classes and Disambiguation

Our lower bound heavily relies on the theory of partial concept classes
introduced in the work of [AHHM22]. Concepts in a partial concept class are
allowed to be undefined in certain regions of the input domain. These regions
vary based on known structural assumptions on the data like margin-
separatedness, data lying on a low-dimensional subspace, etc.

######  Definition 1 (Partial Concept Classes [AHHM22]).

Given an input space $\mathcal{X}$, a label space
$\mathcal{Y}=\\{0,1,2,\dots\\}$, and a special symbol $\star$, a partial
concept class $\mathcal{H}$ maps $\mathcal{X}$ to $\mathcal{Y}\cup\\{\star\\}$
i.e., $\mathcal{H}\subseteq\\{\mathcal{Y}\cup\\{\star\\}\\}^{\mathcal{X}}$.
For any $h\in\mathcal{H}$, if $h(x)=\star$, we say that $h$ is undefined at
$x$. The support of a partial concept $h\in\mathcal{H}$ is defined as
$\mathrm{supp}(h)=\\{x\in\mathcal{X}:h(x)\neq\star\\}$, and
$\mathrm{supp}(\mathcal{H})=\bigcup_{h\in\mathcal{H}}\mathrm{supp}(h)$. A
labeled sequence $S=\\{(x_{1},y_{1}),\dots,(x_{m},y_{m})\\}$ is realizable by
$\mathcal{H}$ if there exists a partial concept $h\in\mathcal{H}$ such that
$\forall i\in[m],~{}h(x_{i})\neq\star\text{ and }h(x_{i})=y_{i}$.

If every concept in the partial concept class has full support, the $\star$
symbol becomes irrelevant and we get the usual notion of a total concept
class.

######  Definition 2 (Total Concept Classes).

A partial concept class
$\overline{\mathcal{H}}\subseteq\\{\mathcal{Y}\cup\\{\star\\}\\}^{\mathcal{X}}$
that satisfies
$\mathrm{supp}(\overline{h})=\mathcal{X},~{}\forall\overline{h}\in\overline{\mathcal{H}}$,
is a total concept class.

Total concept classes naturally define the notion of “disambiguation” of
partial concept classes.

######  Definition 3 (Disambiguation, Definition 9 in [AHHM22]).

A total concept class
$\overline{\mathcal{H}}\subseteq\mathcal{Y}^{\mathcal{X}}$ disambiguates a
partial concept class $\mathcal{H}$ if for every finite labeled sequence
$S=\\{(x_{1},y_{1}),\dots,(x_{m},y_{m})\\}$ realizable by $\mathcal{H}$, there
exists $\overline{h}\in\overline{\mathcal{H}}$ such that $\forall
i\in[m],~{}\overline{h}(x_{i})=h(x_{i})$.

The hard-to-compress hypothesis class that realizes our lower bound in Theorem
1 will be a suitable disambiguation of a hard-to-compress partial concept
class. Next, we define the relevant complexity parameter that completely
captures the learnability of a multiclass hypothesis class — the DS dimension.

###  2.2 DS Dimension

As mentioned above, while the VC dimension of a binary (total) concept class
was long known to completely characterize its learnability, the corresponding
problem of characterizing the learnability of a class on multiple classes was
only resolved recently in the work of [BCD+22]. They showed that a
combinatorial complexity parameter called the DS dimension (due to [DSS14]) is
the appropriate equivalent of the VC dimension in terms of characterizing
learnability of multiclass concept classes. Since total classes are special
cases of partial classes, we define the DS dimension more generally for
multiclass partial concept classes below.

######  Definition 4 (DS dimension [DSS14]).

Let $\mathcal{H}\subseteq\\{\mathcal{Y}\cup\\{\star\\}\\}^{\mathcal{X}}$ be a
partial concept class and let $S=\\{x_{1},\dots,x_{d}\\}\in\mathcal{X}^{d}$ be
an unlabeled sequence. For $i\in[d]$, we say that $f,g\in\mathcal{H}|_{S}$ are
$i$-neighbours if $f(x_{i})\neq g(x_{i})$ and $f(x_{j})=g(x_{j}),\;\forall
j\neq i$. We say that $\mathcal{H}$ DS-shatters $S$ if there exists
$\mathcal{F}\subseteq\mathcal{H},|\mathcal{F}|<\infty$ satisfying

  1. 1.

$\forall f\in\mathcal{F}|_{S},\;\forall i\in[d],$ $f(x_{i})\neq\star$.

  2. 2.

$\forall f\in\mathcal{F}|_{S},\;\forall i\in[d],$ $f$ has at least one
$i$-neighbor $g$ in $\mathcal{F}|_{S}$.

The DS dimension of $\mathcal{H}$, denoted as
$d_{\mathrm{DS}}=d_{\mathrm{DS}}(\mathcal{H})$, is the largest integer $d$
such that $\mathcal{H}$ DS-shatters222When $\mathcal{Y}=\\{0,1\\}$, DS-
shattering is equivalent to the standard notion of VC-shattering i.e.,
realizability of all binary patterns. some sequence $S$ of size $d$.

###  2.3 Sample Compression Schemes

The way in which [BCD+22] construct a learning algorithm for multiclass
concept classes having finite DS dimension is through a sample compression
scheme. This is sufficient because a successful sample compression scheme
implies the existence of a learning algorithm [DMY16]. Here, we formally
define sample compression schemes.

######  Definition 5 (Sample Compression, Definition 29 in [AHHM22]).

A compression scheme $(\kappa,\rho)$ consists of a compression function
$\kappa:(\mathcal{X}\times\mathcal{Y})^{*}\to(\mathcal{X}\times\mathcal{Y})^{*}\times\\{0,1\\}^{*}$
and a reconstruction function
$\rho:(\mathcal{X}\times\mathcal{Y})^{*}\times\\{0,1\\}^{*}\to\mathcal{Y}^{\mathcal{X}}$.
$\kappa$ and $\rho$ must satisfy the following property: for any sequence
$S\in(\mathcal{X}\times\mathcal{Y})^{*}$, $\kappa(S)=(S^{\prime},B)$ such that
the elements in $S^{\prime}$ necessarily also exist in $S$.The size $k(m)$ of
the compression scheme for a given sample size $m$ is

$k(m)=max_{S\in(\mathcal{X}\times\mathcal{Y})^{m},(S^{\prime},B)=\kappa(S)}\max(|S^{\prime}|,|B|).$
(1)

The (unqualified) size $k$ of the compression scheme is the maximum size
$k(m)$ over all $m$, or infinite if the size can be unbounded.

A compression scheme $(\kappa,\rho)$ is a sample compression scheme for a
partial concept class
$\mathcal{H}\in\\{\mathcal{Y}\cup\\{\star\\}\\}^{\mathcal{X}}$ if for all
finite labeled sequences $S=\\{(x_{1},y_{1}),\dots,(x_{m},y_{m})\\}$
realizable by $\mathcal{H}$, $\rho(\kappa(S))$ is correct on all of $S$ i.e.,
$\forall i\in[m],~{}\rho(\kappa(S))(x_{i})=y_{i}$.

######  Remark 1.

Observe that we only care about compressing sequences realizable by the class
(no points in the sequence should be labeled with a $\star$), and that the
reconstructor $\rho$ always outputs a total concept.

###  2.4 Sample Compression Scheme of [MY16]

The $O(d_{\mathrm{VC}}\cdot 2^{d_{\mathrm{VC}}})$-sized compression scheme of
[MY16] requires crucially using the uniform convergence principle [VC15] and
also a bound on the dual VC dimension of binary classes having finite VC
dimension. These ingredients are combined with a clever application of von
Neumann’s minimax theorem [vN28] to yield their sample compression scheme.
While they are able to use their compression scheme for binary classes in a
blackbox manner to derive compression schemes for certain multiclass
hypothesis classes having finite graph dimension, the graph dimension does not
characterize multiclass learnability (more on this in Section 4.1). Instead,
we discuss here why their techniques don’t translate directly to the
multiclass setting in light of the DS dimension being the more relevant
dimension of interest, as shown by [BCD+22].

Firstly, the principle of uniform convergence ceases to hold in the multiclass
setting, and the sample complexity of different ERM (Empirical Risk Minimizer)
learners can differ by an arbitrarily large factor when the the number of
labels is infinite [DSBDSS15]. Moreover, the compression scheme of [MY16]
crucially makes use of proper learners for binary classes i.e., learning
algorithms whose output hypotheses always belong to the class. On the other
hand, proper learners provably cannot learn multiclass hypothesis classes
[DSS14]! Additionally, for binary classes having VC dimension
$d_{\mathrm{VC}}$, the dual VC dimension of the class is bounded above by
$2^{d_{\mathrm{VC}}+1}$ [Ass83]. However, in the multiclass setting, the
corresponding dual DS dimension may not be bounded above by any finite
function of the DS dimension (see Table 1 for illustration)! In particular, we
can have every concept in the class use its own set of labels, disjoint from
any other concept’s labels. If we do this, then it is easy to see that the
class cannot DS-shatter any pair of points. However, the dual class can
readily DS-shatter arbitrarily large sets.

$\overline{\mathcal{H}}$ $\mathcal{X}$ | $x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{4}$ | $x_{5}$ | $x_{6}$ | …
---|---|---|---|---|---|---|---
$\overline{h}_{1}$ | 1 | 1 | 1 | 1 | 1 | 2 | …$\in\\{1,2\\}$
$\overline{h}_{2}$ | 3 | 3 | 3 | 3 | 4 | 3 | …$\in\\{3,4\\}$
$\overline{h}_{3}$ | 5 | 5 | 5 | 6 | 5 | 5 | …$\in\\{5,6\\}$
$\overline{h}_{4}$ | 7 | 7 | 8 | 7 | 7 | 7 | …$\in\\{7,8\\}$
$\overline{h}_{5}$ | 9 | 10 | 9 | 9 | 9 | 9 | …$\in\\{9,10\\}$
Table 1: Every hypothesis in $\overline{\mathcal{H}}$ uses its own unique set
of two labels. Thus, no pair $(x_{j},x_{k})$ can be DS-shattered by
$\overline{\mathcal{H}}$. However, notice how the dual class (wherein
$\overline{h}_{j}$’s (rows) become the input domain, and $x_{j}$’s (columns)
form the hypothesis class) can easily realize $i$-neighbors (as in Definition
4). In particular, we can see that the dual hypotheses corresponding to
$x_{2},x_{3},x_{4},x_{5},x_{6}$ each disagree with the dual hypothesis
corresponding to $x_{1}$ at exactly one of
$\overline{h}_{1},\overline{h}_{2},\overline{h}_{3},\overline{h}_{4},\overline{h}_{5}$.
We can easily add the remaining dual hypotheses (i.e., columns) to complete
the DS-shattering of
$\\{\overline{h}_{1},\overline{h}_{2},\overline{h}_{3},\overline{h}_{4},\overline{h}_{5}\\}$.
Similarly, we can even add new rows, each with its own set of labels, and
realize arbitrarily large dual DS dimension.

Due to these reasons, it seems apparent that the techniques from [MY16] don’t
port over to the multiclass setting, at least in a straightforward manner. In
fact, our main result (Theorem 1), which we will now proceed towards proving,
shows that this pursuit of constructing a bounded-DS dimension sample
compression scheme in the multiclass setting is indeed fruitless.

##  3 Lower Bound via Disambiguation

The main ingredient we use to establish Theorem 1 is the following result from
the work of [AHHM22], which refutes the sample compression conjecture for
binary partial concept classes. While [AHHM22] stated their result only for
$\mathcal{Y}=\\{0,1\\}$, we can freely think of the label set in their
construction to be $\mathcal{Y}=\\{0,1,2,\dots\\}$ instead, where we don’t use
the extra labels available at any point. Walking through their proof pointwise
then already gives a lower bound for sample compression in (multiclass)
partial concept classes. Moreover, as mentioned above, if we only ever use
$\\{0,1\\}$ labels, DS-shattering is equivalent to VC-shattering. With these
considerations, we can state the result from [AHHM22] in the following form
(for completeness, we provide a proof in Appendix A):

######  Lemma 3.1 (Theorem 7 in [AHHM22]).

There exists a partial concept class
$\mathcal{H}\subseteq\\{\mathcal{Y}\cup\\{\star\\}\\}^{\mathcal{X}}$ where
$\mathcal{Y}=\\{0,1,2,\dots\\}$ that has the following properties:

  1. 1.

$\forall h\in\mathcal{H},~{}\forall
x\in\mathcal{X},~{}h(x)\in\\{0,1,\star\\}$,

  2. 2.

$\mathcal{H}=\bigcup_{n=1}^{\infty}H_{n}$ where each
$\mathcal{H}_{n}\subseteq\\{\mathcal{Y}\cup\\{\star\\}\\}^{\mathcal{X}}$,

  3. 3.

$|\mathcal{H}_{n}|,|\mathrm{supp}(\mathcal{H}_{n})|<\infty$ for every $n$,

  4. 4.

$\mathrm{supp}(\mathcal{H}_{n})\cap\mathrm{supp}(\mathcal{H}_{m})=\emptyset$
for every $n\neq m$,

  5. 5.

$d_{DS}(\mathcal{H}_{n})=1$ for every $n$,

  6. 6.

$d_{DS}(\mathcal{H})=1$,

and additionally satisfies: any sample compression scheme for $\mathcal{H}$
must have size $\Omega((\log(m))^{1-o(1)})$, where $m$ is the size of an input
sequence realizable by $\mathcal{H}$, and the $o(1)$ term goes to 0 as
$m\to\infty$. In particular, there does not exist a sample compression scheme
for $\mathcal{H}$ having a size that is a finite function solely of the DS
dimension of $\mathcal{H}$.

Now, we make a simple observation: as a consequence of the definition of
disambiguation (Definition 3), sequences realizable by a disambiguating total
class are necessarily a superset of the sequences realizable by the
corresponding partial class. This leads to the following proposition, whose
proof is immediate from the definitions of sample compression and
disambiguation.

######  Proposition 3.2 (Compression monotonic in disambiguation).

Let $\mathcal{H}\subseteq\\{\mathcal{Y}\cup\\{\star\\}\\}^{\mathcal{X}}$ be a
partial concept class and
$\overline{\mathcal{H}}\subseteq\mathcal{Y}^{\mathcal{X}}$ be a total concept
class that disambiguates $\mathcal{H}$. Then, if there exists a sample
compression scheme $(\kappa,\rho)$ for $\overline{\mathcal{H}}$ of size $k$,
then $(\kappa,\rho)$ is also a sample compression scheme for $\mathcal{H}$.

There is now a natural strategy to prove a sample compression lower bound for
total concept classes: find a partial concept class of small DS dimension that
is hard to compress to a small size. Then, construct a disambiguation of this
class to a total concept class. Given the proposition above, the
disambiguating class would be at least as hard to compress as the partial
class. However, we would want the DS dimension of the disambiguating class to
also be small, in order for the lower bound to be meaningful.

The first ingredient in the above strategy is already available to us — choose
the partial class $\mathcal{H}$ given by Lemma 3.1 that has DS dimension 1.
The crucial task that remains is constructing a disambiguation
$\overline{\mathcal{H}}$ of $\mathcal{H}$ that also has small DS dimension.
But given the power of conjuring new labels at will in the multiclass setting,
this is not all too hard — we can construct a disambiguating
$\overline{\mathcal{H}}$ that also has DS dimension 1 in a straightforward
manner. We disambiguate each partial concept $h\in\mathcal{H}$ with a total
concept $\overline{h}$ that assigns the $\star$’s in $h$ a unique label which
is never again used by any other disambiguating concept. This preserves the DS
dimension of the disambiguating class.

######  Lemma 3.3 (Disambiguation with no DS blow-up).

There exists a total concept class
$\overline{\mathcal{H}}\subseteq\mathcal{Y}^{\mathcal{X}}$ where
$\mathcal{Y}=\\{0,1,2,\dots\\}$ such that $\overline{\mathcal{H}}$
disambiguates $\mathcal{H}$ from Lemma 3.1 above and satisfies
$d_{\mathrm{DS}}(\overline{\mathcal{H}})=1$.

###### Proof.

Recall that $\mathcal{H}=\bigcup_{n=1}^{\infty}\mathcal{H}_{n}$, where each
$|\mathcal{H}_{n}|<\infty$. This means that $\mathcal{H}$ is countably large.
Let $h_{1},h_{2},h_{3},\dots$ be an enumeration of all the concepts in
$\mathcal{H}$. Then, for each $i\in\\{1,2,\dots\\}$, define the total concept
$\overline{h}_{i}:\mathcal{X}\to\mathcal{Y}$ as follows

$\displaystyle\overline{h}_{i}(x)=\begin{cases}h_{i}(x)&\text{if
}h_{i}(x)\neq\star,\\\ i+1&\text{otherwise.}\end{cases}$

Consider the total concept class
$\overline{\mathcal{H}}=\bigcup_{i=1}^{\infty}\overline{h}_{i}$. By
construction, $\overline{\mathcal{H}}$ disambiguates $\mathcal{H}$. Further,
any sequence DS-shattered by the partial class is certainly also DS-shattered
by $\overline{\mathcal{H}}$, and hence
$d_{\mathrm{DS}}(\overline{\mathcal{H}})\geq 1$. Now, let
$S=\\{x_{1},\dots,x_{d}\\}$ be any sequence that is DS-shattered by
$\overline{\mathcal{H}}$. Then, according to Definition 4 above, let
$\overline{\mathcal{F}}=\\{\overline{f}_{1},\dots\overline{f}_{m}\\}\subseteq\overline{\mathcal{H}}$
be the finite subset of $\overline{\mathcal{H}}$ that realizes this
shattering. Namely, if we think of all the distinct patterns
$\overline{f}_{1}|_{S},\overline{f}_{2}|_{S},\dots,\overline{f}_{m}|_{S}$ that
$\overline{\mathcal{F}}$ realizes on $S$, then every pattern
$\overline{f}_{i}|_{S}$ has a neighbor $\overline{f}_{j}|_{S}$ in every
direction $l\in[d]$ ($\overline{f}_{i}|_{S}$ and $\overline{f}_{j}|_{S}$ are
the same everywhere but at index $l$). There can be two cases: either every
string $\overline{f}_{i}|_{S}$ is such that
$\overline{f}_{i}|_{S}\in\\{0,1\\}^{d}$. But this would mean that the partial
concepts $\\{f_{1},\dots,f_{d}\\}$ themselves realize the DS-shattering of
$S$, implying that $d\leq 1$. In the other case, there is some
$\overline{f}_{i}$ which satisfies $\overline{f}_{i}(x_{l})\in\\{2,3,\dots\\}$
for some $l\in[d]$. But now observe that no other function in
$\overline{\mathcal{H}}$ other than $\overline{f}_{i}$ attains the label
$\overline{f}_{i}(x_{l})$ on $x_{l}$ — this is merely an artefact of our
construction of $\overline{\mathcal{H}}$. In particular, this means that
$\overline{\mathcal{H}}$ cannot realize a neighbor for $\overline{f}_{i}|_{S}$
in any direction other than $l$, meaning also that $d\leq 1$. This completes
the proof that $d_{\mathrm{DS}}(\overline{\mathcal{H}})\leq 1$. ∎

######  Remark 2.

Lemma 3.3, Proposition 3.2 and Lemma 3.1 together imply Theorem 1.

##  4 Discussion

We showed that unlike the binary setting, compression and learnability are not
equivalent in the multiclass learning setting. Namely, if we are allowed
infinite labels, it is possible that a hypothesis class is learnable, but the
size of a compressed sample must necessarily scale with the size of the
original sample, and cannot be independent of it. Our result illustrates a
separation between the paradigms of compression and learnability in the binary
and multiclass settings. In the following, we discuss the relevance of our
result in the context of a past result on multiclass compression by [MY16],
and also discuss why similar techniques as above do not work in order to prove
lower bounds for sample compression via disambiguations that are only allowed
to use binary labels.

###  4.1 Upper Bound from [MY16]

As mentioned above, the seminal work of [MY16] answered the question “does
learnability imply compression?” in the affirmative for binary hypothesis
classes. Namely, for any binary hypothesis class of VC dimension
$d_{\mathrm{VC}}$, [MY16] construct a sample compression scheme of size
$O(d_{\mathrm{VC}}\cdot 2^{d_{\mathrm{VC}}})$. In fact, there is a nice
reduction (outlined in Appendix B for completeness) from the multiclass
setting to the binary setting that allows them to use their compression scheme
as is, and obtain a sample compression scheme of size $O(d_{G}\cdot
2^{d_{G}})$ for any (multiclass) hypothesis class, where $d_{G}$ is the graph
dimension of the class. The graph dimension $d_{G}$ is defined as follows:

######  Definition 6 (Graph dimension [Nat89]).

Let $\overline{\mathcal{H}}\subseteq\mathcal{Y}^{\mathcal{X}}$ be a hypothesis
class and let $S\in\mathcal{X}^{d}$ be a sequence. We say that
$\overline{\mathcal{H}}$ G-shatters $S$ if there exists an
$\overline{f}\in\overline{\mathcal{H}}$ (which realizes the $G$-shattering),
such that for every subsequence $T\subseteq S$, there exists an
$\overline{h}\in\overline{\mathcal{H}}$ such that

$\displaystyle\forall x\in T,~{}\overline{h}(x)=\overline{f}(x),\;\text{and
}\forall x\in S\setminus T,~{}\overline{h}(x)\neq\overline{f}(x).$

The size of the largest sequence that $\overline{\mathcal{H}}$
G-shatters333Note that just like DS-shattering, $G$-shattering is also
equivalent to VC-shattering when $\mathcal{Y}=\\{0,1\\}$. is called the graph
dimension of $\overline{\mathcal{H}}$, denoted as
$d_{G}(\overline{\mathcal{H}})$.

However, even if it is the case that a hypothesis class always permits a
sample compression scheme of size $O(d_{G}\cdot 2^{d_{G}})$, the graph
dimension $d_{G}$ need not necessarily be finite for a learnable hypothesis
class when the label space is allowed to be infinitely large. In particular,
[DSS14] constructed a learnable hypothesis class $\overline{\mathcal{H}}$ that
has $d_{G}(\overline{\mathcal{H}})=\infty$. This is precisely why the
compression scheme of [MY16] in terms of the graph dimension does not allow
them to immediately conclude that “learnability implies compression” in the
multiclass case. Furthermore, our lower bound does not contradict their upper
bound. This is because the disambiguation we construct in Lemma 3.3 above only
preserves the DS dimension444and also, the Natarajan dimension [Nat89], which
is also required to be finite for PAC learnability.. On the other hand, the
graph dimension of the disambiguating class can (and must) increase
arbitrarily, so that the $O(d_{G}\cdot 2^{d_{G}})$ bound is still a valid (but
not meaningful) upper bound on the size of the compression scheme. Here is a
simple example to see why this might be the case: fix a sequence
$S=\\{x_{1},x_{2},x_{3}\\}$, and say that some $h$ in the partial class
$\mathcal{H}$ realizes the pattern $(0,0,0)$ on this sequence. Say also that
the set of distinct patterns that is realized on $S$ by the rest of the
partial concepts in $\mathcal{H}$ is
$(\star,0,0),(0,\star,0),(0,0,\star),(\star,\star,0),(\star,0,\star),(0,\star,\star),(\star,\star,\star)$.
Observe that this sequence is not remotely (DS/VC) shattered by the partial
class. Now, let us think of the patterns that the disambiguating class
realizes on this sequence. Since each total concept in the disambiguating
class labels the $\star$’s in the partial concept it represents with a
distinct number, the patterns on $S$ realized by $\overline{\mathcal{H}}$
would be something like:

$\displaystyle(0,0,0)$ $\displaystyle\longrightarrow\;$ $\displaystyle(0,0,0)$
$\displaystyle(\star,0,0)$ $\displaystyle\longrightarrow\;$
$\displaystyle(3,0,0)$ $\displaystyle(0,\star,0)$
$\displaystyle\longrightarrow\;$ $\displaystyle(0,7,0)$
$\displaystyle(0,0,\star)$ $\displaystyle\longrightarrow\;$
$\displaystyle(0,0,11)$ $\displaystyle(\star,\star,0)$
$\displaystyle\longrightarrow\;$ $\displaystyle(20,20,0)$
$\displaystyle(\star,0,\star)$ $\displaystyle\longrightarrow\;$
$\displaystyle(39,0,39)$ $\displaystyle(0,\star,\star)$
$\displaystyle\longrightarrow\;$ $\displaystyle(0,53,53)$
$\displaystyle(\star,\star,\star)$ $\displaystyle\longrightarrow\;$
$\displaystyle(100,100,100).$

We can readily see that $S$ is G-shattered by $\overline{\mathcal{H}}$
($\overline{h}$ realizes the $G$-shattering). This phenomenon must indeed be
occurring at a larger scale — arbitrarily large sequences must be getting
G-shattered by $\overline{\mathcal{H}}$ in the manner illustrated above, so as
to ensure that the $O(d_{G}\cdot 2^{d_{G}})$ upper bound does not contradict
our lower bound from Theorem 1.

###  4.2 Disambiguation Using Only {0,1} Labels

In the disambiguation that we constructed above, we crucially used the power
of multiple labels available to us. In fact, this was necessary. If instead,
we were constrained to only consider disambiguations that label $\star$’s with
either 0 or 1, we cannot hope to preserve the DS (or rather VC) dimension of
the disambiguating class. This is immediate from Theorem 1 in [AHHM22], which
says that any binary (total) concept class disambiguating the partial class
from Lemma 3.3 must have infinite VC (= DS) dimension. Thus, this approach
with binary disambiguators will only let us derive a lower bound on the
compression size for what has now become an unlearnable class, a not-so-
interesting result. In contrast, and perhaps intriguingly, disambiguating with
multiple (or in our case, infinite) labels allows us to retain the
learnability of the disambiguating class, while also inheriting the lower
bound on the compression size from the underlying partial class.

## Acknowledgements

I am deeply grateful to Moses Charikar for his discussions and valuable
feedback on the manuscript. This work is supported by Moses’ Simons
Investigator Award, and NSF awards 1704417 and 1813049.

## References

  * [AHHM22] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran.  A theory of pac learnability of partial concept classes.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658–671. IEEE, 2022.
  * [Ass83] Patrick Assouad.  Densité et dimension.  In Annales de l’Institut Fourier, volume 33, pages 233–282, 1983\.
  * [BBDG+22] Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, and Robin Kothari.  Unambiguous dnfs and alon-saks-seymour.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 116–124. IEEE, 2022.
  * [BCD+22] Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff.  A characterization of multiclass learnability.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 943–955. IEEE, 2022.
  * [BDHT17] Shalev Ben-David, Pooya Hatami, and Avishay Tal.  Low-sensitivity functions from unambiguous certificates.  In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67, page 28. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017.
  * [BEHW89] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth.  Learnability and the vapnik-chervonenkis dimension.  Journal of the ACM (JACM), 36(4):929–965, 1989.
  * [BLT14] Nicolas Bousquet, Aurélie Lagoutte, and Stéphan Thomassé.  Clique versus independent set.  European Journal of Combinatorics, 40:73–92, 2014.
  * [DMY16] Ofir David, Shay Moran, and Amir Yehudayoff.  On statistical learning via the lens of compression.  arXiv preprint arXiv:1610.03592, 2016.
  * [DSBDSS15] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz.  Multiclass learnability and the erm principle.  J. Mach. Learn. Res., 16(1):2377–2404, 2015.
  * [DSS14] Amit Daniely and Shai Shalev-Shwartz.  Optimal learners for multiclass problems.  In Conference on Learning Theory, pages 287–316. PMLR, 2014.
  * [Fre95] Yoav Freund.  Boosting a weak learning algorithm by majority.  Information and computation, 121(2):256–285, 1995.
  * [FS97] Yoav Freund and Robert E Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  Journal of computer and system sciences, 55(1):119–139, 1997.
  * [Göö15] Mika Göös.  Lower bounds for clique vs. independent set.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1066–1076. IEEE, 2015.
  * [Kah91] Jeff Kahn.  Recent results on some not-so-recent hypergraph matching and covering problems.  DIMACS, Center for Discrete Mathematics and Theoretical Computer Science, 1991.
  * [LW86] Nick Littlestone and Manfred Warmuth.  Relating data compression and learnability.  1986\.
  * [MSWY17] Shay Moran, Amir Shpilka, Avi Wigderson, and Amir Yehudayoff.  Teaching and compressing for low vc-dimension.  In A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, pages 633–656. Springer, 2017.
  * [MY16] Shay Moran and Amir Yehudayoff.  Sample compression schemes for vc classes.  Journal of the ACM (JACM), 63(3):1–10, 2016.
  * [Nat89] Balas K Natarajan.  On learning sets and functions.  Machine Learning, 4:67–97, 1989.
  * [Val84] Leslie G Valiant.  A theory of the learnable.  Communications of the ACM, 27(11):1134–1142, 1984.
  * [VC74] Vladimir Vapnik and Alexey Chervonenkis.  Theory of pattern recognition, 1974.
  * [VC15] Vladimir N Vapnik and A Ya Chervonenkis.  On the uniform convergence of relative frequencies of events to their probabilities.  In Measures of complexity, pages 11–30. Springer, 2015.
  * [vN28] J v. Neumann.  Zur theorie der gesellschaftsspiele.  Mathematische annalen, 100(1):295–320, 1928.
  * [War03] Manfred K Warmuth.  Compressing to vc dimension many points.  In COLT, volume 3, pages 743–744. Springer, 2003.

##  Appendix A Proof of Lemma 3.1

In this section, we essentially rewrite the proof by [AHHM22], which is a
beautiful reduction from a recent breakthrough result by [BBDG+22], which in
turn builds upon the works of [BDHT17, Göö15] to show a nearly tight bound for
the Alon-Saks-Seymour problem [Kah91, BLT14].
[AHHM22] translate the result by [BBDG+22] into the construction of a partial
concept class that is hard to disambiguate with a small total class, and also
consequently hard to compress.

###  A.1 A Partial Class That is Hard to Disambiguate

We recall some concepts from graph theory. Given a graph $G=(V,E)$, the
chromatic number $\chi(G)$ of $G$ is the minimum number of colors required,
such that each vertex can be assigned a color in a way that no two vertices
connected by an edge have the same color assigned to them. The biclique
partition number $\mathrm{bp}(G)$ is the minimum number of complete bipartite
graphs required to successfully partition the edge set $E$ of $G$. Each
complete bipartite graph in the decomposition consists of all the vertices in
$V$ (some possibly isolated, but the rest forming a complete bipartite graph)
and a subset of the edges in $E$. [BBDG+22] proved the following result
relating these two quantities, in response to a problem originally posed by
Alon, Saks and Seymour [Kah91]:

######  Theorem 2 (Corollary 3 in [BBDG+22]).

For every $n$, there exists a finite simple graph $G=(V,E)$ with
$\mathrm{bp}(G)=n$ such that

$\displaystyle\chi(G)\geq n^{(\log(n))^{1-o(1)}},$

where the $o(1)$ term goes to $0$ as $n\to\infty$.

Now, we describe the clever reduction by [AHHM22], who leverage the lower
bound result above to construct a partial concept class that is hard to
disambiguate with a small total concept class. Given $n$, let $G=(V,E)$ be the
graph promised by Theorem 2, and let $B_{i}=(L_{i},R_{i},E_{i})$ be $n$
complete bipartite graphs (identified with numbers in $[n]$) that witness the
partitioning of the edge set of $G$ such that $\mathrm{bp}(G)=n$, and the edge
sets $E_{i}$ are pairwise disjoint. Let $\mathcal{Y}=\\{0,1,2,\dots\\}$, and
define the multiclass partial concept class
$\mathcal{H}_{n}\subseteq\\{\mathcal{Y}\cup\\{\star\\}\\}^{[n]}$ as follows:
for each vertex $v\in V$, $\mathcal{H}_{n}$ contains a partial concept $h_{v}$
such that for each $i\in[n]$,

$h_{v}(i)=\begin{cases}0&\text{if }v\in L_{i},\\\ 1&\text{if }v\in R_{i},\\\
\star&\text{otherwise}.\end{cases}$ (2)

Since $\\{0,1\\}$ are the only non-$\star$ labels in $\mathcal{H}_{n}$, DS-
shattering reduces to VC-shattering. We have the following two lemmas:

######  Lemma A.1 (Lemma 31 in [AHHM22]).

$\mathrm{DS}(\mathcal{H}_{n})=1$.

###### Proof.

Since there exists at least one edge in $G$, the hypotheses corresponding to
the endpoints of this edge shatter a set of size 1, and hence
$\mathrm{DS}(\mathcal{H}_{n})\geq 1$. We will show that for any $i\neq j$,
$\mathcal{H}_{n}$ cannot simultaneously realize the patterns $(0,0)$ and
$(1,1)$ on $(i,j)$, implying that $\mathrm{DS}(\mathcal{H}_{n})<2$. Towards a
contradiction, assume that some $h_{u}$ satisfies $h_{u}(i)=0$ and
$h_{u}(j)=0$. From $\eqref{eqn:pcc-def}$ above, this means that $u\in L_{i}$
and $u\in L_{j}$. Now, assume also that some $h_{v}$ satisfies $h_{v}(i)=1$
and $h_{v}(j)=1$. This means that $v\in R_{i}$ and $v\in R_{j}$. But since the
bipartite components $B_{i}$ are complete, this means that the edge $(u,v)$
exists in both $B_{i}$ and $B_{j}$, contradicting the disjointedness of the
edge sets $E_{i}$ and $E_{j}$. ∎

######  Lemma A.2 (Lemma 32 in [AHHM22]).

Let $\overline{\mathcal{H}}_{n}\in\mathcal{Y}^{[n]}$ be a total concept class
that disambiguates $\mathcal{H}_{n}$. Then, $\overline{\mathcal{H}}_{n}$
defines a coloring of $G$ using $|\overline{\mathcal{H}}_{n}|$ colors.
Therefore, from Theorem 2 above,

$\displaystyle|\overline{\mathcal{H}}_{n}|\geq n^{(\log(n))^{1-o(1)}}.$

###### Proof.

Let $\overline{h}_{v}\in\overline{\mathcal{H}}_{n}$ be the total concept that
disambiguates $h_{v}\in\mathcal{H}_{n}$ i.e., every sequence realizable by
$h_{v}$ is also realizable by $\overline{h}_{v}$. Then, we identify the
concept $\overline{h}_{v}$ with a unique color $Id(\overline{h}_{v})$, and
assign the vertex $v$ this color. This defines a candidate coloring of the
vertices of $G$. It remains to argue that no two endpoints of any edge in $G$
are assigned the same color. Indeed, let $(u,v)$ be en edge in $G$. Then, this
edge necessarily exists in exactly one of the bipartite components
$B_{i}=(L_{i},R_{i},E_{i})$, meaning that either $h_{u}(i)=0,h_{v}(i)=1$ or
$h_{u}(i)=1,h_{v}(i)=0$. Whatever be the case, $h_{u}$ and $h_{v}$ necessarily
disagree on $i$, and therefore so do their disambiguators $\overline{h}_{u}$
and $\overline{h}_{v}$, implying $Id(\overline{h}_{u})\neq
Id(\overline{h}_{v})$. ∎

Now, for each $n$, we can instantiate $\mathcal{H}_{n}$ as defined above, each
having its own separate domain, and extend the domain of every
$\mathcal{H}_{n}$ to the union of the domains as follows: every
$h\in\mathcal{H}_{n}$ labels the domain of any other $\mathcal{H}_{m}$
entirely with $\star$. For the domain-extended $\mathcal{H}_{n}$’s thus
defined, by construction, we have that
$\mathrm{supp}(\mathcal{H}_{n})\cap\mathrm{supp}(\mathcal{H}_{m})=\emptyset$
for all $n\neq m$. Furthermore, since each $\mathcal{H}_{n}$ has a support of
size $n$ and is based on a finite simple graph, we already have
$|\mathcal{H}_{n}|,|\mathrm{supp}(\mathcal{H}_{n})|<\infty$. Let
$\mathcal{H}=\bigcup_{n=1}^{\infty}\mathcal{H}_{n}$. Since any shattered
sequence would have to entirely lie in the support of a single
$\mathcal{H}_{n}$, by Lemma A.1 above, we also have that
$\mathrm{DS}(\mathcal{H})=1$. This justifies all the points describing
$\mathcal{H}$ in Theorem 1.

###  A.2 Compression Implies Disambiguation

The following lemma shows that sample compression schemes imply
disambiguations of bounded size for partial concept classes.

######  Lemma A.3 (Proposition 14 in [AHHM22]).

For $\mathcal{Y}=\\{0,1,2,\dots\\}$, let
$\mathcal{H}\in\\{\mathcal{Y}\cup\\{\star\\}\\}^{\mathcal{X}}$ be such that

  1. 1.

$\forall h\in\mathcal{H},~{}\forall
x\in\mathcal{X},~{}h(x)\in\\{0,1,\star\\}$,

  2. 2.

$|\mathrm{supp}(\mathcal{H})|\leq n$.

Then, if $(\kappa,\rho)$ is a sample compression scheme for $\mathcal{H}$ of
(unqualified) size $k$, then there exists a disambiguation of $\mathcal{H}$ of
size at most $(4n)^{k+1}$.

###### Proof.

By definition of a compression scheme, $\kappa$ must be able to compress the
support of every $h\in\mathcal{H}$ to a short labeled sequence of size at most
$k$, such that the output of $\rho$ on this short sequence (together with some
appropriate bit string of size at most $k$) correctly labels the entire
support of $h$. Thus, if we iterate over all possible realizable sequences and
bit strings of size at most $k$, the reconstruction by $\rho$ on all of these
necessarily disambiguates every single partial concept in $\mathcal{H}$. The
total number of bit strings of size at most $k$ is $<2^{k+1}$. Next, since
$|\mathrm{supp}(\mathcal{H})|\leq n$, the total number of configurations that
we need to apply $\rho$ to is at most $\sum_{i=0}^{k}n^{i}\cdot 2^{i}\cdot
2^{k+1}$ (choose a sequence of $i$ elements from $\mathrm{supp}(\mathcal{H})$,
label it in one of $2^{i}$ possible ways, and append a bit string of size at
most $k$ to it), which is at most $(4n)^{k+1}$ as required.

∎

###  A.3 Putting Things Together

Say there exists a compression scheme $(\kappa,\rho)$ for $\mathcal{H}$
defined in Section A.1 above that compresses labeled sequences of size $m$ to
size $k(m)$. Then, observe that $(\kappa,\rho)$ defines a compression scheme
of (unqualified) size $k=k(m)$ for $\mathcal{H}_{m}$ (for any sequence
realizable by $\mathcal{H}_{m}$, which must be of size at most $m$, elongate
the sequence (if required) to have size exactly $m$ with duplicate elements,
and $(\kappa,\rho)$ now correctly compresses-reconstructs it). From Lemma A.3
above, this implies a disambiguation of $\mathcal{H}_{m}$ of size at most
$(4m)^{k(m)+1}$. But then, Lemma A.2 necessitates that

$\displaystyle(4m)^{k(m)+1}\geq m^{(\log(m))^{1-o(1)}}$

which gives us that $k(m)=\Omega((\log(m))^{1-o(1)})$ as required.

##  Appendix B Sample Compression Scheme in Terms of Graph Dimension

We elaborate on the reduction from sample compression schemes for binary
hypothesis classes to those for multiclass hypothesis classes from Section 4.1
from [MY16]. Given a hypothesis class
$\overline{\mathcal{H}}:\mathcal{X}\to\mathcal{Y}$ having graph dimension
$d_{G}$, construct the binary hypothesis class
$\overline{\mathcal{H}}^{\prime}:(\mathcal{X}\times\mathcal{Y})\to\\{0,1\\}$,
defined as follows:
$\overline{\mathcal{H}}^{\prime}=\\{\overline{h}^{\prime}:\overline{h}\in\overline{\mathcal{H}}\\}$
where $\overline{h}^{\prime}$ is defined as follows:

$\displaystyle\overline{h}^{\prime}(x,y)=\begin{cases}1&\text{if
}\overline{h}(x)=y,\\\ 0&\text{otherwise.}\end{cases}$

We can then see that
$d_{\mathrm{VC}}(\overline{\mathcal{H}}^{\prime})=d_{G}(\overline{\mathcal{H}})$.
Now, given a sample $S=\\{(x_{1},y_{1}),\dots,(x_{m},y_{m})\\}$ realizable by
$\overline{\mathcal{H}}$, the compressor constructs the sequence
$S^{\prime}=\\{((x_{1},y_{1}),1),\dots,((x_{m},y_{m}),1)\\}$ that is
realizable by $\overline{\mathcal{H}}^{\prime}$. Theorem 1.4 in [MY16] then
implies that there exists a sample compression scheme of size $O(d_{G}\cdot
2^{d_{G}})$ for $\overline{\mathcal{H}}^{\prime}$. Namely, let
$\mathrm{ERM}_{\overline{\mathcal{H}}^{\prime}}(S^{\prime})$ be any hypothesis
in $\overline{\mathcal{H}}^{\prime}$ entirely consistent with $S^{\prime}$.
Then, there exist subsequences $S^{\prime}_{1},\dots,S^{\prime}_{t}$ of
$S^{\prime}$ (where $t=O(2^{d_{G}})$) each of size $O(d_{G})$ such that the
majority vote of
$\mathrm{ERM}_{\overline{\mathcal{H}}^{\prime}}(S^{\prime}_{1}),\dots,\mathrm{ERM}_{\overline{\mathcal{H}}^{\prime}}(S^{\prime}_{t})$
is 1 on every $(x_{i},y_{i})$ pair in $S^{\prime}$. This equivalently means
that the majority vote of
$\mathrm{ERM}_{\overline{\mathcal{H}}}(S_{1}),\dots,\mathrm{ERM}_{\overline{\mathcal{H}}}(S_{t})$
is the correct label $y_{i}$ for every $x_{i}$ in $S$. Thus, the compressor
compresses $S$ to $S_{1},\dots,S_{t}$ (along with a bit string of size
$O(d_{G}\cdot 2^{d_{G}})$ specifying splits), and the reconstructor invokes
ERM on each $S_{i}$ and takes the majority vote to obtain correct predictions
on all of $S$.


# Revisiting magnetotransport in Weyl semimetals

G. Sharma  School of Basic Sciences, Indian Institute of Technology Mandi,
Mandi 175005, India  Snehashish Nandy  Department of Physics, University of
Virginia, Charlottesville, Virginia 22904, USA  Karthik V. Raman  Tata
Institute of Fundamental Research, Hyderabad, Telangana 500046, India  Sumanta
Tewari  Department of Physics and Astronomy, Clemson University, Clemson,
South Carolina 29634, USA

###### Abstract

A series of recent papers have claimed that intranode scattering, alone, can
contribute to positive longitudinal magnetoconductance (LMC) due to chiral
anomaly (CA) in Weyl semimetals (WSMs). We revisit the problem of CA induced
LMC in WSMs, and show that intranode scattering, by itself, does not result in
enhancement of LMC. In the limit of zero internode scattering, chiral charge
must remain conserved, which is shown to actually decrease LMC. Only in the
presence of a non-zero internode scattering (however weak), one obtains a
positive LMC due to non-conservation of chiral charge. Even weak internode
scattering suffices in generating positive LMC, since it redistributes charges
across both the nodes, although on a time scale larger than that of the
intranode scattering. Furthermore, our calculations reveal that, in contrast
to recent works, in inhomogeneous WSMs strain induced axial magnetic field
$B_{5}$, by itself, leads to negative longitudinal magnetoconductance and a
negative planar Hall conductance.

Introduction: Chiral anomaly (CA) finds its genesis in high-energy physics [1,
2], whereby the left/right-handed Weyl fermions are not conserved in the
presence of non-orthogonal electric and magnetic fields. The anomaly has
resurged in Weyl semimetals (WSMs), and has been of great interest in the
condensed-matter community over the last decade [3, 4, 5, 6, 7, 8, 9, 10, 11,
12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]. Since Weyl semimetals host Weyl
fermions as quasiparticle excitations, chiral anomaly is expected to occur in
these materials in the presence of external electromagnetic fields. Positive
longitudinal magnetoconductance (LMC) [10], and the planar Hall effect (PHE)
[23] are some key signatures to identify the manifestation of chiral anomaly
in Weyl semimetals. Significant efforts have recently been devoted to capture
the behavior of these anomaly induced conductivities in WSMs [9, 10, 11, 12,
13, 14, 15, 16, 17, 18, 19, 20, 21, 22].

The calculation of conductivity via the linear response formalism [24]
inherently assumes a timescale $\tau_{\phi}$, that can be interpreted as
arising from interactions between the system and the external electric field
that inelastically exchange energy at a rate $1/\tau_{\phi}$. The rate is
assumed to be ideally zero, or in other words, $\tau_{\phi}$ is assumed to be
the largest of all relevant timescales. In the context of weakly disordered
Weyl semimetals, when Landau quantization is relevant at high magnetic fields,
chiral anomaly manifests itself by a positive contribution to the longitudinal
magnetoconductance, i.e., $\mathbf{j}\propto B(\mathbf{E}\cdot\mathbf{B})$,
where $\mathbf{E}$ and $\mathbf{B}$ are the applied electric and magnetic
fields. The current in this case is limited by the internode scattering time
($\tau_{\mathrm{inter}}$), which corresponds to a timescale at which
quasiparticles scatter across the nodes and switch their chirality. Therefore,
chiral charge is not conserved, but the global charge remains conserved. For
linear response formalism to work, $\tau_{\mathrm{inter}}$ must be much less
than $\tau_{\phi}$. Unfortunately, this approach breaks down if one considers
intranode scattering as the only dominant scattering mechanism, since in this
case the chiral charge must remain conserved along with the global charge.

In the limit of weak magnetic field, Son and Spivak [10] highlighted the
importance of internode scattering induced positive LMC in WSMs via the
semiclassical Boltzmann approach. Despite this, a series of recent papers
suggested that intranode scattering, alone, can give rise to positive
longitudinal magnetoconductivity via a $\mathbf{E}\cdot\mathbf{B}$ force term
incorporated in the semiclassical equations of motion [14, 15, 16, 17, 18, 19,
20, 21]. It is therefore implied that positive LMC manifests in WSMs even in
the limit when $\tau_{\mathrm{inter}}/\tau_{\mathrm{intra}}\rightarrow\infty$
(where $\tau_{\mathrm{intra}}$ is the intravalley scattering time).
Importantly, these works also make no distinction between the parameter
regimes $\tau_{\mathrm{intra}}\ll\tau_{\phi}\ll\tau_{\mathrm{inter}}$, and
$\tau_{\mathrm{intra}}\ll\tau_{\mathrm{inter}}\ll\tau_{\phi}$. The distinction
between the two cases actually has drastic consequences, as chiral charge is
conserved in the former, but the latter indicates global charge conservation,
which occurs on a timescale larger than the intravalley timescale
$\tau_{\mathrm{intra}}$, but smaller than $\tau_{\phi}$. The claim that
intranode scattering, alone, can positively increase LMC, inherently assumes
that $\tau_{\mathrm{intra}}\ll\tau_{\phi}\ll\tau_{\mathrm{inter}}$.

In this Letter, we show that the intranode scattering alone cannot yield
positive LMC in WSMs, as this result is inconsistent with chiral charge
conservation. We begin by first showing that semiclassical calculations of LMC
with a momentum-independent scattering time, as is assumed in the recent works
[14, 15, 16, 17, 18, 19, 20], violate chiral charge conservation. Chiral
charge conservation is shown to be consistent only with a momentum-dependent
scattering rate, which, very importantly, yields a $negative$ LMC. We
therefore show that internode scattering is necessary to obtain positive LMC
in Weyl semimetals, as opposed to the recent works. Even very weak internode
scattering drives the system to show positive LMC, and only sufficiently
strong intervalley scattering beyond a critical strength switches the sign to
a negative LMC [21]. Chiral anomaly is therefore an internode phenomena in
WSMs, even in the weak-$B$ limit where the semiclassical formalism is valid,
consistent with the Landau-level picture. Our results also have important
consequences in the context of inhomogeneous WSMs (IWSMs), where we show that
strain, alone, leads to a negative longitudinal magnetoconductance, and
contributes a planar Hall conductance which is of opposite sign to that of an
external magnetic field. These results, which can be experimentally verified,
are also in contrast to some other recent papers [25, 26].

Inconsistencies of momentum-independent scattering time: For a single isolated
Weyl node $H_{\mathbf{k}}=\chi\hbar v_{F}\mathbf{k}\cdot\bm{\sigma}$, the
steady-state Boltzmann equation takes the following form [27]

$\displaystyle e\mathcal{D^{\chi}}_{\mathbf{k}}\left(-\frac{\partial
f_{0}}{\partial\epsilon_{\mathbf{k}}}\right)\left(\mathbf{v}^{\chi}_{\mathbf{k}}+\frac{e}{\hbar}\mathbf{B}(\Omega^{\chi}_{\mathbf{k}}\cdot\mathbf{v}^{\chi}_{\mathbf{k}})\right)\cdot\mathbf{E}=\mathcal{I}_{\mathrm{coll}}\\{f_{\mathbf{k}}\\}$
(1)

where $\mathbf{v}^{\chi}_{\mathbf{k}}$ is the semiclassical band-velocity,
$\mathbf{E}$ and $\mathbf{B}$ are external electric and magnetic fields,
respectively, $\Omega_{\mathbf{k}}^{\chi}$ is the Berry curvature, $f_{0}$ is
the equalibrium Boltzmann distribution, $\epsilon_{\mathbf{k}}$ is the energy,
and
$\mathcal{D}^{\chi}_{\mathbf{k}}=(1+e\mathbf{B}\cdot\Omega^{\chi}_{\mathbf{k}}/\hbar)^{-1}$.
Within the relaxation-time approximation, the collision integral
$\mathcal{I}_{\mathrm{coll}}\\{f_{\mathbf{k}}\\}$ is simply

$\displaystyle\mathcal{I}_{\mathrm{coll}}\\{f_{\mathbf{k}}\\}=-\frac{\delta
f^{\chi}_{\mathbf{k}}}{\tau_{\mathbf{k}}},$ (2)

where $\delta f^{\chi}_{\mathbf{k}}$ is the deviation from the equilibrium.
Particle conservation implies that

$\displaystyle\sum\limits_{\mathbf{k}}\delta f^{\chi}_{\mathbf{k}}=0$ (3)

In the geometry when $\mathbf{E}\parallel\mathbf{B}\parallel\hat{z}$, the
equation for particle conservation, Eq. 3, reduces to the following form [27]:

$\displaystyle\int{\tau^{\chi}(\theta)\left({v}^{\chi}_{z}+\frac{e}{\hbar}{B}(\Omega^{\chi}_{\mathbf{k}}\cdot\mathbf{v}^{\chi}_{\mathbf{k}})\right)\frac{k^{3}(\theta)\sin\theta}{|\mathbf{v}^{\chi}_{\mathbf{k}}\cdot\mathbf{k}|}d\theta}=0.$
(4)

Here all the quantities in the integrand are evaluated on the Fermi surface at
zero temperature. A simplifying approach often employed is to assume that the
scattering time is independent of momentum $\mathbf{k}$, i.e.,
$\tau^{\chi}(\theta)=\tau^{\chi}$ [14, 15, 16, 17, 18, 19, 20]. However, it
can be easily verified from Eq. 4 that when $\tau^{\chi}(\theta)$ is
independent of the polar angle $\theta$, the L.H.S. of the equation does not
reduce to zero! Even if we ignore the contribution due to the orbital magnetic
moment, the integral above still turns out to be non-zero.

For the case with a pair of Weyl nodes of opposite chiralities, if the
internode scattering is assumed to be strictly zero, then particle number must
be conserved on individual Weyl nodes, and thus, the above result of non-
applicability of momentum independent scattering time is valid even for the
case of two Weyl nodes. A momentum-independent scattering time is thus
inconsistent with particle number conservation, at least in the limit of
infinite internode scattering time.

Figure 1: (a) LMC for an isolated Weyl node is always negative due to chiral
charge conservation. (b) $\Lambda^{\chi}(\theta)$ between $0$ and $\pi$ at
$B=1T$. (c) The corresponding normalized deviation in the distribution
function (proportional to $\delta f^{\chi}_{\mathbf{k}}$), which integrates to
zero. Here we choose $\chi=1$.

LMC for zero internode scattering: When internode scattering is zero, it
suffices to calculate the result for a single isolated Weyl node, and the
contribution from both the nodes can be simply summed over. Since we have
shown that the momentum-independent relaxation time is not valid, we instead
choose the collision integral in Eq. 1 to be:

$\displaystyle\mathcal{I}_{\mathrm{coll}}\\{f_{\mathbf{k}}\\}=\sum\limits_{\mathbf{k}^{\prime}}\left(\Lambda^{\chi}_{\mathbf{k}}-\Lambda^{\chi}_{\mathbf{k}^{\prime}}\right)W_{\mathbf{k}\mathbf{k}^{\prime}}.$
(5)

Here the scattering rate $W_{\mathbf{k}\mathbf{k}^{\prime}}$ must not be taken
to be independent of momenta, and without loss of generality, the unknown
function $\Lambda^{\chi}_{\mathbf{k}}$ can be assumed to be

$\displaystyle\Lambda^{\chi}_{\mathbf{k}}=(f^{\chi}_{\mathbf{k}}-h_{\mathbf{k}}^{\chi})\tau_{\mathbf{k}}$
(6)

where
$h^{\chi}_{\mathbf{k}}=\mathcal{D^{\chi}}_{\mathbf{k}}\left({v}^{\chi}_{z}+{e}{\hbar^{-1}}{B}(\Omega^{\chi}_{\mathbf{k}}\cdot\mathbf{v}^{\chi}_{\mathbf{k}})\right)$,
$\tau^{-1}_{\mathbf{k}}=\sum_{\mathbf{k}^{\prime}}W_{\mathbf{k}\mathbf{k}^{\prime}}$,
and the function $f_{\mathbf{k}}^{\chi}$ is the unknown. In the first Born
approximation, and in the simplest case of point-like disorder, the scattering
rate is evaluated to be

$\displaystyle W_{\mathbf{k}\mathbf{k}^{\prime}}$
$\displaystyle=\frac{2\pi}{\hbar}|U|^{2}\delta(\epsilon_{\mathbf{k}}-\epsilon_{F})\times$
$\displaystyle(1+\cos\theta\cos\theta^{\prime}+\sin\theta\sin\theta^{\prime}\cos(\phi-\phi^{\prime})),$
(7)

where $U$ is the strength of the disorder in appropriate units. We emphasize
that the explicit dependence on the direction of momenta, i.e., the polar and
azimuthal angles, which comes from the chirality of the Weyl fermion
wavefunction, survives even in the absence of momentum-dependent disorder
strength $U$. The Boltzmann equation reduces to

$\displaystyle
f^{\chi}(\theta)=\int{F^{\chi}(\theta^{\prime})\tau(\theta)(1+\cos\theta\cos\theta^{\prime})(f^{\chi}(\theta^{\prime})-h^{\chi}(\theta^{\prime}))d\theta^{\prime}},$
(8)

where
$F^{\chi}(\theta)=k^{3}(\theta)(\mathcal{D}^{\chi}_{\theta})^{-1}\sin\theta|\mathbf{v}_{\mathbf{k}}\cdot\mathbf{k}|^{-1}$.
Again, all the quantities in the integrand above are evaluated on the Fermi
surface. To this end, incorporating particle conservation, along with the
following ansatz solves the above Boltzmann transport equation:

$\displaystyle\Lambda^{\chi}(\theta)=\tau(\theta)(a^{\chi}+b^{\chi}\cos\theta-h^{\chi}(\theta)),$
(9)

Finally, the current due to the deviation in equilibrium is evaluated as:

$\displaystyle\mathbf{j}^{\chi}=-e\sum\limits_{\mathbf{k}}{\dot{\mathbf{r}}^{\chi}(\delta
f^{\chi}_{\mathbf{k}})},$ (10)

and the longitudinal conductivity $\sigma_{zz}(B)$ can be evaluated. We define
$\delta\sigma_{zz}(B)=\sigma_{zz}(B)-\sigma^{0}_{zz}$, where $\sigma^{0}_{zz}$
is the zero field conductivity,

Figure 2: (a) LMC for a pair of Weyl nodes of opposite chiralities becomes
negative beyond a critical intervalley scattering strength $\alpha_{c}$. Here
$\alpha$ is increased from 0.1 to 1. (b) The normalized deviation in
distribution functions (proportional to $\delta f^{\chi}_{\mathbf{k}}$) at
both the valleys for three different values of $\alpha$.  Figure 3: Conditions
to observe positive or negative LMC for TR-broken Weyl semimetals.  Figure 4:
(a) Strain induced LMC for a pair of Weyl nodes of opposite chiralities is
always negative. Here $\alpha$ is increased from 0.1 to 1. (b) The normalized
deviation in distribution functions (proportional to $\delta
f^{\chi}_{\mathbf{k}}$) at both the valleys for three different values of
$\alpha$. $B_{5}$ field is chosen parallel to $\mathbf{E}$.

Fig. 1 (a) plots the evaluated LMC, $\delta\sigma_{zz}(B)$ for an isolated
Weyl node, which turns out to be always negative, and independent of the
chirality of the Weyl node. This result is in direct contrast to the recent
papers concluding that intranode scattering alone can produce positive LMC in
WSMs [14, 15, 16, 17, 18, 21, 19, 20]. Fig. 1 (b) plots
$\Lambda^{\chi}(\theta)$ as a function of the polar angle $\theta$, while Fig.
1 (c) plots the normalized distribution function. The distribution function
directly reflects $\delta f^{\chi}_{\mathbf{k}}$, which integrates to zero, as
expected from particle number conservation. Since we assume zero intervalley
scattering, our result is valid in the limit when two Weyl nodes that are
practically uncoupled. In other words the internode scattering time
$\tau_{\mathrm{inter}}$ is largest of all relevant timescales. As a
complementary approach, we also solve this problem using an ansatz free,
numerical solution to the Boltzmann equation, and reproduce the same findings
[27].

LMC with non-zero internode scattering: The collision integral takes the
following form

$\displaystyle\mathcal{I}_{\mathrm{coll}}\\{f_{\mathbf{k}}^{\chi}\\}=\sum\limits_{\mathbf{k}^{\prime}}\sum\limits_{\chi^{\prime}}\left(\Lambda^{\chi}_{\mathbf{k}}-\Lambda^{\chi^{\prime}}_{\mathbf{k}^{\prime}}\right)W^{\chi\chi^{\prime}}_{\mathbf{k}\mathbf{k}^{\prime}},$
(11)

where the scattering rate
$W^{\chi\chi^{\prime}}_{\mathbf{k}\mathbf{k}^{\prime}}$ has internode as well
as intranode scattering. Again, for point-like disorder the scattering rate is
evaluated to be

$\displaystyle W^{\chi\chi^{\prime}}_{\mathbf{k}\mathbf{k}^{\prime}}$
$\displaystyle=\frac{2\pi}{\hbar}|U^{\chi\chi^{\prime}}|^{2}\delta(\epsilon_{\mathbf{k}}-\epsilon_{F})\times$
$\displaystyle(1+\chi\chi^{\prime}(\cos\theta\cos\theta^{\prime}+\sin\theta\sin\theta^{\prime}\cos(\phi-\phi^{\prime}))),$
(12)

where the disorder parameter $U^{\chi\chi^{\prime}}$ allows us to tune the
internode and intranode scattering strengths differently. Hereafter, we denote
the ratio
$|U^{\chi\neq\chi^{\prime}}|^{2}/|U^{\chi=\chi^{\prime}}|^{2}\equiv\alpha$.
The solution presented before is extended for the case of two nodes [27] with
finite internode scattering. Fig. 2 (a) plots LMC for increasing intervalley
scattering strength. We find that LMC for a pair of Weyl nodes of opposite
chiralities becomes negative beyond a critical intervalley scattering strength
$\alpha_{c}$, as also observed in Ref. [21, 22]. This is attributed to orbital
magnetic moment that has opposite effect on the Fermi surfaces of both nodes
[21], and renders them dissimilar in the presence of external magnetic field.

The striking observation here is that even for weak internode scattering, LMC
is positive, as opposed to the case of strictly zero internode scattering. We
also note that the distribution function obtained here for the case of weak
internode scattering is very different from the one obtained in Fig. 1 for the
case of zero internode scattering. In the latter case the deviation of the
distribution function must integrate out to zero at a single node, i.e., the
chiral charge is conserved. This condition is relaxed in the presence of weak
internode scattering, as particles can scatter across nodes, and only the
global charge needs to be conserved.

It must be noted that the Boltzmann transport equation gives the steady-state
solution that is valid in the limit
$t\gg\max\\{\tau_{\mathrm{inter}},\tau_{\mathrm{intra}}\\}$. Hence, the
particles are allowed to scatter and redistribute across both the nodes on a
timescale much less than $\tau_{\phi}$. These observations summon very
important points: (i) intranode scattering, by itself, does not yield positive
LMC due to chiral charge conservation, (ii) finite internode scattering is a
necessary condition for observing positive LMC even in the semiclassical
low-$B$ limit, (iii) chiral anomaly induced positive LMC is therefore a pure
internode phenomenon, reconciling the Boltzmann and the Landau-level picture,
(iv) sufficiently large internode scattering beyond a critical value
$\alpha_{c}$ switches the sign of LMC from positive to negative.
Correspondingly,
$\tau_{\phi}\gg\tau_{\mathrm{inter}}>\tau_{\mathrm{inter}}^{\mathrm{c}}$ is
necessary to observe positive LMC in experiments, where
$\tau_{\mathrm{inter}}^{\mathrm{c}}$ is the critical intervalley scattering
time below which LMC becomes negative. On the other hand, when
$\tau_{\mathrm{inter}}$ becomes less than $\tau_{\phi}$, one must always
observe negative LMC as dictated by $\tau_{\mathrm{intra}}$. Fig. 3 summarizes
the conditions to observe positive and negative LMC.

Figure 5: (a) Minimal model of inversion asymmetric WSM with four nodes.
Chirality of a node is indicated by $\chi$, and internode scattering from node
$i$ to $j$ (and vice-versa) is denoted by $\alpha^{ij}$. The sign of LMC as a
function of internode scattering without strain is plotted in (b), and, with
only strain in (c). Strain, alone, does not increase LMC.  Figure 6: (a)
Planar Hall conductivity as a function of magnetic field in the absence of
strain, and, (b) as a function of the axial magnetic field $B_{5}$ in the
absence of external magnetic field. The angle of the magnetic field in (a) and
axial field (b) were chosen to be the same.

Inhomogeneous WSMs: We now show that our results have very important
consequences in the characterization of Weyl systems with naturally occurring
inhomogeneities. An axial magnetic field $\mathbf{B}_{5}$ that couples to Weyl
fermions of opposite chirality with an opposite sign, can be realized by an
inhomogeneous strain or magnetization profile in IWSMs [28, 29, 25]. Thus, the
magnetic field felt by each Weyl node is
$\mathbf{B}^{\chi}=\mathbf{B}+\chi\mathbf{B}_{5}$. Interestingly, it has been
pointed out that strain alone can result in positive contribution to LMC even
in the absence of external magnetic field ($\mathbf{B}=0$) [25]. In striking
contrast, again, we discover that this result is incorrect, and strain alone
does not yield positive LMC, but rather decreases conductance, as plotted in
Fig. 4 (a). Furthermore, the distribution functions switch sign as compared to
Fig. 2. This again is attributed to a combination of directional dependent
scattering processes, as well as global charge conservation [27]. In the
absence of strain, the switching of LMC from positive to negative is
attributed to the effect of orbital magnetic moment, but here, even ignoring
the OMM contribution does not affect our result qualitatively. This is
because, unlike the former case, strain induced OMM affects both the nodes
equally, and thus the Fermi surfaces retain their similarity. We extend the
formalism to the case of an inversion asymmetric WSM. We choose a prototype
model of a system with four Weyl nodes located at the points
$\mathbf{K}=(\pm\pi/2,0,\pm\pi/2)$ in the Brillouin zone. The minimal model is
given by

$\displaystyle H=\sum\limits_{n=1}^{4}\chi_{n}\hbar
v_{F}\mathbf{k}\cdot\bm{\sigma},$ (13)

where $\chi_{n}$ is the chirality of each Weyl node, and specifically, we
choose $\chi_{1}=-\chi_{2}=\chi_{3}=-\chi_{4}=-1$, such that time-reversal
symmetry is respected (see Fig. 5 (a)). We consider four possible internode
scatterings as shown in the figure, and scattering between diagonal nodes is
neglected. Furthermore, we choose $\alpha^{12}=\alpha^{34}$, and
$\alpha^{32}=\alpha^{14}$. The behavior of LMC without strain is plotted in
Fig. 5 (b). Sufficiently large internode scattering across (either
$\alpha^{12}$ or $\alpha^{14}$) yields negative LMC. In the presence of only
strain induced field $B_{5}$, we never get a positive contribution to LMC as
shown in Fig. 5 (c).

Planar Hall effect in IWSMs: To evaluate the planar Hall conductivity, the
magnetic field is made non-collinear with the electric field direction. We
rotate the magnetic field along the $x-z$ plane, that breaks the azimuthal
symmetry. Nevertheless, the Boltzmann formalism can be generalized [27] to
evaluate the planar Hall conductivity. Focusing on the strain induced planar
Hall effect, we find that contrary to previous reports [26], the strain
induced contribution is not only opposite to that of the regular planar Hall
effect, but also is different in magnitude. In Fig. 6 we explicitly show that
for the same orientation of the $B$ and the $B_{5}$ field, the magnitude and
the sign of planar Hall conductance are different from each other. Strain,
thus has a planar Hall conductance of opposite sign to that due to an external
magnetic field.

Final words: Reconciling with the Landau-level picture, we show that chiral
anomaly induced positive LMC is indeed an internode phenomenon, even in the
weak-$B$ semiclassical limit. Our results have remarkable implications in the
context of Weyl semimetals, including the result that strain induced axial
magnetic field $B_{5}$, produced negative LMC, and contributes against the the
planar Hall conductance due to an external magnetic field.

Acknowledgement: G. S. acknowledges support from SERB Grant No.
IITM/SERB/GS/305. S. T. acknowledges support from Grant No. NSF 2014157.

## References

  * Adler [1969] S. L. Adler, Axial-vector vertex in spinor electrodynamics, Physical Review 177, 2426 (1969).
  * Bell and Jackiw [1969] J. S. Bell and R. Jackiw, A pcac puzzle: $\pi$ 0→ $\gamma$$\gamma$ in the $\sigma$-model, Il Nuovo Cimento A (1965-1970) 60, 47 (1969).
  * Armitage  _et al._ [2018] N. Armitage, E. Mele, and A. Vishwanath, Weyl and dirac semimetals in three-dimensional solids, Reviews of Modern Physics 90, 015001 (2018).
  * Volovik [2003] G. E. Volovik,  _The universe in a helium droplet_ , Vol. 117 (Oxford University Press on Demand, 2003).
  * Nielsen and Ninomiya [1981] H. B. Nielsen and M. Ninomiya,  _No-go theorum for regularizing chiral fermions_ , Tech. Rep. (Science Research Council, 1981).
  * Nielsen and Ninomiya [1983] H. B. Nielsen and M. Ninomiya, The adler-bell-jackiw anomaly and weyl fermions in a crystal, Physics Letters B 130, 389 (1983).
  * Wan  _et al._ [2011] X. Wan, A. M. Turner, A. Vishwanath, and S. Y. Savrasov, Topological semimetal and fermi-arc surface states in the electronic structure of pyrochlore iridates, Physical Review B 83, 205101 (2011).
  * Xu  _et al._ [2011] G. Xu, H. Weng, Z. Wang, X. Dai, and Z. Fang, Chern semimetal and the quantized anomalous hall effect in hgcr 2 se 4, Physical Review Letters 107, 186806 (2011).
  * Zyuzin  _et al._ [2012] A. Zyuzin, S. Wu, and A. Burkov, Weyl semimetal with broken time reversal and inversion symmetries, Physical Review B 85, 165110 (2012).
  * Son and Spivak [2013] D. Son and B. Spivak, Chiral anomaly and classical negative magnetoresistance of weyl metals, Physical Review B 88, 104412 (2013).
  * Goswami and Tewari [2013] P. Goswami and S. Tewari, Axionic field theory of (3+ 1)-dimensional weyl semimetals, Physical Review B 88, 245107 (2013).
  * Goswami  _et al._ [2015] P. Goswami, J. Pixley, and S. D. Sarma, Axial anomaly and longitudinal magnetoresistance of a generic three-dimensional metal, Physical Review B 92, 075205 (2015).
  * Zhong  _et al._ [2015] S. Zhong, J. Orenstein, and J. E. Moore, Optical gyrotropy from axion electrodynamics in momentum space, Physical Review Letters 115, 117403 (2015).
  * Kim  _et al._ [2014] K.-S. Kim, H.-J. Kim, and M. Sasaki, Boltzmann equation approach to anomalous transport in a weyl metal, Physical Review B 89, 195137 (2014).
  * Lundgren  _et al._ [2014] R. Lundgren, P. Laurell, and G. A. Fiete, Thermoelectric properties of weyl and dirac semimetals, Physical Review B 90, 165115 (2014).
  * Cortijo [2016] A. Cortijo, Linear magnetochiral effect in weyl semimetals, Physical Review B 94, 241105 (2016).
  * Sharma  _et al._ [2016] G. Sharma, P. Goswami, and S. Tewari, Nernst and magnetothermal conductivity in a lattice model of weyl fermions, Physical Review B 93, 035116 (2016).
  * Zyuzin [2017] V. A. Zyuzin, Magnetotransport of weyl semimetals due to the chiral anomaly, Physical Review B 95, 245128 (2017).
  * Das and Agarwal [2019] K. Das and A. Agarwal, Berry curvature induced thermopower in type-i and type-ii weyl semimetals, Physical Review B 100, 085406 (2019).
  * Kundu  _et al._ [2020] A. Kundu, Z. B. Siu, H. Yang, and M. B. Jalil, Magnetotransport of weyl semimetals with tilted dirac cones, New Journal of Physics 22, 083081 (2020).
  * Knoll  _et al._ [2020] A. Knoll, C. Timm, and T. Meng, Negative longitudinal magnetoconductance at weak fields in weyl semimetals, Physical Review B 101, 201402 (2020).
  * Sharma  _et al._ [2020] G. Sharma, S. Nandy, and S. Tewari, Sign of longitudinal magnetoconductivity and the planar hall effect in weyl semimetals, Physical Review B 102, 205107 (2020).
  * Nandy  _et al._ [2017] S. Nandy, G. Sharma, A. Taraphder, and S. Tewari, Chiral anomaly as the origin of the planar hall effect in weyl semimetals, Physical Review Letters 119, 176804 (2017).
  * Mahan [2008] G. D. Mahan,  _9\. Many-Particle Systems_ (Princeton University Press, 2008).
  * Grushin  _et al._ [2016] A. G. Grushin, J. W. Venderbos, A. Vishwanath, and R. Ilan, Inhomogeneous weyl and dirac semimetals: Transport in axial magnetic fields and fermi arc surface states from pseudo-landau levels, Physical Review X 6, 041046 (2016).
  * Ghosh  _et al._ [2020] S. Ghosh, D. Sinha, S. Nandy, and A. Taraphder, Chirality-dependent planar hall effect in inhomogeneous weyl semimetals, Physical Review B 102, 121105 (2020).
  * SI [2022] See supplementary information, (2022).
  * Cortijo  _et al._ [2015] A. Cortijo, Y. Ferreirós, K. Landsteiner, and M. A. Vozmediano, Elastic gauge fields in weyl semimetals, Physical Review Letters 115, 177202 (2015).
  * Pikulin  _et al._ [2016] D. Pikulin, A. Chen, and M. Franz, Chiral anomaly from strain-induced gauge fields in dirac and weyl semimetals, Physical Review X 6, 041021 (2016).