Robustness of the Frank-Wolfe Method under Inexact Oracles and the Cost of Linear Minimization
Tao Hu · 2026
Read Robustness of the Frank-Wolfe Method under Inexact Oracles and the Cost of Linear Minimization by Tao Hu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-11548.txt.
Introduction
Tao Hu tests the Frank-Wolfe method under inexact oracles in this preprint. The 2026 work deals with optimization over convex sets. Frank-Wolfe avoids projections by using a linear minimization oracle. In practice, both gradients and oracles can be inexact.
Hu asks how much error the method can tolerate. For smooth nonconvex functions, a convergence guarantee is given. The rate blends a 1 over root k decay term. An added delta term prices the oracle's inexactness. The study also weighs the oracle's cost against projection. Linear minimization is often far cheaper per step. The results tell users when cheap steps still converge.
Catalog record
| CREATOR | Tao Hu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 18 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-11548
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Robustness of the Frank-Wolfe Method under Inexact Oracles and the Cost of Linear Minimization Tao Hu Abstract We investigate the robustness of the Frank-Wolfe method when gradients are computed inexactly and examine the relative computational cost of the linear minimization oracle (LMO) versus projection. For smooth nonconvex functions, we establish a convergence guarantee of order 𝒪 ( 1 / k + δ ) \mathcal{O}(1/\sqrt{k}+\delta) for Frank-Wolfe with a δ \delta –oracle. Our results strengthen previous analyses for convex objectives and show that the oracle errors do not accumulate asymptotically. We further prove that approximate projections cannot be computationally cheaper than accurate LMOs, thus extending to the case of inexact projections. These findings reinforce the robustness and efficiency of the Frank-Wolfe framework. ∎ 1 Introduction The Frank-Wolfe method is a projection-free method for constrained optimization. At each iteration, Frank-Wolfe solves a linear minimization subproblem instead of a projection, which can be advantageous on structured domains such as simplices or spectrahedra. Classical analyses guarantee an \mathcal{O}(1/k) convergence rate for convex objectives 6 ; 4 and \mathcal{O}(1/\sqrt{k}) for nonconvex ones 7 . Despite its popularity, the robustness of Frank-Wolfe under inexact gradient information remains incompletely understood. In deterministic optimization, the \delta –oracle model 3 is used to bound the gradient error. We revisit this framework and derive new nonaccumulation bounds for both convex and nonconvex settings. Let Q\subset\mathbb{R}^{d} be a compact convex set and f:Q\to\mathbb{R} be the objective function. Denote \|\cdot\| to be the l^{2} norm. We consider the minimization problem: \begin{array}[]{rl}\min\limits_{x}&f(x)\\ \mathrm{s.t.}&x\in Q\ .\end{array} The Frank-Wolfe method, which has a linear minimization oracle as its basic module, is an effective way to address this problem. At the iteration point x_{k}\in Q , the Frank-Wolfe method solves the linear minimization subproblem \tilde{x}_{k}\in\arg\min_{x\in Q}\big\{f(x_{k})+\nabla f(x_{k})^{\top}(x-x_{k})\big\} and updates with x_{k+1}=(1-\overline{\alpha}_{k})x_{k}+\overline{\alpha}_{k}\tilde{x}_{k} where \overline{\alpha}_{k}\in[0,1) . In the convergence analysis of the Frank–Wolfe method, the following auxiliary sequences are frequently used and will also appear in our proofs: \beta_{k}=\frac{1}{\prod_{j=0}^{k-1}(1-\overline{\alpha}_{j})},\qquad\alpha_{k}=\frac{\beta_{k}\overline{\alpha}_{k}}{1-\overline{\alpha}_{k}},\qquad k\geq 1. (1) Here, \{\overline{\alpha}_{k}\}_{k=0}^{+\infty} denotes the sequence of step sizes used in our algorithm. We follow the conventions \prod_{j=0}^{-1}(\cdot):=1 and \sum_{i=0}^{-1}(\cdot):=0 . We denote the Frank-Wolfe gap at the point x\in Q as G(x)=\sup_{y\in Q}\nabla f(x)^{T}(x-y). Besides the convergence guarantee, robustness and the efficiency of the Linear Minimization Oracle are also important aspects of the Frank-Wolfe method. The performance of Frank-Wolfe under inexact gradient is a very interesting problem. With unbiased gradients and bounded variance (or sub-Gaussian tails), Stochastic Frank-Wolfe variants achieve a Frank-Wolfe gap of \mathcal{O}(\varepsilon) with \mathcal{O}(1/\varepsilon^{4}) gradient evaluations, and variance reduction accelerates finite-sum problems and can achieve the same Frank-Wolfe gap with \mathcal{O}(1/\varepsilon^{3}) gradient evaluations 11 ; 5 ; 9 ; 8 ; 16 ; 13 . For heavy-tailed noise, Stochastic Frank-Wolfe with clipping or robust estimation achieves high-probability guarantees 14 ; 12 . In the deterministic setting, there is situation where the gradient error is bounded by \delta/D but can be arbitrarily chosen along the training trajectory. This case is often relaxed and referred to as obtaining a \delta -oracle: \left|(g_{\delta}(x)-\nabla f(x))^{T}(x-y)\right|\leq\delta,\,\forall\;y\in Q. (2) If we use an increasingly accurate gradient along the iterates, like if \left|(g_{\delta}(x_{k})-\nabla f(x_{k}))^{T}(x_{k}-y)\right|\leq\frac{1}{k+1}\delta LD^{2},\,\forall\;y\in Q, then G(x_{k})\leq\frac{27LD^{2}}{4(k+2)}(1+\delta). For the more common scenario, where the error does not decrease, Freund and Grigas prove an \mathcal{O}(1/k+\delta) convergence of the Frank-Wolfe gap 4 , and we show an \mathcal{O}(1/\sqrt{k}+\delta) convergence for nonconvex functions in this paper. Sometimes we consider objective functions that are convex but non-smooth or the case when the gradients are computed at shifted points 2 . Those functions may not obtain a gradient, but they can be equipped with a (\delta,L) oracle 3 : 0\leq f(x)-(f_{\delta,L}(y)+g_{\delta,L}(y)^{T}(x-y))\leq\frac{L}{2}\|x-y\|^{2}+\delta,\,\forall\;x,y\in Q. Since the first bound of the Frank-Wolfe gap under (\delta,L)- oracle, which is \mathcal{O}(1/k+k\delta) , has been proposed 4 , it has been an open problem for more than ten years whether the final guarantee of the Frank-Wolfe gap is optimal theoretically. Besides robustness, the ease of computing the Linear Minimization Oracle is widely considered another major advantage of the Frank–Wolfe method, which makes it more prevalent than proximal gradient methods. However, this belief is currently supported mainly by intuition and set-specific comparisons 1 ; 10 . Additionally, we address a recent question posed by Woodstock 15 on whether linear minimization oracles are inherently cheaper than projection operators. We show that even coarse, approximate projections cannot outperform accurate LMOs in computational complexity. Our main contributions are as follows: (i) Nonconvex Frank-Wolfe with a \delta -oracle. We prove that for L -smooth nonconvex objectives, Frank-Wolfe with a \delta -oracle achieves \min_{0\leq k\leq K}G(x^{k})\ \leq\ \sqrt{\frac{2C\,(f(x^{0})-f^{*})}{K+1}}\ +\ 2\delta. (ii) Projection vs. LMO. We prove that a K -approximate projection at a scaled point -\lambda x produces an \varepsilon -accurate LMO at x with \varepsilon=\mathcal{O}((K+D^{2})/\lambda) , establishing that approximate projections can not be uniformly easier than LMOs. 2 Frank-Wolfe with an Inexact Oracle Let Q\subset\mathbb{R}^{d} be compact and convex, and f:Q\to\mathbb{R} be convex with L -Lipschitz gradient. The Frank-Wolfe update in Algorithm 1 uses the \delta -oracle g_{\delta} defined in ( 2 ). Algorithm 1 Frank-Wolfe with a \delta -oracle 1: Initialize x_{0}\in Q . 2: for k=0,1,2,\ldots do 3: Query g_{\delta}(x_{k}) . 4: Solve \tilde{x}_{k}=\arg\min_{x\in Q}g_{\delta}(x_{k})^{\top}(x-x_{k}) . 5: Set x_{k+1}=x_{k}+\overline{\alpha}_{k}(\tilde{x}_{k}-x_{k}) , \overline{\alpha}_{k}\in[0,1) . 6: end for Lemma 2.1 Under ( 2 ), for any x_{k}\in Q , f^{\star}\;\geq\;f(x_{k})\;+\;\min_{x\in Q}g_{\delta}(x_{k})^{\top}(x-x_{k})\;-\;\delta. Proof By convexity, f(x)\geq f(x_{k})+\nabla f(x_{k})^{\top}(x-x_{k}) for any x\in Q . From ( 2 ), \nabla f(x_{k})^{\top}(x-x_{k})\geq g_{\delta}(x_{k})^{\top}(x-x_{k})-\delta . Therefore, f(x)\geq f(x_{k})+g_{\delta}(x_{k})^{T}(x-x_{k})-\delta. Taking \min_{x\in Q} on both sides yields the claim. We also recall a subproblem-level accuracy transfer. Proposition 2.2 ( ( 4 , Prop. 5.1) ) Fix \overline{x}\in Q and \delta\geq 0 . If \tilde{x}\in\arg\min_{x\in Q}g_{\delta}(\overline{x})^{\top}x , then \nabla f(\overline{x})^{\top}\tilde{x}\;\leq\;\min_{x\in Q}\nabla f(\overline{x})^{\top}x\;+\;2\delta. The convergence theorem of Frank-Wolfe with a \delta - oracle on convex objectives is given by Freund and Grigas as follows (one can actually show that the result of Freund and Grigas actually applies to the widest range of step-sizes): Theorem 2.3 (Nonaccumulation under \delta -oracle, convex case 4 ) Let Q be compact convex with diameter D , and f be convex with L -Lipschitz gradient on Q . Let g_{\delta} satisfy ( 2 ). For the Frank-Wolfe iterates of Algorithm 1 with stepsize satisfying \sum_{k=0}^{+\infty}\overline{\alpha}_{k}=\infty , \sum_{k=0}^{+\infty}\overline{\alpha}_{k}^{2}<\infty and \overline{\alpha}_{k}\downarrow 0 , then f(x_{k+1})-f^{*}\leq(1-\overline{\alpha}_{k})\big(f(x_{k})-f^{*}\big)+2\overline{\alpha}_{k}\delta+\tfrac{1}{2}LD^{2}\overline{\alpha}_{k}^{2}, (3) and hence \displaystyle\limsup_{k\to\infty}(f(x_{k})-f^{\star})\leq 2\delta . Example 2.4 (Tightness up to constants) Let Q=[-1,1] , f(x)=\tfrac{1}{2}x^{2} (convex, L=1 , D=2 ). Define a \delta -oracle by g_{\delta}(x)=\nabla f(x)-\tfrac{\delta}{D}\,\operatorname{sign}(x) . Frank-Wolfe with \overline{\alpha}_{k}=2/(k+2) converges to a neighborhood whose size is proportional to \delta . 3 Nonconvex Frank-Wolfe with an Inexact Oracle We now consider nonconvex minimization over a compact convex set S\subset\mathbb{R}^{d} : \min_{x\in S}f(x), where f is differentiable and has L -Lipschitz gradient on S . Denote D:=\operatorname{Diam}(S) and set C\;\triangleq\;\max\{\,LD^{2},\;GD\,\}\quad\text{with}\quad G:=\sup_{x\in S}\|\nabla f(x)\|<\infty. The Frank-Wolfe gap at x is G(x)\;\triangleq\;\max_{s\in S}\,\langle\nabla f(x),\,x-s\rangle. We assume access to a \delta -oracle for the gradient, i.e., for every x\in S there exists g_{\delta}(x) such that \big|\langle\nabla f(x)-g_{\delta}(x),\,s-x\rangle\big|\ \leq\ \delta\quad\forall\,s\in S. (4) Define the approximate Frank-Wolfe gap \tilde{G}(x)\;\triangleq\;\max_{s\in S}\,\langle g_{\delta}(x),\,x-s\rangle. From ( 4 ) it follows that |\,G(x)-\tilde{G}(x)\,|\ \leq\ \delta. (5) Algorithm 2 Nonconvex Frank-Wolfe with a \delta -oracle 1: Input: x^{0}\in S , curvature constant C\geq\max\{LD^{2},\,GD\} , error level \delta\geq 0 . 2: for k=0,1,2,\ldots do 3: Query