11. Continuous-time models
11.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.20000002010543685 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 7.21571816563555e-10 All the primal scalar constraints are verified up to an error of 7.074164865006338e-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.684432710751497e-09 (PEPit) Final upper bound (dual): -0.20000002574229303 and lower bound (primal example): -0.20000002010543685 (PEPit) Duality gap: absolute: -5.636856176272076e-09 and relative: 2.8184278048074267e-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_*))
11.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.1751469748629293e-09 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 1.3103319446316331e-08 All the primal scalar constraints are verified up to an error of 3.2757248828870714e-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.927687298250013e-08 (PEPit) Final upper bound (dual): 0.0 and lower bound (primal example): 2.1751469748629293e-09 (PEPit) Duality gap: absolute: -2.1751469748629293e-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
11.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.31622777856752843 (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 5.118823388165078e-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.482952099021607e-09 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 2.328561771704438e-08 (PEPit) Final upper bound (dual): -0.31622777578996025 and lower bound (primal example): -0.31622777856752843 (PEPit) Duality gap: absolute: 2.7775681754604875e-09 and relative: -8.783441442249373e-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)
11.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: -4.440892098500626e-15 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite All the primal scalar constraints are verified (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.296563188039727e-11 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.5004650319851282e-10 (PEPit) Final upper bound (dual): 0.0 and lower bound (primal example): -4.440892098500626e-15 (PEPit) Duality gap: absolute: 4.440892098500626e-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