Antonin Chambolle

Claire Delplancke

Matthias J Ehrhardt

Carola-Bibiane Schönlieb

Junqi Tang

Stochastic Primal Dual Hybrid Gradient Algorithm with Adaptive Step-Sizes

whether they are published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

The stochastic primal-dual hybrid gradient (SPDHG) algorithm introduced in [START_REF] Chambolle | Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging applications[END_REF] is a stochastic version of the primal-dual hybrid gradient (PDHG) algorithm, also known as Chambolle-Pock algorithm [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF]. SPDHG has proved more efficient than PDHG for a variety of problems in the framework of large-scale non-smooth convex inverse problems [START_REF] Ehrhardt | Faster PET reconstruction with non-smooth priors by randomization and preconditioning[END_REF][START_REF] Papoutsellis | Core Imaging Library-Part ii: multichannel reconstruction for dynamic and spectral tomography[END_REF][START_REF] Schramm | Fast and memory-efficient reconstruction of sparse poisson data in listmode with non-smooth priors with application to time-of-flight PET[END_REF][START_REF] Zdun | Fast MPI reconstruction with non-smooth priors by stochastic optimization and data-driven splitting[END_REF]. Indeed, SPDHG only uses a subset of the data at each iteration, hence reducing the computational cost of evaluating the forward operator and its adjoint; as a result, for the same computational burden, SPDHG attains convergence faster than PDHG. This is especially relevant in the context of medical imaging, where there is a need for algorithms whose convergence speed is compatible with clinical standards, and at the same time able to deal with convex, non-smooth priors like Total Variation (TV), which are wellsuited to ill-posed imaging inverse problems, but preclude the recourse to scalable gradient-based methods.

Like PDHG, SPDHG is provably convergent under the assumption that the product of its primal and dual step-sizes is bounded by a constant depending on the problem to solve. On the other hand, the ratio between the primal and dual step-sizes is a free parameter, whose value needs to be chosen by the user. The value of this parameter, which can be interpreted as a control on balance between primal and dual convergence, can have a severe impact on the convergence speed of PDHG, and the same also holds true for SPDHG [START_REF] Delplancke | Improving a stochastic algorithm for regularized PET image reconstruction[END_REF]. This leads to an important challenge in practice, as there is no known theoretical or empirical rule to guide the choice of the parameter. Manual tuning is computationally expensive, as it would require running and comparing the algorithm on a range of values, and there is no guarantee that a value leading to fast convergence for one dataset would keep being a good choice for another dataset. For PDHG, [START_REF] Goldstein | Adaptive primal-dual splitting methods for statistical learning and image processing[END_REF] have proposed an online primal-dual balancing strategy to solve the issue, where the values of the step-sizes evolve along the iterations. More generally, adaptive step-sizes have been used for PDHG with backtracking in [START_REF] Goldstein | Adaptive primal-dual splitting methods for statistical learning and image processing[END_REF][START_REF] Malitsky | A first-order primal-dual algorithm with linesearch[END_REF], adapting to local smoothness in [START_REF] Vladarean | A first-order primal-dual method with adaptivity to local smoothness[END_REF] and are widely used for a variety of other algorithms, namely gradient methods in [START_REF] Malitsky | Adaptive gradient descent without descent[END_REF], subgradient methods in [START_REF] Bonettini | Scaling techniques for epsilonsubgradient methods[END_REF] and splitting methods in [START_REF] Bonettini | Variable metric techniques for forward-backward methods in imaging[END_REF][START_REF] Bonettini | Inertial variable metric techniques for the inexact forward-backward algorithm[END_REF][START_REF] Bonettini | A block coordinate variable metric linesearch based proximal gradient method[END_REF][START_REF] Bonettini | On the convergence of primal-dual hybrid gradient algorithms for total variation image restoration[END_REF][START_REF] Malitsky | Golden ratio algorithms for variational inequalities[END_REF] to improve convergence speed and bypass the need for explicit model constants, like Lipschitz constants or operator norms. For SPDHG, an empirical adaptive scheme has been used for Magnetic Particle Imaging but without convergence proof [START_REF] Zdun | Fast MPI reconstruction with non-smooth priors by stochastic optimization and data-driven splitting[END_REF].

On the theoretical side, a standard procedure to prove the convergence of proximal-based algorithms for convex optimization is to use the notion of Féjer-monotonicity [START_REF] Heinz | Convex analysis and monotone operator theory in Hilbert spaces[END_REF]. Constant step-sizes lead to a fixed metric setting, while adaptive step-sizes lead to a variable metric setting. Work [START_REF] Patrick | Variable metric quasi-Fejér monotonicity[END_REF] states the convergence of deterministic Féjer-monotone sequences in the variable metric setting, while work [START_REF] Combettes | Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping[END_REF] is concerned by the convergence of random Féjer-monotone sequences in the fixed metric setting.

In this work, we introduce and study an adaptive version of SPDHG. More precisely:

• We introduce a broad class of strategies to adaptively choose the step-sizes of SPDHG. This class includes, but is not limited to, the adaptive primal-dual balancing strategy, where the ratio of the step-sizes, which controls the balance between convergence of the primal and dual variable, is tuned online.

• We prove the almost-sure convergence of SPDHG under the schemes of the class. In order to do that, we introduce the concept of C-stability, which generalizes the notion of Féjermonotonicity, and we prove the convergence of random C-stable sequences in a variable metric setting, hence generalizing results from [START_REF] Patrick | Variable metric quasi-Fejér monotonicity[END_REF] and [START_REF] Combettes | Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping[END_REF]. We then show that our proposed algorithm falls within this novel theoretical framework by following similar strategies than in the almost-sure convergence proofs of [START_REF] Gutiérrez | On the convergence and sampling of randomized primal-dual algorithms and their application to parallel MRI reconstruction[END_REF][START_REF] Alacaoglu | On the convergence of stochastic primaldual hybrid gradient[END_REF].

• We compare the performance of SPDHG for various adaptive schemes and the known fixed step-size scheme on large-scale imaging inverse tasks (sparse-view CT, limited-angle CT, lowdose CT). We observe that the primal-dual balancing adaptive strategy is always as fast or faster than all the other strategies. In particular, it consistently leads to substantial gains in convergence speed over the fixed strategy if the fixed step-sizes, while in the theoretical convergence range, are badly chosen. This is especially relevant as it is impossible to know whether the fixed step-sizes are well or badly chosen without running expensive comparative tests. Even in the cases where the SPDHG's fixed step-sizes are well-tuned, meaning that they are in the range to which the adaptive step-sizes are observed to converge, we observe that our adaptive scheme still provides convergence acceleration over the standard SPDHG after a certain number of iterations. Finally, we pay special attention to the hyperparameters used in the adaptive schemes. These hyperparameters are essentially controlling the degree of adaptivity for the algorithm and each of them has a clear interpretation and is easy to choose in practice. We observe in our extensive numerical tests that the convergence speed of our adaptive scheme is robust to the choices of these parameters within the empirical range we provide, hence can be applied directly to the problem at hand without fine-tuning, and solves the step-sizes choice challenge encountered by the user.

The rest of the paper is organized as follows. In Section 2, we introduce SPDHG with adaptive step-sizes, state the convergence theorem, and carry the proof. In Section 3, we propose concrete schemes to implement the adaptiveness, followed by numerical tests on CT data in Section 4. We conclude in Section 5. Finally, Section 6 collects some useful lemmas and proofs.

Theory

Convergence theorem

The variational problem to solve takes the form:

min x∈X n i=1 f i (A i x) + g(x),
where X and (Y i ) i∈{1,...,n} are Hilbert spaces,

A i : X → Y i are bounded linear operators, f i : Y i → R ∪ {+∞} and g : X → R ∪ {+∞} are convex functions. We define Y = Y 1 × • • • × Y n with elements y = (y 1 , . . . , y n ) and A : X → Y such that Ax = (A 1 x, . . . , A n x).
⟨A i x, y i ⟩ -f * i (y i ) + g(x), (2.1)
where f * i stands for the Fenchel conjugate of f i . The set of solution to (2.1) is denoted by C, the set of non-negative integers by N and 1, n stands for {1, . . . , n}. Elements (x * , y * ) of C are called saddle-points and characterized by

A i x * ∈ ∂f * i (y * i ), i ∈ 1, n ; - n i=1 A * i y * ∈ ∂g(x * ). (2.2)
In order to solve the saddle-point problem, we introduce the adaptive stochastic primal-dual hybrid gradient (A-SPDHG) algorithm in Algorithm 2.1. At each iteration k ∈ N, A-SPDHG involves the following five steps:

• update the primal step-size τ k and the dual step-sizes (σ k i ) i∈ 1,n (line 4);

• update the primal variable x k by a proximal step with step-size τ k+1 (line 5);

• randomly choose an index i with probability p i (line 6);

• update the dual variable y k i by a proximal step with step-size σ k+1 i (line 7);

• compute the extrapolated dual variable (line 8).

A-SPDHG is adaptive in the sense that the step-sizes values are updated at each iteration according to an update rule which takes into account the value of the primal and dual iterates x l and y l up to the current iteration. As the iterates are stochastic, the step-sizes are themselves stochastic, which must be carefully accounted for in the theory.

Algorithm 2.1: A-SPDHG (variable step-sizes, serial sampling)

1: Input: dual step-sizes (σ 0 i ) i∈ 1,n , primal step-size τ 0 , update rule; probabilities (p i ) i∈ 1,n ; primal variable x 0 , dual variable y 0 2: Initialize ȳ0 = y 0 3: for k ∈ 0, K -1 do

4:

Determine (σ k+1 i ) i∈ 1,n , τ k+1 according to the update rule and the values of (σ l i ) i∈ 1,n , τ l , x l and y l for l ∈ 0, k .

5:

x k+1 = prox τ k+1 g (x k -τ k+1 A * ȳk )

6:

Randomly pick i ∈ 1, n with probability p i 7:

y k+1 j = prox σ k+1 i f * i (y k i + σ k+1 i A i x k+1 ) if j = i y k j if j ̸ = i 8: ȳk+1 j = y k+1 i + 1 pi y k+1 i -y k i if j = i y k j if j ̸ = i 9: end for 10: return x K
Before turning to the convergence of A-SPDHG, let us recall some facts about the state-of-theart SPDHG. Each iteration of SPDHG involves the selection of a random subset of 1, n . In the serial sampling case where the random subset is a singleton, SPDHG algorithm [START_REF] Chambolle | Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging applications[END_REF] is a special case of Algorithm 2.1 with the update rule

σ k+1 i = σ k i (= σ i ), i ∈ 1, n , τ k+1 = τ k (= τ i ), k ∈ N.

Under the condition

τ σ i < p i ∥A i ∥ 2 , i ∈ 1, n , (2.3)
SPDHG iterates converge almost surely to a solution of the saddle-point problem (2.1) [START_REF] Alacaoglu | On the convergence of stochastic primaldual hybrid gradient[END_REF][START_REF] Gutiérrez | On the convergence and sampling of randomized primal-dual algorithms and their application to parallel MRI reconstruction[END_REF].

Let us now turn to the convergence of A-SPDHG. The main theorem, Theorem 2.1 below, gives conditions on the update rule under which A-SPDHG is provably convergent. Plainly speaking, these conditions are threefold:

(i) the step-sizes for step k + 1, (σ k+1 i ) i∈ 1,n and τ k+1 , depend only on the iterates up to step k, (ii) the step-sizes satisfy a uniform version of condition (2.3), (iii) the step-sizes sequences (τ k ) k≥0 and (σ k i ) k≥0 for i ∈ 1, n do not decrease too fast. More precisely, they are uniformly almost surely quasi-increasing in the sense defined below.

