Quelques remarques :

• les exemples ont été reformatés dans le format dont on avait discuté,
• le fichier celine_test.py permet de tester la (quasi) totalité des exemples (sur le modèle de adri_test.py et de ay_test.py),
• une modification dans pep.py sur une des fonctions d'inégalité : elle se renvoyait elle-même (ce qui créait une boucle infinie),
• Il va y avoir pas mal de conflit au moment de merger @bgoujaud.

A votre dispo pour échanger sur les exemples!

Fix things for PR78 on coordinate descent. 2 tests are commented: 1 in test_examples.py and 1 in test_uselessly_complexified_examples.py. They should be removed.

Note 1: PR not entirely ready to be validated. Note 2: class and function names can be discussed & updated ("partition" alone might be cleaner than "block_partition" for instance)

Todo:

• Clean comments [status: to be reviewed]
• Check PEP8 and other conventions [status: improved]
• Incorporate a class of functions whose conditions depends on the blocks (necessary conditions), typically that of the paper: A better convergence analysis of the block coordinate descent method for large scale machine learning (Lemma 1.1). [status: done]
• Add a deterministic example, for instance that of On the Worst-Case Analysis of Cyclic Coordinate-Wise Algorithms on Smooth Convex Functions. [status: will not do]
• Other tests? [status: many tests incorporated]

Hello,

Reporting a minor evaluation bug: it looks like the Points that are not associated with functions might not be correctly evaluable after solving the PEP. Example below (essentially exact line search example, where I try to evaluate a worst-case dx after solving the PEP).

--------------------------------------------------------- Main file:

from PEPit import PEP
from PEPit.functions import SmoothStronglyConvexFunction
from PEPit.primitive_steps import exact_linesearch_step
from PEPit.primitive_steps import inexact_gradient_step

def wc_inexact_gradient_exact_line_search(L, mu, epsilon, n, verbose=1):


    # Instantiate PEP
    problem = PEP()

    # Declare a strongly convex smooth function
    func = problem.declare_function(SmoothStronglyConvexFunction, mu=mu, L=L)

    # Start by defining its unique optimal point xs = x_* and corresponding function value fs = f_*
    xs = func.stationary_point()
    fs = func(xs)

    # Then define the starting point x0 of the algorithm as well as corresponding gradient and function value g0 and f0
    x0 = problem.set_initial_point()

    # Set the initial constraint that is the distance between f0 and f_*
    problem.set_initial_condition(func(x0) - fs <= 1)

    # Run n steps of the inexact gradient method with ELS
    x = x0
    for i in range(n):
        _, dx, _ = inexact_gradient_step(x, func, gamma=0, epsilon=epsilon, notion='relative')
        x, gx, fx = exact_linesearch_step(x, func, [dx])

    # Set the performance metric to the function value accuracy
    problem.set_performance_metric(func(x) - fs)

    # Solve the PEP
    pepit_verbose = max(verbose, 0)
    pepit_tau = problem.solve(verbose=pepit_verbose)

    # Compute theoretical guarantee (for comparison)
    Leps = (1 + epsilon) * L
    meps = (1 - epsilon) * mu
    theoretical_tau = ((Leps - meps) / (Leps + meps)) ** (2 * n)

    # Print conclusion if required
    if verbose != -1:
        print('*** Example file: worst-case performance of inexact gradient descent with exact linesearch ***')
        print('\tPEPit guarantee:\t f(x_n)-f_* <= {:.6} (f(x_0)-f_*)'.format(pepit_tau))
        print('\tTheoretical guarantee:\t f(x_n)-f_* <= {:.6} (f(x_0)-f_*)'.format(theoretical_tau))

    # Return the worst-case guarantee of the evaluated method (and the reference theoretical value)
    return pepit_tau, theoretical_tau, dx.eval()

--------------------------------------------------------- Calling the function:

L = 1
mu = .1
epsilon = .5
n = 1

wc_inexact_gradient_exact_line_search(L, mu, epsilon, n, verbose=1)

--------------------------------------------------------- Output + Error

(PEPit) Setting up the problem: size of the main PSD matrix: 6x6 (PEPit) Setting up the problem: performance measure is 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 9 scalar constraint(s) ... function 1 : 9 scalar constraint(s) added (PEPit) Compiling SDP (PEPit) Calling SDP solver (PEPit) Solver status: optimal (solver: MOSEK); optimal value: 0.8751298780724822 (PEPit) Postprocessing: solver's output is not entirely feasible (smallest eigenvalue of the Gram matrix is: -1.05e-08 < 0). Small deviation from 0 may simply be due to numerical error. Big ones should be deeply investigated. In any case, from now the provided values of parameters are based on the projection of the Gram matrix onto the cone of symmetric semi-definite matrix. *** Example file: worst-case performance of inexact gradient descent with exact linesearch *** PEPit guarantee: f(x_n)-f_* <= 0.87513 (f(x_0)-f_) Theoretical guarantee: f(x_n)-f_ <= 0.87513 (f(x_0)-f_*)

ValueError Traceback (most recent call last) /tmp/ipykernel_265884/2910429637.py in 4 n = 1 5 ----> 6 wc_inexact_gradient_exact_line_search(L, mu, epsilon, n, verbose=1)

