Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization
Authors: Ruichen Jiang
Ali Kavis
Qiujiang Jin
sujay sanghavi
Aryan Mokhtari
Venue: NeurIPS 2024 poster (2024)
Keywords: min-max optimization
second-order methods
adaptive methods
saddle-point problems
variational inequalities
Primary area: optimization

Abstract: We propose adaptive, line-search-free second-order methods with optimal rate of convergence for solving convex-concave min-max problems. By means of an adaptive step size, our algorithms feature a simple update rule that requires solving only one linear system per iteration, eliminating the need for line-search or backtracking mechanisms. Specifically, we base our algorithms on the optimistic method and appropriately combine it with second-order information. Moreover, distinct from common adaptive schemes, we define the step size recursively as a function of the gradient norm and the prediction error in the optimistic update. We first analyze a variant where the step size requires knowledge of the Lipschitz constant of the Hessian. Under the additional assumption of Lipschitz continuous gradients, we further design a parameter-free version by tracking the Hessian Lipschitz constant locally and ensuring the iterates remain bounded. We also evaluate the practical performance of our algorithm by comparing it to existing second-order algorithms for minimax optimization.

Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization
Ruichen Jiang
Ali Kavis ECE department, UT Austin kavis@austin, utexas. edu
Qiujiang Jín ECE department, UT Austin giujiangiin00gall com
ECE department, UT Austin rj rjiangoutexas.co
Sujay Sanghavi ECE department, UT Austin sanghavi Gmail utexas edu
Aryan Mokhtari
ECE department, UT Austin
mokhtari Saattarrr@uutinn... utexas.ede
Abstract
We propose adaptive, line search-free second-order methods with optimal rate of convergence for solving convex-concave min-max problems. By means of an adaptive step size, our algorithms feature a simple update rule that requires solving only one linear system per iteration, eliminating the need for line search backtracking mechanisms. Specifically, we base our algorithms on the optimistic method and appropriately combine it with second-order information. Moreover, distinct from common adaptive schemes, we define the step size recursively as function of the gradient norm and the prediction error in the optimistic update. We first analyze a variant where the step size requires knowledge of the Lipschitz constant of the Hessian. Under the additional assumption of Lipschitz continuous gradients, we further design a parameter-free version by tracking the Hessian Lipschitz constant locally and ensuring the iterates remain bounded. We also evaluate the practical performance of our algorithm by comparing it to existing second-order algorithms for minimax optimization.
Introduction
In this paper, we consider the min-max optimization problem, also known as the saddle point problem:
min xERm yeR-
yx,
(1)
where the objective function f 12 x Ra + IR is twice differentiable and convex conexxe i.c., f(. y) is convex for any fixed y E R and f(x,)) -) concave for any fixed x E RT The saddle point problem (1) is fundamental formulation in machine learning and optimization and naturally emerges several applications, including constrained and primal-dual optimization [1, 21, (multi-agent) games [3], reinforcement learning [4], and generative adversarial networks [5, 6]. The saddle point problem, which can be interpreted as a particular instance of variational inequalities and monotone inclusion problems [2], has rich history dating back to [7]. We often solve (1) using iterative, first-order methods due to their simplicity and low per-iteration complexity. Over the past decades, various first-order al algorithms have been proposed and analyzed for different settings [1, 8-15). Under the assumption that the gradient of / Lipschitz, the aforementioned methods converge at rate of OL/TT), where 7' is the number of iterations, This rate is optimal for first-order methods [10, 16, 17].
Recently, there has been surge of interest in higher-order methods for solving (1) [18-23], mirroring the trend in convex minimization literature [24-28]. In general, these methods exploit higher- order derivatives
achieve faster convergence rates. From a practical viewpoint, any method
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

involving third and higher-order derivatives is essentially conceptual framework; it is unknown how to efficiently solve auxiliary problems involving higher-order derivatives, making it virtually impossible to efficiently implement methods beyond second-order [24]. Therefore, we focus on second-order methods and review the literature accordingly.
The existing literature on second-order algorithms for minimax optimization, capable of achieving the optimal convergence rate of O(1/T2-5), falls into two categories. The first group requires solving a linear system of equations (or matrix inversion) for their updates but needs a "line search" scheme to select the step size properly. This includes methods such as the Newton proximal extragradient method [18. 191, second-order extensions of the mirror-pre prox algorithm [20], and the second-orde optimistic method [21]. These methods impose a cyclic and implicit relationship between the step size and the next iterate, necessitating line search mechanisms to compute a valid selection that meets the specified conditions.
The second group, which includes [22, 233, does not require a line search scheme and bypasses the implicit definitions and search subroutines. They follow the template of the cubic regularized Newton method [29] for convex minimization and solve an analogous "cubic variational inequality sub-problem" per iteration. Despite having explicit parameter definitions, these methods require specialized sub-solvers to obtain approximate solutions to the auxiliary problem, increasing the per-iteration complexity. Moreover, both groups of algorithms rely vitally on the precise knowledge of the objective's 's Hessian Lipschitz constant.
While the above frameworks achieve the optimal iteration complexity for second-order methods, their requirement for performing a line search or solving a cubic sub-problem limits their applicability. Recently, the authors in [30] proposed method with optimal iteration complexity that requires neither the line search nor the solution of an auxiliary sub-problem. In each iteration, they compute a "candidate" next point Yt from the base point - However, unless the step size satisfies a "large step condition". which requires the exact knowledge of the Hessian's Lipschitz constant, the base point remains the same for the next iteration, slowing down the convergence in practice. Therefore, remains an open problem to design a simple, efficient, and optimal second-order method without the need for line search, auxiliary toob-probles, and the knowledge of the Hessian's 's Lipschitz constant.
Our Contributions. Motivated by the aforementioned shortcomings in the literature, our proposed framework completely eliminates the need for line search and backtracking by providing a closed- form, explicit, simple iterate recursion with a data-adaptive step size that adjusts according to local information. In doing so, we develop parameter-free method that does not require any problem parameters, such as the Lipschitz constant of the Hessian. The key to our simple, parameter- free algorithm is a careful combination of the second-order optimistic algorithm and adaptive regularization of the second-order update. We summarize the highlights of our work as follows:
1. We first present an adaptive second-order optimistic method that achieves the optimal rate of ((1/T without requiring any form of line search, assuming the Hessian Lipschitz and its associated constant is known. We introduce a recursive, adaptive update rule for the step size as a function of the gradient and the Hessian at the current and previous iterations. Our step size satisfies specific error condition, ensuring sufficient progress while growing at a favorable rate to establish optimal convergence rates.
2. Under the additional, mild assumption that the gradient is Lipschitz, we propose parameter- free version with the same optimal rates which adaptively adjusts the regularization factor by means of a local curvature estimator. This method is completely oblivious to any problem- dependent parameter including Lipschitz constant(s) and the initialization. Importantly, we achieve this parameter-free guarantee without artificially imposing bounded iterates, which is a common yet restrictive assumption in the study of adaptive methods in minimization [31-33] and min-max [34, 35] literature.
2 Preliminaries
An optimal solution of (1) denoted by (x". .y") is called a saddle point of f. as it satisfies the property
f(x",y) S [(xxy"") < f(x, for any x E Rmm y E R2. Given this notion of optimality, one can measure the suboptimality of any (x, using the primal-dual gap, i.e., Gap(x,y) := maxyeR" f(x,ý) - mingeR" f(x,y). y). However, it could be vacuous if not restricted to a bounded region. For instance, when y(x (x. y), this measure is always Cap(x, y) = too, except at
2

---

the saddle point (0. To remedy this issue, we consider the restricted primal gap function:
Gapxxy(xx == max f(x. min (()
(Gap)
yey
where X C. R and Y C. R" are two compact sets containing the optimal solutions of problem (1). The restricted gap function is a valid merit function (see [l, I1J, and has been used as a measure of suboptimality for min-max optimization [1]. Next, we state our assumptions on Problem (1).
Assumption 2.1.
The objective f is convex-concave, i.e. f(,)) is convex for any fixed y E IR" and f(x,) is concave for any fixed x E IR"
Assumption 2.2. The Hessian of f is Lz-Lipschitz, i... 1 (() (x2( & L211(x1- X2. y2)ll for any Y1), (X2, (2) R x R".
Assumptions 2.1 and 2.2 are standard in the study of second-orde methods in min-max optimization and constitute our core assumption set. That said, only for the parameter- free version of our proposed algorithm, we will require the additional condition that the gradient of f is L1 Lipschhii
Assumption 2.3. The gradient of f is Li-Liscchiz, i.e., [ - (f(x),y2)1 & L11((11 X2, Y1 y2)ll for any (11, (x2, R" x RR.
To simplify the notation, we define the concatenated vector of variables yx, Rm x R", and define the operator F : Rm++ + Rm+n at z = (x. as
F(z) = / - (x,
Under Assumption 2.1, the operator F is monotone, i.e., (F(z)) F(Z2), 2 22) 2 0 for any 21, 22 E IRT x R", Moreover, Assumption 2.2 implies that the Jacobian of F. denoted by F', is Læ-Lipschitz, i.e., for any z1. Zg E Rm x R" we have ||F' (z,) - | olop S L2 121 zell. This is referred to as pecdnd-order smoothness [20, 21J. Similarly, Assumption 2.3 implies that the operator itself is L.pLLipschit, i...
[F))
(z2) S Ln [z] z2|l for any 21, Z2 E R. x R
Finally, the following classic lemma plays a key role in our convergence analysis, as it provides an upper bound on the restricted primal-dual gap the averaged iterate. Proof can be found in [36].
Lemma 2.1. Suppose Assumption 2.1 holds. Consider fI...., OT 2 0 with Σ 0g = and T
2 (X1, yi),................. ... ZT Yr = Ein Oyy, Then, f(xr, y) - f(x YT) S E 0g (2(;) 2, 2) for any (x, y) E TRm x RR.
R x xR.. Define the average iterates as Åт Et 0,x₁ and
For simplicity and case of delivery, our algorithm and analysis are based on the operator representation of Problem (I). By means of Lemma 2.1, our derivations with respect to the operator F imply convergence in terms of the (restricted) primal-dual (Gap) function.
3 Background on optimistic methods
At its core, our algorithm is second-order variant of the optimistic scheme for solving min-max problems [12, 14, 15, 21J. As discussed in [36, 37], the optimistic framework can be considered as an approximation of the proximal point method (PPM) [38. 39]. which is given by Zt+1 z: n, (z)+1). ). To highlight this connection, note that PPM is an implicit method since the operator F is evaluated at the next iterate Z1+1- The first-order optimistic method approximates PPM by careful combination of gradients in two consecutive iterates. The second-order variant [21], however, jointly uses first and second-order information, which describe next. Its key idea is approximate the "implicit gradient" F(2(+1) in PPM by its linear approximation F F(z:) F'(z,) (z 2.) around the current point 2,, and to correct this "prediction" with the error associated with the previous iteration.
Specifically, the correction term, denoted by e, == F(z,) - F(z,-)
(1(zz-))zz 2, 1), is the
difference between F(z.) and its prediction L 1. To express in formal way,
T): F (Z)+1) R
ne F (zz + F' (z)) (Ze+1 2,)
17 F(,,) F(2.1)) F' (z (2:
Z z-11) (3)
prodiction term
correction term
The rationale behind the optimism that if the prediction errors in two consecutive rounds do not vary much i.c., 1 & 7h-1et, then the correction term should help reduce the approximation
3

---

Algorithm 1 Adaptive Second-order Optimistic Method
1: Input: Initial points Zn
21
E m I initial parameters no 0 and Ao 0
2: for =
do
3: Set: C = F(ze)) - F 1 F' (2(-1)) z(-1)
4: Set the step size parameters
L2
(I)
max
18-1,
2110:11
(II)
2(nc- 1lerll V / Arl F(z))))
124 21
21-1
5: Update: Zr41 2t 1 (Apl + + :/. (z:)) (n.F(z)) + 10-))e)
6: end for
7: return ZT+1 = (Et= ne) mn)'-E 7:21-1
error and thus lead to faster convergence rate. Replacing n: (2++1) by its approximation in (3) and rearranging the terms leads to the update rule of the second-order optimistic method:
1
(I + (z.)) (n.F(z,) 7e-1)))
(4)
The key challenge is to control the discrepancy between the second-order optimistic method and PPM. This equivalent to managing the deviation between the updates of the second-order optimistic method and the PPM update. We achieve this by checking additional condition denoted by
e == 1/ (Z F(z:)
F' (Z,)) 2.)ll S a+| 2xl1,
(5)
where a E (0, 0.5). Note that if the prediction term perfectly predicts the prox step, we recover the PPM update and the condition holds with a For the standard second-order optimistic algorithm in (4), we need to select < 0.5. The condition in (5) emerges solely from the convergence analysis.
While the above method successfully achieves the optimal complexity of (1/TL..5) there remains major challenge in selecting 7/- naïve choice guided by the condition in (5) results in an implicir parameter update. Specifically, note that the error condition in (5) involves both l) and the next iterate 1, but Z is computed only after the step size Tソ is determined. Consequently, we can test whether the condition in (5) is satisfied only after selecting the step size 7/., The authors in [21] tackled this challenge with a direct approach and proposed a "line search scheme", where 7/2 is backtracked until (5) is satisfied. While their line search scheme requires only a constant number of backtracking steps on average, it is desirable to design simpler line search-free algorithms for practical and efficiency purposes.
4 Proposed algorithms
As discussed, the current theory of second-order optimistic methods requires line search due to the implicit structure of (5). In this section, address this issue and present class of second-order methods that, without any line search scheme, are capable of achieving the optimal complexity for convex-concave min-max setting. To begin, we first present general version of the second-orde optimistic method by introducing an additional scaling parameter AІ. Specifically, the update is
Zt+1 2, (A₂I F(.)) (n.) + m--1;;)
(6)
when A, we recover the update in (4). Crucially, the regularization factor enables flexibility in choosing the parameters of our proposed algorithm and plays vital role in achieving the parameter- free design, which does not need the knowledge of the Lipschitz constant. What remains be shown is the update rule for 77 and Aς. In the following sections, we present two adaptive update policies for these parameters. The first policy is ame-search-free. explicit, and only requires knowledge ledge of T2 The second approach does not require knowledge of L2 and is completely fareeeter-free, but it requires an additional assumption that I, -ipsccii, which is satisfied when V is -Lpsschti (see Assumption 2.3).
Adaptive and line search-free -odder optimistic method (Option D) In our first proposed method, we set the parameter X, to be a fixed value À and update the parameter T/ using the policy:
4x
1/t 7/ L2l + V SaX [(

---

As we observe, 7h only depends on the information that is available at time t. including the error term norm ||e/|| and the operator norm [z,))) Hence, the update explicit and does not require any form of backtracking or line search. That said, it requires the knowledge of the Lipschitz constant of the Jacobian F' denoted by L.2. We should note that > in this case is free parameter, and we set it as À Lg to be consistent with the parameter-free free method in the next section. The update for 7t might seem counter-intuitive at first glance, but as we elaborate upon its derivation in the next section, it is fully justified by optimizing the upper bounds corresponding to the optimistic method.
Parameter-free adaptive second-order optimistic method (Option II). While the expression for step size 77 in (7) is explicit and adaptive to the optimization process, however, it depends on the Hessian's 's Lipschitz constant L2- Next. we discuss how to make the method parameter-free so that the algorithm parameters X and Th do not depend on the smoothness constant(s) or any problem-dependent parameters. Specifically, we propose the following update for X and T/::
2ad1
2/
1/1 =
where X = max A1-1:
(8)
7h-1 le + V Vn-
11 + 4a [F()))]
1 2z 1|
These updates are explicit, adaptive, and parameter-free. In the next section, we justify these updates.
5 Main ideas behind the suggested updates
Before we delve into the convergence theorems, we proceed by explaining the particular choice of algorithm parameters and the derivation process behind their design, through which we will motivate how we eliminate the need for iterative line search.
Rationale behind the update of Option I. First, we motivate the design process for updating ne and À in Option (I), guided by the convergence analysis. We illustrate the technical details leading to the parameter choices in Step by introducing a template equality that forms the basis of our analysis.
T+1 be generated by Algorithm 1. Define the "approximation error" as Proposition 5.1. Les {2: ==
e 2 F(Z++1) - F(z;) - F' f((2z)(z+)) - Zt). Then any z E IRd, we have
T
Σ n (F(2+1)) 2441 2)
Σ
A (112 2112 || 2|
Σ d 11 22-1 112
2
+ M/ (eT+1, ZT+1 - z) Mh-1 (e,, Zi - 21+1). -2-11
(9)
(A)
(B)
As we observe in the above bound, if we set X to be constant (A, A), then the first summation term the right-hand side will telescope. On top of that, if apply the Cauchy- Schwarz inequality and Young's 's incquality on terms (A) and (B) and regroup the matching expressions, we would obtain
ΣT nh (F(2411); Z.+1 2141-2) 2) S 3 || -2|-
2TTT -2/22 ΣT
(3f || 3े 1 2c+1l²))
We make two remarks regarding the inequality above. (i) By using Lemma 2.1 with 0, Et ntc
for 1 < S T, the left-hand side can be lower bounded by (I mh) (((T+11,)- (T+1).
where the averaged iterate žr+1 (8T+1.F4+)) is given by žr+1 E Th Ei=n (ii If we can show that the summation on the right-hand side non-positive and divide both sides by Et= Th, we obtain a convergence rate of (L/ ΣT 1)) for (Gap) at the averaged iterate.
To obtain the optimal rate of O(1/T1.5), the analysis guides us be more conservative with the latter point and ensure that the summation on the right-hand side is strictly negative (see Section 6 for further details). Specifically, we require each error term in the summation to satisfy "² X ||c
a²) Al|z, 2 2|2 for a given a E (0, })- Rearranging the expressions we obtain n/" ee 2 < a² x2 z, Z 1|2, and we retrieve an analog of the error condition (5) by simply taking the square root of both sides. A naive approach would be choose т}r small enough to satisfy the condition. However, since our convergence rate is of the form Σ/= Me, this approach would also slow down the convergence of our algorithm and achieve a sub-optimal rate.
- 11,.. || <
5