In order to state the theorem rigorously, let us introduce some useful notation and definitions. For all k ∈ N, the σ-algebra generated by the iterates up to point k, F (x l , y l ), l ∈ 0, k , is denoted by F k . We say that a sequence (u k ) k∈N is F k k∈N -adapted if for all k ∈ N, u k is measurable with respect to F k .

A positive real sequence (u k ) k∈N is said to be quasi-increasing if there exists a sequence (η k ) k∈N with values in [0, 1), called the control on (u k ) k∈N , such that ∞ k=1 η k < ∞ and :

u k+1 ≥ (1 -η k )u k , k ∈ N.
(2.4)

By extension, we call a random positive real sequence (u k ) k∈N uniformly almost surely quasiincreasing if there exists a deterministic sequence (η k ) k∈N with values in [0, 1) such that ∞ k=1 η k < ∞ and equation (2.4) above holds almost surely (a.s.).

Theorem 2.1 (Convergence of A-SPDHG). Let X and Y be separable Hilbert spaces, A i : X → Y i bounded linear operators, f i : Y i → R ∪ {+∞} and g : X → R ∪ {+∞} proper, convex and lower semi-continuous functions for all i ∈ 1, n . Assume that the set of saddle-points C is non-empty and the sampling is proper, that is to say p i > 0 for all i ∈ 1, n . If the following conditions are met:

(i) the step-size sequences (τ k+1 ) k∈N , (σ k+1 i ) k∈N , i ∈ 1, n are F k k∈N -adapted, (ii) there exists β ∈ (0, 1) such that for all indices i ∈ 1, n and iterates k ∈ N,

τ k σ k i ∥A i ∥ 2 p i ≤ β < 1, (2.5)
(iii) the initial step-sizes τ 0 and σ 0 i for all indices i ∈ 1, n are positive and the step-sizes sequences (τ k ) k∈N and (σ k i ) k∈N for all indices i ∈ 1, n are uniformly almost surely quasi-increasing, then the sequence of iterates (x k , y k ) k∈N converges almost surely to an element of C.

While the conditions (i)-(iii) are general enough to cover a large range of step-sizes update rules, we will focus in practice on the primal-dual balancing strategy, which consists in scaling the primal and the dual step-sizes by an inverse factor at each iteration. In that case, the update rule depends on a random positive sequence (γ k ) k∈N and reads as:

τ k+1 = τ k γ k , σ k+1 i = γ k σ k i , i ∈ 1, n . (2.6)
Lemma 2.2 (Primal-dual balancing). Let the step-sizes sequences satisfy equation (2.6) and assume in addition that (γ k ) k∈N is F k k∈N -adapted, that the initial step-sizes satisfy

τ 0 σ 0 i ∥A i ∥ 2 p i < 1, i ∈ 1, n ,
and are positive, that there exists a deterministic sequence (ϵ k ) k∈N with values in [0, 1) such that ϵ k < ∞ and for all k ∈ N and i ∈ 1, n ,

min γ k , (γ k ) -1 ≥ 1 -ϵ k . (2.7)
Then, the step-sizes sequences satisfy assumptions (i)-(iii) of Theorem 2.1.

Lemma 2.2 is proved in Section 6.

Connection with the literature:

• The primal-dual balancing strategy has been introduced in [START_REF] Goldstein | Adaptive primal-dual splitting methods for statistical learning and image processing[END_REF] for PDHG and indeed for n = 1 we recover with Lemma 2.2 the non-backtracking algorithm presented in [START_REF] Goldstein | Adaptive primal-dual splitting methods for statistical learning and image processing[END_REF]. As a consequence, our theorem also implies the pointwise convergence of this algorithm, whose convergence was established in the sense of vanishing residuals in [START_REF] Goldstein | Adaptive primal-dual splitting methods for statistical learning and image processing[END_REF].

• Still for PDHG, [START_REF] Malitsky | A first-order primal-dual algorithm with linesearch[END_REF] proposes without proof an update rule where the ratio of the step-sizes is either quasi non-increasing or quasi non-decreasing. This requirement is similar to but not directly connected with ours, where we ask the step-sizes themselves to be quasi nonincreasing.

• For SPDHG, the angular constraint step-size rule proposed without convergence proof in [START_REF] Zdun | Fast MPI reconstruction with non-smooth priors by stochastic optimization and data-driven splitting[END_REF] satisfies assumptions (i)-(iii).

Outline of the proof: Theorem 2.1 is proved in the following sub-sections. We first define in Section 2.2 metrics related to the algorithm step-sizes on the primal-dual product space. As the step-sizes are adaptive, we obtain a sequence of metrics. The proof of Theorem 2.1 is then similar in strategy to those of [START_REF] Alacaoglu | On the convergence of stochastic primaldual hybrid gradient[END_REF] and [START_REF] Gutiérrez | On the convergence and sampling of randomized primal-dual algorithms and their application to parallel MRI reconstruction[END_REF] but requires novel elements to deal with the metrics variability. In Theorem 2.5, we state convergence conditions for an abstract random sequence in a Hilbert space equipped with random variable metrics. In Section 2.4 and Section 2.5 we show that A-SPDHG falls within the scope of Theorem 2.5. We collect all elements and conclude the proof in Section 2.6.

Variable metrics

For a Hilbert space H, we call S(H) the set of bounded self-adjoint linear operators from H to H, and for all M ∈ S(H) we introduce the notation:

∥u∥ 2 M = ⟨M u, u⟩, u ∈ H. By an abuse of notation we write ∥ • ∥ 2 α = ∥ • ∥ 2 αId for a scalar α ∈ R. Notice that ∥ • ∥ M is a norm on H if M
is positive definite. Furthermore, we introduce the partial order ≼ on S(H) such that for M, N ∈ S(H),

N ≼ M if ∀u ∈ H, ∥u∥ N ≤ ∥u∥ M .
We call S α (H) the subset of S(H) comprised of M such that αId ≼ M . Furthermore a random sequence (M k ) k∈N in S(H) is said to be uniformly almost surely quasi-decreasing if there exists a deterministic non-negative sequence (η k ) k∈N such that ∞ k=1 η k < ∞ and a.s.

M k+1 ≼ (1 + η k )M k , k ∈ N.
Coming back to A-SPDHG, let us define for every iteration k ∈ N and every index i ∈ 1, n two block operators of S(X × Y i ) as:

M k i =    1 τ k Id -1 pi A * i -1 pi A i 1 piσ k i Id    , N k i =   1 τ k Id 0 0 1 piσ k i Id   ,
and a block operator of S(X × Y ) as:

N k =            1 τ k Id (0) 1 p1σ k 1 Id . . . 1 piσ k i Id . . . (0) 1 pnσ k n Id            .
(2.8)

The following lemma translates assumptions (i)-(iii) of Theorem 2.1 on properties on the variable metric sequences.

Lemma 2.3 (Variable metric properties). (a) Assumption (i) of Theorem 2.1 implies that (M k+1 i ) k∈N , (N k+1 i ) k∈N , i ∈ 1, n and (N k+1 ) k∈N are F k k∈N -adapted. (b) Assumption (ii) of Theorem 2.
1 is equivalent to the the existence of β ∈ (0, 1) such that for all indices i ∈ 1, n and iterates k ∈ N,

(1 -β)N k i ≼ M k i .
(c) Assumptions (ii) and (iii) of Theorem 2.1 imply that (M k i ) k∈N , (N k i ) k∈N , i ∈ 1, n and (N k ) k∈N are uniformly a.s. quasi-decreasing.

(d) Assumption (ii) and (iii) of Theorem 2.1 imply that the sequences (τ k ) k∈N and (σ k i ) k∈N for all i ∈ 1, n are a.s. bounded from above and by below by positive constants. In particular, this implies that there exists α > 0 such that N k i ∈ S α (X × Y i ) for all i ∈ 1, n and k ∈ N, or equivalently that N k ∈ S α (X × Y ) for all k ∈ N.

Remark 2.4 (

Step-sizes induced metrics on the primal-dual product space). The lemma implies that M k i , N k i and N k are positive definite, hence induce a metric on the corresponding spaces. If n = 1 and for constant step-sizes, M k i corresponds to the metric used in [START_REF] He | Convergence analysis of primal-dual algorithms for total variation image restoration[END_REF], where PDHG is reformulated as a proximal point algorithm for a non-trivial metric on the primal-dual product space.

Proof of Lemma 2.3. Assertion (a) of the lemma follows from the fact that for all iterate k ∈ N, the operators M k+1 i , N k+1 i and N k+1 are in the σ-algebra generated by τ k+1 , σ k+1 i , i ∈ 1, n . Assertion (b) follows from equation (6.2) of Lemma 6.1 to be found in the complementary material. The proof of assertion (c) is a bit more involved. Let us assume that assumption (iii) of Theorem 2.1 holds and let (η k 0 ) k∈N and (η k i ) k∈N be the controls of (τ k ) k∈N and (σ k i ) k∈N for i ∈ 1, n respectively. We define the sequence (η k ) k∈N by:

η k = max η k i , i ∈ 0, n , k ∈ N, (2.9)
which is a common control on (τ k ) k∈N and (σ k i ) k∈N for i ∈ 1, n as the maximum of a finite number of controls. Let us fix k ∈ N and i ∈ 1, n . Because the intersection of a finite number of measurable events of probability one is again a measurable event of probability one, it holds almost surely that for all (x, y

i ) ∈ X × Y i , ∥(x, y i )∥ 2 N k+1 i = 1 τ k+1 ∥x∥ 2 + 1 p i σ k+1 i ∥y i ∥ 2 ≤ 1 1 -η k 1 τ k ∥x∥ 2 + 1 p i σ k i ∥y i ∥ 2 = 1 + η k 1 -η k ∥(x, y i )∥ 2 N k i . Hence the sequence (N k i ) k∈N is uniformly quasi-decreasing with control η k (1 -η k ) -1 k∈N , which is indeed a positive sequence with bounded sum. (To see that η k (1 -η k ) -1
k∈N has a bounded sum, consider that η k k∈N is summable, hence converges to 0, hence is smaller than 1/2 for all integers k bigger than a certain K; in turn, for all integers k bigger than K, the term η k (1 -η k ) -1 is bounded from below by 0 and from above by 2η k , hence is summable.) One can see by a similar proof that (N k ) k∈N is uniformly quasi-decreasing with the same control. To follow with the case of (M k i ) k∈N , we have, as before:

M k+1 i =    1 τ k+1 Id -1 pi A * i -1 pi A i 1 piσ k+1 i Id    ≼ M k i + η k 1 -η k N k i ≼ 1 + η k 1 -η k 1 1 - √ β M k i thanks to (b).
Let us conclude with the proof of assertion (d). By assumption (iii), the sequences (τ k ) k∈N and (σ k i ) k∈N are uniformly a.s. quasi-increasing. We define a common control (η k ) k∈N as in (2.9). Then, the sequences (τ k ) k∈N and (σ k i ) k∈N are a.s. bounded from below by the same deterministic constant

C = min τ 0 , σ 0 i , i ∈ 1, n ∞ j=0 (1 -η j
) which is positive as the initial step-sizes are positive and (η k ) k∈N takes values in [0, 1) and has finite sum. Furthermore, by assumption (ii), the product of the sequences (τ k ) k∈N and (σ k i ) k∈N is almost surely bounded from above. As a consequence, each sequence (τ k ) k∈N and (σ k i ) k∈N is a.s. bounded from above. The equivalence with

N k i ∈ S α (X × Y i ) for all i ∈ 1, n , and with N k ∈ S α (X × Y ), is straightforward.

Convergence of random C-stable sequences in random variable metrics

