RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates
Authors: Laurent Condat
Peter Richtárik
Venue: ICLR 2023 poster (2023)
Keywords: optimization
randomized algorithm
stochastic algorithm
proximal splitting
proximity operator

Abstract: Proximal splitting algorithms are well suited to solving large-scale nonsmooth optimization problems, in particular those arising in machine learning. We propose a new primal–dual algorithm, in which the dual update is randomized; equivalently, the proximity operator of one of the function in the problem is replaced by a stochastic oracle. For instance, some randomly chosen dual variables, instead of all, are updated at each iteration. Or, the proximity operator of a function is called with some small probability only. A nonsmooth variance-reduction technique is implemented so that the algorithm finds an exact minimizer of the general problem involving smooth and nonsmooth functions, possibly composed with linear operators. We derive linear convergence results in presence of strong convexity; these results are new even in the deterministic case, when our algorithms reverts to the recently proposed Primal–Dual Davis–Yin algorithm. Some randomized algorithms of the literature are also recovered as particular cases (e.g., Point-SAGA). But our randomization technique is general and encompasses many unbiased mechanisms beyond sampling and probabilistic updates, including compression. Since the convergence speed depends on the slowest among the primal and dual contraction mechanisms, the iteration complexity might remain the same when randomness is used. On the other hand, the computation complexity can be significantly reduced. Overall, randomness helps getting faster algorithms. This has long been known for stochastic-gradient-type algorithms, and our work shows that this fully applies in the more general primal–dual setting as well.

Published as a conference paper at ICLR 2023
RANDPROX: PRIMAL-DUAL OPTIMIZATION ALGO- RITHMS WITH RANDOMIZED PROXIMAL UPDATES
Laurent Condat & Peter Richtárik
Visual Computing Center
King Abdullah University of Science and Technology (KAUST)
Thuwal, Kingdom of Saudi Arabia
Contact: https: hittps://ccondatt github.
ABSTRACT
Proximal splitting algorithms are well suited to solving large-scale nonsmooth optimization problems, in particular those arising in machine learning. We propose new primal-dual algorithm, in which the dual update is randomized; equivalently, the proximity operator of one the function in the problem is replaced by a stochastic oracle. For instance, some randomly chosen dual variables, instead of all, are updated at each iteration. Or, the proximity operator a function is called with some small probability only. A nonsmooth variance-reduction technique is implemented so that the algorithm finds an exact minimizer of the general problem involving smooth and nonsmooth functions, possibly composed with linear operators. We derive linear convergence results in presence of strong convexity; these results are new even in the deterministic case, when our algorithms reverts to the recently proposed Primal- -uall Davis-Yin Yin algorithm. Some randomized algorithms the literature are also recovered as particular cases (e.g.. Point-SAGA) But our randomization technique is general and encompasses many unbiased mechanisms beyond sampling and probabilistic updates, including compression. Since the convergence speed depends the slowest among the primal and dual contraction mechanisms, the iteration complexity might remain the same when randomness is used. On the other hand, the computation complexity significantly reduced. Overall, randomness helps getting faster algorithms. This has long been known for ppchastic-gradient-yy algorithms, and work shows that this fully applies in the more general primal-cual setting as well.
be
INTRODUCTION
Optimization problems arise virtually
quantitative fields, including machine learning, data
science, statisties, and many other areas (Palomar & Eldar 2009 Sra et al. 2011 Bach al.
2012 Cevher et al., 2014, Polson et al. [015) Bubeck 2015: Glowinski et al.] 2016: Chambolle
Pock 2016 Stathopoulos et al. 2016). In the big data era, they tend be very high-dimensional, and first-order methods are particularly appropriate to solve them. When a function is smooth, an optimization algorithm typically makes calls to its gradient, whereas for nonsmooth function, its proximity operator is called instead. Iterative optimization algorithms making use of proximity operators are called proximal (splitting) algorithms (Parikh & Boyd 2014). Over the past 10 years or so, primal-dual proximal algorithms have been developed and are well suited for a broad class of large-scale optimization problems involving several functions, possibly composed with linear operators (Combettes & Pesquet 2010: Bot et al. [0014] Parikh & Boyd, 2014 Komodakis & Pesquet 2015 Beck 2017]
Condat et al. 2023a Combettes Pesquet, 2021 Condat al. 2022c).
However, in many situations, these deterministic algorithms are too slow, and this is where ran- domized algorithms come to the rescue; they are variants of the deterministic algorithms with a cheaper iteration complexity, obtained by calling random subset, instead of all, of the operators or updating a random subset, instead of all, of the variables, at every iteration. Stochastic Gradient
Descent (SGD)-type type methods (Robbins & Monro. 1951 Nemirovski al.) 2009 Bottou, 2012 Gower et al. 2020; Gorbunov et al., 2020; Khaled et al. 2020b) are a prominent example, with the huge success we all know. They consist in replacing call the gradient of function, which

---

