Stochastic global optimization of continuous functions via random walks on Grassmannians

We introduce a stochastic global optimization method based on random walks on Grassmannian manifolds. To minimize a continuous objective \(\ell:\mathbb{R}^d \rightarrow \mathbb{R}\), the method repeatedly samples random \(k\)-dimensional linear subspaces (with \(k \ll d\)), solves the resulting low-dimensional restrictions of these problems to these subspaces using an arbitrary black-box optimizer, and updates the iterate (which monotonically improves upon the previous iterate). Unlike classical optimization analyses that rely on convexity, smoothness, Lipschitz bounds, or Polyak-Lojasiewicz-type conditions, our convergence guarantees depend only on the geometric distribution of restricted minima across the \(k\)-dimensional subspaces passing through a given point in \(\mathbb{R}^d\). We identify a gap parameter — an analogue of a spectral gap for random walks — that controls the rate at which the iterates approach the global minimum value. Finally, we argue that the same analysis yields a blind-spot robustness property: sufficiently narrow, deep dips of the loss function (small-measure regions where \(\ell\) spikes downward) have limited influence on the algorithm’s trajectory, since they are unlikely to be encountered by random subspace sampling.