Learning boolean functions with input-ouput examples and side-information

The Kushilevitz-Mansour, "low-degree", and Goldreich-Levin algorithms aim to learn a function $$f: \{0,1\}^n \rightarrow \{0,1\}$$ from a sufficiently large set of input-output examples $$(x_i, f(x_i))$$. But lets say that I have a function $$g: \{0,1\}^n \rightarrow \{0,1\}^2$$, and let $$g_1, g_2 : \{0,1\}^n \rightarrow \{0,1\}$$ be the mappings from the input to the "first" and "second" output bits of $$g$$, respectively. Given input-output examples $$(x_i, g(x_i))$$, one could (in theory) learn $$g_1,g_2$$ individually, by treating the observations $$g(x_i)$$ as paired observations of $$g_1(x_i)$$, $$g_2(x_i)$$, and ignoring the appropriate element. Naively, to learn $$g_1$$ you'd ignore the second element of the pair and apply your Boolean-function-learning algorithm, and likewise for $$g_2$$. In practice, one or both of these might fail, because (say) learning $$g_1$$ and/or $$g_2$$ requires too many input-output examples, individually. But these learning algorithms don't exploit the available side information, i.e., that $$g_1,g_2$$ are individual "slices" of $$g$$.

My question is this: are there versions of Boolean-function-learning algorithms that could exploit this side information?

• What's the class of possibilities for $g$? Linear functions? Low-degree functions? Something else? I don't think the question is answerable without that.
– D.W.
Commented Oct 9, 2022 at 18:44