Randomized Primal-Dual Coordinate Method for Large-scale Linearly Constrained Nonsmooth Nonconvex Optimization
Authors: Lei Zhao
Daoli Zhu
Xiao Li
Venue: ICLR 2022 Submitted (2022)
Keywords: primal-dual methods
constrained nonconvex nonsmooth optimization
coordinate descent methods
global convergence
iteration complexity

Abstract: The large-scale  linearly constrained nonsmooth nonconvex optimization finds wide applications in machine learning, including non-PSD Kernel SVM, linearly constrained Lasso with nonsmooth nonconvex penalty, etc.  To tackle this class of optimization problems, we propose an efficient algorithm called Nonconvex Randomized Primal-Dual Coordinate (N-RPDC) method. At each iteration, this method only randomly selects a block of primal variables to update rather than updating all the variables, which is suitable for large-scale problems.  We provide two types of convergence results for N-RPDC. We first show that any cluster point of the sequence of iterates generated by N-RPDC is almost surely (i.e., with probability 1) a stationary point.  In addition, we also provide an almost sure asymptotic convergence rate of $O(1/\sqrt{k})$. Next, we establish the expected $O(\varepsilon^{-2})$ iteration complexity of N-RPDC in order to drive a natural stationarity measure  below $\varepsilon$ in expectation. The fundamental aspect to establishing the aforementioned convergence results is a \emph{surrogate stationarity measure} we discovered for analyzing N-RPDC. Finally, we conduct a set of experiments to show the efficacy of N-RPDC.

Under review as a conference paper at ICLR 2022
RANDOMIZED PRIMAL-DUAL COORDINATE METHOD FOR LARGE-SCALE LINEARLY CONSTRAINED NONS- MOOTH NONCONVEX OPTIMIZATION
Anonymous authors Paper under double-bling blind review
ABSTRACT
The large-scale linearly constrained nonsmooth nonconvex optimization finds wide applications in machine learning, including non-PSD Kernel SVM. linearly constrained Lasso with nonsmooth nonconvex penalty, etc. To tackle this class of optimization problems, we propose an efficient algorithm called Nonconvex Randomized Primal-Duse Coordinate (N-RPDC) method. At each iteration, this method only randomly selects a block of primal variables to update rather than updating all the variables, which is suitable for large-scale problems. We provide two types of convergence results for N- RPDC. We first show that any cluster point of the sequence of iterates generated by N-RPDC is almost surely (i.e., with proba- bility 1) a stationary point. In addition, we also provide an almost sure asymptotic convergence rate of ((I/Vk). Next, we establish the expected ()= iteration complexity of N-RPDC in order to drive natural stationarity measure below e in expectation. The fundamental aspect to establishing the aforementioned con- vergence results is surrogate stationarity measure we discovered for analyzing N-RPDC. Finally, we conduct a set of experiments to show the efficacy of N- RPDC.
INTRODUCTION
Many large scale problems arising in machine learning amounts to solving the following linearly constrained nonsmooth nonconvex optimization problem:
min ZEX
= f(x) + g(x)
(P)
s.t Ax-b=
where A E Raxd and b E R". Throughout this paper, we impose the following assumptions on problem (P: the function f Rd + R is possibly nonconvex and continuously differentiable with its gradient V being Ly-Lisschitz continuous, X is convex and compact set of R4, i.e., there exits a positive number M such that M = max ex ||x x'I|, and g Rdd - IR is nonsmooth and nonconvex. More precisely, g is assumed to be lower semicontinuous (Lss.c) Py Pg-weakly convex and has bounded subgradients over X. i.e., there exists Lg > 0 such that || < Lg. Ys E 0g(x). E X, where 0g the subdifferential of g (see (4) for definition). Let F* be the optimal value of
Recall that function is said to be Pg weekly convex if g(-) 2g -1 convex for some constant Pg 2 Vial 1983). is worth mentioning that a wide class of nonsmooth nonconvex functions belong the weakly convex class; see, e.g., (Vial 1983 Davis & Drusvyatskiy 2019) for more discussions on weak convexity.
We further assume g(x) = Σ (2:) is block separable with respect to the space decomposition
X
XN.
C
Rd
and Σ de d.
Let A = (A,, A2, A E x be the corresponding partition A, where A₁ E Baxd, When N d, each X2 C R corresponds to box constraint on the coordinate s;; for 1,....d. d.

---

Under review as a conference paper at ICLR 2022
Motivations. Our motivation for studying large scale problem P stems from the fact that this problem class finds wide applications in machine learning. To be more specific, we will present several practical examples below that give rise to (P).
Application 1: Non-PSD kernel support vector machine. Support vector machine (SVM) is a widely utilized technique for supervised learning (Boser al.) 1992 Cortes & Vaapnk 1995). In order to improve the interpretability and enhance the robustness, some non-PSS kernels are used in the kernalized SVM method, such as the sigmoid kernel (Lin & Lin| 2003), the jittering kernel (DeCoste) & Schölkopi 2002), the tangent distance kernel (Haasdonk & Keysers 2002, August), to name a
few. Formally, the kernalized SVM problem can be written
min we [E(00,] s.t.
2 Qr 1 y v===0.
(2)
where Q is a d x dl non-PSD matrix, c E R is the upper bound of all variables, y E 1-1,1)a 1 is the vector of labels, and 1a an d-dimensional vector of all 1s.
Application 2: Linearly constrained Lasso with nonsmooth nonconvex penalty. The Lasso is one of the most popular methods for variable selection. The standard Lasso uses -n-morm select important variables. Some works propose to utilize nonsmooth nonconvex regularizers to further improve the performance of the Lasso; see, e.g.. (Breheny & Huang 2011, 2015] Rakotomamonjy et al. 2019). If additional prior information is available, the works (Deng et al.) 2020, May] Gaines et al. 2018 James et al., 2013 Won et al. 2019) propose the constrained Lasso model. The linearly constrained LASSO with nonsmooth nonconvex penalty can be formulated as follows:
min #EX s.t.
1 | b1l? + Σ )(x;)
Br Br-c=0 0
where r (x1 ..... Id) X C C A E Raxd is the design matrix, b E R is the response vector, B E Rmxd and E I are given constraints, and é is a nonsmooth nonconvex regularizer such as MCP (Zhang et al. 2010) or SCAD (Fan & Li 2001) penalty.
There are plenty of other applications that give rise to Pl. e-g., the robust M-estimators, distributed learning, etc. Due to the limitation of space, we will not expand them in details here.
Related works. Linearly constrained nonconvex optimization. Perhaps the most widely utilized class of algorithms for solving constrained optimization problems are the Primal-dual methods. Previous works on single-loop primal-dual methods mainly consider linearly contained convex optimization problems. The work (Bot & Nguyen| 2020) considers nonconvex instance with special linear constraint Ar - 2 = 0, where both x and z are decision variables and the matrix A is assumed to be surjective. Under these assumptions, convergence results were established for proximal alternat- ing direction method of multipliers (ADMM). The recent works (Zhang & Luo 2020a b) provide convergence results of ADMM using gradient-based updates for linearly constrained smooth non- convex optimization problems with a general linear constraint Ax = b, i.c., problem (P) with g = O. The main insights of their results are construction of an proximally regularized auxiliary problem that dates back to (Bertsekas) 1979) and a properly constructed Lyapunov function. Then, they es- tablished descent property on the Lyapunov function based on the dual error bound condition (see also (Hong& & Luo 2017)), which leads to iteration complexity results. The method introduced in (Zhu et al. 2020) can be used to solve problem (P) with specific linear constraints. This method based on the auxiliary problem principle of augmented Lagrangian (APP-AL) method (Cohen & Zhu 1984; Zhao & Zhu 2019 2021). which can be seen as a warkwdd splitting method and applics Jacobian updating strategy However, both ADMM-type and APP-AL-type methods compute the full gradient of primal variables and update all primal variables at each iteration. There- fore, the computation complexity of one iteration of these types of methods are expensive for large-scale problems (See Remark 2.
Randomized coordinate methods for unconstrained optimization. In the past decade, big data applica- tions are ubiquitous in machine learning. The formulated optimization problems often involve very large datasets, and hence computing the function value or the gradient can be very expensive. These
ADMM applies Gauss-Seidel like minimization strategy, which is related to the Douglas-Rachford Rachford split- ting method.
2

---

Under review as a conference paper at ICLR 2022
observations motivate the study of the randomized coordinate methods. The researches on this type of methods can be traced back to [Nesterov] 2012 2014). In (Nesterov] 2012). Nesterov studied the iteration complexity of the randomized coordinate gradient (RCG) descent method for smooth convex optimization. Later, in (Nesterov 2014), the same author analyzed the randomized coordi- nate subgradient method for set of piece-wise linear nonsmooth convex optimization problems. The works (Richtárik & Takáč, (014) and (Lu & Xiao, 2015) extends Nesterov's 's results to convex additive composite optimization. Iteration complexity and linear convergence of RCG were studied in (Patrascu & Necoaral 2015) and (Karimi et al., 2016) for nonsmooth nonconvex optimization and smooth nonconvex optimization, respectively. Moreover, by employing an asynchronous point to evaluate the gradient in each iteration, The works (Liu & Wright, 2015) and (Liu et al. 2014) establish the iteration complexity results of asynchronous RCG for convex smooth optimization and additive composite optimization, respectively.
Few results on randomized coordinate methods for linearly constrained optimization. Though the randomized coordinate-type methods for unconstrained optimization are extensively studied, there are only a few results for this type of methods concerning coupled linearly constrained optimization problems. The works (Gao al. 2019 Wang al. 2014) study the randomized primal-dual co- ordinate (RPDC) method and provides iteration complexity results for linearly constrained convex optimization. Better complexity results of RPDC were obtained for linearly constrained strongly convex optimization (Xu & Zhang 2018). The recent works (Zhu & 'Zhoo 2020 Latafat et al.)
2019 Fercoq & Bianchi [201 Alacaoglu et al.) 2020) provide almost sure (i.c., with probability
1) asymptotic convergence results of RPDC-type methods for linearly constrained convex optimiza-
tion. is worth emphasizing that the works (Latafat al., 2019) Fercoq & Bianchi 2019 Alacaoglu
et al. 2020) establish sequential convergence results (i.e., the convergence of the whole sequence of iterates).
However, the above mentioned works only considers either ADMM-type and APP- meth- ods for linearly constrained smooth nonconvex optimization problem or the randomized coordinate methods for linearly constrained convex optimization. To the best of our knowledge, no previous re- sult concerns convergence and iterate complexity of the randomized coordinate methods for linearly constrained nonsmooth nonconvex optimization, which will be the main focus of this paper.
Main contributions. In this paper, we aim to solve the large-scale linearly constrained nonsmooth nonconvex optimization problem (P). To tackle it, propose the Nonconvex Randomized Primal- Dual Coordinate (N-RPDC) method based on an auxiliary problem (see Section (2). Relying on the mild local uniform metric subregularity property (see Section 3.3 ), we provide two types of conver- gence results for N-RPDC (see Section 4). We first show that any cluster point of the sequence of iterates generated by N-RPDC is almost surely (i.e., with probability 1) a stationary point of (P). In addition, we also provide an almost sure asymptotic convergence rate of O(I/Vk), k). where k repre- sents iteration number. Next, we establish the expected iteration complexity of N-RPDC. Namely, N-RPDC needs most O( number of iterations in order to drive a surrogate stationarity mea- sure below E in expectation.
The fundamental aspect to our convergence analysis is surrogate stationarity measure we discov- ered for analyzing N-RPDC (see Section 3.1. which is one of the main contributions of this work. The standard stationarity measure (i.e., checking KKT conditions) is not directly applicable here due to the stochastic nature of N-RPDC. Instead, we define the notion of reference point and use its distance to the iterate generated by N-RPDC as a surrogate stationarity measure. Then, such a surro- gate stationarity measure is clarified by showing that it is an upper bound of the standard stationarity measure at the reference point up to a numerical constant (see Proposition 3.1 and Remark 3.I
There are also some other interesting techniques that utilized for establishing the above conver- gence results. For example, the utilization of the local uniform metric subregularity is crucial in order to deal with the nonsmooth nonconvex term g in problem (P). it is far from obvious how to prove the previously used error bound condition if g is not null (see Section 3.3).
Notations. We use (:.) and || || to denote the Euclidean inner product and the Euclidean norm, respectively. For a matrix A, its minimum eigenvalue is denoted by (A). The spectral norm of matrix A is denoted by ||- Let & be a subset of Rd We use projg(=) to denote the orthogonal projector onto S and dist 2, S) := infzes ||x 2|| to denote the distance between x and S. When
3

---

Under review as a conference paper at ICLR 2022
0, 2 = 0, we set di) = toc. Is(2) +00, $ represents the indicator function of the
S. is convex set, then the limiting normal cone $ is defined Ng(2) {E (5:5 S 0, JÇ E 8).
AUXILIARY PROBLEM AND PROPOSED ALGORITHM
In this section, we will define an auxiliary problem of PP. An important feature of the auxiliary problem is that it has exactly the same set of KKT points to the original problem (P). Furthermore, the auxiliary problem has better geometric structure, which makes it casier to solve. Finally, we will propose a primal-dual coordinate method based on the auxiliary problem.
Let us first present some preliminaries on the subdifferential and KKT conditions. Due to the fact that problem (P) is highly nonsmooth and nonconvex, general purpose is design efficient algorithm for finding a stationary point rather than globally optimal solution. Hence, we will define certain suitable stationarity measures in this subsection.
Recall that the function in problem is r-weakly convex. By Vial have
1983
Proposition 4.6), we
0g(x) --(=))))-) - TX,
where ht is the associated convex function such that g(x) 1x(x) - 1 ||]||3 (see Vial 1983 Propo- sition 4.3) for the guarantee of the existence of such function h) and @h(xr) the convex subdifferential. Thus, the subdifferential of weakly convex function is always well defined.
The Lagrangian of problem (P) can be written as
Ap L( p) f(x) g(z) Az - b),
where p is the dual variable. Then, we have the following KKT conditions for problem P
V + 0g(x) Nx(xx) A
0 OC(x,))
(5)
Ar b
A feasible point (r,p) X x R" is called a stationary point of P if it satisfies the above KKT conditions, ie., it satisfies dist (0, p)) 0.
2.1 THE AUXILIARY PROBLEM
Thanks to the construction used in (Bertsekas 1979 we introduce an auxiliary problem to P in
the following:
min ER
F+ F+ 2) f(x) + g((x= - _ || z||²
(P+)
s.t
Ar b 0-
where a > L.g + Pg is a regularization parameter.
We now characterize the set of stationary points of
P+
Towards that end, let (x, 2,
x Rd R². The Lagrangian of (P+) is given by
[t(w)= = L+ (x, 2) f(x) g(z)
511x: x 211² + (p, Ax b).
Thus, we have the following KKT conditions for problem (P+)
Vs(x) 0g(x))
(x + Nxxxx) AAD a ( - x)) Ar b
ATp
0 E OC = +
(6)
A point 2,P) E X x Rd x R satisfying the above KKT conditions is called stationary point of iP+ One crucial feature the auxiliary problem that has exactly the same set of stationary points as that of the original problem (P) which is presented in the following lemma.
Lemma 2.1 (relation between stationary points of (P) and (P) The following statements
equivalent: (a) (x" p²) is a stationary point of problem PR: and (b) (x* x','''''''''' ,p*) is a stationary point of problem
4

---

Under review as a conference paper at ICLR 2022
Algorithm N-RPDC: Nonconvex Randomized Primal-Dual Coordinate Method
Initialization: set x E X, z" E IR and p" E Null(A)) )); Step sizes 7), Ctz, and Otg.
1: for k k= 0, 1,... do
2: Update p as p = p + 11(xx* b).
3: Choose i(k) from {1,..., N uniformly random;
4: Update r and z through coordinate steps:
x=+1 arg min (Vi(s) + o(x" - =I >sk)) Ti(K)) + 95(a)(
DEX
+ Dar,
(phtl + 7(Ax - b), AC(o)
02
1
*+1
arg min
ZER (a(2* 2 )(K), (((3)) +
||
2/ 112
204
5:
end for
Proof. We first prove that part (a) implies part (b). Since (x", .p) is a stationary point of (P) we have 0 E aC(x*, pp"). Upon plugging = x" in the L* 2, p.p") shows that ff*((""> p=). The inverse direction is proved by similar argument.
The auxiliary problem be viewed quadratically regularized version of the original problem (P) with an additional variable z. Recall that f has -Liischhttz gradient and g is Py-weakly convex.
We have the following benign properties of the auxiliary problem (Pt whose derivations can be found in Appendix (A.2]
(1) f(x) + || =|12 continuously differentiable in (I,, with Lipschitz continuous gradient;
(2) F+ (2, f(x) ((x) g| 211 is weakly convex in (z, with parameter Ly + Pgi
(3) F+ is bi-strongly convex, i.e., (+x z) is strongly convex in for every fixed and Ft (z, 2) is strongly convex in 2 for every fixed x.
2.2 NONCONVEX RANDOMIZED PRIMAL-DUAL COORDINATE METHOD
As we established in the last subsection, problem P has the same set of stationary points as that of the original problem (P) and the former has a series of benign properties. These observations motivate us to design algorithm for solving the original problem by targeting on (P+) Similar
to standard primal-dual methods, our algorithm for solving problem (pt) builds on the following augmented Lagrangian of P
5+ (x. p) = f(x) g(x) -12 2112 + (p. Ar b) + 11 - b1l
With the augmented Lagrangian, our algorithm designed by performing an APP-AL update over (Ir, P) at each iteration. Furthermore, the updates for variables æ and are achieved through randomized coordinate steps. We depict our algorithmic i.e the N-RPDC method- in [
The proximal term D(r, ,² used in N-RPDC is the so-called Bregman distance function. Let 3x be the strong convexity parameter of the Bregman distance function D(r, It is safe for the readers to think xx = 1 I =11 2 for now. We put the more general choices of D(z, x*) in Appendix A.3
is worth mentioning that the subproblem for updating ++1 N-RPDC has a closed form solution once the Bregman distance function ((x, x*) 1| x=1 and (x();) ) is SCAD, MCP, quadratic, or norms with v E (1,2,0o).
Remark 2.1 (computational complexity). is claimed in (Nesterov) 2012 2 Wright 2015) that a co-
ordinate method can have much lower computational complexity than its full counterpart. Let us take the second motivating application (i.e., nonsmooth nonconvex constrained Lasso, problem (3) in Application 2) in Section aas an illustrative example show that the computational complexity of one iteration of N-RPDC with N = d can be much cheaper than the full primal-dual counterpart (ADMM-type APP-type method). Note that in this case, each X, is box constraint the coordi-
5

---

Under review as a conference paper at ICLR 2022
nate 24. Suppose we set (x, x²) = 2/1l2= x²11 Then, the update of w (xhtt , pp+t)) consists of: 1) phtl p¹ ns x((k) Fauun to (c((N)) az (A((A((s)) pk olak
=)((0)) + (Bi()) (ph+1 + + and x 1 ()((()) sht ")((()) where Ixem) is the indicator function of ((())- 3) kt1
*s(k) = 2k *(()) - -==0(=* ((())) with k+1 (zz((K) = z =)(((()) We also update the residual
vectors as p = p + Asx ((e) - ((())) and sh+1 s BB(N)) (2 ((k) (()) If we precompute
= Ar b and Sn' Bx c, and the proximal mapping prox,, Ix to admits closed form solution (which is the case when is the SCAD MCP penalty), then the above updates have total complexity ( n)).. Therefore, the complexity of N-RDC is d'x cheaper than its full counterpart (which has computational complexity of O(d max m,)) in one iteration).
3 STATIONARITY MEASURE, LYAPUNOV FUNCTION, AND UNIFORM METRIC SUBREGULARITY
In this section, we will establish a series of important results, which serve as the foundations for our later convergence analysis.
3.1 THE STATIONARITY MEASURE
Consider the current iterate w If w++1 is updated by the full primal-dual counterpart N-RPDC
(i.e., N = 1 in Algorithm 1. then the step length | - -++11| || is a natural stationarity measure due the facts that dist ac (0+((+++)))))))))) (w))
1+ with some step sizes hidden in the big-O and lime-+00 I - w I| O can be established by an easy argument based on an appropriate Lyapunov function. However, if wh+ is updated by our N-RPDC with N * 1, which is stochastic algorithm that only updates part of w to =+1 it is no longer obvious to show limg-++o I/ *++ = Therefore, due to the stochastic nature of N-RPDC, the step length I|l - -w*+1| cannot play the role of stationarity measure. This observation motivates us to work with a surrogate stationarity measure. Towards that end, for given point w the reference point of w Tww) (w,, TT,,, and
O(I
(x, 2, p), we define
(w) + 7xx b);
D x)
(ww)) arg min (V f(x) + a - 2). v) + +(v)) + (Tp()) -Ax + yEX
(8)
ax
(w(w) arg min (a(z r),u) + 20 lyy 2112.
yERd
One possible way to understanding the reference point is to let w = " then T(w*) is nothing else other than the next iterate =++1 if the full primal-dual method is utilized, i.e., N = in N-RPDC. However, it is worthing mentioning in the case where N >> 1. we do not need to compute the reference point T(w*) explicitly. Instead, N-RPDC only use block coordinate for updating.
The next proposition provides us a valid stationary measure, which is crucial for our later conver- gence analysis.
Proposition 3.1 (surrogate stationarity measure). For all w (x, 2, p) E X x Rd x R", we have
dist (0, ac (T(w)) S cllw T(w)ll =: ((w).
Here, T(w) is the reference point of w defined in (8) and v3 max { az + Ls + 20 +||A|| J.
LK
2|AA||+1 "
20,
a positive constant.
Remark 3.1 (interpretation of the surrogate stationarity measure). The mapping ((w) will serve as the surrogate stationarity measure for analyzing the convergence of N-RPDC. Particularly, it is clear that dist (0, OCt (T(w)) = 0 when & (ww) = 0. In order to characterize the iteration com- plexity of N-RPDC, we focusing on achieving Φ (ww) < E since it implies that w is e-close to the reference point T(w) which is an e-stationary point (here, Tww) is defined to be e-stationary since

---

Under review as a conference paper at ICLR 2022
dist (0, (T < E). These interpretations clarify surrogate stationarity measure. Note that similar notion of surrogate stationarity measure dates back to Ekeland's 's variational principle (Ekeland) 1974) and also appeared in recent advances of the analysis of the subgradient-type meth- ods; see, e.g., (Davis & Drusvyatskiy. 2019 Li et al. 2021). It is interesting to note that the main difference between our approach and the existing ones lies in the choice of the reference point. Let us take the approach used in (Davis & Drusvyatskiy (019) for analyzing subgradient-type method as an example. The authors define the proximal mapping of the objective function as the reference point, while we utilize the update of the full primal-dual method (i.e., N = 1 in Algorithm I as the reference point. Such a main difference comes from different sources of difficulties. The main difficulty for the analysis of subgradient-type method in (Davis & Drusvyatskiy (019) comes from the fact that this algorithm intrinsically not a descent method on the objective function, while our main difficulty is due to the stochastic nature of N-RPDC.
3.2 THE LYAPUNOV FUNCTION AND ONE-STEP ANALYSIS
Recall that the function F+ defined in
p+ is strongly convex in x for every fixed (see our analysis
in Section 2.1. Let us define
v(z) =
min =EX, Ar-b=0
Ft (x,
and x(z) = arg mrg *EX, A=-b=0
Ft (t,x)).
(9)
In addition, we also define
(2 = min L z,p) and x(2,p) = arg min L (2, =EX
(10)
#ex
where C is defined in
Next, mimicking the construction of the Lyapunov function used in (Zhang & Luo 2020b), we define
A(w) <J (w) + 2 (v(2) (z,
(11)
as the Lyapunov function for our convergence analysis. The first part of A(- is augmented La- grangian (w) of (P+). The second part is dual gap of (P+) with fixed Additionally, by the definition of v/, (2, we have that C+ (w) 2 (z, By the strong duality, we have v(2)= max (2, p). Therefore, we have the fact that A(w) 2 22))2
Standard analysis for primal-dual methods develops certain descent property on the Lyapunov func- tion. Before that, we first present preliminary one-step analysis for N-RPDC. Note that indices i(k), k 2, in N-RPDC are random variables. Thus, it generates a random output. We use
Fx (i(0), i(I)....,, i(k)
denote the filtration generated by the random variables i(0), i(A). Clearly, have Fk C Fx+11 We use Ei(R) and Ey, to denote the expectations taken over the random variable i(k: and the filtration Fx. respectively. The following lemma provides estimations for v(2) (2.p) and Lt) (w) after one-step execution of N-RPDC.
Lemma 3.1 (one-step analysis of N-RPCC.. Suppose 0 < az S //// [L, + 20 + 111 + 5] and
[1+00>11A|]++ LK For all k 2 0, we have
+1)
0 0<n 1 1/
2N
o-L1-Po
A(w**
2 11 )10 N
20
0
302
1 - -T2(w*>11
(12)
0 T.,
Pg.
+ Az( Io(w²)) - 6112
o Tp(w²()
x( x22²))²
where a is defined in 1 and X any positive constant.
Toward establishing certain decent property the Lyapunov function in terms of the stationar- ity measure ((w*), we have to connect all the terms on the right-hand side of the inequality of Lemma o² (wrk) = [To*= Thus, it remains upper bound ||<r(=* (=(
by 2x ))) bll. which needs the so-called uniform metric subregularity property.
7

---

Under review as a conference paper at ICLR 2022
3.3 UNIFORM METRIC SUBREGULARITY AND ITS CONSEQUENCE
Let us define the parameter set-valued mapping
V Vf(x)) ( + 0y(()) + ol 2) 2) +x((aa)
A ( )
(x,
(13)
-r
as the subdifferential of I, with respect to (z, p) with fixed z. Clearly, we have (x(s,)))
0 (r((z, p) - due to the optimality of p)) in (10. To proceed, we introduce the notion of local uniform metric subregularity property for the parameter set-valued mapping.
Definition 3.1 (local uniform metric subregularity, ef. (Kruger & Duy Cuong, 2021)). Let (y) U U=: V be set-valued mapping. We call that (u) satisfies the locally metric subregularity property with parameter (ò, k) uniformly over all E 2 if
dist (u, H. (0) E K dist (0, H,)) Vz E Z, for any u E {u' U dOst(O, (u)( Σ 6), where 6, k. > 0 are uniform constants.
(14)
This local error bound condition gives the following result.
Lemma 3.2. Suppose the set-valued mapping 0L., (xx,1) p) defined in 13 satisfies the local uniform metric subregularity property. then there > (independent of 2) such that K|I
[|x(2,p) x(2))| Ax(2 p) bll, whenever || (2, - bll S 8.
Equipped with this lemma, we are able to upper bound ||a((*,, (T (w("))
ar x=(*)|l by
||Ax(* Tp (T("))) bll locally in order to establish the descent property the Lyapunov func- tion. We will discuss this descent property in the next section. Now, let us provide the conditions on problem (P) in order to ensure the local uniform metric subregularity assumed in Lemma 3.2
Lemma 3.3 (sufficient condition for local uniform metric subregularity). Consider problem Suppose that V f(x)) is piecewise affine and 0g(x) is polyhedral multifunction and X is a polyhedral
set, then C (x.p) defined in (13) satisfies the local uniform metric subregularity property.
Remark 3.2 (generality of local uniform metric subregularity). This sufficient condition ensures that (x. must satisfy the local uniform metric subregularity property whenever f is quadratic (can be nonconvex, i.e., its Hessian is required to be positive semidefinite), 9 can be written as ||. || 2 1 Eg-norm, loc- -norm structure, and X is a polyhedron, which covers all the two motivating applications listed in Section
Remark 3.3 (comparison to the error bound condition utilized in (Zhang & Luo 2020b)). Recall that the work (Zhang Luo (020b)) considers problem (P) with g = O. They use the so-called dual error bound condition (see (Hong & Luo 2017)) instead of the local uniform metric subregularity property. However, we argue that it is far form obvious how to extend their technique to cover nonsmooth nonconvex case, as is not clear whether one establish the dual error bound condition if g is not null.
Remark 3.4 (further comments the surrogate stationarity measure Φ(w) defined in Proposi- tion 3.1). It is interesting that the sufficient condition in Lemma 3.3 also ensures that ac+ (w) satishies the local metric subregularity when (w) S with sufficient small æ (Robinson) 1981
i.e., dist(w, W) < n' dOs (w)) for some x' > where W the set of stationary points of
p+
Then, have (w: W) < (1/c x')e which follows from dist(T(w) W) & n's (due to < E) and the triangle incquality.
4 w
4 CONVERGENCE AND ITERATION COMPLEXITY OF N-RPDC
Equipped with all the machineries developed in Section 3 we are now ready to establish the conver- gence properties of N-RPDC.
4.1 DESCENT PROPERTY ON THE LYAPNOV FUNCTION
Upon invoking Lemma 3.2 in Lemma 3.1 we can derive the descent property in expectation on the I Lyapnov Function.
8

---

Under review as a conference paper at ICLR 2022
Lemma 4.1 (expected sufficient decrease for )²). Suppose that Assumptions of Lemma 3.1 hold. If the set-valued mapping 0 , (z. property (see Definition
p) defined in (13) satisfies the local uniform metric subregularity
3.1 Let À minf 20 oN² }. the parameter os satisfy 0 < Oz
1/ 20 +
Lo-s-pp + and 01 = min 11, 20)(xx22)++1 Then, we have
30
0-
A(w*) - Ae
||ue T(
4.2 ALMOST SURE CONVERGENCE RESULTS AND EXPECTED ITERATION COMPLEXITY
In this subsection, we establish the almost sure (i.e., with probability 1) convergence results for N-RPDC.
Theorem 4.1 (almost sure convergence result). Under the setting of Lemma 4.1 then
(a) limg- (ww") = almost surely.
(b) The sequence {w²) is almost surely bounded.
(c) Any cluster point of the sequence {w²} is almost surely a stationary point of Ap
In addition, we can also provide the almost surely asymptotic rate of convergence the sense of limit inferior for our N-RPDC method.
Theorem 4.2 (almost sure O(1/V)) convergence rate). Under the setting of Lemma 4.1 we have
limini v ((w)) almost surely k-+
i.e. the asymptotic O(L/Vk) convergence rate holds almost surely.
The almost sure convergence rate established above is of asymptotic nature, which concerns the behavior of N-RPDC when k > Next, we also provide the iteration complexity results of N-RPDC in expectation.
Theorem 4.3 (expected iteration complexity). Under the setting of Lemma 4.1 The sequence {w*} is generated by N-RPDC. Then
min Er x11²) S V oskst
cl++1)
Consequently, to achieve E, (ww) S E for some S I, N-RPDC needs at most (e(( number of iterations.
C16
Remark 4.1. Note that the closely related work (Zhang & Luo 2020b) provides a similar itera- tion complexity result (i.e., O(e²)) if = 0. By contrast, our results can deal with the additional nonsmooth nonconvex term g. addition, we also provide the almost sure convergence results, complementing the results in (Zhang & Luo (020bb. Let also emphasize that the main moti- vation of our algorithm lies in that N-RPDC is randomized coordinate method, which more suitable for modern large-scale problems.
Remark 4.2. The recent work (Zhang & Luo 2020a) establishes a global dual error bound condi- tion, which allows them to avoid the compactness assumption on X. Due to the existence of g. we utilize the local uniform metric subregularity rather than this dual error bound condition. To further relax the compactness assumption on X in problem (P), one possible direction is to establish a global version of the utilized local uniform metric subregularity. We leave this direction future work.
NUMERICAL EXPERIMENTS
Because of the limitation of space, we put the numerical experiments in Appendix A. We can observe that N-RPDC with larger N slightly outperforms that with smaller N in terms of conver- gence speed. We also compared our N-RPDC to the algorithm proposed in (Zhang Luo 2020b); Figure [ We observe that N-RPDC slightly outperforms their algorithm. Note that the main motivation of N-RPDC is that it is more suitable for modern large-scale problems due to its reasonably fast convergence speed and low computational complexity at each iteration.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Ahmet Alacaoglu, Olivier Fercoq, and Volkan Cevher. Random extrapolation for primal-dual coor- dinate descent. In International conference on machine learning, pp. 191-201. PMLR, 2020.
D.P. Bertsekas. Convexification procedures and decomposition methods for nonconvex optimization problems. Journal of Optimization Theory and Applications, 29(2): 1992)1199197, 1979.
Bernhard E Boser, Isabelle M Guyon, and Vladimir N Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the fifth annual workshop Computational learning theory, pp. 144-152. ACM, 1992.
Radu Ioan Bot and Dang- Shog-Khoaaaa Nguyen. The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates. Mathematics of Operations Research, 45(2):682-712, 2020.
P. Breheny and J. Huang. Coordinate descent algorithms for nonconvex penalized regression, with applications biological feature selection. The annals of applied statistics, 5(1):232, 2011.
Breheny and Huang. Group descent algorithms for nonconvex penalized linear and logistic regression models with grouped predictors. Statistics and computing, 25(2):173-187, 2015.
Pierre Carpentier, Guy Cohen, Jean-Philippe Chancelier, and Michel De Lara. Stochastic multi- stage optimization. At the Crossroads between Discrete Time Stochastic Control and Stochastic Programming Springer-Verlag Berlin, 2015.
Guy Cohen and Daoli Zhu. Decomposition and coordination methods in large scale optimization problems: The nondifferentiable case and the use of augmented lagrangians. Adv. in Large Scale Systems, 1:203-266, 1984.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3):273-977, 1995.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207-239, 2019.
D. DeCoste and B. Schölkopf. Training invariant support vector machines. Machine learning, 46 (1):161-190, 2002.
Deng, M. C. Yue, and A. So. An efficient augmented lagrangian -based equality-constraine lasso. In ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 5760-5764. IEEE, 2020, May.
bassd method for linear
Marie Duflo. Random iterative models, volume 34. Springer Science & Business Media, 2013.
I. Ekeland. On the variational principle. Journal of Mathematical Analysis and Applications, 47(2): 324-353, 1974.
Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association, ([(4566):334-1333 2001.
Olivier Fercoq and Pascal Bianchi. coordinate-dessent primal-dual algorithm with large step size and possibly nonseparable functions. SIAM Journal on Optimization, 29( 10011140-,,4, 2019.
B. R. Gaines, Kim, and H. Zhou. Algorithms for fitting the constrained lasso. Journal of Compu- tational and Graphical Statistics, 27(4))861-871, 2018
Xiang Gao, Yang- Yang Xu, and Shu-Zhong Zhang. Randomized primal-dual proximal block coor- dinate updates. Journal of the Operations Research Society of China, 7(2):205-250, 2019.
B. Haasdonk and D. Keysers. Tangent distance kernels for support vector machines. In Object recognition supported by user interaction for service robots, volume 2, pp. 864-868. IEEE, 2002, August
10

---

Under review as a conference paper at ICLR 2022
M. Hong and Z. Q. Luo. On the linear convergence of the alternating direction method of multipliers. Mathematical Programming. 162((-2):165- 199, 2017.
G. M. James, C. Paulson, and P. Rusmevichientong: Penalized and constrained regression. Unpub- lished manuscript, 2013.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewicz condition. In Joint European Conference Ma- chine Learning and Knowledge Discovery in Databases, pp. 195-811. Springer, 2016.
A. Y. Kruger and N. Duy Cuong. Uniform regularity of set-valued mappings and stability of implicit multifunctions. Journal of Nonsmooth Analysis and Optimization, 2, 2021.
Puya Latafat, Nikolaos Freris, and Panagiotis Patrinos. A new randomized block-coordinate primal-dual proximal algorithm for distributed optimization. IEEE Transactions Automatic Control, (1100)4450-40655 2019.
Xiao Li. Shixiang Chen, Zengde Deng, Qing Qu, Zhihui Zhu, and Anthony Man-Cho So. Weakly convex optimization over stiefel manifold using riemannian subgradient-type methods. SIAM Journal on Optimization, 31(3):1605-166) 1634, 2021.
H. T. Lin and C. J. Lin. A study sigmoid kernels for and the training of non-psd kernels by smo-type methods. Unpublished manuscript, 2003.
Ji Liu and Stephen J Wright. Asynchronous stochastic coordinate descent: Parallelism and conver- gence properties. SIAM Journal on Optimization, 2511):351-377, 2015.
Liu, Steve Wright, Christopher Ré, Victor Bittorf, and Srikrishna Sridhar. An asynchronous par- allel stochastic coordinate descent algorithm. In International Conference Machine Learning, pp. 469 477, 2014.
Zhaosong Lu and Lin Xiao, On the complexity analysis of randomized block-coordinate descent methods. Mathematical Programming. 152(1-2):615 142261,,,,,,6 2015.
Yu Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-32,, 2012.
Yu Nesterov. Subgradient methods for huge-scale optimization problems. Mathematical Program- ming, 146(1-2):25-299,, 2014.
Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87, Springer Science & Business Media, 2003.
Andrei Patrascu and Ion Necoara. Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization. Journal of Global Optimization, 61(1):19-46, 2015.
A. Rakotomamonjy, G. Gasso, and Salmon. Screening rules for lasso with non-convex sparse regularizers. In International Conference on Machine Learning, pp. 5341-5350. PMLR, 2019.
Peter Richtárik and Martin Takáč. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Mathematical Programming, 144(1-2):1-38, 2014.
Herbert Robbins and David Siegmund. A convergence theorem for non negative almost super- martingales and some applications. In Optimizing methods statistics, pp. 233-257. Elsevier, 1971.
S. M. Robinson.
Some continuity properties of polyhedral multifunctions. Mathematical Program- ming at Oberwolfach, 206-214, 1981.
Jean-Philippe Vial. Strong and weak convexity of sets and functions. Mathematics of Operations Research, 8(2):231-259) 1983.
H. Wang. A. Banerjee, and Z. Q. Luo. Parallel direction method of multipliers. arXiv preprint arXiv: 4064., 2014.
11

---

Under review as a conference paper at ICLR 2022
J. H. Won, J. Xu, and K. Lange. Projection onto minkowski sums with application to constrained learning. International Conference on Machine Learning, pp. 3642-364355 PMLR, 2019.
Stephen J Wright. Coordinate descent algorithms. Mathematical Programming, 151(1):3 3-,443334,,4 2015.
Yangyang Xu and Shuzhong Zhang. Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization. Computational Optimization and Applications, 70 (1):91-128, 2018.
Cun-Hui Zhang et al. Nearly unbiased variable selection under minimax concave penalty. The Annals of statistics, 38(2):894-942, 2010.
Zhang and Z. Luo. A global dual error bound and its application the analysis of linearly constrained nonconvex optimization. arXiv preprint arXiv:2006. /6440, 2020a.
J. Zhang and Z. Q Luo. A proximal alternating direction method of multiplier for linearly strained nonconvex minimization. SIAM journal on Optimization, 30(3)2222--2302, 2020b.
L. Zhao and D. Zhu. First-order primal-dual method for nonlinear convex cone programs. arXiv preprint arXiv:1801.002
2019.
L. Zhao and D. Zhu. On iteration complexity of first-order primal-dual method for nonlinear convex cone programming. Journal of the Operations Research Society of China, pp. 1-35, 2021.
D. Zhu, L. Zhao, and S. Zhang. first-order primal-dual method for nonconvex constrained opti- mization based the augmented lagrangian. arXiv preprint arXiv:2007.1223 12219, 2020.
Daoli Zhu and Lei Zhao. Linear convergence of randomized primal-dual coordinate method large-scale linear constrained convex programming. In International Conference Machine Learning, pp. 11619-11628. PMLR, 2020.
A APPENDIX
The Appendix organized as follows. Subsection A.1 discusses implementation details for N- RPDC and presents numerical experiments on non-PSI) kernel SVM and sum to zero constrained LASSO problem with SCAD penalty. Some properties of the auxiliary problem (P+) are given in subsection A.2 Some examples of Bregman distance function are given in A.3 Subsection A.4
shows the proof of Proposition 3.1 Subsection A.5 provides the proof of Lemma 3.1 Proof of
Lemma 3.2 is given in subsection AA6 Subsection A.7 provides the proof of Lemma 3.3 Sub-
section A.8 shows the proof of Lemma [.1 Subsection A.9 provides the proof of Theorem 4.1
Subsection A.10 gives the proof of Theorem 4.2 The proof of Theorem 4.3) is given in subsec-
tion A.11
A.1 NUMERICAL EXAMPLES
This subsection discusses experiments conducted using MATLAB R2020a on a personal computer with Intel Core i5-6200U CPU (2.40GHz) and 8.00 GB RAM.
A.1.1 NoN-PSD KERNEL SUPPORT VECTOR MACHINE PROBLEM
Consider the non-PSD kernel support vector machine problem.
min #t c
1 T Qx 1
s.t.
T T 0
where x. Rdd are the decision variables, and Q d d is a matrix, possibly non-PSD. Let Q [Q] QT ".. TT) E I be an appropriate partition of matrix Q and Q, be d; x matrix.
C of PSD kernel SVM can be written as
(w) = L (z, 2.p) = 2
Qx
x x
|| - 2112 + (p.v) TT x) + ? Ely x112.
12

---

Under review as a conference paper at ICLR 2022
heart scale
ionosphere
25
30
ADDMM
minossessdaat(O aL, (1wk)
ADDMM
20
N =10
=100
N -90
20
N770
mingsks 4
15
10
10
0
200
400
600
0
200
400
600
epoch
epoch
Figure 1: Evolution of minogiee o (w*) versus epoch counts for several different choices of (i.e., the number of blocks in N-RPDC), where nADMM refers to the algorithm proposed in (Zhang & Luo 2020b). Left: dataset heart.scale Right: dataset ionosphere, The results are obtained by averaging 50 independent trials.
3.3 for problem Non-PSD kernel SVM, aC;; is locally metric subregular in (I, 2) uniformly in point O. N-RPDC with D(x,x") 2 311x support vector machine problem is
Thanks of Proposition
I²1 for non-PSD kernel
p* k+1 + pp n7y x²;;
Choose i(k) from 21,2,... NJ with equal probability
gh+1 min (2 (Qi(k) + oax* - -x ))())))))))))))))(0)) Idecs + (1(k) (1 ry x²) ss(ss)
zE|0,c]a
1 || 11
20
k+1
min =ER
(a(=* x x²) Dick)) 2(())
|| 1
20x=
Thus, the primal subproblem of N-RPDC has the closed form
- az Queaya o( - )200) - Inses (p" + +yy x (810))))) ]
k+1 2 ((k)
= II ((A)
Ik (i(k)
A+1 .k jpi(k)
{((()))
and
k+1 = (i(k) - a2 - x² )())())-
(ik)
R+1
((((() =){((K))
We used LIBSVM dataset cheart_scal. and ionosphere the experiment. Q was generated using the sigmoid kemel (Lin & Lin 2003), and we selected 1. We compared two algorithms: nonconvex ADMM in (Zhang & Luo 2020b) (nADMM), and N-RPDC from this paper on these two datasets.
For N-RPDC algorithm, we partitioned the variables N 10, 90 blocks for heart. scale and N 10, 70 blocks for ionosphere.
In order to verify the theoretical results of this paper, we compute the sequence reference point [T(w*)} along with the sequence {w*} generated by N-RPDC. In the real world applications of N-RPDC, the reference point sequence is not necessary to compute. In Figure I the left graph show the number of blocks and minogAge $(w*) with respect epoch count for heart sca le; the right graph show the number of blocks and minogkga ((w*)) with respect epoch count for icnosphere. For both datasets, minock<: ((w*) of each epoch of N-RPDC is the average value of 50 times result. Moreover, we can draw the conclusion that N- N-RDC slightly outperforms ADDMM and larger N is slightly outperforms small N.
13

---

Under review as a conference paper at ICLR 2022
A.1.2 SUM TO ZERO CONSTRAINED LASSO PROBLEM WITH SCAD PENALTY
Consider the sum to zero constrained LASSO problem with SCAD penalty:
(CLASSO-SCAD)
min =E|-1,11
21l b1l + Σ d(a))
s.t.
1 = 0:
where I E Rd is the decision variables and A E IRnxd is the regressors matrix. Let A (A1, Ag.... AN) E Rn x be an appropriate partition of matrix and A; be an n d; matrix. b E IR" is the response vector. 1 is an d-dimensional vector of 1s. 6(-) is the SCAD penalty:
14]
14| <
- -20
<(1)) =
1< | 1 LER
2(0-1)
1+0
||| > 0.
t of (CLASSO-SCAD) can be written
n
= CT,)),
Az 6112
Σ ((xx) + / 5111 =1| + (p, 1/ ( 2117
Thanks of Proposition
3.3 for problem (CLASSO-SCAD), ac² is locally metric subregular in 2. uniformly in 2 at point O. We take D(x, x²) = ||æ - 1²1 and construct N-RPDC al- gorithm for (CLASSO-SCADD
following:
pd k+l + -
Choose i(k) from f1, (1.2..... N with equal probability
x+ll min (AT (Ax - b) + ol* 2² )(RR + 1a, (g) x:(s))
-E(-1,1j
+
Σ
(x,,) + 1|:0 - -m11?
20x
d2
1
k+ min
(a(2*
x* )(R) 2(())) +
|| 112
=ER
20x
where / +1 + 7 [[ x* Thus, the primal subproblem of RPDC has the closed form
(s) @ max(0, 15 - plda,)) 11 ccc {
15* S 1 + μ
k++ [i(k)
Aoo ( f- [(0 1)c* p
1 1+ μ < l se
4- {5*}
|c 0
A+1 })((())
with <h ((6))
aulATiy (Ar* - b) + o2* - )((k) + Imin and μ az.
k-1 =((K) a20 x )()))));
((()) }zz((k) z)(((H))
In this experiment, the elements of A E Raxd are selected i.i.d. from a Gaussian / 1) distribu- tion. To construct sparse true solution xt E Rdd given the dimension d and sparsity 8, we select entries of x² at random to be nonzero and (0, normally distributed, and set the rest to zero. The measurement vector b E R" is obtained by = Ar" + ő with the elements of the noise vector 6 R are i..d. (0, 0.001). We choose 0 = 2.3 with dataset and n = 720, d = 2560, s = 16 for the second datasct.
360, d 1280, 8 for the first
We partitioned the variables N 10, 40, 80 blocks. Thus d; 128, 32, 16 for the first dataset and d, = 256, 64, 32 for the second dataset.
In order to verify the theoretical results of this paper, compute the sequence of reference point (T } along with the sequence {w*] generated by N-RPDC. In the real world applications of N-RPDC, the reference point sequence is not necessary to compute. In Figure 2 the left graph
14

---

Under review as a conference paper at ICLR 2022
d=1280.n=360,s
d-1280,n=360,5-8
0.1
0.5
N 10
N 110
0.08
=40
0.4
N 40
minggieg 4 (1x))
-80
minnogle 4 (w
N=80
0.06
0.3
0.04
0.2
0.02
0.1
0
50
100
0
50 epoch
100
epoch
Figure 2: Evolution of minucAse ((w²) versus epoch counts for several different choices of N (i.e., the number of blocks in N-RPDC) on synthetic dataset. Left: n = 360, d = 1280, = 8. Right: n 720, d = 2560, 8 = 16. The results are obtained by averaging 50 independent trials.
show the number of blocks and min ((w") with respect to epoch count for the first dataset; the 05k5t
right graph show the number of blocks and min ((w") with respect to epoch count for the second 0
dataset. For both datasets, min (w**) ) for each epoch of N-RPDC is the average value of 50 times oSkst
result. Additionally, we can draw the conclusion that larger N is slightly outperforms small N.
A.2 SOME PROPERTIES OF THE AUXILIARY PROBLEM
P+
The auxiliary problem can be viewed as quadratically regularized version of the original problem P with an additional variable z. Recall that f has Ly-Lischhitz gradient and g is Py-weakly convex. We have the following benign properties of the auxiliary problem (
(1) f(z) + g1 - 2|I is continuously differentiable in (Ix 2) with Lipschitz continuous gradient;
(2) F+ (x, = f(x) + ((x) + a| - =1|2 is weakly convex in (a, 2) with parameter Ly + Pgi
(3) Ft (z, 2) is bi-strongly convex, i... F' F* 2) is strongly convex in x for every fixed 2 and Ft (z,2) is strongly convex in for every fixed x.
The first property is trivially true. To see the second property, we note that the LipLscchtttz gradient
property of f implies that (xx 2 ((y + (8, y) - yll2 Vx, E IRd (Nsterovv) 2003
Lemma 1.2.3). This, together with [Vial 1983 Proposition 4.8), establishes that f Is Ly weakly c Fl By (Vial [983] Proposition 4.1), we have that f + g is weakly convex with parameter Ls + Pg- We have shown the second property y recognizing that 2) + _| =||² is convex mapping. The third property is a direct consequence the definition of weak convexity, which
yields that f(x) + 9(x) g x 2|I2 is (L, + Pg) strongly convex in 2.
A.3 SOME EXAMPLES OF BREGMAN DISTANCE FUNCTION
The proximal term D(x, x²) used in N-RPDC is the so-called Bregman distance function, which is defined as
D(r, K K(x) - K(**) (V -*))
Here, Rd R the core function, which is 3K -tr-olrygyyy convex and has -xpLiishhitz continuous gradient on Rdd One popular choice of the core function is K K(x) = 2 ||=:11 which yields D( = ج| 11 However, more generally, the core function can also be selected as the Q-quadratic proximal regularization term K(x) 1 || l.. where Q is positive definite matrix. This choice covers some second-order methods as we can set Q to be the regularized Hessian matrix.
AAttually, this derivation verifies the fact that any continuously differentiable function with L- Lipschitz continuous gradient is T--eakly convex.
15

---

Under review as a conference paper at ICLR 2022
A.4 PROOF OF PROPOSITION 3.1
Proof. The optimal condition of
Tr (ww**) arg min(V/ (x**) + - ((x)) (Tp(w* 7Ax - b), Ax)
D(a
az
and T3 (w("x) = arg min -z) + 2011 || 12 yields that
=E
0 Vf + (o (w))) + o0 - 2² Nxx(TT("))) + + (T((") + +((Ax* b)]
1 - VK (1)) VK(**)]
02
1
0 0= - x²) +
- (Tx(w*) - =²
022
Let
&x Vf(Tx(w*)) (f((t) + o(Ta(u()
() o(x* -xxx-2t -7A "AT(AA b)
as -
Vf(Tx(w")) Vf(x*) + (Tx Tx(1*1) oxx* - 2/ _AAT )
- -p²)
77
1 -
(15)
0g
6.
- -(T((wt)-Tx(u") - olz -xx)
-- (Ta(w>)) -z
1
(16)
az
and
1 - - -1 A(Ta(w")) - x
9, = 17
(17)
Then have that
[=(=*)) + +N2(TT((*)) εx Vf(Tx(w + (g(TT(( -
+ A ATTT TT(");
(T2( (T(l=*));
&, AT=(w*) b;
By the expression
15 17) of &
02 and are given posi-
tive numbers and Assumptions
of problem there exists positive number
v max {
1 20, ~||A|++1 and the following incquality holds { LK. + L, + 20 + ||A||: a.
|E|| < cllw* T(
Combining Ec+ (T+(() and it follow the desired statement.
A.5 PROOF OF LEMMA 3.1
order to provide the Lemma 3.1 we need the following two propositions as preparation.
Proposition A.I (Lipschitz properties of a<>) and a(2zp)). Suppose a > Ls + Pg. Then
(i ||x(=) - x(=')l S - || 2'11:
(i)) [|((2,)) x(2'.p)] S --(E)+og) ||= - z'1l
16

---

Under review as a conference paper at ICLR 2022
Proof. (i)
with X = fxr X|Ar - b- = 0}. Since
a > Ly + Pg. we have 0z b4 convex in z. Therefore
(x((=),²) - (=((2),==
(x((2), - 2 (x(x),=) ( - 10 (x(x)))) (x((2)),,) [llx((2) ='12² -|0( (z(2). - (x(2),
-
+2 [||x(2²) - ==1²= 1-======)--- - -
- - t - 2, 2,0(²²) - x(())
(L, + Pa) ||+()) r(2')1] + o0 2, x=22) - xx)))
Again using the strongly convex of ((x 2) in x. we have that
(L Pg) [1x(2) - x=2')11
(x(x),)) (x(22),
2
Therefore
[ax(2) x(=')ll
a
1|2 =
0 0- pg)
=) (ii) Let (ex, 2. = C 2x), (x))). Since > L, Pg. function sp 2,p) also is (Ly
Pg) sttrongly convex in Therefore
((x(z,)),='.p) 4 (a< ,2),
(=((t..)),' y 2,]] -
+lx - -<(('',)),'''p)
= 2 [1]x(2,p) - 1 (t(2.))==1+ + (z(2,)), - - 2)pp)
11 (1)) - =|1 - ())(='))) - =
2
= 10 (x( 2,p) 4 (a(2' x), + tz 2 (2''2'''') p) s(z,p))
s (LD + Pg) |,(2,p) =(==, p)1 0 - 2, x(= p)) - <(2,
2
Again using the strongly convex of ((r, in x. we have that
(x((,,)), 2' .p) 1 (x(s', 2), -- (Le Pa) | x02' 1P112
2
Therefore, ||x(,,p) =<2',p)]1 S [ || 2'1l.
Proposition A.2. Suppose Ly + Pg. Let {w*} } be generated by N-RPDC. For given wh the primal output (x*+1 1) are random variables, and the following assertion hold:
L t0 + +111
Lg.
| - x(2" TT((w*))]l
+1 1aat- Tx("*))l.
(18)
σ L
Pg
Proof. Since s0 TT(w*)) = arg min (+ (2, * Tp(ww)) and Ct 2, () is - -sy-srngglyy
NEX
convex in æ. then JG (Q + N2
have that
(a - 1, Pg) ( x(2" ()("")) s (V - + ç, T.T. x(2² T,(w))))
+(A (T)((x))))))) (A - 6)]. (w - =<* ((=*))(("*))
follows that
(a (o- (,,(,")))"")))))
< [V (TT - xx + A [T (AT, bb]]l
Again using the optimal condition of
17

---

Under review as a conference paper at ICLR 2022
T3 (w = arg min (V (v/(x*) + t - =; + (((x) + (Tp(w**) + >AA -b), b), Ax) + D(r,a"
ZEX
we have that
0 E Vf((*) + (g(TT(("))) +
- - + A [Ip((((**) + *Axx 6]]
- ax - -VX((()
Therefore
Vf([x(w*)) + ( - 0g(Ix(w + + N2
(x= + +7(TT, -b],
with
- 02 VK(Ta(w*)) < = V](((ww))) - V/(x*)+ o (Ta(w x²) + 7 A(Tx(u=*) - - ). By Assumptions on (P), we obtain that
LK _x 112 To(w")ll
| - (L, + + +
ax
and
"o(=",Tp""") (T - L, + + 7 |||
LX
(T²" - (
nr 1| - (a(w
σ L,g Pg
Then by the triangle inequality, above inequality yields the desired result.
With these two propositions in hands, provide the technical proof of Lemma 3.1
Proof of Lemma 3.1
Step 1: Estimate the term L (w**) - Bi(CK) Litt (w)++). By the dual update of N-RPDC, we have that
(=t 2 - (** 2b pht1)= (pt pptt1 Az b) -00--110 11p 11
(19)
Since x++1 1 is the solution of subproblem of a in N-RPDC scheme, we have that
(Vi(s)((**)) + ox )i(k)) (x - xx=xx""0 (((s)) + Be())(11 - 9i(k) (=(()) kt1)
1 - D(x,,*)) 1 D(x , ) 2 0
+ + +(Ar* b), (x x + +
(20)
Oz
Take x in 20), by the fact that gi(h) (1)(2)) 9u(k) (t1))) -((x*) -g(x+t1)
and
V (())f(**) + ol** - ==*) + (Air)) Tip 1 + (Ax* - b)], (a*k x )(1))
= (V)(a*) oa(x - + A A + 7Axx=* - b)], x x1t1),
=²
we have that
)* - - + g(xxt) g(ahtl) + (prt1 + (AAr - b), A(x* * - x(tl)) (Vf(x*) oz - (
1 D(a k+ ,x 2 0
ax
It yields that
(2gtt) Ft (b - + (p++1 (
>(Ax - A(x - xntt)))
1 D(1 , ) - [f(x)t1) - f(x²) - (V)(z"), x++1
k+1 - -x²11
12 - 11
Og
2
0x ax (T.f + t0) -
20
18

---

Under review as a conference paper at ICLR 2022
Since (rxA - b), A(x 2ltl)) (11Ar* - b112 - -11Ar - b112 + ||A(2* 113), therefore
(1 ,e,,, L.t (afttt, ,²th xett) BK 5x- (Ig to 711 ?11A113) || 111111
(21)
20z
Additionally, since 2 1 is the solution of subproblem of in N-RPDC, we have that
(a(c" -x x²)) )s(k): (2 + + 12 -
, 2 2 0.
(22)
as
Take = = ² in (2). by the fact that (a(** - x )()) (=* - = = (0(2* - -xx)),,, ) 2t =
have that
1
(a(** ,0)),² - 2ttl 2 -1 11 -
a
Since
(a(** x²),² 2* 2lt22-
(a(z xxt1), ) st 2k + (a x²t) 2t 2ktl)
(1 2²112 - || - 1 + 11 - 112)
+ (a( - x )²²,,²² x² - xt1)
(112 - 2/113 || - 2 2 + 1| 22+2
2 (11x. -x** - + |1 - 112)
(1 - x || ++1 - 11+ + 00|=* - 1/
10 -1²+11?
2
above inequality yields that C.t (a 2t 2x. xt2) L:t (1+ k+1 p )11
(1x - 2/112 || -2tt1 112)
- o)]l - 2 a I1rt - 112
0;
2
(23)
By the combination of (9
21 and 23
we obtain that
C+ (1x ,² * .p' L.
(5
+1
R+1
1111
Ax - (Lg + 20 + )
1|
x 11 + +(- ( 0)|l2* 211
-
-11---111- 11p0*
1 1112
2
0g
")
Take expectation with respect to i(k: both side of above inequality, have that C (x* > )²*) - (x(() C, (att1 k+1 ,p xt1)
8x
(Ls + 20 ))
Ea - 22 + (- o F - 112
2 a,
2
02
1
110
112
77
By the fact that Es(a) 11 - x² x 112
b 11 (1( Es(as - 112= -1
- -T2(w*) 112
and p*+1 (w())), above inequality follows that
c (at 2 ,p*) C, (a -ttt1 . p(t))
8x
(Lg 20 + 11)
1
|1at - Ta(w>>)12 +
N (- =*)l=* -T(
2N
0=
110p
Tp )12
19

---

Under review as a conference paper at ICLR 2022
Step 2: Estimate the term v=²*)= 1(2*+1). ). By the Danskin's theorem, we have that Vr(z)
a (2 - =x))). By statement (i) of Proposition A. we have that
[Vr(z*) - Vu(=*+1)]| - و Pa +o) 11 -
2/11111
The gradient Lipschitz property of follows that
+ -2) 12a 20. (24) v(z*) - v(zh+1) )) 2 as* xx(²), 2t 2 - 2((0 L, -Pg) 2
a²
Step 3:
Estimate the term (y petz) ((tht),ptt))
vir(sh,p) pt). Since a(2
arg min L (z, 2 p*), we have
zEX
(2 tt - uy( phtt)
ct(x(=ht) pp xt),, ) 2 2t1 ip xt) L (a(=** (lll=,pp""""" -pt 2t, 11t2)
ct((tttt ), ,,tt) ptt1) c (a(z)tt1 (/ ,p/t2), 2h phtt)
2 (1x(( ,p )) = - |
kt1 p p - =x/112)
2 0l2 x(2 .p ), x+1 2²
(25)
By the concavity of (2, and (2,p) Ar(z, p) b, we have
() pht1) v5 .p*) 2 11 - p² Ar(z² ",, px+1)= - b)
_ 11 1 2 Ax* p b11
1
21
2
1 1p - p² A/xx( . pp+t) b]112.
2m
By the dual update of N-RPDC, the above inequality yields that
4/y
p
++1)
-
l1p* p 21 + -/ Ar( " xt1) - -b122 - - -| A x02* ( )+1
1
27y
21
1
1pp -p + " AAt(** ppppp) - -b112 - ||112 11 - xx(h )1. (26)
2m
2
2
By Proposition
A.2
26
guarantees that
M/y p (+1
(2
2
+ 11, + !? 21 1pp
1 (xt -112
ph11
2
L1 + + + ?|1A|1 2 +
Lx
3 |A|2
as
+1
1|00 - To (2(*x)) 112
2
T.g Pg
(27)
By the combination of (5) and 27 obtain that
1by (=*11 xt1) v/y(2* p²)
2 0l* - x(
k+l ,11t) - ++l 2k) + 2m
11 -p=t11
L + + 7/11A112
Lx
+1 )
2
+ ! 2 -Ax(t (pt1)) -b112 - 111l
11a
- (u
σ L1 Pg
(28)
20

---

Under review as a conference paper at ICLR 2022
Step 4: Estimate the term [x(2*) - (2 pp']] - E, (. [1(2 12(( ,0t ,ph+))]
Summing
statement (24) and 28 we obtain the variation of dual gap:
[r(=") Dhy (2" p [1( - (2 +1 .p 1]
(x((ztt1 k+1 1 - x(2²)), - - 2 Lis pg)
+ 0
11 - 11
2
1p 11 112 + 1/2 A1(== ,/,,,,,,
?
(e((==pptt] pptt))= - bl12
21
Lap +o o 71 All + az +1) 1| - (Tx
2
|All
(29)
2
Ls Pg
By Proposition
A.1
we have that
0 (x( p )) x(2 ) 2/ - 21
o (x= * p p xx=² )==)),²= ) - -2tt1 + (xr (e
.pttt) - xx6" xxtt,,ptt) ppt1), 2h - x
m 2\ 1|2 111 0d |a(=" .1 ) x(=*)|²
2
o || k -
- ||o( , +1) =0(zt11 , ,
2
0 +
o²
|| 2 ad || 1)
)) x12
(30)
2X
0 Lg Pg
2
with A > 0 is any positive number. By the combination of and (30.. we have that
[u(2*)
- - (2 p 1
0
+
2( L.--spp Pg) + 1
30
) 11 - -2
σd
|| 11((="pptt) p(tl) - 112
2X
2
1pth
k
pd 1+
112 + 2 A1r(( (hkx(="pb/tt) ) blb -b12
!7
21)
LB + 7||A|12 2 +
Lx as
2 )1(
-
!
1112
+
11
(31)
L L Pg
Take expectation with respect to i(k) both side of above inequality, we have that
(x(2*)
(1 1.=,pp" p²]] Bi(k) ((())((((()))
(2 .p
[1]]
302
= σ) |a(2 xx - x1²
+ 2
21
2(0 - Ly -Pa)
2
1pt
1 + 1/ 11 (p,,tt))) bbl2
2n
Tof + a + 7|11112 + Lx
2
--2 I1111
a=
+1
11 TT(w">>1
σ O-L,- L1-
By the fact that Ex(A)ll** follows that
=121112 11 (2 and p = Tr(w*), above inequality
(2(2*)
(1 ,p''] Bi(N) (2 44 (2*+1,p""*)
1 ④
+ 2 pp) + 2) 11a -Te(w*)
30²
σd |a(2* Io((w()) - x122))11
N
21
2
l,p*
TT( + + Ax(z (Tp((())) b1l2
2m
(I
[L. + a + 1| +
Lx 2
--
||1112
os
+1) 1|
(32)
- L, Pg
21

---

Under review as a conference paper at ICLR 2022
Step 5: Estimate the term A(w*) - Be(x))(whht).. obtain that
By the combination of Step 1 and Step
(ww²) - (e(()) ((w
SK
(Ls + 20 + -]1AA1²
L, + 0 + 7|1
+ Lx
+ 41) )
27 Tu(""
A||
1
2N
0 L1 Pg
1
20
0
30²
11 - T Te(w0)) 112
N 0g3
- 1, py.
AzllAA(2** Ip(x")) -b1 -o>llz(>>* Ip(w")) - )12
(33)
Since < az S 5k/ 20 + 7/1A112 5]. then
8x
(Ls + 20 + +1|l|1? 2 Moreover,
as
2 Ly 1ytot>lld| Lp- + +1) implies
0 p<
Aww*) Eux))(w**)))
2
1
302
N 11 k - (T( +2
20
11 - (w=))(1
N
02z
X
0 Ly Pg.
tnllAx(2* ) - b11² - -o\lI=(2² (T(("")) - 112
(34)
A.6 PROOF OF LEMMA 3.2
Proof. The result is directly by the fact that dist (0, 8C; (z(2,)), ||Ax(z, b/1-
A.7 PROOF OF LEMMA 3
Proof. The claim is provided by the results of Proposition 1 and Corollary of (Robinson) 198] 1.
A.8 PROOF OF LEMMA
Proof. Taking = min
87g
1 and 0 < az < 1/ 1/(20- + + o- 1
30
in
20 M1 + ox
Lemma 3.1
have that
A(w*) AE
2
2 N
11aa - Tz (u
+ N 11 TT= + Ax( ,Tx("")) b11
minf
20 +1' OR? + 1= (T,(""))) - )1
8n
"
(35)
For the last two terms of above inequality, we have two cases to discuss.
Case 1: ||Ax(** (y( bll Ar
< 8.
Since (x, is locally metric subregular in (x., p) uniformly in z over TRd at point with parameters K. O. (35) yields that
A(w²) - A(w+)) 2
N 1 Ts (2 + // N 11 - -Te(w*))
2
+
"
allll A - -61l2.
(36)
ON² +
Case 2: ||Am(** (y(w)()
b1l 2
7
22

---

Under review as a conference paper at ICLR 2022
Since M max || 2'11, we have that
2, a,a'ex
A||Ax(=* Tp (p((w()) b112 - aa1 =p((w - (1
" Am(=" Tp(u= b112 + "
2 " o\M2
2a Ax
||x Ip(w=*)) bl1
(37)
For both case,
35 yields that
A(w*) A(x
| (w
1 011 - -T
7
Al ,T,(""))) - -b12. (38)
Ok² +
By Proposition
A.2 above inequality yields that
A (w*)
Ax
2 N
11*
)1
2 11 -x(="; (1
'x
N
az
+ N
1
11 T=(W=>)1
11
|Axo( To((o))) bb12
+2
2 N |, -Ta(w*)]12+
|A( - -x( (1)
Lyto+1|1||+++ LK
A|
o-L1--p +
+ N
1
11 - -T(w*>)1
+ OK +2
7
|Ar(s* (Tp(w=)) - 611
2
N 11a - (1* + N 1zz - -Tx (x )12
+ 2(on² 22 (2)1A(+* - x((* ,
"
(2= 1)12 + 2 Ip(w*)) -1l3)
2 11a [T(
+
N 11* -=(w=*)] 2(ox² + 2)
1
"
AAr bbl
N
= N 11 )1(
+ 1
N 1 - - 2n( 22
1
11 - -Tp(x*))²
2 C1 1 - )1,
(39)
N
with c min {1, 21(0n ).
A.9 PROOF OF THBBREM 4.1
In order to provide the Theorem
we need the famous Robbins-Siegmund theorem.
Theorem A.I. (Robbins-Siegmund Theorem, Robbins & Siegmund (1971,, Theorem 1.3.12
in Duflo (2013), Theorem 2.27 in Carpentier et al. (2015) Let (A* Jee,, (pt)eeN, {u*]eeN and {nr" Tke be four positive sequences of real-valued random variables adapted to the filtration [Ex)EEN. Assume that
Bg. ARtA h+1 < (1 + +1+1 s x², VkEN,
and that
E1t < to0 and Σ vt t00, a.s. KeN
KeN
23

---

Under review as a conference paper at ICLR 2022
Then, the sequence {A* TEe almost surety converges to a finite random variable A and Σ
n
KEN
+00, a.s.
Then derive the technical proof of this theorem.
Proof of Theorem 4.1
(a) By Lemma 4.1 and the fact that A(w) F*, we have that
Eass) B( F*] I [A(**) F=]
C1 T(w*)) 112
w
N
By the -abbins-Siegmund Theorem (Theorem A.
we obtain that, lim A(w*) is almost
k-+oo
too Σ I| T|w")]2 < +o0 a.s.. Therefore, we have + F(w*)) O: k=0
surely exists and
(b) By the compact of X, we have the sequences {x*) and {x(²*)} are bounded.
By statement (a), we have lim A(w*) is almost surely exists. It follows that the sequence k=++0
{) is almost surely bounded. By the definition of A(w*), we also have that A(w*) 2 v(=*) F(x((*)) 2 F*. Therefore the sequence {u(=*)} is almost surely bounded.
Now we show the almost surely boundness of the sequence {2*} by contra- diction. Suppose P [[I=*1] + +oo}
0. Since the sequence {a(=*)} is
bounded, there exists a subsequence (=*}} such that a==*') + T. Therefore P (
+ (x(**)) 2K 1|? - + > O, which follows contradiction
with that (u(=*') is almost surely bounded. Therefore, we obtain the almost surely boundness of the sequence )
Next we propose the boundness of {p*}. By the optimal condition of problem of Tg (w*) = arg min(Vf((*) + ol )*), x) + g(z) + (Tz(w*) + x(Ar bx) D(z,='), meX
a we have
=²) + Og(TT(w0*)) + 0 E VS(x') + ta -²")
)) + [T,(W ((x* -b] b)
1 VK vK(2*).
Since (w**) = NB (N 1)x* and the boundness of the sequence {a*}. we have the sequence (T, (T=(w) is bounded. By bounded of subgradient of g, the boundness of {a*), J. (Tx (w*)) and the almost surely boundness of {**}, J. it follows that || (TTTTT("")) < to0,
Wk: > O, a.s.. By the fact that p*+ = (w*),, we have that
IA 1 t00,
Vk > 0,
By update of p in N-RPDC, we have that
p+1 p. + gh+11 when
p++ (Ax
-b) b) n Σ (ar x²) Tm((A,
with x² be the optimal solution of (P Since pd Null(AT), we have AT ATD0 0 and | g < +00, a.s.. Then we have two cases to discuss.
Case 1: rank(A) Obviously, we have that
1 S ||A ||ATTt+111
< +00,
Vmii(AAT)
be the smallest eigenvalue of matrix AAT. Case 2: rank(A) = < n. Without loss of generality, assume the first r rows of A (denoted by A e grxd) are linearly independent, we have
with Amin (AAT) (AA
A Ar
) ( Fxr A"
BA"
AA random variable X is finite if ([w E ()X(w)) = +oo3) [++]))= 0.
24

---

Under review as a conference paper at ICLR 2022
where Ixr R is the indentity matrix and B R( Let Q := 1xxr +B² B. It easy to show that Q is symmetric and positive definite. By the fact that pl 17A Σラ= (x) x²), we have that
| pp
(A7) (Lrx: (
1xxr B
A"
x
x
j=1
(1)) "OnT" Σ
*
(x0 -x")
5=1
Amin (AT(A)) QmA" > (2v - x²))
Amin (AT(A")T) Amin (Q
(QQQQ) Q))AA
> - x²)
where Amin (AT(A))T is the smallest eigenvalue of positive semidefinite matrix A (Ar))
and Amin (Q Q) the smallest eigenvalue of positive semidefinite matrix QTQ. Q. Using the fact that
1 = II
Σ j=1
(x)
x 112
Irxr
||n
A'
(x) -x')
B
S Amax (Q) IIA"
Σ ( -x))1
where Amax (Q) the largest eigenvalue matrix Q. Therefore, we have that
Amax (Q)
1 k+ 1 < Amiu (AT(AA)) Amin (QTQ) 11 8t 112
Therefore, for both cases, there exists ò > 0 such that
|| s 0|| p a.8.
which yields the almost surely boundness of {p*} by the triangle inequality. Therefore, the sequence {wr} is almost surely bounded.
(c) By lim I|=* T(w*))l [| = a.s. in statment (a), Lemma 2.1 Proposition 3.1 the almost k-+00
surely boundness of {w*), and the closedness of a2 (-), we obtain the desired result.
A.10
PROOF THEOREM
Proof. Suppose this statement does not hold, that is,
IP inm /k (w 8 0,
+00
for some 0. Then for ko large enough, for all kn have
Rf (
v 0.
Therefore
4000
400
+00
82
IP
(
()
(
))
Σ
0.
1
k=k
25

---

Under review as a conference paper at ICLR 2022
+o0
Since the fact that
Σ
+00, we have that above inequality is contradicted with the fact that
k+1
k=
Σ ()(w)))2 < to0 a.s. in the proof of Theorem 4.1 Therefore, obtain the desired result.
A.11 PROOF OF THEOREM 4.3
Proof. Recalling the inequality of Lemma 4.1 and the fact that A(w*) 2 u(zh) F", have
Basay [xa)]A(w F*] I [A(**) F*]
N2N ($(
Taking expectation with respect Fe, t k for above inequality, obtain that
Ex, [A(AA=*1))
F*] S E,, [A(w") - F*]
C1 Ey, ()?
2²
By the fact A(w*)= 2 v(z*) 2 F", follows
ER A(w")) F²
NN
By the Jensen's inequality and the convexity of function h(x) x² x R. it follows that
ER (E s A(w")-1
F* -
By the fact that E,, ((w*) 2 0 and h(x) = x², x E R is monotonic increasing in on [0, +oo), we have that
E ((w+t) 2 s A(ww) F*.
C1 (++1) c²N
min Ockst
Here comes that
2 (A(w") F²) cl
min Ex, (w oskst
t+1
26


Reviews:
[{"review_id": "SEaaPg02_MK", "reviewer": "Reviewer_Wyna", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strength:\n- The paper relaxes the uniform boundedness assumption of the subgradients for general nonconvex functions $g$ to the linear boundedness assumption of the subgradients for a class of weakly convex function $g$. \n- To conduct the analysis for the randomized algorithm, a surrogate stationarity measure is proposed based on the distance of the generated sequence of a reference point. \n\nWeakness:\n- The paper is merely an extension of Algorithm 2.2 in Zhang & Luo (2020b) to a randomized version. Although some new notations/relaxation of assumptions were proposed, the analysis and techniques of the paper rely on a combination of the techniques used in Zhang & Luo (2020b) and standard techniques of randomized algorithms in the literature. \n", "summary_of_the_paper": "The paper proposes a randomized primal-dual method for solving the nonconvex nonsmooth optimization problem with linear constraints. The main analysis relies on the idea of using auxiliary problems and the Lyapunov function proposed in  (Zhang & Luo, 2020b). \nThe paper shows that any cluster point of the generated sequence is almost surely a stationary point of the nonconvex nonsmooth problem and also provides an almost sure asymptotic convergence rate together with the expected iteration complexity of the proposed method. \n", "summary_of_the_review": "The paper is well written and has certain contributions. I would support its publication in ICLR but my support is not strong.  ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "H5iWdWidGr2", "reviewer": "Reviewer_Adyx", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "While this paper has some promise, it has some major issues that prevents me from being sure of the significance of the contributions.\n\n1. The authors assume compactness of set $\\mathbb{X}$ and hence the subproblem for $x^{k+1}$ is not easy to solve even in the convex case. When $g_i$ is a convex function, this problem will be related to the proximal operator of $g_i + \\delta_{\\mathbb{X}_i}$ where $\\delta$ is an indicator function. Even though the proximal operator of individual terms in the sum can be easy, the proximal operator of the sum is not always easy to compute. \n\nI see this as a shortcoming of the analysis which requires compact domains. We can see in the proof of Th 4.1 (b), compactness of $\\mathbb{X}$ is used to show boundedness of the sequence, from which existence of a subsequence immediately follows. Indeed, in standard analysis, we derive boundedness of the iterates, rather than assuming it.\n\n2. The authors assume that there exists $L_g, G_g$ such that for all $s\\in\\partial g(x)$, one has $\\|s\\| \\leq L_g + G_g \\|x\\|$. But we also have that $\\| x\\|$ is bounded due to compactness of $\\mathbb{X}$. What is then the difference of the assumption compared to bounded subgradient assumption? The authors also mention this at the end of page 3, where they talk about almost sure boundedness, why is it not immediate from compactness of $\\mathbb{X}$?\n\n3. Can you please give more examples and also clarify more Remark 2.1. Remark 2.1 says that update of $x^k$ only requires the prox of $\\phi$, why is the $\\mathbb{X}$ constraint is not enforced? \n\n4. I think the authors using their own result for the rate of deterministic method is not very fair here. Can the authors use an existing analysis for a deterministic method to compare, such as [1] or other references therein. Of course, [1] considers a problem without the weakly convex term. The authors can compare their results with $g=0$ with [1]. Of course, the assumption in [1] is different from the one in this paper and therefore the authors should make it clear difference between their assumption and the assumption of [1].\n\nMy main problem with the authors' current comparison in Remark 4.1 is the following. When we compare SGD and GD, we cannot say that we set the number of functions in SGD to be $1$ (which would give a rate $1/\\sqrt{k}$ in the convex case) and use it as a rate for GD. Obviously, with GD, we can prove a much better rate and the comparison would not be fair, if we use the result of SGD with number of functions set to be $1$.\n\n5. The experimental results are also far from being convincing. First, as my previous point, the authors need to use an existing deterministic algorithm as a reference, rather than their algorithm with $N=1$. Moreover, in the plots, we do not really see much of a difference between the full or stochastic methods.\n\n6. The authors are missing a large number of references that studied linearly constrained problems or problems with metric subregularity, in the convex case. For example [2, 3, 4]. At the beginning of page 4, the authors talk about $g$ being null in the reference they cite. In [2, 3], g is not null and hence the authors should provide a better argument. For example, the reference that the authors cite (Zhu, Zhao, 2020) only proves almost sure subsequential convergence even for convex case, whereas [2, 3, 4] all prove almost sure sequential convergence in this convex case, which is of course much stronger.\n\nMinor comments: 1. It will be easier to follow the theoretical results if the authors group assumptions separately. Right now, the authors say \"under the assumptions in Lemma 4.1\" where Lemme 4.1 says \"under the assumptions of Lemma 3.1\", etc., which makes it harder for the reader to follow.\n\n[1] https://arxiv.org/pdf/1801.01994.pdf\n[2] https://arxiv.org/pdf/1706.02882.pdf\n[3] https://arxiv.org/pdf/2007.06528.pdf\n[4] https://arxiv.org/pdf/1508.04625.pdf", "summary_of_the_paper": "This paper develops a randomized primal-dual algorithm for solving linearly constrained problems with a nonsmooth nonconvex objective and convex constraint set. Specifically, the objective is composed of a smooth nonconvex term and a weakly convex and hence nonsmooth nonconvex term. The authors show that the limit points of the algorithm are stationary points. The authors then prove almost sure asymptotic rate of $1O(/\\sqrt{k})$ and complexity of $O(\\epsilon^{-2})$ for obtaining an $\\epsilon$-stationary point, in expectation. Some preliminary empirical results are included.\n", "summary_of_the_review": "While this paper has some promise, it has some major issues that prevents me from being sure of the significance of the contributions, such as the inaccuracy in comparison of complexities, or per iteration costs. Moreover, the assumptions seem quite strong to guarantee some important conclusions (such as boundedness of the sequence, see the remark in Th 4.1 (b)).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "1lZ-6F_AMcf", "reviewer": "Reviewer_NZQN", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "1. For convex case (including nonsmooth and bregman divergence), this paper proposed randomized coordinate primal-dual coordinate method for augmented Lagrangian. \n\nParallel Direction Method of Multipliers\nHuahua Wang, Arindam Banerjee, Zhi-Quan Luo, Neurips, 2014 \n\n2.  The z update is cheap and has a closed form, it seems unnecessary to use the gradient and coordinate. I think it will also make the algorithm faster and it may not need a smallest enough step size for the z update as in Lemma 4.1. Further question is if simply using the closed form, could we use ADMM Gauss-Seidel style update, i.e. ||z-x^k || ?  empirically runs faster.\n\n3. In Lemma 3.1, dual step size  \\eta requires to be very small. Explanation and tuition could help better understand the algorithm. \n\n4. The paper could present more about the experiments in terms of comparison with existing methods to show the effectiveness of the proposed method, particularly when double the dimension of primal variable.", "summary_of_the_paper": "This paper studies a particular type of nonconvex nonsmooth problem. The authors propose to use the Bertsekas' convexification procedure on the nonconvex problem, and then use randomized coordinate method to solve the corresponding augmented Lagrangian. The paper also proposes a so-called surrogate stationarity measure to establish the convergence rate for the proposed method.", "summary_of_the_review": "Overall, the paper looks good and the results are aligned with randomized coordinate methods, i.e. O(1/N). ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "1NocKzs37t", "reviewer": "Reviewer_6TRm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "strengths:\nS1. This paper is well-written. It illustrates the basic idea of the coordinate descent method for solving linearly constrained nonconvex nonsmooth problems in a clear way. \nS2. The proposed N-RPDC algorithm is novel. Using the local uniform metric subregularity property, the authors establish the global convergence of the proposed algorithm and prove that any limit point of the algorithm is a clustering point. I find the proofs of this paper are rather technical and nontrivial.\nS3. The authors provide nice explanations and discussions for their algorithm design and theoretical analysis.\n\n\nweaknesses \nW1. The proposed algorithm involves several unknown parameters (e.g., rho_g, sigma), these parameters could greatly affect the practical performance of the coordinate descent methods. The authors do not discuss the practical choice of these parameters in the experiment section.\n\nW2. In the sufficient decrease properties in lemma 4, the parameters kappa and delta are unknown, it is not known how to choose these parameters to guarantee the global convergence of the algorithm.\n\nW3. The convergence analysis of ALM for solving nonconvex problems has been well-studied using the Kurdyka-Lojasiewicz inequality assumption. It is not clear whether the new local uniform metric subregularity assumption is weaker than the KL inequality assumption.\n\n\nminor issues:\nM1. The parameter beta_K is not defined in Lemma 3.1. I think it is the strong convexity parameter of the Bregman distance function.\nM2. It seems to me that solving the auxiliary problem reduces to the inertial proximal or Nesterov's momentum strategy, which has been wildly used in solving the minimax optimization problems. It will be helpful to make discussions on this point.\n\n ", "summary_of_the_paper": "This paper proposes a randomized primal-dual coordinate method for solving linearly constrained nonsmooth nonconvex optimization problems. At each iteration, this method only selects a primal variable to update randomly. The proposed algorithm can solve large-scale problems since the computational complexity in each iteration is very cheap compared with the full gradient methods. The authors prove that any cluster point of the sequence of iterates is almost surely a stationary point. Some experiments on the non-PSD kernel SVM problem and the linearly constrained Lasso problem show that it is practical.\n\n  ", "summary_of_the_review": "See above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear Authors,

The paper was received nicely and discussed during the rebuttal period. However, the current consensus suggests the paper requires another round of revisions before it gets accepted. 

In particular:

- it is not clear if the new method with randomization improves over the deterministic methods, either in theory and practice.
- it is not clear how the assumptions made in this work compare to the existing ones and what the implications are, in terms of applications.

Reviewers were not satisfied by the replies received during the rebuttal period. 
One reviewer stated that the argument "first coordinate method for this setting" is valid, but not sufficient to justify publication at this stage. 

Best
AC
Decision: Reject