Gradient Descent Program: Universality and Landscape

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 $ϵ>0$, 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.