arXiv:2605.14151math.OCcs.LG2026-05

用随机子空间搜索全局最优,不依赖光滑性假设。

Stochastic global optimization of continuous functions via random walks on Grassmannians

  • 在低维子空间上做随机游走优化目标函数
  • 收敛速度由子空间最小值分布的几何间隙决定
  • 对窄深谷等盲区具有鲁棒性,适合非光滑问题

我们提出一种基于格拉斯曼流形上随机游走的随机全局优化方法。为最小化连续目标函数ℓ: ℝᵈ→ℝ,该方法反复采样k维线性子空间(k≪d),利用任意黑箱优化器求解限制在这些子空间上的低维问题,并更新迭代点(单调改善前一次)。与依赖凸性、光滑性、Lipschitz界或Polyak-Lojasiewicz条件的经典分析不同,我们的收敛保证仅依赖于通过ℝᵈ中某点的k维子空间上受限极小值的几何分布。我们定义了一个间隙参数——类比于随机游走的谱间隙——控制迭代点趋近全局最小值的速度。最后,我们指出同一分析可导出盲点鲁棒性:损失函数中足够狭窄、深度较大的下陷区域(小测度区域,ℓ向下剧烈下降)对算法轨迹影响有限,因其被随机子空间采样遇到的概率极低。

原文摘要 · Abstract (English)

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.

优化算法随机方法几何优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。