PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Lie-Bracket Approximations for Zeroth-Order Optimization on Manifolds

Mahmoud Abdelgalil, Miroslav Krstic, Jorge I. Poveda

arXiv:2609.38069v1math.OCcs.SYeess.SY

TL;DR

Global zeroth-order optimization on smooth manifolds lacks continuous-time frameworks that avoid gradient evaluations. This paper introduces a stochastic Lie-bracket random ODE and shows that its fixed-parameter dynamics yield infinite-horizon practical probabilistic guarantees, with a limiting Langevin diffusion concentrating near global minimizers.

  • Problem

    Continuous-time geometric frameworks for global zeroth-order optimization on smooth manifolds remain largely unexplored, despite the need for global guarantees without gradient information.

    Source: §I · p. 1

  • Method

    The paper drives a random ODE with McShane-type Wiener-process approximations and an actuation-frame compensation to approximate Riemannian Langevin dynamics using objective measurements.

    Source: §I · p. 1

  • Results

    At fixed ε > 0, the approximating dynamics yield global practical probabilistic optimization guarantees over infinite horizons and arbitrary initial conditions.

    Source: §I · pp. 1–2

  • Takeaways & Limitations

    The algorithm’s objective-measurement-only dynamics can have global measure-theoretic guarantees on compact manifolds through fixed-parameter invariant-measure analysis.

    Source: §I · pp. 1–2

    For general compact boundaryless manifolds and objectives, convergence of the limiting diffusion to its invariant measure can be slow for large κ.

    Source: §IV · p. 3

Abstract

from arXiv · show

We propose a continuous-time algorithm for zeroth-order global optimization of smooth functions on compact manifolds that synthesizes Riemannian gradient dynamics using only objective measurements, without evaluating gradients. The algorithm is formulated as an ordinary differential equation driven by piecewise-smooth McShane-type approximations of the Wiener process, with a geometric compensation term that depends only on the actuation frame and not on the objective function. Our main result establishes infinite-horizon practical probabilistic guarantees for fixed approximation parameters. To this end, we show that the algorithm's trajectories approximate, in the mean-square sense, a Riemannian Langevin diffusion whose unique invariant Gibbs measure concentrates on the set of global minimizers. We exploit this approximation to establish finite-horizon probabilistic convergence guarantees and directly analyze the algorithm's long-time behavior to obtain the infinite-horizon result.

I. INTRODUCTION

The paper addresses the lack of continuous-time, zeroth-order frameworks for global optimization on smooth manifolds. It introduces stochastic Lie-bracket approximations and analyzes their long-time behavior at fixed approximation parameters.

I. INTRODUCTION

  • Continuous-time geometric frameworks for global zeroth-order optimization on smooth manifolds remain largely unexplored, while existing stochastic zeroth-order methods are predominantly discrete-time.The introduction also notes that gradient-based methods can have spurious equilibria and that deterministic extremum seeking on manifolds generally offers only local or almost-global convergence.Source: §I · p. 1
  • Stochastic Lie-bracket approximations (SLBA) combine bounded update rates with Brownian dithering to optimize using objective measurements without additional cost-function knowledge.The algorithm is a random ODE driven by McShane-type approximations of a Wiener process, with a drift compensation depending on the actuation frame rather than the objective.Source: §I · p. 1
  • At fixed ε > 0, the sampled dynamics admit invariant measures whose long-time behavior yields global practical probabilistic guarantees over infinite horizons and arbitrary initial conditions.The paper identifies invariant-measure analysis of the fixed-ε approximating dynamics as a novelty relative to stochastic extremum seeking.Source: §I · pp. 1–2

II. NOTATION AND PRELIMINARIES

The preliminaries establish the paper’s manifold setting and notation for geometric operators, distances, norms, and probability measures.