Let H be a Hilbert space and C ⊂ H a subset of H. Let (Ω, σ(Ω), P) be a probability space. All random variables in the following are assumed to be defined on Ω and measurable with respect to σ(Ω) unless stated otherwise. Let (Q k ) k∈N be a random sequence of S(H).

A random sequence (u k ) k∈N with values in H is said to be stable with respect to the target C relative to (Q k ) k∈N if for all u ∈ C, the sequence ∥u k -u∥ Q k k∈N converges almost surely. The following theorem then states sufficient conditions for the convergence of such sequences.

Theorem 2.5 (Convergence of C-stable sequences). Let H be a separable Hilbert space, C a closed non-empty subset of H, (Q k ) k∈N a random sequence of S(H), and (u k ) k∈N a random sequence of H. If the following conditions are met:

(i) (Q k ) k∈N
takes values in S α (H) for a given α > 0 and is uniformly a.s. quasi-decreasing, (ii) (u k ) k∈N is stable with respect to the target C relative to (Q k ) k∈N , (iii) every weak sequential cluster point of (u k ) k∈N is almost surely in C, meaning that there exists Ω (iii) a measurable subset of Ω of probability one such that for all ω ∈ Ω, every weak sequential cluster point of (u k (ω)) k∈N is in C.

then (u k ) k∈N converges almost surely weakly to a random variable in C.

Stability with respect to a target set C is implied by Féjer and quasi-Féjer monotonicity with respect to C, which have been studied either for random sequences [START_REF] Combettes | Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping[END_REF] or in the framework of variable metrics [START_REF] Patrick | Variable metric quasi-Fejér monotonicity[END_REF], but to the best of our knowledge not both at the same time. The proof of Theorem 2.5 follows the same lines than [10, Proposition 2.3 (iii)] and uses two results from [START_REF] Patrick | Variable metric quasi-Fejér monotonicity[END_REF].

Proof. The set C is a subset of the separable Hilbert space H, hence is separable. As C is a closed and separable, there exists {c n , n ∈ N} a countable subset of C whose closure is equal to C. Thanks to assumption (ii), there exists for all n ∈ N a measurable subset Ω n (ii) of Ω with probability one such that the sequence (∥u

k (ω) -c n ∥ Q k (ω) ) k∈N converges for all ω ∈ Ω n (ii)
. Furthermore, let Ω (i) be a measurable subset of Ω of probability one corresponding to the almost sure property for assumption (i). Let

Ω =   n≥0 Ω n (ii)   Ω (i) Ω (iii) .
As the intersection of a countable number of measurable subsets of probability one, Ω is itself a measurable set of Ω with P( Ω) = 1. Fix ω ∈ Ω for the rest of the proof.

The sequence (Q k (ω)) k∈N takes values in S α (H) for α > 0 and is quasi-decreasing with control (η k (ω)) k∈N . Furthermore, for all k ∈ N,

∥Q k (ω)∥ ≤   k-1 j=0 1 + η j   ∥Q 0 (ω)∥ ≤   ∞ j=0 1 + η j   ∥Q 0 (ω)∥,
where the product

∞ j=0 1 + η j is finite because (η k ) k∈N is positive and summable. By [11, Lemma 2.3], (Q k (ω)) k∈N converges pointwise strongly to some Q(ω) ∈ S α (H).
Furthermore, for all x ∈ C, there exists a sequence (x n ) n∈N with values in {c n , n ∈ N} converging strongly to x. By assumption, for all n ∈ N, the sequence (∥u k (ω) -x n ∥ Q k (ω) ) k∈N converges to a limit which shall be called l n (ω). For all n ∈ N and k ∈ N, we can write thanks to the triangular inequality:

-∥x n -x∥ Q k (ω) ≤ ∥u k (ω) -x∥ Q k (ω) -∥u k (ω) -x n ∥ Q k (ω) ≤ ∥x n -x∥ Q k (ω) .
By taking the limit k → +∞, it follows that:

-∥x n -x∥ Q(ω) ≤ lim inf k→∞ ∥u k (ω) -x∥ Q k (ω) -l n (ω) ≤ lim sup k→∞ ∥u k (ω) -x∥ Q k (ω) -l n (ω) ≤ ∥x n -x∥ Q(ω) .
Taking now the limit n → +∞ shows that the sequence (∥u k (ω) -x∥ Q k (ω) ) k∈N converges for all x ∈ C. On the other hand, because ω ∈ Ω (iii) , the weak cluster points of (u k (ω)) k∈N lie in C. Hence, by [START_REF] Patrick | Variable metric quasi-Fejér monotonicity[END_REF]Theorem 3.3], the sequence (u k (ω)) k∈N converges almost surely to a point u(ω) ∈ C.

We are now equipped to prove Theorem 2.1. We show in Section 2.4 and Section 2.5 that A-SPDHG satisfies points (ii) and (iii) of Theorem 2.5 respectively and conclude the proof in Section 2.6. Interestingly, the proofs of point (ii) and of point (iii) rely on two different ways of apprehending A-SPDHG. Point (ii) relies on a convex optimisation argument: by taking advantage of the measurability of the primal variable at step k + 1 with respect to F k , one can write a contraction-type inequality relating the conditional expectation of the iterates' norm at step k + 1 to the iterates' norm at step k. Point (iii) relies on monotone operator theory: we use the fact that the update from the half-shifted iterations (y k , x k+1 ) to (y k+1 , x k+2 ) can be interpreted as a step of a proximal-point algorithm on X × Y i conditionally to i being the index randomly selected at step k.

A-SPDHG is stable with respect to the set of saddle-points

In this section, we show that (x k , y k ) k∈N is stable with respect to C relative to the variable metrics sequence (N k ) k∈N defined in equation (2.8) above. We introduce the operators P ∈ S(Y ) and Σ k ∈ S(Y ) defined respectively by

(P y) i = p i y i , (Σ k y) i = σ k i y i , i ∈ 1, n ,
and the functionals (U k ) k∈N , (V k ) k∈N defined for all (x, y) ∈ X × Y as:

U k (y) = ∥y∥ 2 (P Σ k ) -1 , V k (x, y) = ∥x∥ 2 (τ k ) -1 -2⟨P -1 Ax, y⟩ + ∥y∥ 2 (P Σ k ) -1 .
We begin by recalling the cornerstone inequality satisfied by the iterates of SPDHG stated first in [START_REF] Chambolle | Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging applications[END_REF] and reformulated in [START_REF] Alacaoglu | On the convergence of stochastic primaldual hybrid gradient[END_REF].

Lemma 2.6 ([1], Lemma 4.1). For every saddle-point (x * , y * ), it a.s. stands that for all k ∈ N\{0},

E V k+1 (x k+1 -x * , y k+1 -y k ) + U k+1 (y k+1 -y * )|F k ≤ V k+1 (x k -x * , y k -y k-1 ) + U k+1 (y k -y * ) (2.10) -V k+1 (x k+1 -x k , y k -y k-1 ).
The second step is to relate the assumptions of Theorem 2.1 to properties of the functionals appearing in (2.10). Let us introduce Y sparse ⊂ Y the set of elements (y 1 , . . . , y n ) having at most one non-vanishing component.

Lemma 2.7 (Properties of functionals of interest). Under the assumptions of Theorem 2.1, there exists a non-negative, summable sequence (η k ) k∈N such that a.s. for every iterate k ∈ N and x ∈ X, y ∈ Y, z ∈ Y sparse :

U k+1 (y) ≤ (1 + η k )U k (y),
(2.11a)

V k+1 (x, z) ≤ (1 + η k )V k (x, z), (2.11b) ∥(x, z)∥ 2 N k ≥ α∥(x, z)∥ 2 , (2.11c) V k (x, z) ≥ (1 -β)∥(x, z)∥ 2 N k , (2.11d)
P -1 Ax, z ≤ β∥x∥ (τ k ) -1 ∥z∥ (P Σ k ) -1 .
(2.11e)

Proof. Let (η k i ) k∈N and (η k i ) k∈N be the controls of (M k i ) k∈N and (N k i ) k∈N respectively for all i ∈ 1, n . We define the common control (η k ) k∈N by:

η k = max max η k i , ηk i , i ∈ 1, n , k ∈ N. (2.12)
For all y ∈ Y , we can write

U k+1 (y) = n i=1 ∥(0, y i )∥ 2 N k+1 i ≤ (1 + η k ) n i=1 ∥(0, y i )∥ 2 N k i = (1 + η k )U k (y),
which proves (2.11a). Let us now fix x ∈ X, z ∈ Y sparse and k ∈ N. By definition, there exists i ∈ 1, n such that z j = 0 for all j ̸ = i. We obtain the inequalities (2.11b)-(2.11d) by writing:

V k+1 (x, z) = ∥(x, z i )∥ 2 M k+1 i ≤ (1 + η k )∥(x, z i )∥ 2 M k i = (1 + η k )V k (x, z), ∥(x, z)∥ 2 N k = ∥(x, z i )∥ 2 N k i ≥ α∥(x, z i )∥ 2 = α∥(x, z)∥ 2 , V k (x, z) = ∥(x, z i )∥ 2 M k i ≥ (1 -β)∥(x, z i )∥ 2 N k i = (1 -β)∥(x, z)∥ 2 N k .
Finally, we obtain inequality (2.11e) by writing:

P -1 Ax, z = 1 p i |⟨A i x, z i ⟩| ≤ ∥A i ∥ p i ∥x∥∥z i ∥ = ∥A i ∥ p i * τ k σ k i p i 1/2 ∥x∥ (τ k ) -1 ∥z∥ (P Σ k ) -1 ≤ β∥x∥ (τ k ) -1 ∥z∥ (P Σ k ) -1 ,
where the last inequality is a consequence of (2.5).

Lemma 2.8 (A-SPDHG is C-stable). Under the assumptions of Theorem 2.1, (i) the sequence (x k , y k ) k∈N of Algorithm 2.1 is stable with respect to C relative to (N k ) k∈N , (ii) the following results hold:

E ∞ k=1 (x k+1 -x k , y k -y k-1 )
2 < ∞ and a.s.

x k+1 -x k → 0.

Proof. Let us begin with the proof of point (i). By definition of A-SPDHG with serial sampling, the difference between two consecutive dual iterates is almost surely sparse:

a.s. ∀ k ∈ N \ {0} , y k -y k-1 ∈ Y sparse .
Let us define the sequences

a k = V k (x k -x * , y k -y k-1 ) + U k (y k -y * ), b k = V k+1 (x k+1 -x k , y k -y k-1 ),
which are a.s. non-negative thanks to (2.11c) and (2.11d). Notice that the primal iterates x l from l = 0 up to l = k + 1 are measurable with respect to F k , whereas the dual iterates y l from l = 0 up to l = k are measurable with respect to F k . Hence a k and b k are measurable with respect to F k . Furthermore, inequalities (2.10), (2.11a) and (2.11b) imply that almost surely for all k ∈ N \ {0},

E a k+1 |F k ≤ (1 + η k )a k -b k .
By Robbins-Siegmund lemma [START_REF] Robbins | A convergence theorem for non negative almost supermartingales and some applications[END_REF], (a k ) converges almost surely, sup k E a k < ∞ and

∞ k=1 E b k < ∞.
From the last point in particular, we can write thanks to (2.11d) and the monotone convergence theorem:

E ∞ k=1 y k -y k-1 2 (P Σ k+1 ) -1 ≤ E ∞ k=1 (x k+1 -x k , y k -y k-1 ) 2 N k+1 ≤ (1 -β) -1 E ∞ k=1 b k = (1 -β) -1 ∞ k=1 E b k < ∞, hence ∞ k=1 ∥y k -y k-1 ∥ 2 (P Σ k+1 ) -1 is almost surely finite, thus ∥y k -y k-1 ∥ 2 (P Σ k+1 ) -1 k∈N\{0}
, and in turn ∥y k -y k-1 ∥ (P Σ k+1 ) -1 k∈N\{0} , converge almost surely to 0. Furthermore,