---

Hence, our goal is to select the largest possible ni that satisfies the condition in (5). Next, we will explain how we come up with an explicit update rule for step size nT that achieves this goal. Our strategy is quite simple; we first rewrite the inequality of interest as
Te || Ill
S 1.
(10)
0:
2 ||
Then, we derive an upper bound for the term on the left-hand side that depends only on quantities
available at iteration t. A sufficient condition for (10) would be showing that the upper bound of
nt. m/||ox+1ll
is less than 1. Note that by Assumption 2.2, can upper bound || || and write
n.L=lle.-Z--1l. 2nd As the final component, we derive an upper bound for |z, Z(+1l || that only depends on the information available at time In the next lemma, which follows from the update rule and the fact that F is monotone, we accomplish this goal. The proof is in Appendix A.2.
0 11 < De 2,,
We Wellet+11ll
2,
Lemma 5.2. Suppose that Assumption 2.1 holds. Then, the update rule in Step 5 in Algorithm I implies | ze+1ll S x. nell F(()]
x, 1 7
We combine Lemma 5.2 for A = with the previous expression and rearrange the terms to obtain
T/ L2 2z Zz+1
MeL2((1 [(:))]l || + T/- ||e,
(11)
20d
20x2
Hence, we obtained an explicit upper bound for the left hand side of (10) that only depends on terms at iteration t or before. Therefore, sufficient condition for satisfying (10) is ensuring that n.L2(1
- Iex < 1. Since aim for the largest possible choice of The intend to satisfy this condition with equality. After rearranging, we end up with the following expression:
2ax=
2ax²
(e
F [(:)) + 7h- |l,,ll)
(12)
L2
The expression in (12) is a quadratic equation in m7 and it is an explicit expression where all the terms are available at the beginning of iteration t. Solving for 77. leads to the expression in (7).
Rationale behind the update of Option II. Choosing the regularization parameter À properly is
the key piece of the puzzle. First, recall the error term ΣT= d (|zz, z/2 Z z from Proposition 5.1. When A is time- varying this summation no longer telescopes. A standard technique in adaptive gradient methods to resolve this issue (sce, e.g., [40. Theorem 13]3 involves selecting A to be monotonically non-decreasing and showing that the iterates {2, are bounded. We follow this approach, and in the next proposition, of the iterates to the optimal solution,
investigate the possibility of ensuring that the distance [|z - 12? remains bounded.
Proposition 5.3. Let (2t) T+1 be generated by Algorithm I and x² E RR x Rn be solution to Problem (1). Then,
ZT+1 2
z²11² < 2
|||| - =2113
2(+11
7t-
(er, Zt
Z(+1)
de
1=1
1=1
(A)
(13)
NT AT
(eT+11 WT41 - z²) +
A M
(er, 2z - 2²))
Ae-1
(B)
(C)
To derive the boundedness of h22 from (13), all error terms (A), (B), and (C) in (13) should be upper bounded. As detailed in the proof of Lemma C. second term (B) and it does not impose restrictions on our choice ÿ and X, To control term (A) and (C), we apply Sauchy-Schwarz and Young's 's inequalities individually; we get 11-1 A. (e,, Z, Z1+1) S
apply Assumption 2.3 to control the
oi
||e.1| ||zz - z 2|,,, and also ( + m (e,, z, =zz) <
"2
||e 12+ + -1)
X
z" 12, respectively. Combining the new terms obtained from (A) and (C) and summing from t =
T. we obtain Σi=1 x
T 2nd
l|e + ΣT_ |lz, 11 + Σ T d
1 A. 1) 112. The

---

last term will remain in the recursive formula, hence manageable. On the other hand, we need to make sure that the first two terms can be canceled out by the negative terms we have in (13). Thus, we need
to enforce the condition
2ni X141
||e 2 + illz: Z 1|2 2 Izz z++1ll S (1 2a ) || zc-1
where a E (0, 2 This condition can be simplified as
DI e4-1 X 2 Z1+1l1 S Sa² + aditillz - ze+1ll
Me|e
S
(14)
Comparing with (11), we observe that the difference is that À is replaced by A4+1- Thus, we propose to follow a similar update rule for 7) as in (7). However, recall that L2 appears in the update rule of (7), yet we do not have the knowledge of L2 in this setting. Hence, we assume that we can compute a sequence of Lipschitz constant estimates { at each iteration t. The construction of such Lipschitz estimates will be evident later from our analysis. Specifically, in the update rule of (8), will replace À by d and replace L2 by i leading to the expression
4xx2
(15)
Th exll + V (m--1 0000
le,11) + Sa L [[()))]]
By relying Lemma 5.2 and following similar arguments, we show that
mh mn/eet11l a 1z zet1ll
A Lg (e+1)
(16)
Ae+1
f(9)
where - (t-1))
2 e|
can be regarded as "local" estimate of the Hessian's 's Lipschitz constant.
[ 1 x
Thus, to satisfy the condition in (14), the natural strategy would be to set A = i and ensure that L((+1) < (t+1) Ar+1- Finally, recall that the sequence { should be monotonically non-decreasing, i.e., Ac+1 2 A for t E (T), leading to our update rule for Ae+1 as shown in (8). This 1((+1)
way, the right-hand side of (16) becomes ž.
< 1 and thus the error condition (14) is satisfied. By
replacing 1. with x and simplifying the expression, we arrive at the update rule for in (8).
6 Convergence analysis
In this section, we present our convergence analysis for different variants of Algorithm 1. We first present the final convergence result for Option (I) of our proposed method. Besides the convergence bound in terms of (Gap), we provide a complementary convergence bound with respect to the norm of the operator, evaluated at the "best" iterate.
Theorem 6.1. Suppose Assumptions 2. and 2.2 hold and let {2t] T+1
t= be generated by Algorithm I, 21 1=|| for all t 2 1. Moreover,
where X = L2 (Option (I)) and a = 0.25. Then ||z zn
S v3
Gapxxy(ZT+1) < SuPxExxy ||| z/|2
/ 2L2
F 22) 36.25 20
10
(17)
71.5
[(22))] 6| 2= V 16L2
F F(z1)
+ 290L3
1
min 1e (+.....T++1)
(18)
Theorem 6.1 guarantees that the iterates {zg J:20 always stay in a compact set {z E Rd || zz <
va 21 z²1] Moreover, demonstrates that the gap function at the weighted averaged iterate
Zr+1 converges the rate of O (T5), which is optimal and matches the lower bound [23]. Finally, the convergence rate in (18) in terms of the operator norm also matches the state-of-the-ar rate achieved by second-order methods [18], [41, Theorem 3.7], [30, Theorem 4.9 (a)).
Proof Sketch of Theorem 6. I. We begin with the convergence with respect to (Gap) in (17). The proof consists of the following steps.
7

---

Step 1:
As mentioned in Section 5, the choice of 1/, in (7) guarantees that mi|le(+1| 2 sa>lzz - -1+1
This allows us to prove that the right-hand side of (9) is bounded by a |||z| - = = L/2 ||z =
Hence, using Lemma 2.1, we have Gapx xy (ZT+1) S suP2Ex'>>' 2 ||| - = 21 11)
Step 2: Next, our goal is to lower bound Σ t=l Tr- By using the expression of 77 in (7) we can show
a lower bound on 17t in terms of ||e/]| and F (z)) as (formalized in Lemma B.2)
(1 11c 1124-2-111-- 21111 +
1 ad [F(
Ti 2 2ad ( 22>)
(19)
Additionally, we need to establish upper bound (2+)l1 By leveraging the update rule in (4) and Assumption 2.2, we show that F(2,)] S (1++)))
2 Zt 1 + ad || 21-2 || for t 2 2
9c-1
in Lemma B.2. Thus, [F(z))] can be bounded in terms of IZe Zt- /l. | 21-2 and 7h-1- In
addition, by using Proposition 5.3, we can establish that Σ |z++1 zel1 O(Iz] z 11?)
Step 3: By combining the ingredients above, with some algebraic manipulations we can show that E "f O (| - z' 1 + | (l)) (check Lemma B.3). Hence, using Hölder's inequality, it holds that El n 2 T (1 -1/2,
1/2, This finishes the proof for (17).
Finally, we prove the convergence rate with respect to the operator norm in (18). Essentially, we reuse the results we have established previously. By using the upper bounds on [[F())] and Σx
"/ from Lemmas B.2 and B.3 respectively, and combining them with the bound
ET. 12+11 20 O(Iiz z= 12²) (see Proposition B.I), we show that IT+ [[F(z)]]
O
VllVE - 7/ = (Iz) z" 1/1 21 zz 12+ X|F((z))l) Then the bound fol- lows from the simple fact that mini(....,T+)) [2))) S + E [[(())]]-
(Al|z)
Next, we proceed to present the convergence results for Option (II) of our proposed method that is freee. Note that if the initial scaling parameter X overestimates the Lipschitz constant
e S L2 by Assumption 2.2. and thus in this case the maximum in (8) will be always At- As a result, X stays constant and the convergence analysis for Option (I) also applies here. Given this argument, in the following, we focus on the case where the initial scaling parameter X1 underestimates L2, i.c., A1 < L2. Moreover, is rather trivial to establish that x < L2 for all t 2 1 using induction.
L2, we have A A for all f 2 This is because we have -
Theorem 6.2. Suppose Assumptions 2,2, and 2.3 hold and let {ZiTEz TT+1 be generated by Algo- rithm 1, where x is given by (8) (Option (II) and a = 0.25. Assume that A < L2. Then we have ||z- - xz S D for all & 2 1, where D> |z - zz 2 + D2)
1,2
21
|2 1²? Moreover, it holds that X
X
L2 (supzexxx)
F( A
+ -145| zz 1/2
Gapxxy(2TH)) (ZT+1) 5
(20)
T1.5
D
([(())]] Ai + 72.5||z1 112
min T F(zz))l
(21)
SE (2......
T
Under the additional assumption of Lipschitz operator. Theorem 6.2 guarantees that the iterates stay bounded. This is the main technical difficulty in the analysis, as most previous works on adaptive methods assume compact set. On the contrary, we prove that iterates remain bounded within a set of diameter D= = O ( + 4 -z= z" II). Compared to Option (I) in Theorem 6.1, the diameter increases by a factor of X1 i.e., the ratio between L2 and our initial parameter A₁. Morcover, Theorem 6.2 guarantees the same convergence rate of (155..5). In terms of constants, compared to Theorem 6.1, the difference is no more than (.3. Thus, with a reasonable underestimate of the Lipschitz constant, X = cL2 for some absolute constant e < 1, the bound worsens only by constant factor.
Proof Sketch of Theorem 6.2. We begin with the convergence with respect to (Gap) in (20). The proof consists of the following three steps.
8

---

Step 1: By using Proposition 5.3, we first establish the following recursive inequality:
[z++1 - 2- 2
L X
21|21 - 11 +
A--1 -
-1)-1))10 12, - =2
3,+1 - -2,l?: (22) 2
1
2=2
==1
as shown in Lemma C.I in the Appendix. Note that this upper bound for Mx41 z 112 on the right-hand side depends on ||z, 11 for all 8 S t. By analyzing this recursive relation, we obtain
|z+ 1--1--2- = S D and E ||z,- 112a-2a:1 Zo+1 11? s 2D2 for all 2 where D
L2 212
2i 1|:
x1
x
see Lemma C.2 for details.
Step 2: After showing a uniform upper bound on | 2"1,, Proposition C.3 establishes the
adaptive convergence bound Gapxxy S L2 (suPRexxy) ||z z D?) (E 11
Step 3: Following similar arguments as in the proof of Theorem 6.1, we can show Σt=1 ni
O + X ((2z))) (check Lemma C.5). By applying the Hölder's inequality Σt 1/1 2
TIE (1/()) we obtain the final convergence rate.
Finally, along the same lines Theorem 6.1, we can show that Σ X
F(z))l OD D2 + Since d S L2 and min (i.. T+1 [(z))] S
O
+ EL F(2)))l, we obtain the result in (21).
Remark 6.1. Our results can be extended to the more general problem of monotone inclusion with proper modification to the algorithm. We chose to focus on the unconstrained min-max problem for ease of presentation, so that we can better highlight the key novelties and make it accessible to broader audience. In future work, we plan to extend our results for the monotone inclusion problem.
Remark 6.2. Our proposed algorithm with Option (II) achieves the same rate as Option (I) but does not require prior knowledge of the Hessian's Lipschitz constant, making fully parameter-free However, since it requires an additional assumption on Lipschitz gradients (Assumption 2.3), the existing lower bound [23] does not directly apply to certify its optimality. That said, we hypothesize that the L,- LipLhipschizz gradient assumption should not improve the lower bound based on the existing evidence from the convex minimization setting. Specifically, [42] proves that for convex minimization
with L1 -ipschhht gradient and Lg-Lipschitz Hessian, the optimal rate is O (min{ T2 D2 1g }).
where D the initial distance. When I' is sufficiently large, the second term will become the smaller one, showing that the Lipschitz gradient assumption does not improve the optimal rate. While their construction does not imply an analogous rate for our setting in Theorem 6.2 we conjecture that the Lipschitz gradient assumption should not improve the lower bound of (11/T11155
7 Numerical experiments
In this section, we present numerical results for implementing both variants of our algorithm: the version with X; Le (Adaptive SOM 1) and the parameter-free variant (Adaptive SOM II). We also compare these with the homotopy inexact proximal-Newton extragradient (HIPNEX) method [30] and the optimistic second-order method with line search (Optimal SOM) [21]. To assess convergence
toward the solution z", we plot (zzr))l II /[[[((z))) )l?. For complete details, check Appendix D.
Synthetic min-max problem: We first consider the min-max problem in [21, 30], given by
minxeR" maxyeR" f(x,y) = (Ax - y y (Lx
which satisfics Assumptions 2.1 and 2.2. Let (x,y) Rd. with d 2n, and recall that F(z) is defined in (2). Following the setup in [30], we generate the matrix A E IRdxd to ensure condition number of 20. The vector b E Rdd is generated randomly according to AN I). We report results across various values of La and problem dimension d (for complete details, see Appendix D) and present a representative subset here. Focusing on large dimensions highlights computational efficiency, as shown in Fig. 1, where our line-search-free free methods outperform both the optimal SOM and HIPNEX in runtime. The performance gap with the optimal SOM widens as the dimension grows: line search demands more steps, especially with larger L2, with each step becoming increasingly costly due to the Hessian computation and inversion in high dimensions.

---

12"
10'
10
Adeption SGM
Adapeloo SOM
10
Adppiive SOX HIPNEX Optima:
Adaapiive SOM
10
HIPNEX
Optinaal
2102 2002 2500
4200
5000 6000
7000
1400 2100 2000 2000
(a) d = 10
(b) d = 5 10
Figure Synthetic min-max problem: Runtimes under large dimension regime with L 104.
16
15
Adiattive
Adapiive
Adeptinn SOM HPNNEX
Adaaption 90M HIPPEE
10
Outinaal SOM
Optinal 50M
107
(a) Le 10
(b) L2 10
Figure 2: AUC maximization: Runtimes under large Lipschitz (L2) regime with dimension 10
AUC maximization problem: We consider second problem where we maximize the Area Under the Receiver Operating Characteristic Curve (AUC), where we want to find a classifier 0 E IRd with a small error and a large AUC. This problem could be formulated as a min-max problem in [43-45]:
1-P P
min max x (0,,,,))
(0, a.) (b;
= 11)
(0, - 2) - --1=
N
N
2(1 + v) +
Σ 0, a:) - -11 p)ll [b: = =1) + 6 ||x1| p(1 ?
where u, E R are auxiliary variables, {(a,, | denote the (data, label) pairs (a, Bd and b, E (1), I is the indicator function, and p is the ratio of positive labels. Similar to the observations above, Fig. 2 demonstrates that both of our methods outperform the optimal SOM and HIPNEX in terms of runtime, particularly in the early stages of the execution.
Conclusion and limitations
We proposed the first parameter-free and line-search-free second-order method for solving convex- concave min-max optimization problems. Our methods eliminate need for line-search and backtracking mechanisms by identifying a sufficient condition the approximation error and designing a data-adaptive update rule for step size T) that satisfics this condition. Notably, distinct from conventional approaches, adaptive step size rule can be non-monoo.iic Additionally, removed the requirement to know the Lipschitz constant of the Hessian by appropriately regularizing the Hessian matrix with adaptive scaling parameter Xς-
The convergence rate for our fully parameter- free method was established under the additional ussumption that the gradient is Lipschitz continuous. This assumption helps control the prediction error without imposing artificial boundedness conditions. Our method ensures that the generated sequence remains bounded even without access to any Lipschitz parameters. Extending these parameter-free guarantees without the Lipschitz gradient assumption remains an open problem worth exploring.
10

---

Acknowledgments
This work was supported in part by the NSF CAREER Award CCF-2338846, the NSF AT Institute for Foundations of Machine Learning (IFML) and NSF Tripods ENCORE Institute. Research of Ali Kavis is funded in part by the Swiss National Science Foundation (SNSF) under grant number P500PT_217942.
References
[1]
Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision, 40: 40:120-11 1es1120-145 145, 2011.
[2] F. Facchinei and J.S. Pang. Finite-Dimensionas Variational Inequalities and Complementarity Problems. Springer Series in Operations Research and Financial Engineering. Springer New York, 2007.
[3] T. Basar and G.J. Olsder. Dynamic Noncooperative Game Theory. Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, 1999.
[4] Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2817-2822 PMLR, 2017.
[5] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[6] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. variational inequality perspective on generative adversarial networks. International Conference on Learning Representations, 2019.
[7] G. Stampacchia. Formes bilineaires coercitives les ensembles convexes. In Académie des Sciences de Paris, volume 258, pages 4413-4416, 1964.
[8] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[9] Leonid 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:845 848, 1980.
[10] Arkadi Nemirovski. Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004.
[11] Yurüi Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Program., (09(333):319-34) 2007.
[12] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Shai Shalev-Shwartz and Ingo Steinwart, editors, Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pages 993-1019, Princeton, NJ, USA, 2013. PMLR.
[13] Yura Malitsky. Golden ratio algorithms for variational inequalities. Mathematical Programming 184:383 410, 2018.
[14] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In International Conference Learning Representations, 2018.
[15] Yura Malitsky and Matthew Tam. A forward-backwant splitting method for monotone inclusions without cocoercivity. SIAM Journal on Optimization, 30(2):1451-142, 2020.
11

---

[16] Arkadi Nemirovski. Information- based complexity of linear operator equations. Journal of Complexity, 8(2):153-175, 1992.
[17] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-poin problems. Math. Program.. 185(1-2)) 11)1-32, 2021.
[18] Renato D. C. Monteiro and B. F. Svaiter. On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. SIAM Journal on Optimization, 20(6):2755-2877, 2010.
[19] Renato D. C. Monteiro and Benar F. Svaiter. Iteration prration-complextty of a Newton proximal extragradient method for monotone variational inequalities and inclusion problems. SIAM Journal on Optimization, 22(3):914-935, 2012.
[20] Brian Bullins and Kevin A. Lai. Higher-order methods for tion and monotone variational inequalities. SIAM Journal on Optimization, 32(3):2208 2229, 2022.
min- max optimiza-
[21] Ruichen Jiang and Aryan Mokhtari. Generalized optimistic methods for convex-concave saddle point problems. arXiv preprint #xXv:2202.096744 2022.
[22] Decksha Adil, Brian Bullins, Arun Jambulapati, and Sushant Sachdeva. Optimal methods for higher-order smooth monotone variational inequalities. arXiv preprint arXiv:2205.06167, 2022.
[23] Tianyi Lin and Michael Jordan. Perseus: A simple and optimal high-order method for variational inequalities. Mathematical Programming, pages 1-42, 2024.
[24] Yurii Nesterov. Implementable tensor methods in unconstrained convex optimization. Math. Program., 186(1-2):157-183 2021.
[25] Yurii F. Nesterov. Superfast second-order methods for unconstrained convex optimization. J. Optim. Theory Appl., 191(1):1-30, 2021.
[26] Yurii Nesterov. Inexact high-order poont methods with auxiliary search procedure. SIAM Journal on Optimization, 31 (1())2200722825 2021.
[27] Yurii Nesterov. Inexact basic tensor methods for some classes of convex optimization problems. Optimization Methods and Software, 37(3):878 906, 2022.
(28) Dmitry Kovalev and Alexander Gasnikov. The first optimal acceleration of high-order methods in smooth convex optimization. In Proceedings of the 36th International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2024. Curran Associates Inc.
[29] Yurii Nesterov and Boris Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming, 108: 177-205, 2006.
[30] M. Marques Alves, J. M. Pereira, and B. F. Svaiter. A search-free (11/13/2) homotopy inexact proximal-Newton extragradient algorithm for monotone variational inequalities. arXiv preprint arXiv:2308.058877 2023.
[31] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Leurning Research, 12(61)2111-2215, 2011.
[32] Kfr Y. Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and acceleration. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[33] Ali Kavis, Kfr Y. Levy, Francis Bach, and Volkan Cevher. Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[34] Francis Bach and Kfrr Levy. A universal algorithm for variational inequalities adaptive to smoothness and noise. arXiv preprint
2019.
12

---

[35] Alina Ene, Huy L Nguyen, and Adrian Vladu. Adaptive gradient methods for constrained convex optimization and variational inequalities. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8), 2021.
[36] Aryan Mokhtari, Asuman E. Ozdaglar, and Sarath Pattathil. Convergence rate of O(1/k) for optimistic gradient and extragradient methods in smooth convex conccve saddle point problems. SIAM Journal on Optimization, 30(4):3230-322 2020.
[37] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra- gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In Silvia Chiappa and Roberto Calandra, editors, Proceedings the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1497-1507. PMLR, 2020.
[38] B. Martinet. Régularisation d'inéquations variationnelles par approximations successives. Revue française d' l'inormattiuue et de recherche opérationnelle. Série rouge, 4(R3):154-158, 1970.
[39] R Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877-898, 1976.
[40] Francesco Orabona. modern introduction to online learning. arXiv preprint arXiv:1912.13213. 2019.
[41] Tianyi Lin and Michael Jordan. Monotone inclusions, acceleration, and closed-loop control. Mathematics of Operations Research, 48(4): 2023.
[42] Yossi Arjevani, Ohad Shamir, and Ron Shiff. Oracle complexity of second-order methods for smooth convex optimization. Math. Program., 178(332):327-36, 2019.
[43] Tianyi Lin, Panayotis Mertikopoulos, and Michael I. Jordan. Explicit second-orde min-max optimization methods with optimal convergence guarantee, 2024.
[44] Yiming Ying. Longyin Wen, and Siwei Lyu. Stochastic online maximization. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[45] Zebang Shen, Aryan Mokhtari, Tengfei Zhou, Peilin Zhao, and Hui Qian. Towards more efficient stochastic decentralized learning: Faster convergence and sparse communication. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4624-4633, PMLR, 10-15 Jul 2018
[46] Ernest K Ryu and Wotao Yin. Large-scale convex optimization: algorithms & analyses via monotone operators. Cambridge University Press, 2022.
13

