Race to the bottom – Race to the bottom — the OPTIM@EPFL blog

Gradient descent can converge to any isolated saddle point

nonconvex

saddles

It is clear that if the Hessian at a saddle point has a positive eigenvalue, then GD can converge to that point for some initializations. We show that this still holds even if the Hessian does not have positive eigenvalues, as long as the saddle point is isolated.

Nicolas Boumal, Dmitriy Drusvyatskiy, Quentin Rebjock

The difference-of-Hadamard lift of the 1-norm regularizer enjoys \(2 \Rightarrow 1\)

nonconvex

lift

sparse

Minimizing \(f(x)\) with a 1-norm regularizer is equivalent to minimizing \(g(y, z) = f(y \odot y - z \odot z)\) with the squared 2-norm regularizer. To this known result, we add that second-order critical points \((y, z)\) map to first-order stationary points, revealing simple benign non-convexity results.

The zero-set of a nonzero real-analytic function has measure zero

analytic

If an analytic function vanishes on an open set then it is zero everywhere (Identity Theorem). This is still true if we replace open set by set of positive measure.

The usual smooth lift of the nuclear norm regularizer enjoys \(2 \Rightarrow 1\)

nonconvex

lift

rank

Minimizing \(f(X)\) with a nuclear-norm regularizer is equivalent to minimizing \(g(L, R) = f(LR^\top)\) with the squared Frobenius norm regularizer. To this classical result, we add that second-order critical points \((L, R)\) map to first-order stationary points \(LR^\top\) under a bounded-rank constraint.

Nicolas Boumal, Andrew D. McRae

Saddle avoidance and center-stable manifold: a proof from first principles for a general setup

nonconvex

saddles

CSMT

The center-stable manifold theorem is old. It has become important in non-convex optimization, but the proof is rarely spelled out. We reconstruct one here, at a level of generality that is useful to optimizers.

Andreea Musat, Nicolas Boumal

Saddle avoidance and stable manifold: a proof from first principles for a simple setup

nonconvex

saddles

CSMT

Gradient descent with fixed step-size avoids strict saddle points almost surely. The now standard proof of this fact relies on the Center Stable Manifold theorem, which may feel like a black-box. This post provides an explicit proof, back to first principles, for a simplified setting.

Nicolas Boumal, Andreea Musat

Foreword to lecture notes by Irène Waldspurger from her Cours Peccot

nonconvex

rank

Irène Waldspurger is a laureate of the Cours Peccot, and as such gave a series of lectures at the Collège de France in 2020. She wrote matching lecture notes for the Cours Spécialisés de la Société Mathématique de France. At their request, this is a foreword I wrote for these notes.

Benign landscape of the Brockett cost function: asymmetric case

nonconvex

The second-order critical points of \(f(X, Y) = \trace(AX\transpose BY)\) for \(X, Y\) orthogonal are globally optimal. This implies a number of equally well-known corollaries, including benign non-convexity of \(f(X) = \trace(AX)\) and \(f(X) = \sqfrobnorm{A-X}\) for \(X\) orthogonal.

Positive semidefinite Laplacians with negative edge weights

graphs

If an undirected graph has nonnegative edge weights, its Laplacian \(L = D-A\) is psd. Conversely, if \(L\) is psd, what does that reveal about the signs of the weights? Not much.

Benign landscape of low-rank approximation: Part II

nonconvex

rank

The landscape of \(X \mapsto \sqfrobnorm{AXB - C}\) subject to \(\rank(X) \leq r\) is benign for full rank \(A, B\). Same for the landscape of \((W_1, W_2) \mapsto \|W_2W_1 B - C\|_{\mathrm{F}}^2\) (2-layer linear neural networks). We show these by combining a few basic facts.

Nicolas Boumal, Christopher Criscitiello

Benign landscape of low-rank approximation: Part I

nonconvex

rank

The minimizers of \(\sqfrobnorm{X-M}\) subject to \(\rank(X) \leq r\) are given by the SVD of \(M\) truncated at rank \(r\). The optimization problem is nonconvex but it has a benign landscape. That’s folklore, here with a proof.

Nicolas Boumal, Christopher Criscitiello

Benign landscape of the Brockett cost function

nonconvex

The second-order critical points of \(f(X) = \trace(AX\transpose BX)\) for \(X\) orthogonal are globally optimal. This implies a number of equally well-known corollaries.

Optimality conditions on the orthogonal group

manifolds

Consider a cost function restricted to the set of orthogonal matrices or rotation matrices. Its local minima satisfy first- and second-order necessary optimality conditions, spelled out here.

Simplex, sphere, and Fisher–Rao metric

manifolds

For optimization problems on the simplex, the Fisher–Rao metric makes sense. This post reviews why that is, and spells out how to use that metric by simply lifting the problem to optimization on a standard sphere.

The Maximum Theorem

topology

If an optimization problem depends on some parameters, then the optimal value is a function of those parameters. Sometimes, that function is continuous.

Small geodesic triangles

manifolds

In a geodesic triangle \(xyz\), the vector from \(x\) to \(z\) is almost the vector from \(x\) to \(y\) plus the (parallel transported) vector from \(y\) to \(z\), if the triangle is small. The Hessian of the squared Riemannian distance function provides a neat way to quantify this.

Retractions locally preserve distance

manifolds

The Riemannian distance from \(x\) to \(\Retr_x(v)\) is not much bigger than \(\|v\|_x\) (for small \(v\)).