source_nonuniform.tex

\section{Non-Uniform Generation with Replay}
\label{sec:non-unif}

In contrast to the uniform notion of generation, the sample complexity in the non-uniform case depends on the particular, \emph{unknown} target hypothesis (see Definition~\ref{def:non-uniform-gen} in Appendix~\ref{app:overview-generation}).
As a result, a generator cannot commit in advance to observing a fixed number of distinct examples before producing new outputs, as in~\Cref{sec:uniform}.
This precludes a direct adaptation of the reduction-based constructions from uniform generators used in, e.g.,~\citet{li2024generation}.\looseness=-1

In the standard setting, all countable classes are non-uniformly generatable~\citep{li2024generation,charikar2024exploring}.
In contrast, \Cref{thm:hardness-non-unif} shows that this guarantee fails in the replay setting: countability alone no longer suffices.
Nonetheless, every finite hypothesis class remains non-uniformly generatable as an immediate corollary of~\Cref{thm:uniform_with_replay}.
Together, these results account for the row on non-uniform generation in~\Cref{tab:replay-separation-classes}.

\begin{theorem} [Hardness of non-uniform generation with replay] \label{thm:hardness-non-unif}
    There exists a \emph{countable} binary hypothesis class \(\cH\subseteq \bc{0,1}^\cX\) satisfying the UUS property that is \emph{not} non-uniformly generatable with replay.
\end{theorem}

\begin{proof}
Let \(\cX=\bZ\).
For each \(n\in \bN\) define the hypotheses \(h_n\) and \(h_\infty\) by
\[
\supp{h_n}=\bc{1,\ldots,n}\cup \bZ_{<0}, \quad \supp{h_\infty}=\bN.\]
Let \(\cH \coloneqq \{h_\infty\}\cup\{h_n:n\in\bN\}\).
Assume for contradiction that there exists a generator \(\cG\) that non-uniformly generates \(\cH\) with replay. 
Let \(d\coloneqq d^\star_{h_\infty}\) denote the (non-uniform) sample complexity associated with \(h_\infty\).

We define an adversarial sequence \(\br{x_t}_{t\ge1}\) online.
For \(t=1,\ldots,d\), set \(x_t\coloneqq t\).
For each \(t\ge d\), set \(x_{t+1}\coloneqq o_t\), i.e., from time \(d\) onward the adversary always replays the most recent generator's output \(o_t \coloneqq \cG\br{x_{1:t}}\).
By construction, \(\br{x_t}_{t\ge1}\) is a valid replay sequence for \(h_\infty\) and \(\cG\): the first \(d\) points lie in \(\supp{h_\infty}\) and every subsequent point is a replay. \looseness=-1

Since \(\abs{\bc{x_1,\ldots,x_d}}=d=d^\star_{h_\infty}\), generatability in the non-uniform setting implies that for all \(t\ge d\),
\[o_t\in \supp{h_\infty}\setminus\bc{x_1,\ldots,x_t}=\bN\setminus\bc{x_1,\ldots,x_t}.\]
In particular, since \(x_{t+1}=o_t\), it follows that the generator outputs \emph{fresh} natural numbers from time \(d\) onward.
Thus, the set of distinct points in \(\br{x_t}_{t\ge1}\) is unbounded.

Next, observe that the same sequence \(\br{x_t}_{t\ge1}\) is also a valid sequence with replay for \(h_d\) and \(\cG\): we have \(1,\ldots,d\in\supp{h_d}\), and for all later times the adversary supplies replays (which are allowed to lie outside the support of \(h_d\)). 
Because the sequence \(\br{x_t}_{t\ge1}\) contains infinitely many distinct points, there exists a finite \(T\in\bN\) such that \(|\{x_1,\ldots,x_T\}|\ge d^\star_{h_d}\).
Applying the non-uniform guarantee to the target \(h_d\) therefore yields that, for all \(t\ge T\),
\[
o_t\in \supp{h_d}\setminus\bc{x_1,\ldots,x_t}.
\]

Combining this with \(o_t\in\supp{h_\infty}=\bN\) for all \(t\ge d\), we obtain that for all \(t\ge \max\{d,T\}\),
\[
o_t\in \supp{h_\infty}\cap\supp{h_d}=\{1,\ldots,d\}.
\]
Thus, for all sufficiently large \(t\), the output \(o_t\) must lie in the finite set \(\{1,\ldots,d\}\) while also being fresh relative to \(\bc{x_1,\ldots,x_t}\).
This is impossible: after at most \(d\) such fresh outputs, every element of \(\{1,\ldots,d\}\) has already appeared in the input sequence.
The resulting contradiction shows that no such generator \(\cG\) can exist.
\end{proof}