---

Appendix
A Missing proofs in Section 5
A.1 Proofs of Propositions 5.1 and 5.3
Before proving Propositions 5.1 and 5.3, we first present a key lemma.
Lemma A.1. Consider the update rule in (6). For any z E IRd, we have
Th ( (2++1), Ze41 - 2) = (e((e11, Zt-1 - =) ?/--1 (er, Z2 - z) + 1/- (er, 2x - Ze41)
X
(23)
(122 z/12 || z/|² ||z z 21+1l²2).
2
Proof. To begin with, we rewrite the update rule in (6) in the following equivalent form:
1++1 2e - (A,I FFF (zr)) (1): ((.)((z)) (z:) + -e=)
(A + F). (2))) - 2,) = -17 F): ((z) - 1/t-10t
+ N F (z.) + F' (z - 2)) = =de(z; 2++1) - 1/t-10t--
Hence, by using the definition 01+1 = F(z++1) F(2z) - (()2) - -2e), this further implies that
Th: 11 me++1 + (F((F)))) + F',))( 2;)) 11+111 1e + de(ze 2z+1). (24) Moreover, we have
Te (F((FZ))) Ze41 - 2) = 1e(ee++ Ze+1 - 2) -/--1 (er, Z2+1 - 2) + do (e: - 2z+1, 22+1 2)
= 1/t (0/+1, 2 2) 7/-11 (c,, 2, - 2) + 1p- (0t, 2++1)
+ A (12z z||2 - || z|| - || 2++1 11²)
2
where we used the elementary equality (a, b) = 1/lla+ + bll2 _|lall? - - b in the last equality. This completes the proof.
Proof of Proposition 5.1. By summing the inequality in (23) from t = 1 to t = T and noting that the first two terms on the right-hand side telescope, we obtain:
T
Th (F (2(-)))) Zc+1 21111
z) (eT+1, ZT+1 -z) - (11 21 - 2) +
Th- (er, Zz 2(+1)
A (lzz 2/22 |z+1 z/|2 - |z. z 12)
1=1 2
Since T/o 0, rearranging the terms lead to (9).
Proof of Proposition 5.3. we first note that, since (2*) and F is monotone, it holds that
(F(z.+1), Zi+1 - z²) = (F(z+11) F(z"), 2 - z²) 2 O. Moreover, dividing both sides of (23) by X and letting z = z", we obtain that
5 n (F(z+1), 21+1 -2") (er+1, 2t+1 - -2") 7-- (e,, 2t - z²) + 7h-1 (er. 2z z441)
7tt X
X
dx
1 (11z:
2 |2 2²112 ||ze ze+ 2.+1113) 113)
2
Rearranging the terms, we get
2 11-1
2 2-1
< ||z 2² 2²112+
1
Tt (c++1, Z241 -z")
1 1 (ce, z²)
X,
+
71-1
(er, 2t 2(41)
5 1z. 2 11
X
14

---

By summing the above inequality from t = 1 to = T, we obtain that
2 Zr-1
1 =211 < 2
21 z²112
2 1z ze41 112 +
Σ
(er, 2t
-i+11)
t=1
(25)
(e (e,+1, Zc41 11
-z")
7
(er, Ze - z²¹)
d
Finally, we can write
T/t
(c--1,
22+1 -2')
1/-1
(ot, 2t -z") A
X
(11 1)
T1t 1r-1, Ze41 -z") M x-1
(e,, Zz - -2") +
1/- 1h- 1 21 - z²).
X
Ae- xx
Summing the above inequality from = 1 to t = yields
T
1tt
(e++1, Zt+1 -z") z²) !h-1
(er, Z, -22)
A
VT (er+1, 2T+1 z²)
1
m0 2²)
\T
A--1
Xe
1=2
The incquality in (13) follows by combining (25) and the above inequality.
A.2 Proof of Lemma 5.2
We first rewrite the update rule in (6) in the following equivalent form:
Z (A.1 + Fz (Ze41 zr)
(AeI FF (2))) (7) F (Z:) + 1e-)):)
F (2:) 1
By taking the inner product with z for both sides of the equaltiy, we obtain that
Xellzz al|lz:11 2: + m (F (2:) 2z), Ze+1 2+) = - (n F(z)) + - Ze+1 zz). (26)
Since F is monotone by Assumption 2.1, this implies that the Jacobian matrix F' (z(z satisifes (F' jz, z) for any z E IRT x _ (e.g., see [46, Section 21.) Thus, we have (F'(z,) (Ze41 21), Ze+1 2 2 0 and (26) further implies that
Ae|lz 12 < - F (zz)) + T7- Ze+1 z1) S F(n) + m--eelllzzt zell-
Hence, we obtain that ||z,1 zell S 3, [(,,)) + - S 3. n F(())( the triangle inequality.
+ x. / from
B Proof of Theorem 6.1
We first present the following key proposition, which will be the cornerstone of our convergence analysis. We establish that the iterates remain within a neighborhood of solution characterized by the initial distance (part (a)) and that optimization path has finite length (part (c)). We also present the adaptive convergence bound (part (b)). The proof is in Appendix B.1.
Proposition B.1. Suppose Assumptions 2.1 and 2.2 hold and let (z, 1 be generated by Algorithm 1,
where X L2 (Option I) and (0, 1). Then the following results hold:
(a) [z z" 11 <
- 1 - 122 for all 2
(b) Consider the weighted average iterate 2r+1 := ΣT m1 (ET= m1). For any compact
sets X CRR, y C CR", we have Gapxxy (2T+1) S La supzexxx ||21 -212 (Ei= 111)
15

---

(c) Ei=lle Ze z++1ll -
1- ||z
1 =²1
In Proposition B.I, we have shown that Σ M+41 zell² is bounded. Using that, our goal is
to express the upper bound on 1 in terms of [[+1 Zell. which will help us show that + is T
"
summable sequence. This will verify that we achieve the optimal rate of ((1/T1 We begin by and | (2:)ll in the following lemma, whose proof can be found in
computing upper bounds 4i Appendix B.2.
Lemma B.2. Fort 2 the following results hold:
(a)
S t 1z Ze-1 11
++2l1 ((())l
(b) [( $ (L+a)d
7z++1 Zz || + ad 1ze 2t 21-1/1-
7
Using the bounds established in Lemma B.2, prove upper bound on Et= lemma. The proof in Appendix B.3.
1 mi
in the following
Lemma B.3. We have
T 17a²
Σ
1 ME
+ 16a + 4
||| =211²² Yt
2
F [2))))
2(1 20
Now we are ready to prove Theorem 6.1. Besides the convergence bound terms of the (Gap) function, we provide additional bound with respect to the norm of the operator, evaluated the "best" iterate.
Proof of Theorem 6.1. By Proposition B.1,
Gap(Zr+1) S
Σ M
sup
|zo - z 1²1
2 zEX'X>'
Moreover by Holder's inequality we can show,
-1/2
Σ
T 2 1.5
(27)
n
1=0
t=
Plugging in the lower bound on Σ from (27) yields
Gap(žT+1) supxexxy
z²112
T1.5
Combining the above with the upper bound in Lemma B.3 completes the result.
Next we prove the complementary convergence bound with respect to the norm of the operator. From (36) (see the proof of Lemma B.3), we also obtain that
T+1
(1 2 - 2
T
F(z)))
<
Σ
(28)
vI 2a
T/
t=1
Combining (28) with Lemma B.3, we obtain that
T+1
(1 A z=|l
||z - 2
2(1 + 2a)2
2z
2
F(z)) <
+ ad
F((z))]
v1 2a
2(1 2a)
a²
2ax)
Finally, the result follows from the fact that m T+1)
[[())]] < Σ F(z))]l
16

---

B.1 Proof of Proposition B.1
Before proving Proposition B.1, we will formalize the error condition implied by the constant choice of regularization parameter X = X.
Lemma B.4. Consider the update rule in (6) and let ne be given by (7). Then we have me nellz Zel - 2a and me n S a
zell-
Proof. We first prove that my 1/|lz411 ze|l following quadratic equation:
S 2xx. To see this, we define 1/e as (7) by solving the
To (T [( + m/-1lleell) 2ad2
L2
Thus, by using Lemma 5.2 with x
L2, can prove that
Mallz+1 - 2, - 1/t
X (mell [(z) + 7c-1/ S 2a.
Note that ||e+1 == := [| - F FZz) - F (z.) (Z(+1 - =z)il S レ/2 |1+1 - z0l1² = =// |++1111 - zell?
by Assumption 2.2. Hence, this implies that 7/ ||+1|| S An | 20113 ax|lze+1 ze|1.
Now, we have all the necessary tools to prove Proposition B.1.
Proof of Proposition B.I. We first use Lemma B.4 to control the error terms in (9) and (13). Specifi- cally, by using Cauchy-Schwar inequality and Young's 's incquality, for 2 2 we obtain:
Mh- (e,, Zt Z141) I 1/t el i 24t1ll S adllz; 2 22 Ze+1ll
ad
a2
(29)
Zi 11-111
Ze Z1+1
2
2
Similarly, we can bound the first term by
at
a1
1/T (eT+1, 2741 2) S /r/lee++11 ||| 27+1 z/|
S
IT+T
2t 21
+
MT - z/12. (30)
Proof of (a) telescope:
Since Ae = A for all 2 1, the first summation term on the right-hand side of (9)
>
(lzz 2||² || -213)
2 z1 z||²
2
51|zT+1 -z11?
2
1=1
Furthermore, by (29) and (30), we have
mm(eT+1,2TH z) +
Mh- (e,, Ze
ZZ-111
2=
a1 < |zr+1 - 2r/12+
a1
12T+1 z/|² +
T
aa
Iz
2-1112
ad
1l 211ll²) (31)
2
2
t=2
T
I 2 |r+1 2||² +
ad
aa
Σ
1 - 2/+1/12
Hence, by applying all the inequalities above in (9), we obtain that
Σ n (F(z+1)) 24-1 - -2) 5 > |z - =||²
T
(1 - a 2T++ - 2/1² Σ
T
(1
2a)
2 ||z
2111
2
2
1=1
Since we have a E (0, 1), the last two terms in the above incquality are negative and this further
implies that Σt' 1/1 (F (2: 2c-1 z) < l| 2112 leads to
4 ||z|
2/22. By applying Lemma 2.1,
f(xT+1,8) - f(x, Fr+1) Σt ne (F 2x+1 2)
I <
T
z|12
Σr nt
2 21
m
Taking the supremum of (x,y) over X' V.
obtain the desired result.
17

---

Proof of (b) and (c) (13) telescope:
Since A X for all f 2 1, the first summation term on the right-hane hand side of
11+11 -2") 9h-1 (es, z¹¹)
1r (cr+1, Z741 2²),
A
where we used the fact that no
Using (31), we also have
AT (er+1;2T+)
2²)
Σ
1|- (ee; 2++1) 2r+1
22
1
21+1
2=2
1=1
Hence, applying the above inequality (13), we obtain:
1 1 2 |TT+1 =211 11 2- 1
2a
2z 21+1/12.
(32)
To begin with, since 1/2 the last summation term in (32) is negative. Hence, this further implies
that 1- | 2²1 1|2 S 2 |2 z= 11 which proves Part (b). Moreover, since the left-hand side
of (32) is non-negative, this also leads to 1-2a Part (c).
2 Σ/=1 ||z
zetal² < f11z1 - z z²1l? which proves
B.2 Proof of Lemma B.2
By the update rule in (8). we have
1
(I-Illlalll + V n 1/ 8aA/
8a 2
M
16a
1/ + //=1// Faz/
8a
12
F(2))]
1 < 7 || 11:4--1-11
F2,)))
2:-1 11
ad
By using (6), we can write
7. = 1711+11 77--6t - A(z(+1 - zz).
Hence, by using the triangle inequality, we have
Nell F((+1)) n7 ||0/+1/| 77-11///a || A||z||1 2 (1 aa) zill + aallzz 2,-1l1.
where we used Lemma B.4 the last inequality.
B.3 Proof of Lemma B.3
By summing the inequality in Part (a) in Lemma B.2 over f. = 1,..., T, we have
T
1z
2-11
[(())
(33)
a)
The first summation term can be bounded as second summation, we use Part (b) in Lemma B.2 to get
[z 1-11 < 4(1-2a) 1| - 2² For the
T
(1 )))
+ ad 1|: - Zz 2z-111
F(zz))l < F(Z))] +
2c-1
zell
(34)
m
18

