Online Frank Wolfe
wc_online_frank_wolfe(M::Real, D::Real, n::Int; solver = Clarabel.Optimizer, verbose = true)Problem statement
Compute a PEPit worst-case guarantee for wc_online_frank_wolfe.
Consider the online convex minimization problem, whose goal is to sequentially minimize the regret
\[R_n \triangleq \max_{x\in Q} \sum_{i=1}^n f_i(x_i)-f_i(x),\]
where the functions $f_i$ are $M$-Lipschitz and convex, and where $Q$ is a bounded closed convex set with diameter upper bounded by $D$. We also denote by $x_\star\in Q$ the solution to the minimization problem defining $R_n$ (i.e., $x_\star$ is a reference point). Classical references on the topic include [1, 2].
Performance metric
This code computes a worst-case guarantee for online Frank-Wolfe (OFW), see [1, Algorithm 27]; the code uses the choice [3, Section 2] here. That is, it computes the smallest possible $\tau(n, M, D)$ such that the guarantee
\[R_n \leqslant \tau(n, M, D)\]
is valid for any such sequence of queries of OFW; that is, $x_t$ are the query points of OFW.
In short, for given values of $n$, $M$, $D$: $\tau(n, M, D)$ is computed as the worst-case value of $R_n$.
Algorithm
Online Frank-Wolfe is described by
\[ \begin{aligned} \text{dir}_t & = & x_t-x_1 + \eta \sum_{s=1}^t g_s \\ v_{t} & = & \text{argmin}_{v\in Q} \langle \text{dir}_t;v\rangle\\ x_{t+1} & = & (1-\sigma) x_t + \sigma v_t \end{aligned}\]
where $\eta=\tfrac{D}{2M}\left(\frac{3}{n} \right)^{3/4}$ and $\sigma=\min\{1,\sqrt{3/n}\}$.
Theoretical guarantee
We compare the numerical results with those of [3, Theorem 2.1]:
\[R_n \leqslant \frac{4}{3^{3/4}} MDn^{3/4}\]
References
[2] F. Orabona (2025). A Modern Introduction to Online Learning.
Arguments
M: the Lipschitz parameter.D: the diameter of the set.n: number of iterations.solver: JuMP optimizer constructor used to solve the generated SDP.verbose: print example and solver progress information when true.
Returns
pepit_tau: worst-case valuetheoretical_tau: theoretical value
Julia usage
pepit_tau, theoretical_tau = wc_online_frank_wolfe(M, D, n; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.933013, 1.475576)