- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper considers gradient descent as a computation model and presents two groups of theoretical results. First, the authors showed that gradient descent computation is highly expressive by showing that execution of arbitrary circuit can be expressed by running gradience descent on certain loss functions. Second, the author shows that even if the loss function has good properties like strong convexity or contractive, it is still PSPACE-hard to predict the trajectory of gradient descent. Next the authors turn to gradient descent as an optimizer for semidefinite relaxations, motivated by lifting circuit constraints to moment matrices. They show that gradient descent on a square factor, with a polynomial approximation of the log-det barrier and a fixed initialization, converges geometrically and gives a gradient-based certificate of approximate optimality or infeasibility.
Critical strengths
- The paper is transparent about the scope of its contributions.
- The constructions use several neat technical devices.
Critical weaknesses
- The motivation for treating gradient descent as a computation model is weak.
The paper frames gradient descent as a computation model ("gradient descent program"), but it never explains what this framing gains, or what it tells us about gradient descent as it is actually used.
Prior work used this framing for a clear purpose. [1] work with natural learning objectives (soft-margin SVM, one-hidden-layer ReLU networks) fed with data points. They show that the fine-grained behavior of online GD on such problems is PSPACE-hard to predict, even though it nearly converges. [2] use emulation to show that SGD is universal for efficient learning, and they separate SGD from full-batch GD and SQ algorithms. That result says something concrete about what deep learning can and cannot learn. In both cases, the conclusion is about GD on learning problems.
In this work, the objectives are hand-built interpreters. They use dual-rail encodings, smooth-step "read" polynomials, step size 1 and exact arithmetic. As a result, the universality claim is close to tautological: with an arbitrary objective, one GD step can implement any polynomial update rule. That shows nothing about GD's power on any problem one would actually optimize. It also does not answer the opening question of "how efficiently" GD executes algorithms: running a circuit through the compiled objective is never cheaper than evaluating the circuit directly. Similarly, a PSPACE-hardness result is given in Section 3, but it is unclear what the result implies for reasoning about practical training dynamics.
"Gradient descent program" is never formally defined. The paper also does not impose any of the restrictions that would make it a non-trivial model with its own resources and separations, such as noise, bounded precision, conditioning, or natural objective classes.
- The paper is a compilation of loosely related results, and its length makes it infeasible to review at a conference like ICLR.
The submission has a 9-page main text and about 85 pages of appendices with dozens of theorems, lemmas and propositions. The main text is effectively an extended abstract: almost every claim can only be checked in the appendix. Verifying these proofs within an ICLR review period is not realistic, so reviewers cannot vouch for correctness.
Furthermore, the paper is essentially composed of two halves that are technically independent. The execution/complexity half (Sections 2-3) and the factored-SDP optimization/landscape half (Section 4) share no technical content. No result in Section 4 starts from a circuit or uses the compilers of Sections 2-3. The circuit-to-moment-matrix lift that is supposed to connect them is described in a paragraph and never analyzed. All of the applications (MAX-CUT, Lovász theta, matrix completion, K-means, contrastive learning) start from standard SDP formulations, not from circuits.
[1] V. Chatziafratis, T. Roughgarden, J. R. Wang. On the Computational Power of Online Gradient Descent. COLT 2019. [2] E. Abbe, C. Sandon. Poly-time Universality and Limitations of Deep Learning. Communications on Pure and Applied Mathematics, 2023 (arXiv:2001.02992).
Questions for authors
What conclusion about gradient descent as used in machine learning or optimization follows from this work but not from prior work?