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

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