II. NOTATION AND PRELIMINARIES

  • M denotes a smooth, connected, compact, orientable n-dimensional manifold without boundary, embedded in R^m.The notation includes tangent and cotangent spaces and the Borel σ-algebra of M.Source: §II · p. 2
  • The Riemannian metric determines the meanings of grad, div, Δ, Hess, and ∇, while d denotes geodesic distance and vol the Riemannian density.The text also defines smooth functions, continuous functions, smooth vector fields, Lie brackets, and flows.Source: §II · p. 2
  • Probability measures on M use weak convergence, total variation, and bounded-Lipschitz distance; E and P denote expectation and probability.The bounded-Lipschitz distance metrizes weak convergence on compact M.Source: §II · p. 2

III. PROBLEM FORMULATION AND THE SLBA ALGORITHM

The section formulates optimization from objective evaluations alone and constructs an ODE whose stochastic limit is used to analyze its trajectories.

III. PROBLEM FORMULATION AND THE SLBA ALGORITHM

  • The objective ϕ is available only through evaluations ϕ(x), and the algorithm is designed to drive trajectories toward the minimizer set.The stated target is the set S⋆ of minimizers.Source: §III · p. 2
  • A spanning family of vector fields on M supplies the actuation frame; tangential projections of ambient coordinate fields provide one such family.The construction uses Wiener paths and increments on a grid with step ε.Source: §III · p. 2
  • The McShane-type interpolation swaps functions within a vector-field pair when their corresponding Wiener increments have opposite signs, producing piecewise-smooth dithering.Its derivative is piecewise continuous and drives the random ODE.Source: §III · p. 2
  • The ODE uses objective measurements and a compensation drift specified from the actuation frame independently of ϕ, and its vector field keeps solutions on M.As ε tends to zero, Wong–Zakai theory gives trajectory approximation by a Stratonovich SDE driven by the same sample path.Source: §III · pp. 2–3

IV. THE LIMITING DIFFUSION AND ITS GIBBS MEASURE

The limiting SDE is identified with Riemannian Langevin dynamics and has a unique Gibbs invariant measure. That measure concentrates near global minimizers as κ increases, while mixing can become slow in general.

IV. THE LIMITING DIFFUSION AND ITS GIBBS MEASURE

  • The actuation frame induces a canonical Riemannian metric, and with a suitable compensation the limiting SDE has the Riemannian Langevin generator and a unique invariant Gibbs measure.The invariant measure has density proportional to e^-2κϕ relative to Riemannian volume.Source: §IV · p. 3
  • As κ increases, the Gibbs measure assigns probability approaching one to every open neighborhood of the global minimizer set.Closed sets separated from the minimizer set have exponentially small measure in κ.Source: §IV · p. 3
  • For fixed κ, the limiting diffusion converges exponentially in total variation at a rate set by its spectral gap.For general compact boundaryless M and objective ϕ, convergence can be slow at large κ as the spectral gap decays; a uniform lower bound is available when ϕ is Morse with a unique local minimum.Source: §IV · p. 3
  • Trajectory approximation transfers limiting-diffusion mixing properties into finite-horizon probability bounds for the random ODE.The proposition applies to open sets with smooth boundary and selects ε sufficiently small for the specified horizon and tolerance.Source: §IV · p. 4

V. INVARIANT MEASURES OF THE ALGORITHM

The section moves beyond compact-time approximation by directly analyzing the sampled algorithm’s long-run behavior. Its transition kernel has invariant measures that approach the limiting Gibbs measure, yielding probabilistic bounds near and away from the global minimizers.

Long-time behavior

  • The finite-horizon exponential bound does not describe behavior as t → ∞, so the section analyzes the chain’s long-run behavior directly.The analysis fixes ε and κ unless otherwise stated.Source: §V · p. 4

Invariant measures

  • Every fixed ε > 0 gives the sampled chain an invariant probability measure because its transition operator is Feller on compact M.The chain’s Markov characterization and Feller property establish existence before its long-run behavior is analyzed.Source: §V · p. 4

Long-time behavior

  • For sufficiently small fixed ε, the sampled chain’s transition probabilities and invariant measures approach the Gibbs measure in bounded-Lipschitz distance after a sufficiently long time.Theorem 3 gives the bound uniformly over starting points and all later sampled times.Source: §V · p. 4

