In the Linear GS Game, the adversary picks \(t\)  points and two colorings for these points which are everywhere different. Then the learner responds with an NL pattern \(\eta _t \in \lbrace 0,1\rbrace ^t\)  with the goal that there is no \(h \in \mathcal {H}\)  that is \(N\) -consistent with the adversary's input. Hence, the learner aims to find forbidden NL patterns in the data.
The finiteness of the NL tree implies the existence of a winning strategy for the learner in the game and, hence, an algorithm (which one can construct) for learning to rule out NL patterns.
Then, we show how to simulate this game using any \(\mathcal {H}\) -realizable sequence and utilize the learner's strategy to, eventually, find forbidden NL patterns in the data.
The simulation of the game is another novel part for the linear rates (see fig:pattern-algo).
Intuitively, there exists some finite number \(m\) , which depends on the data sequence, such that for any collection of \(m+1\)  points, there exists some invalid NL pattern. The definition of the NL patterns then indicates that we cannot \(N\) -shatter any collection of \(m+1\)  points and hence we can work, in some sense, with a class whose Natarajan dimension is \(m\) . We can then use the one-inclusion hypergraph algorithm [1]}, [2]}, [3]}, [4]} (see appendix:one-inclusion) to get a good predictor for the data. Again a single execution of the above strategy is not sufficient, we have to use data-splitting and aggregate our collection of predictors using the majority vote. algorithms:universal2 achieves an optimal rate of \(1/n\) . Finally, we prove that a class with an infinite NL tree requires arbitrarily slow rates.