/tmp/ipykernel_265884/1085922103.py in wc_inexact_gradient_exact_line_search(L, mu, epsilon, n, verbose) 48 49 # Return the worst-case guarantee of the evaluated method (and the reference theoretical value) ---> 50 return pepit_tau, theoretical_tau, dx.eval() 51 52

~/anaconda3/lib/python3.9/site-packages/PEPit/point.py in eval(self) 268 # If leaf, the PEP would have filled the attribute at the end of the solve. 269 if self._is_leaf: --> 270 raise ValueError("The PEP must be solved to evaluate Points!") 271 # If linear combination, combine the values of the leaf, and store the result before returning it. 272 else:

ValueError: The PEP must be solved to evaluate Points!

For the record: postprocessing issue when no eigenvalue is set to zero. Error below: problem in "pep.py" in "get_nb_eigenvalues_and_corrected_matrix(M)"

This is particularly problematic when trying to find low dimensional instances.

ValueError Traceback (most recent call last) /tmp/ipykernel_635912/2564841825.py in 41 42 # Solve the PEP ---> 43 pepit_tau = problem.solve(verbose=1, dimension_reduction_heuristic="logdet2")

~/anaconda3/lib/python3.9/site-packages/PEPit/pep.py in solve(self, verbose, return_full_cvxpy_problem, dimension_reduction_heuristic, eig_regularization, tol_dimension_reduction, **kwargs) 369 370 # Print the estimated dimension before dimension reduction --> 371 nb_eigenvalues, eig_threshold, corrected_G_value = self.get_nb_eigenvalues_and_corrected_matrix(G.value) 372 if verbose: 373 print('(PEPit) Postprocessing: {} eigenvalue(s) > {} before dimension reduction'.format(nb_eigenvalues,

~/anaconda3/lib/python3.9/site-packages/PEPit/pep.py in get_nb_eigenvalues_and_corrected_matrix(M) 466 467 # Get the highest eigenvalue that have been set to 0. --> 468 eig_threshold = max(np.max(eig_val[non_zero_eig_vals == 0]), 0) 469 470 return nb_eigenvalues, eig_threshold, corrected_S

<array_function internals> in amax(*args, **kwargs)

~/anaconda3/lib/python3.9/site-packages/numpy/core/fromnumeric.py in amax(a, axis, out, keepdims, initial, where) 2731 5 2732 """ -> 2733 return _wrapreduction(a, np.maximum, 'max', axis, None, out, 2734 keepdims=keepdims, initial=initial, where=where) 2735

~/anaconda3/lib/python3.9/site-packages/numpy/core/fromnumeric.py in _wrapreduction(obj, ufunc, method, axis, dtype, out, **kwargs) 85 return reduction(axis=axis, out=out, **passkwargs) 86 ---> 87 return ufunc.reduce(obj, axis, dtype, out, **passkwargs) 88 89

ValueError: zero-size array to reduction operation maximum which has no identity

most examples say that

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 + CVXPY details.

where the first 1 should be -1

Add warnings on parameters for function values that are per default "differentiable" + warnings in the QuickStart (size of G, feasible set + parameter reuse_gradient).

L ensemble des changements est décrit en messages de commits: Tout est fait dans PEP. Le reste concerne l utilisation des changements. J ai vérifié:

• les tests
• les examples
• la doc
• le readme
• le notebook
• le papier

Mais si vous voulez verifier que je n ai rien n oublié, c est cool! ;)

Hi and thanks for the great package !

The link to the demo in the readme seems broken: https://github.com/bgoujaud/PEPit/blob/master/ressources/educational/PEPit_demo.ipynb

This PR creates the constraint class. Note it is not a child class of Expression as I first expected. I changed this plan. Now an inequality between two expressions is not an expression anymore. And the use of '<=0' is now necessary. I made the appropriate changes in some primitive steps files.

PS: Please review the previous PR first as I already rebased this branch onto the previous one.

The changes are transparent for the authors. They are twofold:

• Keep track of the order of the constraints in PEP.solve to make easier any modification. No need to maintain both solve and _eval_constraint_dual_values methods.
• Factorize updates of the lists of contraints. They now are dealt by send_constraint_to_cvxpy and send_lmi_constraint_to_cvxpy methods instead of the solve one. Those 2 now return None.

Hello, this looks like a promising package! Here are random remarks I got while running the tuto with Aymeric.

• In CI, don't comment the pep8 test :stuck_out_tongue:
• In CI, run the tuto notebook to make sure this is not broken with new changes.
• it can be anoying for import to have capitalize name PEPit, using pepit avoid having to remember what is capital and what is not.
• I was surprised that SmoothStronglyConvexFunction does not raise a ValueError when given mu=0. Using an internal base class wth clearly split cases would avoid user shooting them selfves in the foot.
• PEP.set_initial_point: in term of API, it is weird to call a set_* method that do not take any argument. Would call this create_initial_point or get_initial_point.
• In tutorial, section Algorithm Implementation, iit would be nice to define n here.
• In the tuto, section Solving the PEP, you could rewrite the equation $|f(x_t) - f(x*)| \le \tau |x_0 - x*|$. It would help to compare with the equation bellow, saying $\tau = L / 4 ...$ .
• In tuto Comparison of analytical (obtained in the literature) ... could be move to a follow up notebook to avoid scaring people (stuff after conclusion is always scary :) )