source_proper.tex

\section{Proper Generation in the Limit with and without Replay}
\label{sec:proper}

We now shift our focus from \emph{improper} to \emph{proper} generation, where the generator outputs a hypothesis \(\hat{h}_t\) at each round.
We focus exclusively on the \emph{in-the-limit} notion of proper generatability for two reasons.
First, prior work on proper generatability has primarily addressed the in-the-limit setting: \citet{kleinberg2024language} established that all countable classes are properly generatable in the limit using a generator relying on membership and subset queries (see \Cref{thm:proper-gen-in-the-lim}).
In~\Cref{subsec:lb-proper}, we strengthen this line of work by providing a computational lower bound showing that membership queries alone are insufficient for proper generation in the limit in the standard setting.
Second, as we show in~\Cref{subsec:proper-with-replay}, the notion of proper generatability with replay is so strong that a separation from the standard setting arises even in the (easy) setting of generatability in the limit of finite classes.


\subsection{An Impossibility Result for Proper Generation in the Limit Using Only Membership Queries}
\label{subsec:lb-proper}
\citet{kleinberg2024language} give a universal membership-query-only algorithm that improperly generates in the limit any countable hypothesis class.
A similar algorithm also achieves \emph{proper} generation in the limit for any countable class, but requires additional access to subset queries.
The following result shows that access to additional queries besides membership queries is indeed \emph{necessary} for proper generation.

\begin{restatable}{theorem}{thmpropernofreelunch}
    \label{thm:lower-bound-proper}
    There cannot exist a (deterministic) generator $\cG$ that only makes membership queries and properly generates in the limit all countable hypothesis classes.
\end{restatable}


\begin{algorithm}[!htbp]
\caption{Hard Hypothesis Class for the Proper Generator $\cG$} \label{alg:lower-bound}
\begingroup
\setlength{\baselineskip}{1.05\baselineskip}
    \begin{algorithmic}[1]

        \Require Proper generator $\cG$
        
        \State Set $F(i,1) = 1$ for all $i \in \bN$
        \State Initialize enumeration queue: $Q \gets \{1\}$
        \State Set up the trap: \(\displaystyle F(i, 2) = \begin{cases}
            0 &\text{if } i = 2, \\
            1 &\text{if } i \neq 2 \\
        \end{cases}\)
        \State Initialize trap pair $\br{i',j'} \gets \br{2,2}$ 
        \State Initialize counters: $I \gets 2$ and $J \gets 2$ 
        
        \For{t=1,2,\ldots}
        \State Show $\cG$ the example $x_t \gets \min Q$; \;Remove $x_t$ from $Q$
         
        \State $k \gets 1$
        \While{$\cG$ issues a new membership query $(i,j)$}
            \State $m \gets \max\{j,k\}$
            \If{$m>J$}
                \For{$n=J+1,J+2,\ldots,m$}
                    \State Set $F(\ell,n)=1$ for all $\ell\in\bN$; \;Add $n$ to $Q$ 
                \EndFor
                \State $J\gets m$
            \EndIf
            \State $I\gets \max\{I,i\}$
            \State $k\gets k+1$
        \EndWhile

        \State Receive \(\mathcal{G}\)'s output $i_t$ \Comment{ Interpreted as \(\hat{h}_t = h_{i_t}\)}
        \State $I \gets \max \bc{ I,i_t}$

        \If{$i_t \neq 1$}
        \State Add $j'$ to $Q$
        \State Diagonalization step: $d_t \gets J+1$; \;Set \(\displaystyle F(i, d_t) = \begin{cases}
            1 &\text{if } i = i_t, \\
            0 &\text{if } i \neq i_t \\
        \end{cases}\)
        \State Set up a new trap: $e_t \gets J+2$; \;Set \(\displaystyle F(i, e_t) = \begin{cases}
            0 &\text{if } i = I+1, \\
            1 &\text{if } i \neq I+1 \\
        \end{cases}\)
        \State Update trap pair: $\br{i',j'} \gets \br{I + 1, e_t}$
        \State Update counters: $I \gets i'$ and $J \gets e_t$
        \EndIf
        
        \State Let $c_t \gets J+1$; \;Set $F(i, c_t)=1\, \forall i \in \bN$; \;Add $c_t$ to $Q$; \;Update $J \gets c_t$
        \EndFor
    \end{algorithmic}
