acceptodds
Under review as a conference paper at ICLR 2027

Gradient Descent Program: Universality and Landscape

Abstract

How efficiently can gradient descent execute an algorithm, and when does a higher-dimensional parametrization help it optimize? We show that every bounded-fan-in Boolean circuit compiles into a strongly convex objective whose unique minimizer encodes the circuit's gate values. From an initialization encoding a Boolean state, gradient descent reaches this minimizer in a number of exact-arithmetic steps proportional to the depth. Through gradient descent on one fixed strongly convex objective, we show that it is possible to simulate polynomial-space computation. Even though the trajectory converges to a known minimizer, determining the answer encoded at a specified future iteration is PSPACE-complete when the iteration count is given in binary, both in exact arithmetic and for a specified finite-precision implementation. A separate clock-free construction evaluates finite-delay Boolean circuits by projected gradient descent with linear total work using cached derivatives. We then lift Boolean circuits to bounded-trace Gram matrices, connecting execution to optimization over semidefinite relaxations. For these relaxations, we construct fixed losses on which ordinary gradient descent finds approximately feasible solutions or certifies infeasibility in polynomially many exact-arithmetic steps. For any , sufficient overparameterization gives every point more than above the global relaxation optimum many directions of negative curvature along which descent can escape. Applications include matrix factorization and completion, sensing, clustering, cuts, constraint satisfaction, moment hierarchies, and neural parameterizations.

Primary area:
optimization
Keywords:
computational universality, gradient descent, semidefinite programming, approximation algorithms, convergence guarantees

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_et2ROpenReview ↗
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
  1. The paper is transparent about the scope of its contributions.
  2. The constructions use several neat technical devices.
Critical weaknesses
  1. 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.

  1. 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?

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

The paper investigates the computational capabilities of gradient descent and the optimization landscapes of matrix representations. It shows how Boolean circuits and recurrent computations can be encoded into gradient-descent trajectories, including strongly convex constructions. It also provides theoretical guarantees for matrix optimization and rank-dependent landscape properties. The contributions are primarily theoretical, with no experimental evaluation.

Critical strengths

The paper presents mathematically detailed constructions and theoretical guarantees.

The strongly convex constructions and PSPACE-complete prediction result offer an interesting theoretical perspective on gradient-descent dynamics.

The authors acknowledge several limitations, including numerical precision requirements and the absence of guarantees for improved practical convergence rates.

Critical weaknesses

Unclear motivation and significance: The paper does not convincingly explain the value of using gradient descent to execute predefined Boolean computations or demonstrate a clear benefit for machine learning.

Lack of coherence: The paper combines several research directions without establishing a sufficiently clear connection or unified contribution.

Presentation and practical relevance: Figure 1 and several equations lack sufficient explanation. The absence of implementation or experimental evaluation also makes it difficult to assess the practical relevance of the proposed constructions, particularly given their numerical precision requirements.

Questions for authors

Beyond theoretical representability, what is the main benefit of encoding existing Boolean computations as gradient descent, particularly for machine learning?

Could the authors clarify the central connection between the circuit-execution results and the matrix-optimization results, and what unified insight the combination provides?

Reviewer_cMNNOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Gradient descent (GD) is the base of many learning algorithms in AI. This paper investigates an "execution picture" and a "landscape picture" for gradient descent. The execution picture sees GD as a a model of computation, and the authors show that one can construct objective functions for which running gradient descent is equivalent to the computation of a boolean circuit under certain conditions. They provide complexity results for these constructions, and then turn towards the landscape picture which discusses ideas from semidefinite programming. GD is run on the factorisation of a matrix, and the authors show that these results are useful for a variety of different problems.

Critical strengths
  • The theory provides some clean results that differentiate between the ease of optimising an objective and the predictability of the trajectory that a gradient descent algorithm follows when run on it
  • For the Semidefinite Programming results, the GD algorithm proposed by the authors reaches an arbitrary accuracy, and for feasibility problems a definitive result can be provided by the algorithm.
Critical weaknesses
  • The paper is difficult to read, especially for a machine learning audience. A lot of theory is compressed into nine pages, some things mentioned in the abstract only appear in the appendices, and a lot of jargon as well as technical terms are either used before being explained or are never explained. I also found it difficult to understand the connection between sections 2 and 3 and section 4, these seem mostly disjunct to me.
  • The paper is very focused on optimisation topics, and I am unsure about its relevance for a machine learning community. The theoretical results are further based on a number of assumptions, and the paper does not clarify how far away from being useful in practice these results are. Some numerical results or at least a discussion of whether any of the ideas in the paper would be helpful for accelerating e.g. algorithms used in practice would be helpful.
Questions for authors
  • What is the main takeaway from Theorem 3.1 for a machine learning audience?
  • Why is strong convexity essential to the results?
  • Given the extremely long appendices, how have the results in these been checked?
  • Could numerical results be provided that show the practical relevance of the discussions?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.