---

Further, it follows from Cauchy- Mtuchy-Schwarz inequality that
T T-1
T
Zi41 - Z:1l 1
1++1 - -2l13,
(35)
T T-1
I T-1
T 2
1|z - 2/-2
Σ
|z - 2el12
n
1=1
Since Et
Zc+1
1-20 -1 z" 2| by Proposition B.I, combining (34) and (35) leads to
Σ
T
[(z)))
||
< (2)))) +
(1 2a 21 - 2
Σ
T-1 1
1
(36)
V1 2x
t=1
Plugging this bound back in (33), we arrive at
(1 + 2a)] 11
z
Σ
10 21
F(2)) )1 +
(37)
4(1
2x.
av 2a
1 Note that Etzo op
appears on both side of (37). To deal with this, we rely on the following lemma.
Lemma B.S. Let a, 2 0 and suppose that x S a + byxx Then it implies that x S 2a + 262.
Proof. We can rewrite the inequality as (Vī - -2)3 s aa+ b Thus, - 3 S aa+ 4 S Va 7a+ 2.
which leads to Vi S vā = x S (vā + b)² < 2a 252.
Thus, by applying Lemma B.5, we obtain that
2 ad
2(1 + 2a) -2" -
22 z 1
F(z))) )2 +
2(1 2a)
(2()
This completes the proof.
C Proof of Theorem 6.2
With the introduction of parameter-free 1). and time-varying A,, one of the main requirements of the analysis is validating the boundedness of the iterate sequence {2:} T++ in the absence of the knowledge of L22 Note that this is where we use the Lipschitz continuity of the gradient of
(Assumption 2.3) to control the prediction error. We begin by an intermediate bound on the distance to solution.
Lemma C.1. Let a E (0, ()) For any 2 1, it holds that
64a L
ds 11-1)
1) 1|z, 11
|z141 2
+ 2 2/112
Σ
(38)
X2
Ao-1
2(1
3a)
|z 20
(39)
Based on the bound above, we present an analogue of the boundedness results in Proposition B.1 below.
Lemma C.2. Define D
61a2L3
X7
+
2L3 1. For any / 2 1, we have
X
|2
1
12,+1 - 5D and Σ
11z-
20+111
1 D
2(1 - [3a)
==0
19

---

Now that we verified that the iterates remain bounded, we can state the adaptive convergence bound for the parameter- algorithm.
Proposition C.3. Suppose Assumptions 2.1 2.3 hold and let (2)) be generated by Algo- rithm I, where x given by (8) (Option (II)) and (0, Define the averaged iterate zT+1 Ei=o 7 /Et ne). Then we have
a
(2 & L2
||z z" 2² xEXXY
sup
D2
Σ
4(1
3a)
the sequel, we present the counterpart of Lemmas B.2 and B.3 for the parameter-free Option (II).
Lemma C.4. For t 1, the following results hold:
(a) 2t 2-111 + aλ, [[((z)]
(b) | 2+41 (L+a)de i
1e41 Ze
ade Tt
1|,
2z-1
Proof. The proof follows from that of its analogue Lemma B.2 up replacing by Ae-
Lemma C.S. We have
17a² + 16a +
[z] -z" =
F(Zz)]|-
4(1
3a)a²
1=
Proof. By summing the inequality in Part (a) Lemma C.4 over I,..., T. we have
Σ
Σ
2 21 11
T
F(z:)l
(40)
t=1
1=1
The first summation term can be bounded 1 "'" For the second summation, note that d S Act1, we use Part (b) Lemma C.4 to get
11
2 2 8(-3a)
D by Lemma C.2.
T Σ Ae F(2,))l
1 [(())) + Σ
1+a
a Ize 21-111
zell
(41)
\1
TJ
ne
1=1
Similarly, by using Cauchy- Schwarz inequalities, these lead
Σ
1 [F(z))) /2 3a.)
(1+2a)D
1
(42)
A1
oF
Plugging this bound back in (40), we arrive at
T
(1 + D
T-1
2
F(())) +
(43)
8(1 - (()3
/ 30)
Note that En be
appears on both side (37), Again, we apply Lemma B.5 to obtain the desired
result
Σ 1=1 m
T
1
2 3a) ad1
D
[(2z)]|+
(1+ 2 D
4(1
a² 3a)
We are finally at position to prove the convergence theorem for the parameter-fres algorithm, which essentially a straightforward combination of the previous lemmas and propositions. Similar to the proof of the constant À setting, we accompany the convergence in the primal-dual gap with the complexity bound with respect to the norm of the operator (gradient of f). Due to space constraints, present this complementary bound in the proof of the theorem.
20

---

Proof of Theorem 6.2. By Proposition C.3,
99 a²
Gapxxy(λr+1) & max L2)
|| 2z 12 xxXXX
sup
D2
Σ
n
8
4(1
3a)
t=0
Combining the ahove with the upper bound in Lemma C.5 completes the result. Moreover, from (42), we also obtain that
Σ
F(z)ll S (1+ 2a)
1
(44)
/ 3a)
1/
Combining (44) with Lemma C.5, we obtain that
T+1
F(Z)) S (1+ 20
17a 16a + 4
2
Σ
1 -2-12 1
[F(z))]l
2 3a)
4(1 3a)a?
ad
Finally, the result follows from the fact that (2....
[F(z)]]
$ E F(z))]
C.1 Proof of Lemma C.1
We begin by formalizing the error condition implied by the parameter-free frree algorithm where d is chosen as in Option (II) in Step in Algorithm 1.
Lemma C.6. Consider the update rule in (6) and let xe and me be given by (8), respectively. Then have T/ /++1 - 2e|l S 2a and ne celll S a [/+11///+111 - zell-
Proof. Similar the proof of the analogous result in the constant A, setting, note that fJ is given as in (8) by solving the following quadratic equation:
(1: [(z)) | + m- m1-ll = 2adc-
Thus, by using Lemma 5.2, we can prove that
m | zell (m [(()) + /n-1//e;|]| 2a.
To prove the second inequality, note that by our choice of \ in (8), it holds that Ae+1 2 and thus ||e++1l| <
2/|ec+1| ||
21+1
det1 ||z+1 zel12. Hence, also obtain e11el A4 1|
2g 1| <
ad++1 22-1 zel.
Moving forward, we present the following upper bound on the approximation error using Assump- tion 2.3.
Lemma C.7. Suppose that Assumption 2.3 holds. Then for any 2 we have
||e == [[(++1)) F(z:) - F' F'(()) z:) S 2L 2141 Zz
Proof. By using the triangle inequality, have ee41 || <
F [z(+1) F F(z,) )1| || FF' (z) (Z++1 Zz |I
By Assumption 2.3, it holds that [[ - Fzz,)l < L1
Z Zz and [['(z,) lop S L1. Hence,
this further implies that || ee+1 || < [[(+))) F(z:)
) +
F (zz) (ll)lll |2 zell 2L |z+11 zill
Proof of Lemma C.1. Our starting point is the inequality (13) in Proposition 5.1.To begin with, we write
1/t (e,-1, 2441 - =2")
(er, 24 x²)
X
X
(e,, Zz - z²) + ( 1 1
(45)
77 (e.-1: Zt+1 - -z")
7
xe-1 xx m- - z²).
X
21

---

Note that the first two terms on the right-hand side of (45) telescope. Moreover, note that Ae-1 S A and thus Ae-1
2 0. By using Lemma C.6, for 2 we can further bound
Te
1 ) 7- me 2²)
1
11
X 7 (n-1||e/|1e
z²1l
1--1
de
X 1
al|zz z2-1lllzze z
(46)
Ac-1
( d - 1) 2
S [zz - zz-1 122 12+ + 1 xx-1
1|z ==11?.
Hence, by plugging in (46) in (45) and summing the inequality from 1 to / T, we obtain that
11t (C++1, 2,++1,2+11
z²)
1
(ct,
2t
- 2²)
de
S 1T AT
(er+1, - =²)) + a²
Σ
T
Izz 2, 11-1 +
T
A -1)
1)² ||z, - z =²1
Ar-1
t=2
t=2
where we used the fact that 170 Lemma C.6, we can bound
0. Moreover, by Cauchy-Schweer inequality, Lemma C.7, and
MT XT
2L1TT
(eT+1) 2T41 -z") S
eT
2TT1
22 s
1T++1
2T aT||||tT z
AT
4a
|rr+1 2"|l-
Ar
Furthermore, for the last error term in (13), we use Cauchy-Schward inequality, Lemma C.6, and Young's 's incquality upper bound
7h-1 (er, 2z - 21-1) S 1h-1
|e - -2+1|| S al|2: - 2z-1 |||2++11 - zzell
A
d
1z 11-111 + 2 21l2441 2el1?
Combining all the inequalities above with (13) in Proposition 5. we arrive at
1TT+1
xz
|2
2
1|
T
Ze
21+1
4aL1
T
|2T+1
1
111
2
2
Ax
2m1
2
Σ
d
-1 1)
2
12, - =211 + a
Σ
|z
2
1-1
Since 1. we can bound a² 9. Rearranging the terms, we obtain
10T+1 - 1-
4aL1 AT
|TT1
2"1l 5
22 12
T
At
- 1)
1 - 12
2
2
2=
1
30
|z
zell?
t=1
Now we can complete the square and write the left-hand side as
4aL1
1
4aL1
8a² Av
2 1
2T+
z²1 =
||2T+]
=z"l1
X2.
1 2²112
16a L3 X/.
1
where we used the elementary inequality that (a b)2
2 1 11. Combining the above two
inequalities and changing T to f leads to the desired result.
22

---

C.2
Proof of Lemma C.2
Define the auxiliary positive sequence {de h22 as follows:
64 13 +2|121 X
1o---22-0 2"11?, dit1 64a L2 -
X² + 2||11 z
Σ
1--1 - 1)
Aa
2
de.
s=2
Then by using induction and Lemma C.I, we can easily prove that Moreover, from the above recursive relation, for 2 1, we have
|
-
z'll
S de for all t 2 2.
22 de = 64
+
- 1
de.
X
X
A--1
Moreover, since X 2 1-- by (8), we have
d -1
2
X
1+
1
2
+
A--1
1-1
x=1
X2
Hence, this implies that
1
X
+
&
17
37_1
X
L+
df
64a211
dc
64a 1
1
<
+
X2-1
X2
X
1
A7
17
x2-1
By summing the above inequality from
2 to
T, we obtain that
d2
64a L3
1
2 21 2
112
64a 2 L3
x1
X
X
X
This implies that _
212 x
z
1|2
+
64a LL x
Since AT S max (1, Lid. we obtain the final
result.
Moreover, by rearranging the terms in (38), we also have
64a L
As
2(1 3a)) Σ 12. 2041
2
2²122
+
Ag-1 -1 1)
||2, x='1
Xo
2=2
64a L
A - 1)
2
+ 2/|1z1
2²11
+
de
X?
Ag-1
2
dz S D²
Dividing both sides by 2(1 3a) finishes the proof.
C,3 Proof of Proposition C.3
Our starting point is the inequality (9) in Proposition 5.1. To bound the first summation on the right-hand side, we write
X1 22 z112-
AT 2
T X
(liz z|/2 1zt11 - =2
|TT1 - 2|/2+ -2|
1z
z/12
2
t=2
Moreover, since d 2 A1-1 for any t +2 2, we have
A \=-1
T
2 22 x/12 < Σ
(A. - A1-1 - -21 + 1| z 112)
T
< Σ ()z - >x_ (D² + +1|z - faa=x111"" 1²1)²)
t=1
(Dr - X1) (D² +1z - =111
23

---

Since
A
2 21 z|| < X1 (lzz - -z- ---1z-z111 - X (D2 + - 2²11²), (=|z-z211)) we obtain that
Σ (lzz z11² - |,+ - -2|1² S AT (D² + 1|z - x I2²) - Ar 2T+I =|1
Furthermore, we can use Lemma C.6 to control the error terms. By using the Cauchy-Swharz inequality and Young's inequality, for 2 2. we have
1/
21 +
1/1 1/ 2, - -21t2) S 1/--1 e; ||| 2 - -24+1 || -
||e211
- 2041l1
24
2
Xe
X ||z zi+1ll
||z
-z1-112
2
2
Q XT
) ||z z(+1
1|z 21-1
2
2
where we used Lemma C.6 in the second in the third inequality and the fact that (2e is non- decreasing the last inequality. By summing the above iequality from t = 1 to T, we obtain that
a 2²\TT
T
Σ (c,, 2t 2141) S
21-1
11
zz ze+1l1
2
a² XT
T
Ae
D²
+
1z
2++1/?
4(1 - 3a)
2
t=2
where we used Lemma C.2 in the last inequality. Similarly, using Cauchy-Schwarz and Young's inequalities, we can also bound
AT 2
2 /er-
mr Pr(e,+1, 2T+1 z)
z||² +
2XT
21,
80212 2T S
Using Lemma C.7 and Lemma C.6, we further have Combining all the inequalies above in (9), we obtain that
2x,-
1/
ITT+1
Ar
AT
D ne (F(4+1)) (),1),,,... 26+1 2) s Ar (D² + 1
2T
2
11 21+1 12
2
tml
8a L2
XT
+
B741
z 2 +
D2
2| Z1+1
2
AT
4(1
3a)
a²
8a L3
< Ar|lz - 1/
1
\x D² + AT
4(1 - 3a)
Finally, we used the fact that Xr S 11. L2] and rest follows simiarly as in the proof of Proposition B.1.
8a²
24² < 112 -
1 XT. The
dr
D Omitted numerical experiments
We solve the linear systems in the subproblems of second-order methods exactly via MATLAB linear equation solver. The hyper-parameters for methods in the prior work are tuned to achieve the best performance per method. Specifically, for the HIPNEX method in [30], has aperrparrmeter
Implementation details:
(0, 0.5), which we choose in the interval |0.05, 0.1, 0.15, .... 0.45) for the best performance. Other hyper-paramen Optimal SOM, the initial step size is set to be I as prescribed. Their algorithm has two line-search hyperparameters a and B3. Note that their a is the same as ours, and we search for the best choice of a and / for their algorithm from the interval [0.1, ......... 0.9]. We use the combination that achieves ...
are determined by the formulas from [30]. For the
the best empirical result.
Our first proposed algorithm in Option (I) does not require any tuning. We initialize our fully parameter-free method (Option (II) using a heuristic, which essentially eliminates the tuning of its parameters, After we choose the initial point 2o. we generate another random point žo which is
24

---

Adaptive
Adaptive
Adaptive SOM 11
Adagtive SOM II IPNNEX
IIIPNXX
Optimal SOM
Optimal SOM
10
107
50
100
150
200
250
300
350
10
20
30
40
50
80
70
50
50
Number of Sterationn T'
Namber of iteratãons T
(a) = 10 L2 = 10
(b) d = 50% L2 = 10".
Figure 3: Synthetic min-max problem: convergence comparison with respect to iteration complexity.
10
10
Adaptive SOM
Adaplive SOM
HIPNEX
Optinal SOM
Adeptive SOM T
10
Adaptive
10
HIPNEX
Optinnal SOM
Number incrations
(a) 10 Le 102.
(b) d 10 Le 10
Figure 4: AUC maximization: convergence comparison with respect to iteration complexity.
close to the initial point. Then, using those two points we compute a local estimate to the Lipschitz constant L2 for the values of λo as Åo 2 F(,)) F(zo) (xo za) Empirically, observe that -zal
this heuristic strategy is competitive and works well across different problem settings and instances.
Finally, we initialize the algorithms at the same point Za (o) Rdd, drawn from the
multivariate normal distribution.
Additional experiments: In Figures and we compare the performance among all 4 methods with respect to the iteration complexity for the synthetic min-max problem and the AUC maximization problem, respectively. Note that those plots do not account for the cost of linear search and back- tracking; they are presented solely to complement Figures and 2 for a complete comparison of the methods. For both problems, adaptive SOM shows slightly better performance than Adaptive SOM I1, consistent with the fact that Adaptive SOM I uses the exact Hessian Lipschitz parameter, while Adaptive SOM estimates it. As expected, the Optimal SOM method, which uses line search to pick the largest possible step size, has the best convergence. However, the performance of our adaptive line search-free method (Adaptive SOM I) and parameter-five method (Adaptive SOM II) is only slightly worse. Additionally, both of our methods outperform the HIPNEX method.
we measure the runtime of the algorithms. When the dimension is small, the relative performance of the methods in terms of runtime is similar to that of in Figure 3 in terms of the number of iterations. On the other hand, in the high dimensional regime, the performance of the Optimal SOM becomes worse against other algorithms in the initial stage because they need to solve the linear equation multiple times during the backtracking line search scheme, which is computationally expensive and time-consuming when the dimension d is large. Also observe that as the dimension increases, our methods perform gradually better than the line search-based approaches, which supports claims efficiency.
In Figure
25