\endgroup
\end{algorithm}


As described in \Cref{alg:lower-bound}, for any given computable proper generator $\cG$ that only makes membership queries, we construct a hard class $\cH$ on which $\cG$ makes infinitely many mistakes by simulating $\cG$'s interaction with an adversarial enumeration.
At a high level, this follows the same ``simulation template'' as the computational lower bound of \citet{charikar2024exploring}; our construction, however, maintains a \emph{countably infinite} class rather than only two hypotheses.
\Cref{alg:lower-bound} defines $\cH=\bc{h_1,h_2,\ldots}$ via a function $F: \bN \times \bN \to \{0,1\}$ defined as \looseness=-1
\[F(i,j) = \begin{cases}
    1 \quad \text{if } j \in \supp{h_i}, \\
    0 \quad \text{if } j \notin \supp{h_i}, \\
\end{cases}\]
which constitutes the (limited) interface available to $\cG$ to interact with the hypothesis class $\cH$.
To compute \(F(i,j)\), one would run \Cref{alg:lower-bound}---which in turn simulates \(\cG\)---until the value of \(F(i,j)\) is assigned.

Because $\cH$ is countable, we can assume that $\cG$ outputs an index $i_t\in\bN$, interpreted as the index of the output hypothesis; that is, $\hat{h}_t = h_{i_t}$.
Since $\cG$ is restricted to membership queries, at every step $t$, it will have gathered information about finitely many hypotheses and finitely many instances (i.e., elements of the domain $\cX$).
\Cref{alg:lower-bound} maintains two counters $I$ and $J$ that delimit the finite ``rectangle'' of hypothesis-instance pairs $(i,j)\in\bN\times\bN$ queried so far by $\cG$; outside this rectangle, it sets memberships adversarially.
To ensure that the revealed sequence enumerates the target support, the construction maintains a queue $Q$ and at each round reveals $x_t=\min Q$, which guarantees that each element entering $Q$ will be revealed after a finite number of rounds.
Additionally, it maintains a \emph{trap} pair $(i',j')$ of hypothesis \(h_{i'}\) and instance \(j'\) such that $j'\notin\supp{h_{i'}}$ but $j'\in\supp{h_i}$ for all $i\neq i'$.
The hypothesis \(h_1\) serves as a reference hypothesis.

