← All setups

Frank–Wolfe with Uniformly Convex Constraints

Descriptions may be stale. Consult the linked Lean sources.

Frank–Wolfe with Uniformly Convex Constraints

We consider minimizing a convex function f:E→R over a compact uniformly convex set C in a finite-dimensional real inner-product space E, starting from a given x0∈C. The gradient is L-Lipschitz on C, with L>0, and distance to the minimizer set satisfies a Hölder error bound. The oracle returns ∇f(x) at x∈C or a minimizer of a queried linear functional over C. We analyze short-step Frank–Wolfe. For ε>0, the goal is a feasible output x¯ with f(x¯)−f(x⋆)≤ε almost surely, where x⋆ minimizes f on C and the randomness comes from oracle tie-breaking.

The optimization problem is minx∈Cf(x). Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. The parameters satisfy L,D,a,c,ε>0,q>3,r>2. The algorithm receives only E, L, and x0; the parameters D,a,q,c,r,ε may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Uniformly convex feasible set). The set C is compact, contains x0, and satisfies ∥x−y∥≤D,x,y∈C. For every x,y∈C, t∈[0,1], and z∈E with ∥z∥≤1, tx+(1−t)y+at(1−t)∥x−y∥qz∈C.

Assumption 2 (Convexity and smoothness). The function f is Fréchet differentiable at every point of C. For all x,y∈C and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),∥∇f(x)−∇f(y)∥≤L∥x−y∥.

Assumption 3 (Hölder error bound). There exists x⋆∈C minimizing f over C. For every x∈C, there exists a minimizer y∈C such that ∥x−y∥≤c(f(x)−f(x⋆))1/r.

There are two query types. The gradient oracle returns ∇f(x) at x∈C. A linear minimization query accepts any g∈E and returns an atom s∈C satisfying ⟨g,s⟩≤⟨g,x⟩,x∈C. Every reply must satisfy its stated condition; selection among minimizing atoms may depend on previous queries and oracle randomness. Both query types count toward a single total oracle-call budget.

Our result is algorithm-specific: we analyze short-step Frank–Wolfe initialized at the given point x0. Each iteration first queries the gradient and then a minimizing atom, and updates according to gk=∇f(xk),sk∈argmins∈C⟨gk,s⟩,γk=min{1,⟨gk,xk−sk⟩L∥sk−xk∥2},xk+1=xk+γk(sk−xk). When sk=xk, the quotient is defined to be zero, so γk=0. Each completed iteration uses two oracle calls. After a total budget of N≥0 calls, with N an integer, the output is the last completed iterate x¯=x⌊N/2⌋. If N is odd, the final gradient query leaves this output unchanged.

The required accuracy is x¯∈C,f(x¯)−f(x⋆)≤εP-a.s., where P is the law of the oracle randomness.

Results

    Lean setup