sup k E a k < ∞ hence sup k ∥x k -x * ∥ 2 (τ k ) -1
, and in turn sup k ∥x k -x * ∥ (τ k ) -1 , are finite, and by (2.11e), one can write that for k ∈ N \ {0},

P -1 A(x k -x * ), y k -y k-1 ≤ β∥x k -x * ∥ (τ k+1 ) -1 ∥y k -y k-1 ∥ (P Σ k+1 ) -1 ≤ β(1 + η k )∥x k -x * ∥ (τ k ) -1 ∥y k -y k-1 ∥ (P Σ k+1 ) -1 .
We know that (η k ) k∈N is summable hence converges to 0. As a consequence,

|⟨P -1 A(x k -x * ), y k -y k-1 ⟩| → 0 almost surely.
To conclude with, thanks to the identity

a k = ∥(x k -x * , y k -y * )∥ 2 N k + ⟨P -1 A(x k -x * ), y k -y k-1 ⟩, k ∈ N \ {0} ,
the almost sure convergence of (a k ) k∈N implies in turn that of (∥(x k -x * , y k -y * )∥ 2 N k ) k∈N . Let us now turn to point (ii). The first assertion is a straightforward consequence of

E ∞ k=1 b k = ∞ k=1 E b k < ∞
and bounds (2.11c) and (2.11d). Furthermore, it implies that

∞ k=1 (x k+1 -x k , y k -y k-1 )
2 is a.s. finite, hence (x k+1 -x k , y k -y k-1 ) a.s. converges to 0, and so does x k+1 -x k .

Weak cluster points of A-SPDHG are saddle-points

The goal of this section is to prove that A-SPDHG satisfies point (iii) of Theorem 2.5. On the event I k = i , A-SPDHG update procedure can be rewritten as

y k+1 i = prox σ k+1 i f * i (y k i + σ k+1 i A i x k+1 ), ȳk+1 i = y k+1 i + 1 p i y k+1 i -y k i , ȳk+1 j = y k j , j ̸ = i x k+2 = prox τ k+2 g (x k+1 -τ k+2 A * ȳk+1 ).
We define T σ,τ i : (x, y) → (x, ŷi ) by:

ŷi = prox σif * i (y i + σ i A i x), x = prox τ g x -τ A * y -τ 1 + p i p i A * i (ŷ i -y i ) , so that (x k+2 , y k+1 i ) = T σ k+1 i
,τ k+2 i (x k+1 , y k ) on the event {I k = i} (and y k+1 j = y k j for j ̸ = i). Lemma 2.9 (Cluster points of A-SPDHG are saddle points). Let (x, ȳ) a.s. be a weak cluster point of (x k , y k ) k∈N (meaning that there exists a measurable subset Ω of Ω of probability one such that for all ω ∈ Ω, (x(ω), ȳ(ω)) is a weak sequential cluster point of (x k (ω), y k (ω)) k∈N ) and assume that the assumptions of Theorem 2.1 hold. Then (x, ȳ) is a.s. in C.

Proof. Thanks to Lemma 2.8-(ii) and the monotone convergence theorem,

∞ k=1 E (x k+1 -x k , y k -y k-1 ) 2 = E ∞ k=1 (x k+1 -x k , y k -y k-1 ) 2 < ∞. Now, ∞ k=1 E (x k+1 -x k , y k -y k-1 ) 2 = ∞ k=1 E E ∥(x k+1 -x k , y k -y k-1 )∥ 2 |I k-1 = ∞ k=1 n i=1 P(I k-1 = i)E T σ k i ,τ k+1 i (x k , y k-1 i ) -(x k , y k-1 i ) 2 = E n i=1 p i ∞ k=1 T σ k i ,τ k+1 i (x k , y k-1 ) -(x k , y k-1 i ) 2 .
Hence we can deduce that

E ∞ k=1 n i=1 p i T σ k i ,τ k+1 i (x k , y k-1 ) -(x k , y k-1 i ) 2 < ∞.
It follows that the series in the expectation is a.s. finite, and since p i > 0 we deduce that almost surely, T

σ k i ,τ k+1 i (x k , y k-1 ) -(x k , y k-1 i ) k→∞ -→ 0 (2.13)
for all i = 1, . . . n.

We consider a sample (x k , y k ) which is bounded and such that (2.13) holds.

We let for each i,

(x i,k+1 , ŷi,k i ) = T σ k i ,τ k+1 i (x k , y k-1 ), so that ∥(x i,k+1 , ŷi,k i ) -(x k , y k-1 i )∥ → 0 for i = 1, . . . , n. Then, one has ∂f * i (ŷ i,k i ) ∋ y k-1 i -ŷi,k i σ k i + A i x k =: A i x k + δ i,k y ∂g(x i,k+1 ) ∋ x k -xi,k+1 τ k+1 -A * y k-1 - 1 + p i p i A * i (ŷ i,k i -y k-1 i ) =: -A * y k-1 + δ i,k
x where δ i,k x,y → 0 as k → ∞. Given a test point (x, y), one may write for any k:

f * i (y i ) ≥ f * i (ŷ i,k i ) + ⟨A i x k , y i -y k-1 i ⟩ + ⟨A i x k , y k-1 i -ŷi,k i ⟩ + ⟨δ i,k y , y i -ŷi,k i ⟩, i = 1, . . . , n g(x) ≥ g(x 1,k+1 ) -⟨A * y k-1 , x -x k ⟩ -⟨A * y k-1 , x k -x1,k+1 ⟩ + ⟨δ i,k x , x -x1,k+1 ⟩
and summing all these inequalities, we obtain:

g(x) + n i=1 f * i (y i ) ≥ g(x 1,k+1 ) + n i=1 f * i (ŷ i,k i ) + ⟨A i x k , y i ⟩ -⟨A * y k-1 , x⟩ + δ k
where δ k → 0 as k → ∞. We deduce that if (x, ȳ) is the weak limit of a subsequence (x k l , y k l -1 ) (as well as, of course, (x k l , y k l )), then:

g(x) + n i=1 f * i (y i ) ≥ g(x) + n i=1 (f * i (ȳ i ) + ⟨A i x, y i ⟩) -⟨A * ȳ, x⟩.
Since (x, y) is arbitrary, we find that (2.2) holds for (x, ȳ).

Proof of Theorem 2.1

Under the assumptions of Theorem 2.1, the set C of saddle-points is closed and non-empty and X × Y is a separable Hilbert space. By Lemma 2.3, the variable metrics sequence (N k ) k∈N defined in (2.8) satisfies condition (i) of Theorem 2.5. Furthermore, the iterates of Algorithm 2.1 comply with condition (ii) and (iii) of Theorem 2.5 by Lemma 2.8 and Lemma 2.9 respectively, hence converge almost surely to a point in C.

Algorithmic Design and Practical Implementations

In this section we present practical instances of our A-SPDHG algorithm, where we specify a stepsize adjustment rule which satisfies our assumptions in convergence proof. We extend the adaptive step-size balancing rule for deterministic PDHG, which is proposed by [START_REF] Goldstein | Adaptive primal-dual splitting methods for statistical learning and image processing[END_REF], into our stochastic setting, with minibatch approximation to minimize the computational overhead.

A-SPDHG rule (a) -Tracking & balancing the primal-dual progress

Let's first briefly introduce the foundation of our first numerical scheme, which is built upon the deterministic adaptive PDHG algorithm proposed by Goldstein et al [START_REF] Goldstein | Adaptive primal-dual splitting methods for statistical learning and image processing[END_REF], with the iterates:

x k+1 = prox τ k+1 g (x k -τ k+1 A * y k ), y k+1 = prox σ k+1 f * (y k + σ k+1 A(2x k+1 -x k ))
In this foundational work of Goldstein et al [START_REF] Goldstein | Adaptive primal-dual splitting methods for statistical learning and image processing[END_REF], they proposed to evaluate two sequences in order to track and balance the progresses of the primal and dual iterates of deterministic PDHG (denoted here as v * k and d * k ):

v * k := ∥(x k -x k+1 )/τ k+1 -A * (y k -y k+1 )∥ 1 , d * k := ∥(y k -y k+1 )/σ k+1 -A(x k -x k+1 )∥ 1 . (3.1)
These two sequences measure the lengths of the primal and dual subgradients for the objective min x∈X max y∈Y g(x) + ⟨Ax, y⟩ -f * (y), which can be demonstrated by the definition of proximal operators. The primal update of deterministic PDHG can be written as:

x k+1 = arg min x 1 2 ∥x -(x k -τ k+1 A * y k )∥ 2 2 + τ k+1 g(x). (3.2)
The optimality condition of the above objective declares:

0 ∈ ∂g(x k+1 ) + A * y k + 1 τ k+1 (x k+1 -x k ). (3.3)
By adding -A * y k+1 on both sides and rearranging the terms, one can derive:

(x k -x k+1 )/τ k+1 -A * (y k -y k+1 ) ∈ ∂g(x k+1 ) + A * y k+1 (3.4)
and similarly for the dual update one can also derive:

(y k -y k+1 )/σ k+1 -A(x k -x k+1 ) ∈ ∂f * (y k+1 ) -Ax k+1 , (3.5)
which indicates that the sequences v * k and d * k given by (3.1) should effectively track the primal progress and dual progress of deterministic PDHG, hence Goldstein et al [START_REF] Goldstein | Adaptive primal-dual splitting methods for statistical learning and image processing[END_REF] propose to utilize these as the basis of balancing the primal and dual step sizes for PDHG.

In light of this, we propose our first practical implementation of A-SPDHG in Algorithm 3.1 as our rule-(a), where we use a unique dual step-size σ k = σ k j for all iterates k and indices j and where we estimate the progress of achieving optimality on the primal and dual variables via the two sequences v k and d k defined at each iteration k with I k = i as:

v k+1 := ∥(x k -x k+1 )/τ k+1 - 1 p i A * i (y k i -y k+1 i )∥ 1 , d k+1 := 1 p i ∥(y k i -y k+1 i )/σ k+1 -A i (x k -x k+1 )∥ 1 , (3.6)
which are minibatch extension of (3.1) tailored for our stochastic setting. By making them balanced on the fly via adjusting the primal-dual step size ratio when appropriate, we can enforce the algorithm to achieve similar progress in both primal and dual steps, hence improve the convergence. To be more specific, as shown in Algorithm 3.1, in each iteration the values of v k and d k are evaluated and compared. If the value of v k (which tracks the primal subgradients) is significantly larger than d k (which tracks the dual subgradients), then we know that the primal progress is slower than the dual progress, hence the algorithm would boost the primal step size while shrinking the dual step-size. If v k is noticeably smaller than d k then the algorithm would do the opposite.

Note that here we adopt the choice of ℓ 1 -norm as the length measure for v k and d k as done by Goldstein et al [START_REF] Goldstein | Adaptive primal-dual splitting methods for statistical learning and image processing[END_REF][START_REF] Goldstein | Adaptive primaldual hybrid gradient methods for saddle-point problems[END_REF], since we also observe numerically the benefit over the more intuitive choice of ℓ 2 -norm.

For full-batch case (n = 1), it reduces to the adaptive PDHG proposed by [START_REF] Goldstein | Adaptive primal-dual splitting methods for statistical learning and image processing[END_REF][START_REF] Goldstein | Adaptive primaldual hybrid gradient methods for saddle-point problems[END_REF]. We adjust the ratio between primal and dual step sizes according to the ratio between v k and d k , and whenever the step-sizes change, we shrink α (which controls the amplitude of the changes) by a factor η ∈ (0, 1) -we typically choose η = 0.995 in our experiments. For the choice of s, we choose s = ∥A∥ as our default.1