The algorithm has two modes---\emph{diagonalization} and \emph{overgeneralization}---and it switches mode automatically by adapting the enumeration $\br{x_t}_{t\ge 1}$ to $\cG$'s outputs, specifically to whether \(\hat{h}_t = h_1\).
The current trap instance enters the enumeration queue $Q$ only at the first subsequent round $t$ (if ever) for which $\hat{h}_t\neq h_1$.
When this occurs, \Cref{alg:lower-bound} also instantiates a new trap pair \(\br{i',j'}\) with \(i'>I\) and \(j'>J\).
There are two cases:
\begin{itemize}
\item  $\cG$ outputs a hypothesis different from \(h_1\) \emph{infinitely} often. In this case, the adversary enumerates $\supp{h_1}$ and forces $\cG$ to make infinitely many mistakes via \emph{diagonalization}: at each round $t$ with $\hat{h}_t\neq h_1$, it inserts a fresh instance $d_t$ beyond the counter $J$ and assigns it to the support of $\hat{h}_t$ but not to that of $h_1$.
\item  \(\cG\) outputs a hypothesis different from \(h_1\) only \emph{finitely} often. Then, after some finite time, it outputs \(h_1\) indefinitely.
In this case, the adversary enumerates the support of the current \emph{trap} hypothesis $h_{i'}$, whose support is strictly smaller than $\supp{h_1}$, so that $\cG$ \emph{overgeneralizes}.
\end{itemize}
\Cref{fig:no-free-lunch} illustrates a few steps of this procedure.


\begin{figure}[!htbp]
\centering
\resizebox{\linewidth}{!}{%
\DrawGrid{3}{2}{2}{2}{2/2}{}{1}{}{Initialization}%
\DrawGrid{4}{5}{3}{5}{2/2,1/3,3/3,3/4,4/3}{}{1,2,5}{1}{Step~1}%
\DrawGrid{5}{7}{4}{7}{2/2,1/3,3/3,3/4,4/3,5/3,6/3}{}{1,2,5,6,7}{2}{Step~2}%
}
\caption{
  Online construction of a hard hypothesis class for a given proper generator.
  \\[1ex]
  The horizontal axis represents the hypotheses in $\cH$, and the vertical axis represents the instances from the domain $\cX$.
  For every coordinate pair $(i,j)$, a filled circle ($\bullet$) indicates $j\in\supp{h_i}$, while an empty circle ($\circ$) indicates $j\notin\supp{h_i}$.
  A box around a label on the vertical axis means that the instance has been added to the enumeration queue $Q$, while a shaded box means that the instance has been shown as an example $x_t$.
  Finally, the L-shaped dashed line marks the current boundaries of $\cG$'s knowledge, as tracked by $I$ and $J$.
  \\[1ex]
  We illustrate the first steps of the interaction. 
  At initialization, the adversary inserts instance $1$ into the enumeration queue $Q$ and installs the \emph{trap} hypothesis-instance pair $\br{i',j'} = \br{2,2}$. 
  The counters $I$ and $J$ are both set to $2$.
  At step 1, the adversary reveals $x_1=1$. 
  For illustrative purposes, we assume that at step 1 the generator $\cG$ outputs $\hat{h}_1 = h_2$.
  This triggers the \emph{diagonalization} mode of \Cref{alg:lower-bound}: instance $d_1 = 3$ is assigned exclusively to the output hypothesis $h_2$; the current trap instance $j'=2$ is added to $Q$; a new trap hypothesis-instance pair $\br{i',j'} = \br{3,4}$ is created beyond $I$ and $J$ by assigning instance $e_1=4$ to all hypotheses except for $h_3$; finally, instance $c_1=5$ is assigned to all hypotheses and is therefore added to the enumeration queue.
  When the round ends, the counters $I$ and $J$ are set to $3$ and $5$, respectively.
  Then step 2 begins with $x_2=\min Q = 2$ being revealed to $\cG$.
  We assume that $\cG$ queries $F(4,6)$: instance $6$ is therefore assigned to all hypotheses and added to $Q$.
  Furthermore, the counters $I$ and $J$ move to $4$ and $6$, respectively.
  Suppose $\cG$ outputs $\hat{h}_2 = h_1$.
  This time the \emph{overgeneralization} mode of \Cref{alg:lower-bound} is triggered.
  In this case, the trap hypothesis-instance pair remains the same.
  At the end of the round, $c_2=7$ is added to $Q$ and the counter $J$ is updated to $7$.
}
  \label{fig:no-free-lunch}
\end{figure}


To prove \Cref{thm:lower-bound-proper}, we first argue about the soundness of our construction by analyzing the function $F$, showing that the corresponding hypothesis class $\cH$ is an \emph{indexed family of recursive languages} (in the sense of \citet{angluin1980inductive}) satisfying the UUS assumption.

\begin{lemma} \label{lemma:soundness}
    For any computable $\cG$, the associated function $F: \bN \times \bN \to \bc{0,1}$ defined in \Cref{alg:lower-bound} is total recursive. Moreover, for every $i \in \bN$, the set $\bc{j\in\bN \mid F(i,j)=1}$ is infinite. \looseness=-1
\end{lemma}

\begin{proof} 
    We show that, for every pair $(i,j)\in \bN\times \bN$, the value $F(i,j)$ is decided at a finite step of \Cref{alg:lower-bound} and is never changed afterward. 
    Observe that whenever \Cref{alg:lower-bound} encounters an instance $j$, it assigns the entire row $F(\cdot,j)$ in a single step, i.e., it fixes $F(i,j)$ for all $i\in \bN$ at once. 
    Therefore, it suffices to show that every instance $j\in \bN$ is encountered exactly once and at a finite step.
    To this end, we claim that, throughout the execution of \Cref{alg:lower-bound}, the set of encountered instances is always exactly the initial segment $\{1,\dots,J\}$, meaning that no instance $j<J$ is skipped during the execution.
    This is true at initialization: the algorithm encounters instances $1$ and $2$, and then sets $J\leftarrow 2$.
    Now consider any later stage of the construction.
    During the processing of $\cG$'s membership queries, suppose that $\cG$ issues its $k$-th query $(i,j)$ in the current round.
    Then, \Cref{alg:lower-bound} assigns values to all still-unseen instances $n$ satisfying \[ J < n \le \max\{j,k\}, \] and updates $J$ accordingly.
    Hence, all newly encountered instances form a consecutive block immediately after the current value of $J$.
    In particular, no instance is skipped, and no previously encountered instance is revisited or modified.
    In all other steps where the algorithm introduces new instances, it uses fresh indices immediately following the current counter (i.e., $J+1,J+2$) and updates $J$ immediately afterward.
    Thus, the set of encountered instances remains an initial segment of $\bN$ at every stage.

    It remains to show that every instance is encountered at a finite step, or equivalently, that the counter $J$ is unbounded.
    There are two cases.
    First, suppose that in every round $t$, the generator $\cG$ asks only finitely many membership queries and eventually outputs some $\hat{h}_t$. 
    Then, each iteration of the outer loop completes, and the last line of \Cref{alg:lower-bound} introduces a fresh instance $c_t$ at the end of every round (even if $\cG$ asks no query in that round). 
    Therefore, $J$ increases by at least one in every round, so $J\to\infty$ as $t\to\infty$.
    Second, suppose that in some round, $\cG$ asks infinitely many membership queries and never produces an output.\footnote{
            For instance, suppose $\cG$ keeps querying whether $j \in \supp{h_i}$ for a fixed $j$ and different $i$ until it gets a negative answer.
            Clearly, in this case $\cG$ would fail at its generation task, granted of course that the hypothesis class resulting from the construction was still valid.
    }
    Let $k$ denote the query counter within that round and note that, by construction, $J\ge k$.
    Since $k$ is unbounded along that infinite query sequence, $J$ is also unbounded within that single round.
    Hence, in either case, $F$ is recursive over its whole domain.

    Finally, the same two-case analysis shows that the resulting hypothesis class satisfies the UUS property.
    If every round is finite, then the fresh instance $c_t$ introduced at the end of each round is assigned to all hypotheses, so each support $\supp{h_i}$ contains infinitely many such instances.
    If instead some round contains infinitely many queries, then as $k\to\infty$, the construction introduces infinitely many new instances during that round, and each of them is again assigned to all hypotheses.
    Thus, $\supp{h_i}$ is infinite for all $i\in\bN$ in either case.\looseness=-1
\end{proof}

Having shown that \Cref{alg:lower-bound} defines a valid hypothesis class, we can now provide the proof of \Cref{thm:lower-bound-proper}.

\begin{proof}[Proof of \Cref{thm:lower-bound-proper}] 
Suppose, for the sake of contradiction, that there exists a deterministic proper generator $\cG$ that uses only membership queries and properly generates in the limit every countable hypothesis class.
Consider the hypothesis class $\cH=\{h_1,h_2,\ldots\}$ induced by \Cref{alg:lower-bound} when run against $\cG$.
Since $\cG$ properly generates $\cH$, we can assume that at each step $t$ the generator $\cG$ halts to produce an output hypothesis $\hat{h}_t = h_{i_t} \in \cH$.
For every round $t$ with $i_t\neq 1$, let $d_t$ denote the fresh diagonalization instance created at round $t$ by \Cref{alg:lower-bound}. By construction,
\[
    d_t \in \supp{h_{i_t}} \quad\text{and}\quad d_t \notin \supp{h_i}\ \ \forall i\neq i_t,
\]
so in particular $d_t\notin \supp{h_1}$.
Also, if $(i',j')$ denotes the current trap pair maintained by the algorithm, then it holds that
\[j' \notin \supp{h_{i'}} \quad\text{and}\quad j' \in \supp{h_i}\ \ \forall i\neq i'.
\]
Additionally, define
\[
    Q_\infty := \{n\in\bN : n \text{ is ever added to } Q\}.
\]
Since at each round $t$ the algorithm reveals $x_t=\min Q$, every $n\in Q_\infty$ is shown after finitely many rounds: only finitely many smaller integers can ever be inserted before it, and each of them is removed after one round.
Therefore, $\br{x_t}_{t\ge 1}$ is an enumeration of $Q_\infty$.
We now distinguish two cases: $\cG$ outputs $\hat{h}_t \neq h_1$ either finitely or infinitely many times.

