acceptodds
Under review as a conference paper at ICLR 2027

What Gradient Descent Can See

Abstract

The Boolean queries computed by DLOGTIME-uniform, polynomial-size, bounded-depth threshold networks are definable in first-order logic with majority quantifiers, the logic of uniform constant-depth threshold circuits. Expressibility is not learnability: polynomial-tolerance correlational queries cannot efficiently learn some targets that these networks represent, with sparse parity the standard witness. We show that this gap is itself logical. We introduce the correlationally visible fragment of that logic, in which a step may introduce new coordinates only when they carry a correlation with the residual of the target given what is already present. In the correlational statistical query model, this fragment is exactly the class learnable to any inverse-polynomial error in polynomial time, for definable targets of logarithmic arity, inverse-polynomial Fourier coefficients, and definable relevant sets. The lower half of the characterization is a leap lower bound proved in the model itself, with absolute constants, for arbitrary Boolean shapes of logarithmic arity. The arity bound cannot be dropped: we exhibit a sparse query with no small coefficient that introduces one coordinate per step, lies in the fragment, and is not learnable. The separation from the full logic is unconditional, witnessed by parity.

Primary area:
foundation or frontier models, including LLMs
Keywords:
descriptive complexity, first-order logic with majority, threshold circuits, correlational statistical queries, leap complexity, learnability, parity

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_imQtOpenReview ↗
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
  1. 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?

  2. Why should I care about the new logical characterization? Is there a syntactic criterion or a natural logical application that demonstrates its value?

Reviewer_3p6mOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This article presents gap results between expressivity and learnability. More precisely, the authors show that within the framework of correlational statistical queries, what is reachable is in nature different from what can be exactly represented by a given class. To achieve this, the authors restrict their study to certain class of functions and domain.

Critical strengths

This article has the merit to address upfront a gap between expressiveness (a description of what can be computed at best by a class), and what they can actually learn via a method like gradient descent. To do so, the authors invoke the Correlational Statistical Query model, that encompass methods such as gradient descent.

Critical weaknesses
  • This article is particularly difficult to read. The writing of the abstract and introduction are expedited. Given the chosen title, it is part of the responsibility of the authors to explicit how the main contributions gives good insights on the gradient method procedure at a high level (and not only at a technical level), and should be stated upfront in the abstract or in the introduction. More generally, the article does not take enough time to provide the reader enough intuition on the nature of the results.

  • It is not discussed whether the assumptions made (inputs are the corner of the hypercube) restrict the study or claims on the general continuous setup of learning via gradient descent.

Questions for authors
  • In Section 3.1: ``...correlational statistical queries, the standard abstraction for the correlations that a gradient extracts from data'': in my understanding, the references mentioned there do not study gradient at all. Can you elaborate on this?

  • Why does the learner has only access through dyadic approximations?

  • In definition 3.2 is the notation of fˆσ(n)fˆ{\sigma}(n) properly introduced? (from context it appears that it's only the permutation of inputs, but this was not defined except an error on my part)

Reviewer_apoUOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper gives a description of certain types of statistical query algorithms in terms of a logical system. In particular it uses descriptive complexity. It gives separations of fragments of "SQ-like" logic to prove separations within certain definable systems.

Critical strengths

It gives a formal proof system perspective on SQ algorithms.

Critical weaknesses

It doesn't provide any new learning results for any natural settings. It certainly does not give any new insight on gradient descent.

Questions for authors

Does this give any new learning lower bounds or upper bounds for interesting function classes?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.