11 Online learning and convex optimization
11.1 Online gradient descent (OGD)
- PEPit.examples.online_learning.wc_online_gradient_descent(M, D, n, wrapper='cvxpy', solver=None, verbose=1)[source]
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]; such algorithms were studied using the performance estimation technique in [3] and using the related IQCs in [4].
This code computes a worst-case guarantee for online gradient descent (OGD) with a step-size \(\gamma=D/M/\sqrt{n}\). 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 OGD; that is, \(x_t\) are the query points of OGD.
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 gradient descent is described by
\[x_{t+1} = x_t - \gamma \nabla f_t(x_t),\]where \(\gamma=D/M/\sqrt{n}\) is a step-size.
Theoretical guarantee: We compare the numerical results with those of [2, Section 2.1.2]:
\[R_n \leqslant MD\sqrt{n}.\]References:
[2] F. Orabona (2025). A Modern Introduction to Online Learning.
- Parameters:
M (float) – the Lipschitz parameter.
D (float) – the diameter of the set.
n (int) – time horizon.
wrapper (str) – the name of the wrapper to be used.
solver (str) – the name of the solver the wrapper should use.
verbose (int) –
level of information details to print.
-1: No verbose at all.
0: This example’s output.
1: This example’s output + PEPit information.
2: This example’s output + PEPit information + solver details.
- Returns:
pepit_tau (float) – worst-case value
theoretical_tau (float) – theoretical value
Example
>>> M,D,n = 1, .5, 2 >>> pepit_tau, theoretical_tau = wc_online_gradient_descent(M=M, D=D, n=n, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 10x10 (PEPit) Setting up the problem: performance measure is the minimum of 1 element(s) (PEPit) Setting up the problem: Adding initial conditions and general constraints ... (PEPit) Setting up the problem: initial conditions and general constraints (0 constraint(s) added) (PEPit) Setting up the problem: interpolation conditions for 3 function(s) Function 1 : Adding 4 scalar constraint(s) ... Function 1 : 4 scalar constraint(s) added Function 2 : Adding 4 scalar constraint(s) ... Function 2 : 4 scalar constraint(s) added Function 3 : Adding 28 scalar constraint(s) ... Function 3 : 28 scalar constraint(s) added (PEPit) Setting up the problem: additional constraints for 0 function(s) (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 0.7071068079799386 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 1.1705181160638522e-08 All the primal scalar constraints are verified up to an error of 4.569347711314009e-08 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual scalar values associated with inequality constraints are nonnegative up to an error of 4.8776329641953e-09 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 2.614006627199603e-07 (PEPit) Final upper bound (dual): 0.7071068126252953 and lower bound (primal example): 0.7071068079799386 (PEPit) Duality gap: absolute: 4.6453566548976255e-09 and relative: 6.569526134486629e-09 *** Example file: worst-case regret of online gradient descent (fixed step-sizes) *** PEPit guarantee: R_n <= 0.707107 Theoretical guarantee: R_n <= 0.707107
11.2 Online Frank-Wolfe (OFW)
- PEPit.examples.online_learning.wc_online_frank_wolfe(M, D, n, wrapper='cvxpy', solver=None, verbose=1)[source]
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].
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{split}\begin{eqnarray} \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{eqnarray}\end{split}\]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.
- Parameters:
M (float) – the Lipschitz parameter.
D (float) – the diameter of the set.
n (int) – time horizon.
wrapper (str) – the name of the wrapper to be used.
solver (str) – the name of the solver the wrapper should use.
verbose (int) –
level of information details to print.
-1: No verbose at all.
0: This example’s output.
1: This example’s output + PEPit information.
2: This example’s output + PEPit information + solver details.
- Returns:
pepit_tau (float) – worst-case value
theoretical_tau (float) – theoretical value
Example
>>> M, D, n = 1, .5, 2 >>> pepit_tau, theoretical_tau = wc_online_frank_wolfe(M=M, D=D, n=n, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 10x10 (PEPit) Setting up the problem: performance measure is the minimum of 1 element(s) (PEPit) Setting up the problem: Adding initial conditions and general constraints ... (PEPit) Setting up the problem: initial conditions and general constraints (0 constraint(s) added) (PEPit) Setting up the problem: interpolation conditions for 3 function(s) Function 1 : Adding 4 scalar constraint(s) ... Function 1 : 4 scalar constraint(s) added Function 2 : Adding 4 scalar constraint(s) ... Function 2 : 4 scalar constraint(s) added Function 3 : Adding 28 scalar constraint(s) ... Function 3 : 28 scalar constraint(s) added (PEPit) Setting up the problem: additional constraints for 0 function(s) (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 0.9330127185046186 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 3.831994018595078e-09 All the primal scalar constraints are verified up to an error of 1.2383195857612606e-08 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual scalar values associated with inequality constraints are nonnegative (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 7.157025748731026e-08 (PEPit) Final upper bound (dual): 0.9330127200996287 and lower bound (primal example): 0.9330127185046186 (PEPit) Duality gap: absolute: 1.595010012955811e-09 and relative: 1.709526549125938e-09 *** Example file: worst-case regret of online Frank-Wolfe *** PEPit guarantee: R_n <= 0.933013 Theoretical guarantee: R_n <= 1.47558
11.3 Follow-the-leader (FTL)
- PEPit.examples.online_learning.wc_online_follow_leader(M, D, n, wrapper='cvxpy', solver=None, verbose=1)[source]
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].
This code computes a worst-case guarantee for follow the leader (FTL). 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 FTL; that is, \(x_t\) are the query points of OGD.
In short, for given values of \(n\), \(M\), \(D\): \(\tau(n, M, D)\) is computed as the worst-case value of \(R_n\).
Algorithm: Follow the leader is described by
\[x_{t+1} \in \text{argmin}_{x\in Q} \left( \sum_{i=1}^t f_i(x) \right).\]Theoretical guarantee: The follow the leader strategy is known to have a linear regret (see, e.g., [1, Chapter 5]); we do not compare to any guarantee here.
References:
[2] F. Orabona (2025). A Modern Introduction to Online Learning.
- Parameters:
M (float) – the Lipschitz parameter.
D (float) – the diameter of the set.
n (int) – time horizon.
wrapper (str) – the name of the wrapper to be used.
solver (str) – the name of the solver the wrapper should use.
verbose (int) –
level of information details to print.
-1: No verbose at all.
0: This example’s output.
1: This example’s output + PEPit information.
2: This example’s output + PEPit information + solver details.
- Returns:
pepit_tau (float) – worst-case value
theoretical_tau (float) – theoretical value
Example
>>> M, D, n = 1, .5, 2 >>> pepit_tau, theoretical_tau = wc_online_follow_leader(M=M, D=D, n=n, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 10x10 (PEPit) Setting up the problem: performance measure is the minimum of 1 element(s) (PEPit) Setting up the problem: Adding initial conditions and general constraints ... (PEPit) Setting up the problem: initial conditions and general constraints (0 constraint(s) added) (PEPit) Setting up the problem: interpolation conditions for 3 function(s) Function 1 : Adding 9 scalar constraint(s) ... Function 1 : 9 scalar constraint(s) added Function 2 : Adding 4 scalar constraint(s) ... Function 2 : 4 scalar constraint(s) added Function 3 : Adding 15 scalar constraint(s) ... Function 3 : 15 scalar constraint(s) added (PEPit) Setting up the problem: additional constraints for 0 function(s) (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 0.933012716710238 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 7.082570717379284e-09 All the primal scalar constraints are verified up to an error of 2.8049949474251434e-08 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual scalar values associated with inequality constraints are nonnegative up to an error of 2.2603605415766684e-10 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.0515587808859884e-07 (PEPit) Final upper bound (dual): 0.9330127181067216 and lower bound (primal example): 0.933012716710238 (PEPit) Duality gap: absolute: 1.3964835954283217e-09 and relative: 1.4967465827821315e-09 *** Example file: worst-case regret of online follow the leader *** PEPit guarantee: R_n <= 0.933013
11.4 Follow-the-regularized-leader (FTRL)
- PEPit.examples.online_learning.wc_online_follow_regularized_leader(M, D, n, wrapper='cvxpy', solver=None, verbose=1)[source]
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]; such algorithms were studied using the performance estimation technique in [3].
This code computes a worst-case guarantee for follow the regularized leader (FTRL). 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 FTRL; that is, \(x_t\) are the query points of OGD.
In short, for given values of \(n\), \(M\), \(D\): \(\tau(n, M, D)\) is computed as the worst-case value of \(R_n\).
Algorithm: Follow the regularized leader is described by
\[x_{t+1} \in \text{argmin}_{x\in Q} \left( \sum_{i=1}^t f_i(x) + \tfrac{\eta}{2}\|x-x_1\|^2 \right).\]Theoretical guarantee: The follow the regularized leader strategy is known to enjoy sublinear regret (see, e.g., [1, Theorem 5.2]); we compare with the bound:
\[R_n \leqslant MD\sqrt{n}\]with a regularization strength \(\eta=D/M/\sqrt{n}\).
References:
[2] F. Orabona (2025). A Modern Introduction to Online Learning.
- Parameters:
M (float) – the Lipschitz parameter.
D (float) – the diameter of the set.
n (int) – time horizon.
wrapper (str) – the name of the wrapper to be used.
solver (str) – the name of the solver the wrapper should use.
verbose (int) –
level of information details to print.
-1: No verbose at all.
0: This example’s output.
1: This example’s output + PEPit information.
2: This example’s output + PEPit information + solver details.
- Returns:
pepit_tau (float) – worst-case value
theoretical_tau (float) – theoretical value
Example
>>> M, D, n = 1, .5, 2 >>> pepit_tau, theoretical_tau = wc_online_follow_regularized_leader(M=M, D=D, n=n, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 10x10 (PEPit) Setting up the problem: performance measure is the minimum of 1 element(s) (PEPit) Setting up the problem: Adding initial conditions and general constraints ... (PEPit) Setting up the problem: initial conditions and general constraints (0 constraint(s) added) (PEPit) Setting up the problem: interpolation conditions for 3 function(s) Function 1 : Adding 9 scalar constraint(s) ... Function 1 : 9 scalar constraint(s) added Function 2 : Adding 4 scalar constraint(s) ... Function 2 : 4 scalar constraint(s) added Function 3 : Adding 15 scalar constraint(s) ... Function 3 : 15 scalar constraint(s) added (PEPit) Setting up the problem: additional constraints for 0 function(s) (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (wrapper:cvxpy, solver: MOSEK); optimal value: 0.7071068096527651 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 7.3442036099876085e-09 All the primal scalar constraints are verified up to an error of 2.9812280422092385e-08 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual scalar values associated with inequality constraints are nonnegative up to an error of 1.6889222586942237e-08 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.2145136205173416e-07 (PEPit) Final upper bound (dual): 0.707106811831799 and lower bound (primal example): 0.7071068096527651 (PEPit) Duality gap: absolute: 2.1790339532756775e-09 and relative: 3.08161924553622e-09 *** Example file: worst-case regret of online follow the regularized leader *** PEPit guarantee: R_n <= 0.707107 Theoretical guarantee: R_n <= 0.707107