First, suppose $\cG$ outputs $\hat{h}_t \neq h_1$ \emph{infinitely} many times.\footnote{The most natural choice would be $\hat{h}_t = h_{i'}$ since at each step, the trap hypothesis $h_{i'}$ is, in some sense, the minimal consistent hypothesis.
}
We argue that this would lead to a contradiction by showing that in this case \Cref{alg:lower-bound} enumerates $\supp{h_1}$ and that $\cG$ makes infinitely many mistakes for $h^\star = h_1$. 
To begin, note that if $h^\star = h_1$ then $\cG$ makes infinitely many mistakes, since each $d_t$ only belongs to the support of $\hat{h}_t$ and thus \[\supp{\hat{h}_t} \nsubseteq \supp{h_1}.\]
It remains to show that, in this case, \(Q_\infty = \supp{h_1}\).
Observe that all instances that are not trap instances are immediately added to $Q$ after being encountered.
Additionally, any trap instance $e_t$ created at round $t$ is added to $Q$ at the next round $s>t$ such that $\cG$ outputs $\hat{h}_s \neq h_1$, which we have assumed to be happening infinitely often in this case.
Conversely, the only instances never added to $Q$ are the diagonalization instances $d_t$, and none of them belongs to $\supp{h_1}$.

Therefore, it must be that $\cG$ outputs $\hat{h}_t \neq h_1$ only \emph{finitely} many times.
Let \[t_0 := \max\{t\in\bN : i_t\neq 1\},\] with the convention $t_0=0$ if $i_t=1$ for all $t\in\bN$.
Let $(\bar{\imath},\bar{\jmath})$ denote the values of the trap pair $(i',j')$ after round $t_0$; if $t_0=0$, then $(\bar{\imath},\bar{\jmath})=(2,2)$.
By definition of $t_0$, \(\hat{h}_t = h_1\) for all \(t>t_0\).
We claim that \(Q_\infty = \supp{h_{\bar{\imath}}}\).
We first show that $Q_\infty\subseteq \supp{h_{\bar{\imath}}}$.
Any instance introduced during the query phase or as some \(c_t\) belongs to all hypotheses, hence in particular to $h_{\bar{\imath}}$.
Any trap instance that is ever released and added to $Q$ must have been created before round \(t_0\).
If it was created when the trap index was \(\tilde{\imath}\), then it is excluded only from \(h_{\tilde{\imath}}\); since trap indices are strictly increasing, we have \(\tilde{\imath} \neq \bar{\imath}\), and thus this instance also lies in \(\supp{h_{\bar{\imath}}}\).
Therefore, \(Q_\infty\subseteq \supp{h_{\bar{\imath}}}\).
Conversely, the only instances never added to \(Q\) are precisely the final trap \(\bar{\jmath}\) and the diagonalization instances \(d_t\) created at rounds \(t\le t_0\) with \(i_t\neq 1\).
By definition, \(\bar{\jmath}\notin \supp{h_{\bar{\imath}}}\). 
Moreover, each such \(d_t\) belongs only to \(h_{i_t}\), whereas the trap created in round \(t\) has index strictly larger than \(i_t\); since trap indices only increase afterward, \(\bar{\imath}>i_t\), so \(d_t\notin \supp{h_{\bar{\imath}}}\).
Thus, \(\supp{h_{\bar{\imath}}}\subseteq Q_\infty\).
We conclude that \(Q_\infty = \supp{h_{\bar{\imath}}}\), so $(x_t)_{t\ge 1}$ is an enumeration of $\supp{h_{\bar{\imath}}}$ and we can set $h^\star = h_{\bar{\imath}}$.
However, this implies that $\cG$ makes infinitely many mistakes also in this case, since \(\bar{\jmath} \in \supp{h_1}\) but \(\bar{\jmath} \notin \supp{h_{\bar{\imath}}}\).

