Abstract:Frank--Wolfe methods avoid projections, but over curved feasible regions the full-space linear minimization oracle (LMO) can itself become the computational bottleneck. We introduce random-subspace Frank--Wolfe (RSFW), the first Frank--Wolfe framework, to our knowledge, that replaces the ambient LMO by exact LMOs over random low-dimensional affine sections of a general feasible set, while preserving feasibility in the original space. For smooth convex objectives over compact strongly convex feasible sets, we prove a dimension-explicit approximate-oracle inequality and derive the standard \(O(1/k)\) open-loop rate, with high-probability and almost-sure counterparts. Under short steps and a gradient lower bound, the same geometric control yields linear convergence, and we extend the sublinear theory to finite-sum stochastic gradients. We also show that random sections can improve the local curvature model controlling short steps: for smooth objectives, the quadratic model along a sampled section is governed by the compressed Hessian, yielding computable \(d\times d\) curvature constants for quadratic objectives over balls and ellipsoids. These results provide a geometric theory of oracle-side randomization in projection-free optimization.
From: Pierre-Louis Poirion [view email]
[v1]
Sun, 24 May 2026 02:08:57 UTC (300 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。