---

Magglinn SORT SEPRES
KIPHEX
SEPREX Ciinn
Jalena ROM
Oytana
Tlanto
T1er10
(a) d = 10 L
(b) d = 10 L 10
d 10a 10a
Adayciie
Aulaetine
Adkiccine SUNE BEPNEX Oytans
SON
BISEX Oyszas
Oytana SON
Tha
(d) d = 10 L 1.
(c) d = 10 T 10
(f) d 10 T 10
12
Adasha 500
Adaupta 500d
Adaata
HIPNER
HUPMER
RIPMEX
109
109
1090
150
10
10
50
373
(g)
10 L
(h) d 10 L 10
(i) d =
10
L
10
Figure 5: Synthetic min-max problem: additional plots for the convergence comparison with respect runtime.
Ag
by Le
10
5e
Ge
10/10
Ap Dandomm
10
Rancom
10
10"43
40
100 120
140
100
120 120
200
Number of iturations
Number of Beratione
(a) L2 102.
(b) Lg = 10
Figure 6: Runtime comparison for the parameter-free free method (Option (II) for solving the min-max problem in Section (d 102) with different initialization Ag
As a complementary result, we tested the sensitivity of our parameter-free method (Option (II) to the initialization of o and reported the results in Figure 6. Specifically, considered the first min-max problem in Section 7, where L2 = 10a and d = 102. Varying the initial choice of Ao from 10 to 0.05, Figure shows that our method exhibits consistent performance. We also tested heuristic initialization procedure as discussed above. The numerical results verify that our method is robust to initialization and our heuristic strategy is competitive and works well across different settings.
26

---

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

---

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

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have uploaded our Matlab codes which generate all the empirical results in the numerical experiments. We have also included the instructions to reproduce all the experimental results Section 7 which could be found in Appendix D.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
piblice/uiides/CoeeSubbbee sow.uummssssoooocccccoooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. wttpccccppppcccttccccccccccccclt wwwpic/ggig///ieeeeeeeee httgg//ee/eeeuuummiieeeeeeeeeeee www.//oodieiiiioooorroroo swi.iiissssiiiiiiioooom.i for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have specified how our algorithms and baselines are initialized and how the hyperparameters are selected. Please check details Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
29

---

Justification: This paper focuses on a deterministic optimization problem and the algorithms considered not have any source of randomness. The objective loss function used in the numerical experiments requires random matrices A and random vectors b. The initial vectors 2g are also generated randomly. We have presented all the details of the random generations of these matrices and vectors. However, all the optimization methods presented in our experiments are deterministic algorithms. There no need to report the corresponding error bars. Please check details in D.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We only need to install the Matlab software on our personal computer with normal CPU to run codes and reproduce the experiments, do run any form of large-scale training.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / http///eurripp.eeeee cttpiipsp..ppppieee
Answer: [Yes]
Justification:
The research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
30

---

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

---

Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's ' creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
32

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
33


Reviews:
[{"review_id": "ZA342KjZSO", "reviewer": "Reviewer_4DVD", "summary": "The authors present a new second-order method for convex-concave min-max optimization based on the optimistic gradient method but modified to work with second-order information. The authors first propose a variant that requires the value of Jacobian Lipschitzness $L_2$ and then introduce an additional parameter-free variant that does not require any hyperparameters. The proposed method obtains the optimal rate for this setting and appears to be quite practical. Finally, the authors test their method on a toy problem and compare it to other second-order methods for the same problem, where we can see the proposed method to perform the best.", "questions": "1. I do not see any mention of the error feedback technique, but the method resembles it a lot. Did it motivate the authors in any way?  \n2. Can a faster convergence rate of $O(1/T^2)$ be established for the same method when we specialize the problem to minimizing a convex function, as has been established for regularized Newton methods?\n3. Why do you need to study specifically min-max problems?\n4. Is Assumption 2.3 needed only to bound the iterate norms?\n5. You assume the gradients to be Lipschitz, doesn't it mean that the $O(1/T^{1.5})$ lower bounds that you cite are no longer applicable since they are established for the class of operators with Lipschitz Jacobian?", "limitations": "I find the limitations section to be right on point.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The authors obtained the optimal rate for the studied problem with a practical method, which doesn't require solving complicated sub-problems. Furthermore, the authors designed a parameter-free version which appears to be very practical.", "weaknesses": "1. Unlike previous work on second-order methods for minimization and variational inequality, this work requires the gradients to be Lipschitz. I'm not even sure if that makes the method optimal in the class since usually the lower bounds are established without this extra assumption.\n2. The problem might lack applications in machine learning. Min-max problems became popular recently due to a period of time when GANs were used, but it's a bit unrealistic to expect a second-order method to be useful in high-dimensional applications.\n3. I think some related work is missing in terms of the algorithm design, in particular, error feedback papers (since this work uses error vectors) and papers on regularized Newton methods (since this work also tries to eliminate line search).\n4. Some more practical experiments would have been welcome here.\n## Minor \nThe light green in the plots is very difficult to see with the white background, I'd suggest changing the colors in the plots based on modern standards for figure formatting  \nIn Section 7, vectors $x$ and $y$ should be made bold to be in line with the formatting style of the rest of the paper  \nSome equations, in the main body and in the appendix, are missing punctuation, e.g., lines 178, 203, 207, 452, 454, 488, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1 This work requires Lipschitz gradients thus lower bounds are not applicable.**\n\n**R1** First, we would like to highlight that our first method (Option I) does not require Lipschitz gradients and achieves the optimal rate for its setting. However, the parameter-free version (Option II) does require the Lipschitz gradients. Consequently, we agree that the existing lower bounds do not apply when Assumption 2.3 is in play. We will add a paragraph to clarify this. \n\nHowever, we would like to propose educated guesses based on analogous lower bounds in convex minimization. Arjevani et al. (2019) shows that for convex minimization with Lipschitz gradient and Hessian, the optimal rate is $O(\\min\\\\{T^{-2},T^{-3.5}\\\\} )$. Since the lower bound for minimizing a convex function with only Lipschitz Hessian is $O(1/T^{3.5})$, the Lipschitz gradient assumption does not improve the lower bound. Similarly, we believe this additional assumption for min-max optimization would not lead to a rate improvement. We will include a remark in our revised version.\n\n---\n**W2 Second-order methods may not be useful in high-dimensional applications.**\n\n**R2** We acknowledge that second-order methods might have limited use as the dimension of the data and the model increase. However, there are scenarios where they could be beneficial.\n\nSecond-order methods can converge in fewer iterations, though they incur the extra cost of calculating the Hessian and its inverse. Thus, there is a trade-off between convergence rate and per-iteration cost. In cases where gradient evaluation is expensive, second-order methods may be more favorable than first-order methods, as they require fewer iterations and gradient queries.\n\nTo improve implementation efficiency, techniques like computing the (inverse) Hessian-vector products (HVP) can significantly reduce costs. [Dagréou et al., 2024] showed that the cost of HVP is less than twice the cost of gradient computation. Thus, we may scale our method to high-dimensional problems when combined with such techniques - please also check out our response **A3** to **Reviewer GGjT**.\n\n---\n**W3 Some related work is missing.**\n\n**R3** Regarding regularized Newton’s methods, we covered the relevant papers for min-max optimization to our knowledge [18,19,20,21,22,23]. We understand that our reviewer might also refer to regularized methods for convex minimization. We only cite the core work [29], and we will happily add the following on (accelerated) cubic methods [Nesterov, 2008; Jiang et al., 2020] and quadratic regularization variants [Mischenko, 2021; Antonakopoulos et al., 2022].\n\nRegarding error feedback, we were not initially aware of this line of work and built our method purely based on optimistic methods, which have been studied since 1980 [9] and have become popular recently [12, 14, 15]. However, we agree one could draw a high-level connection. Focusing on the pioneering work [Seide et al., 2014], error feedback algorithms keep an aggregated vector of errors from an “approximation” step such as compression/quantization. This **aggregated** error is added every iteration to correct the update of the local point. We highlight that our optimistic approach focuses only on the difference between the current and the last iterate, while error feedback vectors accumulate the entire history of errors. We will include a discussion on error feedback algorithms and their relevance. Thank you for making us aware of this.\n\n---\n**W4 Practical experiments.**\n\n**R4** We have included a new experiment for the problem of maximizing the area under the ROC curve. We also repeated the experiment in our paper with higher dimensions and larger Lipschitz constants. Our new plots indicate a clear advantage for our algorithms compared to optimal SOM and HIPNEX once the dimension and $L_2$ increase. Please check out our new plots in the rebuttal PDF and the discussions in our global response.\n\n---\n**Q1 Error feedback technique.**\n\n**A1** Please check our response in **R3**.\n\n---\n**Q2 Can a faster rate of $O(1/T^2)$ be established for minimizing a convex function?**\n\n**A2** This is an excellent question. To our knowledge, no second-order optimistic method for convex minimization, even with line search, achieves a rate better than $O(1/T^{1.5})$. Our current analysis gives this same rate for the convex minimization setting. However, quadratic regularization of Newton’s method with adaptive regularization [Mishchenko, 2022] and cubic regularization of Newton’s method [29] achieve a faster rate of $O(1/T^2)$. Therefore, we conjecture that a minor modification of our method should achieve the same rate. This is a direction we are currently pursuing.\n\n---\n**Q3 Why study Min-Max?**\n\n**A3** Min-max problems have been studied for several decades, long before the popularization of GANs. They have been explored in various formulations, such as variational inequalities, across fields like game theory, economics, and multi-agent learning. With the recent interest in second and higher-order methods, many open problems in min-max optimization need new algorithmic designs. We believe our adaptive parameter strategies offer a solid step forward by providing a new framework to bypass line search, applicable to minimization algorithms as well. We will include a thorough discussion on min-max problems, their relevance, and the implications of our design for other fields.\n\n---\n**Q4 Assumption 2.3.**\n\n**A4** The reviewer is correct: this assumption is only needed to ensure iterates remain bounded. Note that many papers on parameter-agnostic algorithms **artificially** assume bounded iterates (see [32, 33,34, 35, Antonakopoulos et al., 2022]). We addressed this by replacing boundedness with the milder assumption of Lipschitz gradients. Although this complicates the analysis, we believe it is an important step forward.\n\n---\n**Q5 The $O(1/T^{1.5})$ lower bounds are not applicable.**\n\n**A5** Please check our response in **R1**.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NUEEprEZqS", "reviewer": "Reviewer_gLyW", "summary": "This paper consider solving convex-concave minmax problems using second order optimization method. A modified adaptive Optimistic algorithm by approximating the proximal point method using second order information is proposed. It is shown that this method can achieve the optimal convergence rate. Moreover, comparing with the previous second order methods, the method in this paper avoid the line search process and can avoid the precise knowledge of the Lipschitz constant used in finding suitable step sizes.", "questions": "(1). As in the weakness part, can the author provides more explains on the advantages of Adaptive SOM than optimal SOM?\n\n(2). From Figure 2, it seems Adaptive SOM methods will not keep decreasing after some time node. Is this the case? What will happen if we add the iterations of optimization?\n\n(3). From the work of (Mokhtari er al.,) both the optimistic and extra gradient methods can be put in a single framework of approximating the proximal point method. Can the authors provide some comments on the possibilities of using the second order approximate extra gradient method to construct algorithms?", "limitations": "There is no potential negative societal impact from this work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(1). The paper is well written. The basic mechanisms of the proposed algorithms and the difficulties of their analysis are clearly stated at the beginning of the paper.\n(2). The motivation of this work that avoid the seemingly complex process of line search or knowledges of the Lipschitz constant is convinced. Moreover, the proposed algorithm, especially the (Option 2) method achieve this goal, although the additional assumption on the Lipschitz conditions on the gradient are assumed.", "weaknesses": "(1). Beside the theoretical advantages of the proposed methods and optimal SOM method, it is questionable that whether the proposed method has particle advantages compared to optimal SOM. From the experimental results, it seems both the convergence rate of optimal SOM (in Figure 1) and computational times in long term (in Figure 3) are better than the proposed adaptive SOM methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1 Can the authors provide more explanation on the advantages of Adaptive SOM than optimal SOM?**\n\n**A1** In terms of convergence rate (# of iterations needed to reach an accuracy), one cannot expect our method to beat the optimal SOM. This is because the optimal SOM leverages the line search scheme to pick the largest possible step size, while our method achieves the same rate (up to constants) by **removing** the line search. Instead, our goal is to design a method that is easy to implement with minimal effect on performance.\n\nIndeed, there are scenarios where our method has better performance. Since our methods do not require line search, we expect them to be easier to implement and exhibit faster runtime, particularly when $L_2$ is large and, more importantly, when the problem is high-dimensional. When $L_2$ is large the line-search scheme might require several backtracking steps, and each step would be costly when $d$ is large due to the computation of Hessian and its inverse.\n\nSpecifically, Figure 3 in our submission demonstrates the effect of increasing $d$ and $L_2$. Taking $10^{-15}$ as an acceptable accuracy, our methods reach the target faster than other methods when the problem has large $L_2$ and dimension. Furthermore, we have conducted new experiments with larger Lipschitz constant and higher dimensionality. Please check out Figure 1 in the rebuttal PDF and the explanations we provided in the global response. With increasing dimensions and Lipschitz constant, we observe that our methods show significant gains against optimal SOM and HIPNEX.\n\n---\n**Q2 From Figure 2, it seems Adaptive SOM methods will not keep decreasing after some time node. Is this the case? What will happen if we add the iterations of optimization?**\n\n**A2** Let us highlight that Figure 2 studies the case where the Lipschitz constant is very small (L=1), which is in favor of the line-search methods. Optimal SOM can easily pick a large step size via the line search and converge faster, whereas our adaptive methods take a more conservative approach with smaller step sizes. Our methods will eventually reach the same error as optimal SOM with more iterations. \n\nMoreover, Figure 2 reports the performance against the number of iterations, which does not display the cost of line search. The negative effect of increasing the Lipschitz constant **in runtime** for optimal SOM can be observed through Figure 3 (g) -> (h) -> (i). \n\n\n---\n**Q3 From the work of (Mokhtari et al.,2020) both the optimistic and extra gradient methods can be put in a single framework of approximating the proximal point method. Can the authors provide some comments on the possibilities of using the second-order approximate extra gradient method to construct algorithms?**\n\n**A3** This is an excellent question. Integrating our technique with the extragradient (EG) framework to remove the line search turns out to have some technical issues. Specifically, one of the fundamental components that help us avoid the line search is the data-adaptive recursion for $\\eta_t$, and finding the respective formula for EG is the first challenge. Let us explain briefly without the proof details. \n\nEG computes an intermediate sequence, which we can call $z_{t+1/2}$, and uses the gradient information at this middle point to achieve the next point $z_{t+1}$. It is possible to propose a choice of $\\eta_t$ that depends inversely on $\\\\|F(z_t)\\\\|$, which implies that, to lower bound $\\eta_t$, we need to find an upper bound on $\\\\|F(z_t)\\\\|$. However, we are only able to upper bound $\\\\|F(z_{t+1/2})\\\\|$ instead of $\\\\|F(z_t)\\\\|$. This discrepancy prevents us from establishing the same convergence guarantee as in this paper. Nevertheless, this is a truly interesting question (also for minimization problems) and we are actively exploring whether a unification is possible.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KtSrsKazDz", "reviewer": "Reviewer_w2ph", "summary": "This paper proposes adaptive, line search-free second-order methods with an optimal rate of convergence for solving convex-concave min-max problems. By defining the step size recursively as a function of the gradient norm and the prediction error, they eliminate the need for line search or backtracking mechanisms. Additionally, the approach does not require knowledge of the Lipschitz constant of the Hessian.", "questions": "1.See Weakness above.\n2. In Equations (6) and (7), \\alpha appears in the update. However, \\alpha is not mentioned in Algorithm 1. Can you explain its role in the algorithm? Besides, how is \\alpha set in the experiments?\n3. In the experiments, it is mentioned that “all the hyper-parameters are tuned to achieve the best performance per method.” Can you provide details on the tuning process for these hyper-parameters?", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The algorithms presented in the paper are novel. They eliminate the need for line search and backtracking by providing a closed-form, explicit, and simple iterate recursion with a data-adaptive step size.\n2. The authors offer a clear explanation of how they developed this update.", "weaknesses": "The limitation of using line search is not clearly demonstrated. For example, it is unclear if using line search would incur higher computational costs and take more time. This limitation should be illustrated with experimental results. Specifically, in the numerical experiments, the Optimal SOM method shows the best convergence rate. Therefore, it is important to show how these novel algorithms outperform the Optimal SOM method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1 The limitation of using line search is not clearly demonstrated. For example, it is unclear if using line search would incur higher computational costs and take more time. This limitation should be illustrated with experimental results.**\n\n**A1** We believe our reviewer would agree with us that we cannot expect our method to beat the optimal SOM in terms of convergence rate (# of iterations needed to reach an accuracy). This is because the optimal SOM leverages the line search scheme to pick the largest possible step size, while our method achieves the same rate (up to constants) by **removing** the line search. Instead, our goal is to design a method that is easy to implement with minimal effect on performance.\n\nIndeed, there are scenarios where our method has better performance. Since our methods do not require line search, we expect them to be easier to implement and exhibit faster runtime, particularly when $L_2$ is large and, more importantly, when the problem is high-dimensional. When $L_2$ is large the line-search scheme might require several backtracking steps, and each step would be costly when $d$ is large due to the computation of Hessian and its inverse.\n\nSpecifically, Figure 3 in our submission demonstrates the effect of increasing $d$ and $L_2$. Taking $10^{-15}$ as an acceptable accuracy, our methods reach the target faster than other methods when the problem has large $L_2$ and dimension. Having that said, we fully acknowledge your criticism that we should highlight the advantages of our linesearch-free design with more elaborate experiments. \n\nTo this end, we have conducted new experiments with larger Lipschitz constant and higher dimensionality. We kindly ask you to check out **Figure 1** in the **rebuttal PDF** and the explanations we provided in the global response. With increasing dimensions and Lipschitz constant, we observe that our methods show significant gains against optimal SOM and HIPNEX.\n\n---\n**Q2 In Equations (6) and (7), $\\alpha$ appears in the update. However, $\\alpha$ is not mentioned in Algorithm 1. Can you explain its role in the algorithm? Besides, how is $\\alpha$ set in the experiments?**\n\n**A2** Thank you for raising this point. The reason that $\\alpha$ does not appear in Algorithm 1 is that we set $\\alpha = 0.25$ to simplify the expression. The parameter $\\alpha$ stems from the condition in (4), and it controls the approximation error in the second-order optimistic method. Note that, unlike the Lipschitz constant, it is a **free** hyperparameter in our algorithm.  Our method with Option I needs $\\alpha \\in (0, 1/2)$, and the parameter-free version (Option II) requires $\\alpha \\in (0, 1/4)$. We can simply select it as $\\alpha = 1/4$ to unify, which is what we do in the theorems and experiments.\n\n---\n**Q3 In the experiments, it is mentioned that “all the hyper-parameters are tuned to achieve the best performance per method.” Can you provide details on the tuning process for these hyper-parameters?**\n\n**A3** Thanks for the question. For our first adaptive and line search-free second-order optimistic method, we simply choose $\\lambda_t = L_2$. For the parameter-free method, the only hyper-parameter is $\\lambda_0$, and we use a heuristic initialization for our method. We choose an initial point, $z_0$, and generate a second random point $\\hat{z}_0$ which is close to $z_0$. Then, we compute the local $L_2$ estimate to initialize $\\lambda_0 = 2 \\\\| F(\\hat z_0) - F(z_0) - \\nabla F(z_0) (\\hat{z}_0 - z_0)  \\\\| / \\\\|\\hat{z}_0 - z_0 \\\\|^2$. Note that we do not tune $\\lambda_0$ as a hyper-parameter but use a simple initialization rule, which is in parallel with the proposed update recursion for $\\lambda_t$ in Algorithm 1, line 4.\n\nFor the HIPNEX method in [30], it has a hyperparameter $\\sigma \\in (0, 0.5)$, which we choose in the interval $[0.05, 0.1, 0.15, …, 0.45]$ for the best performance. Other hyper-parameters are determined by the formulas from the paper [30]. \n\nFor the Optimal SOM, the initial step size is set to be unit as prescribed. Their algorithm has two line search hyperparameters $\\alpha, \\beta$. Note that their $\\alpha$ is the same as ours, and we search for the best choice of $\\alpha$ and $\\beta$ for their algorithm from the interval [0.1, 0.2, …, 0.9]. We use the combination that achieves the best empirical result.\n\nThank you for raising this point and we will add the above details to the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jeXPQCuI4z", "reviewer": "Reviewer_GGjT", "summary": "This paper introduces adaptive, line search-free second-order methods aimed at solving convex-concave min-max problems. The proposed algorithms use an adaptive step size, simplifying the update rule to require solving only one linear system per iteration. The paper presents two main contributions: an adaptive second-order optimistic method that achieves an optimal convergence rate of O(1/T^1.5) and a parameter-free version that does not require knowledge of the Lipschitz constant of the Hessian. The algorithms are evaluated against existing methods, demonstrating practical efficiency and optimal rates.", "questions": "1. How robust are the proposed methods to deviations from the assumed Lipschitz continuity of gradients and Hessians?\n2. Can the parameter-free method's performance be significantly impacted by the choice of initial parameters?\n3. How does the proposed approach compare to recent advances in machine learning applications, such as training GANs or solving reinforcement learning problems?", "limitations": "The authors pointed out the limitations that missing exact knowledge of the Lipschitz constant can slow down the convergence, and achieving the same parameter-free results without the assumption of Lipschitz continuous gradient remains an open problem.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The introduction of adaptive, line search-free second-order methods with optimal convergence rates for convex-concave min-max problems is a significant contribution to the field.\n2. The paper provides both a parameter-free version and a version requiring minimal problem-specific information. The development of a parameter-free version of the algorithm that adapts based on local information without requiring the Lipschitz constant is noteworthy.\n3. The contributions are clearly stated and proved to be the optimal through theoretical analysis and empirical results.", "weaknesses": "1. While the parameter-free method is innovative, it may still require careful tuning of initial parameters in practice.\n2. Although the numerical experiment shows a promising result, it is limited to specific problem settings and may not generalize across diverse optimization tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1 While the parameter-free method is innovative, it may still require careful tuning of initial parameters in practice.**\n\n**R1** This is an important observation, and thanks for bringing this point up. We agree that removing the necessary parameters will not come for free and we need to initialize $\\lambda_1$ with an estimate of the Hessian's Lipschitz constant. Let us briefly discuss how the parameter-free method behaves for different initializations and also propose a simple initialization technique.\n\nObserve that $\\eta_1 = O(\\sqrt{\\lambda_1})$ and $\\eta_t = O(1 / \\eta_{t-1})$ from Eq. (7). From this simplified view, we observe that the step sizes have a self-balancing property. Specifically, a large (or small) initial value of $\\lambda_1$ will yield a large (or small) initial step size $\\eta_1$. Yet, $\\eta_2$ will be smaller (or larger) as it is inversely proportional to the **previous** step size. Eventually, the step size balances itself in both cases of initialization. \n\nTo support our rationale, we would like to provide empirical verification. In Figure 3 in the rebuttal PDF, we run our parameter-free method for the same objective in Section 7 where $L_2 = 10^4$ and $d = 10^2$. The plot shows that our method has similar performance for a range of initialization. \n\nWe also want to share the practical initialization we use in our experiments: we choose an initial point, $z_1$, and generate a second random point $\\hat{z}_1$, close to $z_1$. Then, we compute the local $L_2$ estimate to initalize as $\\lambda_1=2\\\\|F(\\hat{z}_1)-F(z_1)-\\nabla F(z_1) (\\hat{z}_1 - z_1) \\\\|/\\\\|\\hat{z}_1 - z_1\\\\|^2$. Let us clarify that this initialization rule comes from the proposed update recursion for $\\lambda_t$ (in Alg. 1, line 4) and we use it in the experiments for consistency.\n\n---\n**W2 Although the numerical experiment shows a promising result, ... may not generalize across diverse optimization tasks.**\n\n**R2** Thanks for raising this point. We ran a new set of experiments for the problem of maximizing an area under the receiver operating characteristic curve. This could be formulated as a min-max problem, where we want to find a classifier (set of weights) with **small** error that will also have a **large** area under the curve, as formulated in Eq 5.2 of [Lin et al., 2024]. \n\nPlease check out the respective plots under Figure 2 in the rebuttal PDF. Similar to the min-max problem in Section 7 of our paper, our methods converge relatively fast in the early stages of the execution. Due to time constraints, we have not run higher dimensional experiments for the new problem.\n\n---\n**Q1 How robust are the proposed methods to deviations from the assumed Lipschitz continuity of gradients and Hessians?**\n\n**A1** This is an interesting question. Let us answer by focusing on the parameter-free algorithm (Option II).\n\nThe Lipschitz gradient assumption is required **only** in the analysis to show that the iterates remain bounded, therefore, the algorithm is not affected by its variation. In fact, the experiments in our paper are based on an objective function which is not gradient Lipschitz but only Hessian Lipschitz, showing that our method is robust in that sense. \n\nWe think our reviewer would agree that the main issue is the variation in the Hessian Lipschitz constant $L_2$. In Figure 3 of the Appendix, we varied the Hessian Lipschitz constant from $L = 1$ to $L = 10^4$. We noticed that our proposed method consistently performs well across these different settings and is competitive with the optimal SOM. Similar results can be seen in Figures 2 and 3 in our rebuttal PDF.\n\n---\n**Q2 Can the parameter-free method's performance be significantly impacted by the choice of initial parameters?**\n\n**A2** Good question. We refer the reviewer to our response in **R1** above. As an additional note, a very small initial step size (corresponding to overshooting the Lipschitz constant $L_2$) will “delay” the achievement of the desired $O(1/T^{1.5})$, but our parameter-free method will eventually recover. When the initial estimate for $L_2$ is too small, our method will still converge as we explained in the previous answer, but non-parameter-free methods, which must know the exact Lipschitz constant, will diverge.\n\n---\n**Q3 How does the proposed approach compare to recent advances in machine learning applications, such as training GANs or solving reinforcement learning problems?**\n\n**A3**  To begin with, we would like to acknowledge that second-order methods, both for minimization and min-max problems, might have limited use once the dimension of the data and the model increase, but we believe there are valid scenarios where second-order methods could be beneficial.\n\nSecond-order methods can converge in fewer iterations, but calculating the Hessian and its inverse incurs extra costs per iteration. Thus, there is a trade-off between convergence rate and per-iteration cost. In scenarios where gradient evaluation is expensive, second-order methods may be more favorable than first-order methods, as they require fewer iterations and gradient queries.\n\nIn terms of implementation efficiency, there are techniques to cut this cost significantly, such as computing the (inverse) Hessian-vector products (HVP). [Tran and Cutkosky, 2022] propose a second-order momentum method that uses Hessian-vector products for stochastic optimization. Their algorithm outperforms SGD and Adam in image and NLP tasks and it is only 1.3 to 1.7 times slower than SGD. In the reinforcement learning literature, [Salehkaleybar et al., 2022] developed a second-order policy gradient method, which outperforms baselines by a significant margin in terms of system probes. [Dagréou et al., 2024] conducted an empirical study of different HVP algorithms on Jax and showed that the cost of computing HVP is less than twice the cost of gradient computation. Thus, we may scale our method to high-dimensional problems similarly when combined with such techniques.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their insightful feedback. Following your suggestions, we have performed new experiments, and the plots are included in the shared PDF file.  

- **Practical advantage compared to optimal SOM**. To demonstrate the computational efficiency of our proposed line-search-free method, we consider the same min-max problem in Section 7 with a higher dimension and larger Lipschitz constant. We observe from Figure 1 that our line-search-free methods and HIPNEX in [30] consistently outperform the optimal SOM in terms of runtime. Moreover, the performance gap widens as the dimension of the problem increases; the line-search scheme requires several backtracking steps, especially when $L_2$ is larger, and each step would be costly due to the computation of Hessian and its inverse when $d$ is large. Additionally, both of our methods outperform the HIPNEX method. 
- **Application to AUC maximization problems**. We consider a new problem of maximizing an area under the receiver operating characteristic curve. This could be formulated as a min-max problem, where we want to find a classifier (set of weights) with small error that will also have a large area under the curve, as formulated in Eq 5.2 of [Lin et al., 2024]. Similar to the observations above, Figure 2 demonstrates that both of our methods outperform the optimal SOM and HIPNEX in terms of runtime, particularly in the early stages of the execution. 
- **The impact of the initial parameter $\lambda_0$**. We tested our parameter-free method on the same min-max problem in Section 7 where $L_2 = 10^4$ and $d = 10^2$. Varying the initial choice of $\lambda_0$ from $10^{-4}$ to $0.05$, Figure 3 shows that our method exhibits consistent performance. We also tested a heuristic initialization procedure used in our other experiments ("$\lambda_0$ random" in the figure). Specifically, we choose an initial point, $z_0$, and generate a second random point $\hat{z}_0$ close to $z_0$. Then, we compute the local $L_2$ estimate to initalize $\lambda_0=2\\|F(\hat{z}_0)-F(z_0)-\nabla F(z_0) (\hat{z}_0 - z_0) \\|/\\|\hat{z}_0 - z_0\\|^2$. We also observe that this heuristic strategy is competitive and works well across different settings. 

We will include these new experiments and the above discussions in our revision.


---
**Additional references in our rebuttal:** 

Hoang Tran, Ashok Cutkosky. Better SGD using Second-order Momentum. NeurIPS 2022.

Salehkaleybar, S., Khorasani, S., Kiyavash, N., He, N., & Thiran, P. Momentum-Based Policy Gradient with Second-Order Information, 2022.

Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, Thomas Moreau. How to compute Hessian-vector products? ICLR Blogposts 2024.

Yossi Arjevani, Ohad Shamir, and Ron Shiff. Oracle complexity of second-order methods for smooth convex optimization. Mathematical Programming, 2019

Yuri Nesterov. Accelerating the cubic regularization of Newton’s method on convex problems. Mathematical Programming, 2008.

Bo Jiang, Tianyi Lin, and Shuzhong Zhang. A unified adaptive tensor approximation scheme to accelerate composite convex optimization. SIAM Journal on Optimization, 2020.

Konstantin Mishchenko. Regularized Newton method with global $O(1/k^2)$ convergence, 2021.

Kimon Antonakopoulos, Ali Kavis, and Volkan Cevher. Extra-newton: A first approach to noise-adaptive accelerated second-order methods. NeurIPS, 2022.

R. Monteiro and B. F. Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Journal on Optimization, 2013.

Tianyi Lin, Panayotis Mertikopoulos, Michael Jordan. Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee. 2024

Meta-review: The paper presents a new second-order method for convex-concave min-max optimization and obtain the optimal rate for the studied problem. Moreover, the proposed algorithm appears to be very practical. All the reviewers agreed that the work contributed to the field. I suggest that the authors consider the changes proposed by the reviewers in their revision.
Decision: Accept (poster)