Continuous-time Analysis of Anchor Acceleration
Authors: Jaewook J. Suh
Jisun Park
Ernest K. Ryu
Venue: NeurIPS 2023 poster (2023)
Keywords: acceleration
convex optimization
continuous-time analysis
monotone operator
monotone inclusion
minimax optimization
fixed-point problem
anchor acceleration
TL;DR: We present continuous-time analyses of anchor acceleration for minimax optimization and monotone inclusion problems.

Abstract: Recently, the anchor acceleration, an acceleration mechanism distinct from Nesterov's, has been discovered for minimax optimization and fixed-point problems, but its mechanism is not understood well, much less so than Nesterov acceleration. In this work, we analyze continuous-time models of anchor acceleration. We provide tight, unified analyses for characterizing the convergence rate as a function of the anchor coefficient $\beta(t)$, thereby providing insight into the anchor acceleration mechanism and its accelerated $\mathcal{O}(1/k^2)$-convergence rate. Finally, we present an adaptive method inspired by the continuous-time analyses and establish its effectiveness through theoretical analyses and experiments.

Continuous-time Analysis of Anchor Acceleration
Jaewook J. Suh Seoul National University j jacksuhkr@snu. ac.kr .r
Jisun Park Seoul National University 0olleenp0515@sm ac.
Ernest K. Ryu Seoul National University ernestryušsnu .c.
Abstract
Recently, the anchor accelcration, an acceleration mechanism distinct from Nes- terov's, has been discovered for minimax optimization and fixed-point problems, but its mechanism not understood well, much less so than Nesterov acceler- ation. In this work, analyze continuous-time models of anchor acceleration. We provide tight, unified analyses for characterizing the convergence rate as a function of the anchor coefficient B(t), thereby providing insight into the anchor acceleration mechanism and its accelerated O connvergeee -ooneoooee rate. Finally, we present adaptive method inspired by the cattinuuustimee analyses and establish its effectiveness through theoretical analyses and experiments.
Introduction
Nesterov acceleration [51] is foundational to first-order optimization theory, but the mechanism and its convergence proof are not transparent. One approach to better understand the mechanism is continuous-time analysis: derive an ODE model of the discrete-time algorithm analyze continuous- time dynamics [65, 66]. This approach provides insight into the accelerated dynamics and has led to a series of follow-up work [71, 62, 29].
Recently, a new acceleration mechanism, distinct from Nesterov's, has been discovered. This anchor acceleration for minimax optimization and fixed-point problems [35, 75, 54] has been an intense subject of study, but its mechanism is understood much less than Nesterov acceleration. The various analytic techniques developed to understand Nesterov acceleration, including continuous-time analyses, have only been applied in very limited manner [59].
Contribution. In this work, we present continuous- time analyses of anchor acceleration. The continuous tiemuouus-immeeaee model is the differential inclusion
X E A(() (X - -X))
with initial condition X(0) X, dom A, maximal monotone operator A, and scalar-valued
function (t)). The case 3(t) corresponds to the prior anchor-accelerated methods APPM [35],
EAG [75], and FEG [42].
first establish that the differential inclusion is well-posed, despite the anchor coefficient (()) blowing up at ( 0. We then provide tight, unified analyses for characterizing the convergence rate as a function of the anchor coefficient B(1). This is the first formal and rigorous treatment this anchored dynamics, and provides insight into the anchor acceleration mechanism and its accelerated rate. Finally, we present an adaptive method inspired by the continuous-tin analyses and establish its effectiveness through theoretical analyses and experiments.
1.1 Preliminaries and notation
We provide the organization for prior works in Appendix Here, we review standard definitions and set the notation.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Monotone and set-valued operators. We follow the standard definitions of Bauschke and Com- bettes [15], Ryu and Yin [58]. For the underlying space, consider R with standard inner product (1.) and norm ||-I1- Define domain of A as dom A {z E IR" Ax o 0}. We say A is operator on IR" and write A: R = R maps a point in IR a subset of R We say A: Rd I Rd monotone if
(Ar Ay, x y) 2 0,
Va,y E R"
where the notation means that (u - v, I y) 2 0 for all u E Ar and v E Ay. For μ E (0), say A: IR = IR" is p-strongly monotone if
(Ar Ay.r v) 1a1 ul?:
Vx, ER..
Write Gra = {(x, u) u E Ax) for the graph of An operator A is maximally monotone there is no other monotone B such that Gra A C Gra B properly, and is maximally p-strongly monotone there no other p-strongly monotone B such that Gra A C Gra properly.
For L E (0, o.). single-valued operator T: R + R is L-Lipschitz if
TT Tyl I L| vll,
Vor, RR
Write JA = (I (I+A) A) for the resolvent of A, while I: R - R is the identity operator. When A maximally monotone, is well known that JA is single-valued with dom JA 1R
We say x. IR" is zero A if O E Ar.. We say y, is a fixed-point of Ty, = yx. Write Zer A for the set of all zeros of A and Fix T for the set of all fixed-points of T.
Monotonicity with continuous curves. We say an operator is differentiable if it single-valued, continuous, and differentiable as function. If differentiable operator A is monotone and X: oo) n is a differentiable curve, then taking limit h 0 of
(A(X ( - A(X()), X(I+ h) - X()) 20
2
leads to
A(X()), X() 20. di
(I)
Similarly if A is furthermore p-strongly monotone, then
A(X()), 2 2 dt
(2)
2 Derivation of differential inclusion model of anchor acceleration
2.1 Anchor ODE
Suppose A: Rd = RR is maximal monotone operator and B (0, oo) 00) is twice
differentiable function. Consider differential inclusion
x() -(((()) (X) Xo)
with initial condition X() Xo E dom (A). We refer to this as the anchor ODE. We say
X: [0, oo) R is solution, if it is absolutely continuous and satisfies (3) for E (0, oo) almost everywhere.
Denote S as the subset of [0, oc) on which X satisfies the differential inclusion. Define (x(0)=-X00
(()((((( - -Xu)
for & E S. Since A(X(t) E A(X()) for t S, we say À is a selection of A for S. If [t(( bounded on all bounded subsets of S, then we can extend A to [0, oo) while retaining certain favorable properties. We discuss the technical details of this extension in Appendix E. The statements of Section are stated with this extension.
Sttictly speaking, this is differential inclusion, not a differential equation, but we nevertheless refer to it as ODE.

---

2.2 Derivation from discrete methods
We now show that the following instance of the anchor ODE
x(t)= - 1 (x((t) - Xo),
(4)
where (() = Xo is the initial condition and A: [R" - IR" is continuous operator, is continuous- time model of APPM [35], EAG [75], and FEG [42], which are accelerated methods for monotone inclusion and minimax problems.
Consider APPM with operator AA
x JAAY R-1
k
k (2x
k y
(5)
with initial condition 3d = x. Assume / > O and A: R" + R is a continuous monotone operator. Using y*-1 x* hA obtained from the first line, substituting y and y²-1 in the second line we get,
k k +
x+ hAr
(x - -Aa" + + x.
Then reorganizing and dividing both sides by h, we have
x k+1 x²
Ao
Ax
1
(at-
h
k+
1(h + +1
Identifying 20 Xo. 2hk and x (t),, we have
1+ and so
F+1
batt
eX(1)+000 -0)) A(()))()))( 1+ (h) (X(1) -Xo)
-
Taking limit + 0 and dividing both sides by 2, we get the anchor ODE (4). The correspondence with EAG and FEG provided in Appendix D.4.
The following theorem establishes rigorous correspondence between APPM and the anchor ODE for general maximal monotone operators.
Theorem 2.1. Let A be (possibly set-valued) maximal monotone operator and assume ZerA + 0. Let x be the sequence generated by APPM (5) and X be the solution of the differential inclusion (3) with 3(1) 7. For all fixed T 0,
lim h-+0
max |1a* x(2kh))l
ogk 22
We provide the proof in Appendix D.2.
2.3 Existence of the solution for B())
2F
To get further insight into the anchor acceleration, we generalize anchor coefficient to 8(t) 2 for P.7 > 0. We first establish the uniqueness and existence of the solution.
Theorem 2.2. Consider (3) with $(t) 3. i.e.
x(1) E A(X(()) 7 (x(() Xo).
(6)
for p. > 0. Then solution of (6) uniquely exists.
We provide the proof in Appendix B.
3

---

slow down 2.4 Additional properties of anchor ODE
We state a regularity lemma of the differential inclusion (3), which we believe may be of independent interest. In particular, we use this result several times throughout various proofs.
Lemma 2.3. Let X() and (-) are solutions of the differential inclusion (3) respectively with initial values and anchors Xo and Yo. Then for all E [0, 0o),
( Y(IIl s I Yoll.
We provide the proof in Appendix B.1.
Boundedness of trajectories is immediate corollary of Lemma 2.3. Specifically, suppose (-) the solution of differential inclusion (3) with initial value Xp- Then for all X, E ZerA and t e [0, oo).
(t) - x.Il ||xo -x.1-
This follows from setting Y = X, in Lemma 2.3.
3 Convergence analysis
We now analyze the convergence rate of (t)()) for the anchor ODE (3) with B(t) - and 7, p.p > 0. The results are organized Table
== 1, p= 7 <<1
Case
p<l
p>1
|A((()))
O
(
Table 1: Convergence rates of Theorem 3.1.
Let ,3 be the anchor coefficient function of (3). Define C: [0, x)) - as C(I) = edc 8(s)ds for some v E [0, oo]. Note that = CB and C is unique up to scalar multiple. We call O (B(t) the vanishing the contracting speed, and we describe their trade-off the following. c(t)
speed and
Loosely speaking, the contracting speed describes how fast the anchor term alone contracts the dynamical system. Consider (1) = - (X) (f) a) for E R", a system only with the anchor. Then, X (t) = C(O)
(X( a) + a is the solution, so the flow contracts towards the anchor a with rate C(t)- Intuitively speaking, this contracting behavior leads to stability and convergence. On the other hand, the anchor must eventually vanish, since our goal is to converge to an element in ZerA, not the anchor. Thus the vanishing speed must be fast enough the convergence of the flow to ZerA.
c(t)
p p- 3,y=1
p= 1--1
p=
This observation is captured in Figure 1. Consider mono- tone linear operator A (-1)) d) on R² and (() IF with 7 1 and p 0. Note if there is anchor, the ODE reduces to X -(X) which do not converge [31, Chapter 8.2]. Figure shows that with p > 1, the anchor vanished too early before the flow is contracted enough to result in converging flow. With p < 1, the flow does converge but the anchor vanished too late, slowing down the convergence. With p = 1, the convergence is fastest.
7
Figure 1: Flows of the solution of (6)
with A = (.) = 1, Xo = (1,0) and various p. Flow is from f 0 to
f == 100. The marker plotted every 0.8 units of time until 9.6. Note the last marker of the flow for p = is farther from the optimal point than that of the flow for p = 1.
The following theorem formalizes this insight and produces the results of Table 1.

---

Theorem 3.1. Suppose A is maximal monotone operator with ZerA & 0. Consider (3) with 8(t) T. Let (t) be the selection of (() as in Section 2.1. Then,
| = 0 ( 1 ((()p) + + (8(1)) o (štt))
Note that
8 C(I)
p p=1 p
e
p 1.
We expect the convergence rate of Theorem 3.1 to be optimized when the terms are balanced. When ((t) = +
1
1 p - -
C(1)2
and all three terms are balanced. Indeed, the choice 3(() = & corresponds to the optimal discrete-time choice k+12 of APPM or other accelerated methods.
3.1 Proof outline of Theorem 3.1
The proof of Theorem 3.1 follows from Lemma 3.4, which we will introduce later in this section. To derive Lemma 3.4, we introduce a conservation law.
Proposition 3.2. Suppose À is Lipschitz continuous and monotone. For la > O, define E: (0, oc) -
R as
C(t)
2 [|A(X(()))*
+ 23((t) (A((())),X( - -Xo) + (B(1)+ + B(t)) [x Xull?
E
[.e ds 2
d C(s)) [|X(s) - -oll? ds + ("' [((()// / d A(X(s)), x(s) ds.
ds
to
Then E is constant function.
The proof of Proposition 3.2 uses dilated coordinate W(I) ((I)(X(I) Xa) to derive its conser- vation law in the style of Suh et al. [67]. We provide the details in Appendix E.2.
Recall from (1) that (x)(()))) (())
0, the integrand of the last term of E is nonnegative.
This motivates us to define
C(s) ( d A(())))).x())) ds ds
v(t) - 10
as our Lyapunov function.
Corollary 3.3. Let A be maximal monotone and B(t) = 2 with p > >0, 0,,7000 Let A(X(t)) be the to
selection of (t)(t) as in Section 2.1. For to 2 0, define V 10, 00) + R as
C(t) ( (IA(XX())1I + 23(1) (A(X(I)), Xo) (3(1) + B(t)) ||X(1) -Xoll
((t) 2
d ((s))B(s)
J ds 2
IIX(s) Xool2de ds.
for 1. > 0 and V(0) = lim V(I). Then V(I) S V(0) holds for 1 2 0.
technical detail is that all terms involving d {A(X(s)) have been excluded in the definition of V and this is what allows A to not be Lipschitz continuous. We provide the details in Appendix E.3. Lemma 3.4. Consider the setup of Corollary 3.3. Assume ZerA + 0. Then for t and X. E Zer
de
| S 43(1)2 Ixo0 - x.11 + 4V(0) 2 (S(E) + B(t)) ||x(t)) Xoll
C(t)²
2 ('' d (C()))((s) (Ix(s) Xxol ds.
C(t) ds
5

---

Proof outline of Lemma 3.4. Define
(tt) |[A((())) + 23()) (A(X(t)). -Xo).
Then, from monotonicity of A and Young's inequality,
(t)) 2 |((x()))| + 23(() (A(X(t)), X, X, -xx] XXo)
2 || - (1
+11((t) (X, xooil3)
= 2 ||((X()))2 - 28(1)² | - x.11 -x11
(8)
By Corollary 3.3, (V) 20())
C(i) + (t)) 2 (t) fort > 0. Applying (8) and organizing, get
C(t)a
the desired result. The details are provided in Appendix E.4.
Proof outline of Theorem 3.1. It remains show that last integral term of Lemma 3.4 is O O (B(0))) + (B(t)) The details are provided in Appendix E.5.
L
Before we end this section, observe how our analysis simplifies in the special case 3(() 1 In this case,
((t) = 12 - + Xo),
and this corresponds the Lyapunov function of [59, Section 4] for the case 7 As V(0) the conclusion of Lemma 3.4 becomes
A(X
4 11x x
p
which to the best rate in Table 1.
3.2 Point convergence
APPM is an instance of the Halpern method [54, Lemma 3.1], which iterates converge to the element
in ZerA closest to Xo [34. 73]. The anchor ODE also exhibits this behavior.
Theorem 3.5, Let A be a maximal monotone operator with Zer & 0 and X be the solution of (3). If l/m (X) = 0 and lim 1/C(1) = 0, then, as - Do,
(() argmin ||
Xoll
=EZeTA
We provide the proof in Appendix E.6.
4 Tightness of analysis
In this section, we show that the convergence rates of Table are actually tight by considering the dynamics under the explicit example A = (-1 Throughout this section, we denote A as A when when the operator linear.
4.1 Explicit solution for linear A
Lemma 4.1. Let A: R - R be a linear operator and let 3(() 7. The series
(-LA)" x(1) E ((+
2
T(7 1)Xo:
where I' denotes the gamma function, is the solution for (3) with A A.

---

Note that when 7 = O, this is the series definition of the matrix exponential and X(t) = =e =e- The solution also has an integral form, which extends general ((t).
Lemma 4.2. Suppose A: R Rd is monotone linear operator. Then
X(t) c-tA (L ( Xo
(9)
C(t)
the solution for (3) with A = A.
See Appendix F.I.1 and Appendix F. F.1.2 for details.
4.2 The rates in Table 1 are tight First, consider p > 1 for (t)
p
Theorem 4.3. Suppose lim4-400 there exists an operator A such that
1
# O, iee, suppose B(t) E L 0o) for some to > 0. Then
c(r)
lim 4500
||(((()))| #0,
where X is the solution of (3).
Note that 2 E [L oo) when > 1. The proof of Theorem 4.3 considers 2 (-9 b) for & E R and uses the Fourier inversion formula. See Appendix F.2 for details.
Next, we consider B(t) 2. for cases other than p >
Theorem 4.4. Lel A = ( (-) B(1) = $. 0 0<p & 1, and > O. Let X be the solution given by (9) and Xo # 0. Let
12 for p = 1,, 21
r()) = foy for p = 1,7 11,
t2p for <<p<>
Then,
lim r(t) (f)) #0. (+22
We provide the proof in Appendix F.3.
5 Discretized algorithms
In this section, we provide discrete-ting time convergence results that match the continuous-tima rate of Section 3.
Theorem 5.1. Suppose A be maximal monotone operator, p 0, and 7 0. Consider
x² JAY
kP
(2x -y x-11)+ KP + q
kP
for k 1.2..... with initial condition 1 20 R" Let Ax yx 2h for ls 1.2..... Then this method exhibits the rates of convergence in Table 2.
p= 1, 1=
Case
P<1
p>1
221 <<1
|| ( 0 (
(1)
Table 2: Rates for the discrete- siccretettime method of Theorem 5.1.
Note that the method of Theorem 5.1 reduces to APPM when 7 1, 1.

---

Proof outline of Theorem 5.1. The general strategy is to find discretized counterparts of correspond- ing continuous-tim analyses. However, directly discretizing the conservation law of Proposition 3.2 was difficult due to technical reasons. Instead, we obtain differently scaled but equivalent conservation laws using dilated coordinates and then performed the discretization. The specific dilated coordinates, inspired by [67], are W1 (t) X(t) - Xo for p > 1, (t) = EP (X Xo) for 0 < < 1, Xo) for p- 2 and (t( = t7 (X -X) for p 1, < <<<
=t
In the discrete-time analyses, the behavior of the leading-order terms is predictable as they match the continuous-time counterpart. The difficult part is, however, controlling the higher-order terms that were not present in the continuous-tinn analyses. Through our detailed analyses, we bound such higher-order terms and show that they do not affect the convergence rate the end. We provide the details in Appendix G.3.
Convergence analysis under strong monotonicity
In this section, we analyze the dynamics of the anchor ODE (3) for j-strongly monotone A. When 8(t) and A (6 2). Lemma 4.1 tells that A(((t) : - e e-tA) Xu and therefore that [IA(X(()) = + (12 which is a slow rate for the strongly monotone setup. On the other hand, we will that ((()) -
2y is better choice leading faster rate in this setup.
Our analysis of this section is also based on conservation law, but we use slightly modified version to exploit strong monotonicity.
Proposition 6.1. Suppose Å is monotone and Lipschitz continuous. Let X be the solution of (3) and let R: 20) (0, 0o) be a differentiable function. For to > define E 00) R as
E = C())R((()
(IA(X(()) +28())(((()))))))))))))))))))))) x(1--X)) + (B(1)² +())) ||x(1) -xoll R((s)
2
-f d ((s))(())3(
(Ax(t)Xxol) ds + [(s')) ( (
R(s) (((s) (2) ds.
Lo ds
2
Then E is constant function for E [0, o0).
Proposition 6.1 generalizes Proposition 3.2, since it corresponds to the special case with R(() = 1.
Recall from (2), when A is p-strongly monotone we have
( ds
d
((X(())
| 20.
-
This motivates the choice R(t) eti, since R(a)
Ti.s) p. From calculation provided in Appendix H.2,
2u the choice 3(1) - makes d ( (Cs)) ((a)) O. Plugging these choices into Proposi-
tion 6.1 and following arguments of Section 3, we arrive at the following theorem.
Theorem 6.2. Let A be p-sttrongyy maximal monotone operator with μ > 0 and assume ZerA + Let X be a solution of the differential inclusion (3) with ((1) =. i.e. for almost all t,
2/
X (-A(XX) 2pp
(X))
(10)
Let A(X(t)) be the selection of A(X(t)) as in Section 2.1. Define V [0, 00) + as
(it) = (eltt m- ||A(X()))) + 2p (1 -e- e- 2ut) ((x(((1)) X(t)) Xo) - # (x(() xoll²)
Then V(I) S V())) holds for 2 Furthermore for X. E ZerA,
2/
2
1
[A((())) <
eat -1)
||:0 - X, 12 =
eluu
8

---

In Appendix H.2.3, we show that (10) is a continuous time model for OS-PPM of Park and Ryu [54]. In Appendix C, we show the existence and uniqueness of the solution.
24 E L [to, oo) for any Since ((t) 2ام
O, Theorem 4.3 implies that (t) 0 when A is
merely monotone. This tells that the optimal choice of 3()) for should depend the properties of A. In the following section, we describe how 3()) can be chosen to adapt to the operator's properties.
Adaptive anchor acceleration and experiments
In this section, we present adaptive method for choosing the anchor coefficient 8, and theoretically and experimentally show that this choice allows the dynamics to adapt to the operator's properties. It achieves the optimal
-convergence rate when A is monotone and exponential convergence rate when A is furthermore μ-strongly monotone and Lipschitz continuous.
Theorem 7.1. Suppose Å is Lipschitz continuous and monotone. Consider the anchor ODE
|
x =-X)(X) 2 (A(X), Xo)
(X (X-Xo) -Xo)
(11)
=-B(1)
with initial condition X(0) = Xo and ||A(Xo]]| * Suppose the solution exists and X is continuous at t = O. Moreover, suppose 3: (0, 00) + is well-defined, i.e., no division by zero occurs in the definition of (t)). Then for t > and X, E ZZrr,, we have 3(t) > 0 and
[|A(X()))] - 43(1)² | X.11
3(t)² &
A is furthermore p-strongly monotone, then for O.
p/2
B(t)² -
gut/2 -
We provide the proof in Appendix I.1. Note that anchor coefficient (11) is chosen that ((t) |A((())) 2 + 23(t) (A(X)))), - -Xo) = 0. So left-hand side of (8) is zero and O (B(t)?) convergence rate is immediate. An analogous discrete-time result is shown in the following theorem.
Theorem 7.2. Let A be a maximal monotone operator. Let x = v RR. Consider
x²
JAAk
yx
(2x
()-1) BEXO"
with
A
A #0 112 O,
Bx
- (A* Il x0) + ||
for K 1,2...., where Ar x -
Then Br 2 0 and
Am 11 < <,32 11 x²
1
B < (k: 1)2
for 16 = 1,,,... and x²* E ZerA.
If A is furtheemoore u-strongly monotone and L-Lipschitz continuous, then for k 1,
/1(1 T.2) (1+ L2)) 1 / 11(11 12)
B2 <

---

10a
with APPM
with Halpem, 5
10a
Adaptive
10a
10a
10c
2000
4000
60000
8000
10000
Iteration count
Figure 2: (Left) Network graph. (Right) Squared M-norm the method in Theorem 5.1, we use = 1.5 and y = 2.0.
|Ax*1]
k. Halpern corresponds to
(K+1)Z 10 x=1 matches the exact optimal rate of APPM [54]. In the limit μ + O, the result for the j--strogly monotone case reduces to the result for the monotone case. We provide the proof and details of Theorem 7.2 in Appendix I.3.
For the monotone setup, the rate | ||
The method Theorem 7.2 is discrete-time counterpart of the ODE of (11). The extra term || of the denominator in the definition of 3g vanishes in the continuous-tims limit. We provide further details in Appendix I.2. Analogous to the continuous-time case, a key property of the discrete-ting adaptive method is that the counterpart of (t) is kept nonpositive. In the proof of Lemma I.3, the fact B& plays the key role in proving this property. The extra term
||Ax [|2 in the denominator
and the fact that (Ax*, ak x²) 0 when ||=
leads 3a
7.1 Experiment details
We now show an experiment with the method of Theorem 7.2 applied to a decentralized compressed sensing problem Shi et al. [63]. We assume that we have the measurement b; = Agj + es where A() is measurement matrix available for each local agent i, is unknown shared signal we hope to recover, and e; is an error measurement. We solve this problem a decentralized manner in which the local agents keep their measurements private and only communicate with their neighbors.
As in Shi al. [63], we formulate the problem into an unconstrained & reggullari least squares problem
minimize
E (3llA - bell2 + p||=|11)
and apply PG-EXTRA. We compare vanilla PG-EXTRA with the various anchored versions of PG-EXTRA with 9₃ in Theorem 5.1 and Theorem 7.2. We show the results in Figure 2. Further details of the experiment are provided in Appendix J.
8 Conclusion
This work introduces continuous-time model of anchor acceleration, the anchor ODE X -A(X) - ( - -Xo). We characterize the convergence rate as a function B(t) and thereby obtain insight into the anchor acceleration mechanism. Finally, inspired by the continuous-time analyses, we present an adaptive method and establish its effectiveness through theoretical analyses and experiments.
Prior work analyzing continuous-time models of Nesterov acceleration had inspired various follow-up research, such as analyses based on Lagrangian and Hamiltonian mechanics [71, 72, 26], high- resolution ODE model [62], and continuized framework [29]. Carrying out similar analyses for the anchor ODE are interesting directions of future work.
10

---

Acknowledgments and Disclosure of Funding
This work was supported by the Samsung Science and Technology Foundation (Project Number SSTF-BA2101-08 We thank Jaeyeon Kim for providing valuable feedback. We thank Hangjun Cho for the helpful discussions on well-posedness of ODEs. We also thank anonymous reviewers for the constructive comments.
References
[1] J. K. Alcala, Y. T. Chow, and M. Sunkula. Moving anchor extragradient methods for smooth structured minimax problems. arXiv:2308. 2023.
[2] V. Apidopoulos, J.-F Aujol, and C. Dossal. The differential inclusion modeling FISTA algorithm and optimality of convergence rate in case 3. SIAM Journal on Optimization, 28(1): 551-574, 2018.
[3] H. Attouch and A. Cabot. Asymptotic stabilization of inertial gradient dynamics with time- dependent viscosity. Journal of Differential Equations, 263(9):54 2458, 2017.
[4] H. Attouch and S. László. Newton-like inertial dynamics and proximal algorithms governed by maximally monotone operators. SIAM Journal on Optimization, 30(4):3252-3283, 2020.
[5] H. Attouch and S. C. László. Convex optimization via inertial algorithms with vanishing Tikhonov regularization: Fast convergence to the minimum norm solution. arXiv:2104, 11977, 2021.
[6] H. Attouch and J. Peypouquet. Convergence inertial dynamics and proximal algorithms governed by maximally monotone operators. Mathematical Programming, 174(1):391 432, 2019.
[7] H. Attouch, Z. Chbani, J. Peypouquet, and P. Redont. Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity. Mathematical Programming, 168(():123-175, 2018.
[8] H. Attouch, Z. Chbani, and H. Riahi. Combining fast inertial dynamics for convex optimization with Tikhonov regularization. Journal of Mathematical Analysis and Applications, 457(2): 1065-1094, 2018.
[9] H. Attouch, Z. Chbani, and H. Riahi. Rate of convergence of the Nesterov accelerated gradient method in the subcritical case 3. ESAIM: Control, Optimisation and Calculus of Variations, 25:2, 2019.
[10] H. Attouch, Z. Chbani, J. Fadili, and H. Riahi. Convergence of iterates for first-order op- timization algorithms with inertia and Hessian driven damping. Optimization, pages 1-40, 2021.
[11] J.-P. Aubin and A. Cellina. Differential Inclusions. Springer, 1984.
[12] J.-F. Aujol, C. Dossal, and A. Rondepierre. Optimal convergence rates for Nesterov acceleration. SIAM Journal on Optimization, 29(4):313-33153, 2019.
[13] J.-B. Baillon and R. E. Bruck. Optimal rates of asymptotic regularity for averaged nonexpansive mappings. Fixed Point Theory and Applications, 128:27 -6, 1992.
[14] S. Banach. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fundamenta Mathematicae, 3(1):133-181 1922.
[15] H. H. Bauschke and L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer International Publishing, second edition, 2017.
[16] R. I. Bot and E. R. Csetnek. A second-order dynamical system with Hessian-driven damping and penalty term associated to variational incqualities. Optimization, 18(7):1265-1777 2019.

---

[17] R. I. Bot and D. A. Hulett. Second order splitting dynamies with vanishing damping for additively structured monotone inclusions. Journal of Dynamics and Differential Equations. 2022.
[18] R. I. Bot, E. R. Csetnek, and S. C. László. A second dynamical approach with variable damping to nonconvex smooth minimization. Applicable Analysis, 99(3):361-313 2020.
[19] R. I. Bot, E. R. Csetnek, and S. C. László. Tikhonov regularization of a second order dynamical system with Hessian driven damping, Mathematical Programming, (891))1511-88, 2021.
[20] R. I. Bot, E. R. Csetnek, and D.-K. Nguyen. Fast OGDA in continuous and discrete time. arXiv:2203. 10947, 2022.
[21] M. Bravo and Cominetti. Sharp convergence rates for averaged nonexpansive maps. Israel Journal of Mathematics, 227:163-188, 2018.
[22] A.-L. Cauchy. Méthode générale pour la résolution des systémes d' d'équations simultanées. Comptes Rendus Hebdomadaires des Séances de I' l'Académie des Sciences, 25:536-538, 1847.
[23] R. Cominetti, J. A. Soto, and J. Vaisman. On the rate of convergence of Erasnosel'skii-Moe skin-Mann iterations and their connection with sums of Bernoullis. Israel Journal of Mathematics, 199(2): 757-772, 2014.
[24] C. Daskalakiss A. Ilyas, V. Syrgkanis,, and H. Zeng. Training GANs with optimism. International Conference on Learning Representations, 2018.
[25] J. Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. Conference on Learning Theory, 2020.
[26] Diakonikolas and M. Jordan. Generalized momentum-based methods: A Hamiltonian
perspective. SIAM Journal Optimization, 31(1):915-944, 2021.
[27] Y. Drori. The exact information-based complexity of smooth convex minimization. Journal of Complexity, 39:1-16, 2017.
[28] J. Eckstein and D. P. Bertsekas. On the Douglas Douglas-Rachfond splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55(1):293-318, 1992.
[29] M. Even, R. Berthier, F. Bach, N. Flammarion, H. Hendrikx, P. Gaillard, L. Massoulié, and A. Taylor. Continuized accelerations of deterministic and stochastic gradient descents, and of gossip algorithms. Neural Information Processing Systems, 2021.
[30] George J. Minty. Monotone (nonlinear) operators in Hilbert space. Duke Mathematical Journal, 29(3):3413346; 1962.
[31] I. Goodfellow. NIPS 2016 tutorial: Generative adversarial networks. arXiv: 17X.:1700100166 2016.
[32] E. Gorbunov, N. Loizou, and G. Gidel. Extragradient method: O(1/K) last-iterate conver- gence for monotone variational inequalities and connections with cocoercivity. International Conference on Artificill Intelligence and Statisticy, 2022.
[33] G. Gu and J. Yang. Tight sublinear convergence rate of the proximal point algorithm for maximal monotone inclusion problems. SIAM Journal on Optimization, 3055)1905511211, 2020.
[34] B. Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 73(6):957-911, 1967.
[35] D. Kim. Accelerated proximal point method for maximally monotone operators. Mathematical Programming, 190(1-2)57787, 2021.
[36] D. Kim and A. Fessler. Optimized first-order methods for smooth convex minimization. Mathematical Programming, 159(1-2)811-077. 2016.
12

---

[37] D. Kim and J. A. Fessler. Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions. Journal of Optimization Theory and Applications, 188(1): 192-219, 2021.
[38] J. Kim and I. Yang. Unifying Nesterov's accelerated gradient methods for convex and strongly convex objective functions. International Conference on Machine Learning, 202, 2023.
[39] U. Kohlenbach. On quantitative versions of theorems due to F. E. Browder and R. Wittmann. Advances in Mathematics, 226(3):2764 2795, 2011.
[40] M. A. Krasnosel'skin Two remarks on the method of successive approximations. Uspekhi Matematicheskikh Nauk, 10(1):123-127, 1955.
[41] J. Lee and E. K. Ryu. Accelerating value iteration with anchoring. Neural Information Processing Systems, 2023.
[42] Lee and Kim. Fast extra gradient methods for smooth structured nonconvex-noncoonaas minimax problems. Neural Information Processing Systems, 2021.
[43] L. Leustean. Rates of asymptotic regularity for Halpern iterations of nonexpansive mappings. Journal of Universal Computer Science,
2007.
[44] J. Liang, J. Fadili, and G. Peyré. Convergence rates with inexact non-expansive operators. Mathematical Programming, 159(1):403-434 2016.
[45] Lieder. On the convergence rate of the Halpern-iteratinn Optimization Letters, 15(2): 405-416 2021.
[46] T. Lin and M. I. Jordan. Monotone Inclusions, Acceleration, and Closed-Loop Control. Mathe- matics of Operations Research, 2023.
[47] W. R. Mann. Mean value methods iteration. Proceedings of the American Mathematical Society, 4(3):506-510, 1953.
[48] B. Martinet. Régularisation d'inéquations variationnelles par approximations successives. Revue Française d' d'Informatqque et de Recherche Opérationnelle, Série Rouge, 4(3):154-158, 1970.
[49] B. Martinet. Algorithmes Pour La Résolution de Problèmes d' d'optimisation et de Minimax. PhD thesis, Université Scientifique et Médicale de Grenoble, 1972.
[50] S.-Y. Matsushita. On the convergence rate of the Krasnosel skii-Mann iteration. Bulletin of the Australian Mathematical Society, 96(1):162-1)) 1700, 2017.
[51] Y. Nesterov. A method of solving convex programming problem with convergence rate O(1/k²). Doklady Akademii Nauk SSSR, 269(3):433-577, 1983.
[52] Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer, 2004.
[53] C. Park, Park, and E. K. Ryu. Factor- acceleration of accelerated gradient methods. Applied Mathematics and Optimization, 2022.
[54] J. Park and E. K. Ryu. Exact optimal accelerated complexity for fixed iterations. Interna- tional Conference on Machine Learning, 2022.
[55] J. Park and E. K. Ryu. Accelerated infeasibility detection constrained optimization and treddpoint iterations. International Conference on Machine Learning, 2023.
[56] L. D. Popov. A modification of the Arrow-Hurwiez method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR, 28(5):845-848, 1980.
[57] A. Rakhlin and K. Sridharan. Online learning with predictable sequences. Conference on Learning Theory, 2013.
[58] E. Ryu and W. Yin. Large-Scale Convex Optimization via Monotone Operators. Cambridge University Press, 2022.
13

---

[59] E. K. Ryu, K. Yuan, and W. Yin. ODE analysis of stochastic gradient methods with optimism and anchoring for minimax problems and GANs. arXiv:195./0899, 2019.
[60] Sabach and S. Shtern. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640-660, 2017.
[61] A. Salim, L. Condat, D. Kovalev, and P. Richtárik. An optimal algorithm for strongly convex minimization under affine constraints. AISTATS, 2022.
[62] B. Shi, S. S. Du, M. I. Jordan, and W. J. Su. Understanding the acceleration phenomenon via high-resolution differential equations. Mathematical Programming, 2021.
[63] W. Shi, Q. Ling, G. Wu, and W. Yin. proximal gradient algorithm for decentralized composite optimization. IEEE Transactions on Signal Processing. 63(22):6013-6033 2015.
[64] M. V. Solodov and B. F. Svaiter. A hybrid approximate extragradient proximal point algorithm using the enlargement of maximal monotone operator. Set-Valued Analysis, 7(4):323-345, 1999.
[65] W. Su, S. Boyd, and E. J. Candès. A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights. Neural Information Processing Systems, 2014.
[66] W. Su, S. Boyd, and E. J. Candès. A differential equation for modeling Nesterov's 's accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17(153))1-43, 2016.
[67] J. Suh, G. Roh, and E. K. Ryu. Continuous-time analysis of AGM via conservation laws in dilated coordinate systems. International Conference on Machine Learning, 2022.
[68] A. Taylor and Y. Drori. An optimal gradient method for smooth strongly convex minimization. Mathematical Programming, 2022.
[69] Q. Tran-Dinh and Y. Luo. Halpern- type accelerated and splitting algorithms for monotone inclusions. arXiv:2110.08150 2021.
[70] B. Van Scoy, R. A. Freeman, and K. M. Lynch. The fastest known globally convergent first-order method for minimizing strongly convex functions. IEEE Control Systems Letters, 2(1):49-54, 2018.
[71] A. Wibisono, A. C. Wilson, and M. I. Jordan. A variational perspective on accelerated methods in optimization. Proceedings of the National Academy of Sciences, 113:47):E7331--7733 2016.
[72] A. C. Wilson, B. Recht, and M. I. Jordan. A Lyapunov analysis of accelerated methods in optimization. Journal of Machine Learning Research, 22(113):1-34, 2021.
[73] R. Wittmann. Approximation of fixed points of nonexpansive mappings. Archiv der Mathematik, 5865):486-991, 1992.
[74] T. Wu, K. Yuan, Q. Ling, W. Yin, and A. H. Sayed. Decentralized consensus optimization with asynchrony and delays. IEEE Transactions on Signal and Information Processing over Networks, 4(2):293-300 2018
[75] Yoon and E. K. Ryu. Accelerated algorithms for smooth concave minimax problems with O(1k2)) rate squared gradient norm. International Conference on Machine Learning, 2021.
[76] T. Yoon and E. K. Ryu. Accelerated minimax algorithms flock together. arXiv:2205.1100 10093 2022.
14

---

A Prior work
Acceleration for smooth convex function in discrete setting. There had been rich amount of research on acceleration about smooth convex functions. Nesterov [51] introduced accelerated gradient method (AGM), which has a faster (1/k²²) rate than ((1/k) rate of gradient descent [22] in reducing the function value. Optimized gradient method (OGM) [36] improved AGM's rate by constant factor, and is proven to be optimal [27]. For smooth strongly convex setup, strongly convex AGM [52] achieves an accelerated rate, and further improvements were studied [70, 53, 68, 61]. Recently, OGM-G [37] was introduced as accelerated method reducing squared gradient magnitude for smooth convex minimization.
Acceleration for smooth convex function in continuous setting. Continuous-tinm time analysis of Nesterov acceleration has been thoroughly studied as well. Su et al. [65, 66] introduced an ODE model of AGM (t) + x + ( = 0, providing f(X(t)) - f. E O (1/t²) rate for r 2 3. Attouch et al. [7] improved the constant of bound for r > 3 and proved convergence of the trajectories. Attouch et al. [9] achieved O (1/t-2r/3)
2r/3) rate for 0 < < 3. Apidopoulos et al. [2] generalized their results to differential inclusion with non non-differentiable convex function. Furthermore, wide range of variations of AGM ODE has been
studied [3, 8, 12, 16, 18, 5, 10, 19]. Also, applications to monotone inclusion problem were studied by Attouch and Peypouquet [6], Attouch and László [4], Bot and Hulett [17].
Motivated from above continuous-time analysis for accelerated methods, tools analyzing ODEs have further developed. Wibisono et al. [71]. Wilson et al. [72] and Kim and Yang [38] adopted Lagrangian mechanics and introduced first, second, unified Bregman Lagrangian to provide unified amalysis for generalized family of ODE, where the latter provided analysis for strongly convex AGM. Systemical approach to obtain Lyapunov functions exploiting Hamiltonian mechanics [26] and dilated coordinate system [67] were proposed, and analysis of OGM-G was provided by dilated coordinate framework. Different forms of continuous-time models such as high-resolution ODE [62] and continuized framework [29] were developed.
On the other hand, another type of acceleration called anchor acceleration recently gained attention. As Yoon and Ryu [76] focused, many recently discovered accelerated methods for both minimax optimization and fixed-point problems are based on anchor acceleration. More recently, practical upplications of anchor acceleration to detecting infcasibility for constrained optimization problems [55]. and accelerating value iteration for dynamic programming and reinforcement learning [41] were introduced as well.
Fixed-point problem. The history of studies on fixed sxiet problem dates back the work of Banach [14], which established that the Picard iteration with contractive operator is convergent. Kransnosel Mani iteration (KM) [40, 47] was introduced, which a generalization of Picard iteration. Convergence of KM iteration with general nonexpansive operators was proven by Martinet [49]. For iteration of Halpern [34], convergence with wide choice of parameter were shown by Wittmann [73].
The squared norm || Tyx 1|² of fxxed-ooint residual is common error measure for fixed-point problems. KM iteration was shown to exhibit (1/k) rate [23, 44, 21) and -rae [13, 50). For Halpern iteration,
k)²)-rrate was established by Leustean [43], then improve to ((1/k) rate by Kohlenbach [39]. First accelerated (11/k²) rate was achieved by Sabach and Shtern [60] and the constant was improved by Lieder [45] by a factor of 16.
It is known that there is an equivalence between solving fixed- pointt problem and solving monotone inclusion problem [30, 28, 54]. Proximal point method (PPM) [48] achieves O (1/k))rrate in terms of || | 2 [33].. Accelerated proximal point method (APPM) [35] improved the rate to accelerated O (1/kk2)-rate -rate. Park and Ryu [54] showed APPM is exactly optimal method for this problem and provided exactly optimal method for u--trooggyy monotone operator named OS-PPM, which achieved O (1/e rate. The optimal methods APPM and OS-PPM are based on anchor acceleration [76].
Minimax problems. Minimax optimization problem of the form ming max, L(x, y) have recently gained attention in machine learning society. One of the commonly considered theoretical setting is smooth convex-concave setup, with squared gradient norm as error measure. In terms of [[L((,, y)ll classical EG [64] and OG [56, 57, 24] was shown to achieved O (1/k) [32]. SGDA [59] achieved O (1/k2-2p) rate for p > 1/2 with introducing the term anchor. With introducing a parameter-free free Halpern type method, Diakonikolas [25] achieved O (log k/kk). Recently, EAG [75] first achieved accelerated rate (1(kk²) with anchor acceleration, followed by FEG [42], anchored Popov's 's scheme [69] and moving anchor methods [1]. Fast ODGA [20] also achieved accelerated ((1//² rate. For ôL is furthermore strongly monotone with condition number k, rate.
SM-EAG+ [76] achieved accelerated O 21/
However, continuous-time analysis for anchor acceleration is, to the best of our knowledge, insufficient, Continuous-time analyses of acceleration for monotone inclusion problem were studied by Bot et al. [20], Lin and Jordan [46), but they did not consider anchor acceleration. Ryu et al. [59] considered continuous-time analysis of anchor acceleration, but only with limited cases X A() - 7(X- Xo) for 7 2 1. In this paper, we provide unified continuous-tine time analysis for anchor acceleration with generalized anchor coefficient.
15

---

B Proof of Theorem 2.2
B.1 Proof uniqueness
Proof of uniqueness is immediate from Lemma 2.3, we first prove the lemma.
Proof of Lemma 2.3. It trivial for = O, so we may assume >> By monotonicity of A and Young's 's inequality, we get the following inequality.
d dt
x()) - 2 = (x (x(0) - (1), x(() -()))(()))))))))))))))))))))))))
(A(( ( (((X()))-AOXX))+)0)(((XX))
Y(t) ((t)(X) X(). Y(t))
I -2((t) [x((t) - ((0) + (Xo X()) - (()))
S -2((t) (x(() - ((0) ((t) (1xo - Yoll + [|x(t) - x(H))²)
B(t) (t) (( + + [| -Yol?.
Now define C(t) = eSt p(s)d= for some v >> O, then we see C(t) = ((t))((). Moving - -(( (() Y()I to the left hand side and multiplying both sides by C(t), we have
d di (C(O) Y()))) c(t) d di [Ix(t) Y(0I1 + C(B)((() (I((t) (())
((L))(() 1X, - -Yol d
C(I) ||o -Yll
dt
Integrating both sides from >> to we have
C(t) (t) - (+) - [(c) - Y - C(t) X, - Yoll² - -(e)) I|Xo Yoll?
As nonnegative and nondecreasing. lim,- C(t) exists. Taking limit e + 0+ both sides we have
C(() (I) - Y() < C(1) 1Xo - Yoll".
Finally, dividing both sides by C()) we conclude
(() y()I Xo Yo12
Proof for uniqueness can be done to generalized case (3).
Theorem B.1 (Uniqueness of solutions). If the solution for (3) exists, it is unique.
Proof. Suppose X1, are solutions of (3) with same initial value Xg. By Lemma 2.3, we have
X1 (t) xt)l S |X, Xoll = 0
Therefore (t) = (t) for all t E [0, 20), we get the desired result.
As (6) is special case of (3), uniqueness proof for Theorem 2.2 follows from Theorem B.I.
B.2 Proof of existence
The proof of existence needs tedious work due to the singularity of 7 at t = O, we provide our proof through subsections. # Before start, we provide short outline of the proof. The proof is basically based on the proof provided in [65] and [11].
We first prove the case A is Lipschitz. The differential inclusion becomes ODE when is Lipschitz, we can adopt similar argument done [65]. We consider series of ODEs Lipsehitz with respect to X, approximating x = - (X) - 2
F (Xo
(()). The approximated ODEs have solutions by classical theory of ODE, we obtain the true solution by considering proper subsequence of solutions.
As the solution for Lipschitz A is obtained, we can adopt similar argument done in [11]. We first consider solution Xx with Yosida approximation A^ (I - (I + XA)-1), which is an approximation of A that is Lipschitz continuous. Then we can obtain a subsequence XA converging to original differential inclusion.

---

B.2.1 Existence proof for Lipschitz A
Since will approximate A with Lipschitz continuous functions, first consider the ODE with Lipschitz continuous A. Theorem B.2. (Existence of solution for Lipschitz A)
Suppose A [ + R" is L-Lipschitz continuous function. Consider the differential equation, with initial value condition
(0) = Xo E dom(A).
-((())))))) 2x - Xo).
(12)
tD where 7pp> O. Then there exists a unique solution X (10, o0), (2")) that satisfies (12) for all t E (0, oo). Moreover, for (0) defined by {() litm:-0+ X(e)- Xo, following is true
A(Xo) (0) = A(Xo)
if 0 0<p<1 if = 1
if p> 1.
The proof need some preparation. We will think of approximated solutions Xs. obtain sequence that converges to solution X. Thus we first define X5. From now, will denote A as L-Lipschitz monotone function. Definition B.3. Let 8 < 1. Consider
( -(xx(())) (Xx((1)
((x())))(xx(0)- Xo) 051<6
Es(1) 1- -
(13)
- (Xx(t) Xp) t>
Since right hand side above is (T. + -Lipschhtt with respect X3, the solution uniquely exists by classical ODE theory. Define the solution as Ng. Then for positive sequence {6m Jmen such that 6m < 1 and limm- 5m = 0, consider sequence
{ (Xom) meN
Before start, prove useful lemma we will widely use for the cases that operator is Lipschitz continuous.
Lemma B.4. Let À: R - Ra Lipschitz continuous function. Suppose B: D [0, oo) be continuous function with
D C (0, oo). Consider differential equation
X - - 3(t) - Xu),
with Xo E RR Let X: D + R" be differentiable curve that satisfies above equation for E D. Then for all 0 S a < b such that b) C D, X and the composition A X
|a, b] R are is Lipschitz continuous.
Moreover if (()) is well-defined and bounded for almost all t E [a, b], then X is Lipschitz continuous in [a, bj. Thus if B is twice differentiable, X is Lipschitz continuous.
As Lipschitz continuous functions, X, Ao X and X are absolutely continuous functions.
Proof. We first prove X is Lipschitz continuous. As X, B are continuous in [a, b] we see continuous in (a, b), thus
-o) is
x = max xE(a.b)
[((((t)) + (()) - xo)|
Mi max
rE (E(a.6)
exists. Since its derivative bounded by M1 < oc, we have X is Mı-Lipshitz continuous. As composition of two Lipschitz continuous functions, À X Lipschitz continuous.
First observe if / is twice differentiable, 3 is bounded in (a, bj it is continuous. Now if ((t)) is bounded for t [a, b). i.e.
(3(e)| < M2 for some M2 > 0, for M3 = maxre(a.0) ((())) we have
d (S()((((() -x)) - (())(())())) xo)|| (())((())))))))))))))))) < M2M, 16 al M3M1
Therefore (8)) - Xo) is (M2Mi Mi [b-ul MM,Mi))LLisshiizz continuous. Thus as sum of Lipschitz continuous functions, X is Lispchitz continuous.

---

We will show for every T > 0, the set of derivatives { 18 E 1). is uniformly bounded on [o,
T] and { (8mm }
mEN
converges uniformly on [0. T. We first prove the boundedness of derivatives. To do so, we first prove a useful lemma.
Lemma B.5. For < a suppose X (a. b]
+ R satisfies ODE (or) t E b). Define Ú [[a, b] - R as
(i(t) |}(0)} || +
PP
[(())
| Xo ||
to-
Ú2(1) - - || {
2 +
PP Ps
(1) Xo |
Then Ü, is nonincreasing for 0 < p S 1, and U2 is nonincreasing for p > 1.
Proof. From Lemma B.4 we can check U, and U2 are absolutely continuous in [a, bj. Therefore it is enough to check the derivative is nonpositive for almost all From Lemma B.4, we can differentiate (12) both sides. Thus for almost all we have
d - + iPt1 (X(1) Xo) 1P x0) x(1)=
d -
Recall from monotonicity of Á and (I), we know
(A(0) (000 2 for almost all t. Therefore for almost all t,
i) 0<<s1
(i(t)= = 2 (x(0), + 27p (x(1),(()) - Xo)
2p(p+ + 1)
|x((0) - xoo|
tpt1
totz
= =-2 {81), (x())
(A((1))
27
|
27p
(x(1),()) 8(1) - xxo)
+
10
10+1
( (x(1),81) (t) - -xo) 27p
2xp²
|x(1)= -Xol
||
2 Tp(11 - pp)
(x()) - Xo 2
t1+1
2 (x(t), dt
d A((x(1)) )
27
|Ix(t)) -(x
-xoo²
7p(1 (1 - p)
|x(() - Xo 1
1p
t2+2
00.
(ii p>1 1
p-1 1 02(1)
2
(K(). x()) +
27p (x11), 8 -xo) -
27p
((1) xoo2
(11
+
2
to
1-ー
:20
f2++1
=_P- p-1
( 2
2
(x((), d A(X(()) dt
1-
27
+
27p
(x()) X - -Xo) +
27p
(i((), -Xo)
(xx)) 1d
27p
[((t) - -Xo
(2y-1
f2p
{2p
p 1
|
2
2
(x)) d ((((11))
2n
||x000 - (Xx)
10
di.
< 0.
We now are ready to prove uniform boundedness of derivatives Es. Lemma B.6. Take T For all t E {00,T] and 8 E (0, 1), below inequality holds.
VI + rp A((x))
0<p51
|ia(tt| S MT)
V TD-1
1
+ 2212 + 2y +
p21.
27
18

---

Proof. We prove first statement by considering two cases.
(1) E [0,5]
From Lemma B.4, we know Xa is absolutely continuous and [
is absolutely continuous as well. Differentiating
(13), for almost all & E (0, we have
ES = dt
d ===-2A(Xx(1) A(Xx(t))
X8.
5P
Now for almost all & E (0,6),
d di
8: Xs) -2 Xx (xn,
d (((x(1))
27
{
1=
27
| so.
S
d
5
88
ii 0 <
From above we know
Xx
is nonincreasing in t E [0, 6). we have
|
||x00
(ii) p>>
Integrating
d
|
-
23 27
||,8||| we have
/ 22=
--
s 50 J. || | ds
27
80 1/1 |
2nl
|| |
ds -pp
80
Organizing with respect to || || we have
{xS(O)
| 5
SP 5P + 271
|
SP s $V22
|
2xd DF
276
+
(2) t26 8 Note for > (12) holds, we can apply Lemma B.5.
(i) 0 < 1s
From (i) we know |x,(t) s ||((X)) fort [0, Therefore
| S
|
and we see
[xs(6) -xo0) = 1/²0 X((() do S { [o//
From Lemma B.5 we know Üi(1)) = 1| |is(to\ + +
[xs(() xoo' is nonincreasing. Therefore |//(0)|²= <
(0) for t 2 8. Since d < 1 we have
| S (0((0) - (110)-/(((())))
7p + Ip+I
(x(0) - Xo 2 S v + 7p A((x)]]
s v / |(xo>|| + +~00010 1agg)~>||(xx |
(ii) p>1
From (i) we know {ts(t|
S V
5z
A(Xu)
for E 60. Therefore
| S
5=-1
A(Xo)
and we
2y
24
see
SP $ [ ||<cTم|| ds 3 1-' V 275
28p+1
[xo(6) - Xoo
A(Xo) ds =
|((X))
7

---

Applying (13) and recalling the fact A is L-Lipschitz, we have
2² 82p
Xol1² ((xx(()) xx()) (((x(()) A(X)) A(Xo) Xs(0o]|
[xx(
2 A((x(0)) A(Xo) || + A((x)) + +X((8) 2
- 21 [Is(0) - X I |(Xx))| 1| +4 |
4 1 122 + 4 -
260-1
||ā(xo)
<
7
is nonincreasing. Therefore |
From Lemma B.5 we know (2( /
{((t)|
+ 20 X(1) Xo
(6) for 2 Since < we have
{
/
$ Vūz(0)
7P 82p
[x((0) Xo
+
VIP-1
80-1
A((x)
p (41.200+ + 4y + 2280-1) (00-1)/|(((x))
|((X)
S /V 2x
1
+ 2p + 2x 11+11||A(xo))
27
Therefore for E [0, 2] we have
| s /V 2
(1
+ 2p (212 + + +11 |
22
From (1) and (2), we get the desired result.
We now show the sequence [xom } proposition.
meN converges uniformly on [0, 2] for every T > is suffices to prove following
Proposition B.7. For T >> 0, the sequence &8mm
is Cauchy sequence with respect to supremum norm on [0, 7j.
meN
Proof. Take 0. We want to show, there is N E N such that if n, m N then || {x5 (1) Xi, (1)l for all i [0, c0).
Define (1) 1
xxco Without loss of generality, we may assume 2 u. With Maoe(T) defined
Lemma B.6, will show (t) 28 Made (T)
First consider the case < t 1 8. By Lemma B.6, we have
[xx(t)) xx)() < / (56(0)) xx(0) ds s S'' ([> + | ds
< / (T)dds = (T")
Thus for E [0, 8) we have
d8 (1) < 212 Mad & 28 (T)?
20

---

Now we consider the case & 8. By monotonicity of Å, we have
d
Xs(t)-
xx(0 = (xx(t) (xt)), xx())
dt 2
(A(Xs(()) (()) - 50
(xx(t) - -Xo) + 2 (xx(t) - Xo() - -x,(t)
2 (Xx(t)) Xo) + 2 (Xx(t) Xo(. - X,(())
Eo
8
io (1xx(()) - (t)l
s 0.
Thus we have (t) S (6) for 2 6. Now combining two cases, we have
ds) S 28 Moon (T)
(14)
Since +0 6n = 0, there N such that m > nn> > N implies dm S =. we're done.
We are now ready to prove Theorem B.2. Proof.
(1) Existence of solution.
From Proposition B.7, we know
{ (6om j mEN
converging uniformly on [0, T) for every T >. Denote the limit X,
i.e. define X: [0, oo) - Rd as
lim X (t) = (t).. m-+30
We can check (0) Xo easily since Xsm. (0)
Xo for all m E N. It remains to show X satisfies (12).
Take / > 0. We wish to show
8 h) - x(1) -(1) lim h=0
+ A(((t)) + 7 (x(1) Xo) =0.
h
to
Consider h. 5, T such that 0 < |h] < <t, < < min {1,t |h] and T > t + 1h/. Then (t- [h], + [h]) E [0,
and xs(1)= = A((x(()) - //4 (8s(1) - Xo). Consider inequality
X( h) 1 -x(t) + A(((1)) + 2 (x(1) - -xo) 10
h
X(1+ h) x(1) h
Xall + h) - Xx(0) ||
+ Xx(l h) xx(())
E6(0) + +1 (((0)) 2
18 (x(1) Xo)
h
We now show right hand side goes zero h + O. The point of the proof is, Xs converges uniformly to X and X, is uniformly bounded on [t- - [b]. 7].
From (14) we have
x(++h)- - X(t) Xs(t+h) Xo(t)
1 ((x(+))) - 8s(1 + ti]l + +|(2(0) +|(0(0))80001) S 5 [7]]
$11m Man((T)
< M
Also from (14) and since À is L-Lipschitz continuous, |i5(0) + A(X(1)) + 3 (x(1) xo) - ||||- (A(X:()) 2 (Xx(1) - (x(1)-x))) + A(((1)) + 7 (X(1) -xo
to $ / - X(t)| + 1/4 [x((t) x(t)|| s 28 (L 2 Maoo(T))
10
21

---

Now from Lemma B.4 we have (t) is absolutely continuous, thus
= b:th (Xs(s) - {x(())
Et + 11) (t( Xa(e)
ds
h
h
[7i] 1. gthh J.a (olu du ds
1 eth
S. [[Eaaass)
S [7.
du du
Observe, for almost every E [t
[1) , + [//]] < T) by Lemma B.6 we have
=
d A(Xx(uu))
PY
(Xs(u) - Xo)
2 x
+ u0+1
du
wp
d A A(()((1)
PY
I Xo(()ddo) + +11 Xx(xs)
+
du
1P+1
LM
+ (1- 11-1h/ptti
py
Lo
(ooo(T))d + (t- 1hl) Maor(() (T)
?
prf +
L 4- (L- (1-1N) (L-
Máso = M.
Note M is independent of or 6. While obtaining the inequality, we used the fact that A(xx(.) is LMM -is-hissc continuous in [0, T). Now
J.¹ |[ du ds S
1 [h]
1
1. 1+h S: M du ds
[/ f.aee (s t)
1
M (t
||| M.
[/|
Now consider = 1 with h small enough that satisfies [b| < and [/] + h < t. Then the conditions |h| < t, 0 8 < min {1,t- |/] hold, above arguments are valid. Gathering above results, we have
X(1 h) X(1) + A(((t)) I to (x(t) (x)t
xx)
S 22V2 + 22 (L+ 3) Made (T) + |h|
M O ((h)).
which implies the desired result.
(2) The value and continuity of (t()) att O.
Define Ctt) as
17
p=1
C(t)
p> 0,p
Then for t > 0
d di
(C()) (x(1) (((()-x)) = c(1) (x(1) + (x(1) - -xo) -C())((()))
Integrating both sides from é > to t we have
C()( - Xo) - Xo)=
(())((X())) ds)
As C' is nondecreasing function and bounded below by O, limm--o C(e) exists, taking limit -> 0+ we have
(()((()) - Xo) =- 1/' (()) ds.
22

---

Dividing both sides by #C(t), with change of variable s/t, we have
(t) - Xo
- 1.¹ C(L)
C(s) (()(s)) ds - - [ C(()
C(to)
T
((X(1e)) do.
Observe
C(tv)
p p= 1
C(t) c (
p 1,p 0.
Note I-p 1-11-PP (v- S 0 for E [0, 1}. since T-p and (u- 1) has opposite sign either 0 < < 1 or
p> Therefore e (6 < 1. Also, (t((t) is bounded for v E [o, 1] since A(X()) continuous by Lemma B.4.
So we can apply dominated convergence theorem and take limit t + 0+ Since
<<p p <
lim C(to) - C(t)
6² p= 1
p>1
for +f 0, we have
-A(X,)
0< p < 1
(1) - Xo =-
C(tv) A((((t))) dv
(0) = lim t-0+
lim 600
A(Xo)
p= 1
(15)
C(t)
0
p>
We now check (t) is continuous at t 0.
(i) 0 <<p < For > 0, we know
X(1) -A((()) - (8(1) Xo).
18
Observe
lim 2 (X(() Xo) = lim
Tt' x(t)
Xu -xu
10
0<p<1 1
(16)
6-0+ to
600+
t
7 A(Xo) p=1. 7+1
Now from ODE x() = - ((}(t)) 7. (X))) - -Xo). by taking limit t - 0+ we have
f - A(Xo)
lim x(t)= A(xo) - lim +
(2 (x(t) -xo)
-1 741 A(Xo) p=1. 1.
0 0< <
+ to
Therefore (t) is continuous at 0. (ii) p For p 1, we don't it know the value of lim # (X(1) ((0))-o)) Xo). Thus we first find the limit.
Let's go back to
((s) ->
Recall C(t) Ct).. By taking integration by parts for the right hand side, we have
1/¹ C(s)A(((s)) ds _ (C())((((I)) -
s C(s)A(((ss) ds S:d s" c00 ds
d (() ds.
7
Where we know A()(s)) is differentiable almost everywhere from Lemma B.4. Now, divide both sides by ((t( Then for to we have
(x(()) Xo) -A(((())) ( PP C(+) A(X(s)) ds + ( C(I)
S C(s) d _A((()))) ds C(t) ds
d
=-Ā(8(1)) + {' PDP-1
C(tv) A(X(s)) du+ + L' 1 C(tv)
(d A(X(6)) ld.
C(L)
C(t) ds
23

---

From Proposition B.7 and since X satisties (12) for for s (0,t) we have
7 to (x(s) Xo)
(A(Xs.. (8)) 7 to lim m==20
(88m (5) (s) xo))
Xom (s).
lim m=-000
From Lemma B.6 we know [. (b) S Maor(t) for & E [0, f]. taking limit m + oo we have
|x({) -
(t) for E [0, Thus (s) becomes Man (f)-Lipschitzz continuous in E [0, And so (Á (s)
becomes LM (tipipchhzz continuous in & E 40, we have 4 de A(((s)) - LMMoo(() for almost all
E [0, f]. Moreover ((tu)/C(t)) is bounded for e E [0, 1] since C' is a nonnegative nondecreasing function.
Therefore we can again apply dominated convergence theorem. Reminding lim,-0+
Cits) 0 for p 1, taking C(t)
limit - 0+ we have
lim (X(() - Xo) = -A((X) +0=-A(X)) ++ t
(17)
Finally we have
X(1= - ++
lim
-A(x)
lim
f (8(1)) - (xx())-xx)))))))() = -A((X)) - (-A(Xo)) = =0= =x(0).
z00
Before move on to original inclusion, we prove important corollaries that bound []. Note the main difference between following corollary and Lemma B.6 is that the dependency Lipschitz constant L is dropped for the case p > 1, which will be crucial in the next section.
{ and
||)((())| uniformly
Corollary B.8. Denote X as the solution of (12). Then for T > 0, following inequality is true for t E [0,
((xx))
0 p <1
|
A(XO)
V++I
p=1
2TT-1
A(Xo)
p> 1.
Proof.
i1 0<<$5
As X is the solution for (12), from Lemma B.5 we know
(1(1) = |
PP +p+1
|8(1) Xo 2
is nonincreasing function. From (15), (16) and continuity of x() at 1 = 0. we have
|(xx)) 2
0<p<1
lim Üi(e) = c0
(18)
A(Xo))
p=
Therefore | s sii()= < lim,-o+ Üi( for O, we get the desired result.
(ii) p>> As X the solution for (12), from Lemma B.5 we know
Úz(1) = -1000111- X
|
1|
{(1) Xo
|
{(11) 2
a nonincreasing function. However, as we don't know the value of lim, ppー
we first calculate it. To
do so, we consider
Ú,(1) = -x(00||>((0''' +
rp i++
((t)=
Xo
24

---

In the proof of Lemma B.5, we have observed its derivative becomes
(t(+)=-2 -2
- (tt,, d dt
A(X(())
27
(x(t) - -(()))(((()) (e(()-xX0 ((x((t)xxo)) -xoi|² 7p(1 - p)
xx(t) Xoo
t0t2
yp(p 1) 10+2
[(t) xol|
For >> 0, integrating from c to È we have
Ui(t) S Ui(e)+ +| [" uppp - 1)
((s) Xool ds.
SP+2
8-Xo We consider taking limit - 0+. Observe from (17) and (15) know lim 10
A(Xo) and
|x(0 0,
?
and therefore we have
lim U1(c)= = + lim c+00+
PP ((()) - Xo e = [||
lim c+0
e O.
c+0+
e2p
||x(0)-Xo|]*
|| g2
|800)x01'
Moreover as lim
there is 5 0 such that 0
5 implies
52p
2|| [1 Recalling p > 1, for <<< 8 we have
7
12
l yplp - 1) ((s) Xo 1 ds 1 / 1p(p - 1) A(Xo)
ds
8P42
52-D
72
2p(p 1) 10| {(xo)
2
2p
A
(Xx)
?
0
7
therefore
[x((s) xo|²d. ds 5 2p [(Xo)
2
11p(p-1) 1)
e0-1 f"
(1p(p-1)
1plp 11 1)
{{(s) Xo {
ds oc.
SP+2
sP+2
Thus the integral is well-defined when + 0+. Taking limit e + 0+ we have
(i(() S L Tplp - 1)
[8(s)= - xxol
-xo])xx|o ds.
sp+2
Moving
Pp #p+1
[(())
Xoo]" the right hand side, we get a inequality for |3{(E)|??
|>100 2 (i))
TP |x()- - xol? < {
1plp 1) 2
((())
Xol| ds
YP || ((()) Xo
+
Observe, by L'Hôpital's rule we have
2p(p-11 1) 00
{(s)
Xo ds
7p(p-1) IP12
((t) Xo
2
X(t) Xo
2012
P A(xx)))
lim 1-0++
lim ++
lim yp 20
1P-1
(p- 1)60-2
12p
Now dividing 1p-1 to previous inequality and taking limit, we conclude
lim 0+
X S lim
1
yp(p - 1)
x Xo
1 ds
lim
TP
X Xoo
1--
+++
SP+2
6-0
fpp
p A(Xx))
[
|?
7
0.
25

---

Thus we have lim 8-- |x] 1²= = 0. Therefore,
lim Ü2(c) lim ++0+
{(ee
+
P 22p
[(e)
P xoll)= =
~/= 7 ||(x ||=
c- cP-1
{
2 I lim
+0+ U2(t)= = =||á(xo)]
From
we conclude the desired result.
Corollary B.9. Denote X as the solution of (12). Then for T >>> 0, following inequality is true for t E [0,
(1 + 1) 11 (1+Tt" p
||xx)||
0 <<p<1 1
|(((0)) S
A(Xa)
p=1
p>l. 1. plrttl (TP-1+ + ||(xo))
Proof. First observe,
|(0(00))/= = -1(x00- + 7 (x(() - -xoo]²
= =|<²0|1 2 22 (x()) x((t- -x
32
||
[x(1) Xol|
1200
(X(t)= - -Xo 1
s | +
|12c08|2+ +
72
[x()= Xo 2
+
122
12p
(7+1) (|xx0)/²+
+
7 p2p
[x(1) - 1000xxo1- xol²)
The inequality comes from Young's ' inequality. Now we consider each case.
(i) p = 1
For this case, the terms on the right hand side exactly become Ui Therefore from (18)
A(X(0)) s (7 + ())) s (7+
lim Úi(c) = ||A((x))) e
(ii 0 < p 1
Recall from the proof of Corollary B.8 we know (t S lim.-0+ Üi(c) = ||(x
Therefore we have
X(t) - xol ||| s (i) <
| ? applying Corollary B.8 we get
72 1P+1
| > (7+1) [1xT00|² +
xp t
x(t)
X
2 {1-p)
p
$ (7 |(x)))
(1+
T'
p
i p>L 1
+0+ U2(e) =2 ==|[(xx0)]?
Recall from the proof of Corollary B.8 we know (z( < lim
Therefore we have
26

---

/ x Xo %|| s Ü2( _ & |((x))] || applying Corollary B.8 we get
|A(X(t)|| - (
(|xcts]]
7P +
X(t)= 10--xoo xool 1/
pl +(7+1)
T--1 + ) |
B.2.2
Existence proof for general
Now we move on to the original inclusion. As noticed before, we will approximate A with a Liptschitz function Ax called Yosida approximation. We define and state some facts about Ax lemma, and use it without proof. For the ones who are interested in proofs, see [11, Chpater 3.1, Theorem 2].
Lemma B.10. Define Ax R R" as
A (I- = ( -I-
This is so called Yosida approximation of Followings are true.
(i) Ax is -Lipschhizz continuous and maximal monotone.
(ii) limx- AxT m(A(x))-
Here mx)(x)) defined as m(A(x)) [A)))((), the element of A(x) with minimal norm.
(ii) [x)]l S [I(
(iv) Vr E R". (x E A()Aa))
Now state the proposition that proves existence of Theorem 2.2 Proposition B.11. For Yosida approximation Ax, consider the ODE
Ax(x)=-((Xx())-- (X) Xo)
(19)
with initial value condition Xx(0) = Xo E dom((A. The solution uniquely exists by Theorem B.2, denote the solution
Xx- Now for T 0 and a positive sequence {Nu such that lim,-+oo An 0. define sequence of solutions
[0, + R. im E N}. Then there is subsequence (Amz JeeN such that Xxm, converges to the solution of (6)
uniformly on [0, T].
From Corollary B.8, Corollary B.9 and Lemma B.10 (iii), following lemma is immediate.
Lemma B.12. Let X,, be the solution of (19). Then following is true for t E [0, for all T >>> 0.
[m((A())
0 0<p<1 <1
|xx(t) s (T)
[m(((())]
p=1
2T [Im((X)))
p> 1
and
V (+ ( (1 (1++1(1++7 Tt-2)
[m(A(X))) x/) [lm(A(X)))I 0<p<1
|Ax(X)(0) s Ma(T)
p=1
الا+ام (TD-1+ |Im(A(X))]I
p> 1.
Proof. Replace À with A and X with Xx in Corollary B.8 and Corollary B.9. Applying ||A(X))]l S [|m(A(X))]]] from Lemma 10 (iii), we' re done.
27

---

While we're concluding the existence of converging sequence, we will exploit following lemma from [11, Chapter 0.3, Theorem 4]. For convenience, we restate the lemma here.
Lemma B.13. Let us consider a sequence of absolutely continuous functions I& I&(() ( from an interval of Banach space X satisfying
VI (I)) is relatively compact subset of X
(ii) there exists functionn e(-) E (1, 00)) such that, for almost all E I, [[xx(()]| S c(t)
Then there exists a subsequence (again denoted by) rv.()) converging to an absolutely continuous function af from I X the sense that
(i) (.)(.) converges to xx() over compact subsets of
(ii) (+) converges weakly i(-) in L (I.
Proof. See [11, Chapter 0.3, Theorem 4].
From Lemma B. 12 we can immediately check norm of all derivatives Xx,, are bounded by Mdor(T) So condition (ii) holds with Mdoe( (T). For condition (i), prove FT is convergent in C[, Lemma B.14. Fr convergent sequence in C((0, (."). In other words, Ve > 0, there is N > 0 such that n, m > implies supre(o.T] ||Xx,, (1) X (1)]l <e
Proof. We will show Xx,, is Cauchy sequence in C(O,,T),R*) R*). Let Let U, > O. From (19), we see for & (0,
d 1
(t) xx(1)]1 (x((t)Xx(t)),,)//) xx(1t)
dt 2
-AA)(XX()))
x,()) - (2))) - 7 - -xx01)
I - (A) Xx()) (t))
From definition of resolvent we know I I- JAA- = AAx And from Lemma B.10 (iv) we know Ax E A(Jaa(x((t)).
Thus from monotone inequality see
(X)) (1)x Xx(1) - Xx(1)
(x.(X.(1) - (x)x (X.(X) (A)(X.()))
(X)( - (x(x)()), (x)( (x)(()(0))
S (-(AA(X.(0) - (1)) vA,X,()) - (A1((2(0))
= (A (AX)) (x(Xx())) - -
By Young's inequality
(v A) (X. AxXA)))) - (V1IAAXX000 +ADDI+++JJAAA +AIAAXA(11)))
/ (I(IAXXX)))) +1 11AXX11(0)))) +1 11
(VIIAXXX00)** +1IAx0001)))))
4 (AICA(()))))++)(XXX)X)))))))))))
1
Now applying Lemma B.12 we have
d 1 |xx(()) - -x(00) S 1 (w+ A)Ma(TT)))
dt 2
Then integrating both sides from 0 to & we have
(t) - xx(1)11 s f ( +)
(20)
28

---

Now take O. Then there is N such that for n > N, An TMalTys holds. Then for [0, TT, n, m N, we have
|xx,, (1) (x,((()] (2nn + Ma)) <c
Therefore we get the desired result.
Finally, we are ready to prove Proposition B.11, which implies the main theorem.
Proof of Proposition B. Take T 0. We know Xx, X,,, uniformly converges on [0, 7) by Lemma 1.14. Name the limit X, i.c. define X: [0, 7] + R as (t) = lim,->o Xx,, (t). Then as XA,, (0) = Xo for all n E N, we see X satisfies the initial condition. It remains to show X satisfies (6) almost everywhere.
Recall xAx,,) } is bounded in - ((0, T], R") by Lemma B.12. Thus can apply Lemma B.13, there is subsequence {Xxma } converges weakly to X in L' ((0, J], R"). Furtheremore we have E L ([0, TJ, Rt)) and so (Xx.,) also converges weakly to X in (10, 7), [) as well.
For À > 0, define fx: [o, T + R as
fa(t) = D (Xx(t) Xo) ift > 0 if 0.
0
Then for f: [0, + R" defined as f(t) 3/2 (X(t) Xo) for t > 0 and f(0) 0, we have lime fang (t) f(t). As [[x((t)] (t) + Ax.. (x)) s Ma (T) + (T( for E (0. 77 by Lemma B. we have
(1 S(0)) < (I)S((I)) + II((1)))2 < 4(M (T) + Ma(T))2
Therefore by dominated convergence theorem we have
(' [| (0) s(() 2 dt =
- lim
(0-(0)
[xnn (t) s(0) dt = 0,
lim 000
k
we conclude fxm, strongly converges to f in ((..
Now consider Fx [0, T] + R defined as
Fx = (t(+)= + (x,(t) - Xo)
ift 0
(Xo)
ift= 0
Note since XA are solution to ODE (19), we have
Fx(1) AA(()())
Then for F: [0 -+ [ defined as
(t) + ((((() Xo)
if 0 ift 0,
F())
-m(A(X)))
we see {Fx.,, JKEN converges weakly to F ( 71,R")
On the other hand, by Lemma 1.10 (iv) and the fact -Pxm (t) Axac (Xxmg (t)), we see
-Fxng (1) A(Ja, (Xxmm (1)))
Observe, from the definition of A and Lemma 12, we see
|| (t) JA.A (X,,, (t)) = X, | (XA, (f)) S MAT).
Since Xx,, converges to X in C((0, T). ), by taking - oo above inequality we see J (Xx,)) also converges X in
C((0, 7], ))
Now for A: L= R") + (10 R1,R") R") defined as (A(z))(1) A(x(t)) almost everywhere, by [11, Chapter 3.1,
Proposition 4]. A is maximal monotone since A is maximal monotone. Since - -Fxs weakly converges to F in L" R))
29

---

and JALA (Xx.) strongly converges in ([0, 71, R*). by [11, Chapter 3.1, Proposition 2] we have -F E A(X) in
([0, Ti, R*) Therefore for almost all t E (0, we have
(())) + to
(x(t) -Xo)) E (()
Reorganizing the result with respect to X, we have following is true for almost all t E (0,
X(t) -A( (x(0) Xo).
Since T > 0 was arbitrary, we conclude X satisfies above inclusion for almost all E (0).
C Proof of existence and uniquencess of the solution of (10)
As uniqueness comes from Theorem B. we only need to show the existence. What we need for the existence proof are
Nonincreasing function (() which contains X in Lemma B.5.
iii) Uniform boundedness of (t) for t E [0, as shown in Lemma B.6.
(iii) X (0) lim,- x Xo
lim X (t) as shown in the existence proof of Lipschitz case.
(iv) Uniform boundedness of x1( and (Xx())))) for L E [0,T] T) as shown Lemma B.12
We now show these steps can be also done to the {() = 2p
(i) Nonincreasing function (t) which contains {
From
X(1) = -A((((1))
2p
(x(1) - Xo)
e2pl
for almost all we have
(1))
d A(X(1)) + (
2
2ul
(x(()) Xx))
2/1
x()
dt
22p
-1
c2
Define
Ú(1)= = e 2n² |x(0||* +
211
|x(00) - Xo xoo²
e2pt -1
Therefore for almost all f > 0,
útt)= 2e 2e-2epp 2pt (t(,), x(t))
- 2qr -2N |>((e|]
-2ue
2p
- -
((=220
2/1
3
2caue [x(t) - -Xo ?
+ 2
But -1
cuut
-1
- 2e 2uc ( (x10) de
d
A(8(1))
cRut 1 (x(1).11) 8(1) - xx0) - -2-2210
24
2
2pc 24
|
+2
eRut -1
24c 2pt
|
+2
24
(x((). x(t) -xo) x(t))xx))
24
3
2ct
(x(t) xoll
capt
-1
e2pt
2ue -2ut
||x(()
2
2e
2al
(X().
d (A((01)
-
(x(1)
2ue
(x(1)
((1)-xX0 (x00)-xo) 1
dl
eue
e2ut
5 0.
30

---

(ii) Uniform boundedness of (6)
As (13), we define (t))) as the solution of
A(Xo(1) ह (Xol1) Xo) 05158
2y
{s(1) A(Xx(())
-znt (Xo(t) Xo) t2 8
Again with same arguments of Lemma B.6 we have [ - -xo|| 5 { E [0,7]
and | < <||á(xoo]|
Now for
| s | Vemū(1) Vemu(l)- = etl V
/ 225 [ts(o)]²= +
((
2
|1xs(0) -xo]
(52n -1
S Edul V @ | ((
2400
)²
?
|
e=H - 1)
S ex V2 A(xx)]|
(iii) (0)= = lim X1 lim (t)
Define C(f) := e 2ut Then Ö(t) = (t))((t) for B(t)
cave -1 And since
2u
lim C(tv) lim
e 2pto
1 c 21s f,,
6000 C(t)
6-0
with same argument done to arrive (15), we have
(0) = lim 1+
(t)
Xo
[ ((X(w))) O(I)
C(tu)
d== -1xxxxxx))
lim r0+
/
Now from ODE x(1) = (((((t))
2p - (X(1) Xo), by taking limit both sides by t - 0+ we have
lim x((1) = - A(}(0))
2pd
X(1)
Xo
1 - A(xo)
lim
+++
+-+0+ eatt -
t
2
Therefore, lim - lim (t).
(iv) Uniform boundedness of |x((1)| and ||Ax(1)] for / E [0,7]
Recall U(I) -2e |xaco)|
24 (xx(1)= Xoll² 2 is nonincreasing. So from (iii), we have
2ue |xx(cs|/== +
( cus
2 -) [1x2(() -1x0())))) - xol1² - lim (e-2e |
2/1
(
eZnt ( .) 2 [1xx(1)-
24
c 222
-xol?
+-0++
= = |x,(1))11 + 1 111xx(X))P== = 1 [AA(()))1
Therefore we have from Lemma 10 (iii)
2pa
|xx(t)]
|| s 2 |Axx) < II(((X)))
1
= |x,(t] S eaT
v2 |l
(21)
31

---

and by Young's inequality
:2 - (xx(11 Xoi l
2p
AAA(X)(0) < xa(1)+
| +
( E2ut
2/
_1) ||xa(t)= xool))
2
2
2
[|Ax(Xo)l+++
=(c2uT + (Xo)) S (62NT + +1))mm(((X)))1
Therefore
[Ax(XA(0) Ve2UT + [Im(A(X))]]
(22)
D Omitted proofs for derivation of anchor ODE (4)
D.1 Preparation for the proof of Theorem 2.1
We first provide the boundedness of trajectories as lemma. As mentioned in the discussion after Lemma 2.3, boundedness of trajectories is an immediate corollary of Lemma 2.3. However, to address cases that are slightly more generalized, we present a proof using an argument similar to the one used in the proof of Lemma 2.3. Note the proof argument of following lemma is valid for the solution of differential equation (11) with satisfying the assumptions in Theorem 7.1 as well.
Lemma D.1. (Boundedness of solutions) Suppose (-) is the solution of the differential inclusion (3). Then for all X, E ZerA, E [0, oo) following holds.
(t) - X.Il S Xo - -x.1.
And so, [Ix(() Xoll < 21 - X.Il-
Proof. It trivial for t 0. so we may assume >
Take X, E ZerA. By monotonicity of A and Young's ' inequality, we get the following inequality.
dt (x - x.12 = 2 (x()) x.) - (A(x())) + (() - Xo), X(t) - X.)
--((A(X(1)) + (()( x.) - 3(t) X.), X(1) XX.)
S -2((t) [I - x.1 + 28(t) (Xo- xx, -X,)
S -2((() [x 1000-x,, -x.1² + B(1) (1 - x.1 + (x(()= - xx.
--B(t) (I((() -x.1 ((t) 1|xo - xX.13.
Now again define C(1)= = eft ((e)do for some v > O, then we see C(I) = C())(()) Moving - (()) X,1 to the left hand side and multiplying both sides by C(I), we have
d di (C()) x.IP) C(t) d [x(t) - x. C(t))(() - x.11
di
< C())(()) |Xo - x.11² = d
C()) |X, -x112.
dt
Integrating both sides from >> to we have
C(t) ((x(() x_1 - -() - x.12 s C(1) (x - - 1 -x As 3 > 0, we have C' is nonnegative and nondecreasing, lim C(c) exists. Taking limit - 0+ both sides we have and
dividing both sides by C(t) we conclude
||((1) -(())xx11=2 < X0 - -
The latter statement holds directly from triangular inequality,
|| (t) Xoll < (tx(t) x.Il + |X - XXol s 2 -X,Il
32

---

Following lemma shows APPM is an instance of Halpern method. is immediate from induction, but state lemma due as its importance. Lemma D.2. Consider a method defined as
xkt1 JAY g = =(1 - Bk) (2x - 3²) + BBxT,
for k = 0, with initial condition 5² x. Then for reflected resolvent RA defined as RA 2J 1, above method is equivalent to
g = B&y + (1 -01--811 Bk) Ti²
when T Rr. 80 y Here equivalence means 5 = nrt holds for k: = 0,
Proof.
Proof by induction. As 77" = '10 by assumption, the statement true for Now suppose y² = 5² holds for N.
then
gh+l = (1 - 3x RAU + Boy = (1 - 3x) (2J - 1) 8z + B0g
-²) + Bou = yrt (1) (2J 1) Bov = (1 - 3xx) (2x 3²)
Thus g++l yh+ the statement is true for k + 1. By induction, we get the desired result.
D.2 Proof of Theorem 2.1
Let A: R" > R maximal monotone operator, and h, X, > 0. Again, denote A = Ara) = -I- Since various kind of terms appear in the proof, we first organize the terms and notations.
X Solution of differential inclusion,
1 [ - Xo). X -
Xx* : Solution differential equation,
1 (Xx Xo)- === -
Xx,5 Solution of approximated differential equation,
(t,((t== - (Xx.,)) - 1(xxo(t) - Xo)
0 5 s
(23)
(Xxx,ott (X)
- Xo)
t t2 8.
X x,a : Sequence obtained by taking Fuler discretization of ODE (23),
X X 22 + في (X - -Xo)
0 0 < 5
2h
x - (2 .) + ( - Xo)
k k 4
26
* b.A
Sequence obtained from APPM with operator hA,, i..
k-1 z JAA Vh.A
Vi lo + (2
s + k No-
1
Sequence obtained from APPM with operator /A, i.c.
1 Jnay --
V12 1:
(2
k k-1 )++ +
Xa-
k +
33

---

We want to show for fixed T O,
lim sup 1 x(2hk)] = 0.
h-
oskc z
Equivalently we may show for fixed O, for every nnnN such that hn > 0 and converges to 0,
lim sup n ogks 2hn
| - (2hx = O.
We will show this by considering inequality
- ((2hk)
|| _ (2 - Xx + [Xx(2hk) - (2.k(2
(24)
+ Xx,6 - X /1 + || z²11 + || - = =: ())
Our goal to show, for every {la)nEN such that In > 0 and converges to 0, there is a sequence {(ōn, An) such that 1 supoçk< = S (hn: An; 8n, k)) O, and thus
lim
sup
lohh. x(2h,
sup 2 o5k< 20.
lim
5 (hin Ans 8n k) = 0.
n-0
oSk< Ihe
To clarify our goal, we need to find proper ((6,, )n)) MeN in terms of (ha)neN- As (h, nEN is determined, || - k2), is fixed and doesn't change by the choice of {6 Aa) MEN But if we find {(5m. An) neN that makes S (hr An, 8n A) small, since (24) holds for any choice of ó, A, right choice of {(5m, An)) NEN can gaurantee || Th ((2h, is small. Thus to find such {(5,, An) in)inen
will observe each terms in S to find the required conditions.
Lemma D.3. For h, X, 8 > 0 following is true.
(i) (2kk) Xx (2hA)) O (V2)
(ii) [[Xx(2hk) (2h6al = (8)
(iii) b - 2x -(A).
For Ix,5 = max {2. x2 x² [|m(A(X)))l 1, 2/² Im(A(X)))]]
(iv) |XxS (2hk)) - x O (he2
Further more < 2/2
1xX x O (12Ta +3x (
(v)
0 22x O(h) +0 ( O
267
(0)).
Lx,5
We prove this lemma in next subsection, here we assume the lemma is true and prove Theorem 2. Suppose above lemma is true. The calculations are messy but the strategy is simple; balancing the speed of the terms h, 6, À going zero make above terms reach to zero. Above lemma motivate to take sequences as
hn
SMT
8, min
loga
1
V2 | (In(A(X)))Il 8n
27
A, = max
5n
M
log
where M max (m/ (A(x)))
When lim bnn O with hn >> we can easily check lim 8, and
lim An O. So the cases (i), (ii), (iii) go to zero.
34

---

Now observe from the definition of An we have,
22
[[]mm(((X))))))) on On 1
M
22 (mm(((((X)))) An
M
An 2 max
M
8n
An
8n
Thus
2LA,
Se
3
24
$3
(ons(
logs kn
1
Inea 8317
1
3 S km
S 3NTT
1/8
26n on
2M 8n
0 (6n).
Lindn
M
Therefore when lim hn - 0,
< 1/2/4 +0
1122 2T
112 e.
1/3/2
1 Du e 2hsnoon
(2T (2 T) 22ebban.on on
4I
T
<
0
2T
2T
3 hn
= 11718 + 0
2 nn
T
22 hn
3/4
3dm
km
<
+
0
An
An T
T
T
hn
Rn
3/4
An
1/2
km
2n
<
An
T
T. h2
An
3/2
3 Am
24 Ah T <
+0 0
An
T
3 8n S 3
(h.)
long (h.))
8n 81/2 0.
As lim hn = 0, without loss of generality we may assume hn < Since hn > we have A, is well-defined and satisfies the condition for Lemma D.3. Thus terms for the case (iv) and (v) go zero as well. Therefore we have lim supock T. 5 (hn, An, 8n, k) = 0, as {ha Mnnn is arbitrary, we get the desired result.
D.2.1 Proof for case (i), (ii), (iii), (iv) Lemma D.3
As case proof for (v) need lot of work, we provide it in a different subsection and here we provide the proofs for the cases from (i) to (iv).
(i) [2 - (2hk)) o (V))
This is result of Lemma B. 14. Considering (20) with p = 1, taking limit v
we know
sup 0.21
[X((t) - XtII V
XT
| (VA))
(ii) (2hk) - = (6) This is result of Proposition B.7. Consider (14) with y = p for Lemma B.6 and taking limit - 0. Then applying
Lemma B.10 (iii) we have
[|xx(t) - Xx,(0111 2V22 [|oxa (E(o.T]
< 2v20 ( (x)) (6)).
sup
35

---

(iii)
R - # - 0(2)
We first show show general fact about Yosida approximation and resolvent. From [15, Proposition 23.7 (iv) we have
(x) Jan, (x)]l=
Jnn(#)
1 I+1 (Ju=N)na-)) (w)
[na(#))
A 1+
1 I+x #
A 1+
1 X []n(()) (+)))a()))]
1| 1| Jaa(x)l
From [15, Proposition 23.31 (iii).. we have
(AA(T) J (+)A)A(()] S {A]TAA(()) =x1l.
Combining two facts we get
2\ [JA(()) - JNn S
1+ | J=a())|
From Lemma D.2, we know the iteration of y sequence in (5) is equivalent to below sequence
Xu h k+1
k+1 (2Jna I) (3*
Using this alternating form we have
h
R+1
x+1
(2JRA
1)(())) -(JJAa - ((
Uh
3h.2
k +
k
(1[2JAA 1)( - (2JRA) 1) + ||RAA (wh) Ruan (hh
k +
k
(21 (vh)) JAA, (v+i1] + 11 - whx
k +
k
4X
1lu/ -nna(hhil + l sriall
I
k + 1
11+ x
k
4X ||Xo xX11 + 11 whix))
k + 1
1+
k
The first inequality comes from triangular inequality. The second inequality is from nonexpansiveness of reflected
resolvent RA = A - I, [15, Corollary 23.11]. The third inequality is from the inequality shown previously. The last inequality comes from the convergence rate of APPM[35, Theorem 4.1), | Jnll Now multiplying both sides by le + and summing up from to k we get
[I.oo
4A
4
(k + 1)
X,
X.Il = + 1)
1Xo X.1I 1+ X
I+
Finally, from the relation between - and x* in APPM we have
k+1 h
A+1 K.
Jna (n k+1) - JAa, (2r
IAAN (o) 1 JRAN ( >/1
[una JnaN (2n [
vh k+1 1hit ||
+ 1 X
2X
|1 k+1 Una + I1I
41
21
1|xo - -xll
1+\ 11x0 - xx1l +
1+\ ++1
(2
1
21
11Xo =
h: k+ 1
1+ x
36

---

(iv)
|x,o (2hk) - - O (he2ls,,2)
From (23), consider Xx,5 of function F: R 00) R defined below
[XX Xo) < Axx (
-Ax(X)
F(X,1==
(25)
(X Xo)
t> 6.
Note F is 2 max { : J-iisschizz with respect to X.
For convenience name a - 2h. Define :- Xx,6 (ark) - Xx.5- By definition of Euler discretization and from fundamental theorem of calculus, we have the following
X = Xx + tFF(xx ak)
c((+))
Xx,o(a(k: + +1) = xx,s(akt+ +
Xx,((t)tt
at
= =Xyslak)+ + (a(ktz)
(X2,lak)) + S" Kxols)ds) dt
Xx,s(ak) + aF(Xxx((ak))))oo ak) + Jak fod Xa,(s) ds
(ack-))
From Lemma B.4 we have F(Xx,5, () = (() is Lipschitz continuous respect to I, so Xx.5 is defined almost everywhere and fundamental theorem of calculus is valid. Therefore we have
E = XA,o(a(k + +1) x,
falktt) fod Xx,(s) ds dt
=x,,((ak) x + (F(X),(ak) ak) - F ak)) + Jak
As F is 2max ) 3 Lipschittz with respect to first variable, we have
frrr (a(k-1))
fod [Xao(s)|
|e6+1l| S (xk((ak)) xt,oll + [F(xx((ak)) ak) ak)
ds dt
Jak
< 1 2a max { 2) |e&lll + (olktt) (olktt)) ( ds
|| |Xx,6| is bounded. By differentiating X2.5
Now we observe
Xx.5 dt A
1 ta
(XAS-XX) Xx,s dt
(
Ax(xs))+ 1 (-Ax(Xa,)-Xix)
1 Xx.s
for L 5, we have for almost every
(x +
05t<ō
Xx.5
Ax(X).)) (xx(XX))) - 28.. 128
Considering 7 = 1, 1 to Lemma B.6 and from Lemma B.10 (iv) we have
| (X,))x /2 [m()))))
and thus
= xxx((1)+ max {ō,t) (xx,(1)= Xo)
< [Xxo(t)| max 18, 1 [xxx(()) - Xoll
< Xxa(1)|| + max {8,1] L'' | do S mm)
37

---

And since A is x -Lipscchit,, we know A X2o is 1t22 ( thus we have for almost all 8,
d Aa(XXx((1))
A
Applying these facts we have
| = dt
d (x(Xss((t)
(Xxx
{
22 (m(
4v2
4V2 V2 (2|mm(A(X)))
|Im(((Xal1]
Ilm(A(X))]I] S max
A
8
A
Therefore
{
1 1))
||<x|] |l max V2 (2]lm(((Xo)))
4v2
oz a²
|ec+all
1 2a max
(26)
8
Now for L8,A = max
xx
{1 (l
8,
1 4y² [l((A())))l we show
||xll S 202
Multiplying (1 + 20L2,,8) -k++) ((++)) to (26) have
(1 + 22L2,5) () (k+11 |ea+all 11 S (1 + 22L22,6 ||alll + (1+ + 2abxo) -(++l) Lxssa
As ||ool| = 1|x - x(0]]| 0, summing up from to we have
(1 + 2aLx,)) ||ca|| v
(1+ + 2aLx,,) - L2,5a²
i=1
(1 + 20 20 -1 (1- 11-(1-) 20lA,
L2,5a²
1- (111221
+ 22L2,)) **) a.
Multiplying (1 + 20 to both sides and applying 2h we have
|kal|| S (1 2als,s)* -1) h (11 4hL,,,) -11)
(27)
Now from
(1+ 114h))a)* < (11 4hh2,,) mutoo AhLr,s
applying < 27
|ea||| S h (ethhins - -1) S 2
Therefore
|xxs (2hk) Xh,ol < 2Ts = O (he (11.77..
(28)
D.3 Proof for case (v) of Lemma D.3
As APPM has coefficient 141, we consider x+1 2,5 have
instead X5 due to calculation simplicity. From triangular inequality, we
|| 1x) - ot||
x
x 2,8
- xx
+
38

---

We will show
xx.5 - xx,,1 = (1)) + +0 (1.
| x 3x (o (0(2²
h
+ + h ( +O())
((h) + 0 122 ( O
+ 0(0)
x
L,,6
First one is simple. Since k+t we have
X + 222 2hk) and F is 2 max { 1// J-Lipschitz with respect to the first variable,
x
XX,,5|
2h F| 2hk)
- 2h || (2h)s(2hh))))) 2hAi + 2h (22,, 2hk)) - F(X 2h1
_ 2h Xx || + 4h max {
1
{ x 8 ((xx)(2h))) - x3:1ll
$ 2h |m())(X))] + 4h2 Lx.se 212.07
0 (h) O (122,,,
Second one is complicated, we present our proof with dividing steps to subsections.
D.3.1 Recursive inequality for ea = =|| x =//,a
Define 6 = x - / Recall, Xx,8 was solution of approximated ODE
AX(x,,) (x(() XXo) 0 xx)(1)== F(Xx,,) - -A(,),)) - (X((t - Xo) 2
We now wish to write 1x+1 in terms of Ek. As E6+1 involves k+22 we first write it explicitly. 2,5
x
Xx
+ 1)) 2hF xxx,0 2h(k+
x
2 Xoo) (2hAa(X
0 + 1 Am
xk+1 (2hAx(X + 2,0
(X)+1)
Xo)
k+1 i/4
Now we find recursive inequality considering cases.
(i) + & Recall APPM (5) was defined as
26
kh,A JAAN k-1 Vi
1o (2
d
v + 1e
1
No:
and substituting V 2/,, + hax(x ). we get one line expression
k+1 k h
k Th h (Ai(E)t))+ + 1 Al(ehin))
1
+
Xo.
k
Rewriting k+ to make easier to compare with above,
x
k + 1 x - h (AI +
k
k k Ax(x)t() h A *+1 A
+ *
1
Xo
2,8
+ h (Ax(x)tt) - An(x(t))) (x(xx()))-(((((()))
39

---

As AĄ is -Liisschitz
k
+ h
+ k+1 cx (x)
k
)
+ h
x - xx55 + h
- ||
cb+1 S
cx
ctt1
k+1
A
x
Organizing,
1
k
( 1 x1
h
x
k k+i A
Ex+1
h
k+1
E + /
2,8 -
(ii k+1< 6 2h Rewriting X we have
xk+1 h (Ai(x)t))+ + k+1 1 A
+
Xo
k ++1
k ++1
+ h (Ax(X - A k+ 1+1 +
2h 5
(x -
-oo)
k+I
The only difference between the case (i) is the last term. Therefore with same calculation, we get below inequality.
c++1 I 1
1 k
b X
k+ ++1
h x x
1
cx + h ( x
2,5
x
1: + 1
1
+
k+1
1
2h
5
|
Xu
From case (i) and (ii), by defining
x x
x -
Ax
} (x
+ K 2
Xoll
0 4
+ K+I
ek=
h
X,8
x+1
k+
2h
5
write recursive inequality for all k as below
1
h:
(1+ h
ex + exx)
Æk-
x
k++1
D.3.2 supocis + &
3 (0 + t0 (4622 + O(h) + O
2ff ( (2es) +0
2022.16
+ +8))
Ixx,6
k+1
We will now sum up above inequality. Multiplying (k + 1)
both sides we have
1+
4
k
(1- 4) 1+1
1++1)c+11 v
kep +
(k + 1)ek-
1+
1
(1 1)*
By summing up above inequality from 0 to k: - 1, we have
b i+1
1 KEE
x (i+ 1)e,
1 +
(1 (1+
1=
Note eo vanished as it is multiplied with Reorganizing with respect e we have
4
(1- A i+1
Ek
(i + 1)e;
(1 ++))"*
0=0
Σ
(1 + 1)e;
Σ
(i+1)e 1)e
1=0
40

---

(1-$) (1+3)²
For second inequality follows from the fact 0 <
< 222 which implies 0
I and
<
Observe
f(x) = + is nondecreasing in x E (0, 1) since
H+ T-r
((0² - 1) log
1++t I-x
+ 2x
f()))
x² (x² - 1)
Therefore, from f (2) = we have
#x 1 (
ek s
(i+ 1)e,
3 1
Σ
i 1)ex
Now we show
E(+ (i+1)e: 1)e: = -0 O + (Noelnatt + O(hh)+ +0 h2 +0 + +0
(62b
L22,6
for 0 < T' < 00, k
I 2h
Name N₂- = min {k: ]m From the definition of e we have
Σ ii fi+1)ez
N + k
1 Σ
1)
( x | - x
- - |
Σ
(i +11
2h
x
xo
i+1
5
1=
+ - [ 11)
1 Σ
x
x
+
Xx
x
where inequality follows from the fact _ < for 0 S k: and +
z
2h for 0 No
Now let's observe each term. From Lemma 1.12 and Lemma D.1 we know
x1 s v (Xo)ll(X))Il S (V)))((((x)) (X)(I) S |XA) |[m(A(X))II 5lxx - Xoll 22 - X.Il-
Name M max (V2) [Xo xx.1).
(i) X -
First observe
h
Xx,s (2h(i + 2)) - -Xxs(2h(i+ +))II
xxs(O)d
k-1
2h(1-2)
| de - " (M(22)M s " TTM.
S
ΣΣΣ
22(++1)
1=0
41

---

Thus.
xxx - x2,0
Σ
[ X + 2))
1 2)) X2,,(22(i 1))1l+ + Xx,0(2h(i++ 1)) xxxt ()
1=0
h
k-1
TM > 2e22a,00
X
h
(T
Therefore
f
- o (() + +0 (402reee))
x
==0
(ii \ Ax
Since A is --Lisschitz continuous and from (28)
|
(1)A)(X),)) Ax(X2 + (2x
k
R + M) h (Mo2haat + M)
h
x
Therefore
Σ - + (H(eetntt)) (
(iii) k -
xxto Xu| for No min (k, 1.
First, observe
| - -xxo((111 = 1.80 Xx,(()ds s [|Ixtnoloo] ds I tM.
From (27)
|| |x xo/1 s 1x (2 + 1//|| + (Xxx(2h(i+11) Xoll
Sh 4hT22s) + 2h( + 1)M.
Now as i + 1 < N₂ min {hi
4 }. 12
N
1 N4-1
Σ
xxtt Xo ||
Σ h (1++hhAA6)*
1+1 +2(i+ + 1)
s k 1=0
1t (1 4hLs,s)
No-1 i 1
2hM
Σ
k
4hLx,5
k
1m0
2hN
KLA
28L
(22bAr)
28M O
+0(
T,X.8
TT,,8
42

---

From (i), (ii), (ii) have
k-1
+ L ((oeenser + +0(1) + @ ( + +0
1=+1)===
(0)
T22,5
1=
Therefore,
h +0
h +
(ffermett +O(l) + +0 (ffeesaat)
+0(0))
Ek 3
0
+0
La,5
D.4 Derivation of ODE (4) from EAG and FEG
D.4.1 Derivation from EAG
For L-Lipschitz continuous monotone operator A and stepsize h > 0, EAG-C [75] is defined as
+ (= =0) hA(=*)
k+
k
(= t =0) - h((=*+b))
+ 2
Dividing the second line by h and reorganizing have
k+1 zk -()
(3 -20
h
h(k + 2)
-A((tt)
(** =0) -(A(=*+))-A(C
hikk + 2)
Identify hk = 1, 11=*==x00 X(I), 00 -Xo. =s is converging sequence [76), it is bounded. Thus we see
|A( A(=*) s L
h+ 2*
T,
(2 =0)==)) + --))+nA(**)
h(k: + 2)
1
(X(1) -Xo) +A(X))) = =0())
Lh
+ 2h
Therefore taking limit h - 0+ we have
X(t) = - - - - Xo).
D.4.2 Derivation from FEG
For L-Lipschitz continuous monotone operator A and stepsize h > 0, FEG [42] is defined as
k (2k 20) k
z A+
*k
hA(aA)
++1
k+1
(2* - =0) 1=()=+t).
k
Dividing the second line by h and reorganizing we have
k+1 z
-A(x)tb)
1
(2+ 20)
h
1i(k + 1)
-A((z²)
- hilk + =0)= - -(A(=*+)) (A(=*+))-A(z))
43

---

Identify hk 2t x(t), 20 -o. As 2t is converging sequence [76], is bounded. Thus we see
A(( A(2*)
L
+ zt|
h
hk
=
h(k 1) (2 -20 +
1(kk 1) A(=*)
1
Lh
+ (X(t) -Xo) + A(X(())) 0 (h).
++ h
Therefore taking limit h 0+ we have
-(X()- - Xo).
E Proof of convergence analysis for monotone A
E.1 Extending Å [0, oo)
Lemma E.1. Suppose A is a maximal monotone operator. Let X be the solution for (3). Define as
S s= 5
(o) ((t)= E -((((0)) - (x) -x0())3(((((0)) - Xo) is true
Then as X is the solution for (3), we know [0, o0) is of measure zero.
Define A(X): - Rd as
- Xo)
(29)
and denote A(X(1) Á(X)(I) Assume for every T O, there is M > 0 such that for all E S [0,
A(X()))I S M.
Then A(X) can be extended t E (0) with satisfying following properties.
(i) A(X(t)) A(X(t)) for all t oo).
(ii) For t E [0, (S), there is a sequence (tx beeN such that t E S, lime t = t and A(X(ta) converges to Á(X(t)).
Proof. Take oo), and take a sequence (nnnne such that t, S and lim in = As converging sequence in is bounded, there is T > 0 such that f, E [0. For that T, we have ||)((())) & M by the assumption. As n + A(X(t,)) (t,.)) is bounded sequence, there is subsequence (tneker Jken such that k ((X(tn))) converges. Name the limit as lim, A(X( (t.,))) On the other hand, as X is continuous curve we have lime-+00 X (tmx)) = ((). Then since A is maximally monotone, from [15, Proposition 20.38] we have (X(t), u) E Gra Defining A(X(f)) as u, we get the desired result.
Corollary E.2. Let X be the solution for (6). Then A(X) defined as (29) has extension with properties stated in Lemma E.I.
Proof. First consider the case B() = 3. > 0, > 0. Take > 0. is enough to show there is M > such that for I E EESS(007
| S M.
Recall from Proposition B.1 for Yosida approximation Ax, we denoted X₂, as the solution of
X = =
tp (Xx - Xo),
and we have shown there is a sequence {nn (An)nEN such that XA, uniformly converges to X on T..
44

---

From Lemma B.12, we see for h *0
ftth [x((s) ds
1eth (T)ds
Xx + h) - Xx(t)
Maot (T);
h
h
thus
X(t + x((++h) h))
X()) -x)-(())
Xx + h) -xx(t)
lim X-+0+
S Mdoc(T).
h
h
Therefore for t E Sn [ xt) = -i X(t+R)-X(0)
holds, we conclude
X(t + h) - x()
| lim
S Maoc (T).
h
And also from Lemma B.12, for 1 E 7] we have
(Xa(t) Xx) xix(t) Ar(t)/ s s|xxatt)| + ||Ax (T)e(T) + MT(T), 8
therefore
(x(1) - xo) = lim
(xx(0) - x+0
Xo)l S Mane + Ma(T).
Gathering the result, for 1 E S n [0. we have
A(((t)) (t) + 7 (x(t) Xo) $ [X(0
2 || (x(t) XXo $ 2Ma (T) + MT)...
E.2 Proof of Proposition 3.2
We prove this theorem by deriving the energy with dilated coordinate W(t) = (())( Xx) and conservation law from [67]. Think of dilated coordinate (L)) ((()( Xo). As we're considering the case is Lipschitz continuous, the differentiall inclusion (3) becomes ODE
X(1= A(((()) (()(((() Xo).
Rewriting the ODE in terms of W, we have
(w(()) ((t)(()) = ((( 8(1) W(t) C(t)
C(t)
where tt) x
((t)
(()) + Xo. Organizing, we have
0 w((( (())))(((()))))
From Lemma B.4 we know Á(X(W, t)) is differentiable almost everywhere, by differentiating we obtain second order ODE which holds almost everywhere
W. C(0))AXXXXX()))) (C))) d ( di
W -()) + C(1) d dt A(X(W())
(30)
Now by taking inner product with W and integrating, get equality which was refered conservation law in [67]
E, = 2 w - f. |(0) [ ds f(((s)
c(s) ( ((((())), ds.
45

---

Since ((() - C(t) (x(1)+ (()((()))) - Xoo). we can rewrite the integrand in the last term as
c(s) ((s)
( d ds
A(x(s))) irss) ds = ds=
[ C(s) ( ( (()))))) ds +
d ( (de ((XX ds.
Note the purpose was obtain the first term, which is nonnegative due to monotonicity of A. Now taking integration by parts to the second term we have
1'' ( d A(X())). ds
(W)B))(1)) ds
((AXXWW.)),CC))))WW (( (00)))()++++0000)) W(+)+ (()(WW)))) ds
[ B(6) | do do (B(S)) - B()) (M(ss) ds 1o
- ((A(X(W).)),C(()))))))))) +
((AXX(W))))CCO))))))W))
$L B(6) | [ ds
+ +(()())+B()))
1 [= + B(6) 2
-
1
I (23(3)3(s+ + B(s) (s))
2
On the second equality, we used the fact (t) = -C(())(XX(M))) C() Note the fundamental theorem of calculus for (A(X(W,s)) (s)) is valid since (( s)) is Lipschitz continuous and ((s)) is continuously differ- entiable in (fo 1), so their inner product is absolutely continuous in (lo:4) 4.
Observe the integrand in the last term can be rewritten as
(z()))(s) + B(s)) [[] C(s)² (28()) + +((s) (Ix(s) - Xool d Now gathering the results, we conclude
ds (c()) [|X(s) Xool"
1 | [ B(s) | ds ds ((s)
(
E
ds
ds
C(1)
|A(X(())) (I)
[(D(0)++8() 1 2 [Iv()))]
2
+ +1' C(s)²
( dd ((((())) ) 2 - ds
|/44 (C())
d
[Ix(s) Xoll2 ds
ds
C(t)2
2 (IĀ(X(())I + +3((t (A(X(I)), ef
Xo) + (B(1)2 + +(()) |x(() -xol?)
+ 1' C(s)2 ( d ( ) ds - [ d (C(s))((s) ||x(s) -Xoll ds
)ds-
ds
ds
C(to)² (28(to) ((X((t))) -Xo) + (s(to)2 + k(to)) (X(tt) - -xol
2
Moving the constant terms to left hand side and naming E= = E₁ constant, we get the desired result.
E.3 Proof of Corollary 3.3
E.3.1 V nonincreasing when A is Lipshitz continuous monotone
We first check it is true for the case A is Lipschitz continuous. Then from Proposition 3.2 we can write V(I) as
d dA(X(s)), X()) ds
v(I) = E - t0 ds
C(s)2
46

---

with E in Proposition 3.2. As A is monotone, from (1) we know C(s)² ( (s)) 2 0 holds almost everywhere.
Therefore for h
/ d A(X(s)), ds 50
( + h) V()) -2 C(s)
ds
we see V is nonincreasing function. Therefore for all > 0, (1)) S &lim,-o+ V(c). remains to show the limit lim ((c) exists.
E.3.2
Calculation of V(0)- = -limm-o+ (t) for Lipshitz continuous monotone A
In this section, we calculate lim (t) when A Lipshitz continuous. Recall V was defined as
(()) 2 (IA(X(O))I + 2 (Á(X(I), - Xo) + +((()++ + [1x(1) xool²)
C(t2
t d
((s)
[I((s) Xoll ds.
ds
From now we denote V for the case lg = as VO.
We first check
8t p=1 (
C(I)
(31)
> 0 1.
Observing
7 ds = y logt t
?
ds
for 0 < p < 1
0
1- p
7 1-
ds
for 1,
8P
p
C(t) defined above agrees with the definition of Ctt) for each case. Note
[0 p21
lim C(t)
[1
0 0<p<l.
Now we will show
lim V²(1) = lim C(t)
ifp21
||A((())))
||((x))]1 2
(32)
t0
+-0 2
if <0<<<1
To do so, we first show for > 0
lim '' d (()))((s)) [Ix(s) Xoll2 ds oc. -+
ds
We first provide an elementary fact as a lemma.
Lemma E.3. Let f: (0, oo) IR is a continuous function. Suppose there is a 1, < l/ < co such that
lim sup [tt) <l.
+-
Then 1> 0, o. ([0,4,
47

---

Proof. Since lim sup f(s)s = L, there is E (0,t) such that
0<S<E
|5(s)s < 2/1.-
Then since < 1
J [[()] ds ! |5())8) _ ds S
2/11
2/4
2/1
ds
8
1-9
6 1-4 < 00.
J 89
9
J0
1
By the way f(t) is continuous on [e, M max) [f(s) exists. Therefore,
L. [f(s)dds= S. [f(s)]ds+ + /. lf(s)lds = 1-
2/1 c + M - c) 00.
Applying Lemma H.3, we will show for > 0
s2 d ds
(C()))((s)) ([).)))).))
(33)
Observe
d (C()))()))-(((()888) = -
(-2mn
p(1 ph7
32pt1
(34)
p 1
We first show lim, C(s) = 0 for all n > 0. Take n > 0. Then there is some E N such that k(p 1) n.
With change of variable u = and I. L''óópiial's rule we see
1 8
u
lim C(s)² --0
lim
up-I
nu n-1 lim
n
lim
u 2a+1-1 p
m=
k-1 (n mlp - 1))
lim
-- u-1 = 0.
fn-h(p-1)
2e 2 2
2
2n u eF 20000
(27)
(35)
And thus
s d
((s)
C(s) (- 2p
p(1 +11+10 p)7
lim ++0+
lim
1pp-1 (1 +
0.
ds
2
--0+
SP
By Lemma E.3, we conclude for $2 a
( (C())((1))
) ds < 00.
da
(ii) p = 1
Since ((s) S", we see
2 ((s))((s))
lim 8-0
-1--7
lim | 177777111000 1)521-3 s1-77 =1 7/r
lim s 0.
ds
2
++
2-0
Since 1 < 1, by Lemma E.3 we conclude Ho s² ds
(c()) ds < <0.
(ii) 0 < p < 1
et st
Since lim C(s) lim
1, we see
2 d ((s))((s) ds
lim sup +++
8
= sup C(s)2 -2pm?2 1-1 p(1 + p)>l = p(1 + p)7-
2
s+
Since p by Lemma E.3 conclude So 52
((o))
ds < oc.
48

---

Naming the bound in Corollary B.8 as M (T), we know for T
(
Xo
So
(u)
du
Jo
M(T)
MTT).
s
Therefore applying (33), for
T we have
L.' ds 2
((s)
(-) s2 d (C(O)S(())
ds S M(T) [x((s) xoll3
ds < co.
ds 2
Hence we know ()) is well defined and since lime- So de (Cta))((a) ||x(s) Xoll2 ds 0. we have
C(t)² (IA(X(())) + 23(() (A(X(t)), -xo) + (8(t)++
lim (t) lim t-+++ 2
+ +B(1)) |x((t) - -xol3)
Now we are ready to show the desired result.
p > 1
As know X(t) Xo and (t)(t) are bounded from Lemma D.1 and Corollary B.9. Therefore from (35) we have
0 = lim C(t) lim C(t) = lim C(t) (3(t) + B(t)) ++0+ 6-0
+00
therefore lim,-00 (t) 0.
(ii) p < 1
As
X(t) -60)-Xop Xa
& M(T) < 00 for < L.T, we see
+ limsup (()ppp(((33())) (Á(X(I)), x(1) - S sim ([00)(-~1|((((()))))) ||A(X())] M(T) = 1-0+
6-0+
lim sup C(t)² (B())² + B(t) [x(()= -xol² s <> sylmssup C(t)² (yt2-2p P) M(T)² O.
1+0+
6+0+
Therefore
C(1)
0 {
p =
lim (t) lim 2-0+
|((()))
| 2
60
if < p < 1.
From (i) and (ii) we get the desired conclusion
10 vO(1)
if 2
(0) lim t-
||((x))]|
if <
2
and therefore for general to 0,
to d C(s))B(s)
V(0) lim V(I) lim (1 1-+
||X(s) Xxo12
t-
ds
2
is well-defined.
E.3.3 ((t)= S lim Vs, (0) holds for /. E S and general maximal monotone A
Define S as defined in Lemma E.I. Take t E S, let T > t. Let {mn) be positive sequence X, that lim An = 0. Xx converges X uniformly on [o, 2] and Xx, converges weakly X in L²2 TT, R.). Recall existence of such sequence was gauranteed by Proposition B.
49

---

Recall we denoted X as the solution of the ODE (19). Denote VA V for the case A As.
C(t)²
(1(1) 2 (IAA(X)(0)))+
(1))0))+++++0)) 23()) (Ax (X)( Xx(1) - Xo) (8(1) 11x(10)- - Xoll²)
5. d (())))(())
[Ixx(()) Xoll² ds.
ds
Note equality X(1) A(((()) ((0((()) -X) holds since E S, therefore we have
- -xoli) ((t) = C(t) (|xx000] + -
- d ((s)) S. to ds 2
|| -xoll ds.
The goal of this section is to show
(t) < sup VA, (t) S lip VA, (0) lim VAn (0).
n-000
n-+00
11-000
(1) (tt) < lim supn-to Vx., (t) First observe, from Lemma B.12 we know
(s)s) - Xoll
So (x)s)
ds
So Mao (T)
Mdot
holds for S T. Thus from (33) we have
((s)){(s)
S 82 d ((s))B(s)
[|xx(s) [xxx1))Xxl1
ds 2
ds 2
Therefore applying dominated convergence theorem, we have for to E [0,
lim /'' d. (C(s))((s) (s) Xoll² ds f/d d 72000 ds 2
( ((s))((s))
|x((s) Xool2 ds.
(36)
ds
From elementary analysis, we can easily check lim supn-soc (an + bn) lim sup an + limm bn holds when limn-+oo 6n exists. Thus we have
lim sup VA, (1) V(t) C(t) sup =-+00
[limuup n
Therefore it suffices to show following lemma.
Lemma E.4. Suppose for T >> and sequence (Nn)nek new Xx,, converges to X uniformly on [0, T] and Xx, converges
weakly X in L ([0, 71, RT). Lert E S [0, TT. Then following inequality is true
|x(T)|
|ix. (6)l
lim sup n. n=
Proof.
(i)
{() < limsup,-422 |xx, (s) holds for almost every 8 E [0.
Let D be measurable subset D C []. Since Xx.. - X in ( 71, R") and Xn [² T1, R"), we have
S |x(0s]|ppp
ds= ds=
ds= = lim /' (Xi (s), (6),)(())(() ds n00
/ (xS.. (()))) ds S lim lim / |IAA. ||>||| ds.
lim =limsup
n-
no0
The inequality comes from the Cauchy- -chwarr inequality. Now from Reverse Fatou's Lemma we have
lim limsup
/
|| | (s)
(s) ds < / lim [iA.
X(s) ds.
n n
n n
50

---

Therefore combining two inequalities we have
J lim sup 1=2000
Xxn (s)
-||||||||s|]
|
{}(s)
ds
As D was arbitrary measurable subset of [0, 7]. we conclude for almost every E [0, 7]
(limuup 7-000
1xx, (5) - { (((s) 20 =
{(s)
S lim sup
Xx, (8)
n-+00
i | < simmsupm-so X (t) for & E S S [0,
Let E [J. Then for > such that t h < T, since is measure zero, from (i) we have
hh ((s) ds S
1+h
lim sup
Xxx (s)
n
Now, for some consider
U2, (s)
Xxx (s)
1|| +
sP+I |xxx (s) -xoll f
7P
>pp xp(1-p) - p)
|| Xoll du.
up-2
=fa(s)
Then from the proof Lemma B.5, know
(x) -2
Xx, (6), -2(xxxx)
Ax,
27 X2, (8) ((x, Xo) 5o
holds for almost every s, thus Ux,, is nonincreasing. By the way, as Xx,, converges to X uniformly on (0, using dominated convergence theorem have pp(1 p) wP+2 [X(uu) Xoll du.
CP sP+1
Xoll f.
lim fn(s) R +00
Denote ((s) = limm [n(s).
Using above facts, for [1,4 + hi]
have
lim sup Xx, (8)
lim v Ux (8) - (n(s)
limsup n-+o0
VU,, (1) - [n) =
lim sup Ux, f(8). n-000
(37)
Therefore,
[X + h) - X(t)Il & S.
rth {{(}
1+h
1+h
ds <
lim sup
(s) ds <
lim (t) - f(s)ds. n-000
10000
Note / /Timsup,-so Un,(1) ((8)
continuous function with respect to 8. Thus we have
1 bth Us. f(s)ds
lim
lim sup Ux., (t)- ftt)
h0 J, V n
n-100
lim n
X (1)
lim fn(t) - f(t) = lim |is. (1) n-c
n
Finally as f E S, (()
lim
X(++h) X(t)
exists. Therefore
b
|x(t||
||X(t + h) - X((Ill
lim h h-0
h
gtth
lim h- J
lim sup U2., (t) f(s)ds = lim sup n=000
Xx, (t)
n 2x0
we conclude the desired result.
51

---

(2) lim n Vr, (t) < lim su Vs, (0) As Ax., is Lipschitz continuous, from Appendix E.3.1 we know Va., is nonincreasing, and thus
Va., (t) - lim (e) = VA. (0). -0+
Taking limsup both sides we get the desired result.
(3) lim sup,, o0 Vx,, (0) = lim VAn (0) From (32) and (ii) of Lemma 80, we know
if 1
lim V2, (0) 2-000
if < <<<<1. 1.
And applying (36) we have
V2, (0) %
f d (C()PB(5) |x((s) Xoll ds.
lim Vx. (0) lim
nI 11000
n-
ds 2
As the limit nim VA, (0) exists, the limsup concides with the limit.
E.3.4 Proof for general maximal monotone A First, we show Vtt) < limm-+o VA, (0) holds for & [0, 00). Next, we show lim VA, (0) = limm V(t). Then we have
((t) < lim Vs, (0)
lim V(t) = V(0). +-0
n=000
which our desired result.
(i) vtt) < lim Vx,(0) holds for t E oo) n- Take t E [0, oc). We know the inequality is true when t E S. thus assume t & S. Then from Lemma E.I, we know there is a sequence {tx JREN such that tx E S, limg-soe t4 and A(X(ta)) converges to A(X(t). As t E S, (tx)) < lim VA. (0) holds. Since lima V(ta) = (t),, taking limit k - oo to the inequality we get the
desired result.
(ii) lim Vs,, (0) lim V(L) Take a sequence [KE] such that 4. > and limp-+o 4x = 0. wish to show lime V(ls) lim Vs, (0). -oll)-Xoll are bounded for all k E N. The t boundedness of ||A(X(()))) comes from Corollary E.2. And from Lemma B. we have
Note the arguments in Appendix E.3.2 are valid when [A(((+))] and
(tx) Xoll lim 2
[txx Xoll
Xx(s)
ds
lim X-00+
I Maoe(ta) S sup Mant
t
to
t
KEN
Therefore applying the arguments in Appendix E.3.2 we have
lim
(tx)
lim 10+ 2
C(tx)²
|
k-to
Thus remains to show the limit on the right hand side exists and is equal to lim V2, (0).
For p 2 we know +om C(t2)² 0, thus lim
C(ta)² [((()+)))
since AA(((t))) is bounded.
As +om Vo_ (0) = 0 from (32), we're done.
Now consider the case < p (i) we have
Suppose A(X(ta.) a convergent subsequence Á(X(tx)). First observe from
Im(A(X)))|
(t( < lim 1o. (0) n n00
2
From above inequality, recalling lim C(t ) 1 we have
lim A(X ((X(kx)))
|mm(A(X)))II
lim (tt)))
2
1000
52

---

By the way as tom (taaa) Xo and (tx()))) e (tx(),)), by closed graph theorem we have lim (tx()))) A(Xo). As of m(A(Xo)) is the element in A(Xp) with smallest norm, we have sim ((A)) m(A(Xo)). As all convergent subsequence converges to the same limit m(A(Xa)), we conclude limg- A(X(())) = m(A(Xo)).
Therefore
lim (t&)) 8-000
C(4a)² k4000
lim
|((X(()))
Imm(A(X)))
lim Vo. (0).
2
n
As l arbitrary positive sequence converges to we conclude lim V2, (0) -imm-o+ VO(1) (O Therefore
lim Vi, (0) = (0) - S/0 to d (()))B()) [|x(s) Xoll ds 22000
lim V(t). 6+0
ds
E.4 Proof of Lemma 3.4
Most of the proof is done in the main text. Recall (t) is defined as 2(t) = ||x((())]I* + (A(x(t)). - -Xo), and from (8) we have
1 ((1 2 2 ||A(((0)) -28(1) | X,112.
On the other hand,
(1) C(t)²
(t) = (B(1)² + b(t) (x((t) Xoll²
C(t) J''
4 C(O))(())
||x(s) - -xoll ds.
to ds 2
Note C(t) j Of > 0, we can divide with C(1)². Now from Corollary 3.3 we have we have V(I) 2 V(0) for 1 0, and V(I) V(0)
2 0. Thus for t >
C(t) c(1)2
2V
(B())² +1002+/,00) B(t)) [x((t) - Xol1² +
C(t)2 S
2 d [(s))B(s) |x(ss Xoll ds
C(t)
ds 2
(V)
((V())
((t)
C(t)
C(())
(0)
(V)()
+ +(1) > (1)) 2 1 | 23(1) -2800)/)-2 x.
C(I)
C(1)²
Moving 28(()² |o
x.Il² to the left hand side and multiplying with we get the desired result
x111+ 4V(0) 2 (8(1)+ B(t) [Ix Xoo12 |A((())) S 18(1)211X
C(t)2
+ 2
C(t)2 '"' d (C()))())) (1x(s) - Xol1² ds.
ds
E.5 Proof of Theorem 3.1
Restating Lemma 3.4, we know for & > 0,
|A((())) < 48())² 1 -x,11 2V(0)
2 (B(1) + +B())) ||x(t) Xoll C(1)2
(7)
2
'.' d (C())B(6)) (Ix(s) Xo11 ds.
+ c(122
ds
53

---

As we know [t) - -Xol 2 x.Il from Lemma D.I, it is clear that
43(1)² || - x. -x, - O (3(0))
2V - O c(t)2
(38)
C(t)²
2 (B()) + 3(t)) [IX(t) Xull = O (B())) + o (i()))
Therefore it remains to show
d c(t) I-e ds (C()) |Ix(s) Xoll ds ds= (3(())) -
c(t22 (0(0)) +0 (8(t).
We can check there T > O such that for 8 > T the sign of d (c(s)) does not change, for (()) = - with y > O. de
p O. We first proceed our proof with assuming this condition. The point for this condition is that following equality holds for
t> <>> T.
S." d (C()) ds = ["] ds
(C(o)B(O)) ds.
ds Applying above equality and using [|X(t)) - Xool 2 | X. /l. we see
2
["
(cs)) ||x(s) - Xoll2 ds
C(t)
1o ds
<
2
T
d
(()) [x(()) Xoll ds
''' C(1)2
2
d
(C())B())) [x(ss) xxol2
ds
C(t)2
ds
ds
2M
2
/" d (C()) 4 1o X.1|
< C(1)2
ds
C(1)2 T ds
2M
8 11 1.1 ((())3(()- -C(1))3(2)
C(t)2
C(1)2
2
M ||x X C(T) ((())) +81 x,16 =0 =0(1) ) + +0 (B(1))
$ C(t)2
Therefore from (7) and (38), we conclude
0 (3(1)) +0
1 (
+ +0 (B(1))
It remains to show there is T 0 such that for s T the sign of de (C()))((s) does not change. It can be shown by easy,
but little complicated calculations. Since Č(I) = ((t) we see d (C()) = ( (2)3)))))) + B(s))
(28())3(s)
Therefore it is enough to check the sign of 28 + (ss). Observe
2py2
p)1+p)7
r(1 7)
ifp= =
23(s)B(s) + B(s)
12p+1
sP+2
p(p+11y
27 p+1
p +
sAp+1
Thus when p 1, for all > it is nonpositive if 2 and nonnegative if <<<<<<1 1
When p * 1, we see
foo
if < < 1 if > 1 ,
i00<p< 0
lim ++
lim 8
o
x
if > 1
Therefore by intermediate value theorem there is 7 > 0 such that 7P-1
27 = 0, and for that we have sP-1 p+1
2y is
p+1
nonpositive for s > O < x < and nonnegative for s > Ti > 1. This concludes the proof.
54

---

E.5.1 Proof for the convergence rate in Table 1
Recall, from (31) have
p=1 Te p> 0>0,p$1.
C(()
We now observe (t)) does not effect convergence rate. In other words, show B(t) is not the slowest one that goes zero compared to {())² and लßスz for every case.
(i) 0 <<p < 1
Comparing B(1) 2FFT with B(1)² 2²
see B(1) O (B(1))) when xps1.
(ii) p > 1
1 For > 1, we see 1im c(1)² = = 0. As lim ((t) = lim p--1 = 0, we have (()) = O (clo²)
From (i) and (ii), conclude
| o (8(0))) +0 (cleg)
Now the results in Table is straightfoward.
p 1 When p = 1, we have C(t) 17, Comparing
1 = ア. and B(1) 7
c(t)
(1) || 0 (B(t)? 0 ( if
(2) ||A(X()))| = o (ott)) O (#+ if0 <<09
0< < < 1
When p 1, we have
1
t²
lim 3(1)2 C(I2
lim
0.
722
Therefore, ((00)) (
p >>> 1
1 = 1 a 0 when p > 1. Therefore ||(((())] = o (abrz) ( We observed previously that lim; c(t)
E.6 Proof of Theorem 3.5
Name
X, ITzer (Xo) = arggmin - -Xol-
zEZeIA
We first show
lim sup (X(()) X., Xo -X.) 5. t+0
Proof by contradiction. Suppose not.
Then there e such that for every is E N, there is n& [0, 20) such that
(X(mx) X. X.) >E
By the way, from Lemma I we know ((nx) E 11xo-xx11 (X.). Thus by Golzano-Weierster theorem, there is a converging subseqeunce (X (pe)) he(v). Name the limit as X Since lim ||A((()))|| = 0, (A(X(Ma)))ENN)) converges to 0. Then from [15, Proposition 20.38), (Xoe, 0) E Gra A, i.e. Xoo E ZerA.
55

---

On the other hand, as maximal monotone, by [15, Proposition 23.39] Zer i closed and convex. Since X. llzer A (Xo). by [15, Theorem 3.16] we have (Xxo Xo X.) 0. Thus
0 <<6 lim (x (mw()) X,, Xo X.) (Xx0 X., Xo x.) 50 0, 10000
this is a contradiction, therefore we get the desired result.
Now we show oo X( x.| O. Recall, for 0
X E -((((t)) - (X - Xoo)
From C(I) = (())(()) and monotonicity of A, we observe
d
dt (c(t)*|((()) -x.1') 20(1)² (x(1), X.) + 20()) |x(t)) X+1
(C())(-A(X(I)) (()( - Xo), (o)) X.) + =2((1)2((1) (((t) -x, 1
s -2((t) 3(t) (x(t) - X(t) -X.) ( ((t) (|x(()) - x.
-2((1)((1) (Xo - -(), - -X.)-
Now take e. From lim sup (X(1) X., x.) S 0, there is M > 0 such that
t> M
(Xo X., X(t x.) <e
For that and & > M, integrating from to t we get
-x.1I'c(AM))) (c(s)*|(((5)) - x.11" = C(1) [ - - C(M))* (X(M) - X.11
/ ((3)))B(8)( X(,)(s) -x.) ds
<
|2C(s)² (X, X,, x(s)) x.)
2(ss) = e (c(s)]] = (C(t) - C(M)).
M
By dividing C()) and organizing,
)) + (CUM) ||X(M)) -x.112
((MM)
[x(t) - x.112 <e
1 -
C(t)
By the way from assumption, we have lim (()) = 0. Therefore we conclude
lim |x(()) x.11² Se.
Since > 0 was arbitrary, we get the desired result.
F Proof for worst case examples
The explicit solution for linear A is crucially used in worst case examples. Therefore, first provide proof for it.
F.1
Proof for explicit solution for linear A
F.1.1 Proof of Lemma 4.1
Observing
(1) = Σ (-LA)"
M(n + T(T + 1)x, = Xo + Σ (-LA)"
T(r + 1)x,,
[(n + t +1] +1
n=0
==1
56

---

we can check (0) Xo. Now by using the property of Gamma function [' 1) xI(xx. and paying attention to the lower bound of the summation index we have
(-nA)(-LA)-+ T(7 1)Xo
(-n + 7-)
x(1)= Σ
T(> + 1)Xo
n=1 +
T(n +(
(-tA)=-1
(-t)n-1A" nr
=
T 1)X0 +
I( + 1)
+2)+
T(n x+ 1)
(-tA)"
7
(-t)a A"
I( + 1)Xo = AX((t) 2 (x(1) Xo).
- n=0
[(7 1) +
l'nn +7++)
(-t) n=1
I'n + + 1)
The solution can be written in another form
(1) = =e ye
u u0- eu du Xo-
(39)
As this is special case of (9), here we just briefly check this satisfies the ODE and check other details in the proof of Lemma 4.2. By product rule of differentiation.
x = - 7 S/¹ "² tu- du Xo
( (1))) S'" wu- du Xo ne 1e- d
dt (f) ui-icus du Xo
+9 ye
A(X(I) 2 (() + t 11 (12-le1A) Xo
A(X(t)) (x(t) -Xu).
F.1.2
Proof of Lemma 4.2
Define
x.(t)= (I- A-AA-L (1-A0-AA(( (s. (f(CtC(e)))))
Xo- We show X, is a well-defined solution for (3) with linear A, then show X. is equal to X(t) defined in (9).
C(t)
We first check well-definedness. By definition,, C(t) = eho ((e)de is nondecreasing. Also, |et||| is also nondecreasing since from monotonicity of A we have for all E R
d
x 2 (A(ee e)) 2
dt
Now we see X(t) is well-defined since
C(T) (L CC())ss
||
/// ((--() C(s)
LA
ds
C(I)
(6 ()
C(s)
ds S L (1-1)ds
C(t)
Also above inequality implies second term reaches to zero + 0+, we have lim Xx( Xo- Thus defining (0) = Xo if necessary, we see X, satisfies the initial condition with X. E C(10, co), R*).
We then check (!( becomes the solution. This is immediate from product rule for differentiation. Since di c
c (t))((t) = c(1) (t), we have
x²(1) {d
d -ea
C(I) ( (C())ss Xo
dt C(t)) ) (f, (MC(ss)ss) Xo
d
Ae -AA
-A 1
C(t) dt (1," **AC(s)ds) Xo
=x)(X(() - Xo) -(()(xx(1)) - Xx) - A(Xo) = =-A(X(0) 8(0(X.()) - Xo).
57

---

Finally we now show ((t (t), where (t) defined as (9). From integral by parts we have
(() = e -t C(t) (Lo (())))())) Xo
= L4 1
(1*MC(+)) - L. ((sdd Xo
((t)
(1 1 Ae-
A1-Ae-
[(I) (1. e*((s))s) Xo x.(1)
F.2 Proof of Theorem 4.3
(-) :). we have (t) e- so
If (t) 0, for A
lim 11000
|A((())]I = + O.
So let's consider the case 3 is not ((t) = and ((t) 2 0. For
0 1)
A = 2
-1 0
name the solution for ODE X = (x(e)) - B(0)(xx - Xoo as Xg. By Lemma 4.2 we have
Xe(1) etAs
C(I) (1/ ( (ss)
Xo.
We want to show,
38 E R.
lim
|| ( (t)) #0 0
t1000
|| |
From lim, लोे # 0, we see lim,
* 0. And since Ag is invertible except the case & 0, have
lim (x))) =0
lim 10
||((tt]]= =0
lim
((s) + +C0)) =
Now let assume Ay R, lim;- |14g( = 0 and lead to contradiction. Define f IR - B2 as
f(8) = ((())(())
8 8>0
0
s $50. 0.
Then 1% f(s)ds [C(s) lim C(t) C(0) < 00 we have f L'' L'(R R)). Note lim C(t) exists, since is
nondecreasing and by the assumption is bounded.
cos 2m
sin 2m{s cos 2T{$
Now setting Xo 0) and from c
(-ssin
sin E
we see
J00 As ((s) Xo= Xo= (1,00 cos((Ts
/ sin(-2rs()(($dds
= (Re(f(E)) Im(f(())) T
where f(E) is Fourier transform of f. From assumption we have vg E R, I1 e (()3)())))))) 0. we have
(Re(f(E)) Im(f(E))) -
58

---

By the way, from Fourier theory we know f vanishes infinity thus
||C(
E-+00 [(() O.
lim
Therefore we have f(E) = for all ç E R. Now f = 0 clearly L (RR, R), we can apply Fourier inversion, and conclude f = 0 almost everywhere.
However, f(s) = (s) is not zero almost everywhere since (s) is not constantly zero. Thus contradiction, we get the desired result.
F.3 Proof of Theorem 4.4
F.3.1 Proof for the case p = 1, 2
Recall from (39), we know
(t) = -e -Ap S ceAgt-1 Xu-
Without loss of generality, we consider the case Xo = (1,0)².
Plugging y = 1 gives
x(1)
11 11 A 1 [(ead] Xo =
1 - -
(I (1-e-1)) (1, = - (,, sin i)"
sn
t
Therefore
lim [t)(((t))]I =
lim (+00 (1 - cost, -1stost, sin t) 1)7| + 0.
1-000
i y > We will show lim [ltA(XX()) (+))I = 7. With change of variable tu and integration by parts we have
(2) (A()(t)) - At (x-11) S(" c*Ag"~ ds Xo
= = eALA f'' endd endd Xo
(1)-ee 1)e ( sod 2 Xo
e aa
Xo - (7 -
= Xo (7 -)e -ta (L cos(loooo-2dd) ddv L' 20000 T
By the way, from 7 we have x--2 E (0, 1). by Riemann-Lebesgue lemma we have
cos(tu)o>> lim (' sin(to)u> 2-2 0. 1000
Observe as e -1 is rotation, we know
e -IA (L," cos(tu)o*~2dd L. sin(to)u dv )1 = II. cos(tu)u Lf sin(to)o)-2du)
Taking limit oo we know right hand side converges to zero, we conclude
lim -CA cA (L) cos(to))*~2 2- 2 f sin(tv)o = 0.
1000
Therefore.
lim e -t ( cos(lu)o)~22ds L' sin(to)o)~2 10000
lim [IA(((())] = 7Xo - -7(7 -1)--1
-1||Xool =7
59

---

F.3.2 Proof for the case p- 7
Since A, e are invertible,
1 e x(t)
lim e [IA(X # 0 + 1-200
lim E (()( # #0
lim t 1-300
#0.
000
Therefore is enough observe 47 Again for Xu (1.0)
)
- xx)(( = ( ex1gg-1 ds Xo
(So cos(8))) " ds J. sin(s)s7-11ds ds T
Since s"-1 decrease monotonically to zero, we may apply similar argument with alternative series test, Define an 11= sin(s)s dds and name S, Ek=1 Un- Then for m E N, L >> 2mm see
S2m z L. sin(s)s ds S S2m-1-
By the way S = lom Sn exists by alternative series test, thus we have
[ sin(s)s"-1dds 5
lim E
by squeeze theorem. Note S $2..2 S2 > O. With similar argument, we can conclude lim;-+oo So cos also exists.
Therefore we conclude lim (t)ll * 0 since
(T% cos(s)s L ssin(ss)-
lim
|(2X((I)
lim 7 t-+00
2 2
F.3.3 Proof for the case <<<1
Recall from (9), we have
X(I) C(I) ( ([= Xo.
e-t
Our goal is to show
lim 22 IA(X(()) #0.
We first observe, it is enough show
lim B(I)C()) 1 sis) +0. 0.
This follows from below facts.
(1) Since 3(t) = 7 #
and A is linear and invertible,
lim +00
SP ||A(X())) = lim 1000 B(t)²
(I #0
lim t1000 3(t)
x(1)
#0.
(2) Recall from (31), we have C(t)
+ for ((t) _. so C(0) = lim C(t) = 1 and lim 3(1)(()) = 0.
Thus lim (())(() [|C(0)]] = 0, second term is ignorable. Therefore the problem reduces to
-IA
( ((s))(s)) mAds) Xo #0.
lim
t-
3(t)C(t)
60

---

(3) Since e is linear and invertible, problem reduces
((s))) d Xo + 0.
lim
3(t)C(t)
(4) Again without loss of generality, let Xo (1,0)² Recalling e SA we see it sufficient to show
cos
sin 8) cos 8
focusing component
sin
lim 1 11000 B(t)C(t))
J C(s)B(s) sin ds + O.
Now we prove the statement. For convenience, name D(1) = ((t)C(t). We want to show
(8))
lim
s #
((t)
=S(1)
We first observe
D + 8) D(t + T)
lim sup 8E(0.6]
= 0.
To do so, we first show 1im
D(t+-5) D(E+*)
1 for 8 E [). Take ō E [0, Observe
0) B(t+o)C(t+
t +
e (++8))-
+ P
(10))
D) +
1 1+0
e ((+m)))
1
Considering L'ôspital's rule for the exponent, we see
1-p
x(p 1 1)
Liz -
b+ 140
lim (1+ 6)) t000
(1-(1+))
+
lim 1-000
lim
(1-5)-
lim
-
0.
1
(t + 1p-1
1000
(p - 1) (t - 8)0-
1
(1 + T)P
1. As the exponent reaches to zero, we conclude lim, 000 D(++m)
D(t++8)
Now from
D(t) = C(t) (3(0)= = - 10 7t -p--2-11
(yt - -pt").
we see (t) is nondecreasing for N
since 0 < < Therefore for (3) (7)x*
) we have supsejo.4
D(++0) D(l+x)
-
max {
D()) - 1/.
D(4+)
D(+=)
D(+++)
B1..
so it reaches to zero as t + Do.
Now we prove desired statement. Proof by contradiction. Suppose lim S(t) 0. Then for < <<<<< 2" there is T₁ > such that t > Ti implies |S(t) < c. Now for t. > T1, observe
2e > 15(1 + π) - S(() = J. D(s)
D(t + x) sin sis - 1r'
D(s) D(t)
sin s ds
1
S. D(s) sin ds +
1
D(1)) 1 D(s) s
1
D(1 + γ)
D(1 ()
((s)
sin ds - (1 D((
D(t) T)
D(s)
1)
sin ds
Dit + T)
D(t)
On the other hand, there is T2 such that t Th implies supse|o.<]
D(++8) D((+m)
1
$.j Now for t = 2nm > max(Ti, T2).
(2n+1)
D(s) sin s ds
D(1) D(t +
(2n+1)s
2c >
x (((()) >
(1- c) s) ds - = 2 - 2c.
D(t+T)
Jznr
2n0
This contradicts the fact < 1. we prove the assumption lime fo S(I) = 0 is not true. Therefore lim S(t) + 0.
61

---

G Proof of convergence analysis for discrete counterpart
G.1 Correspondence between discrete method in Theorem 5.1 and continuous model (6)
To check the correspondence of the method with (6), we provide informal derivation. Assume operator A is continuous. Then we have y² = x + Ax by substituting y² and yf the method can be equivalently written as
k+1 + Ark+l
kP
(a* Art)) + 7
kp + x
(40)
kP +7
This be considered special of below method, with / 1.
kP
h h--Pay
hA
(xk hA**)
ke + hhh-pp py
1P + h² -py
Dividing by h both sides and reorganizing, have
k+1 z²
hPPP
A+++1
Ar
(x+ - x0)
hP + boy
hPke + 11y
Identifying hik = t, x² (t) and taking h + O, we have
x()) = -
2 (X (X))
IP
As monotonicity is preserved for scalar multiple, rescaling 2A to A does not change the class operators that the ODE covers. For notation simplicity, replacing 2A to A we have
x() A(X(())
2 (X)
G.2 Proof of boundedness of ||>*|
While proving Theorem 5.1, we need upper bound for || Therefore we first prove following lemma. Lemma G.I. Let A be maximal monotone operator. Consider method
x² = =- g² (kk) (2x* xx + 3E00"
for 1,2...., with sequence {BaJEEN 0 S 3k S 1 and initial condition y" = x0 R".
holds
1|* x=11 5 =110=|1>0 2=11- -
for x² E ZerA. And so, | - z011
-o0-=o11 2 2/ =I
Proof. Recall from Lemma D.2, we know for
RR 2 given method equivalent to below method
k+z = 3xy0 + (1 - 8x) Ty
Note that x* E Zer A + E Ax + x- JAx + x= = Tz + x² E Fix T. We first prove ||y* x= s 11 - -z"1 by
induction. The statement is trivially true when k Now suppose the statement is true for it E N. Then
||0 k+1 2011 = || (y) x²) + (1 - Bx) (Ty² x')l
< 3x 1/3/ x² + (1 1 Bx) Ty 2+1
8x 1110 x= (1 3a) 11y* x*1
< 8x 11100 x" (1 - 3e) 1 x01
1110 x=
The first inequality is just triangular inequality, the second inequality comes from the fact xt Fix T and Tis nonexpansive, and the last inequality is from induction hypothesis. By induction, we have || x²
< 11 x= for t = 0, 1,
62

---

Define Az yh-1 - xh, then Ac Ax since JAn 1 xt. Observe for 1,2..... from monotone inequality we have
11 x²1 x11²= A + (ot - || + (Ao* , -x") + 1|0 - x² 112 2 | x² 1|²
Therefore we conclude
||a - x11 I |1 x² - 11000 - x11| =0 || - x111
The latter statement holds directly from triangular inequality,
| x S || x² +1+ +1100 x01 S | -x"1|
G.3 Proof of Theorem 5.1
The outline of the proofs originate from continuous proofs. To simplify calculations, instead of directly deriving discrete counterpart of Proposition 3.2, we consider rescaled conservation law for each cases. By considering dilated coordinate
W1 = X - Xo for > 1, W2 t" (X Xo) for 0 < p < 1, W3 = = - Xo) for 1, 7 2 1 and W4 = t (X - Xo)
for p- 1.0 1, we obtain below conservation laws.
F |A(((()) 2 + 27 (A(X(I)) X(1) -x) +
2 p2p
+
PP
[x -Xoll
#
10+1
+ (((
d A(X())) x(6) ds+ S/' SP (((s) + P (X(s)) - XXo 12 ds + 1
>p(p 1))
||x(s) - -xoll ds
2 2 Sp+2
ds
Es F |((((())| 2 + 2 (A(X(I),,X(I) -Xo) (0² - 7pt 1) )11x(1) -Xoll
+ 1'2000 28
A(( X(s) ds + 1 25 (1-pse-1) 1) |*{(s|| || ds + /' 1p(p - 1) 1)s0-211X(s)) - Xool'ds
ds
10
Es = t2 |((((()))|* + (A(((()))) - Xu) + 777 - 1) |X(t) -Xoll
I"d 20² ( d ds
A(x())), ds + 1' 28 - 10|x((0) || ds
to
((( E t2 |(((()))| + 2 (A(X(t)), X(t) - XXo) + +7 - 1)607 [(((t) - Xoll
d (()))))) ds + 1/' 27(7 -
25
Xool' ds.
do
Lyapunov style proof can be obtained by considering below functions
Ui(t) = | +
2Y (A(X(0). - Xx) + ( 72 {3p
+ YP
[Xx(t) - Xo11
EP
to+T
U2(t) = 2² [|A(X(()) 2 + (A(X(()), x(1) - Xo) + +,, - -ypt"- (1x((t - Xoll2
Uz(t) = &² ||A(((()) + 27 (A(())))) Xo) +~ (r- - (x) - 2xol?
Ua(t) = ( ||A(((())))) + ( X(t) - Xx)) + 7(> - 118772 ( (t) - Xoll2
The main blocks of the calculations corresponds to continuous cases, but there are some 'errors' in terms of Art and at 20 occur due to discretization. The proofs are done by showing these 'errors' don't 't effect to the conclusions.
(0) Preparation.
For all cases, we will consider functions of the form
= 0s A k 2 + by (Āx* x - x0) + ck 1|a 0012
(41)
63

---

and consider U U* As similar calculations will be repeated, we first organize the repeating calculations. That is, we prove following equality is true.
uktl U* + Av (Ax Axa
x kh-
-x²) - Th (Ar#tl Ar A
x 1-:t1xx7 x²))
(42)
ak+1 - d
kP +
||A
dE KP +7 - -ak) ||Axo11
k0
kp
+ bk+1 - A1
7
Tk - ck+1
k0 + γ
(Ar 12 - -00 + (Tk - Cx+1) (Azhtl xt - =20)
kP
kD
kD
+ (Tk - 11+1) (Aot, xhtl1_ - =20 +
A KP +
bx - Th - ck+1 kP + (Act ,2 - =20)
? | x 2011 1,,t1=x011- -c++1 kp +
||at =011 + (cx+1 - (x) |:0e - x 2012
- -c+1 10
Observe, this can be shown by checking below equalities are true. (Ax*+1_ Ar sk+1 x²))
(43)
KP +7 || 112 2
(Axet2 x - x00
KP
A 12
? (Ar x - 20)
kn
ko +
kP + 7
(Aaht1_ - Aot, sht 1 x
(44)
= (Aahth xkt1 =x²) + (Art xx x0) - ((Atttl x th - x0) + (Ar xx+z - x00)
Ck+1 1| - x 011 - ck 1|a - r012 1
(45)
kP +7 (Ax*t1 xxtt1 - x00 Ck+1 (Azthtt , =z0)
,
=ck+ k0
Ch+1 ( (Ax xb11 x00 Ck+1
KP + (Ax* xt =20)
7 |
=01 cx+1
7 1:0 - x011 + (cx+1 (x) 1|0 20112
Ck+1 1D
kp + ?
Proof for (43) Recall, the method was defined as
yh ke +
kP
(2x - - + kP +
7 z
x ++ JAy
By considering k+1 + Ar = y², substituting y² and y we can rewrite the method as
kt1 Artt1
AP +7 (a (a+- )r*)+ (o*=Aa=)+
7
+ kP +
(46)
By multiplying k + y to both sides and reorganizing we have,
(K" + 7) {(x*11 20) + Ax ++ $1 12 ((x -x²) -Ax* By subtracting both sides by (2 x0) and (k" + ()* L²)) respectively, above equation can be rewritten as
(A + (a - x²1)) = (k" + +z) + + - x²)) - Ck* + (A k+1 + (a++1- - x²1) = k2 Ao + 7z0 - x0))
From above, we get the following
(K" + 7)p (Āx
Ar A =z²)
(k. + T)p (An 1 .+1 - x²t) + (R: + 7) (Aat+1, Anty
- -(KP + TPt (Axt 1h11
1 - xx²) >- (k" + >) (An Art)
=-(k" + +7) {AA -k (Ax + h+ 2² })} + 1s (Ax* -(k" + (Aa +0Rt1 - x²11))
-(KP + +)) ()x k+1 (I. + An + ( x+1 2²) + 1. (, Ar +7(2" -2²))
-(PP + 7) ((KP + Am 1|2 + 7 AAx k+1 b+1 - 2²1) + k2 ( ,* - =x0))
64

---

Now dividing both sides by (kP + ?), we get the desired result.
Proof for (44)
This can be checked by just expanding the inner product of left hand side.
Proof for (45)
First, observe
Ck+1 ||af11 - 2011² - ck || x0112
Ck+11 (1122t1 - xx0 || - -112* - =011² + (cx+1 - cxx 1|2* - =011
Ck+1 (o rh, (1ltt - =²) + (at - x1") + (cx+1 (xx) 1|00 - x012
CK+1 ((abt1 - st nett I0) + (att1 x r - x0))) + (cx+1 - (x) 1| x 2012
Reorganizing (40), we get two different expressions for Jk+1 - xt.
x+ I² Ar
Aahh
7
(xt -20)
kP
kP + 7
x 1²
KP + 7 Ax
k+1 + Aat
7 (x =x
kp
Now plugging these to previous equality, be get the desired result.
Ck+1 |
001 c* 1|,
- x011
KP +7
Ax Ax*
,rtt1 ,0t x² kP + (x* -x0) x00) s0th 200)
2 (s (1tt1- -20)
-CCK+
kp
An
An +
7
+ (cx+1 - ck) 11a - 101
kP +
10 + Y
(A x - 20) Ck+1 (Aont)) ,0th - -x0)
=ck+1
KP
kt
(Ax k+1 x00) C1+1 10 + ( (Ave att - x0))
ch+1
11abtt1 - 2011 - ck+1 kp +
? 11 - 2012 + (cx+1 - cx) 1|5 z012
ck+1 10
(i) || Plugging
= 01) for p > 0,0,000
0% = 1 + 7
0y = 7
7kP
( 7 -
-(p-
(k + 1)p -1-1))
2k
km
Ck+1
4 (k2 + 3)
k2p
k0
A = 1 + 2
Ts = Cx+1
to (41) and (42), we obtain
Uk+1 - 1k +
1
7
ThP
(1
(I: + 1)p 1) (Ao x 20
2kp
4 (KP
+ +3)
1:2p
kP
7
(2kP +7)
||
7 (2k + 7)
|| A
+
2p
2
km
(k+ 1)p
2k (ke + 7)
y2
7
1
1
(A 1 =z
k2p
2
kP
(k + 1)p
722
7kP
kp (1+1)))) ))1))) (Ar x 100)
(ReP
+ 7)
2(k + +))
y2
(k+ + 1pp)
|
2012
2 (2kp +7)
k:2p
kp
65

---

7
))
| =20 + [cc+11 - cx) || - x
(Kp + +7) (2kP +7)
k2p
kp
(k + 1)
7 (2kp +7)
Ar
h2
1
1 11p) )) (2 x0)
2h220
2kp +7
91
2
kp
(A: - 1)p
7 7(ke +7)
An* +
1
k2
(A: + 130/ )) (a* 200)
7
2kp (KP +7)
2kp +Y
2
1 7
7
||A
2
(I: +)
7
22
+
k2p
1
1
2
| 11l---0 =x0
2 (2kg +7)
(A: + 1)p
kP
(k:
+ 1)
$1,1
7ko
22
1
+
2p
1
2
1
110 2012
2 (kP + 7) (2kP + +7)
(k + 1)P
KP
4
kp
(I: + 1)p
81.0
+ (c++1 - (+) 11s =011?
The continuous counterpart of above equality is
úi(t)+ + á (A(X()).X(1))
di
= - |(X(0)) (2 (x(1- - - 1)
1 1xp(p
[x(1)= - Xoll2
1D+2
which can be obtained by differentiating and reorganizing the conservation law for Ej. Note, as 2
(x+1)0
O (12P) 0 (
(x.-), the order of the term 24047 (7+
2 2
corresponds to (3r + f).
(++1)²
Thus we can see the sum of first two terms on the right hand side of the equality for discrete setting corresponds to the first term the right hand side of the equality for continuous setting.
We can observe that sk,1, $k,0 O (121F) O (pt22)
). And since c%
O
p
+
0
k
we have Ct+1 Cc are summable for > 0.
O
( + O kF+z
as well. Therefore the coefficients of ||att1 Il and
I|It
x
From Lemma G.I, we know ||a**1 - 1= and ||a* - -0 || are bounded by 4
1
x
The term (Az Ar x++1 - x²) on the left hand side nonnegative from monotonicity of A. and the coefficient
nonnegative as well. The coefficient of ||A 1|² in the right hand side, - [ [x+1]=/ ) is nonpositive. As a
result, we get below inequality.
1 r
U++1 < U*
||aAt1- =012² + (cx+1 cx) =x0
+
2
kp
(k+ 1)p
< U² + +2|122
x x012 Σ
20
7
7 ;11)) + 2cx+++ -ca) (ca+) = M.
10
(I: + 130
m=1
As done in (8), by monotonicity of A and Young's inequality
M z th ax | + by (Ax*, . x0) + ck - 10
2 .4 || A 112 + by (Ax* xx xx= x2) =0)
z 44 A. * $11² - 1 (1Ax 122 * 62 ||a + 1|=-==0011)) =0]1²)
= 2 (1+ 2) ||
1
+
72
|z* 2
2k2p

---

Reorganizing, we get the desired result
Ax* k
2
2
(1-2) -1
kp 1--)²² M + 72
| - x0112
2k2p
=
1 + kp - -
M +
72
1|=- =0113)
= (1).
2k
(ii) |A(z)]| O (FT) for 0 < 1,70, 0.
Plugging
ak+1 kp 1.0 + 2)
kPq2 Ck+1
bk+1 = yk?
4 (k2 + 3)
A = ak+1
Tk = ck+1
to (41) and (42) with p = 1, we obtain
Uk+11 - Uh + 1: hP + ?) 4 (ke + 2)
kPy2
(Autt) - Aut, whtt - -2th
y3
= WP + 2)) ||A ||2 7² At xbtl =20)
| 2012
4 (R: + 7)
kP (k* + 2)
(k: 1)a² (II= - 1)p + -)) | 1| + 7 (- 1)
11)ppp + h - 7(k: 1)))
+
(Ax* * xx - =20)
KP +7
kp +
7
73 (kp- (k: 15-11 1)P)
120h - =011 + 8 ((K 1)00 + }}}) (A:P + 3}
1 - x01
4 (Ap + +7) (AD + 7)
7 (1 - =29) || + gk Ax +
|²2
(b + 2))
M +
rk (s - x20)
2kp +
29k
733 (kpp - (K: - -))p
110 200112
+ 8 ((k- - 11p + 2) (1oP + 2)
4qk
4km + 7) (kP + z)
The continuous counterpart of this equality is
< d J. (A(X(0).x(1))
Ú2(t) + 2620 22:2
= -26 1) 2x(00))
(X(1) -
- 11pp--11 1) [[()) - -Xol1
which can be obtained by differentiating the conservation law for Ez. The first term on the right hand side correspond to the sum of first two terms in the right hand side of discrete equality. Thus we may expect the order of the coefficients for the terms would match, and we will check the expectation is indeed true.
With some calculation, we can observe
2 - 1)p ((k- ((k- 1)2 - kP)²
Sk
4 ((ks - ([1p-1)p+ + () (kv + () dk
+
where
du = 2k - 1)"d ((k- - 1)" + 7) - 3p - 2k.0 + 27 - 11)8 ((+ (l=-13 1)p + :2)
2
By considering Newton expansion and from 0- < p < 1, we see
dz = 2p + 2k + O (k30-1) - 21.30 - 2 + 27h22 + 0(k2)
= 2 + 0 (k3p- + O (k*) = 0 (1.20.
67

---

Thus we can check the leading order of numerator is p + (2p 2) 5p--2, 2, and leading order the denominator is ppppp- 2p 4p. As 5p - 4p p - 2, we have 8k E O (km-2), which matches with the continuous counterpart.
Therefore Σ 8k 00.
On the other hand, we see
k2P (AP + 3))
(k: 1)p ((k- 1)p 2)
9h
k0 +
pk. < 2. (k2 -kk-1 0 (kp-)) (IAP -oh" O ((k-))) + )
7 k2 +2pk 2p 21- O 2)
2
Since p > 2p 1, we have limg Qk = -c. Note this matches with the continuous counterpart as well.
Therefore there is > 0 such that for N. Il Now for N we have
Ukt1 S Un + sy 11 - x012 s UN + 4
Σ
|| - x²1
11=2= = M.
Sm
m=N
Thus for k > N, by monotonicity of A and Young's 's inequality
kpq2
rht1 M > Th+1 1.P R + 2) ?) | + thke (Aaht2 , - x0)
11 2012
(ks + 3)
2 10 18 + 2) | 112
+ yks (Aahtl x 04)
2 1P 1. + 2) A
k2
( R + 2 |
722
x - x 011
+ kp
2
1t (kP + 2)
kpq2
1| - 2.012
2
2k +
Reorganizing, we get the desired result.
| +21 <
M
7²
1x00
x² 2111)) = 0
(
KP (kp + 3)
2
k:20
(iii) |( ( for p 7 1.
Plugging
but1 = 7 (k k 1 (7 (7-1)) -1))
1
1
0k++ = k2
cK+1 c++1= 77 -1) 1)
A = k(k + 1);
= Cc+1
68

---

to (41) and (42), we obtain
Uk+i - + [kkk+ +1)
- 7 - -
-
- 1) (An Art, whtt - x4h
1:2 1 ||Aco11
= - -v - 1)(k (k + 1) 1|AA
k 7
777 1) (k: + 7))
(Ar , - x2) - 7(7 1) (N: - 77)
(Are 220
k
k + 7
22 - 1)
7/(7 - 1)
||
- =0012
| - x 2012
4k
4 (k 7)
2
= - (01-1) 1)(() +1)
|A +
7
(1+ ?
(I 200)
2(k: + 1)
4k
11)
|Ar**
+ 2 (1
2
(x* - -x0) ||
k+
2k
4k
77 117111 1)
8(7 -2) - 72
|| =10
70 1)
(8 (8- 1:
7
| - x0
64k(k+1 + 1)
k
64k(k + 7)
=0
84.0 (pte)
The continuous counterpart of above equality is
+2(1)+212 - (00) Xo)
21 -22
which can be obtained by differentiating the conservation law for Fz.. Note the terms match with same order of
coefficients, except two | - 10 and
|at x 2012 while these terms are summable as sk,1, $k.0 O ( kz)
Therefore we have
Uk++1 s Uh -sk,1 || - =012 5k,0 1106 - =011
S U 4 11000 x01 (sm,1 + sm, M.
Thus by monotonicity of A and Young's incquality
M Uk = 122
Az
1|
+ 7
k -
1 (7 -1) (Aa* , - =00) + 4 20 - 1) 1| =0012
1
2
= k22 1| +7
k:
2 (T 11) (Aitt - x00)
2 22
|
11?
1
h
( - 1) || +22 1|/00 1111==~-000 =201
2
2
22
2
22
1x-
2
2
Reorganizing, we get the desired result.
+ x2
x² x-1²²) = 0 ((z
A k
1|
M
1100
k
2
(iv) {( O (127 for p- 1,0 < 1.
Plugging
1 27-2
ax= = 1229
by = 7/
Ck+1 = 4 4//7 - 1
4
b = 1,211 (k- + +),
Tk = Ck+1
69

---

to (41) and (42) with p= = 1, we obtain
uh+l= -Uk + 2 (K: + 7) + 1
4 77(1 -2)6)-2) (Anlt) - -00, ktt - x²)
=((k + +)) (k ?) |A
=up
+
k + 7(k + 1)
3) 2x-2
(1s 7)
1 k k+t 1
4 1717 - 1)621-2)
(Acttl, satt1 =20)
4
k
=8k,1
+
Th 1 - 7h: k (x/)
1 27-2
(1 + t 7
11 - 1)62r-2
1
(Ār" =20
7 (7 1)622-3/ 11-1111111 ||,/h/11
100 2
1 11 1 1)6
1
1 x0 101
+ (r 1) (1:27-2 - (I: - 1)20 1|a
1
- 1012
The continuous counterpart of this equality is
(1(1) + 21 ((((()))x()) da - X
(x())
X,11²
dt
which can be obtained by differentiating the conservation law for Es. Thus we may expect the order of the matching terms are equal, and the terms do not occur the continuous version do not bother our desired conclusion. We check our expectation is true.
Terms || - 211 and ||a - 2 correspond to - xoll. The coefficients for || - =11 and
1z* - 001 2 are clearly O (k22-3), which equals the order of continuous counterpart. Since < 1, we know
these terms are summable.
Next we observe Qu < 0. Observe
(As + 1)
(k + 7)²
1
122
|+ k.
1
27
< 1 + T
7)
2
1 K
To check the last inequality true, consider f(xx = x², Since this function concave for 0 < < 1, we see
(1+1)==0 = (1+
( 1
s f(1) +
Finally we focus on 8k.0 and 84,1- As cross terms don't 't appear in continuous version, we may expect these terms are 'small', or in mathematical words, summable. From Cauchy-Schware inequality we know
(Ax I - z0) < Ar**1
k+1
|
x0
(Ax*, x. x0)
Ar
Since | and ||A,| are bounded from the proof for case (i), we know two innerproduct terms are bounded.
Thus if we show Σx= |sk.o] ; Ex= |sk,1| < co, we can conclude (Tk is bounded. Considering Newton expansion, we see
3
27-2
7k 1)
k +
- 2 +7)
4
-x22
+ 7
1 2 (7 - 1)) 122-2 +
3
+0 1 (1:2--3 - 27 - 222227
1
2/7 2
22 + 0 01127-3)
70

---

Therefore
1 Sk,1 27(7 - +0 - (2+ ))
1
With similar argument
8R.0 = - 1 - h
4 -
1 2y-2
=
-1+
k
4 17 - 1)621-2
1
k+
= - k22--2 - (27 - 2) 2,-3 + +0 (127-44 - -(2- ?
) 1
k k+, 77(7 1)621-2
4
1 27 - 1)12 + O (121-8) - 5766 1)62 + 0 (127)9)) = 0 01621-3)
2
Therefore, we have
Uh+1= s U* + sk,1 Ax |||| - 201
0 | || z"11
1 - 201 c
|r - =01 + (c++1 cx) ||=² =011
cR+1 k
1 7
(1sm,1l) || || r0 + |smmal ||ا || z01))
m=1
(mm+1 2 || 20112 (( (cmtt m. +
7
+lox+1 oal) 110 1 =0133) 109-
+
M1.
m
m=1
By Young's 's inequality
M₁ + 1 77(1 -))2?-
2
||0 - 2012 x22 (?*1|A=" 1|2 + 7k
1
27-2
(A x 200
-/
11 24-2
) k 1|2 + 7k k (x-1
(Ar , x - x00)
1 27-2
= = +
k , k
(x- -20")
4
2²
1 2y-2)
2 AA 1 7 b1 Ar x1 112
k1-y
|| - =2 201/2
2
= - (k>-1) and 7 < 1, this terms goes to zero as k - oc thus there is some M2 > 0 such that 2 (>hl-> (k: - -- 2) 2
Since ke- 1- (k: - 1-
1, - xz < M2 for all 2 1. Reorganizng terms, we obtain the desired result
|Aa S 1.9 M + M₂ + 7(1 - 2--2 1 - x =011²)= = O (
1 1:29
H Proof of convergence analysis for strongly monotone A
H.1 Proof of Proposition 6.1
We take dilated coordinate ((1) (()) Xo) as did in the proof of Proposition 3.2. Recall from (30), the second order version of the ODE was written as 0 = W. -3(1)W + =()) Now for we multiply R(()² in the ODE and obtain
0 = n(() ( - 3()) + C(1) d
C() (xx)) di
71

---

Now taking inner product with W and integrating we have
R(t)2
A(s)
R(s) [ (s)) 2 ds ["
B(s))(s)} |M(s)] ds
E = 2
R(s)²
[ C(s)((S)
((), ds. ds
Note the second term which is obtained from integration by parts, would not appear if R(t) 1 as in Proposition 3.2. This is key term to exploit the condition A is strongly monotone.
Now again with (tt) C(t) (x(t) + (()) Xoo). we rewrite the last term as
[ C(S)((S)
d ( A(X(())) (ir))) ds
ds
- -f'C())R (_)(((())))) ds ( ds.
Taking integration by parts to the second term we have
1/" de
d
ds -
=-
=- 1.2 -- ((X(WW))) ((s) + R(s)
R((s)
((s) + B(+)) CC177////W1++++000)333330006 ds
=I" B(s))(s)² [1rrs ds + L B(s) + 2 R(s) ((s) +B(s) R(s)² ((s)s R(s))
The fact (()))(((W,t) -t) is applied to the second equality. Note the fundamental theorem of calculus is valid since 3()) (s) is differentiable, A(X(W())) f)) is Lipschitz continuous in [to, t| by Lemma B.4, and so their inner product absolutely continuous in [fo, t).
Now consider the second integrand except the term marked with * From integration by parts we have + B(s)) 1'' (B()) + B(s) R(3) (W()), ds ((()))+(())) R(s)² 2 [[()))
- 1
(2356))(0)+ + B(s)) R(s)++ +())))(()) 28(0)R(S) |[ ds.
The integrand except marked term can be rewritten as
(2)())3())(()+ + B(6))(())))))) +3(s)) R(s) (IW
t0
1
L' ((s)
+5(())(ss)) ((s) Xoll ds
2 t
1 /' d (())))()))3)))))
[x(()) Xoll² ds.
2 ds
Now collecting the terms marked with #, we have
S R2s)²
R(s) [ ds + [
R(s)
R(s) RRS) ((s) (ir(s), ds I' ((s) (IW(s)
=-/- 1' R(s)2
R(s)
(V(s)) - -8())))))))) -()))(o]|'ds--- - MS)C(()) R(s)
R(s) [((5) ds.
R(s)
72

---

Collecting all results we have
R(1)2
| +
+ (0(S) + B(s) R(s)2 [[(())22
F1 =
2
+ [: ((S))
( d ds (((()))) ds I'd [((() R((s)
{{(s|| ds
R(s)
1
l d (CO)R(())())) [IX(s) Xoll2 ds
+
2
ds
C())R(()2
(IA(X(0)1* + +3((1) (((X()))X(1)) - -Xo) + (B(1)² + B(1)) (|x(1) - Xoll²)
2
C(S))R(s} (()AA )
R(s) {x(s)|² ds - f"' ds
1((x)
(()))
+
(x((s) - -xoll ds
2
to
C(to)2
(A((6)((((())) X(1o) - Xo) + (B(10)2 + +B((0) (x Xoll²)
2
constant
Renaming E = Ei constant, we get the desired result.
H.2 Proof of Theorem 6.2
H.2.1 Proof of the inequality (tt S (0)
The basic structure of the proof same as Appendix E.3. We do not repeat the whole proof here, instead we check the steps done in Appendix E.3 are also valid for the setup in Theorem 6.2.
(i) V is nonincreasing for Lipschitz continuous p-strongly monotone A. Recall V in Theorem 6.2 was defined as
(II)= (ettt
=2 | + 2p(1 2ut) (A(X()), - Xo) -2,2 (1 (1- -ue) [1X(1) - Xool²-
2
(47)
We first check following equality is true.
(it) = C(t))R(t)
(IA(X(0)) + 20(1) (A(X())) - XXo + (B(0)² + B(0)) [[x - -xol²) (48)
2
Recall we're considering (10),3()) = -..
2p
As d
log (1 - 2ul) = 2pe
- = 3(1), we have
2p
di
1-e-
C(t) = elc ca0a ds (oR(1-e 20t)
2P
2ut
As B(t)
4/² Ju²"e2w 2pe 11)
and R(t)= = eut
C(1)2 1 (1 (1-c c 22tt)
(eltt -e-ue²
c=2nt)2(2ue @ut
2
2
-21 ((1)) = c 241 (62t1) -1)²
2/ (1 c -20d)
-
C(t) (000)+B(0)) (Eut - cur
2pl
2uu
=2p² (e (6-2ut-1) - 1).
2
22ut
-1
(E2ut - -1)2
This proves the desired equality. Now we show
v(t) = E - 1. R(s) =
((_A(
R(s)
|x(6)|² ds,
(49)
R((s)
73

---

where E' is from Proposition 6.1 which was defined as
E R(t) (IĀ(X(U))* + (3((1) (Ā(X - -Xo) (8(0)= +(0) [x Xoll3) [((s) R(s) x(to|() ds /'d d (()))(())}(())) [Ix Xoll ds.
Lf R(s)) ((
ds
(clo)RRee} ds 2
From (48) and the definition of E, is enough to show
0. Since 44p (c2ut 1)2
(()) = (1 - 22u))² czrl
(~
-44
2
we see de ((o)) O.
Now since A is Lipschitz continuous, we know E is constant from Proposition 6.1. Therefore from (49), for t > 0, [b]] < & we have
C())R(()} (1 ds
((2x((()))
R(s) ds.
x(+o]
R(s)
As R(a) R(s) = 1 and is j-strooggly monotone, from (2) we see
) d x()))))
R(ss) R(s)
{(()) / 2 0.
ds
Therefore V(t + h) - V(t) 2 0 for h > 0, we get the desired result.
(ii) Calculation of (0) for Lipshitz continuous monotone Å Plugging t = 0 to (47) we immediately obtain V(0)= = O.
iiii) (tt) < 0 holds for all E [0, and general maximal p-strongly monotone A
We check the arguments in Appendix E.3.3 and Appendix E.3.4 are also valid here.
Define S as defined in Lemma 1. Take / E 5, let T > L. As checked in Appendix C, the arguments used in the proof 2μ
Proposition B. is also valid for the case ((t) = : This fact provides the required sequence (Xx, InE where Xx., converges to X uniformly on [0, 1]. and XA,, converges weakly X in ((), R"). As in Appendix E.3.3, denote VA as V for the solution with AA. Then from (i) we know Vx is nonincreasing for all n E N, we have lim sup Vx, (t) S lim supn-+oo Vx, (0) = -.
Moreover, we can check the extension of Á defined in Lemma E. is also valid. From (21) and (22), we e"T VI [Im(A(X))]] || and (Xx(t)) I VeZuT + 1 |lm))(X))] for all X > 0, E [O,T]. Therefore we can prove Corollary E.2 for the case ((t) 2 with the same proof, replacing MA by
know
[t) <
Velu +1 [m()AX)))] and (T) by V2 [|m)A(X))]]l- Thus A(X(!) is well-defined for L 0, plugging
anT
= 0 to (47) we obtain V(0) 0. Therefore we have
sim Vs, (1) S sim (0) 0 V(0),
n
n
it remains to show (t) S lim sup, VA, (t). Observe, as equality x(() = -((((t)) 8()( - Xo) holds since E S, from (48) we have
R(t)2
(11xT00ff + ((0) (X((t) Xoll²)
V(t)
2
Therefore if is suffices to check Lemma E.4 is valid here with some Ux.. For some > 0, Define Us.: 10, oc) + R as
U2, (t) = Xx, (t) - -3() || (t) - xoll2 + S. ((s))
23(s)2
||Xx, (s) - -Xoll ds
3(s)
fn(()

---

We proceed similar argument with Lemma B.5. Differentiating Xx, (t) -Ax,. ((0()) (t) -Xo). we have for almost all t >> 0
Xxm d
dt (X(0) - XX) B(t))xx, (t).
Therefore for almost all > 0.
U²n(0 (t)
-2 (2 (A, -0)0 xo1l ( (Xx, (1), (X),,)) Xx, (1) xx)++ + [(()) 20(()²
| (1) -ool
B(1)
d _ -2 (t)
Ax, (X(1)) - ((0)(x,. (((())--((((xx.)) (1)-))))))))))) - Xo) (X) -o)- -8()x())) -2((1( (xixn (t), (t)-(()))) - x0)) - 23(1)
dl
B(1) (t) - X
= --2(Xx. (t).
d _ As. (x(00) 23(() -28(() xxx + A(1)
12 50.
(X (t) - -Xo)
B(t)
Therefore Ux,, is nonincreasing, we can prove ||x(|| S lim supp | (1) with same argument in Lemma E.4.
Therefore we have V(I)= < V(0) = 0 for E S. Extending the result to [0, oo) can be done with the same argument done in Appendix E.3.4.
H.2.2 Proof for convergence rate
Recall
V(I) (elt =u2y
|(((())) + 2p((1 - 22-) (A(X()),X()) - Xo) - 21
-222
e 220) [|X(1) - Xoll².
Observe
(t)
(came - 4 (A(X())) - Xo) - 4n2 (X(() Xoo12
1 22st 2pt
= (etit 1) - X(1) Xo) + 4n² (IX(1) Xoll²)
+ eell 1)]1 + C!C (4) x(1) -Xo) - 4/² (1x(1) Xoll²)
=p(1)
From the law of cosines, we have [tx(t) Xol12 = 11x(0) XXII- - -((((t) -Xo, Xo, - X.) - -IX. -Xoll² Applying
this to p(t) we have
p(t)
4ycet ((A( - X.) (A(X(I)), - -x)) -l(((() - -xull3)
4re!" ((A(X())((X())) - X.), X(1- -X.) -()((((X(I)) - (x(((( Xo), - xx)- - x2.).)
Thus
(t)
(e 1) 1))(A(((()) - 2x(x(1) Xo)il² 2 + CC" 1)1 1)|(((0)))++0))
1 2pt
= ((ett - 1))I (x(x(() - -xo)l22 - 4pc (Ā(X(t)) - 2/(x(()) - Xo - -X,)
+ e!ue (ate 1)1 1X))((200)12 4pc (Ā((()) m(X(1) - xx.), - X-) + = 11o -X,12
= -(cue - 11) (|/A((((0) - (2(((() Xo)
2uett
(Xu - x.)|| -x.)
4p2e2ut
ext - 1 - 1
elt
+ ett (cte - -1)1 + 4quent ((A(X(I)), X(t) - x.) x.)-111X(0 - xx11²) + 141/2e1111 - xx112.
75

---

Now since A is u-strongly monotone, (A( X.) -11xx(t)xX.If
-x 0. From previous section we know
0 ((0) Vtt) for all t O. Therefore for all f >>
0 2 (v())
1 e 2pr e-2 2 cE"( - 1))] + (ypPeMr 41c2221
1180 - -X.11
eltt -
4ppess
e (oule - 1))1A(X(0))
eur 1 |x00 - -x.11?
Organizing, we conclude
( edit -1
2
Á((())) <4
1
|Xx - -x.11
H.2.3 Informal derivation of ODE from the method
Assume A: IR + IR be continuous monotone operator: In [54], the method OS-PPM is presented as
JnA 1-1 k-
1
{ x
1 (,- -2a) y
y = 1
where y0 = =x", v = + 2hμ and = 1 + v² + + u2k
Using n
x + hAa substituting 1² and y
this method can be expressed in single line.
k+ hArkt1
(1-1)
Aat
1 _
8k
8k
Reorganizing and dividing both sides by h. we have
k+l xt
1
1
h Ax
Axt
(xt - )²
USk
hsk
Identifying xº = -Xo- 2hk = x, =(t),
X(t + 2h) -t()) -A(X(++2h)
(
1 1--1) A(X())
-x((1) -Xo)-
h
U8k
hSE
Now observe
2k+
(1 + 2h11) 2R+22
lim
hskk
lim
h
lim h
h-0
h-00
v2 -1
h00
(1 + 2/14)² )22
(1 + 2h11)2(1 + 2h41) -
lim
h-0
4 + h4r)
lim
lim
h-
V/ h-+
+ 2h4u
1
1
4p
lim
lim
11 = 1 x
x 0 =0
4+
D8k
++
2ee -1
Taking limit h + + and organizing,
4f
2) - -(4)
eapt (X(1) Xo).
By diving both sides by 2, we get the desired anchor ODE
2μ1
x(1) = -A((())
(X(1) Xo)-
76

---

I
Proof omitted in Section 7
1.1 Proof for Theorem 7.1
We first check
| - =
where
x(1) A(((()) ((0(((() - Xo) |
B(() ((A(X(t), x(t) - -Xo)
By definition of (()), (t) defined in (8) becomes zero, i.e.
0 (t) = [ + 28(t) (A(X()),X-X))
Plugging (t)) 0 to inequality (8) we have
0 02 2 ||(X(()) -3(()) | -x,11
Reorganizing, we get the desired result. Other results need some works, we provide the proof with steps into subsections.
L1.1 ((t) > 0 for t
Taking inner product with Á(X) to the ODE and applying (t) = 0 we have
(X())A(((I)) = =-1|A(X(00|]= - B(t) (A(X(()). Xo) = - ||Ax((0)
As assumed to be continuous, taking limit - 0+ we have
lim (x())A(x(()) +-+++
lim X(1,, A())) ++++
1 lim | = - -1000==~111aa00 ||Ao,1)
- 1-0
On the other hand, by assumption we have lim; (t) lim4-+0 X(t) X1 and ||A(Xo)]| # O, thus
lim + t X(X(())))(I)) - Xo) = A(Xo): lim x(0)= |((x)))l' < 0.
(50)
+-0+
Therefore there is such that (A(X(I)), X(t) Xo) O for E (0, thus for E (0, have (A(X(t)).x(t)) - Xo) * 0 so B(t) well-defined and satisfies
|((())))
B(1) 2 (()(X(t)), X(t) - -X,)
0.
Observe the denominator of (t) zero when [|A((()))| 0. As 3 assumed be well-defined, have ||(((()))| +
for all t 0. Since 3 is continuous as A and X are continuous, by intermediate value theorem we have ||((()))]] > for all 1>
I.1.2 Proof for the main statements
We first show following lemma.
Lemma I.I. Following equality holds for almost every > 0.
(8()) (A(X())), X(t) - Xo) = (( ((x()))))())
(51)
77

---

Proof. Since A is Lipschitz continuous by assumption, by Lemma B.4 we know (t) is differentiable almost everywhere. Differenniaaing (t)) we have
0 (t) ( d A(X(0))(((())) + ()(() Xo) + +B((t) ( ((X(())))x()) xo) -20(t) (A(X())),x())
d
dt
dt
de d ((X(()) + Xa) + +28(t) (A(X(t)), X(t) - Xo)
23(1)
Xo))
A(X(0).(1)
-2((0 |A((()) + ( - ((()))((0)²) (A(X(t)),X(I) XX)
d A(X(I), x(1)
+48(19 (A(X()), X()) - Xo) + (B(1) (LV0-8(1) B(0P) (A(X(1)) - -Xo)
= -2 A(X(t). x(1)
+ (300) + )()) (A(x(I), - Xo)
for & (0, oc) almost everywhere. The equalities come from the ODE x() - -()())())((()0))))) -Xo) and the fact
(t) = 0. Reorganizing, we have the desired equation (51).
Now we show the upper bounds of ((L) for each monotone and strongly monotone case. Observe from (51) and the definition of (1), we have for almost all E (0, oo)
(t) + B(t) 2,((t)
- (
(52)
(i) When Å is monotone. From (52) and (1) we have for almost all I. E (0, oo)
B(t) + B(t)²
|
( L t (AAX)))) 20.
23(()
Since 3(t) > 0 we have
B(t) + [()) < 0.
almost everywhere. Now dividing both sides by B(t)² we have
3())
<
B(t)2
holds almost everywhere. Since
B(t) 3(1)2
d 2
integrating above inequality both side from 8 to f we have
30
1
1
8 < 3(t)
B(t) <
3(6)
8 8+
3(3)
By the way, from (50) we have
(((()))
lim t,3(t) = lim
1,
(A((()), X 1-0
1 = 0. Therefore taking limit 5 + 0+ we have thus lims-s0 ((8) = 0o, so lim +0+ 3(8)
1
1
B(t) < lim
8-+0+
t 8
+ 300)
78

---

i When A p-strongly monotone.
From (52) and (2) for almost all & E (0, oo) we have
(11) 3())
( d ( A(X),x x) 24 |x/////o/
||A(((t)))
(53)
23(()
de
On the other hand, observe
x = ( - Xo)l?
A(X()) + 23(1) (A(X(1), X(1) Xo) +3(1)) (Ix(1) Xoll = (0(1==5(1)]1000 (|(()) -(())- Xoll²
=+(0==
From Cauchy-Schwarr inequality we see
A(X()))) -28(() (Ā(X()), X()) - Xo) E 23(1) ||(((())) Xoll,
therefore ||A(X(())|I 23(1) [x(1) Xoll- Combining above observations, have for almost all >> 0
4 x I| 43(1)² (() - Xoll
2 1.
(54)
|(((()))
|(((()))]|*
From (53) and (54), we get an incquality for B(t) and B(t)
((t) + 3(t)
((t)
B(t)
28(1) 28(())
4
Moving 2
800) to the right-hane hand side and reorganizing, we have for almost all t >> 0
B(t) 1 3(0 B(t))
B(t) 1
B(t)
+ 3(t)
#
3(1) 5S2 3(1
2 3(t)
/ + 3(1)
Integrating above inequality both sides from 5 to we have
* 5) < | log (t) + log (- + B(t))] log お +(10)
1 + 3(8)
log B())
3(t)
As observed in case (i) know lims 3()) xo, taking limit R - 0+ both sides have
tt
+ B(t)
log (1 1+
1/2
1/2
< log
e/2/2 11+ 3(t)
2
((t)
3(t)
Organizing, we get the desired result.
11/
B(L) S
eut/2
1.2 Correspondence between the ODE (11) and the discrete method in Theorem 7.2
Observe, the case h 1 for below method corresponds to the method provided in Theorem 7.2.
JNAV k-1
|1A
if | +
8 (hAck x - =0))===>>> + 11AA0*
if || 0
y (1 (2x - - + 32.0
79

---

We now show when continuous and ||Ax*112 o for all & 2 we obtain the ODE (11) when we take limit + 0+. Note when A is continuous A equals A. From hA + zh+1 y², substituting y and y we get single line expression hAr + x x (1 Ax)(x* hAx*) + 3xxx
Reorganizing and dividing both sides by h. we have
x+1 x
8k ( (x*- =x0).
A - Ax)Ax*
h
Identify x0 Xo. 2hk and x² ((). Then see
3x AA x² 2²) + h Ax -(A(X(I)), X(O) Xo) + MIX(X())))
1:2 A0
[A(X1))12
Thus 0% O (h), we have lim 3x Now taking limit + 0+ we have
| (X(t) - Xo). 2x(()) = - x((X())xX)) -Xo)
Dividing both sides by 2, we obtain (11).
1.2.1 Correspondence between convergence rates in Theorem 7.1 and Theorem 7.2
From identification above, see B(t) corresponds and x = (() we have
& 24
Therefore we see with identification x.) Xo,, x-' Xx, 2hk
32 x*1
divide by A2, A-0+
| (** 111 82 11 x² 2011 4h2
1000
|((((())) 44((1) I| Xx11²
(2h)²
And we can also check that the bound Bx E+I for the monotone case, is equivalent to 24 S 2i++ork and corresponds to (()) S { as well.
Now suppose A is p-strongly monotone and L-Lipschitz continuous. Then hA is hu-sttongly monotone and hL-Lipschitz continuous, we have the following inequality from Theorem 7.2
Bk
2(1 + (b1.)*
(55)
2h
11
hy (h()))
1+(h))²
Recalling the identification 2hk f., we see
((1++
1-001
a(1+(N1)2)
hp
-(1+ 1+ + (hL))
h4
ai
hy 1+ (hZ)²
h-00
1 + (KL)3
=
eut/2
Therefore identifying 3(t)
8e and taking limit + 0+ to the inequality (55), we have 2h
1/2
3(t) <
eat/2 -
I.3 Proof of Theorem 7.2
Recall, the method was defined as
k JAY k-1
|
if || +
(Axk xb - =x0)= + ||
A
*
(1 Bx) - -) )- + 3
80

---

First, we assume Az for all 0. Define
th -1-33 -Bx) |A* + Ba( x² σ0)
(1-Bk)
for .......,
and
Φh 1| + Bk-1 (Ax", 1
x r.))
for k: = 2....... Note by definition of Be. we have Th = 0. Our goal to prove
gk+ S.
Then with the same argument with (8) we can conclude ||A - BR110e x=' 112. To do so, we first show following lemma.
Lemma L.2. For 1, following is true.
= (1 Bx) = (A) Aot, 2kt1 x²))
(56)
Proof. Recall y = x 1 + A Substituting 3r and y 1 the method is equivalent to ++1 Ax = (1 - (x)(2* Art) + Saxx
From above we can get two different expression of (1 (z x²1)
(1- - (x)((
x²) = -1 (A+ + Ax*) - 33 (Ax + (x h+1 - -x0) = (1 [aa][((A'')) [( + Axt) - Bx (Axt (x* -2")]]
With reorganizing, first equality can be obtained by subtracting both sides by By (x - x²) and the second equality can be obtained by multiplying both sides by (1 - 3z).
From this we have
(1 (Ax Ax x --11-2) x²²)
(Ax (1 -1- 1x 211) - (Ax* " (1 - Bx) - x²))
(Aatt1 -(1 -Ax) k+1 + Pott) - Bx (x k+1 + (xxt1 - x. 20)))
3x) (Āx*, -AAx Axt) + Bx Axx (=*--x"13
= -(1 - Be)l k+1 112 1/2- - (A Ark+1 + +0 -x0))
+ (1 - 9&) (12 (Ax" Az - (x* - =x")))
B&) ((1 Ax) + Be(Aat xt -x0))= || 112 Bx (Aatt) rttl - x0)
= (1 - 0* ++1
Since A monotone we have (Ax*+1 Az x+1 -x²) 2 0. we see that the right-hand side of (56) is greater or equal
to 0f - 3x 0. Thus it remains to show - 3x 2 0. As the index is quite confusing, provide it as a lemma to avoid confusion while proceeding the proof.
Lemma I.3. If Ar* + for all 2 1, then
(Az*, -00) <0, Bk E (0.1),
b+ 50
for all k 1.
Proof. Proof by induction. From x² = Jays = Jax" " we have xf + Art x0 and so x² - x0 = Axx Applying these
facts we have
(Ax', x1 x0) = -11AAz'11 < <0.
||
B1 -(Az!, xe x0) + || (0,
81

---

As 1 81 > 0, from (56) we have
(1)3:)0² -2²
-0== 3-" (1 - 3:) - -Ax", x² x²) 2 0.
As $- 0 by definition, have x² < 0. Therefore the statement is true for h: = 1.
Now suppose the statements are true for By induction hypothesis, we know
0 02 a k+ = | + Bx (Ax g x
As 3 > from induction hypothesis and Ac # by assumption, reorganizing $h S we have
||
(Aohti xhtl x²)- S
BR < 0.
And therefore
|| A
Bk+1
E (.,1). (Ax R+1 xb+1 x + A1
Since
1 Bk+1 > by (56) we have
(1 - Bk+1) ) h-t k+22_ = (1 - 3K+1) Ast-1 x+2 xhtl) 20. 0.
Since Th+1 = 0 by definition, we have gx+2 0. Therefore the statements are true for k 1, by induction, we get the desired result.
Suppose || 1|2 # for all k 2 From the lemma we know o S 0 for k 2 1, with the same argument of (8) we have
for x= E ZZerA
0 2 $1+1 A| 1+1 1|2 + 3x (Ax
xkt1 -htll=x --- - Bx (xx kt1 x0 - xx*)
2 11 12 3x (Ax k+1
1². -x)
A 1|= ( |o 1
|
+
B2
-1100
11==-x'11 -x-11)
32 11 2=1 1 =5ll 1112
2
Organizing, we get
A k- 112 S 821120 x=1 112
Now we show the upper bound of 3r. Observe from (56) and the fact & = O. we have
(1 - 3x) (Ax A A+1 x²)) (1 B*) xb+1
Bk g - gutt1
(
(Bx=
3x
Bx
-1)
||A 12
Bk+1
3k+1
As 1 8x # for t 2 1 by Lemma 1.3, dividing both sides by 1 - Br. get the discrete counterpart of (52),
Br
Bg
(Ax Ar xhtl s²
32+1
|1
(57)
3x
When A monotone. From (57) and monotonicity of A we have
Bk
0 5 (Az
Art, kt1
2bb)
3x
From Lemma 1.3 we have 1 - 3x 0, therefore
Bk 36
1
122
=
+ 1 S
B
Bx
Bx+1
Summing up, as 31 and
0 we have
1
1
1
+ (k:
-
1)
+15
Bk Σ
3
3x
k + 1
82

---

ii When A p-strongly monotone. Since A is p-strongly monotone, from (57) we have
Dr Be+s
Bx
14 | r²1|²= S (Ar Art a 1
A 112
3k
|
x'1
Define rh
for k 0, ..... Dividing both sides by ||Ax+t11| and organizing, have
Azt+1
ThJ
B6+1
Bx
Bx -1
TEP(1 - Bx) -
3k
Bs
11-1= Br
1) 3n. - -(1 - Bx).
1 8k
Bk+1
Bk-1
Dividing both sides by Be and reorganizing, we get a recursive inequality for
1
33x
(1 11+re TEM) ( (1--1) +15 8k+1
(58)
We now prove upper bound of 3g from above inequality. Lemma 1.4. Suppose A be a p-strongly monotone operator. Let By be sequence defined Theorem 7.2 and let Fk
Ank41 for k: 0, 1,.... Then following holds for 1.2.....
Bk 1-11 (1+rap)
+2
j=1 i=j
Proof.
First observe, the statement is equivalent
k-1k-1
12
Σ j=
(1+n))++ +1.
8
The proof can be done by induction with (58).
When & 1, recalling 31 2 from the proof Lemma I.3, we can check the inequality is true.
Now suppose the inequality is true for is = m. Then from (58) we have
2 (1 + Tmj)
+1
8m+1
3m
m- 1 mm1
(1 + Tmf)
Σ
II
(1+
m2)) +1 +1 +1
=
m m
m
EI rad) + (1 + rmft)
+1 ΣI #=
(1+ 1++)
Therefore, we get the desired result.
Under the identification considered in Appendix I.2, the continuous counterpart of r is
[x(+]]
1+t xk
|
x
h-+0+
Tk
| ++1++11
(2h)²
A
AA(()))
and is greater or equal to 1 by (54). We obtained an exponential convergence rate in continuous setup from this fact. In the same spirit, we can get an exponential convergence rate for discrete setup there positive lower bound for rs. we provide it as a corollary of Lemma I.4.
83

---

Corollary 1.5. Consider the setup of Lemma 1.4. Suppose there 2 such that Tk 2 r for 0, ........ Then following is true for k = 2,
8k 5
(1+ - 1 rp
Proof. From тk 2 r we have
k-1 EI jl
k-1k-1
(1++
+
EII
(1 (1+Tp) +2
j=
(1 (1+ ru) +1 (1 + ru)*
Σ (1+ +2 Σ
+ ry
ru
1=0
Applying Lemma 1.4, we get the desired result.
We now show
I+L holds when A is furthermore L-Lipschitz continuous.
iiii) When A is ju-strongly monotone and L-Lipschitz continuous.
Recall from the proof Lemma I.2, we know
x= x+1 x Ax R+I (1- B1) Ax -Ba =x)).
Taking inner product with Ar both sides we have
(Ar", x - x²) = (Ax Ax* - T = (Ar Art)).
From above equality we can check
| - x*1 1| + || - A =1|AA 111 + 1||attt - Iet + Ao*l1 2 ||
As A is L-Lipschitz continuous, we have
(1 + 1.)) ||a.t1 x² $11 || 2 1²1 || - Aat1|² ||
Dividing both sides by (1 + 1.2) || | I|2 we get a lowerbound for rk
1 z*1
||0++1112
1+
Applying Corollary 1.5 get the desired result
11(1 + +12)
Bx S
(1+1/(1 p/(1 + I.2)) &
+ pa(1 + 12)
Note if we take limit - 0+, with substitution a I+1= we have
L3)
lim p=+0+
11+1111- L2)) 1 + lim a -1)+
+1 1: +11*
which is the bound for the monotone case.
I.3.1 If there is k 2 0 such that Ar =
Suppose *r* = 0 for some k. Let N be the very first iterate such that Az = 0. Then from previous argument we know Theorem 7.2 is for 1o N. Thus remains show the statements are true for k 2 N.
From Av.. = we know y = N. + A = And since A = 0 implies BN = 0, from the definition of the method have N 2 N N. Therefore
N+1 N
JAA N.V
we conclude x² - NNo E ZerA for all k 2 N. Thus 3n 0, || for all k 2 N. the Theorem 7.2 is trivially true for k 2 N.
84

---

J Details of experiment in Section 7.1
We solve a compressed sensing problem of Shi et al. [63] which is formulated as an é-rregularized least-squared problem
minimize E (2 bell² + p||=|11}
=ER
We solve this problem in decentralized manner due to the problem setup where the network of local agents are Figure 2 and each agents communicate only with their neighbors, the nodes connected to each agents by edge. We use Satropolis-Hasttng matrix mixing matrix W E R"x" and apply PG-EXTRA, Let Wi, denote ji,j)-th entry of W and N, S (1,2..... n
denote the index of the agents in the neighborhood of agent i. Consider
x+1 PloXoppl-ll
Wa a. (A - -b()) - w.
JEN.
k+1 W w
2
-
Σ
Wi Wx,xx
k = 0,1
(PG-EXTRA)
JEN;
to the problem above. Under suitable choice of parameters, PG-EXTRA can be seen as a fixed- iteration of an averaged operator with respect to al [74. Theorem 2], where the metric matrix M defined as
(1/a)I U
UT
M
aT
and U is symmetric definite matrix with U² } W). That is, denoting x² w Rdxn as the vertical stack of x and w respectively [58, Chapter 11.3], PG-EXTRA can be rewritten (x++1, w T(x* w*). Using this T, we proceed the experiment with the Halpern method
(x 1o++1,##t + = 8 (x", w + (1 - -3x) T(x" w
When T an averaged operator, it is nonexpansive, we know T = IR = 2J for some maximal monotone operator A [54, Lemma 2.1]. Considering the equivalence discussed in Lemma D.2, presented algorithms of the form
above Halpern method is equivalent
k+1 JAy
h+1 = =(1 -1- (1k) (2x - x²) + B,x0,
by corresponding y* (x++1, wb))). Note the operator norm A | can be calculated by considering below equation
M
(Ty k-1 1) JAY 3/ x (Ax x²t -z
We use the anchor coefficients Br k+I 3h 10, with 1.5, 2.0 and the adaptive choice of 3, in Theorem 7.2 with M-norm. Note, in the experiment the adaptive coefficient is calculated by considering below equation
1
1
Ty y² 35
1
||A
2 Ty 1 P2 + (Ty
,²)as
2 Act |
(-2Art, Art xtth x0)
|| 133
(Ar * . x0
||
We choose the dimension of signal d 100, the number of agents 20, the number of measurement for each agent m, 4, L -regularization parameter p = 0.01, and algorithm parameter a = 0.01.
K
Broader Impacts
Our work focuses on the theoretical aspects of convex optimization algorithms. There are no negative social impacts that we anticipate from theoretical results.
L
Limitations
Our analysis concerns convex optimization. Although this assumption is standard in optimization theory, many functions that arise in machine learning practice are not convex.
85


Reviews:
[{"review_id": "wywtqBSFFB", "reviewer": "Reviewer_MP6a", "summary": "The paper analyzes the dynamics of anchor acceleration using a differential inclusion. It derives a convergence rate that depends on the anchor coefficient and shows that the rate is tight using a certain instance. By discretizing the differential inclusions, the authors derive an algorithm that generalizes the state-of-the-art APPM algorithm and provide an analysis of its convergence rate. In addition, the authors propose an algorithm that adaptively varies the anchor coefficient and show its performance both theoretically and empirically.", "questions": "- Since A is treated as a set-valued operator in \"Monotone and set-valued operators\" of Section 1.1, I understood that Ax in the equations in Lines 39 and 41 is a set. Then those equations involve the inner product of a point and a set in Euclidean space. Such an inner product is not clear to me. Additionally, in Line 50, A is assumed to be a differentiable operator, but the definition of the differentiability of set-valued operators is nontrivial. So, I guessed that A here is a single-valued operator. Is it correct? If so, it would be good to clarify it.\n\n- Theorem 2.2 states the uniqueness of the solution of the differential inclusion (6) rather than a differential equation. Is this a valid claim? It seems for me that there is more than one solution depending on which of the elements in A(X(t)) in equation (6) is chosen at each time t. Adding a comment on this point would facilitate the reader's understanding.", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Compared to existing papers that provide analysis of anchor methods through continuous-time analysis, this paper provides better convergence rates in a more general setting.\n\n- The adaptive anchor acceleration method in Section 7 is interesting, and the method is inspired by the analysis of continuous-time dynamics. It is a meaningful example of the potential of ODE analysis for optimization algorithm design.", "weaknesses": "- In terms of algorithms and their theoretical analysis, the contribution of this paper does not appear to be significant. In my understanding, the main result of this paper is deriving a known convergence rate in a different way, and proposing a different algorithm that achieves the same rate as the known one. There is insufficient discussion of how the results of this paper are superior to existing studies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable review. \nWe're glad that you've felt our adaptive anchor acceleration method in Section 7 as a \"meaningful example of the potential of ODE analysis for optimization algorithm design\". \nWe address the answers to your questions and feedbacks as follows. \n\n\n\n**Q1.**\n\n- As mentioned by the reviewer, $\\\\mathbb{A}x$ is a set.\nThe definition of the inner product between a point and a set is clarified in Line 40, which is referenced from [Ryu \\& Yin, 54].\nWe will replace 'i.e' in Line 40 to other expressions such as 'which means that' to avoid confusion.\nThank you.\n-  We missed to mention that the definition of differentiable operator includes singe-valuedness.\nAs you mentioned, $\\\\mathbb{A}$ in Line 50 is single-valued, and we will clarify this issue.\nThank you for pointing this out.\n\n\n**Q2.**\n\nYes, it is a valid claim, and we provide the proof in Section B.1. of the appendix. \nRecall that in Line 59, the solution was defined as a function $X\\\\colon [0,\\\\infty) \\\\to \\\\mathbb{R}^n$ that satisfies certain condition, and in case of theorem 2.2, it is:\n*\"absolutely continuous and satisfies (6) for $t\\\\in(0,\\\\infty)$ almost everywhere, with initial condition $X(0)=X_0$.\"*\nThe claim of theorem 2.2 is that if a function $X \\\\colon [0,\\\\infty) \\\\to \\\\mathbb{R}^n$ satisfy such conditions, it is unique as a function. \nNote that this fact holds true regardless of $\\\\mathbb{A}(X(t))$ being a set.\n\nTo provide further clarification, for the unique solution $X$, the element of $\\\\mathbb{A}(X(t))$ satisfying $\\\\dot{X}(t) \\\\in -\\\\mathbb{A}(X(t)) - \\\\frac{\\\\gamma}{t^p} (X(t)-X_0)$ is uniquely chosen for each $t>0$ up to measure zero. \nOnce the absolutely continuous function $X\\\\colon [0,\\\\infty) \\\\to \\\\mathbb{R}^n$ is determined, its derivative $\\\\dot{X}$ is defined almost everywhere and is unique up to measure zero.\nAs a consequence, the selection defined in Line 61, $\\\\tilde{\\\\mathbb{A}}(X(t)) := -\\\\dot{X}(t) - \\\\frac{\\\\gamma}{t^p} (X(t)-X_0)$ is determined almost everywhere and is unique up to measure zero as well. \n\nA standard reference that rigorously establishes the well-posedness of such differential inclusions is [33]. \n\n\n\n\n**Weakness.**\n\nThrough the convergence analysis for the generalized anchor coefficient $\\\\beta(t)$, we were able to obtain a more refined understanding of the role of the anchor coefficient, which further motivated our adaptive method.\nTheorem 3.1 and the results in Table 1 give the intuition that the (i) vanishing speed of $\\\\beta(t)$ must be fast enough in order not to slow down the convergence, and (ii) the optimally balanced choice for monotone condition is $\\\\frac{1}{t}$. \nThis intuition is strengthened via checking the tightness and the correspondence to the discrete setup in section 4 and 5.\nHowever, Theorem 6.2 shows that the linear rate is attainable for $\\\\mu$-strongly monotone operator with $\\\\beta(t)$ vanishing linearly fast, but not with $\\\\beta(t) = \\\\frac{1}{t}$ (Line 196). \nOverall results of section 3 to 6 lead to another message that \"anchor coefficient should be chosen to adapt to the operator's property.''\nThis motivates our adaptive method. \nMoreover, observing the commonly occurring terms from Proposition 3.2 and Proposition 6.1 referred to as $\\\\Phi(t)$, we could get inspiration to design our adaptive method which keeps $\\\\Phi(t) = 0$.\n\n\n\nAgain, we thank the reviewer for the constructive feedback. We believe we have addressed the reviewer's concern about the validity of Theorem 2.2. In that case, we kindly ask the reviewer to consider raising the score."}, {"review_id": "ue4U8sLKGD", "reviewer": "Reviewer_aLVj", "summary": "The paper focuses on the analysis of anchor acceleration, a recently discovered acceleration mechanism for minimax optimization and fixed-point problems. The authors provide tight and unified analyses to characterize the convergence rate of anchor acceleration and present an adaptive method inspired by continuous-time analyses. The contributions include a differential inclusion model of anchor acceleration, well-posedness analysis, convergence rate analysis with a power-law anchor coefficient, and an adaptive method for choosing the anchor coefficient.", "questions": "- Can you provide more details on the motivation behind using anchor acceleration and how it differs from other acceleration mechanisms, such as Nesterov's acceleration?\n\n- Can you provide more insights into the choice of the anchor coefficient $\\beta(t)$ and how it affects the convergence rate of the algorithm?\n\n- Can you provide more details on the assumptions made in the analysis and how they may affect the applicability of the proposed method to real-world problems?", "limitations": "The authors does not seem to discuss the limitations adequately, they do mention that carrying out more advanced analyses for the anchor ODE are interesting directions of future work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Given the limited understanding of the anchor acceleration mechanism compared to Nesterov acceleration, the authors aim to provide a formal and rigorous treatment of the anchored dynamics through continuous-time analyses. They also seek to gain insight into the anchor acceleration mechanism and its accelerated convergence rate.\n\nThe authors present a differential inclusion model of anchor acceleration and establish its well-posedness. They analyze the convergence rate of the anchor ODE with a power-law anchor coefficient. The trade-off between the vanishing speed and the contracting speed of the anchor term is discussed. The authors also provide a proof outline of Lemma 3.4 and Theorem 3.1 to derive the convergence result. Additionally, the study presents an adaptive method for choosing the anchor coefficient based on continuous-time analyses.", "weaknesses": "- Novelty of applying continuous analysis to anchor acceleration: It would be helpful for the authors to clarify the motivation behind applying continuous analysis techniques specifically to the problem of anchor acceleration. Given the existence of continuous analysis techniques, what is the significance of applying them to anchor acceleration? This clarification would strengthen the novelty of the paper.\n\n- Importance of anchor acceleration: The paper could benefit from providing a clear explanation of why anchor acceleration is important and how it differs from other acceleration mechanisms, such as Nesterov acceleration. This would help readers understand the relevance and practical implications of anchor acceleration.\n\n- Technical challenges of applying continuous analysis: Can you elaborate on the specific technical challenges encountered when applying continuous analysis to the anchor acceleration problem? Discuss any unique aspects or complexities involved in analyzing the convergence properties of anchor acceleration using continuous-time techniques?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the valuable feedback and thoughtful questions. \nThe answers to your questions are as follow. \n\n**Importance of anchor acceleration, difference between Nesterov's acceleration (W2, Q1) :**\n\nThe main difference between Nesterov acceleration and anchor acceleration is that they are optimal methods for **different settings**.\nNesterov acceleration is optimal in convex minimization problems, whereas anchor acceleration is optimal in minimax problems and fixed point problems.\nFor minimax problems, an anchor-based method called EAG [70] was the first algorithm to achieve $\\\\mathcal{O} \\\\left( \\\\frac{1}{k^2} \\\\right)$-rate, and FEG [39] improved convergence rate by constant and generalized the setting.\nfor fixed point problems, Halpern method of [42] and OC-Halpern [51] are probably exactly optimal [51], and equivalently APPM [34] and OS-PPM [51] are proven to be exactly optimal for monotone inclusions.\nAll aforementioned methods use anchor acceleration. \nTherefore we believe that the anchor acceleration is the primary acceleration mechanism for these settings (which are not convex minimization) and their optimal use in discrete-time algorithms motivates our work.\n\n\n**Novelty of applying continuous analysis to anchor acceleration, technical challenges of applying continuous analysis (W1, W3) :**\n\nWe think the Lyapunov functions we've introduced in Corollary 3.3 represent a non-trivial technical challenge that we overcame.\nSpecifically, we introduce the Lyapunov function of the form\n\\\\begin{align*}\n    V(t) &= \\\\frac{C(t)^2}{2} \\\\left( \\\\left\\\\| \\\\mathbb{A}(X(t)) \\\\right\\\\|^2 + 2\\\\beta(t) \\\\left\\\\langle \\\\mathbb{A}(X(t)) , X(t) - X_0 \\\\right\\\\rangle + ( \\\\beta(t)^2 + \\\\dot{\\\\beta}(t) )  \\\\left\\\\| X(t)-X_0 \\\\right\\\\|^2 \\\\right) \\\\\\\\ &\\\\quad\n        - \\\\int_{t_0}^{t} \\\\frac{d}{ds} \\\\left( \\\\frac{C(s)^2\\\\dot{\\\\beta}(s)}{2} \\\\right) \\\\left\\\\| X(t)-X_0 \\\\right\\\\|^2  ds,\n\\\\end{align*}\nwhich is very different from the Lyapunov functions use for Nexterov acceleration [Su et al., 61, 62]:\n\\\\begin{align*}\n    \\\\mathcal{E}(t) = \\\\frac{2t^2}{r-1} ( f(X(t) - f^{\\\\star} ) + (r-1) \\\\left\\\\| X(t) - x^\\\\star + \\\\frac{t}{r-1} \\\\dot{X}(t)  \\\\right\\\\|^2. \n\\\\end{align*}\nIn the analysis of optimization algorithm, the construction of an appropriate (continuous- or discrete-time) Lyapunov function is often the main technical challenge, and we argue that discovering this Lyapunov function and using it to characterize the continuous-time dynamics is a novel contribution.\n\nUsing this Lyapunov function, we obtained convergence rates for generalized coefficient $\\\\beta(t) = \\\\frac{\\\\gamma}{t^p}$ with $\\\\gamma>0$ and $p>0$ as in Table 1. \nThis result provides us with a more refined  understanding of the anchor mechanisms. \nThese results also extend to discrete setup, as section 5 confirms such correspondence.\nWe then provide analysis for strongly monotone conditions as well (section 6). \nThe insights from these analyses culminate in designing the adaptive method of section 7, which we believe to be useful in practice due to its adaptability to both monotonicity and strong monotonicity.\n\n\n**Insights into the choice of the anchor coefficient $\\\\beta(t)$ (Q2) :**\n\nWe answer this question by summarizing Section 3 of the paper.\nAs the name 'anchor' suggests, the anchor term pulls the trajectory towards the anchor.\nIntuitively speaking, sufficient amount of pull by anchor leads to contracting behavior of the dynamics and convergence as well.\nHowever, the anchor should eventually vanish, since our goal is to converge to an optimum $X_\\\\star$ making $\\\\mathbb{A}$ zero, not to the anchor.\nTherefore, the vanishing speed $\\\\beta(t)$ of anchor should be fast enough for the flow to safely converge to the optimum.\nProper balancing between 'necessity of anchor' and 'vanishing anchor' leads to fast convergence, and choice of $\\\\beta(t) = \\\\frac{1}{t}$ for merely monotone $\\\\mathbb{A}$ can be found with such intuition.\n\n\n**Applicability of assumption (Q3):**\n\nOne of the most significant applications of anchor acceleration is minimax optimization.\nThere are several papers using anchor acceleration for minimax optimization that have been published in ML venues, such as EAG [70, ICML 2021] and FEG [39, NeurIPS 2021].\nOur work considers the problem of making the norm of monotone operators small efficiently.\nThe saddle differential operator $G_L = (\\\\nabla_x L,\\\\, - \\\\nabla_y L)$ of convex-concave minimax function $L \\\\colon \\\\mathbb{R}^n \\\\times \\\\mathbb{R}^m \\\\to \\\\mathbb{R}$ is a monotone operator, thus anchor scheme is applicable. \nThe point where $G_L$ outputs zero vector is the saddle point of $\\\\min_x\\\\max_{y} L(x,y)$,\nthus minimizing $\\\\left\\\\| G_L(x,y) \\\\right\\\\|^2$ solves this minimax optimization problem.\n\n\nWe thank the reviewer for the clarifying questions. We hope we have addressed the reviewer's primary concern about the significance of the anchor acceleration. If so, we kindly ask the reviewer to consider raising the score."}, {"review_id": "zmPtABJYGq", "reviewer": "Reviewer_mK3f", "summary": "This paper conducts a continuous-time analysis of an acceleration method called \"anchoring\", where the main contributions are four-fold. The authors provided a unified analysis of the convergence rate of anchor acceleration, which includes both the constant and adaptive cases. Then the authors presented an adaptive method for anchor acceleration that is inspired by our analysis and achieves faster convergence rates than the constant method. After this, the authors proved that the adaptive method is robust to noise and can handle non-convex optimization problems. Finally, the authors provided numerical experiments that demonstrate the effectiveness of the adaptive method on various optimization problems. Overall, the paper provides a valuable contribution to the field of optimization and is in general well-written and well-presented.", "questions": "Are there some mismatches in the definition of Lyapunov functions at various places? For instance, the $V(t)$ definition in Line 133 [Corollary 3.3], when pinning $\\beta = \\frac{1}{t}$, and the last in Line 147 [last but one display of Section 3.1] differs by a factor of 2. These are minor, but I do encourage the authors to check them carefully.\n\nCan you provide examples of applications where anchor acceleration might be particularly useful? I understand that anchor acceleration has been discovered to be an acceleration mechanism for minimax optimization and fixed-point problems,  but would anchor acceleration be useful in other optimization problems as well?", "limitations": "This is a theoretical paper and admits no negative social impacts, to my best knowledge.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper provides a comprehensive analysis of the convergence rate of anchor acceleration, which includes both the constant and adaptive cases. The paper provides a clear and concise presentation of both the theoretical analysis, where I checked the technical proofs of all results with a detailed focus on Theorem 3.1 [Section E.5] and Theorem 6.2 [Section H.2] and they are solid. The idea of using the factor $\\frac{2 \\mu}{e^{2 \\mu t}-1}$ is is new and reasonable, since for \\mu-strongly convex objectives $\\mu\\to 0^+$ it is consistent with the standard $\\frac{1}{t}$ anchoring rate (the analysis provided is significantly more general, which should be honored). The adaptive method presented in the paper is also interesting, which appears faster convergence rates than the constant method and is robust to noise and non-convex optimization problems. The paper also clearly presented numerical experiments which demonstrate the effectiveness of the adaptive method on various optimization problems.\n", "weaknesses": "The paper assumes a certain level of mathematical background, which might be difficult for some readers unfamiliar with literature to follow. Further, the paper seems not provide a comparison of the adaptive method with other state-of-the-art optimization methods. In addition, the paper does not provide a detailed discussion of the limitations of the adaptive method and areas for future research. I have not checked but the assumptions of the adaptive method presented in the paper might be more stringent than required.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are pleased that the reviewer found our paper to \"provide a valuable contribution to the field of optimization\". \nEspecially, we're sincerely grateful that the reviewer thoroughly engaged with the technical proofs and highlighted the potential applicability of the ideas to more generalized cases.\n\n\n**Weakness : Further, the paper seems not provide a comparison of the adaptive method with other state-of-the-art optimization methods.**\n\nWe haven't provided the detailed comparison due to the fact that (i) there is no other adaptive methods to compare our method with and (ii) we already compared the state-or-the-art optimization methods other than adaptive methods.\nTo the best of our knowledge, our adaptive method is the only purely adaptive method present in the implicit method for monotone inclusion setup, which does not require any line search or backtracking procedure.\n(One can compare our method with that of [23], which requires backtracking of some sort.)\nFurthermore, non-adaptive schemes we compare our methods with (APPM, EAG, FEG) are all guaranteed with optimal convergence rate with matching lower bound.\nWe will make sure that to further emphasize on this point.\nThank you for pointing this out.\n\n\n**Weakness : In addition, the paper does not provide a detailed discussion of the limitations of the adaptive method and areas for future research. I have not checked but the assumptions of the adaptive method presented in the paper might be more stringent than required.**\n\nWe first want to clarify that our adaptive method only requires the standard assumption of maximal monotonicity, and it is guaranteed to have at least the same convergence rate as the state-of-the-art algorithm APPM. However, with additional assumptions, the adaptive method can be faster. This is the first adaptive of its kind (implicit method adapting to monotonicity or strong monotonicity without any linesearches or inner loops) and we derive it from continuous-time analysis. This adaptive method will certainly have limitations and we expect it to be possible to relax the assumptions guaranteeing linear rates. This is a very interesting direction of future work, and we view our contribution to be finding the first adaptive method of this kind and providing a proof of concept that this type of adaptivity is possible.\n\n**Q1.**\n\nThank you for pointing out this typo. The Lyapunov function in Line 147 has to be divided by factor 2. \nWe will correct this in our revision.\n\n\n**Q2.**\n\nThe fixed-point iteration subsumes convex optimization algorithms such as ADMM, PDHG, Condat-Vũ, three-operator splitting, and the anchor mechanism can provide acceleration for these algorithms.\nFor a specific task, anchor acceleration is practically useful in detecting infeasibility for constrained optimization problems [Park \\& Ryu, 2023], and accelerating value iteration for dynamic programming and reinforcement learning [Lee \\& Ryu, 2023].\n\n- J. Park and E. K. Ryu, Accelerated Infeasibility Detection of Constrained Optimization and Fixed-Point Iterations. ICML'23.   \n- J. Lee and E. K. Ryu, Accelerating Value Iteration with Anchoring. arXiv preprint. "}, {"review_id": "vtpcxAgpLK", "reviewer": "Reviewer_KkKu", "summary": "\nThe paper extends the continuous time analysis anchor ODE in [55] to involved a more general choice of the coefficient $\\beta(t)$ and show that the choice in [55] is in some sense optimal. They then go on to show:\n- correspondance with the discrete anchoring schemes APPM/FEG/AEG\n- Anchor ODE converges to a minimal $\\ell_2$-distance from initialization (like APPM [51])\n- Tightness of continuous time rates for anchor ODE\n- Convergence of APPM for more general choice of stepsize than $1/(k+2)$.\n- faster convergence under $\\mu$-strongly monotonicity for anchor ODE by choosing $\\beta(t)$ dependent on $\\mu$.\n- convergence with adaptive stepsize for both anchor ODE and APPM (single-valued) that recovers the rates for monotone and strongly monotone+Lipschitz", "questions": "- Can we obtain convergence for explicitly schemes such as AEG/FEG?\n- It seems very interesting that you can adapt both to L and $\\mu$. Would this work for explicit scheme?\n- Why distinguish between Halpern and APPM in Fig. 2 if they are equivalent?\n- What is $M$ in the $y$ axis of Figure 2?\n- FEG generalizes to cohypomonotone problems. Can anchor ODE handle cohypomonotonicity?", "limitations": "(see comments)", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall an impressive work. It seem interesting that one can adapt to both the smoothness parameter and the strong monotonicity modulus. The work seems fairly completely, I only leave a few comments/remarks below.\n", "weaknesses": "- My main concern is why we consider $\\beta(t)$ other than $1/t$ in the first place. The proof seems much more involved, but what does it buy us considering $1/t$ is already in some sense optimal. My understanding is that if only $1/t$ was considered then [55] and [34]/[Theorem 18](https://large-scale-book.mathopt.com/LSCOMO.pdf) already proofs convergence for anchor ODE and APPM respectively. At least clarifying this would be helpful.\n- The work contextualizes the results but usually quite late. Overall contextualizing w.r.t. existing work upfront and motivating the sections. E.g. elaborate on [55] in l. 20 and explicitly say \"adapt to the strong monotone modulus\" in l. 221. Explicitly compare theorem 5.1 with existing results for APPM.\n\nComments:\n\n- In terms of limitations maybe mention that the convergence results for the discretized schemes are only for implicit schemes (APPM)\n- I would mention existing discretization result up front (in [55] in contrast they only consider GD with anchoring and does not get $1/k^2$)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive and constructive review, we're glad that the reviewer found our paper to be \"impressive\" and \"complete\". \nWe would like to start by sharing the most interesting observation we've gained while addressing your questions. \n\n**Q5.**\n\nThe anchor ODE introduced in our paper does not handle cohypomonotonicity. \nHowever, we thought about this question and found a novel ODE that handles cohypomonotonicity. We are exited to share it here. \n\nConsider the ODE\n\\\\begin{align*}\n    \\\\dot{X}\n    = - \\\\left( 1 - \\\\frac{\\\\rho}{t}  \\\\right) \\\\mathbb{A}(X) - \\\\frac{1}{t} ( X - X_0 ) + \\\\rho \\\\frac{d}{dt} \\\\mathbb{A}(X) .\n\\\\end{align*}\nDefine Lyapunov function as\n\\\\begin{align*}\n    V(t) =  \\\\left( \\\\frac{t^2}{2} - t \\\\rho \\\\right) \\\\left\\\\| \\\\mathbb{A}(X) \\\\right\\\\|^2 + t \\\\left\\\\langle \\\\mathbb{A}(X), X-X_0  \\\\right\\\\rangle.\n\\\\end{align*}\nBy differentiating, we have\n\\\\begin{align*}\n    \\\\dot{V}(t) \n        &=  \\\\left( t - \\\\rho \\\\right) \\\\left\\\\| \\\\mathbb{A}(X) \\\\right\\\\|^2 \n            +  \\\\left( t^2 - 2 t \\\\rho \\\\right) \\\\left\\\\langle \\\\frac{d}{dt} \\\\mathbb{A}(X), \\\\mathbb{A}(X)  \\\\right\\\\rangle  \\\\\\\\ &\\\\quad\n            + \\\\left\\\\langle \\\\mathbb{A}(X), X-X_0  \\\\right\\\\rangle\n            + t \\\\left\\\\langle \\\\frac{d}{dt} \\\\mathbb{A}(X), X-X_0  \\\\right\\\\rangle \n            + t \\\\left\\\\langle \\\\mathbb{A}(X), \\\\dot{X}  \\\\right\\\\rangle \\\\\\\\\n        &= t^2 \\\\left\\\\langle \\\\frac{d}{dt} \\\\mathbb{A}(X), \\\\left( 1 - \\\\frac{2 \\\\rho}{t} \\\\right) \\\\mathbb{A}(X) + \\\\frac{1}{t} ( X-X_0 ) \\\\right\\\\rangle \n            + t \\\\left\\\\langle \\\\mathbb{A}(X), \\\\left( 1 - \\\\frac{\\\\rho}{t} \\\\right) \\\\mathbb{A}(X) + \\\\frac{1}{t} ( X - X_0 ) + \\\\dot{X}  \\\\right\\\\rangle \\\\\\\\\n        &= t^2 \\\\left\\\\langle \\\\frac{d}{dt} \\\\mathbb{A}(X), - \\\\dot{X} - \\\\frac{\\\\rho}{t} \\\\mathbb{A}(X) + \\\\rho \\\\frac{d}{dt} \\\\mathbb{A}(X)  \\\\right\\\\rangle\n            + t \\\\left\\\\langle \\\\mathbb{A}(X), \\\\rho \\\\frac{d}{dt} \\\\mathbb{A}(X)  \\\\right\\\\rangle        \\\\\\\\\n        &= - t^2 \\\\left( \\\\left\\\\langle \\\\frac{d}{dt} \\\\mathbb{A}(X), \\\\dot{X} \\\\right\\\\rangle - \\\\rho \\\\left\\\\|  \\\\frac{d}{dt} \\\\mathbb{A}(X) \\\\right\\\\|^2   \\\\right)    \\\\\\\\\n        &\\\\le 0.\n\\\\end{align*}\nLast inequality holds since $\\\\mathbb{A}$ is $\\\\rho$-cohypomonotone. \n\nNow from $V(t)\\\\le V(0) = 0$, we have\n\\\\begin{align*}\n    \\\\frac{t^2}{2} \\\\left\\\\| \\\\mathbb{A}(X) \\\\right\\\\|^2\n    &\\\\le t \\\\left( - \\\\left\\\\langle \\\\mathbb{A}(X), X-X_0  \\\\right\\\\rangle + \\\\rho \\\\left\\\\| \\\\mathbb{A}(X) \\\\right\\\\|^2    \\\\right) \\\\\\\\\n    &= t \\\\left( - \\\\left\\\\langle \\\\mathbb{A}(X), X-X_\\\\star  \\\\right\\\\rangle + \\\\rho \\\\left\\\\| \\\\mathbb{A}(X) \\\\right\\\\|^2  + \\\\left\\\\langle \\\\mathbb{A}(X), X_0-X_\\\\star  \\\\right\\\\rangle  \\\\right)   \\\\\\\\\n    &\\\\le t \\\\left\\\\langle \\\\mathbb{A}(X), X_0-X_\\\\star  \\\\right\\\\rangle \\\\\\\\\n    &\\\\le t \\\\left\\\\| \\\\mathbb{A}(X) \\\\right\\\\| \\\\left\\\\|  X_0-X_\\\\star \\\\right\\\\|.\n\\\\end{align*}\nReorganizing we have $\\\\left\\\\| \\\\mathbb{A}(X) \\\\right\\\\| \\\\le \\\\frac{2}{t} \\\\left\\\\|  X_0-X_\\\\star \\\\right\\\\| $, thus we conclude\n\\\\begin{align*}\n    \\\\left\\\\| \\\\mathbb{A}(X) \\\\right\\\\|^2 \\\\le \\\\frac{4}{t^2} \\\\left\\\\|  X_0-X_\\\\star \\\\right\\\\|^2.\n\\\\end{align*}\n\n\n**Q1.**\n\nYes, it is obtainable. \nWe can show that explicit schemes such as EAG/FEG converges to the optimum point closest to the starting point.\nAs proved in Theorem 3.5, we know the convergence to the closest optimum point is a property for continuous anchor schemes. \nOn the other hand, as observed in appendix D.4, we know explicit schemes like EAG/FEG also correspond to our continuous scheme when limiting the stepsize to zero. \nThus we expect the trajectories of the anchor-based algorithm to converge to the closest optimum for proper stepsizes. \nThis expectation is true and is formalized in [71 Theorem 1].\n\n**Q2.**\n\nIt's an intriguing question, and it seems to be a nontrivial issue. \nWe believe that this could be an interesting direction for future work.\n\n**Q3.**\n\nThe label `Halpern' in Figure 2 corresponds to the method in Theorem 5.1 with varying $p>0$ and $\\\\gamma>0$, whereas APPM corresponds to the method in Line 71, which is the specific case of $p=1$ and $\\\\gamma=1$ in Theorem 5.1, which uses optimal $p$ and $\\\\gamma$.\n\nFigure 2 shows that even if APPM is the method with optimal $p$ and $\\\\gamma$ for (merely) monotone condition, it may not be optimal for each instance.\nThe choice $p=1.5$ and $\\\\gamma=2.0$ may not even converge under monotone condition (see Table 2), but it outperforms APPM for specific instance in our experiment.\n\n**Q4.**\n\nIn the experiment section, we solve a compressed sensing problem in decentralized manner using PG-EXTRA [59].\nPG-EXTRA can be understood as a proximal point method with respect to certain metric defined with matrix $M$ [54], and corresponding monotone operator is actually monotone in $\\\\langle \\\\cdot,\\\\, \\\\cdot \\\\rangle_M$ where $\\\\langle x,\\\\, y \\\\rangle_M = x^\\\\intercal M y$ and $\\\\|x\\\\|_M = \\\\sqrt{x^\\\\intercal M x}$.\nTherefore, the performance measure of this problem should be $\\\\|\\\\tilde{\\\\mathbb{A}} x\\\\|_M$ rather than $\\\\|\\\\tilde{\\\\mathbb{A}} x\\\\|$ (Euclidean norm), and our theoretical guarantee applies to this new metric.\n\n**W1. Why we consider $\\\\beta(t)$ other than $\\\\frac{1}{t}$ in the first place?**\n\nThrough the analysis with general $\\\\beta(t)$, we obtain a more refined understanding of anchor acceleration, and using this understanding, we were able to design our adaptive method.\nAlso, as the answer for the Question 3, the choices besides $p=1$ and $\\\\gamma=1$ may be suboptimal when the operator is merely monotone, but the ther choices may be useful when the operator satisfies stronger properties.\n\n**W2, C1, C2.**\n\nThank you for your valuable comments. \nIn the later version, we will add the point in the limitation section that our work is for implicit schemes. \nAdditionally, we will explicitly mention the prior comparable results and the motivations up front. "}]

Author rebuttal:
# Common Response

First and foremost, we thank all reviewers for their time and feedback on our paper. We are pleased to see that most of the reviewers found our contributions to be valuable, especially the adaptive anchor method that we obtained using the insight gained through the continuous-time analyses. Although one reviewer expressed concerns regarding novelty, we believe this is perhaps due to a misunderstanding, and we clarify that Nesterov and anchor accelerations are accelerations applied to different/disjoint settings, making them not in competition with each other. We provide further details of the distinction in the individual response, and we hope this resolves the misunderstanding. 

Meta-review: The paper conducts an analysis of the continuous time equivalent of the so-called "anchor point acceleration" technique for finding zero points of monotone operators (e.g. stationary points in min-max problems). The analysis sheds light on the choice of anchor point regularization schedule and motivates a novel adaptive version of this schedule. There is a consensus for acceptance across reviewers, with which I concur.
Decision: Accept (poster)