Reducing the overhead with subsampling:

Noting that unlike the deterministic case which does not have the need of extra matrix-vector multiplication since A * y k and Ax k can be memorized, our stochastic extension will require the computation of A i x k since we will sample different subsets between back-to-back iterations with high probability. When using this strategy, we will only have a maximum 50% overhead in terms of FLOP counts, which is numerically negligible compared to the significant acceleration it will bring towards SPDHG especially when the primal-dual step-size ratio is suboptimal, as we will demonstrate later in the experiments. Moreover, we found numerically that we can significantly reduce this overhead by approximation tricks such as subsampling:

d k+1 ≈ ρ p i ∥S k (y k i -y k+1 i )/σ k+1 -S k A i (x k -x k+1 )∥ 1 (3.7)
with S k being a random subsampling operator such that E[(S k ) T S k ] = 1 ρ Id. In our experiments we choose 10% subsampling for this approximation hence the overhead is reduced from 50% to only 5% which is negligible, without compromising the convergence rates in practice.

A-SPDHG rule (b) -Exploiting angle alignments

More recently, Yokota and Hontani [START_REF] Yokota | An efficient method for adapting step-size parameters of primal-dual hybrid gradient method in application to total variation regularization[END_REF] propose a variant of adaptive step-size balancing scheme for PDHG, utilizing the angles between the subgradients ∂g(x k+1 ) + A * y k+1 and the difference of the updates x k -x k+1 .

If these two directions are highly aligned, then the primal step size can be increased for bigger step. If these two directions have a large angle, then the primal step-size should be shrunken. By extending this scheme to stochastic setting we obtain another choice of adaptive scheme for SPDHG.

Algorithm 3.1: A-SPDHG, rule (a)

Input: dual step-size σ 0 , primal step-size τ 0 , α 0 ∈ (0, 1), η ∈ (0, 1), δ > 1, probabilities (p i ) 1≤i≤n ; primal variable x 0 , dual variable We present this scheme in Algorithm 3.2 as our rule (b). At iteration k with I k = i, compute:

y 0 Initialize ȳ0 = y 0 , v 0 = d 0 = 0, s = ∥A∥ for k ∈ 0, K -1 do If v k > sd k δ then τ k+1 = τ k 1-α k , σ k+1 = σ k (1 -α k ), α k+1 = α k η If v k < sd k /δ then τ k+1 = τ k (1 -α k ), σ k+1 = σ k 1-α k , α k+1 = α k η If sd k /δ ≤ v k ≤ sd k δ then τ k+1 = τ k , σ k+1 = σ k , α k+1 = α k x k+1 = prox τ k+1 g (x k -τ k+1 A * ȳk ) Randomly pick i ∈ 1, n with probability p i y k+1 j = prox σ k+1 f * i (y k i + σ k+1 A i x k+1 ) if j = i y k j if j ̸ = i ȳk+1 j = y k+1 i + 1 pi y k+1 i -y k i if j = i y k j if j ̸ = i v k+1 = ∥(x k -x k+1 )/τ k+1 -1 pi A * i (y k i -y k+1 i )∥ 1 d k+1 = 1 pi ∥(y k i -y k+1 i )/σ k+1 -A i (x k -x k+1 )∥ 1 -
q k+1 = (x k -x k+1 )/τ k+1 - 1 p i A * i (y k i -y k+1 i ), (3.8)
as an estimate of ∂g(x k+1 ) + A * y k+1 , then measure the cosine of the angle between this and x k -x k+1 :

w k+1 = ⟨x k -x k+1 , q k+1 ⟩ (∥x k -x k+1 ∥ 2 ∥q k+1 ∥ 2 )
.

(3.9)

The threshold c for the cosine value (which triggers the increase of the primal step-size) typically needs to be very close to 1 (we use c = 0.999) due to the fact that we mostly apply these type of algorithms in high-dimensional problems, following the choice in [START_REF] Yokota | An efficient method for adapting step-size parameters of primal-dual hybrid gradient method in application to total variation regularization[END_REF] which was for deterministic PDHG.

Recently Zdun et al [START_REF] Zdun | Fast MPI reconstruction with non-smooth priors by stochastic optimization and data-driven splitting[END_REF] proposed a heuristic similar to our rule (b), but they choose q k+1 to be the approximation for an element of ∂g(x k+1 ) instead of ∂g(x k+1 ) + A * y k+1 . Our choice follows more closely to the original scheme of Yokota and Hontani [START_REF] Yokota | An efficient method for adapting step-size parameters of primal-dual hybrid gradient method in application to total variation regularization[END_REF]. We numerically found that their scheme is not competitive in our settings.

Algorithm 3.2: A-SPDHG, rule (b)

Input: dual step-size σ 0 , primal step-size τ 0 , η ∈ (0, 1), probabilities (p i ) 1≤i≤n ; primal variable x 0 , dual variable y 0 Initialize ȳ0 = y 0 , w 0 = 0, Please also note that the early jump in terms of function value is within our expectation due to the stochasticity of the algorithms. We include the images reconstructed by the algorithms at termination (50th epoch).

α 0 = 1 for k ∈ 0, K -1 do If w k < 0 then τ k+1 = τ k 1+α k , σ k+1 = σ k (1 + α k ), α k+1 = α k η If w k ≥ c then τ k+1 = τ k (1 + α k ), σ k+1 = σ k 1+α k , α k+1 = α k η If 0 ≤ w k < c then τ k+1 = τ k , σ k+1 = σ k , α k+1 = α k x k+1 = prox τ k+1 g (x k -τ k+1 A * ȳk ) Randomly pick i ∈ 1, n with probability p i y k+1 j = prox σ k+1 f * i (y k i + σ k+1 A i x k+1 ) if j = i y k j if j ̸ = i ȳk+1 j = y k+1 i + 1 pi y k+1 i -y k i if j = i y k j if j ̸ = i q k+1 = (x k -x k+1 )/τ k+1 -1 pi A * i (y k i -y k+1 i ) w k+1 = ⟨x k -x k+1 , q k+1 ⟩/(∥x k -x k+1 ∥ 2 ∥q k+1 ∥ 2 ) end for return x K

Numerical Experiments

In this section we present numerical studies of the proposed scheme in solving one of the most typical imaging inverse problems, the Computed Tomography (CT). We compare A-SPDHG algorithm with the original SPDHG, on different choices of starting ratio of the primal and dual step-sizes. In our CT imaging example, we seek to reconstruct the tomography images from fan-beam X-ray measurement data, by solving the following TV-regularized objective:

x ⋆ ∈ arg min x∈R d 1 2 ∥Ax -b∥ 2 2 + λ∥Dx∥ 1 (4.1)
where D denotes the 2D differential operator, A ∈ R m×d and x ∈ R d . We consider three fanbeam CT imaging modalities: Sparse-View CT, Low-Dose CT and Limited-Angle CT. We test the A-SPDHG and SPDHG on two images of different sizes (Example 1 on a phantom image sized 1024 × 1024, while Example 2 being an image from the Mayo Clinic Dataset [START_REF] Mccollough | Tu-fg-207a-04: Overview of the low dose ct grand challenge[END_REF] sized 512 × 512.), on 4 different starting ratios (10 -3 , 10 -5 , 10 -7 and 10 -9 ). We interleave partitioned the measurement data and operator into n = 10 minibatches for both algorithms. To be more specific, we first collect all the X-ray measurement data and list them consecutively from 0 degree to 360 degree to form the full A and b, and then interleavingly group every 10-th of the measurements into one minibatch, to form the partition {A i } 10 i=1 and {b i } 10 i=1 . For A-SPDHG we choose to use the approximation step for d k presented in (3.7) with 10% subsampling hence the computational overhead is negligible in this experiment. We initialize all algorithms from a zero-image.

We present our numerical results in Figures 1, 2, 3 and 6. In these plots we compare the convergence rates of the algorithms in terms of number of iterations (the execution time per iteration for the algorithms are almost the same, as the overhead of A-SPDHG is trivial numerically). Among these, Figures 1 and2 report the results for large-scale sparse-view CT experiments on a phantom image and a lung CT image from Mayo-Clinic dataset [START_REF] Mccollough | Tu-fg-207a-04: Overview of the low dose ct grand challenge[END_REF], while Figure 3 reports the results for low-dose CT experiments where we simulate a large number of measurements corrupted with a significant amount Poisson noise, and then, in Figure 6 we report the results for limited-angle CT which only a range of 0-degree to 150-degree of measurement angles are present, while the measurements from the rest [150, 360] degrees of angles are all missing. In all these examples we can consistently observe that no matter how we initialize the primal-dual step-size ratio, A-SPDHG can automatically and consistently adjust the step size ratio to the optimal choice which is around either 10 -5 or 10 -7 for these four different CT problems, and significantly outperform the vanilla SPDHG for the cases where the starting ratio is away from the optimal range. Meanwhile, even for the cases where the starting ratio of SPDHG algorithm is near-optimal, we can observe consistently from most of these examples that our scheme outperforms the vanilla SPDHG algorithm locally after a certain number of iterations (highlighted by the vertical dash lines in relevant subfigures), which further indicates the benefit of adaptivity for this class of algorithms2 . Note that throughout all these different examples, we use only one fixed set of parameters for A-SPDHG suggested in the previous section, which again indicates the strong practicality of our scheme.

For the low-dose CT example, we run two extra sets of experiments, regarding a larger number of partioning of minibatches (40) on Figure 4, and warm-start from a better initialization image obtained via filter-backprojection on Figure 5. We found that in all these extra examples we consistently observe superior performances of A-SPDHG over the vanilla SPDHG especially when the primal-dual step-size ratios are suboptimal. Interestingly, we found that the warm-start's effect does not have noticeable impact of the comparative performances between SPDHG and A-SPDHG. This is mainly due to the fact that the SPDHG with suboptimal primal-dual step-size ratio will converge very slowly in high accuracy regimes (see Fig 5(d) for example) in practice hence the warm-start won't help much here.

We should also note that conceptually all the hyperparameters in our adaptive schemes are basically the controllers of the adaptivity of the algorithm (while for extreme choices we recover the vanilla SPDHG). In Figures 7 and9, we present some numerical studies on the choices of hyperparameters of rule (a) and rule (b) of A-SPDHG algorithm. We choose the fixed starting ratio of 10 -7 for primal-dual step-sizes in these experiments. For rule (a), we found that it is robust to the choice of the starting shrinking rate α 0 , shrinking speed η and the gap δ. Overall, we found that these parameters have weak impact of the convergence performance of our rule (a) and easy to choose.

For rule (b), we found that the performance is more sensitive to the choice of parameter c and η comparing to rule (a), although the dependence is still weak. Our numerical studies suggest that rule (a) is a better-performing choice than rule (b), but each of them have certain mild weaknesses (the first rule has a slight computational overhead which can be partitially addressed with subsampling scheme, while the second rule seems often being slower than the first rule), which require further studies and improvements. Nevertheless, we need to emphasis that all these parameters are essentially controlling the degree of adaptivity of the algorithms and fairly easy to choose, noting that for all these CT experiments with varying sizes/dimensions and modalities we only use one fixed set of the hyperparameters in A-SPDHG, and we are already able to consistently observe numerical improvements over vanilla SPDHG.

Conclusion

In this work we propose a new framework (A-SPDHG) for adaptive step-size balancing in stochastic primal-dual hybrid gradient methods. We first derive theoretically sufficient conditions on the adaptive primal and dual step-sizes for ensuring convergence in the stochastic setting. We then propose a number of practical schemes which satisfy the condition for convergence, and our numerical results on imaging inverse problems supports the effectiveness of the proposed approach.

