Learning Boolean halfspaces with small weights from membership queries (Q329608)

The paper aims to learn Boolean halfspaces with small weights from a minimally adequate teacher. A Boolean halfspace is a function \(f = [w_1x_1 + \dotsb + w_kx_k \geq u]\) that returns the truth value of the inequality in which \(x_1, \dotsc, x_k \in \{0, 1\}\) are Boolean variables and \(u, w_1, \dotsc, w_k \in \{0, \dotsc, t\}\) for a fixed constant~\(t\). The latter restriction to small nonnegative integer weights essentially makes the problem finite provided that the number~\(k\) of relevant variables is given. The minimally adequate teacher in this case is a membership oracle that correctly answers queries for function values, which are Boolean values. In other words, the learner has access to a finite amount of function values and needs to determine the coefficients \(u, w_1, \dotsc, w_k\) of the Boolean halfspace. The currently best known bound for the number of necessary queries to learn the hidden halfspace is improved from \(k^{O(t^5)}\) to~\(k^{O(t)}\) using two rounds of queries. A non-adaptive algorithm using only~\(k^{O(t^3)}\) is also provided. Both algorithms proceed in essentially the same fashion. They first perform queries to determine the relevant variables as well as the symmetries for variables. Once those have been identified, the remaining variables have nonzero coefficients and those coefficients can indeed be ordered due to the symmetry information. In the adaptive setting, all halfplanes that are consistent with the current information can now be constructed and additional queries can be used to distinguish the remaining candidates, whereas in the non-adaptive setting additional queries are required to ensure that the answer is uniquely determined. Overall, the paper is well written and is nicely illustrated. All proofs are presented in full details and even basic facts are established with great care. Anyone with some minor background in basic mathematics should be able to appreciate the paper.