2 Composite convex minimization
2.1 Proximal gradient
- PEPit.examples.composite_convex_minimization.wc_proximal_gradient(L, mu, gamma, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x) + f_2(x)\},\]where \(f_1\) is \(L\)-smooth and \(\mu\)-strongly convex, and where \(f_2\) is closed convex and proper.
This code computes a worst-case guarantee for the proximal gradient method (PGM). That is, it computes the smallest possible \(\tau(n, L, \mu)\) such that the guarantee
\[\|x_n - x_\star\|^2 \leqslant \tau(n, L, \mu) \|x_0 - x_\star\|^2,\]is valid, where \(x_n\) is the output of the proximal gradient, and where \(x_\star\) is a minimizer of \(F\). In short, for given values of \(n\), \(L\) and \(\mu\), \(\tau(n, L, \mu)\) is computed as the worst-case value of \(\|x_n - x_\star\|^2\) when \(\|x_0 - x_\star\|^2 \leqslant 1\).
Algorithm: Proximal gradient is described by
\[\begin{split}\begin{eqnarray} y_t & = & x_t - \gamma \nabla f_1(x_t), \\ x_{t+1} & = & \arg\min_x \left\{f_2(x)+\frac{1}{2\gamma}\|x-y_t\|^2 \right\}, \end{eqnarray}\end{split}\]for \(t \in \{ 0, \dots, n-1\}\) and where \(\gamma\) is a step-size.
Theoretical guarantee: It is well known that a tight guarantee for PGM is provided by
\[\|x_n - x_\star\|^2 \leqslant \max\{(1-L\gamma)^2,(1-\mu\gamma)^2\}^n \|x_0 - x_\star\|^2,\]which can be found in, e.g., [1, Theorem 3.1]. It is a folk knowledge and the result can be found in many references for gradient descent; see, e.g.,[2, Section 1.4: Theorem 3], [3, Section 5.1] and [4, Section 4.4].
References:
[2] B. Polyak (1987). Introduction to Optimization. Optimization Software New York.
- Parameters:
L (float) – the smoothness parameter.
mu (float) – the strong convexity parameter.
gamma (float) – proximal step-size.
n (int) – number of iterations.
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_proximal_gradient(L=1, mu=.1, gamma=1, n=2, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 7x7 (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 2 function(s) Function 1 : Adding 6 scalar constraint(s) ... Function 1 : 6 scalar constraint(s) added Function 2 : Adding 6 scalar constraint(s) ... Function 2 : 6 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.6561000457691557 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 5.562925261728628e-09 All the primal scalar constraints are verified up to an error of 1.0696409768334858e-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 2.6270914088577513e-07 (PEPit) Final upper bound (dual): 0.6561000458025597 and lower bound (primal example): 0.6561000457691557 (PEPit) Duality gap: absolute: 3.340394627571186e-11 and relative: 5.091288514780078e-11 *** Example file: worst-case performance of the Proximal Gradient Method in function values*** PEPit guarantee: ||x_n - x_*||^2 <= 0.6561 ||x0 - xs||^2 Theoretical guarantee: ||x_n - x_*||^2 <= 0.6561 ||x0 - xs||^2
2.2 Proximal gradient on quadratics
- PEPit.examples.composite_convex_minimization.wc_proximal_gradient_quadratics(L, mu, gamma, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x) + f_2(x)\},\]where \(f_1\) is \(L\)-smooth, \(\mu\)-strongly convex and quadratic, and where \(f_2\) is closed convex and proper.
This code computes a worst-case guarantee for the proximal gradient method (PGM). That is, it computes the smallest possible \(\tau(n, L, \mu)\) such that the guarantee
\[\|x_n - x_\star\|^2 \leqslant \tau(n, L, \mu) \|x_0 - x_\star\|^2,\]is valid, where \(x_n\) is the output of the proximal gradient, and where \(x_\star\) is a minimizer of \(F\). In short, for given values of \(n\), \(L\) and \(\mu\), \(\tau(n, L, \mu)\) is computed as the worst-case value of \(\|x_n - x_\star\|^2\) when \(\|x_0 - x_\star\|^2 \leqslant 1\).
Algorithm: Proximal gradient is described by
\[\begin{split}\begin{eqnarray} y_t & = & x_t - \gamma \nabla f_1(x_t), \\ x_{t+1} & = & \arg\min_x \left\{f_2(x)+\frac{1}{2\gamma}\|x-y_t\|^2 \right\}, \end{eqnarray}\end{split}\]for \(t \in \{ 0, \dots, n-1\}\) and where \(\gamma\) is a step-size.
Theoretical guarantee: It is well known that a tight guarantee for PGM is provided by
\[\|x_n - x_\star\|^2 \leqslant \max\{(1-L\gamma)^2,(1-\mu\gamma)^2\}^n \|x_0 - x_\star\|^2,\]which can be found in, e.g., [1, Theorem 3.1]. It is a folk knowledge and the result can be found in many references for gradient descent; see, e.g.,[2, Section 1.4: Theorem 3], [3, Section 5.1] and [4, Section 4.4].
References:
[2] B. Polyak (1987). Introduction to Optimization. Optimization Software New York.
- Parameters:
L (float) – the smoothness parameter.
mu (float) – the strong convexity parameter.
gamma (float) – proximal step-size.
n (int) – number of iterations.
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_proximal_gradient_quadratics(L=1, mu=.1, gamma=1, n=2, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 8x8 (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 2 function(s) Function 1 : Adding 10 scalar constraint(s) ... Function 1 : 10 scalar constraint(s) added Function 1 : Adding 1 lmi constraint(s) ... Size of PSD matrix 1: 4x4 Function 1 : 1 lmi constraint(s) added Function 2 : Adding 6 scalar constraint(s) ... Function 2 : 6 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.6561000114872446 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 1.796118427878115e-09 All required PSD matrices are indeed positive semi-definite up to an error of 4.525137966284814e-09 All the primal scalar constraints are verified up to an error of 1.511348379779065e-09 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite All the dual matrices to lmi are 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 0.548909470924843 (PEPit) Final upper bound (dual): 0.6561000103069384 and lower bound (primal example): 0.6561000114872446 (PEPit) Duality gap: absolute: -1.180306186121527e-09 and relative: -1.798972969755044e-09 *** Example file: worst-case performance of the Proximal Gradient Method in function values*** PEPit guarantee: ||x_n - x_*||^2 <= 0.6561 ||x0 - xs||^2 Theoretical guarantee: ||x_n - x_*||^2 <= 0.6561 ||x0 - xs||^2
2.3 Accelerated proximal gradient (a.k.a., FISTA)
- PEPit.examples.composite_convex_minimization.wc_accelerated_proximal_gradient(mu, L, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f(x) + h(x)\},\]where \(f\) is \(L\)-smooth and \(\mu\)-strongly convex, and where \(h\) is closed convex and proper.
This code computes a worst-case guarantee for the accelerated proximal gradient method, also known as fast proximal gradient (FPGM) method or FISTA [1]. That is, it computes the smallest possible \(\tau(n, L, \mu)\) such that the guarantee
\[F(x_n) - F(x_\star) \leqslant \tau(n, L, \mu) \|x_0 - x_\star\|^2,\]is valid, where \(x_n\) is the output of the accelerated proximal gradient method, and where \(x_\star\) is a minimizer of \(F\).
In short, for given values of \(n\), \(L\) and \(\mu\), \(\tau(n, L, \mu)\) is computed as the worst-case value of \(F(x_n) - F(x_\star)\) when \(\|x_0 - x_\star\|^2 \leqslant 1\).
Algorithm: Initialize \(\lambda_1=1\), \(y_1=x_0\). One iteration of FISTA is described by
\[\begin{split}\begin{eqnarray} \text{Set: }\lambda_{t+1} & = & \frac{1 + \sqrt{4\lambda_t^2 + 1}}{2}\\ x_t & = & \arg\min_x \left\{h(x)+\frac{L}{2}\|x-\left(y_t - \frac{1}{L} \nabla f(y_t)\right)\|^2 \right\}\\ y_{t+1} & = & x_t + \frac{\lambda_t-1}{\lambda_{t+1}} (x_t-x_{t-1}). \end{eqnarray}\end{split}\]Theoretical guarantee: The following worst-case guarantee can be found in e.g., [1, Theorem 4.4]:
\[f(x_n)-f_\star \leqslant \frac{L}{2}\frac{\|x_0-x_\star\|^2}{\lambda_n^2}.\]References:
- Parameters:
L (float) – the smoothness parameter.
mu (float) – the strong convexity parameter.
n (int) – number of iterations.
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_proximal_gradient(L=1, mu=0, n=4, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 12x12 (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 2 function(s) Function 1 : Adding 30 scalar constraint(s) ... Function 1 : 30 scalar constraint(s) added Function 2 : Adding 20 scalar constraint(s) ... Function 2 : 20 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.05167329605152958 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 6.64684463996332e-09 All the primal scalar constraints are verified up to an error of 1.6451693951591295e-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 8.587603813802402e-08 (PEPit) Final upper bound (dual): 0.051673302055698395 and lower bound (primal example): 0.05167329605152958 (PEPit) Duality gap: absolute: 6.004168814910393e-09 and relative: 1.1619480996379491e-07 *** Example file: worst-case performance of the Accelerated Proximal Gradient Method in function values*** PEPit guarantee: f(x_n)-f_* <= 0.0516733 ||x0 - xs||^2 Theoretical guarantee: f(x_n)-f_* <= 0.0661257 ||x0 - xs||^2
2.4 Simplified accelerated proximal gradient
- PEPit.examples.composite_convex_minimization.wc_accelerated_proximal_gradient_simplified(mu, L, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f(x) + h(x)\},\]where \(f\) is \(L\)-smooth and \(\mu\)-strongly convex, and where \(h\) is closed convex and proper.
This code computes a worst-case guarantee for the accelerated proximal gradient method, also known as fast proximal gradient (FPGM) method. That is, it computes the smallest possible \(\tau(n, L, \mu)\) such that the guarantee
\[F(x_n) - F(x_\star) \leqslant \tau(n, L, \mu) \|x_0 - x_\star\|^2,\]is valid, where \(x_n\) is the output of the accelerated proximal gradient method, and where \(x_\star\) is a minimizer of \(F\).
In short, for given values of \(n\), \(L\) and \(\mu\), \(\tau(n, L, \mu)\) is computed as the worst-case value of \(F(x_n) - F(x_\star)\) when \(\|x_0 - x_\star\|^2 \leqslant 1\).
Algorithm: Accelerated proximal gradient is described as follows, for \(t \in \{ 0, \dots, n-1\}\),
\begin{eqnarray} x_{t+1} & = & \arg\min_x \left\{h(x)+\frac{L}{2}\|x-\left(y_{t} - \frac{1}{L} \nabla f(y_t)\right)\|^2 \right\}, \\ y_{t+1} & = & x_{t+1} + \frac{i}{i+3} (x_{t+1} - x_{t}), \end{eqnarray}where \(y_{0} = x_0\).
Theoretical guarantee: A tight (empirical) worst-case guarantee for FPGM is obtained in [1, method FPGM1 in Sec. 4.2.1, Table 1 in sec 4.2.2], for \(\mu=0\):
\[F(x_n) - F_\star \leqslant \frac{2 L}{n^2+5n+2} \|x_0 - x_\star\|^2,\]which is attained on simple one-dimensional constrained linear optimization problems.
References:
- Parameters:
L (float) – the smoothness parameter.
mu (float) – the strong convexity parameter.
n (int) – number of iterations.
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_proximal_gradient_simplified(L=1, mu=0, n=4, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 12x12 (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 2 function(s) Function 1 : Adding 30 scalar constraint(s) ... Function 1 : 30 scalar constraint(s) added Function 2 : Adding 20 scalar constraint(s) ... Function 2 : 20 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.05263158422835028 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 5.991982341524508e-09 All the primal scalar constraints are verified up to an error of 1.4780313955381486e-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.783914601477293e-08 (PEPit) Final upper bound (dual): 0.052631589673196755 and lower bound (primal example): 0.05263158422835028 (PEPit) Duality gap: absolute: 5.444846476465592e-09 and relative: 1.034520726726044e-07 *** Example file: worst-case performance of the Accelerated Proximal Gradient Method in function values*** PEPit guarantee: f(x_n)-f_* <= 0.0526316 ||x0 - xs||^2 Theoretical guarantee: f(x_n)-f_* <= 0.0526316 ||x0 - xs||^2
2.5 Bregman proximal point
- PEPit.examples.composite_convex_minimization.wc_bregman_proximal_point(gamma, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x)+f_2(x) \}\]where \(f_1(x)\) and \(f_2(x)\) are closed convex proper functions.
This code computes a worst-case guarantee for Bregman Proximal Point method. That is, it computes the smallest possible \(\tau(n, \gamma)\) such that the guarantee
\[F(x_n) - F(x_\star) \leqslant \tau(n, \gamma) D_{f_1}(x_\star; x_0)\]is valid, where \(x_n\) is the output of the Bregman Proximal Point (BPP) method, where \(x_\star\) is a minimizer of \(F\), and when \(D_{f_1}\) is the Bregman distance generated by \(f_1\).
Algorithm: Bregman proximal point is described in [1, Section 2, equation (9)]. For \(t \in \{0, \dots, n-1\}\),
\begin{eqnarray} x_{t+1} & = & \arg\min_{u \in R^n} f_1(u) + \frac{1}{\gamma} D_{f_2}(u; x_t), \\ D_h(x; y) & = & h(x) - h(y) - \nabla h (y)^T(x - y). \end{eqnarray}Theoretical guarantee: A tight empirical guarantee can be guessed from the numerics
\[F(x_n) - F(x_\star) \leqslant \frac{1}{\gamma n} D_{f_1}(x_\star, x_0).\]References:
- Parameters:
gamma (float) – step-size.
n (int) – number of iterations.
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.
Examples
>>> pepit_tau, theoretical_tau = wc_bregman_proximal_point(gamma=3, n=5, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 14x14 (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 2 function(s) Function 1 : Adding 30 scalar constraint(s) ... Function 1 : 30 scalar constraint(s) added Function 2 : Adding 42 scalar constraint(s) ... Function 2 : 42 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.06666666577966336 (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 7.300920007446976e-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 up to an error of 3.627362036465223e-10 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.1600747813276144e-08 (PEPit) Final upper bound (dual): 0.06666666638907442 and lower bound (primal example): 0.06666666577966336 (PEPit) Duality gap: absolute: 6.094110632792749e-10 and relative: 9.14116607081279e-09 *** Example file: worst-case performance of the Bregman Proximal Point in function values *** PEPit guarantee: F(x_n)-F_* <= 0.0666667 Dh(x_*; x_0) Theoretical guarantee: F(x_n)-F_* <= 0.0666667 Dh(x_*; x_0)
2.6 Douglas Rachford splitting
- PEPit.examples.composite_convex_minimization.wc_douglas_rachford_splitting(L, alpha, theta, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x)+f_2(x) \}\]where \(f_1(x)\) is is convex, closed and proper , and \(f_2\) is \(L\)-smooth. Both proximal operators are assumed to be available.
This code computes a worst-case guarantee for the Douglas Rachford Splitting (DRS) method. That is, it computes the smallest possible \(\tau(n, L, \alpha, \theta)\) such that the guarantee
\[F(y_n) - F(x_\star) \leqslant \tau(n, L, \alpha, \theta) \|x_0 - x_\star\|^2.\]is valid, where it is known that \(x_k\) and \(y_k\) converge to \(x_\star\), but not \(w_k\) (see definitions in the section Algorithm). Hence we require the initial condition on \(x_0\) (arbitrary choice, partially justified by the fact we choose \(f_2\) to be the smooth function).
Note that \(y_n\) is feasible as it has a finite value for \(f_1\) (output of the proximal operator on \(f_1\)) and as \(f_2\) is smooth.
Algorithm:
Our notations for the DRS method are as follows, for \(t \in \{0, \dots, n-1\}\),
\begin{eqnarray} x_t & = & \mathrm{prox}_{\alpha f_2}(w_t), \\ y_t & = & \mathrm{prox}_{\alpha f_1}(2x_t - w_t), \\ w_{t+1} & = & w_t + \theta (y_t - x_t). \end{eqnarray}This description can be found in [1, Section 7.3].
Theoretical guarantee: We compare the output with that of PESTO [2] for when \(0\leqslant n \leqslant 10\) in the case where \(\alpha=\theta=L=1\).
References:
- Parameters:
L (float) – the smoothness parameter.
alpha (float) – parameter of the scheme.
theta (float) – parameter of the scheme.
n (int) – number of iterations.
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_douglas_rachford_splitting(L=1, alpha=1, theta=1, n=9, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 22x22 (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 2 function(s) Function 1 : Adding 90 scalar constraint(s) ... Function 1 : 90 scalar constraint(s) added Function 2 : Adding 110 scalar constraint(s) ... Function 2 : 110 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.02779172988059079 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 2.4990957076994907e-09 All the primal scalar constraints are verified up to an error of 7.054584369795003e-09 (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 3.0070786282625263e-10 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 5.968467133801908e-08 (PEPit) Final upper bound (dual): 0.02779173233376415 and lower bound (primal example): 0.02779172988059079 (PEPit) Duality gap: absolute: 2.4531733623656127e-09 and relative: 8.826990521661848e-08 *** Example file: worst-case performance of the Douglas Rachford Splitting in function values *** PEPit guarantee: f(y_n)-f_* <= 0.0278 ||x0 - xs||^2 Theoretical guarantee: f(y_n)-f_* <= 0.0278 ||x0 - xs||^2
2.7 Douglas Rachford splitting contraction
- PEPit.examples.composite_convex_minimization.wc_douglas_rachford_splitting_contraction(mu, L, alpha, theta, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x) + f_2(x) \}\]where \(f_1(x)\) is \(L\)-smooth and \(\mu\)-strongly convex, and \(f_2\) is convex, closed and proper. Both proximal operators are assumed to be available.
This code computes a worst-case guarantee for the Douglas Rachford Splitting (DRS) method. That is, it computes the smallest possible \(\tau(\mu,L,\alpha,\theta,n)\) such that the guarantee
\[\|w_1 - w_1'\|^2 \leqslant \tau(\mu,L,\alpha,\theta,n) \|w_0 - w_0'\|^2.\]is valid, where \(x_n\) is the output of the Douglas Rachford Splitting method. It is a contraction factor computed when the algorithm is started from two different points \(w_0\) and \(w_0\).
Algorithm:
Our notations for the DRS method are as follows [3, Section 7.3], for \(t \in \{0, \dots, n-1\}\),
\begin{eqnarray} x_t & = & \mathrm{prox}_{\alpha f_2}(w_t), \\ y_t & = & \mathrm{prox}_{\alpha f_1}(2x_t - w_t), \\ w_{t+1} & = & w_t + \theta (y_t - x_t). \end{eqnarray}Theoretical guarantee:
The tight theoretial guarantee is obtained in [2, Theorem 2]:
\[\|w_1 - w_1'\|^2 \leqslant \max\left(\frac{1}{1 + \mu \alpha}, \frac{\alpha L }{1 + L \alpha}\right)^{2n} \|w_0 - w_0'\|^2\]for when \(\theta=1\).
References:
Details on the SDP formulations can be found in
When \(\theta = 1\), the bound can be compared with that of [2, Theorem 2]
A description for the DRS method can be found in [3, 7.3]
- Parameters:
L (float) – the smoothness parameter.
mu (float) – the strong convexity parameter.
alpha (float) – parameter of the scheme.
theta (float) – parameter of the scheme.
n (int) – number of iterations.
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
Examples
>>> pepit_tau, theoretical_tau = wc_douglas_rachford_splitting_contraction(mu=.1, L=1, alpha=3, theta=1, n=2, 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 (1 constraint(s) added) (PEPit) Setting up the problem: interpolation conditions for 2 function(s) Function 1 : Adding 12 scalar constraint(s) ... Function 1 : 12 scalar constraint(s) added Function 2 : Adding 12 scalar constraint(s) ... Function 2 : 12 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.35012780295429113 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 1.5819643752082932e-10 All the primal scalar constraints are verified up to an error of 1.7787298300930843e-09 (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 1.1344535856561752e-07 (PEPit) Final upper bound (dual): 0.350127801688298 and lower bound (primal example): 0.35012780295429113 (PEPit) Duality gap: absolute: -1.2659931436509453e-09 and relative: -3.615802952432828e-09 *** Example file: worst-case performance of the Douglas-Rachford splitting in distance *** PEPit guarantee: ||w - wp||^2 <= 0.350128 ||w0 - w0p||^2 Theoretical guarantee: ||w - wp||^2 <= 0.350128 ||w0 - w0p||^2
2.8 Accelerated Douglas Rachford splitting
- PEPit.examples.composite_convex_minimization.wc_accelerated_douglas_rachford_splitting(mu, L, alpha, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x) + f_2(x)\},\]where \(f_1\) is closed convex and proper, and \(f_2\) is \(L\)-smooth and \(\mu\)-strongly convex.
This code computes a worst-case guarantee for accelerated Douglas-Rachford. That is, it computes the smallest possible \(\tau(n, L, \mu, \alpha)\) such that the guarantee
\[F(y_n) - F(x_\star) \leqslant \tau(n,L,\mu,\alpha) \|w_0 - w_\star\|^2\]is valid, \(\alpha\) is a parameter of the method, and where \(y_n\) is the output of the accelerated Douglas-Rachford Splitting method, where \(x_\star\) is a minimizer of \(F\), and \(w_\star\) defined such that
\[x_\star = \mathrm{prox}_{\alpha f_2}(w_\star)\]is an optimal point.
In short, for given values of \(n\), \(L\), \(\mu\), \(\alpha\), \(\tau(n, L, \mu, \alpha)\) is computed as the worst-case value of \(F(y_n)-F_\star\) when \(\|w_0 - w_\star\|^2 \leqslant 1\).
Algorithm: The accelerated Douglas-Rachford splitting is described in [1, Section 4]. For \(t \in \{0, \dots, n-1\}\),
\begin{eqnarray} x_{t} & = & \mathrm{prox}_{\alpha f_2} (u_t),\\ y_{t} & = & \mathrm{prox}_{\alpha f_1}(2x_t-u_t),\\ w_{t+1} & = & u_t + \theta (y_t-x_t),\\ u_{t+1} & = & \left\{\begin{array}{ll} w_{t+1}+\frac{t-1}{t+2}(w_{t+1}-w_t)\, & \text{if } t >1,\\ w_{t+1} & \text{otherwise.} \end{array}\right. \end{eqnarray}Theoretical guarantee: There is no known worst-case guarantee for this method beyond quadratic minimization. For quadratics, an upper bound on is provided by [1, Theorem 5]:
\[F(y_n) - F_\star \leqslant \frac{2}{\alpha \theta (n + 3)^ 2} \|w_0-w_\star\|^2,\]when \(\theta=\frac{1-\alpha L}{1+\alpha L}\) and \(\alpha < \frac{1}{L}\).
References: An analysis of the accelerated Douglas-Rachford splitting is available in [1, Theorem 5] for when the convex minimization problem is quadratic.
- Parameters:
mu (float) – the strong convexity parameter.
L (float) – the smoothness parameter.
alpha (float) – the parameter of the scheme.
n (int) – the number of iterations.
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 (upper bound for quadratics; not directly comparable).
Example
>>> pepit_tau, theoretical_tau = wc_accelerated_douglas_rachford_splitting(mu=.1, L=1, alpha=.9, n=2, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 9x9 (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 2 function(s) Function 1 : Adding 12 scalar constraint(s) ... Function 1 : 12 scalar constraint(s) added Function 2 : Adding 12 scalar constraint(s) ... Function 2 : 12 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.19291482276257793 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 6.6554381338528585e-09 All the primal scalar constraints are verified up to an error of 1.4452049501567643e-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.332184313444333e-08 (PEPit) Final upper bound (dual): 0.19291482672193344 and lower bound (primal example): 0.19291482276257793 (PEPit) Duality gap: absolute: 3.959355510119167e-09 and relative: 2.0523853239582232e-08 *** Example file: worst-case performance of the Accelerated Douglas Rachford Splitting in function values *** PEPit guarantee: F(y_n)-F_* <= 0.192915 ||x0 - ws||^2 Theoretical guarantee for quadratics: F(y_n)-F_* <= 1.68889 ||x0 - ws||^2
2.9 Frank Wolfe
- PEPit.examples.composite_convex_minimization.wc_frank_wolfe(L, D, R, center, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x) + f_2(x)\},\]where \(f_1\) is \(L\)-smooth and convex and where \(f_2\) is a convex indicator function on \(\mathcal{D}\) of diameter at most \(D\) and radius at most \(R\) around center.
This code computes a worst-case guarantee for the conditional gradient method, aka Frank-Wolfe method. That is, it computes the smallest possible \(\tau(n, L)\) such that the guarantee
\[F(x_n) - F(x_\star) \leqslant \tau(n, L, D, R),\]is valid, where x_n is the output of the conditional gradient method, and where \(x_\star\) is a minimizer of \(F\). In short, for given values of \(n\) and \(L\), \(\tau(n, L, D, R)\) is computed as the worst-case value of \(F(x_n) - F(x_\star)\).
Algorithm:
This method was first presented in [1]. A more recent version can be found in, e.g., [2, Algorithm 1]. For \(t \in \{0, \dots, n-1\}\),
\[\begin{split}\begin{eqnarray} y_t & = & \arg\min_{s \in \mathcal{D}} \langle s \mid \nabla f_1(x_t) \rangle, \\ x_{t+1} & = & \frac{t}{t + 2} x_t + \frac{2}{t + 2} y_t. \end{eqnarray}\end{split}\]Theoretical guarantee:
An upper guarantee obtained in [2, Theorem 1] when R = infinity is
\[F(x_n) - F(x_\star) \leqslant \frac{2L D^2}{n+2}.\]References:
- Parameters:
L (float) – the smoothness parameter.
D (float) – diameter of \(\mathcal{D}\).
R (float) – radius of \(\mathcal{D}\).
center (Point) – center of \(\mathcal{D}\). If None, the radius constraint must be observed to one center.
n (int) – number of iterations.
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_frank_wolfe(L=1, D=1, R=float('inf'), center=None, n=10, >>> wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 26x26 (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 2 function(s) Function 1 : Adding 132 scalar constraint(s) ... Function 1 : 132 scalar constraint(s) added Function 2 : Adding 325 scalar constraint(s) ... Function 2 : 325 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.07828953896022825 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 4.135149894158463e-09 All the primal scalar constraints are verified up to an error of 7.746795427365782e-09 (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 3.4682721500621377e-09 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.2155275372348722e-07 (PEPit) Final upper bound (dual): 0.07828954275558239 and lower bound (primal example): 0.07828953896022825 (PEPit) Duality gap: absolute: 3.795354142077656e-09 and relative: 4.847843265504128e-08 *** Example file: worst-case performance of the Conditional Gradient (Frank-Wolfe) in function value *** PEPit guarantee: f(x_n)-f_* <= 0.0782895 ||x0 - xs||^2 Theoretical guarantee: f(x_n)-f_* <= 0.166667 ||x0 - xs||^2
2.10 Improved interior method
- PEPit.examples.composite_convex_minimization.wc_improved_interior_algorithm(L, mu, c, lam, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x) + f_2(x)\},\]where \(f_1\) is a \(L\)-smooth convex function, and \(f_2\) is a closed convex indicator function. We use a kernel function \(h\) that is assumed to be closed, proper, and strongly convex (see [1, Section 5]).
This code computes a worst-case guarantee for Improved interior gradient algorithm (IGA). That is, it computes the smallest possible \(\tau(\mu,L,c,\lambda,n)\) such that the guarantee
\[F(x_n) - F(x_\star) \leqslant \tau(\mu,L,c,\lambda,n) (c D_h(x_\star;x_0) + f_1(x_0) - f_1(x_\star))\]is valid, where \(x_n\) is the output of the IGA and where \(x_\star\) is a minimizer of \(F\) and \(D_h\) is the Bregman distance generated by \(h\).
In short, for given values of \(\mu\), \(L\), \(c\), \(\lambda\) and \(n\), \(\tau(\mu,L,c,\lambda,n)\) is computed as the worst-case value of \(F(x_n)-F_\star\) when \(c D_h(x_\star;x_0) + f_1(x_0) - f_1(x_\star)\leqslant 1\).
Algorithm: The IGA is described in [1, “Improved Interior Gradient Algorithm”]. For \(t \in \{0, \dots, n-1\}\),
\begin{eqnarray} \alpha_t & = & \frac{\sqrt{(c_t\lambda)^2+4c_t\lambda}-\lambda c_t}{2},\\ y_t & = & (1-\alpha_t) x_t + \alpha_t z_t,\\ c_{t+1} & = & (1-\alpha_t)c_t,\\ z_{t+1} & = & \arg\min_{z} \left\{ \left< z;\frac{\alpha_t}{c_{t+1}}\nabla f_1(y_t)\right> +f_2(z)+D_h(z;z_t)\right\}, \\ x_{t+1} & = & (1-\alpha_t) x_t + \alpha_t z_{t+1}. \end{eqnarray}Theoretical guarantee: The following upper bound can be found in [1, Theorem 5.2]:
\[F(x_n) - F_\star \leqslant \frac{4L}{c n^2}\left(c D_h(x_\star;x_0) + f_1(x_0) - f_1(x_\star) \right).\]References:
- Parameters:
L (float) – the smoothness parameter.
mu (float) – the strong-convexity parameter.
c (float) – initial value.
lam (float) – the step-size.
n (int) – number of iterations.
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
>>> L = 1 >>> lam = 1 / L >>> pepit_tau, theoretical_tau = wc_improved_interior_algorithm(L=L, mu=1, c=1, lam=lam, n=5, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 22x22 (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 3 function(s) Function 1 : Adding 42 scalar constraint(s) ... Function 1 : 42 scalar constraint(s) added Function 2 : Adding 49 scalar constraint(s) ... Function 2 : 49 scalar constraint(s) added Function 3 : Adding 42 scalar constraint(s) ... Function 3 : 42 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.06807592021457932 (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 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 2.3085728882628774e-08 (PEPit) Final upper bound (dual): 0.06807590997751518 and lower bound (primal example): 0.06807592021457932 (PEPit) Duality gap: absolute: -1.0237064140827812e-08 and relative: -1.5037716873396614e-07 *** Example file: worst-case performance of the Improved interior gradient algorithm in function values *** PEPit guarantee: F(x_n)-F_* <= 0.0680759 (c * Dh(xs;x0) + f1(x0) - F_*) Theoretical guarantee: F(x_n)-F_* <= 0.111111 (c * Dh(xs;x0) + f1(x0) - F_*)
2.11 No Lips in function value
- PEPit.examples.composite_convex_minimization.wc_no_lips_in_function_value(L, gamma, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the constrainted composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x) + f_2(x)\},\]where \(f_1\) is convex and \(L\)-smooth relatively to \(h\), \(h\) being closed proper and convex, and where \(f_2\) is a closed convex indicator function.
This code computes a worst-case guarantee for the NoLips method. That is, it computes the smallest possible \(\tau(n, L)\) such that the guarantee
\[F(x_n) - F_\star \leqslant \tau(n, L) D_h(x_\star; x_0),\]is valid, where \(x_n\) is the output of the NoLips method, where \(x_\star\) is a minimizer of \(F\), and where \(D_h\) is the Bregman divergence generated by \(h\). In short, for given values of \(n\) and \(L\), \(\tau(n, L)\) is computed as the worst-case value of \(F(x_n) - F_\star\) when \(D_h(x_\star; x_0) \leqslant 1\).
Algorithm: This method (also known as Bregman Gradient, or Mirror descent) can be found in, e.g., [2, Algorithm 1]. For \(t \in \{0, \dots, n-1\}\),
\[x_{t+1} = \arg\min_{u} \{f_2(u)+\langle \nabla f_1(x_t) \mid u - x_t \rangle + \frac{1}{\gamma} D_h(u; x_t)\}.\]Theoretical guarantee:
The tight guarantee obtained in [2, Theorem 1] is
\[F(x_n) - F_\star \leqslant \frac{1}{\gamma n} D_h(x_\star; x_0),\]for any \(\gamma \leq \frac{1}{L}\); tightness is provided in [2, page 23].
References: NoLips was proposed [1] for convex problems involving relative smoothness. The worst-case analysis using a PEP, as well as the tightness are provided in [2].
Notes
Disclaimer: This example requires some experience with PEPit and PEPs ([2], section 4).
- Parameters:
L (float) – relative-smoothness parameter.
gamma (float) – step-size.
n (int) – number of iterations.
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
>>> L = 1 >>> gamma = 1 / (2 * L) >>> pepit_tau, theoretical_tau = wc_no_lips_in_function_value(L=L, gamma=gamma, n=3, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 15x15 (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 3 function(s) Function 1 : Adding 20 scalar constraint(s) ... Function 1 : 20 scalar constraint(s) added Function 2 : Adding 20 scalar constraint(s) ... Function 2 : 20 scalar constraint(s) added Function 3 : Adding 16 scalar constraint(s) ... Function 3 : 16 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.666666666648161 (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.4395949710088729e-11 (PEPit) Dual feasibility check: The solver found a residual matrix that is positive semi-definite up to an error of 1.3315069623255106e-21 All the dual scalar values associated with inequality constraints are nonnegative up to an error of 1.4920638309169674e-11 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 2.427130463022609e-10 (PEPit) Final upper bound (dual): 0.6666666666624239 and lower bound (primal example): 0.666666666648161 (PEPit) Duality gap: absolute: 1.4262924175056924e-11 and relative: 2.1394386263179262e-11 *** Example file: worst-case performance of the NoLips in function values *** PEPit guarantee: F(x_n) - F_* <= 0.666667 Dh(x_*; x_0) Theoretical guarantee: F(x_n) - F_* <= 0.666667 Dh(x_*; x_0)
2.12 No Lips in Bregman divergence
- PEPit.examples.composite_convex_minimization.wc_no_lips_in_bregman_divergence(L, gamma, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the constrainted composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x) + f_2(x)\},\]where \(f_1\) is convex and \(L\)-smooth relatively to \(h\), \(h\) being closed proper and convex, and where \(f_2\) is a closed convex indicator function.
This code computes a worst-case guarantee for the NoLips method. That is, it computes the smallest possible \(\tau(n, L)\) such that the guarantee
\[\min_{t\leqslant n} D_h(x_{t-1}; x_t) \leqslant \tau(n, L) D_h(x_\star; x_0),\]is valid, where \(x_n\) is the output of the NoLips method, where \(x_\star\) is a minimizer of \(F\), and where \(D_h\) is the Bregman divergence generated by \(h\). In short, for given values of \(n\) and \(L\), \(\tau(n, L)\) is computed as the worst-case value of \(\min_{t\leqslant n} D_h(x_{t-1}; x_t)\) when \(D_h(x_\star; x_0) \leqslant 1\).
Algorithm: This method (also known as Bregman Gradient, or Mirror descent) can be found in, e.g., [2, Algorithm 1]. For \(t \in \{0, \dots, n-1\}\),
\[x_{t+1} = \arg\min_{u} \{f_2(u)+\langle \nabla f_1(x_t) \mid u - x_t \rangle + \frac{1}{\gamma} D_h(u; x_t)\}.\]Theoretical guarantee: The upper guarantee obtained in [2, Proposition 4] is
\[\min_{t\leqslant n} D_h(x_{t-1}; x_t) \leqslant \frac{2}{n (n - 1)} D_h(x_\star; x_0),\]for any \(\gamma \leq \frac{1}{L}\). It is empirically tight.
References:
Notes
Disclaimer: This example requires some experience with PEPit and PEPs ([2], section 4).
- Parameters:
L (float) – relative-smoothness parameter.
gamma (float) – step-size.
n (int) – number of iterations.
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
>>> L = 1 >>> gamma = 1 / L >>> pepit_tau, theoretical_tau = wc_no_lips_in_bregman_divergence(L=L, gamma=gamma, n=10, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 36x36 (PEPit) Setting up the problem: performance measure is the minimum of 10 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 3 function(s) Function 1 : Adding 132 scalar constraint(s) ... Function 1 : 132 scalar constraint(s) added Function 2 : Adding 132 scalar constraint(s) ... Function 2 : 132 scalar constraint(s) added Function 3 : Adding 121 scalar constraint(s) ... Function 3 : 121 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.022222222222193107 (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 3.566591466608315e-15 (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 7.9017853022551e-15 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 3.7006729706018063e-13 (PEPit) Final upper bound (dual): 0.02222222222220066 and lower bound (primal example): 0.022222222222193107 (PEPit) Duality gap: absolute: 7.552986014403018e-15 and relative: 3.398843706485811e-13 *** Example file: worst-case performance of the NoLips_2 in Bregman divergence *** PEPit guarantee: min_t Dh(x_(t-1); x_t) <= 0.0222222 Dh(x_*; x_0) Theoretical guarantee: min_t Dh(x_(t-1); x_t) <= 0.0222222 Dh(x_*; x_0)
2.13 Three operator splitting
- PEPit.examples.composite_convex_minimization.wc_three_operator_splitting(mu1, L1, L3, alpha, theta, n, wrapper='cvxpy', solver=None, verbose=1)[source]
Consider the composite convex minimization problem,
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x) + f_2(x) + f_3(x)\}\]where, \(f_1\) is \(L_1\)-smooth and \(\mu_1\)-strongly convex, \(f_2\) is closed, convex and proper, and \(f_3\) is \(L_3\)-smooth convex. Proximal operators are assumed to be available for \(f_1\) and \(f_2\).
This code computes the worst-case guarantee of the contraction achieved by the Three Operator Splitting (TOS). That is, it computes the smallest possible \(\tau(n, L_1, L_3, \mu_1)\) such that the guarantee
\[\|w^{(0)}_{n} - w^{(1)}_{n}\|^2 \leqslant \tau(n, L_1, L_3, \mu_1, \alpha, \theta) \|w^{(0)}_{0} - w^{(1)}_{0}\|^2\]is valid, where \(w^{(0)}_{0}\) and \(w^{(1)}_{0}\) are two different starting points and \(w^{(0)}_{n}\) and \(w^{(1)}_{n}\) are the two corresponding \(n^{\mathrm{th}}\) outputs of TOS.
In short, for given values of \(n\), \(L_1\), \(L_3\), \(\mu_1\), \(\alpha\) and \(\theta\), the contraction factor \(\tau(n, L_1, L_3, \mu_1, \alpha, \theta)\) is computed as the worst-case value of \(\|w^{(0)}_{n} - w^{(1)}_{n}\|^2\) when \(\|w^{(0)}_{0} - w^{(1)}_{0}\|^2 \leqslant 1\).
Algorithm: One iteration of the algorithm is described in [1]. For \(t \in \{0, \dots, n-1\}\),
\begin{eqnarray} x_t & = & \mathrm{prox}_{\alpha, f_2}(w_t), \\ y_t & = & \mathrm{prox}_{\alpha, f_1}(2 x_t - w_t - \alpha \nabla f_3(x_t)), \\ w_{t+1} & = & w_t + \theta (y_t - x_t). \end{eqnarray}References: The TOS was introduced in [1].
- Parameters:
mu1 (float) – the strong convexity parameter of function \(f_1\).
L1 (float) – the smoothness parameter of function \(f_1\).
L3 (float) – the smoothness parameter of function \(f_3\).
alpha (float) – parameter of the scheme.
theta (float) – parameter of the scheme.
n (int) – number of iterations.
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 (None) – no theoretical value.
Example
>>> L3 = 1 >>> alpha = 1 / L3 >>> pepit_tau, theoretical_tau = wc_three_operator_splitting(mu1=0.1, L1=10, L3=L3, alpha=alpha, theta=1, n=4, wrapper="cvxpy", solver=None, verbose=1) (PEPit) Setting up the problem: size of the Gram matrix: 26x26 (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 3 function(s) Function 1 : Adding 56 scalar constraint(s) ... Function 1 : 56 scalar constraint(s) added Function 2 : Adding 56 scalar constraint(s) ... Function 2 : 56 scalar constraint(s) added Function 3 : Adding 56 scalar constraint(s) ... Function 3 : 56 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.4754523346392658 (PEPit) Primal feasibility check: The solver found a Gram matrix that is positive semi-definite up to an error of 1.5440593281219272e-09 All the primal scalar constraints are verified up to an error of 5.277754989985173e-09 (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.1469231961323311e-09 (PEPit) The worst-case guarantee proof is perfectly reconstituted up to an error of 1.1184938806991412e-06 (PEPit) Final upper bound (dual): 0.4754523347677999 and lower bound (primal example): 0.4754523346392658 (PEPit) Duality gap: absolute: 1.285341277856844e-10 and relative: 2.703407227628939e-10 *** Example file: worst-case performance of the Three Operator Splitting in distance *** PEPit guarantee: ||w^1_n - w^0_n||^2 <= 0.475452 ||w^1_0 - w^0_0||^2