To our knowledge, this work constitutes the first theoretical analysis of adaptive step-sizes for a stochastic primal-dual algorithm. Our on-going work includes the theoretical analysis and algorithmic design of further accelerated stochastic primal-dual methods with line-search schemes for even faster convergence rates.

Complementary material for Section 2

We begin by a useful lemma. . We can observe that our default choice of s is indeed a reasonable choice (at least near-optimal) in practice, and when deviating from it may lead to slower convergence.

space X to a Hilbert space Y . Then, which proves the direct implication of (6.1). For the converse implication, consider x ∈ X \{0} such that ∥P x∥ = ∥P ∥∥x∥ and y = -λP x for a scalar λ. Then, the non-negativity of the polynomial

(
∥(x, y)∥ 2 M ∥x∥ 2 = b∥P ∥ 2 λ 2 -2∥P ∥ 2 λ + a
for all λ ∈ R implies that ∥P ∥ 4 -ab∥P ∥ 2 ≤ 0, which is equivalent to the desired conclusion (ab) -1/2 ∥P ∥ ≤ 1. Equivalence (6. Let us now turn to the proof of Lemma 2.2.

Proof of Lemma 2.2. Let us assume that the step-sizes satisfy the assumptions of the lemma. Then, Assumption (i) of Theorem 2.1 is straightforwardly satisfied. Moreover, for i ∈ 1, n , the product sequence (τ k σ k i ) k∈N is constant along the iterations by equation (2.6) and satisfies equation (2.5) for iterate k = 0, thus satisfies (2.5) for all k ∈ N for β = max i τ 0 σ 0 i ∥A i ∥ 2 /p i , which proves Assumption (ii). Finally, equation (2.7) implies that Assumption (iii) is satisfied.

Declarations

Ethical approval

This declaration is not applicable.

Competing interests

There are no competing interests to declare.

Authors' contribution

CD, MJE and AC elaborated the proof strategy and CD wrote parts 1, 2 and 6. JT worked on the algorithmic design, performed the numerical experiments and wrote parts 3-5. All authors reviewed the manuscript.

Funding

CD acknowledges support from the EPSRC (EP/S026045/1). MJE acknowledges support from the EPSRC (EP/S026045/1, EP/T026693/1, EP/V026259/1) and the Leverhulme Trust (ECF-2019-478). CBS acknowledges support from the Philip Leverhulme Prize, the Royal Society Wolfson Fellowship, the EPSRC advanced career fellowship EP/V029428/1, EPSRC grants EP/S026045/1 and EP/T003553/1, EP/N014588/1, EP/T017961/1, the Wellcome Innovator Awards 215733/Z/19/Z and 221633/Z/20/Z, the European Union Horizon 2020 research and innovation programme under the Marie Skodowska-Curie grant agreement No. 777826 NoMADS, the Cantab Capital Institute for the Mathematics of Information and the Alan Turing Institute.

Availability of data and materials

The related implementation of the algorithms and the image data used in the experiment will be made available on the website https://junqitang.com . For the phantom image example we use the one in the experimental section of [START_REF] Chambolle | Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging applications[END_REF], while for the lung CT image example we use an image from the Mayo Clinic Dataset [START_REF] Mccollough | Tu-fg-207a-04: Overview of the low dose ct grand challenge[END_REF] which is publicly available.

  starting ratio 10 -9

Figure 1 :

 1 Figure 1: Comparison between SPDHG and A-SPDHG on Sparse-View CT (Example 1), with a variety of starting primal-dual step-size ratios. Here the forward operator A ∈ R m×d where the dimension m = 368640, d = 1048576. We include the images reconstructed by the algorithms at termination (50th epoch). In the first plot of each subfigure, the black circle indicates the starting step-size ratio for all the algorithms, same for the following figures.

Figure 2 :

 2 Figure 2: Comparison between SPDHG and A-SPDHG on Sparse-View CT (Example 2), with a variety of starting primal-dual step-size ratios. Here the forward operator A ∈ R m×d where the dimension m = 92160, d = 262144. We include the images reconstructed by the algorithms at termination (50th epoch).

Figure 3 :

 3 Figure 3: Comparison between SPDHG and A-SPDHG on Low-Dose CT (where we use a large number of highly-noisy X-ray measurements), with a variety of starting primal-dual step-size ratios. Here the forward operator A ∈ R m×d where the dimension m = 184320, d = 65536. We resized the phantom image to 256 by 256. We include the images reconstructed by the algorithms at termination (50th epoch).

Figure 4 :

 4 Figure 4: Comparison between SPDHG and A-SPDHG with the data being splitted to 40 minibatches on Low-Dose CT. Comparing to the results presented in Fig.3 which used 10 minibatches, we obtain similar results and our A-SPDHG continues to perform more favorably comparing to SPDHG..

Figure 5 :

 5 Figure 5: Comparison between SPDHG and A-SPDHG with warm-start using a FBP (filtered back-projection) on Low-Dose CT. Comparing to the results shown in the Figure 3 which are without warm-start, actually our methods seem to compare even more favorably with warm-start.Please also note that the early jump in terms of function value is within our expectation due to the stochasticity of the algorithms. We include the images reconstructed by the algorithms at termination (50th epoch).

  starting ratio 10 -9

Figure 6 :

 6 Figure 6: Comparison between SPDHG and A-SPDHG on Limited-Angle CT (Example 2), with a variety of starting primal-dual step-size ratios. Here the forward operator A ∈ R m×d where the dimension m = 92160, d = 262144. We include the images reconstructed by the algorithms at termination (50th epoch).

Lemma 6 . 1 .

 61 Let a, b be positive scalars, β ∈ (0, 1), and P a bounded linear operator from a Hilbert Test on the choices for δ

Figure 7 :Figure 8 :

 78 Figure 7: Test on different choices of parameters of A-SPDHG (rule-a) on X-ray Low-Dose fanbeam CT example, starting ratio of primal-dual step-sizes: 10 -7. We can observe that the performance of ASPDHG has only minor dependence on these parameter choices.

  ab) -1/2 ∥P ∥ ≤ 1 ⇔ a Id P * For all (x, y) ∈ X × Y , ∥(x, y)∥ 2 M ≥ a∥x∥ 2 + b∥y∥ 2 -2∥P ∥∥x∥∥y∥ = ∥x∥ 2 a + ∥y∥ 2 b -2(ab) -1/2∥P ∥∥x∥ a ∥y∥ b , Test on the choices for η

Figure 9 :

 9 Figure 9: Test on different choices of parameters of A-SPDHG (rule-b) on X-ray Low-Dose fanbeam CT example, starting ratio of primal-dual step-sizes: 10 -7 .

The choice of s is crucial for the convergence behavior of rule (a), and we found numerically that it is better to scale with the operator norm ∥A∥ instead of depending on the range of pixel values as suggested in[START_REF] Goldstein | Adaptive primaldual hybrid gradient methods for saddle-point problems[END_REF].

The most typical example here would be the Figure1(b)where the optimal step-size ratio selected by the adaptive scheme at convergence is almost exactly 10 -5 , where we have set SPDHG to run with this ratio. We can still observe benefit of local convergence acceleration given by our adaptive scheme.


consumption is becoming widespread in the slums of Buenos Aires in the aftermath of the 2001 crisis. See

The Lost War: The Prohibition of Impossible Drugs, Public Policies and Social Practices in Latin America in the 21st Century

War and prohibitionism

In the post-Cold War era, drug control monopolized security policies in much of the Western hemisphere. The debate on drugs and drug trafficking was synonymous with the debate on the threat posed. The "war on drugs" promoted by the United States became the outcome. It was the logical -and extreme -expression of the paradigm that inspired public policies to combat drug trafficking: prohibitionism. This was built on an illusion: the eradication of the consumption of psychoactive substances, licit or illicit.

The prohibitionist paradigm was intertwined with various discourses -moral, religious, health, legal, economic and security -even though its legitimacy was above all in the authority granted by the health or medical discourse determining what an "at risk" substance was and from when it became so -although this discourse has since changed. Necessary dissuasions for potential consumers, these discourses had a central role in communication practices, emphasizing that the danger associated with drugs was multifaceted. As in the alcoholism movement in the United States 1 , the "war on drugs" has helped to shape a collective by establishing connections between actors from different circles: politicians, doctors, police, the military, religion, lawyers and moral leagues. The actors involved in this cause have succeeded in forging a representation of the world that is intended to Chapter written by Edgardo MANERO. 1 On this subject, see the work of Joseph R. Gusfield. influence public policy. Among the various discourses, security has gradually gained ground, establishing itself almost in symmetry with the medical sector.

Even though, in practice, it is only a market regulation, prohibitionism corresponds to the total prohibition of drug use, to its definition as a crime and therefore to the need for punishment. The prohibitionist paradigm considers harmful drugs. It is in the name of a conception of "good", not only in terms of health, that the prohibition of drug use and its criminalization are justified. It would be a bad activity in itself, degrading, not in line with what society considers to be an ideal of life. Criminalization only confirms its moral condemnation. However, if criminalization is influenced by a religiously-inspired morality, prohibitionism develops even in societies where the neutrality of the State with regard to conceptions of the good often leads to a certain tolerance, including in matters of morals.

The "war" has reduced the issue of drug use to a security problem that is not limited to the fact that those who consume must be and are prosecuted, thus creating the conditions for a social and health problem with a police connotation to be considered on the basis of a "military" logic. As part of the reduction of the drug problem, which is a combination of addiction and illegality, and subject to the logic of eradication -from crops to consumers -militarization has come to be involved in all aspects of Latin American societies. As part of the war on drug trafficking, the Mexican state destroyed places of worship dedicated to the Holy Death in 2009. The "war on drugs" must be seen as an integral part of securing socio-economic problems and the resulting militarization of solutions.

As a public policy, prohibitionism has its raison d'être in the attempt to reduce drug flows and stocks; it seeks to reduce drug demand by attacking, through the use of force -not just state power -the production and distribution process. With the "war", the United States has brought to a climax the prohibitionist discourse, conceived as necessary to safeguard an aseptic social body. Like the anti-communist struggle, prohibitionism requires the elimination of "contagious" and "degenerate" agents. The figure of the enemy coincides with that of a foreign body to be destroyed to save the organism, the "sick society". The prophylactic operation is part of a certain idea of "social cleansing". Prohibitionism makes clear the traces of a representation of social life absorbed by biological metaphors of parasites that generate epidemics that threaten the integrity of the healthy organism. Imagery of the parasite and contagion is a key figure in the discourse of hostility. This imagery, in a broad sense that goes from predator to parasite, allows an analog system oriented to evoke the "infrahumanity" of this threatening Other. This representation of otherness and the action that accompanies it is based on a conception of social harm. This desire to eradicate is in line with the logic of prohibitionism, which proclaims the community's self-defense in the face of aggression. Its actions therefore fall within the pure and simple right to defend oneself against harm, showing us that devaluation remains in itself, beyond the economic situation, an essential recourse of the strategy.

The war advocates the criminalization of drugs in all its aspects -including that of the user -from the manufacture of drugs to consumption and trade, reducing the solution of this problem to the question of eliminating supply, mainly through the use of violence. In prohibitionist logic, supply must be controlled even though the effects of repression on consumption and trafficking are minor. As demonstrated by the number of members of the armed and security forces involved in the struggle, this elimination is primarily the result of the use of force. Prohibitionism has social implications in terms of criminalization first and repression second, not only of certain practices but fundamentally of certain populations. There are different scales in the narco-crime chain, which are perceived and addressed in a differentiated way -and not only by prohibitionist policies.

In the logic of sanctuarization, limited to US society, the repressive procedure is considered the only valid response. The prohibitionist unambiguously expresses this dimension of safeguarding, of setting aside and intangibility, which is specific to sanctuarization as the designation of a space benefiting from a set of measures ensuring protection. As a result of the supply-side concentration, the policies put in place by the United States have made eradication a priority by limiting Latin America to drug trafficking, which is perceived as the only source of corruption and violence, thus reinforcing the idea of a chaotic space. The limited treatment of the drug issue, which occurs from different fields, from politics to journalism, from literature to cinema, collaborates in this. Recurrent and classic points of view highlight the illegal dimension of the phenomenon, the security and economic implications of criminal activity. The problem is reduced to organizations involved in acts of violence, their confrontation with the State or other actors, the laundering of assets resulting from illicit activities2 and a tangle of legality and illegality that rarely goes beyond the economies in which the circulation of drug trafficking money or the complicity of the security forces flows.

The "war on drugs" has gradually made it possible to abandon the Rousseauist idea that war is a matter for symmetrical state actors. It expresses the vision of the scenario from 1989, according to which the "novelty" of violent conflicts was linked to the increased autonomy of the actors involved in them from the state system. The representation of "war" is structured on a geographical distribution and topological allocation that ignores the multiple aspects of drug trade-related flows and pits Latin America, seen as a kind of global south, against a globalizing north, which is not only expressed by the United States. However, the problem posed by drug use and drug trafficking is no longer reduced solely to the demand of the United States. In the 21st Century, Latin America is also becoming an important consumer market, changing the traditional division of labor; Brazil occupies one of the leading positions in cocaine consumption and Argentina has moved from the transit to the consumption and manufacturing of drugs -even synthetic drugs -as well as to playing a supplying role in terms of chemical precursors to narcotic organizations, particularly from Mexico. In addition, the issue also requires considering the United States not only as a market, but also as an actor in the illegal trafficking of arms or money laundering.

The war on drugs is not only rooted in the US government or in the reactionary sectors of Latin American societies. It is necessarily plural: we must talk about wars. The "war" involves both the policies implemented by American governments, the public policies designed by the States of the region, as well as the behavior of large sections of society towards a specific population or the interests that emerge from criminalization. The repressive and functional scheme has a wide range of actors: suppliers of equipment to the armed forces and police, ideologically conservative social actors, pharmaceutical companies claiming to maintain a monopoly on the treatment of certain diseases, members of the judicial system, economic actors and members of the security forces and the political class who benefit from international funding and the benefits of the illegal economy.

The war cannot be reduced to a question of politically conservative sectors. The criminalization of drug use in different political regimes suggests that attitudes towards drugs are part of a world view where the right-left divide; authoritarianismdemocracy must be relativized. Drug policies remind us that they reflect a particularly revealing image of the characteristics of social order, reflecting both the influence of "national" interests and the ambiguities of ideologies. The repressive management of the problem had no mechanical relationship with the political ideological variable or with the type of regime variable, either during or after the Cold War. Prohibitionism is not necessarily the property of dictatorial or right-wing governments. In Argentina, between 1968 and 1973, under the military government, there was no criminalization of drug use. However, in 1974, in a democracy, law 20,771 was passed, which tried to designate both drug traffickers and users as criminals. In the repressive paradigm, Castroist Cuba and Chavist Venezuela coincided with right-wing, democratic or authoritarian governments. The characteristics of prohibition in democratic and dictatorial regimes may change somewhat. This explains the absence of a break with practices and policies implemented during military regimes. Since the return of democracy, Latin American countries have devoted almost the entire budget allocated to the war against drugs to the repressive aspect.

Chronicle of an announced failure

Policies aimed at reducing supply through violence have not stopped either trafficking or the sale of drugs on the US market. The war on drugs was the focus of a policy reduced to the simple desire to limit the supply, particularly of cocaine, on this market. The war on drugs has not reduced its availability or quantity and, fundamentally, has not increased its price. The ban has neither affected supply nor made prices prohibitive. Cocaine has been made more accessible. The price per gram has gradually decreased. In the 21st Century, the gradual reduction in the US market of the importance of crack cocaine compared to methamphetamines and heroin has other causes than "war".

Drugs are more available in terms of quantity and the risks involved in obtaining them are lower than in the past. The war has not affected the quality of cocaine either -it is less cut. The National Institute of Drug Abuses in the United States has shown that the purity of cocaine is even higher. Convincing users to stop their consumption because of a quality that is harmful to health is one of the areas of prohibitionism. In another form, the question of quality is also present in the alternative paradigm: risk reduction. Both positions are crossed by the debate on whether a purer drug is necessarily better for health or not.

Prohibition has not prevented, reduced or even controlled its consumption. The situation is quite similar in the United States, Europe or Latin America, where drugs have been naturalized, contributing to the socialization of young people. The latter may also be related to various forms of trafficking-related crime. This is a problem that affects Latin American slums, but not exclusively. Although there is a lack of accurate information on markets and consumption trends, in general terms, the profile of the consumer and the pattern of drug use have changed. The market is diversified 3 . In Argentina, alcohol, tobacco, synthetic drugs, "cheap" toxic substances such as ketamine, solvents and bases or paco 4 paste are consumed. In relation to users, diversification requires considering the differentiation -established by the World Health Organization -between use, abuse and dependence or between occasional or recreational users and drug addicts. Diversification also implies considering the difference in sensitivity compared to the drug user, the fact that while the social and generational boundaries of drug use are increasingly diffuse, judgment remains dependent on social representations that focus more on the user's profile than on use itself.

In the 21st Century, there is a less rigid consumption model that favors polyconsumption and raises the problem of overdose. This goes beyond the fact that the person who uses opiates or cocaine usually combines them with alcohol. Consumption patterns, especially in the upper and middle classes, are structured around the mixing of substances, and the search for novelties. In social events involving adolescents, prevailing consumption combines marijuana, psychotropic drugs, different types of alcohol and energy drinks.

From basic paste to methamphetamines, prohibition has opened the door to drugs, in some cases more toxic and at cheaper prices. It is not only what remains from processing. The drug market is highly diversified. With the efforts of governments still focused on combatting cocaine and marijuana trafficking, synthetic drugs have taken on a new dimension, not only because of their increasing importance in trafficking or the production of new substances. In Latin America, marijuana and cocaine have traditionally been the main focus of attention in the war against drug use. They now have to face the challenge of new substances. An increase in drug seizures reflects a rapid expansion. The use of amphetamine-type stimulants has increased among young people in countries such as Ecuador, Honduras and Venezuela, surpassing the use of marijuana or cocaine, and large ecstasy seizures have been made in Brazil and Argentina.

Synthetic drugs contribute to the diversification of a market that is changing at a rate faster than that detected by the authorities. As a fashionable phenomenon, production seeks to change the structures of synthetic drugs in order to impose new products, which has consequences for repression. When a component is modified, illegality disappears; it is a new drug not considered by legislation. In this way, producers can avoid being arrested on the grounds that, technically, they were not manufacturing or selling prohibited drugs. The realization is different: reforms are carried out to incorporate new substances into prohibited drug lists.

The normalization of drug use corresponds to a normalization of all manufacturing conditions and the marketing process. Drug trafficking has responded to repression with segmentation and tertiarization, the main consequences of which are primary changes in criminal structures. The subdivision of the cartels involved the end of the traditional model of criminal organization, i.e. an occult pyramidal structure, easily dismantled once identified. This change has consequences on the very essence of the military in the global disorder: the management of the control of legal and illegal flows and stocks. Small laboratories, "kitchens", have sprung up in houses in the slums, as well as in apartments in the centers of Latin American cities. This is a long way from the large laboratories of Mexican organizations in the 1990s. The stereotype of the trafficker is changing. The conditions under which synthetic drugs are manufactured contribute to this. The series Breaking Bad is revealing. The change in marketing methods implies a more obvious separation in the division of labor. This has consequences on probationary material. In Argentina, the bunker, as a physical sales space, is being transformed by adapting to market conditions. The development of delivery or Internet sales makes it easier to access goods. The days when consumers had to go to the outlying districts to buy supplies are somewhat over.

Militarization has had geopolitical consequences. It has encouraged the expansion and search for new cropland and the change of routing as a result of air traffic control. Air traffic is becoming less and less significant. Thus, in the case of Argentina, drugs circulate mainly by land, then by rivers, especially the Paraná. In the 21st Century, the expansion of production and transport areas goes beyond the traditional division of labor. While the relocation of production centers has reduced production in Colombia, it has increased in other countries, especially in the Andean region.

The war on drugs has created elements that destabilize the region. As Bill Clinton acknowledged, the policy towards Colombia has shifted the violence to Mexico. He admitted that the policy aimed at stopping maritime and air traffic from Colombia has led to changes in the geopolitics of drugs. Having always been a major focus of the Latin American agenda in Washington, Mexico has become a crucial issue in terms of its global security agenda. Since 2008, it has been compared to Pakistan. The United States of America's Latin American neighbor is pointed out by some opinion-formers -politicians, journalists, members of think tanks -as a country threatened with implosion, a "failed state", in which, for extreme positions, the US government should reserve the possibility, in the long term, of intervention. In 2010, Hillary Clinton referred to the existence of a "Colombianized" Mexico due to drug trafficking 5 . Mexico was, in her words, "looking more and more like Colombia looked 20 years ago". Obama must have put these statements into perspective. He considered Mexico as a vast democracy, with a growing economy and, as a result, it was not possible to compare it to what has previously occurred in Colombia6 .

The parallelism ignores, first, that Mexico has a state structure that comes from Benito Juarez and the Mexican Revolution, and second, that the ways in which violence has been conceived and spread are very different. In the case of Colombia, the cartels emerged and flourished in a society embedded in a politico-military conflict, in which non-state armed actors dared to challenge a weak state. In the case of Mexico, they emerged with the backing of a strong state, but eroded by corruption and the penetration of narco organizations into the political class and the Armed and Security Forces, and on the basis of cross-border circulation where the United States is a priority component through drug demand, small arms supply or money laundering.

In Mexico, drug trafficking has always involved a certain degree of violence. Military participation in the anti-narco fight has been active for a long time. The Mexican army was the first on the continent to get involved: since the late 1940s, increasing in the 1980s under the government of Miguel de la Madrid. However, in the 1980s and 1990s, Mexico's situation was not comparable to that of Colombia. The PRI's political hegemony established an order that made it possible to regulate drug trafficking through a series of more or less tacit agreements that guaranteed a level of violence that was tolerable by the political system and society. The end of the PRI's hegemony in 2000 with the triumph of Vicente Fox Quesada and Plan Colombia paved the way for a new cycle. Violence derived from drug trafficking was on the rise with Felipe Calderón and lead to a declaration of war on drug trafficking in 2006 as part of the Merida Initiative. The confrontation between the State and narcotics is combined with the struggle between the cartels and the action of paramilitary and/or self-defense groups. Violence is spreading socially and geographically and new issues, such as internal immigration, are emerging.

Militarization has also had social and environmental consequences. The repressive policies inherent in "war" have affected the exercise of rights: phone tapping, detention of people without a judicial warrant, increased administrative custom controls to prevent the free movement of people, penetration of individuals' privacy spaces, for example in the workplace, to determine whether a person has consumed a substance. The institutions have deteriorated as a result of this repressive policy and the corruption it generates, not only in Latin America. In Colombia, in 1999, the wife of a colonel attached to the US Embassy was arrested for drug trafficking7 and in April 2005, American soldiers involved in the war against drugs were arrested for cocaine trafficking. The war on drugs also has an ecological dimension, in particular with a significant impact on the environment, in particular fumigation actions. In 2015, the uselessness of the latter was recognized by the Santos government in Colombia. The decision to arrest them was supported by members of the US Congress8 .

The limits of a new era

In the 21st Century, oriented by failure, the emergence of a critical movement of the military approach to the problem characterizes the region. This movement is not necessarily linked to an ideological-political definition. Criticisms go beyond those traditionally leveled, which highlight both the strengthening of the policing role of the armies and the diversion of resources that could have been used to address factors contributing to trafficking in the region, such as farmers' poverty and corruption. The failure of the war is recognized by a large space. In 2009, the Latin American Commission on Drugs and Democracy, established by former presidents Fernando Cardoso, Ernesto Zedillo and César Gaviria, said that antinarcotic operations were not an effective method. It referred to the need to combat both supply and demand, to control use through prevention, treatment and education, and to decriminalize soft drugs9 . In addition, members of the US Congress regularly argue that more money invested translates into fewer results.

Gradually, on the continent, governments are resisting US drug policies, and are going even further by challenging traditional positions, such as prohibition, crop eradication, fumigation, repression of farmers or the use of bases for military purposes. The change shows both the failure of methods to combat drug trafficking and the decreasing influence of the United States on the region, as well as the consequent consolidation of a relative autonomy of Latin American states. However, the rejection of the war on drugs promoted by the United States does not necessarily translate into the disarticulation of prohibitionist logic. This refusal is as much a challenge to the policies pushed by the United States as it is an expression of the changes in addressing the issue.

The reappropriation of national sovereignty experienced by the neo-populist protesters has played a central role in this refusal. In a context where the influence of nationalism and anti-imperialism in the region is significant, sovereignty is expressed in drug policies. Very early on, there was rejection of Plan Colombia capsizing anti-drug policies to the questioning of the American presence on national territory. For his part, Correa questioned, soon after his victory, the American presence in Ecuador. The result was the non-renewal of the Manta base agreements and the inclusion in the 2008 Ecuadorian Constitution of a refusal to allow foreign interference with an explicit ban on military bases.

In 2009, Bolivian President Evo Morales expelled the DEA, claiming the traditional use of coca leaf, a cultural symbol in the Andean countries, while implementing regulations for this use. In addition, he defended a system that allows farmers to grow coca. However, not only did Morales not demand the legalization of cocaine and other drugs, he even went so far as to criticize them by putting forward "anti-imperialist" arguments. In 2016, as part of the US government's approval of the transnational drug trafficking law, which considers coca leaf as a controlled substance of classification, President Morales said on Twitter: "Bolivia is not a Yankee colony. The coca leaf represents the dignity and sovereignty of our ancient peoples in the Andean region." The law has generated concern among coca leaf producers.

As an expression of the change in the approach to the issue, the rejection of the repressive option was supported by countries in harmony with the hemispheric policies of hegemony. At the 2012 Cartagena Summit of the Americas, countries such as Mexico, Colombia, Guatemala and Uruguay proposed to the United States to establish a discussion on the legalization of soft drugs alongside the development of prevention and rehabilitation policies. Latin American practices are global perspectives that seek to move beyond the prohibitionist paradigm by considering the reasons why individuals use drugs or by trying to establish public health as a key area for understanding the drug problem and developing public policy.

In the context of an increasingly critical assessment of the 2009-2019 Action Plan, which focuses on all-out repression, the UN General Assembly Special Session in April 2016 aimed to mark a turning point in the approach to drug policy. The draft resolution, a non-binding document submitted to the vote of the Assembly, presented significant changes, with more emphasis on health and social issues. Far from the military response, the formulation of the drug problem in terms of health or society contributed to redefining the categories of political action.

The negative effects of prohibitionist policies have led to the search for alternatives, influenced by the debates around decriminalization or legalization. This has a major dimension in a continent where prohibitionism has prevailed, even though the impact in changing the social perception of the problem or in the measures taken in the field of public policies remains nuanced. With regard to marijuana, there is a willingness to experiment, mainly for medicinal use.

Alternative and progressive discourses are developing especially in the Southern Cone, where there is a social willingness to be able to revise legislation and produce new paradigms, even though legislative developments are slow. Criticism of prohibitionism considers that crime has benefited from it. Decriminalization should reduce the use of hard drugs and reduce crime. Yet, the consumption model of the population addicted to paco is not very appropriate for self-cultivation and cannabis clubs, designed on the cultural model of the middle classes.

Uruguay is the society most willing to hear the meaning of experimentation. This country has legislated on marijuana production, although differences within the Frente Amplio political coalition and state apparatus have made it difficult to implement. The slow implementation of the law speaks louder than bureaucratic obstacles; it reflects prejudices and moral positions. The logic of separating the market for hard and soft drugs, of which Holland was a pioneer, inspired the Mujica government in Uruguay to approve the law on the legalization of marijuana, arguing that drug users should not come into contact, via the marijuana black market, with other drug dealers.

In Argentina, although the influence of sectors defending responsible consumption and harm reduction such as the Argentine Harm Reduction Association remains limited, the progress made by consumers' applications for citizenship [START_REF]For example, the documents prepared by the Argentinean Harm Reduction Association "Si te detienen conoce tus derechos" (2005); "Que hacer si te detienen" (2011) or the Manual on Human Rights and Drug Use. Silvia Inchaurraga, Manual sobre derechos humanos y uso de drogas[END_REF] or by the introduction of the debate on the decriminalization of cannabis consumption or the legalization of cannabis use for medicinal use, even though this remains marginal and limited to investigation, shows a certain willingness to disable the punitive logic. Mauricio Macri's arrival in 2015 as part of a social demand for security was accompanied by a speech on the "war on drugs". The "Argentina without Drugs" Plan formulated by his government referred to "A World Without Drugs", proposed by the United Nations in 1998 and subsequently reformulated; these are statements with a very high level of generalization that reiterate ways of approaching the issue under the punitive logic of prohibitionism. The speech given as part of the presentation of the "Argentina without drug trafficking" program on August 30, 2016 is revealing 11 . The principles and objectives set out were identical to those of the 1991 decree of the Menem administration.

In December 2015, Colombia legalized by decree the use of cannabis for therapeutic purposes; permitted by a 1986 law, but without regulation. Brazil has approved a law that, in the case of recreational use, substitutes prison with measures such as community service or educational programs. However, with Jair Bolsonaro in power, the "war" is back. In Chile, the debate is also focused on the medicinal use of marijuana, although it remains marginal. The tendency to rethink prohibitionism also affects more socially conservative countries. Peru is an example of this. It argues that bilateral cooperation in the war against drug trafficking requires new programs to replace coca leaf cultivation and put in place a regulatory mechanism for traditional coca leaf use in 2011. As part of the policy to eradicate this crop, in 2012 coca was declared "part of the nation's national heritage" by the Peruvian government. In Guatemala, President Otto Pérez Molina had asked for a new policy and he was willing to create a legal market, regulated by the government, for some drugs in order to neutralize drug trafficking. He linked his dismissal to this policy. In Mexico, President Enrique Peña Nieto said he was open to alternative points of view, but without pushing the debate. In Mexico City, a progressive stronghold, attempts to decriminalize have failed. In 2016, the arrest of El Chapo rekindled the debate and decriminalization was promoted by members of López Obrador's party.

A temporary closure

In Latin America, since the end of the Cold War, drug trafficking, instituted as a major geopolitical issue, has become a major threat. At the heart of the reconfiguration of the military architecture in the region, it was, until 9/11, the main criterion for US intervention. With the militarization and the role of criminal organizations in strategic debates, drug trafficking is more a security issue than a public health issue. Approaching drug use as a pathology is practiced more by the criminal justice system than by the health care system. However, while drug trafficking is part of political discourse, it is rarely treated as a political actor or perceived as a power project. This is part of the failure in the struggle.

The results of the militarization of the war against drugs are negative. The effort to reduce the supply of illicit substances by means of repressive measures, both in the field of production and marketing, at the same time as the measures to penalize consumption, have not yielded results. Consumption has increased, the age of starting drug use has decreased and more dangerous drugs have developed. The market is also very diversified at the consumer level and a trend towards experimentation and polyconsumption is emerging. In relation to violence, this too has increased and goes far beyond Mexico. From the state of Guerrero in Mexico to the city of Rosario in Argentina, it is clear that prohibition cases kill more than drugs themselves12 . Militarization has had geopolitical, social and environmental consequences, from neighborhood conflicts in relation to US intervention, particularly in the context of Plan Colombia, to the expansion of production and transport areas, corruption of the security force and the judicial system, pollution linked to defoliants, the strengthening of security discourse and the allocation of rights. The limits of the military option are not reduced to Latin America; as Afghanistan, a major producer of cannabis and opium under the occupation of prohibitionist countries, illustrates.

The failure explains, to a large extent, the innovations experienced across the American continent in the discourse on the need to reformulate the way the drug problem is addressed and, to a lesser extent, in public policies and social practices. The issue of decriminalizing the use or legalizing the use of cannabis for medicinal purposes crosses the Americas with varying results. Latin American experiences with drugs are constitutive of the glocal, they connect local and global scales, being part of the international debate on the subject that includes the United States. However, if in general terms, the visibility of the prohibitionist movement in the public arena has weakened, repressive policies prevail. The hegemony of this thinking emerges less from the continuity of arbitrary arrests or the use of false evidence by security forces, particularly against popular sectors, than from the fact that the prohibitionist's own assumption that drug use is harmful to everyone and everywhere has won the cultural battle.

  MANERO, Edgardo, « The Lost War: the Prohibition of Impossible Drugs, Public Policies and Social Practices in Latin America in the 21st Century » in Living with Drugs, A. Stella et A. Coppel (sous la direction de), ISTE Press/Elsevier, London/Oxford, 2020, p. 187-199, ISBN 978-1-78548-317-2 Version auteur (sans mise en page éditeur).

Tokatlian, Juan Gabriel (comps) (2010). Drogas y prohibición. Una vieja guerra, un nuevo debate. Libros del Zorzal, Buenos Aires.

See Primer Estudio Nacional en Pacientes en Salas de Urgencia del país, SEDRONAR, December 2003; Estudio sobre consumo de sustancias psicoactivas en niñas, niños y adolescentes en situación de calle, Observatorio Argentino de Drogas, SEDRONAR, 2005; Estudio nacional en población de 12 a 65 años, sobre consumo de sustancias psicoactivas, SEDRONAR, 2006; Tercera Encuesta Nacional a estudiantes de enseñanza media, Observatorio Argentina de Drogas, SEDRONAR, 2007; Observatorio de la Deuda Social, dependiente de la Universidad Católica Argentina. Barómetro del narcotráfico y las adicciones en la Argentina informe N° 3 -año 2016. Venta de drogas y consumos problemáticos. una aproximación diagnóstica a las adicciones en jóvenes de barrios vulnerables barómetro del narcotráfico y las adicciones en la Argentina. http://www.uca. edu.ar/uca/common/grupo68/files/2017-Observatorio-Informe-3-Narcotrafico-Addiciones-Venta-Drogas-y-Consumos-Problematicos.pdf.

4 Usually confused with crack and misnamed as a paste base, paco is an intermediate product in the manufacture of cocaine hydrochloride involving toxic solvents. In Argentina,

El Universal, 9/9/2010.

See http://www.oem.com.mx/laprensa/notas/n1777236.htm.

L'Express, 25/4/2005.

El Tiempo, 14/5/2015.

Declaración de la comisión latinoamericana sobre drogas y democracia, Drogas y democracia: hacia un cambio de paradigma, http://www.drogasedemocracia.org/ arquivos/livro_espanhol_04.pdf.

In 2016, Mexico was the second deadliest country in the world after Syria. Le Monde, 10/05/2017.