source_uniform.tex

\section{Uniform Generation with Replay}
\label{sec:uniform}

We begin with the simplest result.
In the standard setting, a uniformly generatable class \(\cH\) has the nice property that its sample complexity \(d^\star\) is known, at least information-theoretically~\citep{li2024generation}.
That is, after observing any \(d^\star\) distinct examples from any given \(h \in \cH\), a uniform generator \(\cG\) for \(\cH\) is guaranteed to output unseen elements of \(\supp{h}\).
A naive strategy to convert \(\cG\) into a generator \(\widetilde{\cG}\) that generates \(\cH\) uniformly with replay is to ignore all examples matching a previous output and apply \(\cG\) on the remaining examples.
However, if \(\widetilde{\cG}\) were to output arbitrary elements \(o_t \in \cX\), then the sequence \[x_1,\quad o_1, \quad o_2, \quad o_3, \quad \ldots\] could, in principle, form a valid replay sequence with potentially unbounded cardinality.
In this case, \(\widetilde{\cG}\) would not gather any additional information on \(h^\star\) beyond \(x_1 \in \supp{h^\star}\), and thus would not automatically inherit \(\cG\)'s guarantees.\looseness=-1

To address this challenge, we introduce a preliminary ``burn-in'' phase during which we restrict \(\widetilde{\cG}\)'s outputs, before eventually copying \(\cG\).
\Cref{alg:uniform_to_uniform_replay} illustrates how to construct such a generator \(\widetilde{\cG}\) achieving uniform generation under replay in the most sample-efficient way possible.
This result is stated formally in the following theorem.

\begin{theorem}[Equivalence of uniform generation with and without replay] \label{thm:uniform_with_replay}
    A binary hypothesis class \(\cH \subseteq \bc{0,1}^\cX\) satisfying the UUS property is uniformly generatable with replay if and only if it is uniformly generatable.
    In particular, any generator \(\cG\) that generates \(\cH\) uniformly can be converted into a generator \(\widetilde{\cG}\) that generates \(\cH\) uniformly with replay, without increasing the sample complexity.
\end{theorem}

\begin{proof}
    Clearly, if a generator generates \(\cH\) uniformly with replay then it also generates \(\cH\) uniformly, since all valid sequences in the standard setting are also valid sequences with replay.
    To show the other implication, suppose \(\cG\) generates \(\cH\) uniformly after seeing \(d^\star\) examples.
    \Cref{alg:uniform_to_uniform_replay} shows how to construct a generator \(\widetilde{\cG}\) from \(\cG\) that generates \(\cH\) uniformly with replay.
    Let \(\br{x_t}_{t \geq 1}\) be a sequence with replay for \(h \in \cH\) and \(\widetilde{\cG}\).
    The generator \(\widetilde{\cG}\) repeatedly outputs the first example \(x_1\) until the following condition is satisfied: \(\abs{\bc{x_1, \ldots, x_t}} \geq d^\star\).
    From that moment onward, \(\widetilde{\cG}\) copies \(\cG\)'s outputs.
    Now, let \(t^\star\) be the first time such that \(\abs{\bc{x_1, \ldots, x_{t^\star}}}\geq d^\star\).
    We necessarily have that \(\bc{x_1, \ldots, x_{t^\star}} \subset \supp{h}\), since \(x_1\) is guaranteed to belong to \(\supp{h}\) and \(\widetilde{\cG}\) has only ever output \(x_1\).
    Therefore, since \(\cG\) uniformly generates \(\cH\) with sample complexity \(d^\star\), we have that \(\cG(x_{1:s}) \in \supp{h} \setminus \bc{x_1, \ldots, x_s}\) for all \(s \geq t^\star\).
    It follows that \(\widetilde{\cG}\) achieves uniform generation with replay with the same sample complexity \(d^\star\). \looseness=-1
\end{proof}

We now turn to a setting where the previous approach fails and introducing replay yields a strict separation from the standard setting.

\begin{algorithm}[tb]
\caption{Uniform-to-uniform-with-replay conversion} 
\label{alg:uniform_to_uniform_replay}
    \begin{algorithmic}[1]
        \Require \(\cG\) uniform generator for \(\cH\) with sample complexity \(d^\star\)
        \For{\(t = 1,2,\ldots\)}
            \State Receive new example \(x_t\)
            \If{\(\abs{\bc{x_1, \ldots, x_t}} \geq d^\star\)}
                \State Output \(\cG(x_{1:t})\)
            \Else
            \State Output \(x_1\)
            \EndIf 
        \EndFor
    \end{algorithmic}
\end{algorithm}