Race to the bottom — the OPTIM@EPFL blog

The sphere-to-simplex lift enjoys \(4 \Rightarrow 2\) (and \(3\) is not enough)

nonconvex

lift

simplex

Entrywise squaring (\(y \mapsto y \odot y\)) maps the unit sphere onto the probability simplex. As a result, to minimize \(f\) over the simplex, one can minimize \(g(y) = f(y \odot y)\) on the sphere instead. If \(y\) is second-order critical for \(g\), then its image \(x = y \odot y\) satisfies first-order optimality conditions for \(f\), but \(x\) may only satisfy part of the second-order conditions. We show that, for \(x\) to satisfy the full second-order conditions, it is enough to require \(y\) to be fourth-order critical (and this is sharp).

Pablo Habib, Andreea Musat, Nicolas Boumal

Randomization is necessary to escape saddle points in high dimension

nonconvex

saddles

It is folklore that deterministic optimization algorithms can have a hard time escaping saddle points in high-dimensional settings. We propose one way of making this precise, with a resisting oracle argument.

Radu Dragomir, Nicolas Boumal

When the Hessian is a proxy for its Gauss–Newton approximation (and not the other way around)

nonconvex

PL

Classically, we think of the Gauss–Newton map as a convenient (though imperfect) approximation of the Hessian. Here, I argue that (in the overparameterized regime), some kind of Gauss–Newton “approximation” is actually what we want—and the Hessian may be a way to access it.

Pointers for my students on giving talks

communication

We all give talks and lectures. We can all improve. These are some pointers I assembled for my undergraduate math students long ago.

An old proof that the Morse Lemma loses only one order of regularity

calculus

saddles

The Morse Lemma states that a smooth function can be locally deformed to a pure quadratic near a nondegenerate critical point. The common proofs to that effect lose two orders of regularity, but an old proof shows how to lose only one.

Smooth, globally Polyak–Łojasiewicz functions are nonlinear least-squares

And other neat facts, including hidden geodesic convexity

PL

flows

nonconvex

topology

PŁ functions abound in the literature, especially in optimization. When they are also smooth, they become surprisingly simple—with an exotic twist.

Nicolas Boumal, Christopher Criscitiello, Quentin Rebjock

A different way to define embedded submanifolds: Part I

Smooth retracts are smooth manifolds

manifolds

There are several ways to define manifolds, and the definition we choose conditions all the work that follows. One little known definition may just be the best entry point yet: an embedded submanifold of \(\Rd\) is nothing but the image of a smooth idempotent map.

A different way to define embedded submanifolds: Part II

Building the basics of differential geometry, smoothly

manifolds

In this second part, we start from the definition “the submanifolds of \(\Rd\) are the images of smooth idempotent maps” and build up basic concepts from there: tangent bundles, smooth maps, differentials, metrics, gradients, etc. There is surprisingly little friction. Is this the better way to approach differential geometry?

The google sheet setup I use to grade assignments

tools

My graders and I use a custom Google Sheet to grade problem sets. It’s designed so that the penalties assigned to each type of mistake can be decided at the end, which I find makes the whole process much smoother. And it sends e-mails. You’re welcome to use it too!

The Sasaki metric for Riemannian submanifolds of Euclidean space

manifolds

Given a Riemannian manifold \(\calM\), the Sasaki metric is a natural Riemannian metric for the tangent bundle \(\T\calM\). It is often described axiomatically, but it also admits a simple, transparent formula for the common case where \(\calM\) is a Riemannian submanifold of a Euclidean space. This post provides the formula and illustrates it on the sphere.

Designing polynomials for Muon’s polar factorization: focus on quintics

Muon

Stiefel

The polar factor \(Q\) of a matrix \(X\) is its projection to the set of orthonormal matrices. This is used in the Muon optimization algorithm for LLMs, and also for retractions in optimization on the Stiefel manifold. The polar factor can be well approximated using a polynomial function of \(X\). Here is one more take on how to design that polynomial as a product of quintics.

Nicolas Boumal, Antoine Gonon

Differential of the time-one map of a flow at a critical point

flows

To apply tools from discrete dynamical systems to continuous ones, the standard trick is to iterate the time-one map \(\Phi^1\) of the continuous flow on \(V\). Often, this requires understanding the differential of that time-one map at a critical point \(x\), namely, \(\D\Phi^1(x) = e^{\D V(x)}\). This post derives that formula.

If a smooth function is globally PŁ and coercive, then it has a unique minimizer

PL

nonconvex

If a real-valued function \(f\) is twice continuously differentiable and coercive, and if it also satisfies the Polyak-Łojasiewicz condition globally, then it has a unique minimizer.

Chris Criscitiello, Quentin Rebjock, Nicolas Boumal

Norm of linear combination of unit norm vectors: benign up and down

nonconvex

Some nonconvex functions are easy to minimize but not to maximize, or the other way around. Here is one more example where both are easy.

Maximizing the 4-norm over orthogonal matrices has a benign landscape

nonconvex

Consider maximizing \(\sum_{i,j} X_{ij}^4\) for \(X\) orthogonal. This problem has the strict saddle property, that is, its second-order critical points are globally optimal.

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

lift

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\)).