- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper studies learnability of Boolean function families under coordinate permutations in the correlational statistical query model. For functions depending on logarithmically many coordinates and satisfying a Fourier coefficient condition, it characterizes efficient learning through bounded leap complexity. It then introduces a class of uniformly definable feature derivations, called (sFOM), and proves that this class coincides with the learnable class under the stated assumptions. Additional results include an explicit uniform lower bound and a large-arity counterexample showing that bounded leap alone does not suffice beyond this setting.
Critical strengths
The formal results seem to be correct.
Critical weaknesses
There is a significant disconnect between the stated motivation and the formal setting. The paper begins with expressivity results transformers, then moves to learning with correlation query without much explanation. These are different mathematical questions, and the transition is not adequately justified to the reader. Furthermore, even in the setting of the formal model, the presented results are incremental and it is not well justified that they are interesting or worth attention. For example, the paper promises a logical characterization of the discussed learnability notion, but this logical characterization is obtained by an ad hoc tailored definition that does not seem to bring new insights or be interesting on its own for some reason (e.g. by virtue of being studied before in different context). Finally, for most part the proofs are simple application of the techniques from other authors.
The presentation is not very good. The contribution relies on many mathematical notions from formal learning theory, logic and so on. While these are generally defined, they are not always well motivated. Therefore, the paper is very hard to digest for a reader without experience. Sometimes distinct concepts are conflated in the presentations: for instance, we have both query as a class of Boolean function and then a query in learning theoretic sense which means something else. Several sentences also read like drafting notes or reassurance to an imagined reviewer. Examples include "None of it is new and none of it is changed" on page 11 and "Nothing is sketched and nothing is deferred further" on page 13. The reference point for "changed" is unclear.
Questions for authors
-
What precise new statement about gradient descent or stochastic gradient descent on a specified architecture follows from the paper, and under which assumptions on precision, sampling, and robustness?
-
Why should I care about the new logical characterization? Is there a syntactic criterion or a natural logical application that demonstrates its value?