As both cases yield a contradiction, we conclude that no deterministic generator using only membership queries can properly generate in the limit all countable hypothesis classes.
\end{proof}


\subsection{Proper Generation in the Limit with Replay}
\label{subsec:proper-with-replay}

The following theorem shows that, in the proper setting, replay makes a class of just four hypotheses not generatable under even the weakest notion.
This accounts for the last row of \Cref{tab:replay-separation-classes}.\looseness=-1

\begin{theorem}[Hardness of proper generation in the limit with replay] \label{thm:hardness-proper-replay}
    There exists a \emph{finite} hypothesis class \(\cH\) that is not properly generatable in the limit with replay.
\end{theorem}

\begin{proof}
    For \(i=1,2\), define
    \[\supp{h_i^-} = \mathbb{Z}_{\leq0}\cup\{i\}, \quad \supp{h_i^+} = \mathbb{Z}_{\geq0}\cup\{-i\},\]
    and let \(\cH = \{h_1^-, h_2^-, h_1^+, h_2^+\}\). 
    Suppose, for the sake of contradiction, that there exists a proper generator \(\cG\) that properly generates \(\cH\) in the limit with replay. 
    Let \(x_1=0\) be the first example shown by the adversary. 
    Note that \(x_1\) belongs to the support of all hypotheses in \(\cH\). 
    Therefore, \(\cG\) makes a completely arbitrary choice when choosing its first output \(\hat{h}_1\). 
    We give the argument for \(\hat{h}_1 = h_1^-\); the other cases are handled analogously.

    Consider the following extension of the adversarial sequence of examples: \(x_2 = -1, x_3 = -2\), followed by all the positive integers.
    The resulting sequence \((x_t)_{t\ge 1}\) is a valid sequence with replay for \(\cG\) and both \(h_1^+, h_2^+\): 
    \[
    x_t \in \supp{h_1^+} \cap \supp{h_2^+} \text{ for } t \neq 2,3 \quad\text{and}\quad x_2, x_3 \in \supp{\hat{h}_1}.
    \]
    Additionally, \((x_t)_{t\ge 1}\) contains an enumeration of the support of both \(h_1^+\) and \(h_2^+\) and, thus, is an enumeration with replay in the proper setting for \(h_1^+\) and \(h_2^+\) simultaneously. 
    As \(\cG\) properly generates \(\cH\) in the limit with replay by assumption, there exist \(t^\star_1, t^\star_2 \in \mathbb{N}\) and a sequence of \(\hat{h}_t \in \cH\) such that: 
    \[
    \supp{\hat{h}_t} \subseteq \supp{h_1^+} \text{ for all } t\geq t^\star_1 \quad\text{and}\quad
    \supp{\hat{h}_t} \subseteq \supp{h_2^+} \text{ for all } t\geq t^\star_2.
    \] 
    Therefore, if we let \(t^\star = \max \left\{t^\star_1, t^\star_2 \right\}\), it must be that, for all \(t \geq t^\star\),
    \[\supp{\hat{h}_t} \subseteq \supp{h_1^+} \cap \supp{h_2^+} = \mathbb{Z}_{\geq0}.\]
    However, there is no hypothesis \(h \in \cH\) such that \(\supp{h} \subseteq \mathbb{Z}_{\geq0}\), and thus we have reached a contradiction. \looseness=-1
\end{proof}