Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints
Authors: Zhenwei Lin
Qi Deng
Venue: NeurIPS 2024 poster (2024)
Keywords: Convex optimization; Accelerated primal dual algorithm; Sparse Optimization
Primary area: optimization
TL;DR: We propose faster accelerated primal-dual algorithms for minimizing a convex function subject to strongly convex function constraints.

Abstract: In this paper, we introduce faster accelerated primal-dual algorithms for minimizing a convex function subject to strongly convex function constraints. 
Prior to our work, the best complexity bound was $\mathcal{O}(1/{\varepsilon})$, regardless of the strong convexity of the constraint function.
It is unclear whether the strong convexity assumption can enable even better convergence results. 
To address this issue, we have developed novel techniques to progressively estimate the strong convexity of the Lagrangian function.
Our approach, for the first time, effectively leverages the constraint strong convexity, obtaining an improved complexity of $\mathcal{O}(1/\sqrt{\varepsilon})$. This rate matches the complexity lower bound for strongly-convex-concave saddle point optimization and is therefore order-optimal.
We show the superior performance of our methods in sparsity-inducing constrained optimization, notably Google's personalized PageRank problem. Furthermore, we show that a restarted version of the proposed methods can effectively identify the optimal solution's sparsity pattern within a finite number of steps, a result that appears to have independent significance.

Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints
Zhenwei Lin
Shanghai University of Finance and Economics zhenweilin@163, sufe. edu. cn
Qi Deng"
Antai College of Economics and Management Shanghai Jiao Tong University
qdeng240s edu.
Abstract
In this paper, we introduce faster accelerated primal-dual algorithms for minimizing a convex function subject to strongly convex function constraints. Prior to our work, the best complexity bound was (1/E), regardless of the strong convexity of the constraint function. It is unclear whether the strong convexity assumption can enable even better convergence results. address this issue, we have developed novel techniques to progressively estimate the strong convexity of the Lagrangian function. Our approach, for the first time, effectively leverages the constraint strong convexity, obtaining improved complexity of ((1)VE). This rate matches the complexity lower bound for strongly wawpll--ooox-cooccaae saddle point optimization and is therefore order-optimal. We show the superior performance of our meth- ods in sparsity-inducins PageRank problem. Furthermore, show that restarted version of the proposed methods can effectively identify the optimal solution's 's sparsity pattern within a finite number of steps, result that appears have independent significance.
constrained optimization, notably Google's personalized
Introduction
In this paper, we are interested in the following convex constraine problem:
minxeR"
f(x) s.t. (x(x) S 0, i m,
where f R + R is a convex continuous function and bounded from below and R² + R. 1.2..... m. are strongly convex continuous functions. An important application of this problem. commonly encountered in statistics and engineering, involves the objective f(x) as a proximal- friendly regularizer and gi (x) as data-driven loss function used to gauge model fidelity.
To apply first-order methods for the above dunetion-constrained problems, a common strategy involves double-loop procedure that repeatedly employs fast first-order methods, such as Nesterov's accelerated method, to solve specific strongly convex proximal subproblems. Popular methods among this category include Augmented Lagrangian methods [18 33.. level-set methods (1I,, penalty
methods [17. When both [() and g:(x) (x) are convex and smooth (or composite), it has been found
that these double-loop algorithms can attain an iteration complexity of O(1/e) achieve an E-Crror
*Corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

in both the optimality gap and constraint violation. When the objective is strongly convex, the complexity can be further improved to (L))E)) (33
In contrast to these double-loop algorithms, single-loop algorithms remain popular due to their simplicity in implementation. Along this research line, (32) developed first-order algorithm based on linearizing the augmented Lagrangian function, which obtains an iteration complexity of (1/e)) [4] extended the augmented Lagrangian method stochastic function-constrrained problems where both objective and constraint exhibit an expectation form. Viewing ! as a special case of the
min-max problem:
minxeR" maxyERm ((x,y) : f(x + E (x); s.t. yo 2 0, i = 1,2...,,m
(2)
11 proposed to solve ① and (2) by an accelerated primal-dual method (APD), which generalizes
the primal-dual hybrid gradient method [6] initially developed for saddle point optimization with bilinear coupling term. Under mild conditions, APD achieves the best iteration complexity of O(1/e)
for general convex constrained problem and further improved complexity of (11/V5) when f(x) strongly convex. 4 proposed unified constrained extrapolation method that can be applied to both deterministic and stochastic constrained optimization problems.
Despite these recent progresses, to the best of our knowledge, all available algorithms are suboptimal in the presence of strongly convex function constraints (I) Specifically, direct applications of previ- ously discussed algorithms yield an (1/E)) complexity, which is inferior to the (I)VE) optimal bound for the strongly-conye convex-concayy saddle point problem [22]. It is somewhat unsatisfactory that the strong convexity of g(x) has not been found helpful in further algorithmic acceleration. The core underlying issue arises from the dynamics of saddle point optimization: it is the strong convexity of y) that offers more potential acceleration advantages, yet the strong convexity of L(: ) is substantially harder to estimate than that of g(x). This difficulty is compounded by the interplay between g(x) and the varying dual sequence { The challenge naturally leads us to question: Is it possible to further improve the convergence rate of first-order methods for solving the strongly convex constrained problem
Key intuitions We make an assumption that the minimizer of f(x is infeasible for the function constraint (x) S O, 1 S S m. If this assumption were not made, we would be dealing with an unconstrained optimization problem that would not depend on gxx). This assumption also implies that the optimal dual variables are non-zero, and as a result, the Lagrangian function strongly convex with respect to x. By leveraging the strong convexity, we can use more aggressive step sizes and achieve faster convergence rates compared to other state-of-the-ane the-art algorithms.
Applications in pearsity-constriing optimization We consider the constrained Lasso-typa prob- lem, which minimizes a sparsity-inducd regularizer while explicitly ensuring data-driven error remains controlled:
minxeR" ||I|||
s.t. g(x) S O,
(3)
where g()) is a convex smooth loss term. A motivating application is the approximate personalized
PageRank problem (8). where gxx) (x. Qx) (b, x) is strongly convex quadratic and Q integrates the graph Laplacian with an identity matrix. Compared to the standard Lasso problem B0), min (xx +X|[x|I the constrained problem (3) offers enhanced control over the data fitting error. This advantage, however, is counterbalanced by the challenge of dealing with a nonlinear constraint. Besides concerns about the efficiency in solving (3) it is often desired show the active set (or sparsity) identification, namely, the nonzero patterns of the optimal solution x* can be identified by the solution sequence {xx} in finite number of iterations. Identifying the embedded solution structure within a broader context is referred to as the manifold identification problem [3] [2]. Exploiting the sparsity pattern is particularly desirable in large-scale PageRank problems, result in significant runtime savings. For the regularized Lasso-type problem. it has been known that proximal gradient methods (e.g. [14 19 24) possess the finite active-set identification property. Specifically. (24] introduced "active set complexity", which is defined as the number of iterations required before an algorithm is guaranteed to have reached the optimal manifold, and they proved the proximal gradient method with constant stepsize can identify the optimal manifold in a finite number of iterations. However, for the problem (3). it remains unclear whether first-order methods can identify the sparsity pattern in finite time.
could
2

---

Contributions We address the theoretical questions about strongly convex constrained optimization and the application of sparse optimization. Our contributions are summarized as follows.
First, we present a new accelerated primal-dual algorithm with progressive strong convexity estimation (APDPro) for solving problem ( APDPro employs novel strategy to estimate the lower bound of the dual variables, which leads to gradually refined estimated strong convexity modulus of ((: y). With additional cut constraints on the dual update, APDPro able to separate the dual search space from the origin point, which is critical for maintaining the desired strong convexity over the entire solution path. With these two important ingredients, APDPro exhibits an (( x I| Dy)/ complexity bound to obtain an E-error on the function value gap and constraint violation, where Dy a known upper-boune bound of lyo - y*Il. Moreover, we show that for the last iterate have an & eπror (i.e., |xx 122 E), APDPro requires total iteration of O (([[xo x I| + Ilyo y=1l)/
Both complexity results appear new in the literature for strongly convex-constraie
optimization.
Second, we present new restart algorithm (rAPDPro) which calls APDPro repeatedly with the input parameters properly changing over time. Different from APDPro, rAPDPro dynamically adjusts the iteration number of APDPro in each epoch based on the progressive strong convexity estimation. We show that rAPDPro exhibits a complexity of O log + Dy /VE) to ensure E-error in the last iterate convergence where Dx is the estimated diameter of the primal feasible domain. While is difficult to improve the overall O(1 / /E) bound, rAPDPr appears to be more advantageous when Dx and Dy are the same order of ||x x"I and | y"1l, respectively, and Dx >> Dy- In addition, we show that a similar restart strategy can further accelerate the standard APD. The muulistage-accellratee primal dual method (msAPD) obtains a comparable ((L/v)) complexity of APDPro without introducing additional cut constraint.
Third, we apply our proposed methods to the sparse learning problem (3) In view of the theoretical analysis, all our methods converge at an O(1/VE) rate, which is substantially better than the rates of state-of-th of-the-art first-order algorithms.. Moreover, algorithm rAPDPro has the favorable feature of identifying the optimal sparsity pattern. Note that such selian-et/mm identification is substantially more challenging to prove due the coupling of dual variables and constraint functions. To establish the desired property, we develop asymptotic convergence of the dual sequence to the optimal solution, which can be of independent interest.
conduct
analysis show that the restart
Outline Section 2 sets notations and assumptions for the later analysis. Section 3 presents the APDPro algorithm and develops its stepsize rule and complexity rate. Section presents the restart APDPro (rAPDPro) algorithm. apppies our proposed methods for sparsity- innduiig optimization and shows the sparsity identification result for rAPDPro. Section (o empiricaly examine the convergence performance and sparsity identification of our proposed algorithms. Finally, we draw All the missing proofs are provided in the appendix sections.
4
the conclusion in Section 7
2 Preliminaries
We use bold letters like x to represent vectors. Suppose x E R", 2 1, we use ||x||g (E (x()])) 19)1/9 to represent the normm,, where X(j) is the i-th element of x. For brevity, ||x|| stands for 12- norm... For a matrix A, we denote the matrix norm induced by 2-norm as |||||] = supp||]] ||Ax]] The normal cone of L/ at u is denoted as (u) == {v (v,
u) < 0, Vx E ( Let B(x, r) be (y Ily x|| < r). We denote the set of feasible solutions by Xa = {x 9 (x) < 0, E [m]} and write the constraint function as G((x) == (x), Im (x)) T We assume each (x) is a μ4 strongly convex function, and denote I = [M1,... pm]] /m] Let [m] := (1....,m) m for integer m. We denote minimum and maximum strongly convexity y minje(m) (1z). and j maxje[m] (1g} and the vector of elements 0 by O. The Lagrangian function of problem ① is given by L(x,y) == f(x) + (y, G(x)) where y RRT. Definition 1 (KKT condition). We say that x* satisfies the KKT condition of [ if there exists a Lagrangian multiplier vector y E RT such that 0 E 0x (x) and (y", Gxx*)) =0
the closed ball centered
with radius
0, i.e., B B(x,
The KKT condition is necessary for optimality when a constraint qualification (CQ) holds at x*. We assume Slater's s CQ (Assumption[] holds, which guarantees that an optimal solution is also KKT point 3.
Assumption 1. There exists strictly feasible point x E IR such that G(X) 0.
3

---

We use X to denote a strictly feasible point throughout the paper. Moreover, we require Assumption circumvent any trivial solution.
Assumption 2. For any X E argmin fxx), there exists an E [m]] such that gi(x)) 0.
Remark 1. Assumption is essential for our analysis. While verifying Assumption 2 can be indeed challenging, is achievable for the sparsity-inducing problem considered in our paper. In this example, the solution xi = =0 is the single minimizer of the sparsity penalty.
Next, we give several useful properties about the optimal solutions of problem T Please refer to Appendix [.I] for the proof of Proposition a Appendix fo2 the proof of Proposition
Proposition 1. Suppose Assumption Da holds. Then, for any optimal solution x" of problem T there
exists y" E Th such that KKT condition holds. Moreover, y" falls into == {y |yy|| e).
where E = [(3)) (18)-minyean f(x)
(=
Proposition 2. Under Assumption x" is the unique solution of ① Furthermore, set y
argmaxyERs L(x",y) is convex and bounded.
In view of Assumption 2, Proposition and closedness of the subdifferential set of proper con-
vex functions [2] Theorem 3.9].
27 Chapter 23], we know that dist(af(x*), > 0, where
(ist(Of(x*)) ).0) := mingeaf(x)) EE Furthermore, we make the following assumption:
Assumption 3. Throughout the paper, suppose that a constant r satisfying
dist(Of(x*), 2 2,
is known.
We give some important examples for which the lower bound r can be estimated. Suppose fx) is a Lasso regularizer, i.e., f(x) |x||| then
satisfies (4) More general, consider the group Lasso regularizer, i.e., f(x) = E.=1 P:l| ())| where ((i) E R and Σ b, = n, B is the number of blocks, then = min [8] [P:} when x" * 0. Another example is f fxx = -c cxx, then we have
r |c|].
Remark 2. Condition is similar to the bounded gradient assumption that has been used for accelerating the convergence of the Frank-Woly Wolfe algorithm. See Appendix for more discussions.
When considering the Lipschitz continuity function in R", even quadratic functions are not Lipschitz continuous. However, the Lipschitz continuity of (x) is crucial for algorithm convergence. Therefore, we define the bounded feasible region in the following proposition, with its proof provided in Appendix D.3
Proposition 3. Let X = B(x, minse(m) 2V 2g.(xx)) where x = argmin (x) Then under
Assumptions 7 andd 2 we have x* int X.
Assumption 4. There exist Lx, LG > O such that
[VG(x) -V(x)) < Lx|xx-
Vx, X: x||, -x|,, Vx, X,
x||. x||,
(5)
-(x)) < Lal|x-
(6)
where VG(x) = (x), .., (x)( E x and X is defined in Proposition
The Lipschitz smoothness of the Lagrangian function with respect to the primal variable x is crucial for the convergence of algorithms. Given that the dual variable y is bounded from above, and considering the smoothness of the constraint functions, we can derive the smoothness the Lagrangian function. Combining 5 and the fact ||y|| |yyl| Vy E Y., we obtain that
VG(x)y - yx < Lxy x
X||
VX V
where Txx = č.x. For set X. J/ we use Dx and Dy to denote their diameters, respectively, i.e., Dx = maxx ||x] X2 and Dy maxy1.yEy) ||y1
-ylll-

---

Algorithm Accelerated Primal-Dual Algorithm with Progressive Strong Convexity Estimation (APDPro)
Require: To > 0, 00 > Xn 2) N
I: Initialize: (x-1,--1
(on. 80 Xo. 1-1 f 0o, To 0
2: Set Axy = 1 Dx +
1 Dr
27e
200
3: for k = 0, 0.1....,A do
4: Vi= < [y RT |yy|| 2 N>)
5:
Zy (1 + 0k-1/on)
(ok-1/o G((x-)))
6:
Ys+1 t argmin lly - (yx + 0
7:
X1+1 + prox - TB VG(xx))+++1
8: Compute tu. Xh+1 t (Ti&s + tu 1x*++1) + tx), Tht1 t Th + tk
9: Update Pk+1 + IMPROVE(X,, Xt:
aots Axx
Axy, Pk)
xx
Ts
10: Update Tk+11 and 0h++ depending Pk+1
11: end for
12: Output: KN+I.NN+J
13: procedure IMPROVE(X, x. 3, 3. Pola)
-2
14:
Compute p = μ. max
+
Lx
0 2u
+
Zur
15: Set fnew max (padd p}
16: return Pnew
end procedure
3 APD with progressive strong convexity estimation
We present the Accelerated Primal-Dur Algorithm with Progressive Strong Convexity Estimation (APDPro) solve problem (T). For problem ( APDPro achieves the improved convergence rate O(1/VE) without relying on the uniform strong convexity assumption
For the rest of this 1
22
paper, we denote prox f,x((x mzz, 1) == argmin f(x) + (z, X) 2n
as the proximal x
mapping.
We describe APDPro in Algorithm T The main component of APDPro contains a dual ascent step to update y& based on the extrapolated gradient, followed by a primal proximal step to update XĄ- Compared with standard APD [II], APDPro has two more steps. First, line of Algorithm ] applies novel cut constraint separate the dual sequence } from the origin, which allows to leverage the strong convexity of the Lagrangian function and hence obtain a faster rate of convergence than APD. Second, to use the strong convexity more effectively, in line 9 we perform progressive estimation of the strong convexity by using the latest iterates X₁. and X5- Throughout the algorithm process, we use routine IMPROVE to construct a non non-deccg sequence (Pt). which provides increasingly refined lower bounds of the strong convexity of the Lagrangian function.
The IMPROVE step In order estimate the strong convexity of the Lagrangian function, rely on the subdifferential separation (eq. (4) to bound the dual variables. From the first-order
optimality condition in minimizing L(x, y*) and the fact that x E int X (Proposition we have 0 e 0f(x*))=++++))))))))*())))))00 + VG(x*) + [xx)") = 0 ")+ + VG(x*)>" "y" . It follows from (4) that
S |VV(''>) S [|VG(x") III Ily & |I''Ix//VG((*))
(8)
where the last inequality use the fact that || S |1-- Note that the bound ||y* vr can not be readily used in the algorithm implementation because x* is generally unknown. To resolve this issue, we develop more concrete dual lower bounds by using the generated solution & in the proximity of x*. As we will show in the analysis, APDPro keeps track two primal sequences }x*} and (x&), ), for which can establish bounds on ||x x* I|2 and (y*) μ ||* x" 1|3/,, respectively. This drives us to develop the following lower bound property, with the proof provided in Appendix E.
Proposition 4. Suppose Assumption 4 holds. Lety" E y* be a dual optimal solution.
1. Suppose that ||* x=1 < 23, then we have
||y*|2 > (x, B) == - r +x L
(9)
5