Published as a conference paper at ICLR 2023
can be itself sum expectation of several functions, by cheaper stochastic gradient estimate. By contrast, replacing the proximity operator of possibly nonsmooth function by a stochastic proximity operator estimate is a nearly virgin territory. This is important challenge, because many functions of practical interest have a proximity operator, which is expensive to compute. We mention the nuclear norm of matrices, which requires singular value decompositions, indicator functions of sets on which it is difficult to project, or optimal transport costs (Peyré & Cuturi 2019).
In this paper, we propose RandProx (Algorithm 2), a randomized version of the Primal-Dual Davis- Yin (PDDY) method (Algorithm 1), which is proximal algorithm proposed recently (Salim et al. 2022b) and further analyzed in Condat et al.] (2022c). In RandProx, one proximity operator that appears in the PDDY algorithm is replaced by a stochastic estimate. RandProx is variance-reduce (Hanzely Richtárik, 2019. Gorbunov al.] 2020; Gower et al., 2020); that is, through the use of control variates, the random noise is mitigated and eventually vanishes, so that the algorithm converges to an exact solution, just like its deterministic counterpart. Algorithms with stochastic errors in the computation of proximity operators have been studied, for instance in Combettes & Pesquet (2016), but the errors are typically assumed to decay or some stepsizes are made decaying along the iterations, with a certain rate. By contrast, in variance-reducee algorithms such RandProx, which has fixed stepsizes, error compensation is automatic.
We analyze RandProx and prove its linear convergence in the strongly convex setting, with additional results in the convex setting: we leave the nonconvex case, which requires different proof techniques, for future work. We mention relationships between results and related works in the literature throughout the paper. In special cases, RandProx reduces to Point-SAGA (Defazio 2016), the Stochastic Decoupling Method (Mishchenko & Richtárik 2019), ProxSkip, SplitSkip and Scaffnew (Mishchenko et al. (022), and randomized versions of the PAPC (Drori et al. 2013). PDHG (Chamoolle & Pock 2011) and ADMM (Boyd al., 2011) algorithms. They are all generalized and unified within our new framework. Thus, RandProx paves the way to the design of proximal counterparts variance-reduue SGD--type algorithms, just like Point-SAGA (Defazio 2016) the proximal counterpart of SAGA (Defazio et al. 2014).
PROBLEM FORMULATION
Let X and be finite-dimensional real Hilbert spaces. We consider the generic convex optimization problem:
Find x² arg min (s(x) +)(())+++)))))))))))())) + h(Kx)),
=EX
where K : X - 24 is a nonzero linear operator; f is a convex L, -smoohh function, for some L, 0: that is, its gradient V f Ly-Lisschitz continuous (Bauschke & Combettes 2017, Definition 1.47); and g X + R U {+oo} and h : U + IR (+oo are proper closed convex functions whose proximity operator easy to compute.
We will assume strong convexity of some functions: a convex function & is said to be Py-Strongly convex, for some Pe 2 0, if Φ merely convex.
||2 is convex. This covers the case tég = 0, in which & is
2.1 PROXIMITY OPERATORS AND PROXIMAL ALGORITHMS
We recall that for any function & and parameter 7 > 0, the proximity operator of y is (Bauschke & Combettes 2017) 7): prox x E X + arg min,' (To((x') ( 1 -x(]) 21 This operator has
closed form for many functions of practical interest (Parikh & Boyd 2014, Pustelnik & Condat 2017]]
Gheche al. 2018), see also the website http: http::/proxxmiiimm wtwp:emmmtttopprtotttooo
operator............... net In addition,
the Moreau identity holds:
prox (x) = x prox (//()))
where の² 1 X + sup ((r, xx) - o(x')) denotes the conjugate function of ø (auuschke &
Combettes 2017). Thus, can compute the proximity operator of from the one of o², and conversely.
2

---

Published as a conference paper at ICLR 2023
Proximal splitting algorithms, such the forward backward and the Douglas Rachford algorithms (Bauschke & Combettes 2017). are well suited to minimizing the sum, f + g or + h in our notation, of two functions. However, many problems take the form ① with K * ld, where Id denotes the identity, and the proximity operator of h o K is intractable in most cases. A classical example the total variation, widely used in image processing (Rudin et al. 1992; Caselles al. 2011 Condat 2014: 2017) or for regularization on graphs (Couprie et al. 2013), where / is some variant of the ε norm and K takes differences between adjacent values. Another example is when is the indicator function of some nonempty closed convex set Ω C Ut; that is, h(u) (0 if u 22 +oo otherwise). in which case the problem can be rewritten as
Find x² E arg min (f(z) ((()) s.t. K E Ω. aex
If g 0 and Ω {b} for some E (an(K), where ran denotes the range, the problem can be further rewritten as the linearly constrained smooth minimization problem
Find x² E arg min f(x) s.t. = Kr=b.
This last problem has applications in decentralized optimization, for instance (Xin et al. 2020 Kovaley al., 2020; Salim et al. 2022a). Thus, the template problem (I) covers wide range of optimization problems met in machine learning (Bach et al.) 2012] Polson et al. 2013), signal and image processing (Combettes & Pesquet 2010 Chambolle & Pock (016),, control (Stathopoulos et al. (016)). and many other fields. Examples include compressed sensing (Candès et al.) (006). object discovery in computer vision (Vo al. (2019), trend filtering (Kim al.| group lasso
(Yuan & Lin 2006), square-root lasso (Belloni et al. 2011). Dantzig selector (Candès & Tao 2007
and support-vector machines (Cortes & Vapnik 1995).
2.2
THE DUAL PROBLEM, SADDLE-POINT REFORMULATION AND OPTIMALITY CONDITIONS
In order to analyze algorithms solving such problems, introduce the dual problem to |I
Find u' E arg min (I+ (-+"
(2)
well
where K* :4 > X' is the adjoint operator of K. We can also express the primal and dual problems as combined saddle-point problem:
Find (x", u²) E arg min max #EX well
(f(z) + g(x) + (Kx, u) h² (w))
(3)
For these problems to be well-posed, we suppose that there exists x² E X' such that
0E Vf(=)) 0g(x*) K" K*ah
where (--) denotes the subdifferential [Bauschke Combettes 2017). By Fermat's rule, every x² satisfying (4) is solution (I). Equivalently to (4), suppose that there exists (x* u²) X x 21 such that
{
0 V f((=**)))) + 0g(x=)))))) + K*u
o Kx + 0h (u*)
(5)
Every (x*, u*) satisfying (5) is primal-daa dimall-dull solution pair; that is, x² is solution to I u² is solution to and (x", u ) is a solution
PROPOSED ALGORITHM: RandProx
There exist several deterministic algorithms for solving the problem [ see Condat et al. (003aa) for recent overview. In this work, focus on the PDDY algorithm (Algorithm 1) (Salim et al.) 20226; Condat et al. 2022c). particular, our new algorithm RandProx (Algorithm 2) generalizes the PDDD algorithm with stochastic estimate of the proximity operator of h².
3

---

Published as a conference paper at ICLR 2023
Algorithm PDDY algorithm
Algorithm 2 RandProx
(Salim et al. 20226)
[new]
input: initial points S² X, w eu: stepsizes 7 > 0, 7 > 0
input: initial points x E X, v El:
stepsizes 7 > 0, T > 0:
o" = K'u'
r = K'u"
for t 0, s.l....du do
for t 0, 0.., do
E' = prox yg (x*
7 7V fxx") - 700))
a' = prox,g (xt
(x*)) - 70")
" "1+ = 7
(u' + 7 kāt)
u u¹ + 14w
R² (prox= (u' +TK.) u²)
d'1 : K²u kttutt
re1 = k"u't1
x++1 (((t1 1911-19 -0)
x(+1 == st + w) (vlt1 - -v0)
end for
end for
3.1 THE PDDY ALGORITHM
We recall the general convergence result for the PDDY algorithm (Condat et al. 2022c Theorem 2):
I (0.2/L T> Ty < 1, then (x" (ee)Len converges a primal solution solutiin x² of and (u') JEEN converges to a dual solution u² of (2)
The PDDY algorithm is similar and closely related to the PD30 algorithm Yan 2018 as discussed
in Salim et al. (2022b); Condat et al. (022c). It is also an instance (Algorithm 5) of the Asymmetric Adjoint (AFBA) framework of Latafat & Patrinos) (2017). We note that the
popular Condat-Vū algorithm (Condat 2013 Vū 2013) can solve the same problem but has more restrictive conditions on y and т.
In the PDDY algorithm, the full gradient V can be replaced by stochastic estimator which is typically cheaper to compute (Salim et al.) 2022b). Convergence rates and accelerations the PDDY algorithm, well distributed versions of the algorithm, have been derived in Condat al. (2022c). In particular, if μ > 0 or Hg > 0, the primal problem ( is strongly convex. In this case, a varying stepsize strategy accelerates the algorithm, with a (11(²²) decay of || - x x=12 where x is the unique solution to ( But strong convexity of the primal problem is not sufficient for the PDDY algorithm to converge linearly, and additional assumptions on h and K are needed. We will prove linear convergence when both the primal and dual problems strongly convex; this is natural condition for primal-dus dual algorithms.
We note that h is L,, -moothh for some Ln > O, if and only if ht" is -troongy convex, for some [4h- > O, with jA = 1/L,. In that case, the dual problem (2) is strongly convex.
3.2 RANDOMIZATION MECHANISM FOR THE PROXIMITY OPERATOR OF h*
We propose RandProx (Algorithm 2). a generalization of the PDDY algorithm (Algorithm with randomized update of the dual variable u. Let us formalize the random operations using random variables and stochastic processes. We introduce the underlying probability space (S, F. P). Given real Hilbert space H. an H-valued random variable is a measurable map from (S.F) to (H, BB). where is the Borel r-algebra of H. Formally, randomizing some steps in the PDDY algorithm amounts to defining ((x", a²)) IEN as stochastic process, with x² being X'- random variable and u² -fllude random variable, for every t 2 0. We use light notations and write our randomized algorithm RandProx using stochastic operators R2 on Zt; that is, for every 2 0 and any rd U, R² (r**) is a U/-valued random variable, which can be interpreted as r² plus 'random noise' (formally, rf is itself a v--valeed random variable, but algorithmically, RR is applied to particular outcome in U4 hence the notation as an operator on L/). To fix the ideas, let us give two examples.
Example 1.
The first example is compression AAlistar et al. 2017 2018: Horváth et al. 2022 Mishchenko et al.) 2019 Albasyoni et al., 2020 Beznosikov et al. 2020 Condat et al. (022b):
U = R for some R' multiplies & coordinates, chosen uniformly at random, of the vector r' by d/k and sets the other zero. An application to compressed communication is discussed in Section A.3
and R' is the well known rand-k compressor or sparsifier, with 1 < k < d:
4

---

Published as a conference paper at ICLR 2023
Example 2. The second example, discussed in Section A.1 is the Berouuli,, or coin flip, operator
with probability p, with probability p.
R¹
(6)
for some > O. In that case, with probability p. the outcome of R (r') is 0 and r" does not need be calculated; particular, the RandProx algorithm, prox,*- can expect the iteration complexity of RandProx to decrease. Thus, in this example, R*(r") does not really consist of applying the operator R' r"; in general, the notation R2(r") simply denotes a stochastic estimate of r-.
called, and this why one
Example 3. The third example, discussed in Section A.2 is sampling, which makes possible to solve problems involving a sum Σi= f; of functions, by calling the proximity operator of only one randomly chosen function h, instead of all functions, at every iteration. The Point-SAGA algorithm Defazio 2016) is recovered as a particular case of RandProx in this setting.
Hereafter, we denote by Fr the a-algebra generated by the collection of (X' x U/)-vlled random variables (x x.)..... (x', u²), for every t 2 In this work, we consider unbiased random estimates: for every 2 0,
E R (r²)
Fi =r²;
where [-]] denotes the expectation, here conditionally on Ft, and re the random variable
r' prox-k- (u' TK**) =u
as defined by RandProx. Note that our framework is general in that for + be independent nor have the same law. In simple words, at every iteration, the randomness is new but can have a different form and depend on the past, that the operators R2 can be defined dynamically on the fly in RandProx.
+ t', R' and RD need not
We characterize the operators R2 by their relative variance w 2 such that, for every 2 O,
E [R'(
-111
F w ||:"
This assumption is satisfied by large class of randomization strategies, which are widely used to define unbiased stochastic gradient estimates. refer to Beznosikov et al. (2020), Table 1 in Safaryan et al. (2021) Zhang et al. (2023). Szlendak al. (2022) for examples. In the Example I The value
I. In Example 3, w = n of w is supposed known and used in the RandProx algorithm. Note that w = 0 if and only R² Id, in which case there is no randomness and RandProx reverts the original deterministic PDDY algorithm.
above rand-k, ~ - In Example 2, w
Thus, = + +e', with the variance of the error e' proportional to ||r"1] In particular, if re there is no error and R'( = 0. The stochastic operators RR will be applied to a sequence of random vectors that will converge to zero, and hence the error will converge to zero as well, due to the relative variance property 77). RandProx therefore a variance-reduced method (Hanzely & Richtárik Gorbunov et al. 2020 Gower et al. 2020); the random errors vanish along the iterations and the algorithm converges to an exact solution the problem.
To characterize how the error the dual variable propagates the primal variable after applying K we also introduce the relative variance Wyan 2 in the range K* and the offset Ç E [0, 1] such that, for every 2
B ([(K-(R'()) 1l [i]] wran ||r+ <||
(8)
It is easy to that 8 holds with Wran |||| Pw and 0. this is the default choice without particular knowledge on K*. But in some situations, e.g. sampling like Section A.2 a much smaller value of wran and positive value of ( can be derived.
5

---

Published as a conference paper at ICLR 2023
3.3 DESCRIPTION OF THE ALGORITHM
Let us now describe how the PDDY and RandProx algorithms work. An iteration consists in 3 steps:
1. Given x' and u², the updated value of the primal variable is predicted to be #t
2. The points & and u' are used to update the dual variable to its new value wf+1.
3. The primal variable is corrected from Ie to xf+1, by propagattgggn the difference ut+1 u' using K*
In RandProx, randomization takes place in Step 2. On average, this decreases the progress from u' to u²+1, and in turn from z to x in Step 3, but the progress from z" to 2 due to the unaltered proximal gradient descent step in Step progress speed the primal and dual variables, depending on the relative computational complexity of the gradient and proximity operators. The random enrors are kept under control and convergence is ensured using underrelaxation: let us define, for every 1. 2 O,
kept. Therefore, randomization can be used to balance the
a'+l = - (u' + +KK)).
The PDDY algorithm updates the dual variable by setting u²+1 +1 = a++1. In RandProx, let us define
= u' + R2 ( w²) = al+1 +e
for some zero-mean random error e², keeping in mind that a++1 typically cheaper to compute than a--1, Then underrelaxation is applied: we set
u pūt+1 +11 - p)u'
(10)
for some relaxation parameter P (0, 1];
p p= 14 in the algorithm. That is, the update
of the dual variable consists a convex combination of the old estimate u' and the new, better in expectation but noisy, estimate if+1, Noise is mitigated by underrelaxation, because the error ef is multiplied by p. so that variance multiplied by p². So, even if arbitrarily large, wp? is kept small. Underrelaxation slows down the progress on the dual variable of the algorithm towards the solution, but the iterations become faster, this beneficial overall.
CONVERGENCE ANALYSIS OF RandProx
Our most general result, whose proof is in the Appendix, the following:
Theorem Suppose that μy 0 or By > O, and that pa- In RandProx, suppose that 7 2, >> and yJ ((1 - || Wran) S where Wran and are defined in { For
every 2 0. define the Lyapunov function
T := 1111 - x-
+ (1+ ( 2pm--) I|ue - u² 1=
2
(11)
where x" and nt are the unique solutions to and 2 respectively. Then RandProx converges linearly: for every 0,
E S <c'pp
(12)
where
c max (1
(11 72 1 1)2 .1 (1 + w) + 2Tpx)) ) <1.
2T
(13)
1 + 1 7Mg
1+70g
Also, )eN and (a*) reN) both converge to and (E') converges to u², almost surely.
In Theorem 1, i S in that case the rate e in 113 satisfies
L, we have max(1 - 7H 1)2 = =(1 -1- 741)
2
< -1-774)
7/4 so that
(7(My + 1b)
2T
< 1 min
1
1 74g
(1 + w) + 2T
'The condition 7
2. given for simplicity. Larger values of be used when Hy long
T.
1 in 13

---

Published as a conference paper at ICLR 2023
Table I: The different particular cases of the problem ① for which derive an instance of RandProx,
with the number of the theorem where its linear convergence is stated, and the corresponding condition
on and K. is a shorthand notation for Amin (K K') and 2(b) + (0 if x b, +o0 otherwise).
Deterministic
Randomized
Condition ensuring linear convergence
h
K
Theorem
algorithm
algorithm
any
any
any any any Id
any
PDDY
RandProx
10,- > 0 P4 > 0 A>
any
PAPC
RandProx
2
any
any
forward- barward-bckwward (FB)
RandProx-FB
any
A(b)
any any Id
PAPC
RandProx-LG
any
any
Chambolle-Pode Pock (CP)
RandProx-CP
7
0
any
ADMM
HandProx-ADMin
8
BA. > 0
any any any Id Davis Yin (DY)
RandProx-De DY
Remark 1 (choice T) Given 7, the rate e in (3) 3 is smallest if is largest. So, there seems to be no reason to take | + Wrea) 1, and Ty K] + Wran) 1 should be the best choice in most cases. Thus, one can set 500 701-0) F and keep 7y as the only parameter to tune in RandProx.
In the rest of this section, discuss convergence guarantees than in Theorem for RandProx. Other particular cases are studied in the Appendix; for instance, an instance of RandProx, called HandProx-ADMM. is randomized version of the popular ADMM (Boyd et al. 2011). The different particular cases are summarized in Table
particular cases of ( for which derive stronger
4.1 PARTICULAR CASE
In this section, we assume that g = O. Then the PDDY algorithm becomes an algorithm proposed for least-squares problems (Loris & Verhoeven 2011) and rediscovered independently as the PDFP2O algorithm (Chen et al. 2013) and as the Proximal Alternttnn Predictor-Correett (PAPC) algo- rithm (Drori et al. 2015): let us call it the PAPC algorithm. It has been shown to have primal-dual
forward-backwar structure (Combettes et al. 2014). Thus, when = O, RandProx is a randomized version of the PAPC algorithm.
We note that f is strongly convex, which is not the case of (f + +g) in general. Let us define Aminn (K (*) as the smallest eigenvalue of KK* Amin (KK*) > if and only if ker(K*) {0). where ker denotes the kernel. If Amnn (KK)" > 0, (-K- is strongly convex. Thus, when = 0,
Auin (K K*) 0 and A4-- > 0 are two sufficient conditions for the dual problem ( to be strongly convex. We indeed get linear convergence of RandProx in that case:
Theorem 2. Suppose that g 0. μ O, and that Amin (KK*) 0 PA. >> 0. In RandProx. 2 suppose that 0 < 7 T.y" 0 and yr yr((1 [)] K| + Wran) I 1. Then RandProx converges linearly: for every 2 0, [| < d where the Lyapunov function dit is defined in and
c= cm= max (1- 112,1- 2T + Ammmi (KK))
< 1.
(14)
(1 (++ 2T
Also, (x')LeN and (it)EN both converge to x² and (u')EEN converges to u², almost surely.
When R' Id and w wran 0, RandProx reverts to the PAPC algorithm. Even this particular case, Theorem 2 proves linear convergence of the PAPC algorithm and is new. In In(Chen et al. (2013 Theorem 3.7), the authors proved linear convergence of an underrelaxed version of the algorithm: underrelaxation slows down convergence. In Luke & Shefi (2018), Theorem I is wrong, since it is based on the false assumption that Amiu (K,K;) > 0 for linear operators K;, -...., P. then Amin [K K*) > O, with K + (Kιæ,... K2z). Their theorem remains valid when p 1, but their rate is complicated and worse than ours.
We now consider the more particular consist in minimizing fx) + h((z) and f"(-u) (-w) + h (u). respectively. The dual problem is strongly convex and has unique solution u" -V (xx") ), for any primal solution st. By setting := 1/7
of 0 and K Id. Then the problems 1 and
7

---

Published as a conference paper at ICLR 2023
Algorithm 3 RandProx-FB [new]
Algorithm 4 RandProx-LO [new]
input: initial points z² X, w e:;
input: initial points x² E X, u E
stepsize 0; w 2 0 for t 0, 1....... do
stepsizes 7 1 = K*u u
0, 0; w 2 0
2 = x² - VV)((² yuu
for /. 0, 1, ,... do
d' = (a' (1+)) (ot 7(1 ww)u))
1² = - f(x') gp
n²+1 = u² 1t
RR (Kt - 6)
u+11 w' + mitwy
u't1 = Ktutt
x = st 14w"
xt = ft - 71(1 + (wtt - -at)
end for
end for
(FB), algorithm, which iterates r²+1 prox,h (x* (>*))) Thus, when randomness is introduced, we set Wran = w, Ç == and, according to Remark 1, T == マ[+サ RandProx. By noting that, for every a 0, the abstract operators R' and aR' (1 have the same properties, can put the constant 7(1 w) outside R' to simplify the algorithm, and rewrite RandProx RandProx-FB, shown above. As a corollary of Theorem 2, we have:
in the PAPC algorithm, we obtain the classical proximal gradient, a.k.a.
Theorem 3. Suppose that μy > 0. In RandProx-FB, suppose that 0 < 2, For every 2 0. define the Lyapunov function
x² - x-1 1-'=
(1 (1+ ( + +w + 2pmn-) ||ul 1²1
(15)
where x² is the unique minimizer of I and u² = - VV (x*) is the unique minimizer of (- Then RandProx-FB converges linearly: for every 2 0,
E [[ S c'
where
1+ pm
max (L-TH1),, 1)2
(16)
(1 + w) + Fpm=
Also, (o')eer and (+*) both converge to and (ul) yen converges to u², almost surely.
It is important to note that it is not necessary to have μa. > 0 in Theorem 3. If we ignore the properties of h² the third factor in (16) can be replaced by its upper bound (1+=)*
4.2 LINEARLY CONSTRAINED SMOOTH MINIMIZATION
Let b E ran(K). In this section, we consider the linearly constrained (LC) minimization problem
Find x² E arg min f(x) s.t. Kr b,
(17)
which is particular case of I with 9 = and h
+ (0 if b, 400 otherwise). We have htt E 24 - (u, b) and prox u E 44 - rb. The dual problem to (17) is
Find n* E arg min (5 (f*(K (u.
(18)
well
We denote by u the unique solution to 18) in ran(K). Then the set of solutions of (18) is the affine subspace up + ker(K*) (*). Thus, the dual problem is not strongly convex, unless ker K = {0}. Yet, will see that strong convexity of f is sufficient to have linear convergence of RandProx, without any condition on K.
We rewrite RandProx in this setting RandProx-LC, shown above. We observe that u' does not appear in the argument of R' any more, so that the iteration can be rewritten with the variable v = K and u' can be removed if we interested in estimating dual solution. In any case,
8

---

Published as a conference paper at ICLR 2023
denote by (r)((K) the orthogonal projector onto ran(K) and by Ami (KK*) > 0 the smallest nonzero eigenvalue of KK* Then:
Theorem 4. In the setup
17
18 suppose that μu > O. In RandProx-LC, suppose that 0 < < 2
T.y' 0 and yT ((1 () 2 + Wran) I 1. Define the Lyapunov function, for every 2 0,
1 1|00- xx112 1 | - |ubl=
v' =
(19)
where u/ = Pran(K) (K) (a²) ) is also the unique element in ran K) such that vf = K K x' is the unique solution of (17) and up is the unique solution in ran K) of 18) Then RandProx-LO converges
linearly: for every 2 0,
B[v"] S ct
where
max (1- (1-7 1)?, YT (KK*)
<1
(20)
1
Also, (x')ee and (+*) )eeN both converge to and (ub)ten converges to uhg almost surely.
Theorem 4 is new even for the PAPC algorithm when w = 0: its linear convergence under the stronger
condition yr ||| <
has been shown in Salim al. (2022b) Theorem 6.2), but our rate in (20
better.
We further discuss RandProx-LC, which can be used for decentralized optimization, in the Appendix. Another example of application is when X' = Rd, for some d 2 1, and K is matrix; one can solve
17 by activating one row K chosen uniformly at random at every iteration.
CONVERGENCE IN THE MERELY CONVEX CASE
In theorems, strong convexity f or is assumed; that is, fy > 0 or Mg > O. this section, we remove this hypothesis, so that the primal problem is not necessarily strongly convex any more. But ff(*") is the same for every solution x* of ( and we denote by ff(x*) this element.
We define the Bregman divergence of points (x, X²2 as
(y(ex'') f(x)
f(x)) -(a) -
For every 2 0, D (x' ) is the same for every solution xx of I and we denote by D (x",, xx)) this element. D (z x²) can be viewed as generalization of the objective gap f(x') f(x") the case when V/(=*) * 0. Dy(x', xx" is loose kind of distance between x!' and the solution set, but
under some additional assumptions on f. for instance strict convexity, D x²) + implies that
the distance from x² to the solution tends zero. Also, D, (x',z*) x²) 2 24 -ff(x=)VV(() I1
so that (z x²) 0 implies that (V'()') IEN converges to Vf(xx).
Theorem 11. In RandProx, suppose that 0 < T 0, and 7: ((1 () K1|2 + Wran) S 1.
Then Dy(a', x²) + almost surely and in quadratic mean. Moreover, for every 0, we define
xt = F+1 Dt Ei x.. Then, for every i O,
D
E E[Dy (x' x 2²)]
(2 - (t O(1tt)
(21)
If. in addition, ph- quadratic mean.
0, there is a unique dual solution ut to and (u hex converges to u", in
We can derive counterparts of the other theorems the same way. These theorems apply to all algorithms presented in the paper. For instance, Theorem 11 applies Scaffnew (Mishchenko et al.) 2022), a particular case of RandProx-FL seen Section A.3 and provides for the first convergence results in the non-strongly convex case.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The work of Richtárik was partially supported by the KAUST Baseline Research Fund Scheme and by the SDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence.
REFERENCES
A. Albasyoni, M. Safaryan, L. Condat, and Richtárik. Optimal gradient compression for distributed and federated learning. preprint arXiv:2010.03246, 2020.
D. Alistarh, D. Grubie, J. Li, R. Tomioka, and M. Vojnovic. QSGD: Communication--ficiinnn SGD via gradient quantization and encoding. In Proc. of 31st Conf. Neural Information Processing Systems (NIPS). pp. 1709-1720, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, and C. Renggli. The convergence of sparsified gradient methods. In Proc. of Conf. Neural Information Processing Systems (NeurIPS), 2018.
F. Bach, R. Jenatton, J. Mairal, and G. Obozinski. Optimization with sparsity-inducing penalties. Found. Trends Mach. Learn., 4(1): 1106,-106, 2012.
D. Basu, D. Data, C. Karakus, and S. N. Diggavi. Qsparse-Local-SGD. Distributed SGD With Quan- tization, Sparsification, and Local Computations. IEEE Journal on Selected Areas in Information Theory, 1(1::217-226, 2020.
H. H. Bauschke and P. L.. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York, 2nd edition, 2017.
A. Beck. First-Orler Methods in Optimization. MOS-SIAM Series on Optimization. SIAM, 2017.
A. Belloni, V. Chernozhukov, and L. Wang. Square-root lasso: pivotal recovery of sparse signals via conic programming. Biometrika, 98(4):791-806, 2011.
D. P. Bertsekas. Convex optimization algorithms. Athena Scientifie, Belmont, MA, USA, 2015.
A. Beznosikov, S. Horváth, P. Richtárik, and M. Safaryan. On biased compression for distributed learning. preprint 2iti::0002.221100 2020.
R. I. Bot, E. R. Csetnek, and C. Hendrich. Recent developments on primal- dual splitting methods with applications to convex minimization. In P. M. Pardalos and T. M. Rassias (eds.), Mathematics Without Boundaries: Surveys in Interdisciplinary Research, pp. 57-99. Springer New York, 2014.
L. Bottou. Stochastic gradient descent tricks. In G. Montavon, G. B. Orr, and K.-R. Müller (eds.), Neural Networks: Tricks of the Trade, pp. 421 436-436. Springer Berlin Heidelberg, Berlin, Heidelberg, 2nd edition, 2012.
Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn., 3(1): 1-122, 2011.
S. Bubeck. Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn., 8(3-4): 231-357, 2015.
E. Candès and T. Tao. The Dantzig selector: Statistical estimation when p is much larger than The Annals of Statistics, (5(6):3313-2355 2007.
E. J. Candès, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Information Theory, 52(2):489-509, 2006.
V. Caselles, A. Chambolle, and M. Novaga. Total variation in imaging. In O. Scherzer (ed.), Handbook of Mathematical Methods in Imaging, volume 1016-1057. Springer New York, New York, NY, 2011.
10

---

Published as a conference paper at ICLR 2023
V. Cevher, S. Becker, and M. Schmidt. Convex optimization for big data: Scalable, randomized, and parallel algorithms for big data analytics. IEEE Signal Process. Mag., 31(5):32-44 2014.
A. Chambolle and T. Pock. first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision, 40(1):120-1) 145, May 2011.
A. Chambolle and T.. Pock. An introduction continuous optimization for imaging. Acta Numerica, 25:161-319, 2016.
A. Chambolle, M. J. Ehrhardt, P. Richtárik, and C.-B. Schönlieb. Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging applications. SIAM J. Optim., 28(4): 2783-2808, 2018.
P. Chen, J. Huang, and X. Zhang. A primal-dual fixed point algorithm for convex separable minimization with applications image restoration. Inverse Problems, 29(2), 2013.
L. Combettes and J.-C. Pesquet. Proximal splitting methods in signal processing. In H. H. Bauschke, R. Burachik, P. L. Combettes, V. Elser, D. R. Luke, and H. Wolkowicz (eds.), Fixed- Point Algorithms for Inverse Problems in Science and Engineering. Springer- Verlag, New York, 2010.
P. L. Combettes and J.-C. Pesquet. Stochastic approximations and perturbations in heward-backwwar splitting for monotone operators. Pure and Applied Functional Analysis, 1(1):13-37, 2016.
I.. Combettes and J.-C. Pesquet. Fixed point strategies data science. IFEE Trans. Signal Process., 69:3878-3905, 2021.
P. L. Combettes, L. Condat, J.-C. Pesquet, and B. C. Vū. A forward-backward view of some primal- dual optimization methods in image recovery. In Proc. of IEEE ICIP, Paris, France, October 2014.
L. Condat. A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. J. Optim. Theory Appl., 178(2):460-47, 2013.
L. Condat. A generic proximal algorithm for convex optimizaaiinnnAAppiiaain to total variation minimization. JEEE Signal Process. Lett., 21(8): August
L. Condat. Discrete total variation: New definition and minimization. SIAM J. Imaging Sci., 10(3): 1258-1290, 2017.
L. Condat and P. Richtárik. MURANA: A generic framework for stochastic variance-reduced optimization. In Proc. of the Mathematical and Scientific Machine Learning (MSML) conference. volume PMLR 190, pp. 81-96, 2022.
L. Condat, I. Agarský, and P. Richtárik. Provably doubly accelerated federated learning: The first theoretically successful combination of local training and compressed communication. preprint arXiv:2210. 13277, 2022a.
L. Condat, K. Li, and P. Richtárik. EF-BV: A unified theory of error feedback and variance reduction mechanisms for biased and unbiased compression distributed optimization. In Proc. of NeurIPS, December 2022b.
L. Condat, G. Malinovsky, and P. Richtárik. Distributed proximal splitting algorithms with rates and acceleration. Frontiers in Signal Processing, 1, January 2022c.
L. Condat, D. Kitahara, A. Contreras, and A. Hirabayashi. Proximal splitting algorithms for convex optimization: A tour of recent advances, with new twists. SIAM Review, 2023a. To appear.
L. Condat, G. Malinovsky, and P. Richtárik. TAMUNA: Accelerated federated learning with local training and partial participation. preprint arXiv:2302.09832, 2023b.
C. Cortes and V. Vapnik. Support-vector networks. Machine Learning, 20(3):273-297, 1995.
C. Couprie, L. Grady, L. Najman, J.-C. Pesquet, and H. Talbot, Dual constrained Ta-based regular- ization graphs. SIAM J. Imaging Sci., 1246-12462273 2013.
11

---

Published as a conference paper at ICLR 2023
D. Davis and W. Yin. A three-operator splitting scheme and its optimization applications. Ser- Val. Var: Anal., 1358899-55, 2017.
A. Defazio. A simple practical accelerated method for finite sums, In Proc. of 30st Conf. Neural Information Processing Systems (NIPS), volume 29, pp. 676-684, 2016.
A. Defazio, Bach, and S. Lacoste-Julien SAGA: fast incremental gradient method with support for non-strongly convex composite objectives. In Proc. of 28th Conf. Neural Information Processing Systems (NIPS), pp. 1646-1654, 2014.
Y. Drori, S. Sabach, and M. Teboulle. A simple algorithm for a class of nonsmooth convex concave saddle-poine point problems. Oper. Res. Lett., 2302)220--214 2015.
A. Dutta, E. Bergou, A. M. Abdehmoniem, Y. Ho, Sahu, M. Canini, and P. Kalnis. On the discrepancy between the theoretical analysis and practical implementations of compressed communication for distributed deep learning. In Proc. of AAAI Conf. Artificial Intelligence, pp- 3817-3824, 2020.
M. El Gheche. G. Chierchia, and J.-C. Pesquet. Proximity operators of discrete information diver- gences. IEEE Transactions on Information Theorry 64(2):102--1144, 2018.
R. Glowinski, S. J. Osher, and W. Yin (eds.). Splitting Methods in Communication, Imaging, Science, and Engineering. Springer International Publishing, 2016.
E. Gorbunov, Hanzely, and Richtárik, unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. In Proc. of 23rd Int. Conf. Artificial Intelligence and Statistics (AISTATS), 2020.
E. Gorbunov, F. Hanzely, and P. Richtárik. Local SGD: Unified theory and new efficient methods. In Proc. of 24th Int. Conf. Artificial Intelligence and Statistics (AISTATS), pp. 3556-3564, 2021.
R. M. Gower, M. Schmidt, F. Bach, and P. Richtárik. Variance-reduced methods for machine learning. Proc. of the IEEE, 108(11): 1111111):999998888 November 2020.
F. Hanzely and P. Richtárik. One method to rule them all: Variance reduction for data, parameters and many new methods. preprint arXiv: 1226, 2019.
Hanzely, S. Hanzely, S. Horváth, and Richtárik. Lower bounds and optimal algorithms for per- sonalized federated learning. In Proc. of Conf. Neural Information Processing Systems (NeurIPS), volume 33, pp. 2304-2315 2020.
S. Horváth, C.-Y. Ho. L. Horváth, A. N. Sahu, M. Canini, and P. Richtárik. Natural compression for distributed deep learning. In Proc. of the Mathematical and Scientific Machine Learning (MSML) conference, volume PMLR 190, pp. 1-40, 2022.
P. Kairouz al. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1-2), 2021.
S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. U. Stich, and A. T. Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. Proc. of 37th Int. Conf. Machine Learning (ICML), pp.
2020.
A. Khaled and P. Richtárik. Gradient descent with compressed iterates. In NeurIPS Workshop Federated Learning for Data Privacy and Confidentiality. 2019.
A. Khaled, K. Mishchenko, and P. Richtárik. First analysis of local GD on heterogencous data. In NeurIPS Workshop on Federated Learning for Data Privacy and Confidentiality, 2019.
A. Khaled, Mishchenko, and P. Richtárik. Tighter theory for local SGD on identical and het- erogeneous data. In Proc. of 23rd Int. Conf. Artificial Intelligence and Statistics (AISTATS), 2020a.
A. Khaled, O. Sebbouh, N. Loizou, R. M. Gower, and Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. arXiv:2006.1 1573,, 2020b.
12

---

Published as a conference paper at ICLR 2023
S.-J. Kim, K. Koh, S. Boyd, and D. Gorinevsky. 11 trend filtering. SIAM Review, 51(2):339- 2009.
N. Komodakis and J.-C, Pesquet. Playing with duality: An overview of recent primal-dual approaches for solving large-scale optimization problems. IEEE Signal Process. Mag., 32(6):31-54, November 2015.
J. Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon. Federated learning: Strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016. MrXiv:1610.05491
D. Kovalev, A. Salim, and Richtárik. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. In Proc. of Conf. on Neural Information Processing Systems (NeurIPS), 2020.
Latafat and Patrinos. Asymmetric inclusions involving three operators. Comput. Optim. Appl., 68(1):57-995 2017.
splitting for solving monotone
T. Li, A. K. Sahu, Talwalkar, and V. Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 3(37):50-60) 2020.
I. Loris and C. Verhoeven. On a generalization of the iterative soft- coft-thresholding algorithm for the case of non-separable penalty. Inverse Problems, 27(12), 2011.
D. R. Luke and R. Shefi. A globally linearly convergent method for pointwise quadratically support- able convex-concave saddle point problems. Math. Anal. Appl., 457:1568- 1590, 2018.
G. Malinovsky, D. Kovalev, E. Gasanov, L. Condat, and P. Richtárik. From local SGD to local fixed point methods for federated learning. In Proc. of 37th Int. Conf. Machine Learning (ICML), 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agûera y Arcas. Communication-efiiiient learning of deep networks from decentralized data. In Proc. of Int. Conf. Artificial Intelligence and Staristics (AISTATS), volume PMLR 54, 2017.
K. Mishchenko and P. Richtárik. A stochastic decoupling method for minimizing the sum of smooth and non-smooth functions. preprint arXiv: 1905. 1005511 2019.
K. Mishchenko, E. Gorbunov, M. Takáč, and P. Richtárik. Distributed learning with compressed gradient differences. arXiv:1901 .09269, 2019.
K. Mishchenko, G. Malinovsky, S. Stich, and P. Richtárik. ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally! Proc. of the 39th International Conference Machine Learning (ICML), July 2022.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming, SIAM Journal on Optimization, 1944):574-1169) 2009.
D. P. Palomar and Y. C. Eldar (eds.). Convex Optimization in Signal Processing and Communications. Cambridge University Press, 2009.
N. Parikh and S. Boyd. Proximal algorithms. Foundations and Trends in Optimization, 3(1):127-239 2014.
G. Peyré and M. Cuturi. Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning, 11(5-6):355-67, 2019.
N. G. Polson, J. G. Scott, and B. T. Willard. Proximal algorithms in statistics and machine learning. Statist. Sci., 5081), 2015.
N. Pustelnik and I.. Condat. Proximity operator of sum of functions; application to depth map estimation. IEEE Signal Process. Lett., 187121118771183,, December 2017.
H. Robbins and S. Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22:400-407, 1951.
13

---

Published as a conference paper at ICLR 2023
L. Rudin, S. Osher, and E. Fatemi. Nonlinear total variation based noise removal algorithms. Phys. D, 60(1-4):259-22 268, 1992.
M. Safaryan, E. Shulgin, and P. Richtárik. Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor. Information and Inference: A Journal of the IMA, 2021.
A. Salim, L. Condat, D. Kovalev, and P. Richtárik. An optimal algorithm for strongly convex minimization under affine constraints. Proc. of Int. Conf. Artif. Intell. Stat. (AISTATS), PMLR 151, pp. 4482-4498, 2022a.
A. Salim, L.. Condat, K. Mishchenko, and P. Richtárik, Dualize, split, randomize: Toward fast nonsmooth optimization algorithms. Optim. Theory Appl., 195:102-130, October 2022b.
F. Sattler. S. Wiedemann, K.-R. Müller, and W. Samek. Robust and communication-cfficii federated learning from non-i.idd data. IEEE Trans. Neural Networks and Learning Systems, 31(9):3400- 3413, 2020.
S. Sra, S. Nowozin, and S. J. Wright. Optimization for Machine Learning. The MIT Press, 201 1.
G. Stathopoulos, H. Shukla, A. Szues, Y. Pu, and C. N. Jones. Operator splitting methods in control. Foundations and Trends in Systems and Control, 3(3):249-362, 2016.
S. U. Stich. Local SGD converges fast and communicates little. In Proc. of International Conference on Learning Representations (ICLR), 2019.
R. Szlendak, Tyurin, and P. Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. In Proc. of Int. Conf. on Learning Representations (ICLR), 2022.
H. V. Vo, F. Bach, M. Cho, K. Han, Y. LeCun, P. Pérez, and J. Ponce. Unsupervised image matching and object discovery as optimization. In Proc. of IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8287-8296. 2019.
B. C. Vü. A splitting algorithm for dual monotone inclusions involving cocoercive operators. Adv. Comput. Math., 38(3):667-68) April 2013.
J. Wangni, J. Wang. J. Liu, and T. Zhang, Gradient sparsification for communication-efiin distributed optimization. In Proc. of 32nd Conf. Neural Information Processing Systems (NeurIPS), pp. 1306-1316, 2018.
W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, Y. Chen, and H. Li. TernGrad: Ternary gradients to reduce communication in distributed deep learning. In Proc. of 31st Conf. Neural Information Processing Systems (NIPS), pp. 1509-1519, 2017.
B. Woodworth, K. K. Patel, and N. Srebro. Minibatch vs Local SGD for heterogencous distributed learning. In Proc. of Conf. Neural Information Processing Systems (NeurIPS), 2020.
R. Xin, S. Pu, A. Nedié, and U. A. Khan. A general framework for decentralized optimization with first-order methods. Proceedings of the IEEE, (08(11):1869-188 November 2020.
H. Xu, C.-Y. Ho, A. M. Abdelmoniem, A. Dutta, E. H. Bergou, K. Karatsenidis, M. Canini, and P. Kalnis. GRACE: A compressed communication framework for distributed machine learning. In Proc. 41st IEEE Int. Conf. Distributed Computing Systems (ICDCS), 2021.
M. Yan. A new primal-dual algorithm for minimizing the sum of three functions with linear operator. Sci. Comput.. 76(3):1698-177 September 2018.
M. Yuan and Y. Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 68(1):49-67, 2006.
J. Zhang, K. You, and L. Xie. Innovation compression for communication- distributed optimization with linear convergence. IEEE Trans. Autom. Control, 2023. To appear.
14

---

Published as a conference paper at ICLR 2023
Algorithm 5 RandProx Skip [new]
Algorithm 6 RandProx-Minibatch [new]
input: initial points x0 E X. uº E u;
input: initial points x E X, (u)) E e::
stepsizes 7 > 0, T > 0: p E (0,1]
stepsize y > 0: k E {I....,m}
v0 == K'n
2 = Di=1 un
for t = 0, 1....... do
for 1. = 0, 0...... do
6 prox 7g (x²
7V fxx) ) 70t)
s' == prox 7g (xt
y VVI(x') - -70²)
Flip a coin 0 = with probability p.
pick Ω2 C {1, [I,..., n. of size k unif. at random
0 else)
for [+1 = prox hr (ut +*)
D2 do
if 6r then
u
u u'+l= = prox be (u + 7 kkt)
end for
ot K"u u1" +1
for i E {l....,
m 122 do
x x'+1 = at p.
( - vt)
ui
++1 = u
else
end for
u +1 = u², rltl = v², xt == 5²'
+++1
Σ i= u
end if end for
x = N¹
21 (v 1+ - v²)
k
end
for
Appendix
A EXAMPLES
A.1 SKIPPING THE PROXIMITY OPERATOR
In this section, we consider the case of Bernoulli operators R' defined in (6). which compute and return their argument only with probability p > 0. RandProx becomes RandProx-Sker Skip, shown above. Then
Wran || and < 0.
If 0. RandProx Skip reverts to the SplitSkip algorithm proposed recently (Mishchenko et al. 2022).
Our Theorems and 4 recover the same rate as given for SplitSkip in Mishchenko et al.
(2022 Theorem D.1), if smoothness of h is ignored. If in addition K = Id and
RandProx-Skip reverts to ProxSkip, a particular case of SplitSkip (Mishchenko al. 2022 Our Theorem 3 applies to this case and allows us to exploit the possible smoothness of h in RandProx-
Skip ProxSkip. which not the case of the results of (Mishchenko al.) (022). As practical
application of our new results, let us consider personalized federated learning (FL) (Hanzely et al.) 2020): given a client-server architecture with a master and n 2 users, each with local cost function J. 7,1== .....,
1........ n, the goal is to
a
> Σ 2
minimize (()2)E(RR))
(xx)
(22)
where = n E Tr. Each f, supposed -- -mmoohh and stroonlyy convex. We set (R.
f:z= = (I:) + Ei f((z,). h + Σ || - 12.. f -smooth and -stoonlllyy convex, h is X-smooth, so that pmx = x. Thus, with y T.f" we have in (16]
1
1 2L
μf Ls
c c min
1.
+ 2x1
P
Hence, with p / min(
min
Σイ 1). the communication complexity in terms of
Ls
the expected number of communication rounds to reach eaccuracc is O ( 1) log !). which, up to the '+1' log factor, is optimal (Hanzely et al. 2020). This shows that in personalized FL with À < Ly, the complexity can be decreased in comparison with non-personalized FL, which corresponds to À = +oc. This is achieved by properly setting p in ProxSkip, according to our new theory, which exploits the smoothness of h.
min(Ly,A)
15

---

Published as a conference paper at ICLR 2023
A.2 SAMPLING AMONG SEVERAL FUNCTIONS
We first remark that we can extend Problem ① with the term k(x)) replaced by the sum D his (Kaz) of
proper closed convex functions hú composed with linear operators X + Ug for some real Hilbert spaces U4 by using the classical product-space trick: by defining U = U1 u. h (u:)=1 U Ei=1 (u,),,, K : X' + (K,=)== U. have h( Ei=1 (K.)). In particular, by setting K Id and Ut; = X, consider in this section the problem:
Find x² E arg argg min (F()) g(x) + Σ (,((z) aEX
(23)
We have ht (u=) X i= h (u:) and suppose that every function h is -trongly
convex, for some p4- 2 0; then he is pa- -stro-ttonll convex. Thus, the dual problem to 23 is
(1+
Find (ut (u))== E arg arg (u))_
Σ 1m
ui
+
by (u:))
(24)
1=1
Since K* nld, |||| n. Now, choose Rt the rand-k sampling operator, for some k E (1...., n): R2 multiplies & elements out of the n its argument sequence, chosen uniformly at
random, by n/ and sets the other ones to zero. It is known (Condat & Richtárik 1) that we can set
2022 Proposition
n - k) 1, Wran k:nn 1) Ç k(n 1)
Tー- k
Note that this value of Wran is n - times smaller than the naive bound || = m(nkk) We have (1 - [)] K] + Wran = n. RandProx in this setting, with 7 = m.. becomes RandProx-Minibatch shown above, and Theorem yields:
&
Theorem 5. Suppose that μ > 0 or Hy > O, and that pie > 0. In RandProx-Minibatch, suppose that 0 < < 2, Define the Lyapunov function, for every 2 0,
n (yn + 2p V' = 1| 11
Juf ut
(25)
k
where x² and (ut)== are the unique solutions to 23 Minibatch converges linearly: for every 2 0, E
and 24), respectively. Then RandProx-
< c
where
?11) (7T,, 1)2
2ktu
C = max
(26)
1 7/44
1+
n(yn + 2pp
Also, (I') and (i*) both converge to x² and (u()SE converges to ut, Vi, almost surely.
RandProx Minibatch with i = becomes the Stochastic Decoupling Method (SDM) proposed in Mishchenko & Richtárik (2019). where strong convexity of is not exploited, but similar guarantees are derived as in Theorem 5 if (4g = Linear convergence of SDM is also proved in Mishchenko & Richtárik (2019) in conditions related to ours in Theorems and 4. Thus, HandProx-Minibesr extends SDM to larger minibatch size l: and exploits possible strong convexity of g.
When f 0 and g 0, SDM further simplifies to Point-SAGA (Defazio) 2016). In that case, our results do not apply directly, since there is no strong convexity in of and any more, but when minimizing the average of functions h2, with each function supposed to be L-smooth and j-strongly convex, for some L, 2 /4 > 0, we can transfer the strong convexity to by subtracting 5 to each h; and setting g = $ l| This does not change the problem and the algorithm but our Theorem now applies, and with the right choice of 7, we recover the result in Defazio (016)), that
the asymptotic complexity of Point-SAGA to reach c-accuracy is O ((r nL conjectured to be optimal.
log which is
Thus, RandProx- Minibbatch extends Point-SAGA to larger minibatch size and to the general problem 233 with nonzero / or
When 1, there is randomness and SDM reverts the DY algorithm discussed in Appendix G
16

---

Published as a conference paper at ICLR 2023
Algorithm 7 SDM
Algorithm 8 Point-SAGA
Mishhhennko & Richtárik 2019)
(Defazio 2016)
input: initial points x² E X, (uf) 1= E :::
input: initial points XO X, ( E X
stepsize 7/
stepsize 7 > 0
v" == Σ -= 2
1n
v == u for t = 0,1...d do
for t = 0, 1,.,..... do
6' prox (xt
f - 70²)
4 = x² -00
pick 1 ,l....,
n uniformly at random
pick 1t E ( uniformly at random
x (+1 = proxxyh, (7rug) + 8²)
++ = -ppprx (ynu,, 5²)
det uhe + m
(0' -x++1)
1+1 = u/y + ym (++ x1+1)
for every i E fl...., n
ut = of 1+1 // = v² + Ug ul.
for every E {I.... ,n) Mi) {i']. u ++
= uf
r²m1 = Ei=1 u/
y+ = Ei= utt re + u u.
end for
end for
Algorithm 9 RandProx-Fi [new]
input: initial estimates (x E Xn (u,) 1 X² such that Dx= up = 0: stepsize y > 0; w 2 0 for t 0, 1, 1.... do
for i 1,
at nodes in parallel do V Ji (xx) yu!
a = (*
I/ send compressed vector at to master end for
a' Σ of // aggregation master
broadcast a² all nodes
for i
.,... at nodes in parallel do
= a a²
" u +
71+W] d
2 [+1 at 1+w d
end for end for
A.3 DISTRIBUTED AND FEDERATED LEARNING WITH COMPRESSION
We consider in this section distributed optimization within the client-server model, with a master node communicating back and forth with > 1 parallel workers. This is particularly relevant for federated learning (FL) (Konečný et al. 2016; McMahan et al., 2017 Kairouz et al., 2021 Li et al.) 2020), where potentially huge number of devices, with their owners data stored on each of them, are involved in the collaborative process of training a global machine learning model. The goal is to exploit the wealth of useful information lying in the heterogeneous data stored across the devices. Communication between the devices and the distant server, which can be costly and slow, is the main bottleneck in this framework. So, it is of primary importance devise novel algorithmic strategies, which are efficient in terms of computation and communication complexities. A natural and widely used idea message (Alistarh et al.) 2017 Wen et al. 2017: Wangni et al., 20122 Khaled & Richtárik 2019 Albasyoni et al. 2020: Basu et al. [2000] Dutta et al. [2020] [Sattler al. |220]] Xu et al. 2021) ).
make use of (lossy) compression. reduce the size of the communicated
Another popular idea is to make use of local steps (McMahan et al.[2017 / Khaled et al. [019]] Stich
2019 Khaled et al.) 2020a Malinovsky et al.) 20200 Woodworth et al. 2020 Karimireddy et al.
2020 Gorbunov al. 202 Mishchenko et al., 2022); that is, communication with the server does
not occur at every iteration but only every few iterations, for instance communication triggered randomly with small probability at every iteration. Between communication rounds, the workers perform multiple local steps independently, based on their local objectives. Our proposed algorithm RandProx-F FL unifies the two strategies, in the sense that depending the choice of the randomization
17

---

Published as a conference paper at ICLR 2023
process RA, obtain method with local steps or with compression, or both. The combination of local training and compression has been further investigated our follow-up work (Condat et al. 2022a), and partial participation in Condat et al. (2023b).
Thus, we consider the problem
Σ E(0)
Find x² E arg min xE3*
(27)
where d 2 1 is the model dimension and n 2 1 the number of parallel workers, each having its
own objective function fa. Every function fi IR + R is p-strongly convex and L-smooth, for some L 2 μ4 > O. We define K == L/p.
Now, observe that (27) can be recast 1 minimization of f + h, as studied in Section 4.1 with
with K Id, U X, g 0; that is, as the
X' = -R=)", x f=x=(x=) 7 Σ f(xs),
(28)
h (2:) + (0ifxi= = - In, too otherwise).
(29)
We note that f is ju-strongly convex and L-smooth, and jaa- RandProx-FB yields RandProx-FL, distributed algorithm well suited for FL., shown above. In RandProx-FL, randomization takes the form of linear random unbiased operators R$ applied the vectors sent to the server. Note that at every iteration, the same operator Rt is applied at every an instance of
Making these substitutions in
node; that is, its randomness is shared. We can easily check that RandProx-FL. RandProx-FB, because of the linearity of the R and because the property Σ of = O is maintained every iteration. Formally, R' applied as a whole in RandProx FB consists of n copies of R' applied individually at every node in RandProx-FLL FL, that is why we keep the same notation; in particular, the value of the same in both interpretations.
Interestingly, in RandProx-FLL information about the functions Si or their gradients is never commu- nicated and is exploited completely locally. This is ideal in terms of privacy.
As an application of Theorem 3, we obtain:
Theorem 10. In RandProx-FL FL, suppose that 0 <<<< L.p Define the Lyapunov function, every t #20 0,
a Σ
1 | x01 101 7(1 + w) - ut utll²)
(30)
where x² is the unique solution of (7 and ut ff(x')) Then RandProx-FL converges for every 2 0, E[T < covo, where
comvergs linearly:
max (1-7 (7b, 1)2, (1+
1.
(31)
Also, the (x))EN and (iE) all converge to x* and every (u))EN converges u,, almost surely.
R' is the Bernoulli compressor we have seen before in (6) and in Section A.1 RandProx-FL reverts to the Scaffnew algorithm proposed in Mishchenko al. (2022). , which communicates at every iteration with probability E (0, 1] and performs in average 1/p local steps between successive communication rounds. We have w
The analysis of Scaffnew in Theorem 10 is the same as in Mishchenko et al. (2022). With y = r. the iteration complexity of Scaffinww is ( + 3 log :). and since the algorithm communicates with probability its average communication complexity is O (pm + })) log 4). particular, with - O log !)-
the average communication complexity of Scaffnew
We now propose a new algorithm with compressed communication: in RandProx FL we choose, for every t > R' as the well-known rand-k compressor, for some {1, ...... d): R' multiplies k coordinates, chosen uniformly at random, of its vector argument by d/k and sets the other ones
to zero. We have
The iteration complexity with 7 1 is O de log !) and the
18

---

Published as a conference paper at ICLR 2023
communication complexity, in terms of average number of floats sent by every worker to the master, ((kk + 4 log )), since floats are sent by every worker every iteration. Thus, by choosing = [ as long as 2 vR, the communication complexity in terms of floats (dy log t): this is the same as the one of Scaffnew with = 1 and p = JेP but RandProx- FL with rand-k: compressors removes the necessity communicate full d-dimensional vectors periodically.
B CONTRACTION OF GRADIENT DESCENT
Lemma 1. For every Y > O, the gradient descent operator Id -vV ʃ is cy-Lipschitz continuous, with C, == max(1 MM5, rDy 1). That is, for every (x, x²) E x²2
[[Id - -Vf - (Id ~VVf)=' S - -
Proof Let (xr x') E X², By cocoercivity of V - IyId, we have (Bubeck 2015 Lemma 3.11) Liny
(Vf(x)) (1(x') (a'), x--xx =x)) z
Letpy || - x' 1,t,y [v) f(x')) |2 Hence,
[((dd /V (Id ~/)''11 < (1 ) || x'11
(7² L,tpy fxx) v)(>)))
23
Thus, if 7 S Lytpy since V - V>('')|| > , || x ||.
((dd>>f)== (1d
2 + (72 Litms )1² || x'12
27
Lstus
(1 >14)> - x'112.
On the other hand, 7 2 Lytps* since (x)) <)(2')|| S T1yl100 xx'
(Id -ldd-vVfl-(ld--aa
< [1
27L184
L, + (72 Lytpy ) || 2'12
27
=T> 1)31|z 2'1
Since max(1 Mp.. ?, 1) (1 - 7p4 if y S L,t, L otherwise) 2 0, we arrive at the given expression of Cy.
We note that 7 < 2 and μ > c, <1.
C PROOF OF THEOREM
Let E N. Letp'' E Og(x') be such that af x' -(- properties of the proximity operator. We also define p" == - K"="; we have p" 0g(x*)
exists and is unique, by
Let q¹ = 42, and q-' : ==p" -Hgx*. We have (1 + 7M,) = [\''' - "6 - 7KK
Let w² = xt 7 fx(")) and w² x (((())
Using at defined (9, we have
x*
12 Fi = E 44 Fi] x*1 + +E 1B[12 E B[ Fi]112 Fi
< ||-t x²- 7 KK* (1i -nx))ll 1²) + 2 | - w!l?
- 22c || (a/+t - w2)112
19

---

Published as a conference paper at ICLR 2023
Moreover,
|| x= -7 (att(aat== -x]]1
= -1 - x² 112 x-2 K (att
- wt)l
- -27(2' - xx, =x" (2't1 - -²')
S (1+ + 740) || - x¹1| +,² (x(tttt)1)))))) - u\)]l²
- -2 - -x', =x,KK'
K (a 1+1 - u²) }} + 22' - -x,, ,²,K"(( KK'("" - x²))
= (w' - w² - 760 9¹) - -K (u' -u') -u"), - x²)
+ IK' K (alt1- - x²)l )²
-27(2' - x',K" (al 11 - x²)) + +2 - xx,, K (ul - x²²)
=- --27/0 - q0, .t -x')
+ (1o' - w² + 7 -4") + 7 (u' - =²), - -²²)
+ 1/2|K' |K (a - u r))l - 27/ - -x", K (1it11 u²") ")
= -227 - q¹, xt - x²)
1 (w' - = + + - -4) + >-K'(² - -u²),
+ + 744
w² w² - -7(0 - -²") - -gK* (u' - u²))
+ +22 1| |k^'< (itt1 1--1-1 -w')l - 27/ - =x, KM (i'tt1110 "²))
= 2 - g¹, 2,'² - xx'> +
1
|| |w0 w²1l
1 7H4
72
+ 7/4 10"- + KK KK(n'' -2=)) 11²
+ +72 | (a/t+= 1 u w²)l?
27 - xx, K (i't1 - u²)).
We have (g¹ - ,',""' x²) 2 O. Hence,
| x²- - 7k* (igt11 - -n')]?² -
| w011==
72
119 - 9- + K K'(U' - -n')'" 1
7itls 1itl
1 1
1 + 7/4
+ 2² | - u²))" 2-) 23 - xx, K* (a - -u=))= =²))),
so that
B
| 1, x0113 |i]] S
1
1|00 w0 112
72
||4² - 10* + K K'(n' =1?
1 + 7/1g
1 714g
+ + (1 - () [0]|A<((0 -2²)l 27 - xx, K" (aa+t1 - -u"
+ f || - u11
On the other hand,
FF S 2² u²= + (ilt1 (94t1_29) -2) 2
E
||
u²1l3
+
w "I+ w || - w¹(12
1 w
w²
1112 - -2- 112 (1+ + w)3 l1att1 u² u1
(1 +++w W)2
(1 11+ (ui - -u / - =²)) +
2w
(1 (1+w)) w)z | - ue1l"
w
(1 + w)² 11ue - -u²l1
(1 (1+ w)) (u- - u², attl _ -u*)
2w
a [+1 u²1l
+
w
|| u² 112
(32)
1 +
20

---

Published as a conference paper at ICLR 2023
Let s0ts O0h(((t))) be such that x'+1 u² + TKt' rs*+!; st exists and is unique. We also
define s* = Kxx; we have S" E dhh (u"). Therefore,
||att1 - u²1 1| = ||(u' - )² + (at - u²') u²
= |/ue - u || + || - r²11 || + 2(1²* - u², 10 - u²)
|/uf u=|l || + 2( u², aitt u²) -11utt ulll
|/u u²1l || || |ittt - 11 + 2T 2a uu,,, [K(55 x²))
27 (ūi+1
u 8 8*).
Hence,
E |
1--1-=x1'
1 Fi
1 + w IF. ||
w²11? |Fr
$ 7(1 + )umm
1lw 20 10=12
7
11g q- + K* (u' - x²)]
1 + 714
+ 71 5)
| |K
u² u²)" -2(0²
x², K* (a n²))
+ ywran 12 - u² 2
- |1' - u2' w²2
1
1 | - u $1
+ о
2(0"+1
ut, K(#' -x')) 2(0 u² , 5*)
W
T |u'
w=1
1
||"0* w=' 11= 1 774g
l|0' ---- 9- + K* (u' - =2²)1
711 + (/1))
7/4
1 ++ w
|uu'-u' 11=1 (7(11- 1.. 11] + Wran) - -2 ||00 =2211²
2( u,, st11 s²)
1| -w' 112
7
1|9¹ -g" + K" (u' - (u'-
71 + }mug)
1 + 7M4
1 |/u² - 112 - -2( - u, 5/41_ 8*).
+
By strong monotonicity of Oh", (i/+11 uu, 88411 - =0² 2 Mn- || - n² 111 and using 332.
(i++1 u,,"",";;'' , 1+ 8*) 2 pM (1 + w)F
|| - v² -12² I |is] - w || xx" 11²)
Hence,
1 E ||att11 - =x²12 | + (1 ww
- +
1
E
||uct1 - ==1 FF
llee" w00 w=1²=-
1 7
11a" q" + K3* (''x'' (u'-u*)]1
7(1 + mmon
714
+ ( 1 +
+ 2w)li:)) ) |1-6 =ut
(33)
r
After Lemma I,
100" w=1
||(Ta- 10----V1 ~V)) - (Id - /-/'==1
max(1 7 - 1)2 | x=' 1|2
<
Plugging this inequality in (33) yields
E f
Fi] <
71 + 711g) max(1 - - 1)² 11-² - x011
(34)
1 + w
+ 2w/mn ) 11
7 110¹ - q- + KKt('' u²²) =²)
5
1+ 744
21

---

Published as a conference paper at ICLR 2023
Ignoring the last term in (34). obtain:
-1-10 -1-))))
(
2T (1 w)(1 + 2T
E
Fi.
max
(35)
1 7Pg
1 71g
Using the tower rule, we can unroll the recursion in (35p to obtain the unconditional expectation of Vet+1 Since [[V" + 0, we have E. || 11
and E
| -'1 - Moreover, using
classical results supermartingale convergence (Bertsekas) 2015 Proposition A.4.5), it follows from (35) that / - 0 almost surely. Almost sure convergence of and u' follows. Finally, by Lipschitz continuity of f, K" praxy, we can upper bound || 2=1 by linear combination of
|| 112 and ||ul u*1 u²1 follows that E || x*1 that Et almost surely, as well.
0 linearly with the same rate c and
D PROOF OF THEOREM
Let us go back to 34 Since O, we have o² = =0 =0 H4 = 0, so that
Fe < max (1 7 1,00 x1= w + 2wsun ) 11"² -
-o-1""1l w01
7 || (v' - 111
We have |KK u''] > Amin (KK*) I|u' u² 1|2 This yields
E B[y
Fi] S max(1 - MM4 7h. 1)² 1/21 =²1?
+ + w + 2w/4 >dmin (ami((KK)) (KK*)) ||1e u²
(1-~7e (u-) (%b, - 1)2, 2T + -TTmmiu (KK*)
S max
(36)
(1 + w++)(1 + 2T
The end of the proof is the same as the one of Theorem 1.
Let us add here remark on the PAPC algorithm, which is the particular case of RandProx when = 0. in the conditions of Theorem 2:
Remark 2 (PAPC vs. proximal gradient descent the dual problem) If My 0, f is is pr smooth and T.r -trrongly convex. Then f* K is | smoooth and I Amiu DininKK**) (KK*)- strongly convex. So, if f is computable, can apply the proximal gradient algorithm dual problem (2). which iterates u prox, (u' + (XVff(KK'>
the
with E (0. ( If Xmin (K'' K*) > 0, this algorithm converges linearly: ||u u²12 < e21lu² w²1 with
= max (1 +I.=²> >min (MinnKK") (KK*), T,7 [ - 1). is smallest with 2/(17 |K|2 Amin
Amin [ (K))), which case
By Aunia (KK")
||
Amiia (KK*)
||
This is much worse than the rate of the PAPC algorithm, since involves the product of the condition numbers L //v and |||]| Amin KK)), instead of their maximum. This due calling gradients of fo o K whereas f and K are split, or decoupled, in the PAPC algorithm.
E PROOF OF THEOREM 4 AND FURTHER DISCUSSION
22

---

Published as a conference paper at ICLR 2023
Algorithm 10 RandPriLiCo [new]
input: initial points x² E X, v0 E rran(W);
stepsizes 7 > 0, 7 > 0; 2 0 for t = 0, 1,.,.... do
8¹ x² VV
yot
d= = +S' i a)
r/ v² Itw d=1
x x1+1 = 7
end for
We observe that in RandProx-LC and Theorem is if the sequence (um)nEN had been computed by the following iteration, initialized with x." E X and ug == Pran(K) ()) (x)((( (u)):
s == x² (v*) - yv'
u = ub I-w P ( R2 (T(K3' b))
ue+1 = =K="""
x(+1 = 4t 711 + w)(
Then remark that this is simply the iteration of RandProx, with R' replaced by R' = Pron(K) Rs. Since its argument pf = T(K&' - b) is always in ran(K) K), R² is unbiased, and we have, for every t O.
E R$ (20)
pe
2
Fr x (
11 F5 sw|r"11
where Fr the o-lleerra generated by the collection of random variables (z", ui).... (x", ub). Also, Wran is unchanged. Therefore, the analysis of RandProx in Theorem 2 applies, with u² replaced by ub and by ug. Now, for every u E ran(K),
||K"ul] A (KK*) [ul]?,
and using this lower bound in the proof of Theorem 2, with ua- 0, we obtain Theorem 4.
Furthermore, the constraint Kx = is equivalent to the constraint K Kr = b;;; so, let us consider problems where we given K K and not K in the first place:
Let W be a linear operator on X, which is self-adjoint, i.e. W* = W, and positive, i.e. (Wx, x)) 2 0 for every X. Let E ran(W). We consider the linearly constrained minimization problem
Find x" aargm min fxx)
=x=a.
(37)
sEX
Now, we let 2/ == X' and K K VW, where VW is the unique positive self-adjoint linear operator on X' such that /W /W- = W. Also, b is defined as the unique element in ran (W) ran(K) such that VWb consider the Randomized Primal Linearly Constrained minimization algorithm (RandPriLiCo), shown
Then (37) is equivalent to (17) and the dual problem is (18). We
above. We suppose that the stochastic operators St in RandPriLiCo satisfy, for every 2 0,
(t' Fr = and
(((ss - 111 3 s w 1
(38)
for some 2 0, where r' == -W - ra. In addition, we suppose that the St commute with VW: for every / 2 and x X,
(x) S(Wxz)
This is satisfied with the Bernoulli operators some linear sketching operators, for instance. Then RandPriLiCo is equivalent to RandProx-LC, with St playing the role of R² and Wran = || [[o Ç = 0. Applying Theorem 4 with these equivalences, we obtain:
23

---

Published as a conference paper at ICLR 2023
Algorithm 11 CP algorithm
Algorithm 12 RandProx-CP [new]
(Chambolle & Pock 2011)
input: initial points x. E X, ud El;
input: initial points x² X. w E Ui
stepsizes 7 > 0, T 0; w 2 0
stepsizes 7 > 0, > 0
2 = prox, 1g (x ~K"u")
.: == prox 19 (x (K"nn)
for 1 0, 1,
do
for f = 0, 0.1....d do
d' = R¹ (prox, h (ul + T -Kkk) - u²)
u²+1 = 7 (u' + T 7K('')
u't = u² + Ita d:
// //x+1= = s² - 7K* <K*(n tt u²)
1/ x x 8e pkdd d
a1+1 = prox (t' - -gK -K* u²))
#+ = prox,g (tt
yK* (ul+1 + d())
end for
end for
Theorem 6. In the setting of 37 suppose that μy > O. In RandPriLiCo, suppose that 0 < < L,'
T> and W + w) S Define the Lyapunov function, for every? t 2 0,
v = - ||
1=1 - 1+ w 11 - uōll
(39)
where up is the unique element ran(W) such that of /W uly, x² is the unique solution of and up is the unique element in ran(W) such that (V((x*)) = vW ug. Then RandPriLiCo converges linearly: for every 2 0,
37
EE [[V²]] S c'u0
(40)
where
= max (1-7w1)² (1L,
- 1)?, -1L, Y (W) min
< 1.
(41)
+
Also, (x') leE and (+' )ee both converge to x² almost surely.
RandPriLiCo can be applied to decentralized optimization, like in Kovalev et al. (020): Salim et al. (002aa) but with randomized communication; we leave the detailed study of this setting for future work.
F PARTICULAR CASE f 0: RANDOMIZED CHAMBOLLE-POGE ALGORITHM
In this section, we suppose that = 0. The primal problem becomes:
(g(x) + M(Kr))
Find x* arg min xE
(42)
and the dual problem becomes:
Find u² E arg min (g*(-K"))+hr (
(43)
well
The PDDY algorithm becomes the Chambolle-Pen PPck (CP), a.k.a. PDHG, algorithm (Chambolle Pock 2011), shown above. RandProx can be rewritten as RandProx-CP shown above, too. In both algorithms, the variable z' not needed any more and can be removed.
Since 0, Ly > 0 can be set arbitrarily close to zero, so that Theorem I can be rewritten as:
Theorem 7. Suppose that pg O and ph- > 0. In RandProx-CP. suppose that Y 0, y7 77 K| 112 + Wran) S Define the Lyapunov function, for every ' 0,
1 || x=1
{ 2 I|ue - u² 1²
v : 7
+
(44)
where x² and u² are the unique solutions to 442 and linearly: for every 2 0,
43
respectively. Then RandProx-CP converges
E y I c
(45)
24

---

Published as a conference paper at ICLR 2023
Algorithm 14 HandProx-ADMM. [new]
Algorithm 13 ADMM
input: initial points x² E X, u E Ed:
input: initial points x. E X, u E U: stepsize 7 for & 0, o, do
stepsize 0; w 2 0 for t = 0, 0,1,... do
3 prox (x* ru')
E = prox (x* -60--ri) yu') x r = pn' + yu²) w'+1= = ut + ( x)
d' R' R'' prox (1+ (0' + 7(1 w)u'))
x .++1 = at d d
u²+1 u² 70tw)=
end for
end for
where
2T
C max
(46)
1+
(1 + ()) + 2T
YP4
2m
1 1--min min
1.
(47)
(1+
(1 + (1))(11 + 2T
Also, (x IeE and (+* een both converge to x² and (u') hEN converges to u², almost surely.
It would be interesting to study whether the mechanism in the stochastic PDHG algorithm proposed in Chambolle et al. (2018) can be viewed as a particular case of RandProx-CP; we leave the analysis of this connection for future work. In any case, the strong convexity constants flg and (4a- need be known in the linearly converging version of the stochastic PDHG algorithm, which is not the case here; this is important advantage of RandProx-CP.
Now, let us look at the particular case K Id in 42 and 43
The primal problem becomes:
Find x² E arg min (g(x) + h(x)).
(48)
sEN
and the dual problem becomes:
Find u² E arg min wEll
hh)
(49)
When K = ld, the CP algorithm with r= reverts to the Douglas-Rachford Rachford algorithm, which is equivalent to the Alternating Direction Method Multipliers (ADMM) (Boyd et al. 2011
Condat
et al. 2023a), shown above. Therefore, in that case, with Wran w, and 7(1+))
Hand Hax-Prox-CP can be rewritten as RandProx-ADMM, shown above. Theorem 7 becomes:
Theorem Suppose that H2 > 0 and Pa- > In RandProx-ADMM, suppose that > O. For every t 2 0, define the Lyapunov function
V' 1- (w)+ + 2pm-) ||u² u 1²1
(50)
where x² and ut are the unique solutions to 48 and 49 converges linearly: for every & 2 0,
respectively. Then RandProx-ADMM
E.. 1TT S cT
(51)
where
2T
== max
(52)
1 1 711g"""
(1 w1 (1 2T
7Pg
2T
- min
<1.
(53)
[+
(1 w)( 2T
Also, (x' JeEN and (#') both converge to x² and (ul )EE converges u², almost surely.
25

---

Published as a conference paper at ICLR 2023
Algorithm 16 RandProx-DY [new]
Algorithm 15 DY algorithm
input: initial points xD E X, uD E X'; stepsize Y > 0; 2
(Davis & Yin 2017)
input: initial points x² E X, u E X:
for = 0,1.... do
stepsize 7 >
J prox (xt (V((x>) -mr) d' R (i' (1 ww) (Ø' ++(++
for t = 0, 0.l....dd do
8¹ = prox (x² - -VV -qu))
x1+1 = prox (5' + 7u')
x²1 = s³ Itw
dd d'
u'+1 == ut + 1 (it x
7
u' = u¹ + 7(1+w)=
end for
end for
G PARTICULAR CASE K Id: RANDOMIZED DAVIS-YIE ALGORITHM
After the particular case g discussed in Section 4. and the particular case / 0 discussed in Section F we discuss in this section the third particular case Id in and 2 The primal problem becomes:
Find x² E arg min (f()) + + + +Mx)).
(54)
xEX
and the dual problem becomes:
Find 4² E arg min (U++)) +
(55)
wEl
When K = Id, the PDDY algorithm with , reverts to the Davis Yin (DY) algorithm Davis Yin 2017), shown above. Therefore, in that case, with Wran w, < 0 and "(++w), RandProx can be rewritten as RandProx-DY, shown above, too. When g O, RandProx-DY reverts RandProx- FB and when f = O, RandProx-DD reverts to RandProx-ADMM: in other words, RandProx-DY generalizes RandProx-FB and ADMM into single algorithm. Theorem I yields:
Theorem 9. Suppose that μf > or Py > and that pa- > In RandProx-DY, suppose that <<> 2, For every? t 2 O, define the Lyapunov function,
V' -1=--=-- 11 +1+ ww + 2ph-) ) || I=]
(56)
where x² and u² are the unique solutions to (54g and 55 linearly: for every? 2 0,
respectively. Then RandProx DY converges
[0] S c'
(57)
where
(1 (1- (yL 1)2
2 MA- 1 7M4 (1 w) +
c max
1+7M
2 pn-))
< 1.
(58)
Also, (z') lee and )EN) both converge to x* and (u') )eN converges to u², almost surely.
We note that in Theorem 9, pa- > 0 is required. It is only in the case g = 0, when RandProx-DY DY reverts RandProx-FB, that can apply Theorem 3, which does require strong convexity of h".
H PROOF OF THEOREM 11
Proof of Theorem We have, for every (x, x²) E X2,
[[ /V/rz - (Id 22)' = 1|---11 x' 27 27(V)(x) Vf(x')x== -x))
+ vf(z')11
< || x' 2 (2> - x x²),
26

---

Published as a conference paper at ICLR 2023
where the second inequality follows from cocoercivity of the gradient. Moreover, for every (z, x²) X², (, x') & (z) fa'),, x - x'). Therefore, in the proof of Theorem 1, for every
Primal-dus solution (x*, u²) and 2 since l/w* w |[ld - fV (Id - [
33 yields
E[ Fi] S || far-xx11
x01 - (2 (2-7b;)D,(tt) xx*
1 ++ + 2wspen 1lul u²11²
u011--7 -7 11 - 9" K (u= =²)
Ignoring the last term, this yields
4 ++
Fil
- || x=1|² c(1 +w) (- 2p100 +2p00)
||u² - |
(59)
(2 (2->Ly)DDp ,0*)
x v (2 - - ,x),,
(60)
with c = (1 [+ 2
2
in 59 Using classical results on supermartingale convergence
(Bertsekas] 2015 Proposition A.4.5), it follows from 600p that T converges almost surely
random variable t and that
Σ t=0
Dy < too almost surely.
Hence, x + almost surely. Moreover, for every T
220. O.
(2 LL1
Σ
E B[Ds
vo El s To
(61)
t=
and
(2 (L1) Σ E ( , z²)] wo.
1=0
Therefore, E[D,(a', =²] + 0; that is, (y 2²) + 0 in quadratic mean.
The Bregman divergence convex its first argument, so that for every T 2
T
Dy(*" x
Dy(a',x*).
T
Combining this last inequality with 66 yields
(T'+ + 12 - (D) (a" x xx)] S ~..
Now, if pa- > 0, then < 1 in 55 and since & converges almost surely to tres it must be that
1u u² + O.
The counterpart of Theorem in the convex case is:
Theorem 12. Suppose that 0, and that Amin ( (K (KK*) > 0 or pa- >> O. In RandProx, suppose that 0 < 7 < 2,, T > O, and yT 7T((1 []] + Wran) & 1. Then there is a unique dual solution u" to ② and (u') converges to u², quadratic mean.
Proof of Theorem 12 Considering the proof of Theorem the same arguments as in the proof of Theorem 11 apply, with e in (59) now equal to
2Tμ + Amin (KK*) 1.
(1 + w1 2THx))
I|lu'=""''" Hence, E [Ill' - =u]] + O.
27


Reviews:
[{"review_id": "oMm2QkRhPu", "reviewer": "Reviewer_Lt4E", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies a primal-dual algorithm of a convex problem $f(x)+g(x)+h(Kx)$, where the update of the dual variable is randomized. The main result is the Theorem that says if $f$, $g$, and the conjugate of $h$ are all strongly convex, then the proposed algorithm RandProx converges linearly. The paper also proves the convergence rate for the convex case. ", "summary_of_the_review": "The paper studies an algorithm that simply adds randomization in one step of an existing algorithm. The motivation is not clearly stated and the improvement of the proposed algorithm is not well supported. The writing can also be improved with more examples and discussions.\n\nMinor comments:\n- Section 2.1 line 2: there should be a $\\gamma$ in the definition of $\\text{prox}_{\\gamma\\phi}$.", "strength_and_weaknesses": "**Strengh**\n\n- The paper proposes an algorithm that introduces randomness in the dual update of the PDDY algorithm and proves the linear convergence under the strongly convex assumption.\n\n**Weakness**\n\n- It is not clear why the problem $f(x)+g(x)+h(Kx)$ is important to study. I suggest introducing more background and motivation for this problem. \n\n- It is not clear why adding noise in the dual step is a good idea. It seems that the only benefit is that the cost per iteration might decrease if the randomization is like Example 2 on page 4. However, if one uses the randomization in Example 1, the cost is not decreased, but increased because of the extra multiplication. What is the benefit of introducing randomness at all?\n\n- It would be more convincing if the paper shows some empirical results where the proposed algorithm brings a big improvement over the existing algorithm. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "i6SX-fKU771", "reviewer": "Reviewer_Q4Ce", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Under strong convexity, this work provides a very general framework for primal-dual optimization, where the dual step, corresponding to a proximal operator, is randomized. Using a variance reduction technique, linear convergence rates are obtained. The optimizatio model is the sum of three convex functions, where the first one is smoth, while the other two are not, and the third one is the composition of a linear operator and a non-smooth convex function. Sometimes, this last function is assumed to be smooth, so the dual problem is strongly convex. A few results are provided in the case of just convexity of the objective. The work shows how this framework recovers many previous analysis in different settings and how new results are obtained.", "summary_of_the_review": "As I said above, the paper is general, well-written and with interesting and powerful results.", "strength_and_weaknesses": "This is a very general and clean framework that provides many algorithms and will help in the systematic analysis of other randomized primal-dual algorithms. Several of the applications lead to recover previous algorithms, but the novelty is in the general and simple framework, that allows for covering all those applications under the same analysis and for obtaining new results\n\nIn A.1, it is a bit of an odd (or loose?) assumption to assume that f_i are L_f smooth and then \\sum f_i are L_f smooth, could you comment on that / clarify?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Rg_cdzyhlQ2", "reviewer": "Reviewer_pXRx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considered convex composition optimization whose objective function is the sum of three with one composed with a linear operator. A randomized algorithm, which generalized previous determined Primal-Dual algorithm, was proposed. Convergence rate in the strongly convex case was presented, while for the only convex case, convergence rate for the primal Bregman divergence was provided. Several special cases of the proposed algorithms were discussed. ", "summary_of_the_review": "The paper considered three-block composite optimization problem and proposed a randomized Primal-Dual algorithm to solve the problem. Convergence rates are provided, and discussions on some special cases are presented. No numerical experiments are provided to verify the advantages of the algorithms, which is a major drawback. ", "strength_and_weaknesses": "Strength:\n - The proposed randomized algorithm can deal with the general three block composite optimization problem; several existing work in the literature can be casted as special case of the method. \n - For strongly convex cases, linear convergence rate was proved. \n\nWeaknesses:\n - Practical side, lack of numerical examples to justify the advantage of the proposed scheme. In major parts stochastic methods, the randomization is applied to the gradient parts to reduce complexity. While for the non-smooth part, it is questionable whether randomization can bring as big advantage as the stochastic ``gradient'' methods. For example, when $h\\circ K$ is total variation or wavelet like regularizations, $h^*$ accounts for simple projection, which is not necessarily of very high complexity. \n - When the problem is just convex, only convergence rate on the Bregman divergence of the primal variable $x$ was provided. However, the no rates for the dual variable. What caused this? Is it because that the dual function under this setting is non-smooth?  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster