A first-order primal-dual method with adaptivity to local smoothness
Authors: Maria-Luiza Vladarean
Yura Malitsky
Volkan Cevher
Venue: NeurIPS 2021 Poster (2021)
Keywords: adaptive
primal-dual
convex-concave
composite optimization
local smoothness
local Lipschitz continuity

Abstract: We consider the problem of finding a saddle point for the convex-concave objective $\min_x \max_y f(x) + \langle Ax, y\rangle - g^*(y)$, where $f$ is a convex function with locally Lipschitz gradient and $g$ is convex and possibly non-smooth. We propose an adaptive version of the Condat-Vũ algorithm, which alternates between primal gradient steps and dual proximal steps. The method achieves stepsize adaptivity through a simple rule involving $\|A\|$ and the norm of recently computed gradients of $f$. Under standard assumptions, we prove an $\mathcal{O}(k^{-1})$ ergodic convergence rate. Furthermore, when $f$ is also locally strongly convex and $A$ has full row rank we show that our method converges with a linear rate. Numerical experiments are provided for illustrating the practical performance of the algorithm.

A first-order primal-dual method with adaptivity to local smoothness
Maria-Luiza Vladarean"
Yura Malitsky
Volkan Cevher
(maria-luiza, vladarean, volkan cevher) @epfl.ch yurii malitskyi@liu.s.
LIONS, École Polytechnique Fédérale de Lausanne, Switzerland Linköpping University, Sweden
Abstract
We consider the problem of finding a saddle point for the convex-concave objective min, max, f(x) + (Ar, y) g (y), where a convex function with locally Lipschitz gradient and g is convex and possibly non-smooth. We propose an adaptive version of the Condat-Vū algorithm, which alternates between primal gradient steps and dual proximal steps. The method achieves stepsize adaptivity through simple rule involving || and the norm recently computed gradients of f. Under standard assumptions, we prove an O(k-) ergodic convergence rate. Furthermore, when f is also locally strongly convex and A has full row rank we show that our method converges with linear rate. Numerical experiments are provided for illustrating the practical performance of the algorithm.
Introduction
In this paper we study particular instance of the composite minimization problem
min fz) + 9(Ax),
(1)
where f and g convex, proper and lower-semicootinuuus (l.s.c.,, and A is a linear operator.
Problems of the form (1) have been studied in the literature under various assumptions on f and g. For the particular instances where g A is mooximal-friende and f is L-smooth, the objective is splitting algorithms like the Proximal Gradient algorithm
suitable for applying and its accelerated counterpart [Nesterov, 2013, Beck and Teboulle, 2009]. In general, however, the proximal operator of g o A is not easily computable and such cases a popular approach is to decouple A and by reformulating problem (1) as convex-concave saddle-poin problem:
min maxx(xx, v) f(x) (v).
=EX vE>
where g" denotes the Fenchel conjugate of g. Objective (2) is typically addressed by primal-dual splitting algorithms which, under strong duality, can recover the solution the original problem (1). In the particular case when f and are proximal-friendly and possibly non-smooth, very popular method is the Primal-Dual Hybrid Gradient proposed in [Chambolle and Pock, 201 1], which was further extended to handle an additional T-smooth component with the Condat- Vū algorithm [Condat, 2013, Vū. 2013]. Convergence rates for the latter studied [Chambolle and Pock, 2016a].
Together, these classes of algorithms cover a broad range of problems in diverse fields such as signal processing, machine learning. inverse problems, telecommunications and many others. As result, a great amount of research effort has gone into addressing practical concerns such as robustness
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

to inexact oracles, acceleration and automation of stepsize selection. For comprehensive list of examples and theoretical details we refer the reader review papers [Combettes and Pesquet, 201 Parikh and Boyd, 2014, Komodakis and Pesquet, 2015, Chambolle and Pock, 2016b]. In this work, we focus on the line of investigation studying stepsize regime automation for primal-dual algorithms targeting problem (2).
In their basic form, primal-dual methods require as input stepsize parameters belonging to designated interval of stability, which depends on problem specific constants like the global smoothness parameter and A ||. Dependence on such constants is undesirable because they may be costly to compute and oftentimes one can only access upper-bound estimates, thus leading to overly-conservative stepsizes and slower convergence. Moreover, the need to know L for setting the stepsizes prevents these methods from being applied to functions which are not globally smooth.
Consequently, recent efforts have gone towards devising methods with adaptive stepsizes [Goldstein et al., 2013, 2015, Malitsky and Pock, 2018, Pedregosa and Gidel, 2018]. These approaches resort to linesearch for finding good stepsizes every iteration, and exhibit improved practical performance. It thus appears that better convergence comes at the cost of an indeterminate number of extra steps spent in subprocedures aimed finding appropriate stepsizes.
In this work, we study problem (2) under the assumption that Vf is locally Lipschitz continuous and g is moximal-friennd]] To illustrate the motivation of our framework, take a prototypical example in image processing:
min || - b112 De 12,11 KE KERdd, B DE Rd2xd x 2
where is an image. K is problem-specife measurement operator, b is the vector of (possibly noisy) observations and D is the discrete gradient operator and the regularization term represents the isotropic TVV norm. In order to apply any of the aforementioned primal-dual algorithms, one needs to first choose how to decouple the linear operators. There are three options: decoupling with respect to K leaves us with having compute the proximal operator of the TV norm for the primal step, which is an iterative procedure [Chambolle, 2004]. Decoupling D implies performing gradient steps on f. since in general its proximal operator not efficient. Finally, decoupling with respect both implies increasing the dimensionality of the dual variable to m + 2d, which is problematic for large d and m. The sensible choice the second one (i.e., decoupling D), and the question we seek answer with this work is:
Does there exist a method for solving (2) that adapts to the local problem geometry without resorting to linesearch?
Our contribution is to propose first-order primal-dual scheme that answers this question in the affirmative and is accompanied by theoretical convergence guarantees. Using standard analysis techniques we show an ergodic convergence of O(k when V is locally Lipschitz and g is moximal--riendij and a linear convergence rate for the case when f is in addition locally strongly convex and has full row rank. We provide numerical experiments for sparse logistic regression and image inpainting, as well as use our method as a heuristic for TV-regularizee nonconvex phase retrieval.
The rest of the paper is structured as follows: Section 2 provides details about related work; Section 3 introduces notation, along with technical preliminaries and assumptions to be used in our analysis; Section reports the main theoretical results alongside partial proofs; finally, partial numerical results are provided in Section 5 with the rest being deferred to the appendix due to lack of space.
2 Related Work
Adaptive Gradient Descent (GD) methods. Arguably the most widespread of optimization meth- ods. GD presents similar shortcomings for setting the stepsize as those described in the previous section. particular, much research effort has gone in devising variants of the algorithm that remove the need to estimate the global smoothness constant T.. In recent work, Malitsky and Mishchenko [2020] propose an extremely simple and effective alternative for setting the stepsize тı adaptively at every iteration, as follows:
Tk min (
Tk-1
rk Fk-
(3)
Tk-2 2 (f(())) V (x

---

Adaptivity essentially comes 'for free' in (3), as it involves solely quantities which have already been computed. Moreover, the method requires only the weaker assumption of local smoothness, thus extending the reach of provably-convergen GD to wider class of differentiable functions while maintaining the standard (k--1) convergence rate.
In this work we show that the above technique can be extended to the analysis of primal-dual methods, where it gives rise an algorithm whose stepsizes adapt to the local geometry of the objective's (locally) smooth component f.
Adaptive monotone variational inequality (VT) methods. Malitsky [2020] proposes an algorithm
for solving monotone VIs with stepsize that adapts to local smoothness similarly to (3). This method solves the very general formulation of finding u' such that (F(("), ), u =²) + hh(u) hhu") ) 2 0, Vu for a given monotone operator F' which is locally Lipschitz continuous. Our template (2) can be recovered from theirs by setting u (2, y). with
F(u) F(, Vf(x) + AT -Ar
and h(u)= = (v). The advantages of this approach are the relaxed requirement of local Lipschitz continuity for F and the fact that knowledge of || || is not required. However, since the VI framework is very general and does not take advantage of the problem structure (e.g. the fact that (Az, y) is bilinear term), the method comes with worse convergence bounds than algorithms specifically designed to solve (2). In addition, the algorithm requires as input an upper bound on the stepsizes, despite them being set in accordance to the estimated local smoothness.
First order primal dual algorithms and adaptive versions. A popular method for solving (2)
when is L-smooth is the Condat- Vü algorithm (CVA) [Condat, 2013, Vü, 2013]. The method's
convergence is subject to global stepsize validity condition given by ( L) ! 2 1 where and a are the primal and dual stepsizes, respectively.
Another approach to solving problem (2) is via the Primal-Dual Fixed-Point algorithm based on the Proximity Operator (PDFP*O) or the Proximal Alternating redictor-Correator (PAPC) meth- ods [Loris and Verhoeven, 2011, Chen et al., 2013, Drori et al., 2015]. This approach comes with less restrictive stepsize conditions than CVA owing to a different iteration style, but which nevertheless depend on the global smoothness constant L and || A || and have to be carefully chosen.
In order alleviate the burden of choosing the stepsize parameters in CVA, Malitsky and Pock [2018] propose a linesearch procedure involving only dual variable updates and which, for certain problems such as regularized least squares, does not require any additional matrix-vecttee multiplications. characteristic of this algorithm is that it maintains constant ratio between primal and dual stepsizes through a hyperparameter - a setup which we also use in this work.
Preliminaries
Consider problem (2) and let X, be finite dimensional real vector spaces equipped with the standard inner product (,, :) and the associated Euclidean norm || = V(.)). We denote by g" the Fenchel conjugate of in (1) defined as g" (3() = sup,, { (x., v) g(x)). J. In order to not overload the notation, use AT denote the adjoint operator of A.
One can easily see that (2) is a primal-dual formulation the following primal and dual optimization problems, of which the former is the same as (1):
min f(x) + g(Ax), xEX
max off (")()))
wEy
EX A saddle-point (a", E X x y of problem (2) satisfies the following optimality conditions:
A y Vf(²'), Ar 03"()"))
For (x',1)) E X' x y we define the following quantities:
Pe (z) == f(z) f(z') + - A'''
3

---

- (A'' v²),
Se'y(11,1) == (r) + (y))
These functions are convex for fixed (o'.y) and whenever (a', (z')y) = (x",y"), it holds that Pet Pet.y- (I) 2 0. De .y (x)
(x) 2 0 and Gx- (z, y) 2 0, with the latter quantity representing the primal-dual gap. We also define the gap restricted to a bounded subset B, x B2 C X y as:
(E, =
sup (a' B BB
(x) + De (v):
and note that it is non-negative whenever B1 x B, contains saddle-poing
Given function f X' R and I 0, say that f is L-smooth if its gradient V is Lipschitz continuous: [V - ff(y)ll & L yll, Vx, Furthermore, f is locally smooth Vf is
Lipschitz continuous any compact subset C: vC X, The > 0 such that [VV((x) Vf(y) s Lc]|= - yll, Vx, C.
- x) すo4 1| x 112 Va, We also say that f is j-strongly convex if ((y) 2 f(x) + (VI()), y
Similarly, is locally strongly convex if it is strongly convex any compact subset C: vC C X, 3pe such that f(y) 2 f(x) + (Vf(x). x) Me r y 112 Vx,y
We define the proximal operator of a convex function g X R foo} as px)x,(x) =
arg {9(2) + x - 2 [1²] and say that g is 'proximal -fienndly if prox,(2) (x) has a closed form solution or can be efficiently computed to high accuracy.
Finally, the following two blanket assumptions will hold throughout the paper: Assumption 3.1. Function f convex and locally smooth, while convex, l.s.c,, and proximal- friendly.
Assumption 3.2. A saddle-poiis exists for problem (2) and thus strong duality holds.
We note that Assumption 3.2 is standard in the literature (see e.g., [Chambolle and Pock, 2011]). Assumption 3.1, on the other hand, weaker than the usual global T-ssoothhess premise and thus enlarges the category of admissible functions f with instances such r exp(z). To illustrate, consider the aforementioned function defined on the reals: the global smoothness assumption clearly does not hold, however for any fixed interval [a, b] C IR the smoothness constant can be chosen as exp(b).
For showing linear convergence of our method, we will add the following assumption:
Assumption 3.3. Function locally strongly convex and operator has full row-rank.
4 Algorithm and convergence
The primal-dual method proposed for solving problem (2) under assumptions 3.1 and 3.2, is provided in Algorithm under the abbreviation APDA, which we use from here onwards. APDA follows the same structure as the basic CVA [Chambolle and Pock, 2016a] for the given assumptions. Notice that if we restrict Assumption 3.1 to L-smooth functions we can in fact recover CVA by setting
0g = and T2 = т, 0 = a fixed such that ( - T.) 1 A 1
Algorithm Adaptive Primal Dual Algorithm (APDA)
Input: 4o X, 1/ E V, Tink 70 0o, On 1, B 0, c (0,1) 2 = To Tinit V f (2o) + A yo)
for -1,2,.. do
Set Ti: min
0x Th BBT. On 76-1
ž + (x) - xz-1)
0k+1 prox on (yi + (xAAE))
Tk+1 3b Th V (xxx) + A (b41)
end for

---

4.1
High level ideas
We can rephrase the global stepsize condition of CVA by introducing a free parameter 8 > 0 which represents the ratio between the fixed dual and primal stepsizes: B With this change of variables,
the stepsize validity condition becomes
0, L+ L244 AI?
Our algorithm disposes of CVA's global condition and relies instead on a very similar but local ((m--)) provides an
criterion given by Tk E 0. LL+ 1
where L == || [ -
estimate of the local smoothness constant and / = o. In particular, this requirement is satisfied by the first part of the expression defining Tk in APDA:
Tke = min
1 1+ 0x-1
(5)
2/ L2 + (3/(1 - c)) A
where e E (0, 1). Intuitively, this rule demands that т does not overstep a constant related to the local curvature, thus allowing for larger stepsizes in flatter regions and correspondingly smaller ones otherwise.
By itself, the first term of (5) does not ensure convergence, since aggressegeeess and possibly destabilizing stepsizes might occur in near- lear-linear regions. This issue is addressed by the second part of the expression (5) which, informally, prevents the stepsize from increasing "too fast' in consecutive iterations. Specifically, the increase factor is at most I + 0x-1, where 0₂
It TL-2"
Under these two local stepsize conditions we are able to show APDA's convergence using the weaker assumption of local smoothness of f, thus conveniently removing the need of estimating global smoothness constant L.
Remark 4.1. While Th does not adapt to | for many practical problems this fact is not big hindrance. Function f typically represents the data fidelity term, whose smoothness constant L (should it exist) can far exceed A||-the the linear operator enforcing structured regularization A specific example are TV-regularized imaging problems, where A is the discrete gradient operator whose norm is bounded by /8 [Chambolle, 2004], while the data fidelity term may involve a very large number of measurements and larger norm, consequently.
Remark 4.2. APDA takes an additional primal step prior to the for-loop, which is controlled by Tiit given input. This is needed for estimating L1 in the first iteration. In practice we set Timit = 1e-9, 9, a sufficiently small value to ensure that xn does not depart too far from Zo and yield good estimate of L1. Furthermore, the setting of To so simply ensures that in the first step. T1 (212)(01(1-0)1 and has no impact on further steps. Finally, in our experiments we set = 15-15-1 - this is parameter introduced for theoretical purposes as explained in the following section.
4.2 Analysis the base case
In short, the main steps of our analysis are: first, we establish the inequality that characterizes the dynamics of APDA given in Lemma 4.1 below. Based on are able prove the boundedness of sequences { and {yı= in Theorem 1. In turn, sequence boundedness alongside the local smoothness property of ff allows us to conclude that there exists constant L > 0 such that is L-smooth on the compact set Conv([x*, "0,",,0,,111 II,...,
the closed convex hull generated by {x* .o, .0,,..., Finally, we leverage this information to show that (I2, yk converges point of (2) and derive the associated ergodic convergence rates presented in Theorem 4.1.
saddle
Lemma 4.1. Consider APDA along with Assumptions 3.1 and 3.2 and (x, v) E X V. Then, for all k and Th& E
All
1-2raLs
2rall
1
|| [x41 x 2
yk+1 11
+ +1 T7 || All -TLL)) [x+1 xx
3
+ 7k
THB A|
|| 164+1 32 112 2Tx (1 + 0x) + 2 Dr. (W++1)
Bip
5

---

$ I2 x x112+ 3 11 Uk -11 + Tx = xk-1 112 + 2T Pz,y (xx-
Moreover, it holds that:
1) Lg 2 Tk || TkLks
2)
Thl TAl All > 0.
Proof sketch. The full proof is deferred to the appendix. We use algebraic manipulations, APDA's update rules, the Cauchy-Schwars and Young inequalities and properties of the prox operator to get the recurrence:
1 3
rk+1 - x =01
yk++1 - y11 1 (1 The |||||| me TcLx) Øx+1 - -x
+ (3) Th All)
7 1) 11-1-1 yk 1 + (1 + (x))) + 2Ts (1.+(1
$ || Th 112 + yu y TaLx In -x-1 + 2T ( (6)
where 7/ 0 is free iteration constant involved in Young's inequality.
In order to obtain anything worthwhile we would like to set 7 such that, when unrolling (6) over
the iterations, the terms containing Fx+1 Ig I1 and yk+1 - yv II accumulate on the LHS with positive coefficients. More preciscly, ask that:
Th A Tm
TuLx >
where 1). We note that the RHS of the first inequality could have been chosen as 0, however, we made it strictly positive due to technical reasons related to controlling the sequence y/441 yk In practice, we choose c to be as small as possible.
similar remark holds for the second incquality, where it would have been sufficient to set its RHS to Tk+1 Lx+1- Since this would considerably complicate the analysis, we make the observation that Tuckk 3, Vk and use this simpler uniform upper-bound instead.
1-27. Ly and what is left to show The inequalities (7) are equivalent to asking that 7 E ( ( 1---- 2rel|
is that this is valid interval i.e., that the left endpoint is strictly smaller than its right counterpart. This condition amounts to solving a quadratic inequality in Tke whose solutions lie the interval
0, 1L+V/1++2//000000 satisfies this constraint.
The proof is concluded by showing that our choice of т indeed
We are now ready to state the main convergence result in Theorem 4.1 below, whose full proof given in the appendix.
Theorem 4.1. Consider APDA along with Assumptions 3.1 and 3.2, and let (x" ,y²") E X y be saddle point of problem (2). Then, for all l
1) Boundedness. The sequence {#x, yk)} is bounded. Specifically, for all k,
I x² 112 + 3/ y 112 < M,
where M := =| x² 1
vi y² 11 + 1 21 xo 1| < xx.
2) Convergence to a saddle point. The sequence (x),
yk)) converges to saddle point of (2).

---

Xx = 1
3) Ergodic convergence.
Let Sk
=
T5
Ss
Tx(1 + 0s)ar +
k-1
h
1
Σ (T + + -1+110+1) and Yk =
Then, for any bounded
Sp.
1=1
B x B2 EEXX y and for all k,
9B.xB. (Xg, M(B,, Bo)y L2 + (3/(1 - |A
k
where L is the Lipschitz constant of f over the compact set Conv( fx* 20. $1.... .)) and
M(B, B3) = Su xB, [1 - x 112 + 11 - 112 + 2 æ1 - 2g 11?
The boundedness result of Theorem 4.1 point 1) implies that the closed set C Conv({x* No. .1,... is also bounded and hence compact. The local smoothness assumption on then ensures that there exists I, > 0 such that f is L-smooth over C. Note that such an I. exists for any Tn, Yo since the boundedness result itself holds for any initial conditions (though the value of such L cannot be generally known, as it is path-dependent). Using this fact,
show uniform
lower-bound on the primal stepsize: T 2 [L2 + (8/(1- - c)) || Al)) 1/2 > O, Vk, which is
instrumental in deriving the subsequent convergence results, as well Theorem 4.2. We emphasize that the appearance of constant L in the provided rates is consequence of iterate boundedness, whose proof does not require its knowledge. Finally, we note that our rate comparable to that of CVA in terms of constants.
4.3 Analysis under the additional Assumption 3.3
We now study APDA under the additional assumption of locally strongly convex f and full row rank A. Before proving the result of Theorem 4.2, few remarks are in order. First, the boundedness result of Theorem 4.1 point 1) also holds for constant = 0, since this constant was required only for proving convergence
saddle point in point 2) of the theorem. Second, taking a smaller stepsize than the originally defined тą will not change the validity of Lemma 4.1 or the boundedness result of Theorem 4.1, as it remains within the required interval mentioned in section 4.1.
Consequently, for studying APDA under the additional Assumption 3.3 we can simplify the stepsize expression by taking c 0, because now we are able to show iterate convergence directly by using the strong convexity and full row-rank assumptions. Specifically, we consider the stepsize:
1
Th
min
+ Tk-
0x-
2/ AT2
which is smaller than the one originally considered and, due to the aforementioned remarks it ensures that APDA produces a bounded sequence. It follows that, under the local smoothness and local strong convexity assumptions, there exist constants L and p such that f is L-smooth and μ-strongly convex over Conv( (x", Fo, ..)...)).
The existence of these constants along with A being full row rank, turn, allows us to derive a strengthened version of the inequality in Lemma 4.1 for (a,, v) = (x*,"");
1k+1 - x 112 (3
(1 + 92
+ 91
M1 - 3" 112
2 xx+1 112 + gs 136+1 yk 1|
2
+ 2TA (1
0z) (mx) + 2T Dar (yk+1)
1
1
$ (1 -1-g9h 91) 1| x² 112
ll yk v²
112
|| o xk- 112 +T (IX-1),
where 92, 03. 44, 45 > are constants given the appendix. This new inequality represents in fact contraction, which guarantees the linear convergence rate stated in Theorem 4.2.
7

---

Theorem 4.2. Consider APDA along with Assumptions 3.1, 3.2 and 3.3. Let (x",y") ) E X x y be a
saddle point of problem (2). Furthermore, let Tk be defined by (8) and let 8 = 41.2 + 3 Al
and L: == V 4u² || |l; where L are the strong convexity and smoothness constants of over the compact set Conv (x", 2u. .1)...)).
Then, for all
Fk
1|
yk
4² 1212 12 min (x. M,
where the rate constants are given by:
1 p p 2'
3o min min (A)H
q 48"
r B0 min
(A)p + S. + 41.28"
and M.
x2 xx 112
4 + T) 1/ V2 11 + 1 x2 I1 112 + P s T
L (A)a with miin (A) representing the smallest singular value of A.
8s2t 4L2s'
A few remarks are in order: first, as a sanity check, we observe that when = 0 we recover the contraction factor of [Malitsky and Mishchenko, 2020] which is equal to q.
Second, we make some notes on how our rate compares with existing ones. To our knowledge, there are no explicit results regarding the linear convergence of CVA under assumptions similar to ours (linear rates are usually shown for the 3-component objective without assumptions on see e.g.. [Chambolle and Pock, 6a]). However, in the case of L-smooth and p-strongly-connex f and full row-rank A, Chen et al. [2013] show the linear convergence of PDFP" O with rate:
|| 1 111
[|02 - roll2
11y1 voll3)
(1- min
(1-min
oh minn( A)
/
k-1
max((A)
02 max((A) L
The rate presented in Theorem 4.2 has comparatively worse contraction factor. The reason is that our iteration is set up in the style of CVA, where we essentially have a single stepsize to compute using the rephrasing from Section 4.1. Therefore. тı needs obey the problem structure with respect to both L and || resulting in the 'mixed' term appearing in the denominator.
Keeping the above in mind, the interested reader may find in the appendix that constants q and come from a product between тę and other condition number-related quantities, which is tightly liked to the structure of the main inequality used in the paper. This makes the nice separation of condition numbers achieved in PDFP"O's rate not possible in our case and, it seems, the analysis necessary achieve this kind of adaptivity comes the cost of worse constants (the same remark holds for [Malitsky and Mishchenko, 2020]).
PDFP*O, on the other hand, achieves clean bound by having different iteration style than CVA. as well as a fundamentally different kind of analysis where the iteration is expressed in fixed -oint form to show convergence. In this context the stability conditions sppciffically, < À < 1/ and 0 < 7 < 2L in [Chen et al., 2013). A drawback of this approach, however, that the algorithm has rate guarantees when is only smooth and not strongly convex and only asymptotic convergence is shown. Also, PDFP20 requires matrix-vector multiplications per iteration whereas we only require
the stepsizes are also relaxed
Experiments
We now present some numerical experiments conducted for APDA', Additional problems and results are included the appendix. The experiments were implemented in Python 3.9 and executed on MacBook Pro with 32 GB RAM and 2.9 GHz 6-Core Intel Core i9 processor.
'See https: htttps:///ithut com http:////www.aaaeee////aa/aaaaaa

---

The baseline we compare against in this section as well as the appendix is CVA, for which we use Algorithm in [Chambolle and Pock, 2016a] (using g = 0). In the particular case of sparse logistic regression we also compare against FISTA [Beck and Teboulle, 2009]. For obtaining x we ran one of the algorithms for large number of iterations.
5.1
Sparse binary logistic regression
10
10
10-1
FISTA
F(a) F(())
CVA
10
(primall
(dtall
APDA
10-3
10-9
APDA
109
APDA
10-19
CVA
CVA
1O00
2000
10a
500
1000
10
500 (inerations)
1000
(ilerralioue))
k (iterations)
10
10-1
10-1
F(ar) F(z2)
(prinall)
10-2
(chaal)
10%
FISTA
CVA
10-3
APDA
10
APDA
10-7
APDA
CVA
CVA
1000
2000
10
500
1000
10
500 (iserations)
1000
& (Iteration))
k (iterations)
10-2
FISTA
1
CVA
(primall)
[dual]
10
ARDA
10
10-2
APDA
10
APDA
10-9
CVA
CVA
10-4
1000
2000
500
1000
500 k ((terations)
1000
& (Lteratiou))
k (iterations)
10-4
10-2
10-2
APDA CVA
APDA CVA
F(z) F(
(primal)
10-4
(dhaal)
10-1
10
FISTA
10-5
CVN
10-6
APDA
1000
2000
10
500
1000
10
500 (iterations)
k (iterations))
k (iterations)
Figure 1: The first column shows algorithm convergence. The second column shows comparison of primal stepsizes between APDA and CVA. The third column shows comparison of dual stepsizes between APDA and CVA. Each subfigure represents different dataset: (a) ij cnn; (b) mushr ooms; (c) a9a; (d)covtype.
We consider the problem of sparse binary Logistie Regression on LIBSVM datasets [Chang and Lin, 2011] and show that adaptivity provides faster convergence in 3 of these cases. The objective

---

consider is:
min F(x) = 2E3"
log(1 + exp(= + A All 11
where (gi, b2) Rd (-1,1} and À is the regularization parameter. APDA and CVA be applied to this problem by setting A = formulation (2). Primal-dual algorithms are not the typical choice for solving (9), which is usually addressed by methods such Proximal Gradient FISTA [Beck and Teboulle, 2009]. However, we note that the computational costs of APDA and FISTA are comparable since the matrix-vector multiplication cost of the former removed due to a A = I.
We choose À = 0.005 || Q Il. where Q = [af .... T'1 For APDA we perform a parameter sweep over 3 [1e-3, 1e6] for each dataset and settle for: 3 2. 68e3 for ijenn; 3 = 5. 18e4 for a9a; 3 = 3. 16e1 for mushrooms;
3. 73e-1 for covtype.
For CVA we sweep p [1e-3, 1e6] and set r All+/tE and σ A| by construction, these stepsizes satisfy the validity condition and are as large as possible since the condition satisfied with equality. We do an additional tuning procedure where we choose constants E [1e-10, 1e2] and { E [1e-5, 1e2] and set a = TG. which are subject to verifying the stepsize validity condition of select the best stepsizes across the tuning phases to be (truncated to 3 decimals):
CVA. Finally
T 9. 8.98-49.... 4.0 a = 1. 125e1 for i cnn; T = 2. 655e-4, 5 = 7.896e1 for a9a; T = 9. 936e-4,
5. 5.878e0 for mushrooms;
7. 7288-068
1e-06 for covtype.
Note that the Hessian of f is given by v2f(x) = (())))) where D(x) a diagonal matrix such that D;, = (1 where (z) = (-eeppp-bblg.... E (0, 1). Clearly, over any compact set in C C X' there exist Dmin == min (x, E (0, 1) such that Dmin Q < Q" As a result, a sufficient condition for local strong convexity is that the minimum eigenvalue of Q" Q be greater than O.
The convergence results along with stepsize comparison plots are presented Figure 1. For dataset ij jnenn we run APDA with the modified тı used in Theorem 4.2, since Amin (Q" 75.13 and A has full rank. the latter case, the legend identifier is APDA- use only the basic setting for Tke as Amin (Q Q) S 1e-13.
the remaining datasets we
While APDA outperforms FISTA and CVA on ijcnn, a9a and mushrooms, it shows relatively poor performance on covtype. We hypothesize that this is related to the condition number of Q" Q, which is almost three orders of magnitude larger the latter case: 2e22 versus 3e1, 2e20 and 2e17 for ij cnn, mushrooms and a9a, respectively. A similar behavior is seen in Figure 1.(c) of [Malitsky and Mishchenko, 2020].
Finally, the adaptive property of APDA's stepsizes is visible in the stepsize comparison plots where they shown oscillate within least one order of magnitude throughout the optimization process.
6 Limitations of APDA
The experiments presented in this paper (Section 5 and Appendix A) have the common trait of not imposing hard constraints on the primal variables. As a consequence, we are able to take plain gradient steps in the primal domain. However, for instances such as Poisson linear inverse problems [Bertero et al., 2009], the iterates Ty need to reside in R. because the primal objective contains log functions. APDA cannot handle such cases, as any constraints imposed on the primal variables will only satisfied asymptotically. We consider such scenarios as a future research direction.
10

---

Acknowledgements
The first author is grateful to Ya-Ping Hsich for his feedback on the manuscript and for helpful research discussions throughout the development of this work. The authors also sincerely thank the anonymous reviewers for their time and their thoughtful, constructive feedback which helped improve and clarify this manuscript.
This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 725594 time-data), the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, with the project number 305286. The work was also sponsored by the Department of the Navy, Office of Naval Research (ONR) under a grant number N62909- 11---17--21111111 by
by the Army Research Office and was accomplished under Grant Number W91 1991NN9-191100 the Hasler Foundation Program: Cyber Human Systems (project number 16066). This work was also supported by the Swiss National Science Foundation (SNSF) under grant number MMM021117886511
References
Amir Beck and Mare Teboulle. A fast iterative bbrinkage-threhhlldin thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-2000 2020002222222020 2009.
Mario Bertero, Patrizia Boccacci, Gabriele Desiderå, and Giuseppe Vicidomini. Image deblurring with poisson data: from cells to galaxies. Inverse Problems, 25(12):123008 2009.
Antonin Chambolle. An algorithm for total variation minimization and applications. Journal of Mathematical imaging and vision,
2004.
Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications imaging. Journal of mathematical imaging and vision, 40(1):120-145, 2011.
Antonin Chambolle and Thomas Pock. On the ergodic convergence rates of a first-order primal-dud algorithm. Mathematical Programming, 159(1):253-255) 201
Antonin Chambolle and Thomas Pock. An introduction to continuous optimization for imaging. Acta Numerica, 25:161-319, 2016b.
Chih-Chung
Chih Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-27:27, 2011. Software available at http://wwez csie............ ntu. edu. tt/"cjjin/libssw
Peijun Chen, Jianguo Huang, and Xiaoqun Zhang. A primal-dual fixed point algorithm for convex separable minimization with applications image restoration. Inverse Problems, 29(2), 2013.
Patrick L. Combettes and Jean- Saa--Chrsttophe Pesquet. Proximal splitting methods signal processing. In Fixed-point algorithums for inverse problems in science and engineering, pages 185-212. Springer, 2011.
Laurent Condat. A primal-dual splitting method for convex optimization involving lipschitzian, proximable and linear composite terms. Journal of optimization theory and applications, 158(2): 460-479, 2013.
Yoel Drori, Shoham Sabach, and Marc Teboulle. A simple algorithm for a class of nonsmooth convex-concave saddle-point problems. Operations Research Letters, 43(2):209-214, 2015.
Tom Goldstein, Min Li, Xiaoming Yuan, Ernie Esser, and Richard Baraniuk. Adaptive primal-dual hybrid gradient methods for aaddle-point problems, arXiv preprint a305v: 0546. 2013.
Tom Goldstein, Min Li, and Xiaoming Yuan. Adaptive primal-dual splitting methods for statistical learning and image processing. Advances Neural information Processing Systems, pages 2089-2097, 2015.
11

---

Nikos Komodakis and Jean- Christophe Pesquet. Playing with duality: An overview of recent primal? dual approaches for solving large-scale optimization problems. IEEE Signal Processing Magazine, 32(6):11-54, 2015.
Ignace Loris and Caroline Verhoeven. On generalization of the iterative soft-thresholding algorithm for the case of non-separable penalty. Inverse Problems, 22502) 2011.
Yura Malitsky, Golden ratio algorithms for variational inequalities. Mathematical Programming, 184 (1):383 -10,3-410, 2020.
Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. In Interna- tional Conference on Machine Learning, pages 6702-6712. PMLR, 2020.
Yura Malitsky and Thomas Pock. A first-order primal-dua algorithm with linesearch. SIAM Journal on Optimization, 28(1):411 1-32, 2018.
Yu Nesterov. Gradient methods for minimizing composite functions. Mathematical Programming, 141,, 2013.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in optimization, 1(3): 127 127-239, 2014.
Fabian Pedregosa and Gauthier Gidel. Adaptive three operator splitting. In International Conference on Machine Learning, pages 4085-4094, PMLR, 2018.
Bang Công Vü. A splitting algorithm for dual monotone inclusions involving cocoercive operators. Advances in Computational Mathematics, 38(3))667-681, 2013.
12


Reviews:
[{"review_id": "r8t3azO8Dvw", "reviewer": "Reviewer_EuGK", "summary": "This paper studies adaptivity of first-order primal-dual methods with respect to the smoothness or local smoothness of the problem. The manuscript builds upon a previous publication (Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. In Interna347 tional Conference on Machine Learning, pages 6702–6712. PMLR, 2020) to primal dual setup. Ergodic convergence is shown for the proposed method, where no knowledge of L is needed. The results is based on local smoothness which is defined for pairs of iterates of the sequence of points generated by the algorithm. The case of strongly convex function is also studied.", "questions": "", "limitations": "", "rating": 7, "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": "This is a good paper, it is easy to follow and many of the concepts and ideas and nicely presented. Also, the results are interesting and will provide a good contribution to adaptive methods. I did not checked every line of the proofs but spend a couple of hours going over them and I believe they are correct.\n\nI have a couple of comments that would like to be addressed.\n\nAbstract: some quantification of \"faster convergence\" would be useful, what minor change?\n\nSome more formality is needed in the definition of locally smoothness. Line 121 page 3, do the authors mean there is a finite L such that for each compact subset the gradient is Lipschitz? or for every compact subset one can find a finite L. This might need clarification, because then the example provided is smoothness with respect to two iterates, which is a very local and path dependent constant. An identical comment follows for the local strong convexity property. I believe these items are of crucial importance in the analysis so maybe a formal definition would be great.\n\nSome discussion about the fact the the final bounds are given with respect to the smoothness, (and strong convexity) of the function on the convex hull of the iterates. This is on, but some discussion is needed. For example, does such L exists for any initial point? At the end of the day, we such convergence bounds to estimate the number of iterations required to get some \\epsilon accuracy, and then we will inevitably need some estimate of L. This L in theory depends on all the iterates, all the way to infinite iterates, is there a way to estimate this? \n\nMaybe some extra discussions is needed about the difference between having a function being smooth, and it being locally smooth for all possible sequences of the algorithm for different initial points. I believe this is the critical point that will show the weaker assumptions required in this manuscript. \n\nminor typo in like 119 page 3 \"it its gradient\"\n\nminor: it looks a bit weird to have the algorithm in between a section and a subsection floating around.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "l4PFtIi4hNS", "reviewer": "Reviewer_RYzj", "summary": "Interesting contributions in the field of optimization but not well enough presented and poor match for Neurips.", "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": "The paper presents interesting contributions in convex optimization. But since this is an optimization paper and the experiments are in image processing, without any relationship to machine learning, I think the paper would be more suitable in an optimization journal.\n\nIndependently, I think that the state of the art should be presented in a better way: to minimize f(x) + g(Ax) using the gradient of f and the prox. of g, there are 2 main algorithms: 1) the Condat-Vu algorithm (CVA) and 2) an algorithm proposed independently by several authors and called the PAPC, PDFP2O or Loris-Verhoeven algorithm (LVA), see e.g. in the paper\nCondat et al., \"Proximal splitting algorithms: A tour of recent advances, with new twists\".\nThe CVA should not be called PDHG = the Chambolle Pock algorithm, since this is confusing: this algorithm for this problem would use the prox. of f. The abstract, in particular, is misleading.\nThe LVA has been proved to converge linearly when f is strongly convex and A is full rank; I don't know if this is the case for the CVA.\nSo, I understand that your algorithm is an adaptive extension of the CVA. It should be presented as such and the properties discussed: in the globally Lipschitz case, do you recover what is known about the CVA?\n\nIn Figure 1, it seems that tau and sigma converge almost immediately to some values, around 0.2 and 0.02. I guess that if you use these values in the CVA, you get the same convergence profile. So, CVA is slower only because you chose the wrong stepsize values. So, you method is a way to select automatically the stepsize values in the CVA, which is nice and useful in practice. This is what should be advertised. The \"local adaptivity\" property is not illustrated; in particular, as mentioned at the end of the paper, the method is not suitable for barrier function which are not Lipschitz continuous.\n\nI don't think the experiment in Section 5.2 is relevant, since your theory is in the convex case, so application to a particular nonconvex example does not show anything.\n\n=== update after author response period\nThe responses to the different concerns raised by the reviewers are convincing. My initial evaluation was perhaps too severe: it is true that automatic selection of the stepsizes in optimization algorithms is a difficult but very important topic, so every progress in this area is welcome. \nAnd contrary to other reviewers, I don't think that the work is a marginal step after the work of Malitsky and Mishchenko, since primal-dual methods need particular care to be tamed.\nSo, assuming that the authors will implement the changes they promise to do, I am increasing my score from 4 to 6. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, this is a theoretical work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "IC3gkfAiGd0", "reviewer": "Reviewer_nTWw", "summary": "This paper studies a saddle-point problem with bilinear coupling and no constraints on primal as well as dual variables. Due to the unboundedness of the underlying problem, the paper assumes local Lipschitz smoothness for any compact sets. It proposes an adaptive version of the primal-dual method that estimates the local Lipschitz smoothness constant of the primal function. The authors show that the iterates remain in a bounded set around the saddle-point. Consequently, they can show asymptotic convergence of the limit point. They also show a convergence rate for a weaker notion of the primal-dual gap.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "The novel part of this paper has some novelty in the analysis showing the boundedness of primal and dual variables. It improves upon the setting of Malitsky et al. [2018]. Compared to Malitsky et al. [2018], they assume that the primal function does not have an easy proximal evaluation oracle. To estimate the local Lipschitz constant of the primal function, they use the recently proposed approximation technique by Malitsky and Mishchenko [2020].\n\nThe paper provides a clear exposition of the ideas and gives thorough proof of all claims. The content is easy to comprehend and an experienced reader can grasp the details quickly. \n\nAn issue in the proof of Theorem 4.1 part (3): \nI cannot see the relation \\tau_k(1+\\theta_k) + \\sum_{i = 1}^{k-1} (\\tau_i(1+\\theta_i) - \\tau_{i+1}\\theta_{i+1}) = \\sum_{i = 1}^k \\tau_i. I am getting an additional \\tau_1\\theta_1. Please double-check on whether I am missing anything. If not then please fix this issue. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "While I agree with most of the analysis, there is one thing I have to mention about the convergence criterion primal-dual gap: P(X) + D(Y). \nAs defined in this paper, if the problem is \\min_x \\max_y F(x,y) then primal-dual gap P(X) +D(Y) = F(X, y^*) - F(x^*, Y). This is a weaker criterion than \\sup_{x \\in \\XX,  y \\in \\YY} F(X, y) - F(x, Y) for some compact set \\XX, \\YY containing saddle-point (x^*, y^*).\nTo see this, consider a simple case of F(x, y) = y^TAx. Clearly, the unconstrained saddle-point problem has solution (x^*, y^*) = (0,0).\nIn that case, P(X) + D(Y) = 0 trivially for all X, Y. However, the supremum-based criterion above is 0 iff (X, Y) is a saddle-point. It might be worth checking whether the gap convergence can be proved for the supremum-based criterion.\n\nAn update after the response:\nI am satisfied with the responses by the authors and keep my score.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}, {"review_id": "93hbjisuhy5", "reviewer": "Reviewer_prmj", "summary": "The authors propose an adaptive stepsize updating rule for the primal-dual Chambolle-Pock method that solves min f(x)+g(Ax) for locally-smooth f and cheap-prox-step g. The updating rule for adaptive stepsizes is simple in the sense that it only uses local gradients and ||A||, without needing any further subroutines like line search. They provide theoretical convergence rate for their proposed method under the local-smooth assumption and also with further local-strongly-convex assumption. They also corroborated their findings with experiment results that shows favorable  behavior of the new step-sizes.", "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": "The paper consists some interesting ideas towards improving the practicality of primal-dual methods. The method it proposes is new to primal-dual methods for minimax problem and leads to good empirical performance. My main concerns on the paper is:\n\n1) the novelty of the method: the method is essentially a generalization of the adaptive stepsize updating rule proposed for SGD in Malitsky and Mishchenko, 2019. Most of the ideas and techniques seem similar to that paper and it will be good if the authors can make their own design and contribution more explicit in the paper.\n\n2) the theoretical performance: If I understand correctly, the theoretical rate that the authors show didn't fully match the state of the art of standard non-accelerated primal-dual methods, even when local smoothness degrades to global smoothness. For instance, in Theorem 4.2, there seems to be at least a (L/mu)^{1+alpha} and kappa(A)^{1+alpha} dependence, for alpha>1. (also is q correct in unit? why not optimizing q for stating the final complexity?)\n\nGiven these factors, I think it is a paper with interesting and meaningful result but am slightly worried about if the results included are significant enough to be published in the venue. If the authors have convincing arguments to relieve my worry or can improve their results further, I am happy to change my mind.\n\n* minor comments: \n- The paper will read better if it gives detailed definition of the notations it used, i.e.  dom(g), sigma(A), ... etc.\n- The proof sketch of Theorem 1 could be organized in a better way; especially the second and third terms that authors refer to in line 193 looks unclear.\n- It would be good to add remarks after Theorem 4.2 to explain more clearly in each regime of L/mu, ||A||, which term in the complexity will dominate and what rate one will get from your method.\n- The formatting on line 230 could be improved a bit to avoid confusion in minus sign and hyphen.\n- line 307: satisfies -> satisfied", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors included the limitation of their work in Sec 5.3.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an adaptive variant of the Condat-Vu algorithm for composite bilinear saddle-point problems, providing theoretical guarantees and reporting some promising experimental results. After fairly extensive discussion, the reviewers have converged to a positive consensus on the paper, and I consequently recommend its acceptance. 

Based on the discussion, the authors should carefully revise their manuscript, paying close attention to the following points:

* Comparison with the related works mentioned by the reviewers.

* Clearing-up of the derivation of the strongly-convex case, aiming for a concise bound easily comparable with the best known non-adaptive bound.

* Inclusion of additional results with more extensive tuning of the non-adaptive baseline.

Decision: Accept (Poster)