10 Continuous-time models
10.1 Gradient flow for strongly convex functions
- PEPit.examples.continuous_time_models.wc_gradient_flow_strongly_convex(mu, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the convex minimization problem
\[f_\star \triangleq \min_x f(x),\]where \(f\) is \(\mu\)-strongly convex.
This code computes a worst-case guarantee for a gradient flow. That is, it computes the smallest possible \(\tau(\mu)\) such that the guarantee
\[\frac{d}{dt}\mathcal{V}(X_t) \leqslant -\tau(\mu)\mathcal{V}(X_t) ,\]is valid, where \(\mathcal{V}(X_t) = f(X_t) - f(x_\star)\), \(X_t\) is the output of the gradient flow, and where \(x_\star\) is the minimizer of \(f\). In short, for given values of \(\mu\), \(\tau(\mu)\) is computed as the worst-case value of the derivative \(f(X_t)-f_\star\) when \(f(X_t) - f(x_\star)\leqslant 1\).
Algorithm: For \(t \geqslant 0\),
\[\frac{d}{dt}X_t = -\nabla f(X_t),\]with some initialization \(X_{0}\triangleq x_0\).
Theoretical guarantee:
The following tight guarantee can be found in [1, Proposition 11]:
\[\frac{d}{dt}\mathcal{V}(X_t) \leqslant -2\mu\mathcal{V}(X_t).\]The detailed approach using PEPs is available in [2, Theorem 2.1].
References:
- Parameters:
mu (float) – the strong convexity parameter
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
>>> pepit_tau, theoretical_tau = wc_gradient_flow_strongly_convex(mu=0.1, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 3x3 (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 (1 constraint(s) added) (PEPit) Setting up the problem: interpolation conditions for 1 function(s) Function 1 : Adding 2 scalar constraint(s) ... Function 1 : 2 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.20000002010539425 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 7.215841463375114e-10 All the primal scalar constraints are verified up to an error of 7.074286711983291e-10 (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.684026647576401e-09 (PEPit) Final upper bound (dual): -0.200000025742216 and lower bound (primal example): -0.20000002010539425 (PEPit) Duality gap: absolute: -5.6368217593583125e-09 and relative: 2.8184105963528753e-08 *** Example file: worst-case performance of the gradient flow *** PEPit guarantee: d/dt[f(X_t)-f_*] <= -0.2 (f(X_t) - f(x_*)) Theoretical guarantee: d/dt[f(X_t)-f_*] <= -0.2 (f(X_t) - f(x_*))
10.2 Gradient flow for convex functions
- PEPit.examples.continuous_time_models.wc_gradient_flow_convex(t, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the convex minimization problem
\[f_\star \triangleq \min_x f(x),\]where \(f\) is convex.
This code computes a worst-case guarantee for a gradient flow. That is, it verifies the following inequality
\[\frac{d}{dt}\mathcal{V}(X_t, t) \leqslant 0,\]is valid, where \(\mathcal{V}(X_t, t) = t(f(X_t) - f(x_\star)) + \frac{1}{2} \|X_t - x_\star\|^2\), \(X_t\) is the output of the gradient flow, and where \(x_\star\) is the minimizer of \(f\). In short, for given values of \(t\), it verifies \(\frac{d}{dt}\mathcal{V}(X_t, t)\leqslant 0\).
Algorithm: For \(t \geqslant 0\),
\[\frac{d}{dt}X_t = -\nabla f(X_t),\]with some initialization \(X_{0}\triangleq x_0\).
Theoretical guarantee:
The following tight guarantee can be found in [1, p. 7]:
\[\frac{d}{dt}\mathcal{V}(X_t, t) \leqslant 0.\]After integrating between \(0\) and \(T\),
\[f(X_T) - f_\star \leqslant \frac{1}{2T}\|x_0 - x_\star\|^2.\]The detailed approach using PEPs is available in [2, Theorem 2.3].
References:
- Parameters:
t (float) – time step
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
>>> pepit_tau, theoretical_tau = wc_gradient_flow_convex(t=2.5, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 3x3 (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 1 function(s) Function 1 : Adding 2 scalar constraint(s) ... Function 1 : 2 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: 2.1751470009922017e-09 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 1.3103319435143524e-08 All the primal scalar constraints are verified up to an error of 3.275724880100672e-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.927686319275464e-08 (PEPit) Final upper bound (dual): 0.0 and lower bound (primal example): 2.1751470009922017e-09 (PEPit) Duality gap: absolute: -2.1751470009922017e-09 and relative: -1.0 *** Example file: worst-case performance of the gradient flow *** PEPit guarantee: d/dt V(X_t) <= 0.0 Theoretical guarantee: d/dt V(X_t) <= 0.0
10.3 Accelerated gradient flow for strongly convex functions
- PEPit.examples.continuous_time_models.wc_accelerated_gradient_flow_strongly_convex(mu, psd=True, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the convex minimization problem
\[f_\star \triangleq \min_{x\in\mathbb{R}^d} f(x),\]where \(f\) is \(\mu\)-strongly convex.
This code computes a worst-case guarantee for an accelerated gradient flow. That is, it computes the smallest possible \(\tau(\mu)\) such that the guarantee
\[\frac{d}{dt}\mathcal{V}_{P}(X_t) \leqslant -\tau(\mu)\mathcal{V}_P(X_t) ,\]is valid with
\[\mathcal{V}_{P}(X_t) = f(X_t) - f(x_\star) + (X_t - x_\star, \frac{d}{dt}X_t)^T(P \otimes I_d)(X_t - x_\star, \frac{d}{dt}X_t) ,\]where \(I_d\) is the identity matrix, \(X_t\) is the output of an accelerated gradient flow, and where \(x_\star\) is the minimizer of \(f\).
In short, for given values of \(\mu\), \(\tau(\mu)\) is computed as the worst-case value of the derivative of \(f(X_t)-f_\star\) when \(f(X_t) - f(x_\star)\leqslant 1\).
Algorithm: For \(t \geqslant 0\),
\[\frac{d^2}{dt^2}X_t + 2\sqrt{\mu}\frac{d}{dt}X_t + \nabla f(X_t) = 0,\]with some initialization \(X_{0}\triangleq x_0\).
Theoretical guarantee:
The following tight guarantee for \(P = \frac{1}{2}\begin{pmatrix} \mu & \sqrt{\mu} \\ \sqrt{\mu} & 1\end{pmatrix}\), for which \(\mathcal{V}_{P} \geqslant 0\) can be found in [1, Appendix B], [2, Theorem 4.3]:
\[\frac{d}{dt}\mathcal{V}_P(X_t) \leqslant -\sqrt{\mu}\mathcal{V}_P(X_t).\]For \(P = \begin{pmatrix} \frac{4}{9}\mu & \frac{4}{3}\sqrt{\mu} \\ \frac{4}{3}\sqrt{\mu} & \frac{1}{2}\end{pmatrix}\), for which \(\mathcal{V}_{P}(X_t) \geqslant 0\) along the trajectory, the following tight guarantee can be found in [3, Corollary 2.5],
\[\frac{d}{dt}\mathcal{V}_P(X_t) \leqslant -\frac{4}{3}\sqrt{\mu}\mathcal{V}_P(X_t).\]References:
- Parameters:
mu (float) – the strong convexity parameter
psd (boolean) – option for positivity of \(P\) in the Lyapunov function \(\mathcal{V}_{P}\)
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
>>> pepit_tau, theoretical_tau = wc_accelerated_gradient_flow_strongly_convex(mu=0.1, psd=True, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 4x4 (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 (1 constraint(s) added) (PEPit) Setting up the problem: interpolation conditions for 1 function(s) Function 1 : Adding 2 scalar constraint(s) ... Function 1 : 2 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.3162277785675417 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite All the primal scalar constraints are verified up to an error of 8.763809448107673e-16 (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 5.483010699403177e-09 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 2.328618994746702e-08 (PEPit) Final upper bound (dual): -0.3162277757899436 and lower bound (primal example): -0.3162277785675417 (PEPit) Duality gap: absolute: 2.777598095971001e-09 and relative: -8.783536059207228e-09 *** Example file: worst-case performance of an accelerated gradient flow *** PEPit guarantee: d/dt V(X_t,t) <= -0.316228 V(X_t,t) Theoretical guarantee: d/dt V(X_t) <= -0.316228 V(X_t,t)
10.4 Accelerated gradient flow for convex functions
- PEPit.examples.continuous_time_models.wc_accelerated_gradient_flow_convex(t, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the convex minimization problem
\[f_\star \triangleq \min_x f(x),\]where \(f\) is convex.
This code computes a worst-case guarantee for an accelerated gradient flow. That is, it verifies the inequality
\[\frac{d}{dt}\mathcal{V}(X_t, t) \leqslant 0 ,\]is valid, where \(\mathcal{V}(X_t, t) = t^2(f(X_t) - f(x_\star)) + 2 \|(X_t - x_\star) + \frac{t}{2}\frac{d}{dt}X_t \|^2\), \(X_t\) is the output of an accelerated gradient flow, and where \(x_\star\) is the minimizer of \(f\).
In short, for given values of \(t\), it verifies \(\frac{d}{dt}\mathcal{V}(X_t, t) \leqslant 0\).
Algorithm: For \(t \geqslant 0\),
\[\frac{d^2}{dt^2}X_t + \frac{3}{t}\frac{d}{dt}X_t + \nabla f(X_t) = 0,\]with some initialization \(X_{0}\triangleq x_0\).
Theoretical guarantee:
The following tight guarantee can be verified in [1, Section 2]:
\[\frac{d}{dt}\mathcal{V}(X_t, t) \leqslant 0.\]After integrating between \(0\) and \(T\),
\[f(X_T) - f_\star \leqslant \frac{2}{T^2}\|x_0 - x_\star\|^2.\]The detailed approach using PEPs is available in [2, Theorem 2.6].
References:
- Parameters:
t (float) – time step
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
>>> pepit_tau, theoretical_tau = wc_accelerated_gradient_flow_convex(t=3.4, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 4x4 (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 1 function(s) Function 1 : Adding 2 scalar constraint(s) ... Function 1 : 2 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: -2.6645352591003757e-15 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite All the primal scalar constraints are verified up to an error of 1.199040866595169e-14 (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 5.296296734513817e-11 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.5004105883380378e-10 (PEPit) Final upper bound (dual): 0.0 and lower bound (primal example): -2.6645352591003757e-15 (PEPit) Duality gap: absolute: 2.6645352591003757e-15 and relative: -1.0 *** Example file: worst-case performance of an accelerated gradient flow *** PEPit guarantee: d/dt V(X_t,t) <= 0.0 Theoretical guarantee: d/dt V(X_t) <= 0.0