Random-Subspace Frank--Wolfe over Strongly Convex Sets
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911713831419904 |
|---|---|
| author | Poirion, Pierre-Louis Pokutta, Sebastian Takeda, Akiko |
| author_facet | Poirion, Pierre-Louis Pokutta, Sebastian Takeda, Akiko |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_24819 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Random-Subspace Frank--Wolfe over Strongly Convex Sets Poirion, Pierre-Louis Pokutta, Sebastian Takeda, Akiko Optimization and Control 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. |
| title | Random-Subspace Frank--Wolfe over Strongly Convex Sets |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2605.24819 |