Probabilistic guarantees

  • For sufficiently small ε and sufficiently late samples, the algorithm assigns high probability to any open neighborhood of S⋆ and low probability to closed sets separated from S⋆.The bounds use constants depending on the selected neighborhood or closed set, but independent of κ, ε, sample index, and initial state.Source: §V · p. 4

VI. PROOFS

The proofs identify the Gibbs invariant measure and its concentration, establish convergence rates for the limiting diffusion, and connect finite-time diffusion approximation to the sampled chain’s long-run guarantees. They also show that the sampled dynamics are Markov and admit invariant measures.

Invariant measure and concentration

  • The limiting diffusion has the unique invariant Gibbs measure with density proportional to e^-2κϕ, which concentrates on S⋆ as κ increases.For closed sets disjoint from S⋆, the proof bounds their Gibbs mass by a quantity that decays exponentially with κ.Source: §VI · p. 5

Diffusion convergence

  • For each fixed κ, the diffusion converges exponentially toward its invariant measure at a rate set by the spectral gap; a Morse objective with a unique local minimum gives a gap uniformly bounded below over κ.The proof also derives total-variation bounds, including a specialized bound for a uniform initial density.Source: §VI · pp. 5–6

Sampled-chain construction

  • Independent Gaussian increments make the sampled dynamics a time-homogeneous Markov chain, and its transition operator maps continuous functions to continuous functions.The proof establishes continuity using smooth dependence on each orthant and the fact that the discontinuity set has Gaussian measure zero.Source: §VI · p. 6

Long-run approximation

  • The chain has an invariant probability measure for every ε > 0, and its transition probabilities and invariant measures approach the diffusion’s Gibbs measure for sufficiently small ε.The proof combines finite-horizon trajectory approximation with diffusion convergence and the Chapman–Kolmogorov relation.Source: §VI · pp. 6–7

Probabilistic guarantees

  • The measure approximation yields probability bounds for neighborhoods of S⋆ and closed sets separated from S⋆ at sufficiently late samples.The proof uses bounded-Lipschitz test functions to pass from measure convergence to set-probability bounds.Source: §VI · p. 7

VII. NUMERICAL EXAMPLE

The numerical example uses a vector-field family on S2 and a Morse function with a unique local minimum at x⋆. Simulations show sample paths approaching the global minimizer’s vicinity while remaining on the manifold, and ensemble statistics close to those of the associated Langevin diffusion.

VII. NUMERICAL EXAMPLE

  • The example uses S2 with the vector fields f1, f2, and f3, and a Morse function whose only local minimum is x⋆.Its two critical points are ±x⋆.Source: §VII · p. 7
  • For ε=0.02 and κ=25, random ODE (7) paths from −x⋆, where x⋆=(0,0,1), approach the global minimizer’s vicinity and remain on M for all time.Using N=256 independent paths, the study estimates P{Xk∈U} and E[ϕ(Xk)], with U={x∈M | ϕ(x)<0.06}; the approximations converge to reasonable margins of the corresponding Langevin diffusion values.Source: §VII · p. 7
  • The metric ⟨·, ·⟩ coincides with the metric induced on M by the ambient Euclidean metric on R3, and the ambient-coordinate Levi-Civita connection is ∇XY = G(x)†DXY.The example fixes x⋆ = (0, 0, 1), ε = 0.02, and κ = 25.Source: §VII · p. 7

VIII. CONCLUSIONS

The paper introduces a stochastic Lie-bracket approximation algorithm for global zeroth-order optimization on compact manifolds without boundary. Its analysis establishes finite- and infinite-horizon practical probabilistic convergence guarantees, and it identifies extensions to manifolds with boundaries as future work.

VIII. CONCLUSIONS

  • The proposed stochastic Lie-bracket approximation algorithm addresses global zeroth-order optimization on compact manifolds without boundary.Source: §VIII · p. 8
  • The analysis establishes finite- and infinite-horizon practical probabilistic convergence guarantees for the proposed scheme.Source: §VIII · p. 8
  • Extensions of the algorithm to compact manifolds with boundaries are left for future work.Source: §VIII · p. 8
Loading 2609.38069v1…