---

2. Suppose (y")
p. ||x - xx112 1 S 23, then we have
-2
Iy" (2( := = Lx
8 2p
VG(8)
(10)
2
Our next goal is conduct the convergence analysis for APDPro in Theorem and Corollary Complete proof details are provided in Appendix E. and E.3
Theorem Suppose for any y" E e (y*) 1 2 Po holds, and let the sequence (Tk, Th, lis Pk+1)
generated by Algorithm Sasttmmmsstiii satisfy:
(xt2(TEt1 -P++1) S tATE tK+10 S t LxY L8 S xx
(11)
Then, the set YE is nonempty and y" C Va. Les A(x,y)
27m 1|11 - xol1² + 200 --olyol yx
Tk Ex= t.y.. The sequence (N,, Vkl generated by APDPro satisfies
IK-ITK-1 27x
||x" xx|1² -xxl f(xx,y))
_(x", 1 Tx A(x",)))
(12)
Next, we develop more concrete complexity results in Corollary Corollary 1. Suppose that ok; Tki la satisfy:
To -1 2 Lx + Li00, to =0/000
(13)
Tk+1 T// /1 Pk+17ks ok+1 Tk Tk+1
Then we have
S(xx) - [(x') S G4T
6
||0 xx11 +
Dē
270
200
|[G((x)]++1+ T6tTOP KK+
|x0 - x111 +
D
(14)
200
1 x|Ix-xxx x'113 PR +9( TO)
30p
A(x',y")
where e* c²:== = (f(x*) min f(x)) ((x))/ming /min: (- Do (x) > 0, AE = 2 Σt P28/ (k(//(((:: +1) and Pr
satisfy the following condition, Pk+1 Votk2 (3px+ 10 Jk: (k 1), 3//1/T0
Remark 3. In view of Corollary 7 APDPro obtains an iteration complexity of O(1/ which
is substantially better than the (T/e) bound of APD (T7] and ConFx [4] when the strong convexity parameter PKK is relatively large compared with e.
Remark 4. Additionally, we argue that even when PK O(e), APDPro can obtain the matching O(1/e) bound of the state-of-the-ari algorithms. Specifically, using the definition of Tk: Tke we easily derive the monotonicity of {ax)- It follows from akt1 Tkaok //41
Thokk hoek/(Tx///// V PK+1TK) PE:1TT) 2 as, that Te = -kk-) 4 = =op - ok 2 k. Using a sim-
ilar argument to that of Corollary 7 we obtain the bound [(xK) f(x)) S O(1/K) and
[[*x)))++1| S ((1/K).
Remark 5. The implementation of APDPro requires knowing an upper bound on ||y* When the bound is unavailable, (TT) developed an adaptive APD which still ensures the boundedness of dual sequence via line search. Since our main goal of this paper is to exploit the lower-bound rather than the upper bound ||y []. we leave the extension for the future work.
APDPro with a restart scheme
Note that in the worst case, APDPro exhibits an iteration complexity of O(Dx + Dy)/Ve), which has a linear dependence the diameter. While the ((1 VE) is optimal 25), is possible to improve the complexity with respect to the primal part from ODxx/Va VE) to O log (Dx/VE) To achieve this goal, we propose a restart scheme (rAPDPro) that calls APDPro repeatedly and present the details in Algorithm 2 Inspired by [66, we set the iteration number as function of the estimated strong convexity, detailed in the TERMINATEITER procedure. For convenience describing double-loop algorithm, we superscripts for the number of epochs and subscripts for the number of

---

Algorithm 2 Restarted APDPro (rAPDPro)
Require: PN_1 2 0, ō > 0, vi E (0, 1), d E (0, 1), x No11 NNN,, S
1: Compute 7 (1 1o) (bxv + 1/)
2: for 0, 0. do
3: To = =6 = 0, (xf, 1. 1. t (x NN.,:: (x). - -x 8-1 - ) = 8-1
PN.-.
4: Set Axy = 1 D + 20 Dÿ 0-1 + T. To = 0, = 0, N, =0
To
5: while h < N₂ do
6: Run line 10 APDPro with index set (s. ks)
7: Update No. 1.rk
T-TEMINNTEITER P k), t + k ++1
8: end while
9: end for
10: Output: Y
11: procedure TERMINATEITER P. k.
Polak2 + 3pppou k > 1 k =
12:
Compute Pnew
EF1
13: Compute N
"==[ma(6(Preww// ...
.3VDDy
T(oo)) 11
14:
return N, Pnew
15:
end procedure
sub-iterations in parameters x, T, e.g., xf meaning the x output of first iterations at S-th epoch. To avoid redundancy in the Algorithm| 2 we call the APDPro iteration directly. Note that the notation system here is identical to that of APDPro, with the only difference being the use of superscripts to distinguish the number of epochs.
In Theorem 2 we show the overall convergence complexity of rAPDPro with the proof provided in Appendix F.T
Theorem 2. Let {x0 be the sequence generuted by rAPDPro, then we have
|| x22 S A. D 2 Vs 2 0.
(15)
As a consequence, rAPDPro will find a solution X such that | - x=1 S for any E (0. D3) in at most S log, (Dx /E) epochs. Moreover, The iteration number of rAPDPro find x such that || - x" 122 < E is bounded by
Te
12 111T
22)
logg Dx +1 +1] Ve
G(v222)) (2x)
(16)
w2//800
where w1 and we satisfy Ex-o (wz) 'ES v²", respectively.
(wI)- + 1) and Σs V2 /2'//%,,
Remark 6. The bound Te depends on ē, wi and wT ff = 0((-log V or oz =
then we have Te = oc, which implies that we can not guarantee ||* x*I| S at finite iterations. T. T==o implies that there exists an epoch with infinite sub-iterations. Hence, rAPDPro is reduced to
APDPro if we only consider that epoch.
Remark 7. Comparison of rAPDPro and APDPro involves a number of factors. In particular,
rAPDPro compares favorably against APDPro if [|xo 1 -xxI = $2(y/ log Dx). Moreover, the complexity (T6) can be slightly improved if Dx is replaced by any tighter upper bound of |xx -x"] However, it is still unknown whether we can directly replace Dx with ||x - x=| in (6)).
Dual Convergence For dual variables, we establish asymptotic convergence to the optimal solution, a key condition for developing the active-set identification in the later section. For ease notation, is more convenient to label the generated solution as a whole sequence using a single subscript index: X1. X2..... XN:V1. V2, .......y .N.. Hence, we use the index system j and (s, k) interchangeably. Note that (x5 y 12+1) } and { + correspond the same pair of points. We present the dual
asymptotic result in the following theorem, with the proof provided in Appendix F22
Theorem 3. Assume 7-1 11 p and choose Mo > such that 1 > (0,z(((////0)) 2 8 + vg. We have yy) satisfy the KKT condition, where y" is any limit point of { generated by rAPDPro.
7

---

Remark 8. To establish the asymptotic convergence of the dual variable, we introduce an addi- tional constant å (0.1), 1), which implies that the initial step size must meet stricter requirement than the convergence condition specified in Corollary ] Since of of/ vI+ P {p% is bounded due to the boundedness of the dual variable, { is monotonically decreasing, then infosksN, / 2
(F) 1/22 Hence, inequality, 1 > inf inf/2o(0j-1/o,) 2 8 vo. is al- ways satisfiable if we choose proper 6, Mo such that (1 (1+ > ő 8 vo- Furthermore, Assumption (7)-1 > p mild. Since we always choose large enough rAPDPro, 7 can be sufficiently small. Remark 9. Both algorithms proposed previously require solving quadratic optimization with linear constraints when updating dual variables, which may introduce implementation overheads when the constraint number is high. Inspired by the multi-stage algorithm, additionally propose an algorithm MMulli-Stage APD, msAPD) that uses different step sizes different stages and dynam- ically adjusts the number of iterations in each stage by leveraging strong convexity, as detailed in Appendix H
Active-set identification in sparsity-inducing optimization
In this section, we apply our proposed algorithms to the aforementioned sparse learning problem:
min fxx), s.t. g(x) s O, x X(1) .... X(B) X(o) E 12" isisi
(17)
where f(x) = Ei= P: (|)) is the group Lasso regularizer and gxx) is strongly convex function. We use x to express the i-th block coordinates of x. The goal of this section is to show that rAPDrr can identify the sparsity pattern of the optimal solution of (17) in finite number of iterations.
In general, suppose that fxx) has a separable structure f(x) = E/= f((x())) we define the active
set A(x) for fxx by A(x) == {i (x)( not a singleton). For f(x) = Σ p: ()) ll. easy to see that A(x) is the index set of the zero blocks: A(x*) {i ((( = 0}. Next, we
describe one property for the optimal solution of in Proposition 5 with the proof provided in Appendix G.1
Proposition 5. Under Assumptions aand the KKT point for 17 unique.
To identify the sparsity pattern (active set) of the optimal solution, it is common to assume the existence of non-degenerate optimal solution, which is stronger than the standard optimality condition [24] We say that x* is non-degenerate if 0 E ridC(x", y²) = (x") Vgg("") (y")))))) for the Lagrangian multiplier y*, where ri stands for the relative interior. More specifically, (x", y*) satisfies the block-wise optimality condition
V lo (0) = V)(((()):
if A(x") Vg((") )y" 10) E int (Of((())) if A(x").
Inspired by [24]. we use the radius 77 min;ee.(x))) {p. (xVg(x")''")))))( ly ]I] which describes the certain distance between the gradient and "subdifferential boundary" of the active set. We demonstrate in the following theorem that the optimal sparsity pattern is identified when the iterates fall in neighborhood dependent on with the proof provided in Appendix G.2
Theorem 4. Set X : B(x, minie(m) 2 2
-20.(xx0)) +5) with Ç 0 and 3Lx XF (F
Ph
of in rADPrr, then we have there exists a epoch So such that xi,) x Su. Vk [Na), Vi A(x*).
Remark 10. The active-set identification result is achieved using the optimality condition the next iterate x+1 To ensure x int X, we define an expanded region, which prevents cases where the normal cone differs from {0}.
6 Numerical study
In this section, we examine the empirical performance of our proposed algorithms for solving the sparse Personalized PageRank [8] 23]. The constrained form of Personalized PageRank can be
8

---

10a
10
APD
10a2
ARD
10-4
10-1
APD
Mirrar
10
MsAFD
rAPDPro
MiAADD
rAPoPro
10
10-1
miAPO
10
AFDerestart
164
10-1
10
10-4
APD
10-
Mirrer
10-4
10-7
10
Mirror Prox
msARO
Mirror Prox rAPDPro
TAPDPro
10-9
APD-restart
10
10-92
APDerestart
10
10:41
APDerestart
1.0
1cd
163
165
Figure The first row describes the convergence to optimum, where the y-axis re- ports logio ((I)D2/2 x |D//2** "|)/) for rAPDPro, and logio((I
[|D|/x*1] / //|l""2x") x (1) for APD. APD+restart, msAPD and Mirror-Prox (x" is computed by MOSEK M.. The second row describes feasibility violation, where y-axis reports the feasibility gap 1og10 (max{(, G(xx))) for rAPDrr,, and Iog (max(0, G(x)))) for APD, msAPD and Mirror-Prox. Datasets (Left-Righh order) correspond to bio-CE-HT, bio-CE-LC and econ-beaflw.
written as follows: minxeR= ||D|/x||1 s.t. (x, (x) a D-1/2x) < b, where Q, D and 8 are generated by graph. We implement both rAPDPro and msAPD. We skip APDPro as we observe that the restart strategy consistently improves the algorithm performance. For comparison, we consider the state-of-the-ar accelerated primal-dual (APD) method []. APD with restart mechanism at fixed iterations (APD+restart) and Mirror-Prox [33 6 small to medium-scale datasets (28] are selected our experiments. All experiments are implemented on Mac mini M2 Pro, 32GB. Due to the page limit, we only report results three datasets and leave more details in the last Appendix[]
from various domains the Network Datasets
We plot the relative function value gap [x) f(x )/l](xx)l and the feasibility violation max (xx,, 0} over the iteration number in Figure [ respectively. Firstly, in terms of both op- timality gap and constraint violation, the performance of rAPDPro and msAPD is significantly better than that of APD, APD+restart and Mirror-Pros Additionally, rAPDPro and msAPD often converge to gigh--preiiionn solutions. Secondly, based on the experimental results, it is indeed observed that msAPD exhibits periodic variation in convergence performance, which aligns with our algorithm theory.
1.0
0.9
0.975
0.950
0.8
Mirron Prox
Mirror Prax
0.7-
Nimrr Prox
0.7
rAPOPro
0.900
rAPOPro
rAPDP1o
msAPD
msAPD
0.875-
apd-restart
0.6
AFD+restart
0.6
0.0
0.3
1.0
1.5
2.0
1e4
163
leb
Figure The experimental results on active-set identification. Datasets (Left-Right order) correspond to bio-CE-HT, bio-CE-LC and econ-beaflw. The z z-axis reports the iteration number and the y-axis reports accuracy active-set identification.
Next, we examine the algorithm's 's effectiveness identifying sparsity patterns. We computed a nearly optimal solution x* from MOSEK. Note that x* is dense vector. For numerical consideration, we truncate the coordinate values of zero the absolute value below 10-8 and perform the same truncation to all the generated solutions of the compared algorithms. Then use (lA(x) C

---

((x")++ (x) n (x (x))/))) n to measure the accuracy of identifying the active set, where denotes the set cardinality. For rAPDPro, we consider the last iterate X while for APD, msAPD and Mirror-Prox, we plot the result X3: these are the solutions where the convergence rates are established. Figure[]plots the experiment result, from which we observe that rAPDPro and msAPD are highly effective in identifying the active set. Often, they are able to recognize the structure of the active set within a small number of iterations. Overall, the experimental results show the great potential of our proposed algorithms in identifying the sparsity structure and are consistent with our theoretical analysis.
7
Conclusion
The key contribution of this paper is that we develop several new first-order primal-dual algorithms for convex optimization with strongly convex constraints. Using some novel strategies to exploit the strong convexity of the Lagrangian function, we substantially improve the best convergence rate from ((1/E) to (11/ /E). In the application of constrained sparse learning problems, the experimental study confirms the advantage of our proposed algorithms against state-of-the-ee ahrttrrr first-order methods for constrained optimization. Moreover, we show that one of our proposed algorithms rAPDPro has the favorable feature of identifying the sparsity pattern in the optimal solution. For future work, one direction is to apply the adaptive strategy, such as line search, to our framework to deal with cases when the dual bound is unavailable. Another interesting direction is to further exploit the active set identification property algorithm with active constraint identification, which could be highly desirable when there large number of constraints. It would also be interesting to consider a more general convex objective when the proximal operator is not easy compute.
general setting. For example, it would be interesting to incorporate our
Acknowledgement
This research is partially supported by the Major Program of National Natural Science Founda- tion of China (Grant 72394360, 72394364), Natural Science Foundation of Shanghai (Grant No. 24ZR 1421300). We sincerely thank all the reviewers for their valuable suggestions, which have significantly improved the quality of our article.
References
[1] Mosek ApS. Mosek optimization toolbox for matlab. User's Guide and Reference Manual, Version, 4(1), 2019.
[2] Amir Beck. First-order methods in optimization. SIAM, 2017.
[3] Dimitri P. Bertsekas. Nonlinear programming. Athena Scientific, 1999.
[4] Digvijay Boob, Qi Deng, and Guanghui Lan. Stochastic first-order methods for convex and nonconvex functional constrained optimization. Mathematical Programming, pages 1-65, 2022.
[5] Gábor Braun, Alejandro Carderera, Cyrille W Combettes, Hamed Hassani, Amin Karbasi. Aryan Mokhtari, and Sebastian Pokutta. Conditional gradient methods. arXiv preprint arXiv:2211.14103 2022.
[6] Antonin Chambolle and Thomas Pock. On the ergodic convergence rates of first-order primal-dual algorithm. Mathematical Programming, 159(1):23--287, 2016.
[7] Joseph C Dunn. Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals. SIAM Journal Control and Optimization, 17(2):187-211, 1979.
[8] Kimon Fountoulakis, Farbod Chosta-Khorasani Julian Shun, Xiang Cheng, and Michael W Mahoney. Variational perspective on local graph clustering. Mathematical Programming, 174:553-573, 2019,
10

---

[9] Kimon Fountoulakis and Shenghao Yang. Open problem: Running time complexity of acceler- ated E reguularie pagerank. Conference on Learning Theory, pages 5630-5632. PMLR, 2022.
[10] Dan Garber and Elad Hazan. Faster rates for the frank-wolfe method strongly-convex sets. In International Conference on Machine Learning, pages 541-549. PMLR, 2015.
[11] Erfan Yazdandoost Hamedani and Necdet Serhat Aybat. A primal-dual algorithm with line search for general convex-concave saddle point problems. SIAM Journal on Optimization, 31(2):1299-111 -32119999-99,,,,--1111 2021.
[12] Warren L Hare and Adrian S Lewis. Identifying active constraints via partial smoothness and prox-regularity. Journal of Convex Analysis, 11(2):5112666, 2004.
[13] Niao He, Anatoli Juditsky, and Arkadi Nemirovski. Mirror prox algorithm for multi-term composite minimization and semi-separable problems. Computational Optimization and Appli- cations, 6(2))275-311, 2015.
[14] Franck lutzeler and Jérôme Malick. Nonsmoothness in machine learning: specific structure, proximal identification, and applications. Set- Valued and Variational Analysis, 2864)666..678, 2020.
[15] Michel Journée. Yurii Nesterov, Peter Richtárik, and Rodolphe Sepulchre. Generalized power method for sparse principal component analysis. Journal of Machine Learning Research, 11(2), 2010.
[16] Guanghui Lan. First-order and stochastic optimization methods for machine learning. Springer, 2020.
[17] Guanghui Lan and Renato DC Monteiro. Iteration-complexity of first-order penalty methods for convex programming. Mathematical Programming, 138(1):115-139, 2013.
[18] Guanghui Lan and Renato DC Monteiro. Iteration-complexity of first-order augmented la- grangian methods for convex programming. Mathematical Programming, 155(1):511-541 2016.
[19] Sangkyun Lee, Stephen J Wright, and Léon Bottou. Manifold identification in dual averaging for regularized stochastic online learning. Journal of Machine Learning Research, 13(6), 2012.
[20] Evgeny Levitin and Boris T Polyak. Constrained minimization methods. USSR Computational mathematics and mathematical physics, 605):1-50, 1966.
[21] Qihang Lin, Selvaprabu Nadarajah, and Negar Soheili. A level-set method for convex op- timization with feasible solution path. SIAM Journal on Optimization, 28(4):3290-3311 2018.
[22] Tianyi Lin, Chi Jin, and Michael Jordan. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pages 2738-2779. PMLR, 2020.
[23] David Martinez-Rubio, Elias Wirth, and Sebastian Pokutta. Accelerated and sparse algorithms for approximate personalized pagerank and beyond. arXiv preprint arXiv:2303. /285,, 2023.
[24] Julie Nutini, Mark Schmidt, and Warren Hare. "active-set complexity" of proximal gradient: How long does take find the sparsity pattem?? Optimization Letters, 13(4):645 655, 2019.
[25] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds first-order methods for convex-concave bilinear saddle-poin problems. Mathematical Programming, 185(1):1-35, 2021.
[26] H. Robbins and D. Siegmund. A convergence theorem for non negative almost supermartingales and some applications. In Jagdish S. Rustagi, editor, Optimizing Methods in Statistics, pages 233-257. Academic Press, 1971.
[27] R Tyrrell Rockafellar. Conver analysis, volume 18, Princcton university press, 1970.

---

[28] Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015.
[29] Yifan Sun, Halyun Jeong, Julie Nutini, and Mark Schmidt. Are we there yet? manifold identification of gradient-related proximal methods. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1110-1119. PMLR, 2019.
[30] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B [Methodological), 58(1)2667-288, 1996.
[31] Stephen J Wright. Identifiable surfaces in constrained optimization. SIAM Journal on Control and Optimization, 31(4):1033-1079 1993.
[32] Yangyang Xu. First-order methods for constrained convex programming based on linearized augmented lagrangian function. Informs Journal on Optimization, 3(1):89-117, 2021.
[33] Yangyang Xu. Iteration complexity inexact augmented lagrangian methods for constrained convex programming. Mathematical Programming, (89(1))199-2444) 2021.
[34] Liwei Zhang. Yule Zhang. Jia Wu, and Xiantao Xiao. Solving stochastic optimization with expectation constraints efficiently by stochastic augmented lagrangian-tyPe algorithm. IN- FORMS Journal on Computing, 34(6):2989-3006, 2022.
12

---

Appendix
Limitations
14
Comparison with Frank- Wolfe
14
Auxiliary lemmas
14
Proof details in Section
15
D.1 Proof of Proposition
15
D.2 Proof of Proposition
15
D.3 Proof of Proposition
15
Convergence analysis of APDPro
16
Proof of Proposition
16
Proof of Theerem
16
Proof of Corollary
19
Convergence analysis of rAPDPro
20
Proof of Theorem 2
20
Proof of Theorem
22
Proof details for sparsity identification
23
Proof of Proposition
24
Proof of Theorem
24
A multi-stage accelerated primal-dual algorithm
25
Experiment details
27
Structure of the Appendix
The appendix is structured as follows: Appendix A introduces some limitations of our methods, primarily concerning the application scenarios of our algorithm. Appendix [Bincludes comparisons between ours and some related Frank- Wolfe methods. We give some auxiliary lemmas in Appendix which are very important for the proofs presented later. Appendix D and present the proof of conclusion in Section algorithm to obtain a convergence rate without complicated dual updating. Finally, Appendix offers more extensive details our experiments.
and 3 respectively. Furthermore, Appendix H introduces new
13

---

A Limitations
In this paper, we focus on the theoretical analysis of convex optimization. Although our proposed algorithms for the convex optimization with strongly convex constraints can theoretically improve the existing results from (11/e) (11/VE). However, we still need to point out that our optimization algorithm has the following limitations. One is the algorithm needs a lower bound on the norm of sub-grad gradients of the objective function in the optimal solution, which may not be satisfied for all functions. On the other hand, we require consistent smoothness of the constraints to ensure convergence, and how to use the line search method to ensure convergence a future direction.
B Comparison with Frank- Wolfe
We note that the strongly convex function constraint in ① is a special case of a strongly convex set constraint, as demonstrated in [15]. Over the strongly convex set. has been shown that Frank- Wolfe Algorithm (FW) can obtain convergence rates substantially better than the worst-case (1/EE) rate. show that FW obtains linear convergence over a strongly convex set. Nevertheless, the uniform bounded gradient assumption appears to be stronger than ours, as we only impose the lower boundedness assumption on the optimal solution x" and allow the objective to be non-differentiable. More recently, [10] shows that FW obtains an (1/ /E) rate when the gradient is the order of the square root of the function value gap. For more recent progress, please refer to [5]. Despite the attractive convergence property, FW exhibits certain limitations when applied to the general function constraints (T) addressed in this paper. Specifically, FW involves a sequence of linear optimization problems throughout the iterations. While linear optimization over certain strongly convex sets, such as b-all, admits a closed-for form solution, there exists no efficient routine to handle general function constraints explored in this paper.
Under the bounded gradient assumption, 7 20
C Auxiliary lemmas
The following three- three-point property is important in the convergence analysis. Lemma 1. Let f: IR" + RU(+o0) be closed strongly convex function with modulus μ 2 0. Give X E X. where X is compact convex set and 1 2 0, let x* argmin f(x) + -11x x|| then
for all x E X, we have
f(x) + || x12 2 s(xt)
++ 1x 2
x|
+/1lx x11
Proof. Since X' is a convex compact set, <(x) == [x(x) + [x) 11 is lower-semi-continuuus
(0
E X
and (μ + -tstronyyyy convex, where Lx(x)=
Using the optimality (0 o(x+)) and
$ x
strong convexity, we have o(x) 2 <(xt) + (0, x - x + | - x||², for any x X. This immediately gives the desired relation.
The following result is adjusted from the classic supermartingale convergence theorem 26 Thcorem 1I. We give proof for completeness.
Lemma 2. Let (St F, IP) be a probability space and Fi C ... be a sequence of sub-o -algebaas let aj, by and ej be non-negative F, -m-euuur random variables such Elast1 F,] S aj - by + cj. then we have lim aj < co exists and Σ}=1 by < oc a.s. when Ej= Gj < xc.
F. For each j = 1, 2,
Proof. Define d, = aj - Di= - bi) and for any à > 0, define = infftt Σt q > a}.
j < I, we have
Eldj41 FU = E(aj+1 - Ei b,) F S aj Ei=l (1) b,) =: dj.
(18)
where (a) holds by Ela,-1 F5] E aj + C, bj. and hence
E(dmi(400+)
F. d + Bids+1 Fal4(c08) S dmin(es)
14

---

oo) is supermariigale. & where (a) holds by 18 Therefore, we have (dmmn( F,, F,,15 Since
dmin(t..) = (min(ed)) Ei= -
bn) Ei= min(t.(f-1)1
a -u,
holds for all j. where (a) holds by (m)n( b 2 0. Then it follows from the martingale convergence theorem that limy-+so (miu(t..) exists and is finite a.s., i.., lim dj exists and finite on {t = )o} = {= cj I a}. Since ā is arbitrary, we see that limy-so d, exists and is finite a.s. on Ez-1 oj < co.. By dj = aj - Ex= - br). we have limj- Oj exists and finite and 00
2==1 bj < oc when {Ej=1
j=1 Cj < co
D Proof details in Section 2
D.1 Proof of Proposition I
Proof. Under Slater's CQ, it is standard to show that any optimal solution x* will also satisfy the KKT condition. For example, one can refer [3. For any x Xz. we have
f(x) + (y", G(x)) 2 f(x*) + (y", "((()) = f(xx),
where the equality is from the complementary slackness. In view of the above result and the Slater's condition (i.e., G(xx) < 0), we have
f(x) f(xx) + (y", G(x)) 2 f(x").
(19)
Combining with fact I|y" min.e(m)
{ (x)) S - -t", ,(()), then we have
|yy|| < |yy || S ((x))
minsc (x] = C,
(20)
where the last inequality is by f(x*) 2 minxeR* f(x).
D.2 Proof of Proposition] 2
Proof. We prove the uniqueness property by contradiction. Suppose that there exist (x", y"), (x", y*)
satisfying the KKT condition, then from the complementary slackness, optimality of x" and x", we have
C(x", y") = f(x') = f(x') L(X", y*).
Moreover, we have C(x",") I [(x'.8) S L(x y"). Hence, we must have L(x", 5²) = L(x", .²)). However, since Assumption| 2 limplies y * 0. the strongly convex function C(. has a unique optimizer. Therefore, we conclude that x" = xx
Next, we show that the set of optimal dual variables for problem 1 is convex. Suppose that there exist two optimal dual variables yj and y for the unique primal variable x*, both satisfying the KKT O. This implies that any linear combination of yi and y satisfy KKT condition, i.e., (ayï + by G(x*)) = 0, Va, b. From Proposition I we know any optimal dual variable falls into bounded convex set V. The intersection of two convex sets is also a convex set. Hence, we complete our proof.
condition, then we have (yi. G(x*)) (y "i,")(())
D.3 Proof of Proposition
Proof. From the strong convexity of gi (x)) we have (x(x 2 (x())) + di ||x xXI?, which implies
||* x; 2| < (g:(x) (x(x)))
2
(a)
(x{)
m4
Pi
(21)
x x; 1 (x, (xx())
2
(xx
#4i
where (a) holds by (x) < 0. In view of the triangle inequality and the above result, we have
| x S ||x] - x"1 ||
xi1l < 2 (x.)
Hence, x" E int B & mingemm 2/
29 (x;)
15

---

E Convergence analysis of APDPro
E.1 Proof of Proposition
Proof.
Using the triangle inequality and 5 we have
|V [x) & [|VG(x*) - -VG(x")-VG(()) - &xxl&
x"11.
Combining the above inequality and we obtain
y 1 Lx | - x'|| + VG(()]|
(22)
Next, we develop more specific lower bounds on ||y 1- i). Inequality ( can be easily verified since
we have ||* x"1 S v23. ii). Suppose (y*) / | x²11 1 23, then together with (2 we have
y I Lx
2 (""'" + [V = Lx
2 Mlly
+ VG(X)]
Note that the above inequality can be expressed at bt Lx y /23/u and
S 0 with Ily 1 r
[VG())| Standard analysis implies that (b+ /b2 4ac) /2a, which gives
the desired bound I0
E.2 Proof of Theorem 1
Proof. First, it is easy to verify by our construction that (5% is monotone sequence: ) 3/2 2 2 ..... Our goal is to show ) S V& holds for any 2 by induction. Note that y C Vo immediately follows from our assumption that (y*) 2 Pu. for any y" E )r Suppose that
y" C holds for = 0, O..... K -,-,, 1, we claim:
1. For any x X' and y", we have
((xk,y) [(x, S (xx,))
tx- IK-ITK-1 2Tk
|x xx 1|2
(23)
2. y" Cyk.
Part 1. For k = 0,1, K - 1, taking (z and f(-) + (VG(x))N+H1,) in Lemma following relations
] the
(y++1 - y,2x) S Akt1,
(24)
f(xx+1) + (yk+1, VG(x)) (xx+1 - xx) s f(x) + B2+1,
(25)
where
As+1 A 1. (lly - yxll 1|y - Yk+1 ||y+11 - yx113)
(26)
20
Bx+1 A 2T (||x - Xx 1- |x X |
| Xx 112)
(27)
hold for any x E X' and E NosuSk Vo. The existence of such y follows from our induction hypothesis. Since TT Gi-)) ptrsonly convex, we have
(yK+1, VG(x)) (xx+1 - xx)
2 (yK+1. VG(x;) (xx+1 - xx))
+ (yeti, G(x++1) - G(x)) - -(x G(xx)) + f
xx f xx
Combining this result and (25). we have
f(xx+1) - fxx + (y++1, G(xx+1) - G(x))
< BE+1 (ys+1, VG(x)) (x (x++1 xx)) + (yk+1. G(x++1) G(x+)) 2 ||x -x+122 (28)
On the other hand, by the definition of zg. we have
(y ys+1,2k)
= (y yK41, G(xx) G(x++1)) (y Yk+I, G(Xe+1))
(29)
+ (og-1/0w)(y -R., G(xx) G(xx-1)) + (08-1/04((% -K411, G(x+) - G(xx- 13)-
16

---

Let us denote qk = G(xx)) - G(xx-11) for brevity. Combining (24) and 29
yields
(y - yk+1, G(xx-1))
As+1 + (y yk+1, G(xx++1) G(xx)) (ox-1/ow)(y yk. qu) - (ok-1/Ow)yy - y4+1,
(30)
Putting 28 and
together, we have
[(x++1. y) C(x. yk+1)
I AR+1 + Bk+1 - (yR+I, VGI(XH)
(CG((x)T(xxx) [xx+1 xx)) + (yx+1, G(xx+1) - G(x+))
+ (y -k-1,, 9k+1) yk+1,94+1) (ok-1 (y - yk, qu) + (OR-1/OW) (y4+1 - -K,, 9k) -/ x -x+12
< AR+1 + BR+1 + Lxx X xx|1² - 2 ||x x
+ (y Yk+1, 9k+1) (0k-1/0k)(5 - Yk, qk) + (0k-1/0k)(Nc++ - Yks qk),
where the last inequality is by Lipschitz smoothness of (yx+1, G(-)).
Next, we bound the term (qk- Vk+1 - y&) by Young's inequality, which gives
(y++1 Yk, 9 S zot_ Iy -yall + - ||qu
(31)
follows from 31 and o | 2 12 x xx11 that
((xx+1,8) - ((x,))+))
Th -p Pb x| - x+|2 2 xx+12
Tk ||x x (ok-1/0w)o |qqpl 1 2 9 1|
|
(32)
1 (lly - Ily yk+1l (y -841, 9k+1) - (ox-1/ox) (y yk: 9k)
20
(an- 1 1/ww/// ly yı 1| + م200 2 |
Xx Io - | - x1:12
2
Multiply both sides of the above relation by tx and sum up the result for = 0, 0,,,,..,,5 K 1. In view of the parameter relation (1I. we have
Σ te [[xx++1.) L(x, yk++
(a)
1o(7
pu)
||x - xxol2 IK 1TC-11
|x x xxxl1 1x-10k-- |/x]1
(33)
tog 2
ly yoll2 1K-10K Ily yK 112 + tK-i YK. yk. to - yo. yop
tx (x-17kー1 ||x xx12 x xoll2 + 20 |ly yoll
270
where (a) uses qo = 0 and x xo. and (b) holds by po = 0, to and
tk- (y YK, qk) S 1 2ox-1 Ily yKll fx
|
2/ox-1
Since y) is convex in x and linear in we have
Tk (((K.))) y(x, s Ex=o to [(xx++1,8) L(x, 8x+1)]
(34)
Combining
33 and 34
we obtain
Tk [[(k.)) L(x, 2 |x X
xx-
x
-xxl
1 lly yoll?.
(35)
2
20
Dividing both sides by Tk, we obtain the desired result
Part 2. Next we show y Yk. Lety* be any point in yr Since 35) holds for any x E X' and
y DogAsk-1Jl, 2 y"* can place x x" x y* E y in 23 to obtain
*K 1T 2Tk
Ixx - xx||2 + L(xx, y") L(x 5K) < Tx A(x"
Moreover, the strong convexity of E(: implies
((xK.y") 2 [(x",x") (y ||x x" x²1
+ (y
1
1 x=1
X
17

---

Applying the above two inequalities yields
A x
x"
1| Σ
Tx -000 A(x',y)) Tk A(x", y*). 1/2 ||x - 1
1
(36)
0k-1
In view of 36 and Proposition 4 we have that
(y*) 11 1ay"" max { (xK, DorK 1 (AX)) hg(XK, Tx Axx) AK.
ox
Moreover, since ) C VK-I, we have (y") 4 2 PK-1- Hence we have (y") 2 PK where Pk = max PK- is the output of the IMPROVE procedure. Due to the construction of Vx. we immediately see that y E Vkk This implies y" S Vk and completes our induction proof.
Next, we specify the stepsize selection in Lemma Corollary |
3 and develop more concrete complexity results in
Lemma 3. Let PR+1
for k 1 and òI = =3 eL 70
Suppose Tke The satisfy:
k+1
TO
2
IL Lxx + Lgou, Tht1 Tx + pk-17x) 2, xx+1
(37)
Tot1
Then we have
2
2
1.2
1 -0¹ +
Ts 21 8 Pr + 1)k; Ae 2 min min
(38)
-t 9
where OE
2 2.
B,B 1[K
for k = 1. Moreover suppose pro S 2, where C. f3, then we huve
+
(39)
Proof. We first use induction to show that 1 z o 22 + 1/- It is easy to see that
# 2 l
k2 +
%
9
holds for le 1 by the definition أ1 = / To and T p11+ Assume
$ > x2 +
holds for all l = O..... K, then we have
2K11
11
TK
TK
8 K2
o/
+ PK++
K2 1
9
(40)
R 9
K2 + #/2
+ pktipe
3
p (K
+ 1)² +
9
7/7
which completes our induction. It follows from that, for any k >1
1/2 >
22 g
and the relation among Tr, Lk 0k.
2/2
Th - 1-1 to 1+ 1 -1 1=1
- -
To
==
9
> 1+ To E =1+ N (k + 1)k.
(41)
Similarly, we use induction to prove
2 2
(42)
It is easy to find that श 2 min(p1, }1 We assume that Pa 2 min P1), Vk 2 holds for any
k I,..., K. Considering PK+1 we have
1. Pk+1 2 K-1 / B3 K2 + K
R+1 (min (=)) K2 + 3p1 min (11 K 2 min (p):
18

---

which completes the induction. Moreover, we use induction to show o - oz + 1)2. It is obvious that the inequality holds for k 0. Assume the inequality holds for all k 0, ...... K, then we have
x = x + PK+1 8
ok + Рк+170000к
(43)
< oB (KK +1)² + PK++77(K +
S og(K + +)²
where the last inequality use the relation pk S p, Vk. and pTo S
E.3 Proof of Corollary !
Proof. First, we show that the sequences {Tk, The tk. pk] generated by APDPro satisfy the relation- ship in (II) in Theorem
The first part of I1 can be derived using the monotonicity of {px} as
follows:
t
(ktt
Pk+1) = (ON+ITH+1 0K+IPE+1)
0 (ONTATRII Ok+1PH+1)
t5 (ox(1 + PL+11t)/TH - ok ok-1Pk-1)
00 (0x/TH Tk + Pk+10k ok+1Pb+1) S T
The second part of [I be easily verified using the parameters setting.
Next, we prove the last term in (TP by induction. Firstly, it easy to verify that for any do > there exists E (0, (Lxx + T0) such that last term of (TT) holds. Hence, when A: = 0, the last term of directly from the first term of (3). Suppose that the last term of [I] holds for k
1. From OK-1/OK TK/TK-1 I we have
Lxx + 1zxx 2 Lxx lzoo. ox-1/ox
(44)
Without loss of generality, place x x (|)='l
=
+ +0)
[G(xx]]
[G(x 1] in 23 and using
Iy | S in Proposition It is easy to see ||y+ = Ily ||1 + c*
S C, and
1y 11 2 lly =
ly" 1 c Iyy" |12, Hence, conclude that y E Vk. wk 2 0.
Now observe that L(XK, y") L(x", y²) which implies f(xx) + (y", G(xx)) - f(x') 2 0. In view of (y", G(xx)) S [G(xx 11+) ||y"|| [x| )] 1l. then we have
f(xx) + Ily" [I| f(x") 2 0.
(45)
Moreover, it follows from ||y*| 2 ||y'|| that
C(xK.y*) L(x", .yk) k L(X,,y L(x", .y") f(xx) + (Ily"l + e*) [[[([(()))]] f(x)).
(46)
Combining (45 46) and 23 we obtain
max {c" [c f(xx) - f(x")} I
Tx 250 Xo - x=112 +
2000
DP
(47)
In view of the bound in 388 and the relation between Tk, Tk. get
3
(48)
In view of 47 and
38 we have
max [c']][ 11 f(xx) f(x')} < @4Topx(K
2 -|1|x - x²1
200
Combining 23 and 48 yields 1||xx - - <300A(x" ,,,,,,)))))
TO0
19

---

F Convergence analysis of rAPDPro
F.1 Proof of Theorem
Proof. First, we show that the choice of TO = g = ā. Vs 2 0 satisfy the condition
13 in
Corollary (76))-1 2 (1 vo)(r))-1 LxY / / 2 xxx + cl c
Next, we show (15) holds by induction. Clearly, (15) holds for s = Assume l|x
x=1
11
<
A.
holds for ...... S 1. Then by Theorem we have
x
TW As D3
(49)
o8
In view of the first bound in (38 and the relation between N, N. we can get
9 OOTO
(50)
N
Combining (49) and 50) yields
|| x²2 S (DN, Ng.)²
18
DDG
08rglNN, N.Y².
Since the algorithm sets N, mmax (6(NN, T0) that
V²" -3/2Dr (pN, Dx ()og))
( }1, it follows
(pN, Tú)² 1.
(N N.)
36
9D3
9D3
2 1
TO [pN, N.
18D
which implies the desired result
(5)
Let the algorithm run for S
logg D /E)] epochs, then ||x x1 D3 2- <.. The total
iteration number required by Algorithm 2 for attaining a solution x such that | x=1 S E
ES No S ===0
>>S
6
V2 +1}
PN, 70
1)
(S +
3rDDY
Es=0 V2"
W170
DxDxy 1600
12
2
Dx 1oga
1
3vEDy
1
VE
w2Dx Vo
V2-1
logg
Dx Vs
+1
3v2Dy (v++1)
(V2 102 -1)
m,Dx 7806
12
2
loga
Dx
+1 VV
(v2(2)+2)
Ve:
where (a) holds by E5 (,2)) )-1 = (51) -1 11 and Σ V2' 10x, = =102) V2".
Now, we give some proof details in dual convergence results. Let
(x(x,)) = (T,)
2 x X 2 + ,,, Iyy y,1 + (a,-1/03) (y; y, G(x;) - G(x;-1))
(ag-1/05) [G(xx) 111 2/4;
then we establish an important property about the solution sequence in the following lemma.
Lemma 4. Assume 7-1 > p and choose Vi > 0 such that
1> inf / 2 8 vi--
(51)
120
Then there exists 1/2 > 0 such that for any > 0 and any KKT point (x", .y*):
0 0514)((x',5' 14+10++1x 8²) - unly 25, |xj+1 - -x,|1 + 20, |l - -3,1
0 0<t,2,(x',5
20

---

Proof. First, we give some results that will be used repeatedly in the following. For notation simplicity, we denote 8 = o- In view of Lemma 3 and the parameter ergodic sequence generated by rAPDPro, we have {(Tz)=', " is monotonically increasing sequence in k TÚ u 4 = 1, Vs O, and there exist 23 > 0 such that ē + Va S g m ). Now, for rAPDPro, we claim that there exist v1, U2 > 0 such that the following two conditions hold
1. For any j 2 0, we have
min {1 (1-8,(T))
5, (T, Lxy Lggg))s} 24 >0,
(52)
and
1 min [5 pg. oz
03-1 } 2 12 >0. O.
(53)
2. For any j 2 0, we have
0 S (xx))((xx)))''x=x)""""" "") ( (Xxp (1,x1111111 (54)
Part 1. We first consider two subsequent points x, and x,+1 within the same epoch, and assume
j ~ k). Then, it follows from 0% = / that
-
1) -
1-6 uo.
(55)
of
of
Next, we use induction to show
1-v0 2 Lxv + LGog8-1
(56)
When k = 0, inequality (56) degenerates as the definition TÚ: og. Suppose (56) holds for
k 0, I..... K - 1. Then, from 0g = - - S 1, we have
(o-)o = (1- - vo) 0K) 0 > Lxv + Look 1- 2 Lxx + Look00
0k
which completes our induction proof. Hence, combining (55) and 566. we have
min {1 - 6, ((Tk)= Lxv / vo.
Wk e [N.].
(57)
Furthermore, when switching to the next epoch (s + + 1), we have
(0)
(b)
-
2 oith ((a)tt) (oxx) 1
2
l - o+1 go- = 1 ōg
((To+))) LXY L660-100 .+ )m0
VOT
s+1
MOT,
(58)
where (a) holds by 0j 1, ā 1, (b) follows from (a -1 > 1- Hence, combining (55
and (8) we completes our proof of (52 by setting v1 min ãa 100 un).
Since rAPDPro reset the stepsize periodically and [1i: (Tx) } are two monotonically increas- ing sequences, hence
inf (T, p3) 1 p) 7-1 P. $20
(59)
Consider infReIN.) (o - 80 /o Combining 8 + 1o S infREIN, (07), then
11 5 of inf ke[N_]
inf tg - 5/02) 2 Myo. mسー ke[N.]
(60)
Furthermore, when switching the next epoch (s + + 1), we have
inf 1s+1 o0 + (1 5a (ox,) 1) = x² inf 8(07x) ( 8), .20
(61)
#20
where the last inequality holds by ā = o. < xx. Hence, it follows from (5). there exist 222 min(7-1 - p, 100 / (1 8)} such 53 holds.
(60) and 61 that
21

---

Part 2. for any 2 O, we have
44100+1(x", 8*) s 1/( (5) xx x G(x)),1 y 2
(62)
+ (20,)) -1y ys+i 12 + 2 [G(xx+1) - ((x))
Consider E 10. N. Inequality (5T implies 11
holds (see proof of Corollary in
Section E.3
Hence, for 0 S l No. we have
1)+10 .y) s tx ( I|x
+ + (G(x - G(x)). -3")
(63)
2 lly 1i++1ll 112
2 [[((+)++) G(x))1l²)
where j corresponds k). Furthermore, consider switching to next epoch (s - s + 1). Since i (T)) -1 is increasing sequence in k. p0+1 0, t 1, hence
1. (T
2 to (r0 (1ot1)-1
p 10 ss 2 0.
(64)
Next, we have
(a)
N.
(6) 1++1 (c)
to+ 1001 N. oi.
(b) 2 1otloot
(e) 1otlogt100+
(65)
where (a) holds by the definition of t = z (b)
holds by {tt, of is an increasing sequence in k.
and (c) holds by 06+1 = 1. Hence, by 64 and (65) we have
1f+1Q5+1(x', y I UN
x
x 112 + " [G(x) xll
N,
(66)
yot
+1 | + (G(x G ((x
where j corresponds to (s, No). By putting 63 and (66) together, we complete the proof of 662
Placing yx (x*, y²), (X++1. VK+1) (x)+1.)5-1) in 32 and multiplying t, on both sides, we have
0 S [((xx+11,))) - y5+1)]
1 -ps |x x,1²2 ]
2 ||x - -xi+111 1|
0 |1 1 1i+1ll
20/0,-1
25/0,
+ (20,) -1 (lly ysll² - -lly --lyyyy -i++1l1 113 + (y y,t1, - ( yj
oj 0,5/0,-1 1y - -25112 +
La
|| x,11 -5,15-5--- -Lxy |x,-1 - -x,1
28/0;
2
S 10 - 1++1 1x+1(xx (x",)")) - -n 1 1|x,11 -x,1 x11 2 + (20,) ) -ly - y5 13
(67)
where the last inequality holds by 62) and 52
It follows from 53 03-1/03 s 1 and
(y, 3y-ン".a ..) 2
1 26
1
8/0 1 - yxll
that
[12,(x,8)) 2 1y (2Tg) - ||x - 11 2 + (2a,) 3 -18-= - -111² 20,-1 lly - 5²))3)
(68)
12 X x,| flly, y 5011 > 0.
Combining 67 and 688
complete our proof of (54
L
F22 Proof of Theorem
Proof. Since {(x),,5}} } located in set X' x 3 is bounded sequence, it must have a convergent subsequence lim (x)., yi.)) = (x*,y"), where y* is the limit point. We claim that limit
point (x*,y") y²) satisfies the KKT condition. Placing aj (x*, bj
x, 1| + (2or,) ||y+11 | and ej = 0 in Lemma It follows from (54) in Lemma that
aj 0, by 0. Hence, we have Eラ= ||x++1 x11 2| oo, and Ei= ||y y, co, which
22

---

implies 1om ||x x,++1|/ = and lim 1ly, -o 12= O. There are two different
cases for Jjn when In > oc, and we discuss the value of B),+1 (25) decided by Tja. each of the two cases below.
Case 1: Jyn oc. By the definition of Bj,+1 1 in 27 and lim, |x3 xj
we have
B1 $ | - xj,+ ||x
xj, T/ T..
0.
Case 2: Jjn = cc. It follows from (39) that T,, increases at order (kk), where jn ~ (s, ks. By 23
we obtain ||x xj,l decreases at order (1/kk) (n ~ (s,k)) Hence, combining lim ||x,,
xj,++ 1 0, have Bz,+1 S Tim (I|x * x1l1x x;. "33 0. It follows from
limm-+00 X)n = x", limm-+00 Ba,+1 0 and (25) that
f(x') + (VG(x")y "i"x""y",> xx) S f(x) + (VG(x") "x", VX E X.
Hence, according to the first-order optimality condition, we have
0f(xx) + VG(x")y" +Nx((x)).
(69)
Next, we show the complementary slackness holds for (x", y").. Since Jj has upper bound o lly - -/++1ll || I Dy, lim,-+50 |ly,, +1++ 0 and the definition of Aj,+1 in (26). hence we obtain Aj,+1 S 1 [1v;,
pn j- -j |llly - yj++ill) "=30 0. Combining above, lim Nj, y and (2)) we have 0 S (G(x"), y*)) I -G((xx)) y).. vy E V. Moreover, due the complementary O. Hence, we must have (G(x*). y*) y") = O, which, together with (69). implies that (x", yy" ")" is KKT point.
slackness, there exists an y E ) S such that - -(G(x"),
G Proof details for sparsity identification
Our proof strategy of active-set identification in rAPDPro is similar to those in unconstrained optimization 24]. Namely, we show that the optimal sparsity pattern is identified when the iterates fall in properly defined neighborhood dependent on 7). The next lemma shows that the primal and dual sequences indeed converge to the neighborhood of the optimal primal and dual solutions, respectively, in finite number of iterations.
Lemma 5. There exists an $₁ such that
|| - x"1 x $1 xx1| and 11 -y"ll lly
11 Sr
(70)
where (x*,y" is the unique solution of problem 17 Moreover, there exists an epoch So 2 S1 such that Vs 2 So, we have
1yy
y"1l V ||x; x"1|
3LxY o (2Lxx)) Vk: 1, No.
(71)
Proof. From Theorem 2 and we have lim (,) = y"), where j corresponds to (s, 0). It implies that there exists an epoch Š₁ such that (70) holds.
follows from (35 that ||x]
x"1
- x* 13/Tá + lyý - //1/// Hence, in Te +2 we need prove
I Vogta
order prove xi
31xx
7f x x11 + of Ily y+1l3 S 3LXY +2
(72)
we know that the left hand side of (72) converges to 0 and right hand side (72) is a positive constant. Hence, there exist S2 such that (72) holds, which
From Corollary T and Theorem
implies 7T) holds for k = 1, s = S2. Now we use induction to prove, for Vk E [N we have
32 1x
So 112 +
Ily -²13)) 1/2 <
17
(73)
B2
3LXY 82 Th
(2Lxx))))
To
23

---

When i 1. inequality 73
coincides with (72 with Sz. Now, assume 73
holds for k we aim
prove 773 holds for follows from (35 that
S2 |
(0)
Te+1
Sa
k+1
3xxY
22 +2
3xxY (2fxx)
"
3LxY
(2
where (a) follows from induction, holds by 82
82
L and (c) holds by S.
S2
&
kot k+l
k++l S %k
Hence, we complete our proof of (73. From Theorem 2 we have | x - D3 2-, which implies that there exists a S3 = 2 [Dx
3LxY (3xx
(2Lxx 331 such that ||x x' -
Dx 2 Sy I "
F aLxy #+(2Lxy)-1 which implies that || - x"1 - D3 2 S 3LxY (2Lxxx))
holds for any 2 Sz.
It follows from the definition of $ in (70) and stepsize will be reset at different epoch, then we have (72) holds for 2 mS, S2). which implies that (73) holds with substituting S2 as any 2 max ($1, Furthermore, it follows from Theorem 3 that limy-eo yJ = =y", where corresponds (s, k). Then there exists S4 such that the first term in (7T) holds. Hence, we can obtain that there exist a S. = max (S, (1, S2, S3, 54} such that holds.
It is worth noting that the primal neighborhood defined by the second term of 77 is bit different from the fixed neighborhood in the standard analysis [24], which involves a constant stepsize. As APDPro sets T (1/k), both the point distance and neighborhood radius decay at the same (L/kk) rate. Hence, we use substantially different analysis to show the sparsity identification in the constrained setting.
G.1 Proof of Proposition 5
Proof. The uniqueness of primal optimal solution x" follows from Proposition (ensured by Slater's CQ) implies
2 The KKT condition
E 0f(x)) + Vg(x")y"
(74)
According to Assumption 2 we have x* * O, hence (x )- = (1. B} A(xx(xx) + 0. In view of 774. for any E (x),, we have p.X ||x;)|| VV(g)(("") ly", which gives unique y". N
G.2 Proof of Theorem 4
Proof. It follows from the Lipschitz smoothness of g(-) and property 77 that for any 2 So, we have
V Vg(x || [ (x(
Vg(x Vg(x")yūi+)
(75)
Lxy | - S 3 - k Os...N..
Recall that the primal update has the following form
x = argmin xEX
E + (Vo( + 1 ||x x
2
Since TĀ/(TT + (2Lxx) is monotonically increasing with respect T for the strictly feasible point x, we have
x|| (a) 5 3ixx F+ + 1|x" x
|x
(76)
(8) ( + minge(m) 2/ -2)((x))
14
24

---

where (a) holds by (Z1), F = Th and (b) follows from the definition of x"x x and Ç. Inequality (6) implies that x int X, and hence (x {0}. In view of the optimality condition, we have
Fk (xt
+
Vg((
E p:00l[z isis
(77)
Our next goal is to show [ (()) = X satisfies condition 77 for i E A(x'). Placing X(() = x(() in [Vg(x{))
(x x )] (0)1 ||+ we have
+
7%
V g x yy #2 (xx x
IN IV 1n
V x xy 1 || + || (x(0) - x
o
+ V y + (2
(Ixy)
(78)
2222)))))))
1] + [x9(x")y"1
(22xxx))
+ [ yy (()) & Pss vi A(x)).
In above, (a) follows from 71 and 75
(b) follows from
[[ )y) - g( Jy la)) S lly - y''ll S 3
and (c) holds by the definition of 77. Combining (77) and 78) we have A(x*) S A(xi+1), 2
So. Ak E [N.). which completes our proof.
Table 1: Datasets description and parameter settings
dataset
Node(n)
Edge
b
bio-CE-HT
2617
3K
-0.04
0.4
bio-CE-LC
1387
2K
-0.05
0.4
econ-beaftw
502
53K
-0.01
0.995
DD68
775
2K
-0.005
0.4
DDD242
1284
3K
-0.05
0.4
peking-1
3341
13.2K
-0.001
0.4
H
multi-stage accelerated primal-dual algorithm
Both the previous algorithms need to solve a complicated dual problem that involves linear cut constraint, posing potential issue: the associated sub-problem might lack closed-form solution. To resolve this issue, we present the Multi-Stage Accelerated Primal-Dual Algorithm (msAPD) in Algorithm 3 which obtains the same ((I/VE) complexity without introducing new cut constraint. Our new method is a double-loop procedure for which an accelerated primal-dual algorithm with a pending sub-iteration number (APDPi) is running in each stage. While both APDPi and APDPro employ the IMPROVE step to estimate the dual lower bound, APDPi only relies on the lower bound estimation to change the inner-loop iteration number adaptively, but not the stepsize selection.
We develop the convergence property of APDPi, which paves the path proving our main theorem. For the convergence analysis, it suffices to verify that the initial stepsize parameter To og satisfy assumptions in Theorem
Theorem 5. Let { Vi} be the sequence generated by APDPi, then we have
(()).y") L(x", si) < (x" (xxxxx'')) y"), ||| x" 112 (y uK A
(79)
where Ax(x",y") _ 2 ||اا - x" 2 2:E
II y 1 and (x", (yn) is KKT point.
25

---

10a
10
10
APD
10-3
10
MirroProx
10
APD
10-5
PAPDPro
rAPoPro
10
MimorProx
miAFD
APD-restart
10-1
APD-restart
msAAR
10
0.2
0.8
10a1
10-2
10-3
APD
NirrosPrro
IARDPro
Mirro-Prox rAPDPro
msAPD
APD
APDerestart
Mirrar Prox
10
10:41
miAPD
APD+restart
10-41
10-10
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.6
0.8
0.0
0.5
1.0
Figure 3: The first row is the results of objective convergence to optimum, where the y-axis (11/ ||)) for rAPDPro, and (() reports (() |D++)>*\1)//)''>>>>>>>> [1) for APD, msAPD and Mirror-Prox. The second row is the results of feasibility violation, where y-axis reports the feasibility gap log (max G(x+)]) for rAPDPro, and log (max((, G)))) for APD, APD+restart msAPD and Mirror-Prox. Datasets (Left-Right
order) correspond DD68, DD242 and peking-1.
Algorithm 3 Multi-Stage APD (msAPD)
Require: x" X. E V,
1: Initialize: o 0
2: for = ......... .S do
3: Compute TO [LxY + 180 23 .0 ..22
4: (x*+1,
y s+1 P0
++1) + APDPI(TO og, x ,00
5: end for
6: Output: x s+1 y SS1
7: procedure APDPI(TO oū. Xo. yo, PÚ.
8: Initialize: (x-1.y-1) t (Xo. 800 x
o0,
= 1 + 1 20
D2 276
9: while h < N₂ do
Zs +- 2G((x)) - G(xx-1)
11:
Yk+1 +- argmin |ly (yx + 0122)12
12:
X;+1 + prox,, (xx- 56 V
13:
- + (kSR + (k+1)/(k=1
14:
Pi+1 < IMPROVE(X & D2 Axy ,
15:
Compute N. [max
22+1 }1
ph+1 02
16:
+ k +
end while
18:
return NN NN..P
end procedure
Proof. The stepsize Th = Tū, of = og are unchanged at one epoch, which implies that Pk+1 ie.. 37 are satisfied. By the definition of 70 and où, we have (7d) Lxx + 18,022 LXy + Loog, which means equality holds at the first term in (37).
Since (x) is a strongly convex function with modulus μ4s then we have
L(xK,y") 2 f(x"'x'' + (y") || - x1 G(x",'" 2 L(x', .K).
Summing up the two inequalities above, we can get
(y) XK x" 1
(80)
26

---

Combining 79 and 80 we can obtain the second term of 779.
We show msAPD obtains an 0(1/Vē) convergence rate, which matches the complexity of APDPro.
Theorem 6. Ler {Ra) be the sequence computed by msAPD. Then, we have
| x
2 Vs 2
(81)
For any & E (0, D2), msAPD will find a solution x E X such that | x'11
S & in at most
[loge / epochs. Moreover, the overall iteration number performed by msAPD to find such solution is bounded by
T
8Lxx P%
+2)
logg Dx oe +1 v2)
2D x
Dx VE
Proof. We first show that (81 holds by induction. It is easy to verify that 81 holds for = 0.
Assume |**] x22
A. Dx 2 holds for s O,..., S 1. By Theorem 5 we have
x11 v (y-)
- As + _ D2). Dz)
10
As the algorithm sets Ns-1 = [ max (4/ 8-1 inequalities hold:
10-1)),203 3 /0
As))] the following
2((y") WNs ((Ny"))NN-ITT) 1N < <2(pNs
8-1 Ns
1T ( S 21
D& ( UNS-10
(0N')11 1111 D2 (PNs Ns- 1) -1 - L
Putting these pieces together, we have ||ss runs for S epochs to achieve the desired accuracy E, i.c., overall iteration number can be bounded by
x*1 S
1
As
+ A
As. Suppose the algorithm
2
||
- x11 - D3 2 S E. Then the
Σ N₂
(a) S
2D3 + 1 8-1
+
s=0
1% T0
pkg a Ag
(b)
S Ex= {
(Nrrr + 1) + [ + 2D3
52¹)
p%
xDx
< 8 + +2)
logg D/= 1 + (2 2
2D Pio
Dx
pso
DDx
where (a) holds by Pivg PNo vs 0, (b) follows from the definition of Tō and og.
Remark 11. Theorem 6 shows that msAPD obtains a worst-case complexity of O [log(Dx/ / /V) + (Dx + DD2/Dx)) complexities of msAPD and rAPDPro match when Dx = (211)D))) Dy. Otherwise, rAPDPro appears to be much better in terms of dependence subproblem, which does not involve an additional cut constraint on the dual update.
which is an upper bound of the complexity of rAPDPro (see Theorem 2). The
Dx Dx/Ve. On the other hand, msAPD has simpler
I Experiment details
We examine the empirical performance for solving sparse Personalized PageRank. Let G = (V, E) be a connected undirected graph with n vertices. Denote the adjacency matrix of by A, that is, A = 1 if i j and 0 otherwise. Let D = diag(d)...., dl,) be the matrix with the degrees {d.) y in its diagonal. Then the constrained form of Personalized PageRank can be written as follows:
min xER
||D s.t. 1 (x, Qx) a(s,, D 11112x) < b.
(82)
where Q D-1 -- 3 -=
D-1/2 a E (0, 1), s E A is a teleportation distribution over the nodes of the graph G and b is a pre-specific target level.
27

---

0.
0.9-
APD
Mirro Prox
0.8
APD
APD
0.8
rAPDPro
Prox
0.7
(APOP
msAPD
0.7
rAPOPro
MsAPD
0.7
APD reesaart
0.6
restart
rrestart
0.6
1.0
0.0
0.6
le5
Figure 4: The experimental results on active-set identification. Datasets (Left-Right order) correspond DD68, DD242 and peking- 1. The æ-axis reports the iteration number and the y-axis reports accuracy in active-set identification.
Datasets We selected small-to-median scale datasets from various domains in the Network Datasets (28] We skip large-scale networks as MOSEK struggles to achieve the optimal solution, making it unsuitable for subsequent comparison of the optimality gap. We briefly describe these datasets in Table For more details, please refer to the network repository
Parameter tuning For all experiments, we r minge[n] |dal. μ Amin(Q) and Lx Amax (Q), with (-in(-), Amax denoting the smallest and largest eigenvalue, respectively. For msAPD, we have made additional parameter adjustments. Based on our observations, due to small estimated strongly convex coefficient, msAPD could not switch to the next cycle s early enough. To prevent msAPD from degrading to APD, we iterate according to the predefined number of sub-iterations and manually switch to the next set of parameters. We divide by v2, multiply by 22, and increase the number of sub-iterations in the next period by a factor of /2. For all experiments, we tune the stepsize т, T, from {0.0001, 0.0005, 0.001, 0.005, 0.01 ].01], where т, are the initial stepsizes of rAPDPro, msAPD and APD, y is the constant stepsize of Mirror Proooo All algorithms start with the primal variables initialized zero vectors and the dual variables initialized as ones.
Additional experiment results Figure and Figure 4 deseribe the convergence performance and active set identification results on the last three datasets: DD68, DD242 and peking-1. Furthermore, the Personalized PageRank problem Table 2 The table indicates that, although rAPDPro and msAPD require moderately complex computations to determine the lower bound of the strong convexity parameter, the two methods still accelerate the algorithm's convergence and can significantly reduce the overall convergence time.
we report the time consumption
Table 2: Time summary when max((f(x) (xx-xxxxx(x(x""" /xf(
max (oxx(G()) < 10-3, All experi-
ments were conducted five times, and the results are reported as mean (standard deviation). * means that upon completion of all iterations, the algorithms still fails meet the criteria for both error measures.
dataset
APD
APD+restart
rAPDPro
Mirror-Prox
msAPD
mosek
bio-CE-HT
187.15 (0.86)*
115.95 (1.04)
136.92 (0.92)
370.50 (1.80)*
77.21 (0.67)
0.21
bio-CE-LC
2.58 (0. 16)*
0.65 (0.01)
0.44 (0.01)
4.74 (0.33)*
0.65 (0.03)
0.1
boan-beallw
72.28 (0.59)*
87.12 (0.43)*
18.42 (0.44)
116.13 (1.15)*
66.70 (0.76)
0.16
DD242
43.29 (1.20)*
10.27 (0.39)
6.30 (0.08)
79.16 (0.60)*
10.33 (0.62)
0.16
DD68
36.55 (0.42)*
19.07 (0.66)
22.35 (0.75)
67.73 (1.39)
15.69 (0.37)
0.24
peking-1
122.37 (2.99)*
11.55 (0.69)
4.86 (0.09)
243.45 (7.20)*
11.24 (0.15)
0.21
Nonetheless, we observe that Mosek achieves significantly faster computational efficiency for small-scale problems than algorithm. Therefore, we test the efficiency of rAPDPro some large-scale instances. For large-scale instances, we consider the following problem minxer= ||x Q2x + c. x + d; S 0, = 1, I.... m,, where Q: are dense and positive definite matrix and generated randomly and are generated randomly. Furthermore, feasible region is non-empty. When n 5000 and m 10, MOSEK crashes on our computer, which means not get x" for calculating the optimality gap. Therefore, report the time required
1/11 S.I. x
set proper d; to make the
28

---

for the algorithm to satisfy max[If(x) f(xx)\/ [,, max 0 < 10 and the time taken by the algorithm to complete 10,000 iterations. On this problem. results from small datasets indicate that the performance of the 10,000-step algorithm should be sufficient to meet our specified termination criteria.
Table 3: Comparison computational time seconds between rAPDPro and MOSEK
rAPDPo
MOSEK
24.612
50.38
10
53.997
67.99
12
392
29

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We state the complete contributions in the Introduction section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our work in Appendix A
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
30

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We give all assumptions needed for the theorems proving, such as Assumption 2 and
to ensure the conclusion is correct.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Our experimental reproduction scripts have been placed in the attachment.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
31

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Our experiments use entirely publicly available datasets, and we are committed making our code completely open source.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 //nips.co wttpc//cccpcgguudeeeeeeepeeeepee htt.ggiddde//oeoubibeeeeeeeeeeee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
All details can be found in the paper and supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
32

---

Justification: Since our algorithm is deterministic, our experimental results do not report standard deviation correlation results, but we have experimented on wide range of datasets to demonstrate the robustness of our algorithm.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative eтror rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All experiments
Mac mini M2 Pro, 32GB.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://pw...p..ppp....ooppoctttt
Answer:
[Yes]
Justification:
The code in submission is fully compliant with the NeurIPS code Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
33

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
34

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The creators or original owners of assets are properly credited, and the license and terms of use are explicitly mentioned and respected in the paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification:
We provide complete document of our code.
Guidelines:
The answer NA means that the paper does not release assets. Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
35

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as institution conducting the review.
36


Reviews:
[{"review_id": "FQNVU22r3i", "reviewer": "Reviewer_8Vg8", "summary": "Overall, this paper introduces a new idea and new result which is that we can accelerate constraint optimization as soon as the constraint sets are strongly convex. This result is very interesting to the community, but the paper’s writing is really bad as it is and needs a huge improvement to be publishable in my opinion.", "questions": "- l.7-8: « Our approach, for the first time, effectively leverages the constraint strong convexity, obtaining an improved complexity of $O(1/\\sqrt{\\varepsilon})$ ».\n- l.27-28: « When the objective is strongly convex, the complexity can be further improved to $O(1/\\sqrt{\\varepsilon})$ [cite refs]».\n- l.42-43: « Specifically, direct applications of previously discussed algorithms yield an $O(1/\\varepsilon)$ complexity ».\n\nIs this acceleration result novel?\nWhile I understand that the authors mention a 2-loops vs single loop procedure, this must be clear from the beginning. I find the abstract a bit overselling if there actually is some method, even using 2 loops, that achieves this accelerated rate. I suggest the authors be more specific in their abstract if this is the case.", "limitations": "No limitations other than the claimed assumptions.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "This paper addresses an important problem, constrained optimization, and shows that we can achieve a Nesterov-like acceleration over such problems.", "weaknesses": "Here I list all the remarks that I would like to address, going from typo to concern. They are not all of equal importance, I list them conserving the order of the paper:\n\n- l.87: Can the authors be more precise on which upper bound it is? Is this some known upper bound that we need to use in the algorithm? Or $||y_0 - y_*||$ would work? This is not clear from here.\n\n- l.125: Authors should specify the derivative. Which variables are we deriving against?\n- l.125: $y\\geq 0$ is redundant with $y\\in\\mathbb{R}_+^m$.\n- l.125: I suggest to the authors to avoid such a sequence of different types of relations and instead write \"$G(x^*)\\leq 0$ and $<y^*, G(x^*)> = 0$\".\n\n- l.131: « easily verifiable ». Can the authors explicitly say how? I understand in the particular case they mention right after, but in general, it would require finding all minimizers of $f$ and check. But no practical algorithm is guaranteed to provide an exact solution to unconstraint minimization of $f$, and even less to provide all of them.\n- My personal point of view on Assumption 2 is that, while Problem 1 would be equivalent to an unconstrained minimization problem if this assumption is not verified, we would like to have an algorithm that covers both cases to avoid the need for determining in which case we are. Except if, as authors pretend, Assumption 2 is easily verifiable. It is fair to make an assumption if the most general case if hard to solve, but I think the authors should not underestimate the importance of this assumption in their text.\n\n- Section D1 eq 19: Authors should not use $\\Longrightarrow$ instead of « then » or « thus » or « it follows ». $A \\Longrightarrow B$ has a very precise signification. It means that if A, then B, but without knowing if A is verified. Which is different from stating A as a true statement and concluding with B.\n- Section D1 eq 19: The last $\\leq \\bar{c}$ should be replaced by an equality by definition of $\\bar{c}$.\n\n- l.141: Is the closeness of the subdifferential set of proper convex functions a result originally dated back to 2017? Otherwise, I think a more relevant reference should be preferred. This applied to other references in this paper. Authors should prefer original ones except a more recent one brings some very clear and new explanation to the claim.\n\n- Authors should add a sentence after the different statements they make with a clickable link to the place where we can find the proof in their paper/appendix.\n- l.141: « we derive a subdifferential separation result ». Where is it? From assumption 2, I understand that $d(\\partial f(x^*), 0) > 0$. So if $r$ depends on $f$, the statement is trivial, if it is uniform over all the problems, then it needs proof.\n\n- After stating Assumption 1, the authors should define $\\tilde{x}$ as a generic notation for the existing strictly feasible point so that it can be used later. Otherwise, the $\\tilde{x}$ is not defined in Propositions 1 and 3.\n\n- In general, I suggest the authors motivate their lemmas/propositions/theorems before stating them (e.g. Proposition 3). Otherwise, a reader does not know where all this is going.\n\n- Proposition 3: Why add a $\\zeta$? Since $\\tilde{x}$ is in the interior of $\\mathcal{X}_G$, the first inequality replacing $x_1$ and $x_2$ by respectively $\\tilde{x}$ and $x^*$ should be strict, and therefore $\\zeta$ can be set to 0.\n\n- eq.7: At this stage, the authors explain that we can straightforwardly prove some bound but we do not know why it is useful, nor what it means. More motivation and discussions are needed to improve the writing of this paper.\n\n- l.164: For better readability, I suggest the author use classical tools. What they define as $prox_{f, \\mathcal{X}}(x, z, \\eta)$ is simply the prox of $f$ at a different point: $prox_{f, \\mathcal{X}}(x - \\eta z, \\eta)$. Otherwise one can think that the authors assume access to many different oracles, the proximal operators of many different functions.\n\n- l.178: $N_\\mathcal{X} \\rightarrow \\mathcal{N}_\\mathcal{X}$\n\n\nAlgo 1:\n- l.4: « Compute $\\theta_k$ ». How? Eq.11?\n- $\\theta_k$ is only used in l.5 which defines $z_k$, only used in l.6. I suggest authors merge those lines into a single one.\n- l.8: 3 updates in one line. Authors should at least use « \\qquad » to separate them and increase readability.\n- l.10: Update how? In any way as soon as Thm1 assumptions are verified? $\\gamma$ is not defined in Thm1. Should we look at Cor 1? It is then defined as $\\sigma / \\tau$. Why do we update it after updating $\\sigma$ and $\\tau$? It is not even called in Algo 1.\n\nThm1:\n- Why assume that $t_{k+1} / \\sigma_{k+1} \\leq t_{k} / \\sigma_{k}$ (second inequality of eq.11) while in Algo 1, $t_k = \\sigma_k / \\sigma_0$? The assumed inequality is necessarily true and even an equality.\n- Concerning the third assumption in eq.11, we discussed it above: the expression of $\\theta$ should be replaced in the algorithm for better readability.\n- Replacing $\\theta_k$ by its expression, one sees that the second inequality of eq.12 simply reads $\\delta \\leq 1$.\nIn summary, the second and third assumptions of eq.11 and the second assumption of eq.12 should be removed and replaced by the sole assumption $\\delta\\leq 1$. Moreover, since $\\delta$ is used nowhere in the algorithm, nor in the consequence eq.13 of Theorem 1, but only mentioned in the first inequality of eq.12, we can replace it with its largest possible value, i.e. 1.\nFinally, in conclusion, authors should replace eq.11 and 12 by\n$\\tau_k(1/\\tau_{k+1} -  \\rho_{k+1}) \\leq \\sigma_k / \\sigma_{k+1}$ and $L_{XY} + L_G^2\\sigma_k \\leq 1/\\tau_k$, making the statement much clearer.\n\nCor1:\n- Again, $\\delta$ seems to be used only in the first assumption and neither the algorithm nor the guarantee depends on the choice of $\\delta$, so why not just fix it to the most permissive value, i.e. 1?\n- $\\theta$ is defined for a single used, so why not avoiding a new definition?\n- $t_k$ is finally fixed as in the algorithm. If the authors want to be more permissive in the theorem, $t_k$ must not be fixed in the algorithm.\n- A new notation arrived: $\\gamma$. Why? This is not used in the algorithm.\n- Moreover, all those assumptions can be simplified a lot. First, the last equation of the second line simply writes $\\tau_k^2\\gamma_k$ is constant. Removing $\\gamma_k$ and writing all this in terms of used quantities, we have that $\\sigma_k\\tau_k$ is. constant. In conclusion, the algorithm is parametrized by 3 sequences:  $t$, $\\tau$ and $\\sigma$, with $t\\propto\\sigma\\propto 1/\\tau $,  which can be greatly simplified using only 1 sequence.\n- The two only useful assumptions of theorem 1 now write (with this new proportionality assumption of Cor.1, introducing $c_0 = \\tau_k\\sigma_k$):\n    - $\\sigma_k / c_0 \\geq L_{XY} + L_G^2\\sigma_k$ and using that. $\\sigma_k$ is increasing as pointed out in Remark 3, it suffices to verify this inequality for $k=0$, explaining the first inequality following l.194 (to be taken for $\\delta=1$): $c_0 \\leq \\sigma_0 / (L_{XY} + L_G^2\\sigma_0)$.\n    - $c_0 \\rho_k \\geq (\\sigma_k^2 - \\sigma_{k-1}^2) / \\sigma_k$. Note that it shows $c_0$ should be taken as large as possible and then the previous bound on $c_0$ has to be taken as an equality. Finally, $\\rho_k$ is upper bounded, so is $(\\sigma_k^2 - \\sigma_{k-1}^2) / \\sigma_k$, showing that $\\sigma$ can only increase up to a certain speed, similar to the classical parameters of NAG algorithm. This clearly explains the fact that $t_k$ (as well as $\\sigma_k$ and $1/\\tau_k$) grows as $k$ and $T_k$ as $k^2$, giving eq.14. Remark 3 explains why we obtain at least a $1/k$ guarantee, but it not more complicated to see that we can actually accelerate. In my view, the algorithm, the thm, and the corollary have all been overcomplicated with many notations and assumptions and a lack of explanation. and intuition that would have made all this straightforward to understand.\n\n\nIn summary, I would say that the method is sound as soon as we have some $\\mu_{min}$ (main assumption of this paper) and some $r$ (eq.4) coming from the assumption that no minimizer of $f$ can be a solution to our problem. Note we also need to have access to such a $r$, which does not seem trivial in general.\n\n\nOverall, this paper introduces a new idea and new result which is that we can accelerate constraint optimization as soon as the constraint sets are strongly convex. This result is very interesting to the community, but the paper’s writing is really bad as it is and needs a huge improvement to be publishable in my opinion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your feedback and are grateful for the thorough reading and valuable suggestions for our paper. Due to space limits, we respond to the main technical questions.\n\n**l87:** We establish two upper bounds for two error measures. Since new point $y^+$ is needed for optimality and feasibility gap (see Cor1), while this is not needed for $\\\\|x_k - x^*\\\\| \\le \\varepsilon$. We clarify that our algorithms do not require the $\\\\|x-x^*\\\\|$ and $\\\\|y-y^*\\\\|$. Instead, it relies on $D_X$ and $D_Y$ to replace $\\beta$ in Prop4 for estimating $\\mu_{min}$.\n\n**l125:** We plan to revise KKT condition as follows: We say $x^*$ satisfies the KKT condition of (1) if there exists a Lagrangian multiplier vector $y^* \\in \\mathbb{R}_{+}^{m}$ such that $0\\in \\partial _{x} L(x^*,y^*)$, $G(x^*)\\le 0$ and $\\langle y^*,G(x^*) \\rangle = 0$.\n\n**Is Assu 2 easily verifiable?:** We agree that the term may not be entirely appropriate. Assu 2 would require finding all minimizers of f and check, and solving this issue would be challenging. This indeed motivates the l1 loss, where Assu 2 can be verified.\n\n**Can an algorithm cover both cases?** While it is challenging in general, we feel verifying Assu 2 is possible when projection on the level set of $f(x)$ is easy. First, we compute an $\\epsilon$-solution $\\hat{x}$ of $\\min f(x)$ efficiently, (e.g. in $O(1/\\sqrt{\\epsilon})$ using Nesterov's acceleration). We switch the objective and constraint and consider the following problem: $\\tau^*=\\min _x \\max _i g_i(x), \\text{ s.t. } f(x)\\le f(\\hat{x}).$ When the projection is easy to solve, we can find an approximate solution ($\\bar{x}$) and value $\\bar{\\tau}$ satisfying $\\bar{\\tau}\\le \\tau^*+\\epsilon$ in $O(1/\\sqrt{\\epsilon})$ by using accelerated gradient method and smoothing technique. If $\\bar{\\tau}>\\epsilon$, then we have $\\tau^*>0$ and hence Assu 2 holds. Otherwise, we have $\\tau^*\\le \\bar{\\tau}\\le \\epsilon$, then the solution $\\bar{x}$ naturally becomes an $\\epsilon$-solution of the original problem. We hope this can partially resolve the reviewer's concern. \n\n**closedness** Upon reviewing the literature, we found in [1], Chapter 23, (2nd paragraph, page 215), the statement: \"Obviously $\\partial f(x)$ is a closed convex set, since ...\" However, this is not a formal theorem. This book is one of the earlier sources on \"The closedness of the subdifferential set,\" which we intend to cite.\n\n**L141 derive:** We apologize the statement here is unclear. As you say, it is impossible to determine r for general function. We aim to modify it as follows. In view of Assu 2, Prop 2, we know that $dist(\\partial f(x^*))>0$. Furthermore, we make the following assumption: Throughout the paper, a lower bound $r\\in (0,dist(\\partial f(x^*))]$ is known. We give some important examples for which the lower bound r can be estimated.\n\n**More motivations:** Previously, due to space limitations, we omitted much of the preparatory material. In the revision, we will detail the motivation. Regarding Prop 3, we will add introductory statements: \"When considering the Lipschitz continuity of functions in $\\mathbb{R}^n$, even quadratic functions are not Lipschitz continuous. However, the Lipschitz continuity of $g_i(x)$ is crucial for algorithm convergence. Therefore, we define the bounded feasible region in the following proposition.\" We hope this will improve the understanding of Prop 3.\n\n**$\\zeta$ Prop 3:** We deeply appreciate your rigorous analysis of the inequalities: $\\\\|x^*-x_i^*\\\\|^2\\le \\frac{-2g_i(x_i^*)}{\\mu_i}$ and $\\\\|\\tilde{x}-x_i^*\\\\|^2 < \\frac{-2g_i(x_i^*)}{\\mu_i}$. We will revise the definition of $\\mathcal{X}$. \n\n**Motivation for (7):** $L_{XY}$ is necessary for step size setting in algorithms. We will add the following statement for readability: \"The Lipschitz smoothness of the Lagrangian function with respect to the primal variable x is crucial for the convergence of algorithms. Given that the dual variable y is bounded from above, and considering the smoothness of the constraint functions, we can derive the smoothness of the Lagrangian function. Combining (5) and ...\".\n\n**All problems in Alg1, Thm1 and Cor1.** We apologize for any lack of conciseness and readability. Our goal was to show the flexibility of algorithm parameters. Thm1 shows that the algorithm can converge if the parameters meet certain conditions, and Cor1 specifies these parameters. Introducing many auxiliary sequences reduced readability and did not aid calculations. You suggested that our pseudocode should clearly present the calculation methods for parameters. Using only one sequence, $\\sigma_k$, and setting $\\delta$ to 1 improves readability. Your understanding of our algorithm is commendable. However, to simplify subsequent proofs, we will keep the two step size sequences, $\\tau_k$ and $\\sigma_k$. We have included the pseudocode of our APDPro in the rebuttal PDF. As you suggested, we revise equation (12) to  $\\tau_k(\\tau_{k+1}^{-1}-\\rho_{k+1})\\le\\sigma_k/\\sigma_{k+1}, L_{XY}+L_G^2\\sigma_k\\le1/\\tau_k$ and the precondition in Cor1 to $1/\\tau_0\\ge L_{XY}+L_G^2\\sigma_0$. Furthermore, after eliminating the auxiliary sequence $\\gamma_k$, Lemma 3 requires corresponding modifications. Due to the space limitation, please review our comments for detailed explanations of our revisions.\n\n**2 loop vs single loop:** The reviewer raises an interesting question of whether a method, even one using 2 loops, has achieved or can potentially reach this accelerated rate. While we have not observed any methods aiming to leverage the strong convexity of constraint functions, we believe that further improvement is quite promising based on our technique. Typically, our technique can benefit a wide range of algorithms using Lagrangian multipliers, such as IALM ([32] in paper), which involve 1st-order methods to solve their subproblems.\n\n[1] R Tyrrell Rockafellar. Convex analysis, volume 18. Princeton university press, 1970.", "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": "", "extra_scores": {}}, {"review_id": "vsf0jZgV8z", "reviewer": "Reviewer_rJ7a", "summary": "This paper introduces accelerated primal-dual algorithms for minimizing a convex function subject to strongly convex constraints. Currently, the best complextiy bound for these problems is $\\mathcal{O}(1/\\epsilon)$, even when the constraints are strongly convex. However, this work develops a technique to progressively estimate the strong convexity of the Lagrangian function, and thereby establishes an improved, and optimal, complexity bound of $\\mathcal{O}(1/\\sqrt{\\epsilon})$. Further, a restarted version of the methods can identify the sparsity pattern of the optimal solution within a finite number of steps.", "questions": "1. In Definition 1, does the last condition (orthogonality of the vectors) imply complementarity? Does one not need $\\mathbf{y^*}_i g_i(\\mathbf{x^*}) = 0$ for all $i$?\n2. On line 140, the word \"closeness\" is used. Do you mean \"closedness\"?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper was well written and the problem is of interest to the wider research community.\nThe paper establishes convergence of their method, and exploits the strong convexity of the constraint functions to obtain an improved complexity of $\\mathcal{O}(1/\\sqrt{\\epsilon})$.\nThat the restarted version of the algorithm can identify the sparsity pattern of the optimal solution in a finite number of steps, which is independently interesting.", "weaknesses": "The claim of \"optimal rate\" does assume that $\\tilde \\rho_K$ is small. If it is order epsilon, then the `usual' complexity bound holds (the authors are upfront about this as it is noted in Remark 2). This does weaken the \"optimal\" claim somewhat.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the careful reading and valuable feedback! We hope that the following can resolve your concerns and questions.\nFirstly, you are correct that we can not accelerate our algorithm if $\\tilde{\\rho} _{K}$  is at order $\\mathcal{O}(\\epsilon)$. Indeed, when $\\tilde{\\rho} _{K}$ is of the order of $\\mathcal{O}(\\epsilon)$, as we mentioned in Remark 2, our algorithm reverts to handling convex objective functions and convex constraints. In this case, our algorithm cannot fully utilize the strong convexity of the constraints and can obtain rate $\\mathcal{O}(1/\\varepsilon)$.\nSecondly, we are sorry for the confusing notations in Definition 1. The last condition indeed implies complementarity. Following Reviewer 8Vg8's suggestion, we are preparing to modify Definition 1 equivalently as follows: **Definition 1(KKT condition).** We say that $x^*$ satisfies the KKT condition of (1) if there exists a Lagrangian multiplier vector $y^{*} \\in \\mathbb{R} _+ ^m$ such that \n\n$$0 \\in \\partial _{x} L(x^*,y^*),G(x^*) \\leq 0,\\langle \\mathbf{y} ^*,G(\\mathbf{x} ^*) \\rangle = 0.$$\n\nThese conditions can actually imply $\\\\mathbf{y}^*_{(i)} g _i(\\mathbf{x}^*)=0, \\forall i$. We completely agree with your observation.\nFinally, you are right, it should be \"closedness\".", "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": "", "extra_scores": {}}, {"review_id": "NSjJdVN72I", "reviewer": "Reviewer_ecU7", "summary": "This method proposes new acceleration methods to solve the convex optimization problem with convex constraints. To do this, the authors propose to iteratively improve the lower bounds of the strong convexity parameter of the associated Lagrangian. In turn, this lower bound is used to create cutting planes for the domain of the dual variables. By using this new technique, the authors is able to improve the running time complexity of the base method APD from $O(1/k)$ to $O(1/k^2)$, where $k$ is the number of iterations. The authors verify the claim of running time improve empirically through several datasets.", "questions": "1. For the experimental section, you only show optimality gap vs number of iterations. Could you also report optimality gap vs wall-clock running time? You can report these results in table format during rebuttal.\n\n2. For the baseline method APD, is restart also applied? For fair comparison, I think you should compare rAPDPro with APD + restart.\n\n3. The authors obtain the optimal solutions via MOSEK. Could you report the optimality gap of the MOSEK solver together with what are shown in Figure 1?\n\n4. For Figure 3 and Figure 4 in the appendix, can you explain why the baselines (mirror-P and APD) fail and perform so poorly on the rightmost plot?", "limitations": "The authors have already pointed out the limitations in this submission:\n\n1. The proposed method requires knowing an upper bound on $\\lVert \\mathbf{y}^* \\rVert$.\n\n2. If the evaluation of the proximal operator of $f$ is inexpensive, this method can be rightly applied; if not, this method will incur additional computational cost.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The core techniques (iteratively improve the lower bound of the strong convexity parameter and use it to add cutting planes to the domain of the dual variables) seem to be novel. The improvement on computational complexity is nontrivial and matches the lower bound for this class.\n\nThe writing is clear in terms of highlighting the high-level ideas and emphasizing which part is the authors' contribution.\n\nThe code is also available as part of the supplementary materials.", "weaknesses": "1. For Figure 2 on the active-set identification experiment, I am not seeing a big difference between APD (baseline) and rAPDPro (proposed method). So I am guessing the core empirical contribution is on improving the curve of optimality gap vs number of iterations. It would be nice to show the curve of optimality gap vs wall-clock running time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your comments. We provide the following clarifications to address your concerns. We include Table1 summarizing the time required for the optimal gap and infeasibility to decrease to $10^{-3}$. Additionally, as per your suggestion, we will compare our results with APD+restart. As shown in the table, comparing from the perspective of time, we observe that rAPDPro and msAPD demonstrate faster convergence speeds across different datasets. Regarding your inquiry about the relationship between MOSEK iterations and the optimality gap, since MOSEK employs a second-order algorithm, its computational cost per iteration differs significantly from the first-order method. Therefore, comparing them to the same figure may not be fair. The poor performance of Mirror-Prox and APD in Figure 3 and 4 is primarily due to their theoretical convergence being based on the average sequence. If the initial point is bad, it can adversely affect convergence and active set identification. Finally, we agree with your observations regarding the limitations of our paper, which we have also mentioned in the paper, and these will be the focus of our future direction.\n\n\nTable1: Time summary when max{optimality gap, feasibility gap} ≤ $10^{−3}$(* means that upon\ncompletion of all iterations, the algorithm still fails to meet the criteria for both error measures.)\n| Dataset     | APD                 | APD+restart       | rAPDPro          | Mirror-Prox        | msAPD            |\n|-------------|---------------------|-------------------|------------------|--------------------|------------------|\n| bio-CE-HT   | 187.15 (0.86)*      | 115.95 (1.04)     | 136.92 (0.92)    | 370.50 (1.80)*     | **77.21** (0.67) |\n| bio-CE-LC   | 2.58 (0.16)*        | 0.65 (0.01)       | **0.44** (0.01)  | 4.74 (0.33)*       | 0.65 (0.03)      |\n| econ-beaflw | 72.28 (0.59)*       | 87.12 (0.43)*     | **18.42** (0.44) | 116.13 (1.15)*     | 66.70 (0.76)     |\n| DD242       | 43.29 (1.20)*       | 10.27 (0.39)      | **6.30** (0.08)  | 79.16 (0.60)*      | 10.33 (0.62)     |\n| DD68        | 36.55 (0.42)*       | 19.07 (0.66)      | 22.35 (0.75)     | 67.73 (1.39)*      | **15.69** (0.37) |\n| peking-1    | 122.37 (2.99)*      | 11.55 (0.69)      | **4.86** (0.09)  | 243.45 (7.20)*     | 11.24 (0.15)     |", "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": "", "extra_scores": {}}, {"review_id": "gZVUlZVdKC", "reviewer": "Reviewer_h3VH", "summary": "The authors introduce faster accelerated primal-dual algorithms for minimizing a convex function subject to strongly convex function constraints.", "questions": "See Weaknesses", "limitations": "None", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The authors address the theoretical questions about strongly convex-constrained optimization and the application of sparse optimization.\n\n2. The authors present a new accelerated primal-dual algorithm with progressive strong convexity estimation (APDPro) for solving the problem (1).\n\n3. The authors present a new restart algorithm (rAPDPro) which calls APDPro repeatedly with the input parameters properly changing over time.", "weaknesses": "1. What is the 2-norm (see line 116)? what is the meaning of $\\bot$?\n\n2. The conditions of Theorem 1 are too strict and limited, which hinders the application of APDPro. There are also similar issues with the corollary 1.\n\n3. As illustrated by formulation (2), when $f$ is convex and $g_i$ is strongly convex, $L(\\cdot, y)$ is strongly convex and the convergence rate of gradient descent is linear, which is a well-known conclusion in optimization. However, the convergence rate of your method is sublinear [1, 2]. \n\n4. This paper lacks related work. There are several studies exploring optimization with the objective of minimizing a convex function subject to strongly convex function constraints.\n\n5. The improvement in the convergence rate comes at the cost of increased computational effort per step.\n\n6. Convex optimization with strongly convex function constraints has been explored by [1, 2], but the authors don’t cite these references. Moreover, Nesterov's Accelerated Gradient Method [3] can also achieve a complexity of $1/\\sqrt{\\epsilon}$. The authors did not improve the convergence rate compared to previous works.\n\n\n[1] Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Springer 1999, ISBN 978-0-387-98793-4, pp. 1-634\n\n[2] Yurii E. Nesterov: Introductory Lectures on Convex Optimization - A Basic Course. Applied Optimization 87, Springer 2004, ISBN 978-1-4613-4691-3, pp. 1-236\n\n[3] A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights. J. Mach. Learn. Res. 17: 153:1-153:43 (2016)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the careful reading and valuable suggestions!\n\n**Q1:What is $l _2$ norm and $\\perp$?** We apologize for any confusion caused by the lack of clear definitions. $l _2$ norm for a vector x is defined as $(\\sum _{i=1}^{n}|x _{(i)}|^2)^{1/2}$, where $x _{(i)}$ is the $i$-th element of x. The definition of the $l _2$ norm in the paper is consistent with that of the $l _q$ norm when $q=2$. \"$0\\le y^*\\perp -G(x^*)\\ge 0$\" means $y _{(i)}^*\\ge 0,g _i(x^*)\\le 0$ and $\\sum _{i=1}^{m}y _{(i)}^* g _i(x^*) = 0$.\n\n**Q2:The conditions of Thm1 and Cor1 are too limited.** We slightly disagree with your comments. In Thm 1, we demonstrate that the algorithm can converge if certain parameter relationships are satisfied. In Cor 1, we provide a specific parameter setting and verify that these settings satisfy the relationships in Thm 1. For example, in the parameter settings outlined in Cor 1, all parameter relationships are derived recursively. The key requirement is that the initial step size, $\\tau _0$ and $\\sigma _0$, satisfy $\\tau _0^{-1}\\ge L _{XY}+L _G^2\\sigma _0/\\delta$. Given specified $\\delta$, like $\\delta=1$, this relationship can be satisfied if $\\tau _0$ is chosen to be sufficiently small. We apologize that our original writing may have given the impression that the parameter settings are overly complex. Following the suggestions of Reviewer 8Vg8, we will rewrite these conditions to enhance the readability.\n\n**Q3:$L(\\cdot,y)$ is strongly convex and the convergence rate is linear. However, your result is sublinear.**\nWe respectfully disagree that the sublinear convergence rate is bad. When y is strictly greater than 0, $L(\\cdot,y)$ is strongly convex w.r.t. x. In this context, if y is fixed, the problem becomes an unconstrained strongly convex optimization. The best convergence rate is indeed linear. However, when a constrained optimization problem is expressed in the form of a Lagrangian function, it essentially becomes a minimax problem. Under certain constraint qualifications, like Slater's condition, the feasible region for the dual variable is bounded. Consequently, the lower bound on the convergence rate for first-order algorithms is sublinear [5]. Furthermore, we agree that the algorithm proposed in [2, Section 2.3.5] has achieved a linear convergence rate, which we guess is the algorithm referred to by the reviewer. Note that this algorithm requires both f and g to be strongly convex while ours only need strong convexity of g. More seriously, in each iteration, the algorithm needs to solve a much more difficult quadratic program with quadratic inequality constraints.\n$$\nf(x)+\\langle f'(\\bar{x}),x-\\bar{x} \\rangle + \\frac{\\mu}{2}\\\\|x-\\bar{x}\\\\|^2 s.t. \\ g _i(\\bar{x})+\\langle g _i'(\\bar{x}),x-\\bar{x} \\rangle + \\frac{\\mu}{2}\\\\|x-\\bar{x}\\\\|^2 \\le 0.\n$$\nThe complexity is particularly emphasized at the end of Section 3.5, on page 110 in [2]. Hence, comparing with this algorithm in terms of iteration complexity doesn't seem fair. \n\n**Q4:lacks related work.** We acknowledge that we had previously overlooked relevant literature on achieving linear convergence using a stronger oracle. Our literature review primarily focused on comparisons with first-order algorithms. We observed that most algorithms, such as [4] and [6], assume the objective function to be strongly convex. For the case where the objective function is convex and the constraints are strongly convex, a class of Frank-Wolfe algorithms has been studied. Due to space limitations, we have included this discussion in Appendix B.\n\n**Q5: The improvement comes at the cost of increased computational effort per step.**\nWe agree with the reviewer on the additional computational efforts, however, those additional costs are still manageable.\n- The \"improve procedure\" to estimate the strong convexity computes the norm of the Jacobian matrix, which can be efficiently solved using the Power method or Lanczos method. Additionally, we can significantly reduce computation costs by using a warm start from previous iterates.\n- The dual update of APDPro involves a linear inequality constraint and nonnegative constraints.  Note that this subproblem is easy to solve in our sparsity-constrained problem, one can obtain a closed-form solution. In general, one can enumerate the active constraint and obtain the closed-form solution in each case. This is highly efficient and can be done in parallel when the constraint number is small (say, $\\le 5$, refer to Appendix in [7]). Due to the space limit, we don’t plan to dive further into the details, but if the reviewer is interested, we are glad to explain further. To address more general cases, we developed the msAPD, which leverages the lower bound of the strong convexity to check the stopping condition for the inner loop, thus avoiding complicated dual updates. We believe the msAPD mitigates this issue effectively.\n\n**Q6: Lack references[2],[1] and NAG can also achieve $1/\\sqrt{\\epsilon}$. The authors did not improve rate**\nWe respectfully disagree with your comments that our results are not novel. The previous result [3] is focused on unconstrained optimization. We think the comparison is unfair. Regarding the absence of citations to relevant literature, please see our responses to Q3 and Q4.\n\n[4] Yangyang Xu. Iteration complexity of inexact augmented lagrangian methods for constrained convex pro-\ngramming. Mathematical Programming, 2021.\n\n[5] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave\nbilinear saddle-point problems. Mathematical Programming, 2021.\n\n[6]Erfan Yazdandoost Hamedani and Necdet Serhat Aybat. A primal-dual algorithm with line search for\ngeneral convex-concave saddle point problems. SIAM Journal on Optimization, 2021.\n\n[7]Yunmei Chen, Guanghui Lan, Yuyuan Ouyang, and Wei Zhang. Fast bundle-level methods for unconstrained\nand ball-constrained convex optimization. Computational Optimization and Applications, 2019.", "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": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank the PC, SAC, AC, and all the reviewers, especially the four reviewers. Their feedback has been invaluable, and we will carefully revise our manuscript to meet their standards. We have responded to each comment in the author rebuttal, aiming to resolve their concerns. Due to space limitations and the inability to attach figures in the author rebuttal, we will provide additional explanations for two reviewers' comments.

Reviewer 8Vg8 provided many suggestions on our writing. We have revised the manuscript according to the suggestions to enhance readability. Based on the feedback, the latest version of APDPro in the PDF clearly outlines the specific parameter settings.

Reviewer ecU7 requested a comparison between our algorithms and APD+restart, particularly regarding wall-clock time. Using the condition that both the optimality gap and feasibility gap are less than $10 ^{-3}$ as the stopping criterion, we recorded the required wall-clock time. Our algorithms (rAPDPro and msAPD) are generally faster and more stable compared to other algorithms, including APD+restart.

Meta-review: The authors study the problem of convex optimization with strongly convex constraints. They present new primal-dual first-order methods that improve the complexity bound from $O(1/\epsilon)$ to $O(1/\sqrt{\epsilon})$. The reviewers are in agreement that the paper would be of interest to the community and should therefore be accepted, though please be sure to incorporate the suggested feedback to improve the presentation of the paper for the camera-ready version.
Decision: Accept (poster)