Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximations
Authors: Artem Agafonov
Petr Ostroukhov
Roman Mozhaev
Konstantin Yakovlev
Eduard Gorbunov
Martin Takáč
Alexander Gasnikov
Dmitry Kamzolov
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Variational Inequalities
Quasi-Newton Methods
Min-Max Problems
Lower Bounds
Optimal Methods
Primary area: optimization

Abstract: Variational inequalities represent a broad class of problems, including minimization and min-max problems, commonly found in machine learning. Existing second-order and high-order methods for variational inequalities require precise computation of derivatives, often resulting in prohibitively high iteration costs. In this work, we study the impact of Jacobian inaccuracy on second-order methods. For the smooth and monotone case, we establish a lower bound with explicit dependence on the level of Jacobian inaccuracy and propose an optimal algorithm for this key setting. When derivatives are exact, our method converges at the same rate as exact optimal second-order methods. To reduce the cost of solving the auxiliary problem, which arises in all high-order methods with global convergence, we introduce several Quasi-Newton approximations. Our method with Quasi-Newton updates achieves a global sublinear convergence rate. We extend our approach with a tensor generalization for inexact high-order derivatives and support the theory with experiments.

(F(x), x²) 2 0, for all x E X. Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximations
Artem Agafonor Petr Ostroukhov! Roman Mozhaev2, Konstantin Yakovlev?, Eduard Gorbunov!, Martin Takáč", Alexander Gasnikoy 32,4 Dmitry Kamzolov!
Mohamed bin Zayed University of Artificial Intelligence (MBZUAD, Abu Dhabi, UAE 2 Moscow Institute Physics and Technology (MIPT), Moscow, Russia Innopolis University, Innopolis, Russia Skoltech, Moscow, Russia
Abstract
Variational inequalities represent broad class of problems, including minimiza- tion and min-max problems, commonly found in machine learning. Existing second-order and high-order methods for variational inequalities require precise computation of derivatives, often resulting in prohibitively high iteration costs. In this work, we study the impact of Jacobian inaccuracy on second-order methods. For the smooth and monotone case, establish a lower bound with explicit de- pendence on the level Jacobian inaccuracy and propose an optimal algorithm for this key setting. When derivatives exact, method converges at the same rate as exact optimal second-order methods. To reduce the cost of solving the auxiliary problem, which arises in all high-order methods with global convergence, introduce several Quasi-Newton approximations. Our method with Quasi-Newton updates achieves global sublinear convergence rate. We extend our approach with a tensor generalization for inexact high-order derivatives and support the theory with experiments.
Introduction
In this paper, primarily address the problem of solving the Minty Variational Inequality (MVI) rin 17). Given a continuous operator F X + Rd where X' C Rd is a closed bounded convex subset with diameter maxx,vex' ||æ - y/l. the objective is to find point x E X' such that
(1)
The solution to ( is referred to as weak solution the Variational Incquality (VI) [37]. In contrast, the Stampacchia variational inequality problem 48] consists in finding point xt X such that
(F(=*), x-) 2 0, for all x E X.
(2)
This solution often called strong solution the variational inequality. When the operator F is both continuous and monotone, the weak and strong solutions are equivalent [37].
"Contact details: Artem Agafonov
agafonov. adephystech edu: Petr Ostroukhov
postroukhov www.ouuhhhoo@@@maall...m com: Roman Mozhaev mozhaev htwp:..r@phhsec.ee edu: Konstantin Yakovlev
iakovlev. www.peeeehwpppe.eeeee...c.. edu:
Eduard Gorbunov eduard, gorbunovembzuai. ac, ae; Martin
Takáč takac. www.mail.cc.ooo com; Alexander Gasnikov gasnikov@yandex.. ru; Dmitry Kamzolov
kamzolov. opt@gmail.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Assumption 1.1 The operator F(x) is called monotone, if
(F - Fly), x - 20, 0, for all x, E X.
Another useful assumption is L -issmoothness.
Assumption 1.2 The operator Fxx) is I1 T.1-mmooth, if has Lipschit:-comiiuuuus firstorder derivative -VF())-VF(()))) I Lı|l-- yll, 1 for all E X.
First-order methods. Variational inequalities encompass a wide range of problems, including minimization [99 90, 93 151, min-max problems, Nash equilibrium, differential equations, and others [37 [6]. The extensive research on VI methods dates back several decades, with a notable breakthrough in the 1970s development of the Extragradient method [62
6 Subsequently, matching
was demonstrated that this method achieves global convergence of O ((= g0 431
the convergence rates of other first-orde methods such as optimistic gradient [92
78
63
44),
forward-backward splitting 1951, and dual extrapolation [8]]. These first-order methods collectively exhibit optimal convergence [9
Second-order and high-order methods. To achieve further notable acceleration of methods for VIs,
one can leverage information about higher-order derivatives. For instance, simply incorporating first-
order derivatives (Jacobian) can significantly enhance the convergence speed of the method. Following recent advancements in second-order and high-order methods with global rates for minimization [85]
82
10
79
83
46
58 4
51
64
22 several high-order methods for VIs have been proposed [2]
68
2
72
However, all these methods involve a line-search procedure, resulting in
Ô E 2/3)
convergence for the case of first-order information (Jacobians). Recent works [69
propose methods with improved rates O (e 2233) and establish the lower bound Q (e/33),, rendering these algorithms optimal.
Jacobian's approximation. In the last decade, VIs found new applications in machine learning. There many problems that could not be reduced to minimization, including reinforcement learning 87 (55, adversarial training (75), GANs 42
31 41
76,
28 67 91], classical learning
tasks in supervised learning [56] 91, unsupervised learning 98 R image denoising [35 27), robust optimization [I3. Applying second-order methods, without even mentioning high-order ones, described in a previous paragraph machine learning problems could be challenging task. Although these methods may theoretically converge faster, computing exact Jacobians and the per-iteration costs can be expensive. Therefore, it seems natural introduce inexact approximations of the first-order derivatives. In the context of minimization, several works with inexact Hessians were introduced for both convex 440 3 4 and nonconvex [24
25
23
6l
99
94
74.
[2] 34
problems. Regarding VIs. Quasi-Newton (QN) methods 773 14 can be highlighted. though they, unfortunately, achieve only local convergence in the strongly monotone case 18 38 These methods are relatively less advanced for VIs compared to their counterparts in the field of minimization, where they are considered classics in optimization due their effectiveness and practicality [86]. Modern research on QN approximations for minimization includes methods that exhibit global convergence [57 53 recent work (71) introduces the Newton-MinMax method for convex- concave unconstrained min-max optimization problems, demonstrating an optimal rate under special assumptions on the accuracy of the Jacobian approximation. However, the field of VIs lacks globally convergent inexact second-orde methods with an explicit dependence the accuracy of the Jacobian. This raises several natural questions:
What are the lower bounds for methods with inexact Jacobians? Can we construct an optimal method with inexact first-order information? What is the proper way to approximate the Jacobian to ensure global convergence and reduce the iteration complexity?
In our work, we attempt answer these questions in a systematic manner.
Forr clarity, let note that VI methods that only the information about the operator itself commonly referred to as first- methods. Methods that also use information about the Jacobian of the operator (the first-order derivative) are known as second-order methods. This somewhat contradictory notation stems from applications to minimization problems, where the operator is the gradient (i.e., the first-order derivative), and the Jacobian is the Hessian (i.e., the recond-odde derivative).

---

Optimality measure. Most of our results are stated for the monotone setting (Assumption 1.1. In this context, the optimality of a point & E X is typically measured by a gap function GAP(-) (ap(()):.
R+ 955 80
81
78
69
defined by
GAP(#) = sup (F(x), x) S xex
(4)
where 2 0 is the accuracy of solution. The boundedness of X and the existence of a strong solution ensure that the gap function is well-defined. If O, we get by ( that E is weak solution of VI. We explore the performance of the proposed algorithm in scenarios involving nonmonotone operators F. In such cases, it essential assume that the operator satisfies the Minty condition ensure that the problem is computationally manageable
32
Assumption 1.3 The operator F(x) satisfies Minty condition, if there exists a point x" such that
(F(x),x-x))
for all x E X.
The range of applications of nonmonotone VIs satisfying Minty conditions is quite extensive 20 39
29
36 66 60] We note, that this condition is weaker than monotonicity 30 50 5 and guarantees
the existence of at least strong solution since F is continuous and X' is closed and bounded 47
To measure the optimality of point we define the residue function RES(.) : - R 30 50 59
RES sup (F(#), - x) S, =Ex
The boundedness of and the existence of a strong solution ensure that the residual function is well-defined. If = 0, by 2 get that ft is strong solution of VI.
Contributions. The main contribution of this paper lies in the development a new second-order method robust to inexactness in the Jacobian, common occurrence in machine learning. We demonstrate the algorithm's 's optimality in the monotone case by establishing a lower bound for this key setting. Expanding further:
We introduce novel second-order algorithm, VIJI (Second-order Method for Variational Inequalitues under Jacoibian Inexactness), designed to handle 8-inexact Jacobian information. Specifically, in the context of smooth and monotone VIs, VIJI achieves a convergence rate of
O
D 7
find weak solution. For smooth nonmonotone VIs satisfying the Minty
condition, we demonstrate a convergence rate of O 6DD
vT + 4pp)) to identify strong solution.
Notably, when 8 <
L.D. /T our method matches the convergence rates of optimal exact second-order
methods 2
69
We establish the optimal performance of our algorithm on monotone smooth operators by deriving
a theoretical complexity lower bound of Ω 6D
find weak solution for the case of L D
T9/T
8 b-inexact Jacobians.
Our algorithm involves solving a variational incquality subproblem. To tackle this challenge, we introduce an approximation condition, which makes the solution computationally feasible.
4. We introduce new Quasi-Newton update for approximating the Jacobian, which significantly decreases the per-iteration cost of the algorithm while maintaining a global sublinear convergence rate. Numerical experiments demonstrate the practical benefits of our method.
5. We extend our algorithm for higher-order VIs with inexact high-order derivatives, resulting in D
EP=1
DP+1 rate for monotone and smooth VIs with 8,-inexact i-th derivative T(++1y2 + Ti++1/2
find weak solution. Moreover, extend our proposed high-order method nonmonotone VIs.
6. We propose a restarted version of VIJI for strongly monotone VIs, which exhibits linear rate.
Comparison with Lin, Mertikopoulos, and Jordan 7 To the best of our knowledge, the work [71] is the most closely related to our research. The objective of [7I] was to develop a method for convex-conen unconstrained min-max optimization under inexact Jacobian information with optimal convergence rate (233/ matching the lower bound ((e=~/3) [69. The authors successfully achieve this goal by proposing a second-order algorithm Inexact-Newton-MMnll
AA formal definition is provided in the following section.
3

---

Taylor approximation and oracle feedback. The starting point for our method is the first-order Taylor polynomial of the operator F at point (x(x) F(v) (F())(z - v). Since the computation of Jacobian FV))) could be quite tiresome task, it scems natural to introduce an of the method based on the Perseus [69]. To attain optimal convergence. they constrained the Jacobian inexactness with function that decreases as the method converges and bounded the norm of Jacobian from above. While these assumptions might be suitable for randomized sampling in finite-sum and stochastic problems, they may not hold for many approximation strategies, such as Quasi-Newton algorithms. The aim of our work, however, is to study the impact of Jacobian inaccuracy on the convergence of second-order methods for VIs (a special case which are min-max problems) and to identify the explicit dependence of the convergence rate on the inexactness. Compared to the work 777,, the Jacobian inaccuracy directly affects the step sizes in our algorithm, allowing us to achieve convergence rate of O(E-2/3 - for any given VIJI can be viewed a generalization of Inexact-Newton-Mingg optimization are equivalent. The inexactness of the subproblem and the solution approach proposed in 77] remain valid for our method even with arbitrary large 8. Further details about application of our method to min-mo min-max problems can found in Appendix
With the same assumption on as in [7]). our methods for min-max
2 Preliminaries
Notation. Let I2d be finiteddimensionaa vector space with scalar product (t, For vector Rd denote Euclidean norm as ||=|| For X E RR x.., define
X
2 Ensissd, (X, dy) "
and | = X[z .......... 2.) Fixing p 2 and letting F F Rd be continuous and high-order differentiable operator, we define F(r) as the pud-order derivative at a point x E Rdd To be more precise, letting 21, E RR we have
F())()))
8F ,0* Eish d (x) 2/1 2
inexact approximation (t). Based on it we introduce inexact Taylor approximation main building blocks of our algorithm
v (x(x) F()) J(D][= vI, vER. Rd.
(7)
where (xx satisfies the following assumption.
Assumption 2.1 For given v E 8-inexact Jacobian satisfies:
[[V((v) J(u)l S 6.
(8)
1.2 allows to control the quality of approximation of As it shown, e.g. in 152), Assumption operator F by its Taylor polynomial
F(x) 4. (z)ll < 4 || v/f 2.e
(9)
The next lemma is counterpart of ( for the case of inexact Jacobian.
Lemma 2.2
Assumptions
and 2. hold. Then, for any x, v E
F(r) (x(2) S 4 || 211² + 8|[2 - el|-
3 VLJI algorithm
In this section, extending on recent optimal high-order method for MVIs Perseus we present our proposed method, dubbed as VIII and detailed in Algorithm

---

Algorithm 1 VIJI
Input: initial point zo X, parameters L1, 7, sequence [3x] and opt E 1,2
Initialization: set 80 0 Rd.
for = 0, 1,, ..,, , do
Compute Uk++1 argmax (sk, v ro |/ 100--oll xoll2)-
Compute Tk+1 E X' such that condition (12 holds true.
Compute 1k+1 such that 32 I Ax+1
L1 06+1 - ux+il + 32+1) S 22
Compute Sk+1 = Sk. A (Ix+1).
k== AATIS
if opt = 0,
Output: f
TT:
else if opt
Bkr for kr = ISAST
10t vxll.
else if opt = 2.
The model of objective and subproblem's solution. We begin the description of the algorithm by introducing the inexact model of objective (2)())
(x) (x) + y0( v) + 5L, - - v),
(10)
where 7) > 0 is given constant. Here, we introduced the additional regularization term n7(x v). As will demonstrate, this term is crucial for ensuring that the method's subproblem has a solution. For brevity, we use a regularization constant of 5L. Using larger coefficients would yield the same convergence rate. As other dual extrapolation-typ methods, VIJI includes the following subproblem
find T&+1 E X such that (22 (#*+1), x 2x+1) 2 0 for all x E X.
(11)
First of all, the strong solution of this VI exists because 52% 2 (x) is continuous, and X' is a closed, bounded, and convex set. Next, we demonstrate that in a monotone setting VI [II is also monotone.
Lemma 3.1 Let Assumptions
hold. Then for any x, Uk+1 X' VI is monotone
(2) (O) d 4 44, || |
uil fixxd++ + 5L, (m-v)(=-))
(1) 1)0laxd-
[--
Following the work [69], one can find a strong solution to such VI using mirror-prox methods from (. achieving the following approximate condition
z) s 4 ||z+1 uktil 8| 1
(12)
=EX'
This ensures that the subproblem is computationally solvable in the monotone setting. In specific cases, such as minimax optimization, other efficient subsolvers can be employed 49
Adaptive dual stepsizes. Adaptive stepsizes in dual space Å are another core aspect of the algorithm. Due inaccuracies in the Jacobian, applying the standard adaptive strategy, such in the Perseus algorithm [69], can lead to excessively large steps, potentially slowing down the method. To address this issue, additional term 3R is incorporated into the adaptive strategy for selecting dg. Thus, when ||æ u || is small (indicating proximity to the optimum), 8& has greater influence on the choice of As preventing the method from taking overly aggressive steps. Similar behavior can be observed in accelerated second-order methods for minimization with inexact Hessians from
theoretical Lemma 5]. Appendix B, Lemma E.3] and practical Section 7] perspectives.
Convergence in monotone setting. Algorithm in the monotone case.
Now, we are prepared to present the convergence theorem of
1.2 2.1 hold. Then, after T 2 1 iterations of Algorithm 7 with parameters 8% 5, r) = 10, opt we get the following bound
Theorem 3.2 Let Assumptions 1.1
GAP(TT) sup (F(z), ĀT - O x
D 73/4
SD2
(13)
T
The upper bound 13) consists of two terms. The first one corresponds to exact convergence and matches the lower bound for second-order VI methods [69]. The second term illustrates the impact
5

---

of the Jacobian's 's inexactness on the convergence rate, aligning with the lower bound for first-order methods [89] We also notice that one can make the bound from (13) tighter for the so-called restricted
gap-function [ defined as RGAP(y) = suPzEc (F(x:, y r), where C C X' and the solution set
X of ( satisfies X _ C. In particular, following similar steps as in the proof of Theorem 3.2 one
L 3 7373
6B² bound for RGAP(.T). ) where Î suPzec || soll-
derive O
In the next theorem, we show that the method can achieve the optimal convergence rate of second- order methods under additional assumption on 6.
Theorem 3.3 Let Assumptions L.1 and
1.2
2.1
hold. Let { u be iterates generated by Algorithm 7
((V)((v)) ((v))) on vk]ll || S ōk|[2T vull,
8n S 4 1ate -xll-
(14)
Then, after T 2 iterations of Algorithum with parameters 3x 1 I| uell, 17 10, opt = 0. we get the following bound
GAP(ET) sup (F(x), 2) S zeX
L 7
Note, that condition (4 is verifiable, indicating that the method can adjust to å% in cases of controllable inexactness. Specifically, at each iteration, we can solve subproblem (12. If the assumption regarding dg is not met, can improve Jacobian approximation and repeat procedure. Moreover, similarly to the previous theorem, one can tighten the above bound for RGAP(TT) and get the dependence on = supæec | - - instead of D.
Convergence in nonmonotone setting. To begin with, in the nonmonotone case, the subprob- lem (TT) may not exhibit monotonicity, and solving (12) becomes challenging [3). Yet, certain specific scenarios, such unconstrained minimization tasks, it remains feasible to find solution by leveraging the cubic structure of the subproblem [26]. The following theorem establishes the convergence of VIJI in the nonmonotone setting.
Theorem 3.4 Let Assumptions 1.2
2.1 hold. Then after T 1 iterations of Algorithm 7 with parameters Br ō, = 10, opt 2 we get the following bound
1.3
RES(T) = sup (F(tT), -x) = (4p² =eX'
6D"
VT
The convergence rate could be improved by additional assumption on inexact Jacobian.
Theorem 3.5 Let Assumptions 1.2 1.3 that satisfy (14). Then after T > iterations of Algorithm 1 with parameters By 5 1|| uall. 17 10, opt = we get the following bound
2.1 hold. Let {I,, UR} be iterates generated by Algorithm 7
sup (F(ØT), bT x) =0 (4)2)) xEX
RES(#)
4 The lower bound
In this section, we establish a theoretical lower bound for the complexity of first-order algorithms using inexact Jacobians for monotone MVIs. The proof technique draws inspiration from works 33 and based on lower bounds from 69 89
We start by describing the available information and the method's 's structure. The considered class of algorithms relies on data provided by first-order 6-inexact oracle, denoted as O X - Rd x dddd Given a point ã E X, the oracle returns
(
(T), such that Assumption 2.1 holds.
(15)
The method is able to generate points {#x) that satisfy the following condition
Lin( F ((ro).....)))) ... F(xx)), F argmax ((5, x mn) - xoll²) }}],
2b+1 E X' satisfies that (2g (#k+1 - IR), - 2kt1l 2 0 for all x E X,, where 2g (h) = ai F(T) + [+) + b, + b2l
Next, we state the primary assumption concerning the method's ability to generate new points.

---

Assumption 4.1 The method generates a recursive sequence of iterates {z that satisfies the following condition: for all k Z O, we have that Ik+1 E X satisfies that (S2y -K)), xx+11 Z O for all z X, where
argmax (s, -zo) 211= m and Lin(F(zo).....F(a =EA
As highlighted in 699, Assumption 4.1 is suitably satisfied by various dual extrapolation methods. However, it might not be applicable alternative methods for variational inequalities, such as extragradient methods and their variants. We leave the generalization of inexact lower bounds for these algorithms to future research, even lower bounds for exact algorithms 22 69 do not address
this case. Now, let us introduce the generalization of smoothness
Assumption 4.2 The operator F(x) is i-th-order Li-mmooth 0). is has Lipschit--oominious i-th-order derivative
(FF(z)-V'F(g))) S L. vll, for all x, E X.
(16)
Finally, we present the lower bound theorem for first-order methods with inexact Jacobians.
Theorem 4.3 Let some first-order method M satisfy Assumption 4.1 and have access only 8-inexact
first-order oracle Assume the method M ensures for any Lo-zero-rrder smooth and Lı -irstrrtorder smooth monotone operator F the following convergence rate
GAP(2) S O(1) max
6D2 E.)
D (X(
(17)
Then for all T we have
(T) T,
(T( S T3/2
(18)
Quasi-Newton Approximation
In this section, inspired by Quasi-Newton (QN) methods for Hessian approximation, propose QN approximations for Jacobians. Our goal is to create a simple scheme to approximate the first-order derivative and thereby reduce the complexity of the subproblem. We compute Jn using a QN update and use it as an inexact Jacobian in the model (x) (T0).
J== ΣJ 2iE0Guu Jo PU
(19)
where r is rank of approximation, J E Rdxd > 0,u; E Rdd v, Rd are known. U E R and E Re are matrices of stacked vectors U = [ 11-1] and V = [Vu...., 1y-1] and C' E Rrxr is diagonal matrix C' = diag((cu- .c, C1-1) If u 0 the update becomes symmetric.
L-Broyden is a non-symmetric variant of QN approximation
45 38 of the following form
J++1 J (s:JJ 8. 8
Vi 0, . m
(20)
In view of (19.. this update is obtained by setting u yt s is sts G 1/(s.Ts) s,), and the rank r = m is equal to memory size m.
Damped L-Broyden is another option for QN approximation with non-symmetric damped update
jit J +
1 (yi (ia)a m+1
Vi = O...., m 1.
(21)
8. 5t
By choosing = 1/4 J We define the matrix J (J, J (J. C., where Y and S are formed by stacking the vectors [No, ................................ 1m and [so..... Sm-1]. The matrix (JD Y, S) can be computed for any given pair (Y, S). Next, we describe two strategies for the choice of (s, y) pairs used in (0). (2T).
8i, = 1/ 11m(mm1))))) T)sTTa)) st), m, we derive this update from (9).
QN with operator history is the well- classic variant where operator differences are stored:
8; Zi+1 Ris
yi = F(z+1) F(z,).
This approach is computationally efficient as it does not require additional operator calculations.
7

---

QN with JVP sampling is based on fast computation of Jacobian- Vector Products (JVP):
where 8; are random vectors uniformly distributed on the unit sphere such that ||s;|| = and so..... :0:....8m-- 8m-1 linearly independent. Note, for m < d, each s; is linearly independent with high probability. This approach requires only m operator/VP computations per step, which is considerably fewer than the d JVPs needed for full Jacobian. Utilizing the current Jacobian information allows to improve the accuracy of the approximation.
In the following theorem, we demonstrate that these approximations satisfy Assumption 2. and condition ( for both the QN with operator history and JVP sampling methods.
Theorem 5.1 Let F(x) be Lo-zero-order smooth operator. For m-memory L-Broyden approximation of the Jacobian Jz = Jmh defined iteratively by (20) with 0 3 Jo < Lo have 6 S (m + Log-
For m-memory Damped L-Broyden approximation Jg = J of the Jacobian defined iteratively by I, the condition 8 < 2oo holds true.
21 with 0 3 J m
La
With the primary toolkit for QN approximation in VIs established, we can now discuss efficient way of solving the subproblem [T], which takes the following form
find y X' such that (F(x:) (Ja + nōT 1lyl 2= z), y) 2 0 for all X. (22)
Let us introduce parameter consider another problem
11 x|| for segment search in [0: DJ. To solve 22
find y+ E X' such that F(x) + y- - x, μ+) 2 0 for all = E X,
(23)
where A, Jg + (17 + 5L1 Problems (22 and (3 are equivalent when T 1yy, - x/|. The
subproblem 23 can be reformulated as minimization problem
y/ = argmin (4, - x) + -lly - x: x=|3},
(24)
yEA
where 23 is optimality condition for
24 The goal is to find yr such that u(T) IT - ||,- =|l| < S. As v(T) is a continuous function of r, we can find this solution via bisec-
tion segment-search with log2 v iterations. This ray-search procedure is similar to the subproblem solution for the Cubic Regularized Newton subproblem.
For r-rank QN approximation J" from 199. we can effectively compute F(x), where A, = {no 5L = U CV and J + (n6 5LTT)I
J" + (19ō + 5L = U CV + J
by using the Woodbury matrix identity 97
F(z) = (B + uV) F(z) = --
F(x).
For computational efficiency, it is better to choose Jo as diagonal matrix, then inversion B-1 1 is computed by ((d) arithmetical operations, C-1 by 0(r) operations. VB- requires 0(r²d) dd for classical multiplication and can be improved by fast matrix multiplication. can be computed by O(r"), as inverse of r-rank matrix. The rest of the operations Thus, the total number of arithmetic operations is O(r²d) instead of ((d)) for Jacobian inversion. We need to perform this inversion logarithmic number of times. Therefore, the total computational cost with the segment- search procedure is Ô (r²d + 7 logz( ()).
10-1+VB-L0
cheaper.
6 Strongly monotone setting
Assumption 6.1 The operator F Rdd - TRd is called strongly monotone if there exists a constant > 0 such that
(F(x) F()), x v) 2 p||= yll². for all x, y X.
(25)
To leverage the strong monotonicity of the objective function and achieve linear convergence rate, we introduce the restarted version of Algorithm Aggrri as VIJI-Restarted. Restart techniques are widely utilized in optimization and typically preserve optimality. In other words, restarting an optimal method for convex functions or monotone problems effectively transforms it into an optimal method for strongly convex or strongly monotone problems. Within iteration of VIJI-Restarted listed as Algorithm? 2 we execute VIJI for a predefined number of iterations (26). Next, the output of this run is used as initial point for next run of VIJI with parameters reset, and this iterative process continues.
8

---

Algorithm 2 VIJI-Restarter
Input: initial point 20 E X, D maxx,yex, parameters L, 8.
Initialization: n [log _1 R D. for iol, n do
Set 30 2;-1: R1-1 R..
Run Algorithm 1 with BR = 6, 10, opt = 0 for T3 iterations, where
1 R ò p
1 }1
T. = 0(1)
max
(26)
Set 2; TT.
Theorem 6.2 Let Assumptions 1.2
2.1
6.1 hold. Then the total number of iterations of Algorithm I E, where x² is the solution of is
to reach desired accuracy ||2,
x
((+1)) p
(LD)
+ ( +1) [log 21)
Tensor generalization
In this section, we generalize the results presented in Section B to the p-th order case. We consider higher-order method with inexact high-order derivatives, satisfying the following assumption.
Assumption 7.1 For all x, E X, 2 1, i-th inexact derivative of F, which we denote as G,, satisfies
[[(v'F(o) G. [r -
-| - 6.11z - w11"
(27)
Based on inexact (p- - 1) 1)-th-order Taylor approximation pp.o(x) = F(U) + we introduce the inexact tensor model 2p (z) of the objective
Pp (x) = (x)) E n. [| - u) + 5hg i || x
--l v).
(28)
The tensor generalization of Algorithm D referred to as VIHI (High-order Method for Variational Inequalitues under High-order derivatives Inexactness and detailed in Appendix G involves the inexact solution of the subproblem, which satisfics the following condition:
sup (Ω (Fx+1),, #841 x) xEX
Lp pl
Uet1l
EE
uk+1 1+1
Another difference in VIHI compared to VIJI (Algorithm) D the adaptive strategy for A
1(5p-2 2j
Ap
[x441
Uk+ |P+1
+
-P-14 | 1
2(5+11
The other steps of Algorithm remain unchanged for the higher-order method. Now, we are ready to present the convergence properties of VIHI.
Let Assumptions/ I.I 4.2 with i = - 1, and 7.1 7.777ll hold. Then, after T 2 iterations of VIHI with parameters π) 5p. opt U. get the following bound
Theorem 7.2
GAP(ET) sup (F(x), x) #ex
Lp-1 DP+1
T
T
Finally, extend our tensor generalization to nonmonotone and obtain the following result.
Theorem 7.3
Let Assumptions 7.3 4.2 with p 1, and 7.1 hold. Then after T 2 1 itterations of VIHI with parameters 77 = 5p, opt we get the following bound
(ES(#) sup (F(#)), x) Lp-1 D
7

---

8 Experiments
In this section, we present numerical experiments to demonstrate the efficiency of our proposed methods. We consider the cubic regularized bilinear min-max problem of the form:
min max f(x, y) = (Ar b) + E1|=!| * #E VER.
where p > 0, b [1, .., 0J E Rd and Rdddd with all on the main diagonal and all -1 on the upper diagonal, the rest elements are O. To reformulate it as variational inequality, we define F(x)= = [ (rr,)) v y)]. This problem inspired by the first-order lower bound function for variational inequalities and min-max problems and is commonly used to verify the convergence of high-order methods for 52).
We implement our second-order method for Variational Inequalities with Quasi-New Approximation (VIQA) as PyTorch optimizer. The code is available in the OPTAMI package [58] VIQA Broyden refers to L-Broyden approximation (20) and VIQA Damped Broyden to (21). which are used as inexact Jacobians in VIJI (Algorithm[I) We compare them with the Extragradient method (EG) 62 first-order Perseus (Perseus1), 1), and second-order Perseus with Jacobian (Perseus2).
Ferne2 VSS Inaydes
VRGA Campad Droyden
15.
vipA praydien
12.0
304
10
15.44
10:44
12.44
25066
Seles"
15000
laraton.
Figure 1: Comparison of different methods for d = 50, p = 1E
In Figure [ one can see that second-order information in Perseus2 significantly accelerates the convergence compared to 1erseus1. However, it is expensive to compute Jacobian and solve second- order subproblems every iteration. VIQA with the proposed Damped Broyden approximation (2I) is significantly faster than EG, Perseusl, and VIQA Broyden (20). It shows that this approximation improves the convergence of first-order Perseus and confirms the theoretical result that Damped Broyden is more accurate approximation than classical Broyden from Theorem 5.1 The detailed parameters and setup are presented Appendix
Conclusion
In this work, we introduced second-order method specifically designed to handle Jacobian inex- actness. We demonstrated its optimality in the monotone case by introducing a new lower bound and extended its applicability to tensor methods. However, similar other high-order methods with global convergence properties, our algorithm involves a subproblem that necessitates an additional subroutine for its solution. To address this challenge, we proposed computationally feasible criterion for solving the subproblem and implemented Quasi-Newton approximations for Jacobians, resulting in a significant reduction in per-iteration cost. Future investigations could explore incorporating inexactness within the operator itself and developing adaptive schemes to dynamically adjust for the level of inexactness encountered during the optimization process. Another open problem is design of more accurate Quasi-Newton approximations specifically for Jacobians, focusing on non-symmetrical structure Jacobian and specific inexactness criteria such as Assumption 2.1
10

---

Acknowledgments.
The work supported by MIPT based Center of National Technology Initiatives in the field of Artificial Intelligence for the purposes of the "road map" of Artificial Intelligence development up to 2030 and supported by NTI Foundation (agreement No. No.70-2021-00207 dated 22. 1.2001,, identifier 000000550521QYX00000))
References
[1] S. S. Ablaev, A. A. Titov, F. S. Stonyakin, M. S. Alkousa, and A. Gasnikov. Some adaptive first-order methods for variational inequalities with relatively strongly monotone operators and generalized smoothness. In International Conference Optimization and Applications, pages 135-150. Springer, 2022.
[2] D. Adil, B. Bullins, A. Jambulapati, and S. Sachdeva. Optimal methods for higher-ordet smooth monotone variational inequalities. arXiv preprint arXhv:2205.06/66 2022.
[3] A. Agafonov, D. Kamzolov, P. Dvurechensky, A. Gasnikov, and M. Takáč. Inexact tensor methods and their application to stochastic convex optimization. Optimization Methods and Software, (9 83, 2024. doi: 10. 10900/10556788.22222266111 org/10.1080. 10556788 2023 2261604
URL https://doi
[4] A. Agafonov, D. Kamzolov, A. Gasnikov, A. Kavis, K. Antonakopoulos, V. Cevher, and M. Takáč. Advancing the lower bounds: an accelerated, stochastic, second-order method with optimal adaptation to inexactness, In The Twelfth International Conference on Learning Representations, 2024. /tttps:/:////p/eeee/i/
[5] M. M. Alves and B. F. Svaiter. search-free ((1/k3/2) homotopy inexact proximal-newton extragradient algorithm for monotone variational inequalities. arXiv preprint arXiv:2308.00 05887, 2023.
[6] A. Antipin. Method of convex programming using symmetric modification of lagrange function. Matekon, 14(2):23-38, 1978.
[7] K. Antonakopoulos, A. Kavis, and Cevher. Extra-newton: A first approach to noise-adaptive accelerated second-order methods. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and Oh, editors, Advances in Neural Infor- mation Processing Systems, volume 35, pages
Curran Associates, Inc.,
2022. URL httpp::/proceedde wwwpeeediiiinnnnnnineeeeeeeeeeee cc ctppppp..cppppppr..ii..... c1080470 33864400beeaa0cca333311113333333 Conerreeeeeeeeeeeneeeeeeeeeeeee .dff]
[8] F. Bach, J. Mairal, and J. Ponce. Convex sparse matrix factorizations. arXiv preprint arXiv:0812. 1869, 2008
[9] Bach, R. Jenatton, J. Mairal, G. Obozinski. et al. Optimization with sparsity- induuing penalties. Foundations and Trendy@ in Machine Learning, 4(1):1-106, 2012.
[10] M. Baes. Estimate sequence methods; extensions and upproximations. Institute for Operations Research, ETH, Zürich, Switzerland, 2(1), 2009.
[11] S. Bellavia and G. Gurioli. Stochastic analysis of an adaptive cubic regularization method under inexact gradient evaluations and dynamic hessian accuracy. Optimizzation, 71:227-261, 2022. doi: 10. 1000000031193422222211.2. 1892104. URL http:////.../////.//////////////
http:///....rrr.....000///2//1./ 2021
1892104
[12] Bellavia, G. Gurioli, Morini, and Toint. Adaptive regularization for nonconvex optimiza- tion using inexact function values and randomly perturbed derivatives. Journal of Complexity, 68:101591, 2022. ISSN 0885-064X. doi:
URL
https:// h/wbw. www.eceeiieec.ccccm
[13] A. Ben-Tal Tal, L. El Ghaoui, and A. Nemirovski. Robust optimization, volume 28. Princeton university press, 2009.
[14] A. S. Berahas, M. Jahani, P. Richtárik, and M. Takáč. Quasi-newton methods for machine learning: forget the past, just sample. Optimization Methods and Software, 17:1668-1704 2022. doi: 10. 108000005567888.22.....1 1977880. URI.httpa httppp::////ooooooo/ooooeso htt.://///....00000000008888888
1977806

---

[15] A. Beznosikov, A. Alanov, D. Kovalev, M. Takáč, and A. Gasnikov. On scaled methods for saddle point problems. arXiv preprint arXiv:2206.0888 08303, 2022.
[16] A. Beznosikov, B. Polyak, E. Gorbunov, D. Kovalev, and A. Gasnikov. Smooth monotone stochastic variational incqualities and saddle point problems: A survey, European Mathematical Society Magazine, (127):15-28, 2023.
[17] A. Beznosikov, M. Takác, and A. Gasnikov. Similarity, compression and local steps: three pillars of efficient communications for distributed variational inequalities. Advances Neural Information Processing Systems, 36, 2023.
[18] J. F. Bonnans. Local analysis of newton-type methods for variational inequalities and nonlinear programming. Applied Mathematics and Optimization, 29: 29:161-186, 1994.
[19] L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-311, 2018.
[20] I.. Brighi and R. John. Characterizations of pseudomonotone maps and economic equilibrium. Journal of Statistics and Management Systems, 5(1-3):253-273, 2002.
[21] B. Bullins and K. A. Lai. Higher-order methods for convex-concave min-max optimization and monotone variational inequalities. SIAM Journal on Optimization, 32(3):2208-22 2229, 2022.
[22] Y. Carmon, D. Hausler, A. Jambulapati, Y. Jin, and A. Sidford. Optimal and adaptive monteiro- svaiter acceleration. S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 20338-20350 Curran Associates, Inc., 2022. URL httptt/see/proceednnssseeeeeeeee wwwp://iinnn.uuuinnnn.i.icce cc/ files/ pdf
[23] C. Cartis and K. Scheinberg. Global convergence rate analysis of unconstraiined optimization methods based on probabilistic models. Mathematical Programming, 169:337-375, 2018. ISSN 1436-4646. doi: 10.1007/111007-011-1333-44 URL httth: http://dtt..rr/1..1000000
810107-017-1337-1
[24] C. Cartis, N. I. Gould, and P. L. Toint. Adaptive cubic regularisation methods for unconstrained optimization, part i: motivation, convergence and numerical results. Mathematical Programming, 127(2):245-295, 2011.
[25] C. Cartis, N. I. Gould, and P. L. Toint. Adaptive cubic regularisation methods for unconstrained optimization, part ii: worst-case function-and derivative-evaluation complexity. Mathematical programming, 130(2):295-319, 2011.
[26] C. Cartis, I. Gould, and I.. Toint. Evaluation Complexity of Algorithms for Nonconvex Optimization: Theory, Computation and Perspectives. SIAM, 2022.
[27] A. Chambolle and T. Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40: 120-1154 2011.
[28] T. Chavdarova, G. Gidel, F. Fleuret, and S. Lacoste-Julien. Reducing noise in gan training with variance reduced extragradient. Advances in Neural Information Processing Systems, 32, 2019.
[29] C. Choi, W. S. DeSarbo, and P. T. Harker. Product positioning under price competition. Management Science, 36(2):175-199, 1990.
[30] C. D. Dang and G. Lan. On the convergence properties of non-euclidean extragradient methods for variational incqualities with generalized monotone operators. Computational Optimization and applications. 60:277-310, 2015.
[31] C. Daskalakis, A. Ilyas, Syrgkanis, and H. Zeng. Training GANs with optimism. In International Conference on Learning Representations, 2018. URL https//////peeerreeeee net/forum? id=isJySsJJJb.
[32] C. Daskalakis, S. Skoulakis, and M. Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1466-1478, 2021.
[33] O. Devolder, F. Glineur, and Y. Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical IeeelloPrrre Programming, 146:37-75, 2014. ISSN 1436-4646. doi: 10. 10.1007/510107-013-0677-.
http::ttt///ot org/
12

---

[34] N. Doikov, E. M. Chayti, and M. Jaggi. Second-ordes optimization with lazy Hessians. In A. Krause. E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Searlett, editors. Proceedings of the 40th International Conference Machine Learning, volume 202, pages 8138 -161.. PMIRR 2023. URL. htttp:://proceeingg ampiiiinnnnmm.......mm.mm.. mlr. www..ppeee//////ooooooooeeeeooee wtwp222/ddokoo2222 html
[35] E. Esser, X. Zhang, and T. F. Chan. A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM Journal on Imaging Sciences, 3 (4):1015-1046, 2010.
[36] C. Ewerhart. Cournot games with biconcave demand. Games and Economic Behavior, 85: 37-47, 2014.
[37] F. Facchinei and J.-S. Pang. Finite-dimensional variational inequalities and complementarity problems. Springer, 2003.
[38] D. Fernández. A quasi-newton strategy for the ssqp method for variational inequality and optimization problems. Mathematical Programming, 137:199-223. 2013.
[39] G. Gallego and M. Hu. Dynamic pricing of perishable assets under competition. Management Science, 60(5): 1241:1299, 2014.
[40] S. Ghadimi, H. Liu, and T. Zhang. Second-order methods with cubic regularization under inexact information. arXiv preprint arXiv:1710.0578;; 2017.
[41] G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien. A variational inequality perspective on generative adversarial networks. In International Conference on Learning Representations, 2019. URL htttttt//opperreeeeee wwtppperreiieeeeeeeorruuuuuaaaaa htte/forrmmii-r11aBBnn
[42] I. Goodfellow, J. Pouget-Abaddie M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
[43] E. Gorbunov, N. Loizou, and G. Gidel. Extragradient method: O(1/k) last-iterate convergence for monotone variational inequalities and connections with cocoercivity. In International Conference Artificial Intelligence and Statistics, pages 366-402 PMLR, 2022.
[44] E. Gorbunov, A. Taylor, and G. Gidel. Last-iterate convergence of optimistic gradient method for monotone variational inequalities. Advances in neural information processing systems, 35: 21858-21877 1700 2022.
[45] J. Han and D. Sun. Newton-type type methods for variational inequalities. Advances in Nonlinear Programming: Proceedings of the 96 International Conference on Nonlinear Programming. pages 105-118. Springer, 1998.
[46] S. Hanzely, D. Kamzolov. D. Pasechnyuk, A. Gasnikov, P. Richtárik, and M. Takáč. A damped Newton method achieves global O and local quadratic convergence rate. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 35320-25334 Curran Associates. Inc., 2022. http:tttts:://rcceeeeieee nwwr.sgg......................e cc/ ccppppr. files/ files/ pptssp////2////ieeeeeee aff00cdcca443355510006666333---3 Pat.aa/aaaeeeteeeoaeea-----eeeee wwwfeppeeeeeeeeeeeeeeeeeeeeeeeee pdf
[47] Harker and J.-S. Pang. Finite-dimensional variational inequality and nonlinear complemen- tarity problems: a survey of theory, algorithms and applications. Mathematical programmingg 48(1):161-23) 1990.
[48] P. Hartman and G. Stampacchia. On some non-linear elliptic differential-functiona. equations. Acta Mathematica, 115(1):271-310, 1966.
[49] K. Huang, J. Zhang, and S. Zhang. Cubic regularized Newton method for the saddle point models: A global and local convergence analysis. Journal of Scientific Computing, 91 (2):60 2022.
[50] A. N. Jusem, A. Jofré, R. I. Oliveira, and P. Thompson. Extragradient method with variance reduction for stochastic variational inequalities. SIAM Journal on Optimization, 27(2)668-724, 2017.
[51] M. Jahani, X. He, C. Ma, A. Mokhtari, D. Mudigere, A. Ribeiro, and M. Takác. Efficient distributed hessian free algorithm for large-scale empirical risk minimization via accumulating sample strategy. International Conference on Artificial Intelligence and Statistics, pages 1634-2644, PMLR, 2020.
13

---

[52] R. Jiang and A. Mokhtari. Generalized optimistic methods for problems. arXiv preprint arXiv:2202.096674 2022.
saddle point
[53] R. Jiang and A. Mokhtari. Accelerated quasi-newton proximal extragradient: Faster rate for smooth convex optimization. Advances in Neural Information Processing Systems, 36, 2024.
[54] R. Jiang, Q. Jin, and A. Mokhtari. Online learning guided curvature approximation: A quasi- newton method with global non-asymptotic superlinear convergence. In The Thirty Sixth Annual Conference on Learning Theory, pages 1962-1992. PMLR, 2023.
[55] Y. Jin and A. Sidford. Efficiently solving mdps with stochastic mirror descent. In International Conference on Muchine Learning, pages 4890-4900. PMLR, 2020.
[56] T. Joachims. A support vector method for multivariate performance measures. In Proceedings of the 22nd international conference on Machine learning, pages 377-384, 2005.
[57] D. Kamzolov, K. Ziu, Agafonov, and M. Takáč. Cubic regularization the key! the first accelerated quasi-newton method with a global convergence rate of o(k=²) for convex functions. arXiv preprint arXiv:2 009874987 2023.
[58] D. Kamzolov, D. Pasechnyuk, A. Agafonov, A. Gasnikov, and M. Takáč. Optami: Global superlinear convergence of high-order methods. arXiv preprint arXiv:2410.04086 2024.
[59] A. Kannan and U. V. Shanbhag. Optimal stochastic extragradient schemes for pseudomonotone stochastic variational incquality problems and their variants. Computational Optimization and Applications, 74(3):779-820, 2019.
[60] B. Kleinberg, Y. Li. and Y. Yuan. An alternative view: When does sgd escape local minima? In International Conference on Machine Learning, pages 2698-2707. PMLR, 2018.
[61] J. M. Kohler and A. Lucchi. Sub-sampled cubic regularization for non-convex optimization. In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 1895-1904. PMLR, 2017. URL URL httpp::/pproceeddngggg .mlr
press//70/kohlerr//a html
[62] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[63] G. Kotsalis, G. Lan, and T. Li. Simple and optimal methods for stochastic variational incqualities,
i: operator extrapolation. SIAM Journal on Optimization, 32(3):2041-20) 2073, 2022.
[64] D. Kovalev and A. Gasnikov. The first optimal acceleration of high-order methods in smooth convex optimization. S. Koyejo, S. M.haamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 15339-353351 Curran Associates, Inc., 2022. URL htLp:tttps:/pprceeediie itrersnneerriii www.neeeriisoom www.eipp..ccppppe_fiiil.. files/ e56f htt.a///eae...eoooooooeeeaeeaaaa Confererce- pdf
[65] X. Li and F. Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In K. Chaudhuri and M. Sugiyama, editors, Proceedings of the Swenty-Second International Conference on Artificial Intelligence and Statistics,, volume 89, pages 983-992. PMLR, 4 2019. URL BRLLLttts::/prrceeddigg
mlr. www.ppressseve..e https//vv/11199e html
[66] Y. Li and Y. Yuan. Convergence analysis of two-layer neural networks with relu activation. Advances neural information processing systems, 30, 2017.
[67] T. Liang and J. Stokes. Interaction matters: A note non-asymptotic local convergence of generative adversarial networks. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 907-915. PMLR, 2019.
[68] T. Lin and M. I. Jordan. Monotone inclusions, acceleration, and closed-loop control. Mathemat- ics of Operations Research, 48(4):2353-23322 2023.
[69] T. Lin and M. I. Jordan. Perseus: A simple and optimal high-order method for variational inequalities. Mathematical Programming, pages 1-42, 2024.
[70] T. Lin, M. Jordan, et al. A continuous-time perspective optimal methods for monotone equation problems. arXiv preprint arxivv2206.044770, 2022.
[71] Lin, Mertikopoulos, and M. Jordan. Explicit second-order min-max optimization methods with optimal convergence guarantee. arXiv preprint 2tt.::222....66.666. 2022.
[72] C. Liu and L.. Luo. Regularized newton methods for monotone variational inequalities with h)"" older continuous jacobians. arXiv preprint arXiv:2212.07824 2022.
14

---

[73] D. C. Liu and J. Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programming. 45:503-523 528, 1989. doi: 10.1007/BF01589116. URL https
7/doi orgg 10. 1007 N007/BFTT /BF0118011111666
[74] A. Lucchi and J. Kohler. A sub-sampled tensor method for nonconvex optimization. IMA Journal of Numerical Analysis, 43:2856-2891, 10 2023. ISSN 0272-4979. doi: 10.10933
imanum/drac057. URL BELLhttp::00 https: org/ 10. 1093/ immnum/dracoo
[75] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In Internattional Conference on Learning Representations, 2018. URL httpppps://pperreiiieeeee net atte//oorumm/ddrr1l1fff2..
[76] Mertikopoulos, Lecouat, Zenati, C.-S. Foo, V. Chandrasekhar,, and G. Piliouras. Opti- mistic mirror descent in saddle-point problems: Going the //tpereee// wttprreeeiiwwweeeeeeeeeeeeee Conference on Learning Representations, 2019. URL Jtttpastts////peeeaa id=Bkg8jjC9KQ
mile. In International
[77] G. J. Minty. Monotone (nonlinear) operators in hilbert space. Duke Mathematical Journal, 29 (3), 1962.
[78] A. Mokhtari, A. E. Ozdaglar, and S. Pattathil. Convergence rate of o ((1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization, 30(4):3230-325 2020.
[79] R. D. C. 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, 23; 1092-1155,, 2013. doi: 1137/110833786
URL https://doi. //tp://///ooo////0
[80] A. Nemirovski. Prox-method with rate of convergence (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-2555 2004.
[81] Y. Nesterov. Dual extrapolation and its applications solving variational inequalities and related problems. Mathematical Programming, 109(2):319 1113119344 344, 2007.
[82] Y. Nesterov. Accelerating the cubic regularization of Newton's method on convex prob- lems. Mathematical Programming, 1 112:159-181, 2008 ISSN 1436-4646. doi: 10.1007/ s s10107-006-0089-x https:/:
org /ttp:/10000000000000000000000000
[83] Y. Nesterov. Implemenaablee tensor methods in unconstrained convex optimization. Mathematical
Programming, 186:157-183, 2021. ISSN 1436-4646. doi: 10. 10.10077510107-019-014444 URL
[84] Y. Nesterov. High-order reduueed sowpdduucd--gridiinn
methods for composite variational inequalities. arXiv
preprint arXiv:2311 2.. 2023.
[85] Y. Nesterov and B. Polyak. Cubic regularization Newton method and its global performance. Mathemutical Programminy, 108: 177-205, 2006. doi: 10.10077/11000--0000000-- URL htttps://di..rgg/// wttp:///...000/10000000000--0000
[86] Nocedal and S. Wright. Numerical Optimization. Springer New York, 2 edition, 2006.
ISBN 978-0-387-30303-1 doi: 10. N0.1007/978-0-380 0-777880-----4-5555
[87] S. Omidshafiei, J. Pazis, C. Amato, J. P. How, and Vian. Deep decentralized multi-task multi-agent reinforcement learning under partial observability. In International Conference on Machine Learning, pages 2681 2681-2690. PMLR, 2017.
[88] Ostroukhov, R. Kamalov, Dvurechensky, and A. Gasnikov. Tensor methods for strongly convex strongly concave saddle point problems and strongly monotone variational inequalities. arXiv preprint arXiv:2012.15599 2020.
[89] Y. Ouyang and Y. Xu. Lower complexity bounds of first-order methods for bilinear saddle-poin problems. Mathematical Programming. 185(1):1-35, 2021.
[90] D. A. Pasechnyuk, A. Gasnikov, and M. Takáč. Convergence analysis of stochastic gradient descent with adaptive preconditioning for non-convex and convex functions. arXiv preprint 2308. /4/92, 2023.
[91] W. Peng, Y.HH. Dai, H. Zhang, and I.. Cheng. Training gans with centripetal acceleration. Optimization Methods and Software, 35(5):955-973, 2020.
15

---

[92] L. D. Popov. A modification of the aurow-hurwitz method of search for saddle points. Mat. Zamerki, 28(5)7777-784 1980.
[93] A. Sadiev, A. Beznosikov, A. Almansoori, D. Kamzolov, R. Tappenden, and M. Takáč. Stochastic gradient methods with preconditioned updates. Journal of Optimizaaiion Theory and Applicationss, 201:471-489) 2024. ISSN 1573-2878. doi: 10.00077610955--02--066633 URL
https://doi. org/10..///. 1ww./0000001100--00 023- 02365-3
[94] N. Tripuraneni, M. Stern, C. Jim, Regier. and M. Jordan. Stochastic cubic regularization for fast nonconvex optimization. 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. URL http::ttttsttttcttttl httphhtpsp//rrrceednnggiieeeeeee neur.ps......................... wtt.cc/cppppee... files/
pdf
[95] Tseng. A modified forward-backwand splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, 38(2)4431-446, 2000.
[96] M. A. Woodbury. The stability of out-input matrices. Chicago, IL, 9:3-8, 1949.
[97] M. A. Woodbury. Inverting modified matrices. Department of Statistics, Princeton University,
1950.
[98] I.. Xu, J. Neufeld, B. Larson, and D. Schuurmans. Maximum margin clustering, Advances in neural information processing systems, 17, 2004.
[99] Xu. Roosta, and M. W. Mahoney. Newton-type methods for non-convex optimiza- tion under inexact Hessian information. Mathematical Programming, 184:35-70, 2020. ISSN 1436-4646. doi: 10. 10.10077/10007-019-014000 URL https://doi. or./10.10017 610107-019-0140--2
16

---

Contents
Proofs of Lemmas 3.1
17
Proofs of Theorems 3.3
18
B Proof of Theorem 3.2
18
B.2 2 Proof of Theorem 3.3
21
Proofs of Theorems 3.4
3,5
22
Proof of Theorem 4.3
23
Proof of Theorem 5.1
23
Proof of Theoreml6.2
23
Tensor generalization with more details
25
Preliminaries
25
G.2
Auxiliary lemmas
26
G.3
Convergence in monotone case
27
Convergence nonmonotone case
H
Subproblem solution
32
Experiment details
33
Application to minmax problems
33
Preliminaries
33
2
The method
34
J.3
Convergence analysis
35
Proof of Theorem
36
Proof of Theorem
38
A
Proofs of Lemmas 2.2 3.1
In this section, we let L, := I,.
Lemma 2.2 Let Assumptions 1.2 and 2.1 hold. Then, for any v E X
[F(x) (x)] I - 5||2 e/1.
(29)
Proof. For any x, y E X
[F(x) (x( s (F(x) 2 (x)] (1) v.(x)]
| u/12 + [[(V J(v)){= - - - Tll + 0|| - w/|-
17

---

Lemma 3.1
Let Assumptions 1.1
hold. Then for any 2, E X VI is monotone
(v) (l+(x))) = 4h || u Taxd + 5L1 (e-v)
(n 1)6Taxd-
||
Proof. For all x, v E X
$ (v).(x) + (22((=)²)
nōlaxd + _2|1 2ilLaxd 5L (x - ()- u)?
10 (J())+
||--11 -0-ll
|1|| Laxd 5L (x- (s-v)(--v)* + (17 1)xlax
22-081
4b x 1 Laxd + 5L (a (2==) + (1 1)8laxd.
2--00
B Proofs of Theorems 3.2 3.3
B.1 Proof of Theorem 3.2
In this section, we let == L1. To show the convergence of Algorithm T we define the following Lyapunov function
Ex
-mxx (sk, v - ma) - =oll2.
(30)
o
Lemma B.1 Let Assumption 1.2 2.
hold. Then, for every integer T 2 1, we have
Σ a0 ux v for all x X.
>a (F(EE)) 2) Ea- Er (sT, x - zoo
Proof. By the definition of Lyapunov function (30) and Step 2 of Algorithm have
E (sk, Uk+1 zo) - 1 zol1?
Then, we have
Ex+1 - Ek = (Sk+1, Uk+2 - 22) - (sk: Uk+1 - 20) 1 (1lu4+2 - zoll? |lux11 zoll?)
= [5K+1 8k, Uk+1 w0) + (8k+1, Uk42 Uk+1) 2 (1lv442 zoll2 - -1|02+1 - xo 11 (31)
2
By the update formula for 1,+1, get
(x Uk-1: 8k uk+1 + zb) S 0, for all X.
Letting Uk+2 in this inequality and using (a, b) 1/2 (I]a b1l2 ||a||2 [|b]12), we have
(Sk, 1442-U6411 < (ve+1 -o. 0242-
(1 zoll² ||u2 zoll2 || Uk+ 11?). (32)
Plugging Eq.
31 and using Step 5 of Algorithm 1 into Eq.
obtain:
Ex+1 Ek (8++1 8k, Uk+11 xo) + (8K+11 86, 0242 uk+1) 11 u1+1 1|2
(sk41 5k, uk+2 2o) 1 1 uk+1 2 < )F
2k+2) 11l2222 uk+1
A (F(* x) + Au+1 (F (xx+1), xx+1) + A (#x+11 xb+1 vk+2) 1/2 || uk+1
for any x E X. Summing up this inequality over 0, 1, ..... and changing the counter + 1 to k yields that
du (F(x),, In -x) E6-ET d (F x)+ Σ (F(F)z)) Tx - Uk+1) - 1 U 11
(33)
18

---

Using the update formula for St-+1 and letting so Oa R we have
(ALF( x) 8k-1 8k, 2²) (80 ST, x) (sr, nz). (34)
Since 24+1 E X satisfies have
(Sh (IR), x xR) 11 un 1l 81|25 ux vxll?
for all x E X,
(35)
where (x) Rd - IR defined in 10 Letting x = uk+1 in (35) we have
(S (zx). Th Ukti) S 1 || - uxll - 81122 2n 1|?
(36)
Then,
(F(x))), Uk+1)
(F(xx) - 12% (2ra) + n76 (Ix - vk) + 511| - Ux (xl1(xx uv), xx - UR+1)
(1 (It). 2k Uk+1) 51 . 1x - 0k, J+ - uk+1) 176 Uk. 26 (k+1)
Lem.
f11 - Un 11 120 un+ |1 + 6||20 - vn ll || - uk+il |l $ 411 - ox ( 81|2rx - Un 1x
x* 2k (ara Uk. 2h uk+1) (x - 0k. 2 vk+1)
Next, using (I Uk. 2K uk+1) 2 | ux 11? 1| vxllllu uktil and || uk+ill S |
e + 11 - UA 1 we get
(F(r)), IE Uh-11
S 1/2 || - 12 + 2/2 1|: - Us vx
1 U2 U ||| 6|125 - w/ll + 811.rx - Ux 11 - Uk+11
+ 2 || - uk + 8||20 - 2x - 5L|1 - u/ll + 5L|123 [x - uu 1121/uu Us+1ll - -noll1a - -2x12
+11ō 1la - vx || UR+Ill
4 -0 - u2 12112112 - ux+ill 4L 12 + (n + +)) - 22 exlllva - Bktill - -177 22)6611 - -v.1
Next,
II <
11d2 | uxll uktill 41xL[(xx rxlls
+n 1)6 | 1xllloe U2++1 (n - -2)8 vall= - 11
Uk- 11²)
T
< Σ
(H un v1 u++ill {1|kra vuil²² - 1llv vR+ill? 112)
where the last inequality is due to the following choice of " 10 and A
A (5 vxll + +0) S + Then,
T II
Σ Jmn
velllle - uktall - _11200 vxll bllue 0642l13)
(37)
Σ Etmillarg ex mxx11?)
Plugging and
34
337 into
33
yields that
T
T
ArFF(r)) - x) < Eo Ex + (ST, x0)
Σ
| vall? -usl?
km
19

---

Lemma B.2 Let Assumptions 1.2 1.3 2.1
hold and let x E X. For every integer T 2 1, we have
(F - 211 zoll?
uxl1 S 411=" -roll? Σ a
(38)
where x² E X denotes the weak solution to the VI.
Proof. For any x E X, we have
Er (ST, ro) = max (sT, 2o) 211e zul? (sr, -ro)- NE
Since 80 Od, we have Eg = and
Eo - + (sT, σo) - - ((ST, x - xo) - 21110 - + (ST, x ro) = 2/1l1= xo zoll?
This together with Lemma B.1 yields that
T
T Σ
(F(((()), - x) +
|0 vull2 | -zol,, for all a E X,
which implies the first inequality. Since the VI satisfies the Minty condition, there exists X' such that (F(x),, Th - x²) 2 0 for all k 2 1. Letting x = x² in the above inequality yields the second inequality.
Lemma B.3 Let Assumptions
1.2
2.1 hold. For every integer 2 1, we have
2048L - xol12
20485
(39)
Σ
T3
7
Rx=1
where X denotes the weak solution to the VI.
Proof. Without loss of generality, we assume that Du # x². We have
T
T
T Σ
Σ
(nk)
(Ak) (Ax ( [1 - vkll + +0))
( ak - -vll + +)²
32
1=1
k=1
T Ix 2x 2T
Lemma 72
21²1
zool² 2 2T82.
By the Hölder inequality, we have
1/3
2/3
((.))))) (Aa)2/3
Σ
(1x)
Σ
A
k=1
k=
Putting these pieces together yields that
2/3
T < 323 |0- xol12 1 282T)3
Plugging this into the above inequality yields that
1
2048 1|
xoll
20488 T2
ET dv)
73
Theorem 3.2 Let Assumptions 1.2 1.1 2.1 Then, after T 2 11 itterations of VIJI with parameters 6, 17 10, opt get the following bound
GAP(ăT) sup (F(x), zEZ
x²) S
16/2LDD T372
16./2D2
20

---

Proof. Letting x: E X, we derive from the monotonicity of F and the definition of 7T (i.e., opt = 0) that
T
(F(z), - 2) Et= Σ
(F((())) - σ)
Ak=l
Combining this inequality with the first inequality in Lemma
B.2 yields that
(F(z), ēT - x)) S ||===ol? 2())-1
for all E X.
Since zo E X, we have || - xoll _ D and hence
(F'()), Ør x) S 2 An)
for all a E X.
Then, combine Lemma B.3 and the fact that ||2 Tull S D to obtain that
D2
2048L2D2
204862
16v2LDs
16v28D
(F(*), ET - 2) a)
for all x E X.
T
T3/2
By the definition of a gap function.
4 we have
GAP(ăT) sup (F(x), ēT x) 1
10vZLD 23/2
16v28D
(40)
zEx
B.2 Proof of Theorem 3.3
We directly follow the steps of the proof of Theorem 3.2 Lemmas B.1 B.
remain the same.
Because of the choice of 8x41 1 | U
adaptive strategy for A looks as follows:
1 I L 2 u++1/l S 22. Next Lemma is counterpart of Lemma B.3
32
Lemma B.4 Let Assumplions
1.2
1.3
2.7 hold. For every integer T 2 1, we have
64L||x* -xoll
(41)
k== Ave
T3/2
where x² X denotes the weak solution to the VI.
Proof. Without loss of generality, we assume that Fa * x² We have
Lemma 12.2
Σ (Aa)
(Ac) 2e)-=(AAe (Ae (T.1)0r 12)) <
I,2 1 late
1//1
AT.2110"
roll
1=1
k=1
By the Hölder inequality, we have
T
1/3
T
2/3
Σ1-Σ
(Ax)
(1x) E(u)
Σ
A
A=
1=
1=
km
Putting these pieces together yields that
T
2/3
20l13)3 T s 32 (AT,?|/-- -
Σ A=
Plugging this into the above inequality yields that
64 64 xoll
Σ Av
T3/2
Then, by following the rest of the proof Theorem 3.2
we get
Theorem 3.3 Let Assumptions 1.2 1.1 hold. Let { vn be iterates generated by Algorithm 7 and
[(V) (ux bx vw]ll < dæl1=x - mall. ll.
6% S l ||
Ukll.
Then, after T 2 iterations of Algorithm with parameters 3t = 1/ I|aT vkll. 17 10, opt 0. we get the following bound
GAP(ET) sup (F(z), HT - xx 32L.D
7372
xex
21

---

C Proofs of Theorems 3.4, 3.5
In this section, we let L L1.
Theorem 3.4 Let Assumptions 7.2
1.3
2.1 hold. Then after T 2 we get the following bound
iterations of Algorithm 7 with
parameters Bg 6, = 10, opt
= =0 LD
8D2
RES(
sup (F(iT), (T x)= =EX'
(42)
T
VT
Proof. Since we consider opt then
RES(G) RES( sup (F(Tkr J x))
xEX
From 36 we get
(F(x)), 2h - x) (F(#)) 27, (I - + (1 (Irx), Th x)
L
(43)
[F(x)) 2% (xx)lll|<> 211
u 3 5 21 2x
2
Next, from triangle inequality we have
5L
[F(x)) 1/ (Ix)] = F(xx)) - 22 (1rk) - 1/0(xx - -xx-) +
1 - uk (2 wxm)
2
5L
[F((x)) - 22, (rx=) -116111 - wxll
| 1xe122
2
From this and 22 we get
5L
|| - 22, (I+x)] - 2 |1 uxll + 61|2r uxll +
n101 wall +
| -rxl'
2
3L 22 12ll 8(n + 1))l=x rxll-
Now, return
43
(F(#)), 5k - x)
15
3T. 3T.11222 - U/ll 1 .|| 8(17 + 1) 1) - vie [|ll| It xl| + 2 |1:r rxl13 + 51l.r 1xl1
= -|| - ux 33120 - æ|| + マ || vell + _| - en ll ((n + 1))l> x11 + || - -well)
Since D m || - -/l.
(F(xx), In .) - LD 10 en 8(1 + 2) - vxll-
(44)
Next, from second inequality from (38) and from definition of dey in Algorithm
we obtain
4 4|1x²
=ool2
Ia Ukey 11 min I
1| Uk
20 ukl
(45)
T
Since 44 holds for any x. E X. we get final result
14LD
"x" - zool
25(1 + 2)D((x" xoll
RES (Dkr) sup (F(*k), NEX
T
VT
14LD3 s
25(n + 2)
14LD3
2AD
+
VT
T
VT
Theorem 3.5 Let Assumptions
1.2
1.3 hold. Let {œv, Uk be iterates generated by Algorithm 7 that
satisfy (14). Then after T 2 iterations of Algorithm with parameters 83. = 1| 06 1. 17 = 10, opt we get the following bound
(ES(
sup (F(+r), x
Rr x) 385, D
(46)
The proof of this theorem repeats the proof of Theorem 3.4 with 8 < 1| -kll-
22

---

D Proof of Theorem 4.3
Theorem Let some first-order method M satisfy Assumption 4.1 and have access only 8-inexact first-order oracle 15 Assume the method M ensures for any Lo zerzororrrder smooth and Li-fist-order smooth monotone operator F the following convergence rate
CAP(&) < 0(1) max
SD2 (T)
D (T)
Then for all 2 we have
(T) T,
(T) S T
Proof. We prove this Theorem by contradiction. Assume the existence of method M that satisfies the conditions of Theorem 4.3 and achieves faster rate in one of the terms (T8).
First, suppose (T") 7. Consider the first-order lower bound from [89]. which is established using a quadratic min-max problem as the worst-case function. In this scenario, the operator has
O-Lipschitz continuous Jacobian. Applying first-order method .M this lower bound and using an
inexact Jacobian (xx Lylaxd. yields the rate O La
(ET(T)) ET(T) > T, which is faster than the
lower bound Ω
La D3 contradicting our assumption.
Secondly, let us assume E2(T)) 73/2. The lower bound for exact second-order methods is By taking exact Jacobian in the method M (6 0), place M in the class of exact second-order methods. Consequently, we obtain contradiction with the lower bound.
Ω
DD 1972
669
E Proof of Theorem 5.1
Proof. The proof is common for both formulas (20 and (1 where a = 1 for classical L-Broyden approximation and a m for Damped L-Broyden approximation. First, from Lo-zero-order smoothness, get
VF(2)) - Jzllop & [ + +1Jo lop I Lo + ||Sollop
Now, we upper-bound |Jallep || op by induction:
||
< op
<
jz (1
as,
az.
Hp
J (1
+
l1ve
|| 1lop + Le.
as.
as
as
op
03.
where the last inequality is coming from Lo-zero-order smoothness for operator difference or JVP.
By summing up the previous inequality for in 0, ...... m 1, we get || I Finally, we prove the result of Theorem 5.1
-1 + mLa
F Proof of Theorem 6.2
In this section, we let L L1
Theorem 6.2 Let Assumptions 1.2
6.1 2.1
hold. Then the total number of iterations of Algorithm
reach desired accuracy || x
is
o ((
i +
(1 ( llg 21)
LD
23

---

Proof. From the definition of žy, Jensen inequality, strong monotonicity minty problem and Lemmas B.2 B.3
25
definition of strong
we get
u||
x²11 1
(Auar )2x00)
k==
de
k=1
T
1
d A| xx111
d
k=
leml
A (F(Ix) - 2x x²)
k= k=1
A (F((x), -xx)
kk=
2048L |T
x=1 1|
204882
100 - x²1 2
73
T
2048LL||ag
20 x=
20485 T
2 max
1 2
x= 112
73
21 12 1. Now we run Algorithm in cycle for i 1, .... n and restart every time its distance to the solution becomes at least twice less than R4-1. Thus, let T3 be number of iterations we run Algorithm
Denote R = D,
| inside cycle of Algorithm 2 In other words, let Tü be such that Ri-1 where ēт. is the point, where we restart Algorithm Then the number of
|āT.,, x²1 S 2 iterations before the i-th restart is
2048L R?
204882)
})
11|0r x²112 =
2 max
R
TH
T
(47)
uR
4
2048T.2 R2
204882
})
/
max
72
T
2v
Deriving T. for each case under max, we get
2 L
2 278
Thus,
2 3 R3
276 11
T.
max
(48)
3
Now we calculate the total number of restarts to reach
|
x=" S e. From 47
we can get that
2048L2 R2
204852
))
1
|
201l s
2 max
R
T3
2
Rm-1
112
11 ))
max
22μ
Rn-1
2
= R- 12-2-(n-1) (n-1)-1 < E.
24

---

Deriving from last inequality, we get
log
(49)
Now we provide auxiliary estimation, that we will need next:
20
x
R
2
:=1
==1
1
2
x=1
(50)
2$
Io
< 3 D3.
Finally, we can get the total number of iterations of Algorithm D insidee Algorithm
14 L 276
B
max
1
3 L R
276
+
11
2 L
276
n
+ m
1
11
60
49
2 D
2276
+
log
1
Thus,
(1T)
[.D
0
-
+1
[log L
This completes the proof.
G
Tensor generalization with more details
G.1
Preliminaries
Algorithm 3 VIHI
Input: initial point xo X, parameters Lt. 7), sequence ( and opt e {0, 1,2]. Initialization: set 8g = Rdd for à 0, 0,1,2, ..2,.... do
Compute Uk+1 argmax, (8k, vo) | xo 2)
Compute Ik+1 E X such that condition (53) holds true.
Compute AR+1 such that
((5-2)) & d
Iip-1 |,0
24 1-1 + Σ
|| unll uxll=-1)
[[5+1]
Compute 84+1 3k A F (x1+11) ØT
T AgTTK
if opt
Eke
de
Output: à
PT Tky for kr argmin
else if opt = 1,
SKST | vall
else if opt 2.
25

---

In this section, we provide more details on the generalization of Algorithm with high-order derivatives. We provide the pseudocode of the resulting method in Algorithm convergence of Algorithm
To show the
we use the Lyapunov function (30).
Define the (p- 1)-th order approximations of the F
t p2) - F(u) +
V'P(o)/--uj
(51)
V px)( F(u)
G(v)(r-u]]
(52)
i!
On each step, our method solves the following subproblem:
sup (Pp.rr (xx), 26 x) S pd
f--1
10
Σ
|aa - uslll*!
(53)
ZEX'
Additionally, we will need an auxiliary result from [52], based on Assumption 4.2
The authors show,
that this Assumption allows to control the quality of approximation of operator F by its high-order Taylor polynomial:
[F())) (p,o(=)] s
1- || - =ll pt
(54)
G.2
Auxiliary lemmas
First of all, we provide high-order generalizations of auxiliary lemmas for second-order case from Section A
Lemma G.1 Let Assumptions
7.1 and 4.2 with = p 1 hold. Then, for any x, v E X
[[F(v)) 1 pp,(
l uIl Σ 1 w11..
(55)
Proof.
[F(v) 4 (x)( S [I((v) p 1 v (x)]
-
HI(( G.(u))] u| wl
| w1|
8 || u
Lemma G.2 Let Assumptions L.I I and 4.2 with = -p- - hold. Then for any x, Uk+1 E X
VI is relatively strongly monotone of 1h
(VDp, (z) V2p.o
(|| 01| I, Ixxn + || w11p- 3 (x v)(x -) 1リ-
1سيا1
6 || - د|اا ((n= i)(|= 2 + mm(i - 1)(x u) -
26

---

Proof.
2/2 (Vlpo(z)+ Vopp0())) (xp.(())))
Σ কーصح (ci(u)(z (G(w))(=-o) (G/0/// -()())((-))))()))
nudr o!
(| - 0||
nxn + (i 1-]1]|==- - 3/1 u)(2 7)²)
(1|=
(p- Ij!
(VF(x) + V)())))
1-- ||
211 Inn
T1-1)] f| - = Inx
no: e!
(| - --|1- Iuxa (1- (i-1)||z u1|2 311"-3(00
v)(s3 7)²)
(p-1)) (||= - u1|001 Inx + (p 1)1[z 0/10-3 (x (z =))²)
ارككة
2/ (VF(x) (z) + (
ارما (p-1j) ||
-1|0
I nxn + 54 p-1 | |- (x: - f) - w)²
2]1
(m 1)||=
u1l'~ Inx
(1(((i11)
| - 011i~3 (s u) (2 T)T.
From monotonicity of F we know that 1 (F(x)) F(x)T)== = O. Thus,
(V + (xp
4T.p 1 (p-1) 131
||
2 o1|p-1 Lnxn
55,
|| 2/ 3|1-~((2 32 t)(x 1)²T (p- 2jí
(m= i)||= -ill Inxn
nd.(i-1) x - $1 (x 2) o)².
1=1
By rearranging the terms we get
(V (p + VL (x))
サ (1|= b||l- 1nx + ||00 w1lp 3 (x - u)( - v)²)
4 x - -1|ا (In: - 0](|= u1l21 + 1/ - 1)(x v)(x - u)²).
Thus, if n 2 p. we get that 1 (Vlpm in (x) + V (1)p)(11()77 is relatively strongly monotone.
G.3 Convergence in monotone case
In this subsection we provide theoretical results directly connected to convergence rate of Algorithm Firstly, we need to introduce additional technical lemmas, that generalize corresponding lemmas in Section
Lemma G.3 Let Assumption 1.] hold and 1)= = 5p. Then, for every T 2 1, we have
T
(Z4) 2o x) S Eo Er + (st, xo)
1 1o
1/6 11.
(56)
8
k=1
27

---

Proof. Since the first steps in the proof of this Lemma are the same as in Lemma B.1 we start our reasoning from [3):
T
T
xx -x) s ET
A (F(x)) (o - x) + )x uk+1) - 2 ux+1 11
(57)
Using the update formula for 81++1 and letting 80 Oa E IRd, we have
(A,F(Ix), 2) (s sk: SR x) (ST, z0)
(58)
Now consider II. Using
28 get
(F(xx), Ik Uk+1)
FF
F
V
pim (Tx), Fh Uk+1) + (12 (Ix), , 2x un+1)
p
nd
| - vkl i-1 (ax - Uki 2/ - uR+1)
e!
p 1}1
1
U 11 (xx Uk. 24 ck+1)
p-1
Lp-1 p
|
Uk 12/1=11>xx
uk+ill
x7 5 us prllillarx Uk+1 (Pp. (0xk), Dk+1)
i=1
niós i!
||
ukl |1| (xx - Uk ok+1)
5T,
|| vxll=-1 (Ir UK, uk+1).
Next, using (ER U2
1k+ 1)
2 |2 vul2 - || vallllua uh+ and || ex+1ll s
|| Un + 1lu2 - 1x- 11. we get
(F(xx), xx - vk+1)
uu (1|aa
+ v1ll
||:00 un uullp|lux ve+1ll
fo.
ex (112
p it1 || lxll'lee - vx+1ll)
2x 11 - -11 2x 1' 2k+1 II) 2:6 (1|
(I| - -u ||aT - vn mm/lil/ux - vxtill) 5 lj!
(Sp.vr (Ixx), Tk wk+1).
From definition of the subproblem
533 we have that
p
(Ap.re (Ix), xx - vk+1) S sup (Sp.ve (Ix), xx - x) S pf
L
|| - 1x 11 +
[
xex
Thus,
(F(xk), Ik - Uk+1)
4p=1(1+pp) pd
uk 11 ux Uk+1/l |
Lp- (5p-2)
|
U% p+1
p.
5, (1(1+)))) i!
|
10 vstall
61(m
2) ||
1/6 1-1
1=1
28

---

From this we get
II =
A (F(xx). - ux+1) 211ux uk+1ll
km1
A 1p- (1+bpp) pd
|| Ux 11 uk+ 1ll
A (5p-22) 120 un 1
pp
+ A
(1++m) d
|| - 1x11
ux+1ll
A
6((m 22)
|| 2//1
1 1x+1
1!
i=
p-1
0:=5p
As
ppr
I
uxll
10111-1 1 + Σ
| oz 0zlli-11
(5p + 1)]l2rx uxll ex uk- 11
A
|,00
- uk
11-11
latk
wxll vxll-11)
(5p- - 2)/1000 - rx 1 - 1k+1l13
(5p
Now, if we choose Dg such way that
N
Fy 1
110
- 2x 2x11=-2
2 || vxll6-11 S 2[6p+1]
(59)
4(6p 2)
pl
we get the following
T
us vxllluu Ux+1 || 1 1
wa+ |13]
1=1
22 max
uxll 2r
11120 2k 11?
| - ux11 2 g11 - rx/l"
|| 1x.1
a0 22
k=1
Finally, combining estimations of I and with (57). we get
A (F(xs), xx - x) s Eo Er + (ST, x - 20) - Σ || Ux
Lemma G.4 Let Assumptions 4.2 1.3 hold. For every T 2 we have
2F 2
(20p
8)
L--1 1x- - 2ol
p
2r m +2 p (20p-
8)
(60)
ΣT Σk=1
d
iT
Proof. From Hölder inequality
T
T
Aa
2
k=1
A
29

---

Consider denominator:
59
(4(5p- - 2)) ف 2)) 25
1|20 (m17
[ip-1
2x 11110-1
p-1
6i
1a
uk
11 18-1
pl
i!
,
T
Lp-1
6i ||:
(20p- - 8)
||ax
ux
1x118-1
ux ux| 1||
p!
i!
1=1
For p 2 we have
2 P-T
=2,
p= 2,
p-1 1
p 3.
Consider some nonnegative sequence {a- a 2 0, Vi E I,n]. For p from Jensen inequality we know that (Ei=1 a²)² S Ei= naf. From Lemma 7 of [65] we know that 4/q E [0. 1). y >
0 + (x y) I x² + y². Thus, for p 2 3 we can come to the same conclusion: (Ei=1 a,)= - =
E= of S >i= na;
I In other words,
Σ at
n0
Vp 2 2, a, 0.
(61)
1=1
i=1
Using this inequality, we get
T
Tpp1
T
0
208-1)
k
p(20p 8)
n-T
p!
| - 222l2 + p(20p - 8) F-T
i!
|
2/
P-1
k=
l
k=
i=1
4p(20p 8)--1
Lpp11
p-1
||x"
xol1? + p(20p - 8)
p-1
ukl
2(-11 p-
p!
202 p-1
Consider the second factor in this inequality. If we denote ag-
=
1|
Ukl
by = 1, c=
d p-1 then we can use Hölder inequality:
T-T
n
lanbul
Σ
12
laxl
l
Y2
1b ld
1
1.
c
d
From this get
2
ukll
26 11
< Σ Ia
1xl1
41|2* - xoll
p-1 _
Thus,
Σ k k=1
< 4p(20p- - 8)=²
Lpp-1
1100 - 20.22 +p
8)=²
Σ
1
6
xall
2(1-1) p-1
T
p!
i!
1=
Consider (a + b) ",, p 2 2. For p- = 2 from Lemma 7 in 65
we get (a + b)}
< a+
+04
2(a + b²). For p 2 3 we have from Jensen inequality (a + b) -
+b+)
25 a p-1 +b p-1 In other words.
(a + b) 2 22 -0²
Vp
30

---

Thus,
Σ 4
p--
2 (4p) 1
(20p- 8)
1-p
1| xoll
10100-11 (4p) - (20p 8)
Σ
1
roll
24
p-1
T=-1
p!
i!
- 2"p =
(20p -8
Lp-1 12 1 -xol 10 + +2
p
x
xoll"
11:--117 1
p!
i!
= 2 p - (20p - 8)
1--
1| xol1--
1 + 2 32
(20p
8)
1
6
x
ro
xool"
1T
p!
i
1=1
Now, we can get the final result
T
-k==1 Ax
ΣV
k= dB
7
< (20p
2ºp
8) L--1
1
x0
1,
-
22
1
(20p
8)
p-
6 x
xo xoll= 6-1
T
11
iT
Finally, we provide the convergence rate of Algorithm 3 in monotone case.
Theorem 7.2 Let Assumptions 1.1 4.2 with i 1, and 7.1 Whold Then, after T 2 VIHI with parameters yi = 5p. opt 0, we get the following bound
7.
iterations of
GAP(TT)= = sup (F(x), x) S. =EA
(p-1 DP+1
p 1init1 Σ
T
11 T
Proof. Consider Vo X, opt =
(F(x), FT x.)
T N (F(*)), Fk - x)
50
D2
1| - 20ll2 5
Σ AB k-1
Σ A 2
> d
60
(20p 8) - DP+1 DP+1 2 p
+
2
(20p 8)
p-
D,
p!T pTT
i!
دلن
Thus,
L Lp-1De+1
D,+++1
GAP( sup (F(z), ë7 - x² =0 xEX
T
F=1
-
i=1
G.4
Convergence nonmonotone case
To make our paper more self-contained, we provide convergence rate of Algorithm 3 in nonmonotone
case.
Theorem
7.3
Let Assumptions 4.2 1.3 (and 7.1 with = p- 1 hold. Then after T > 1 iterations of
Algorithm with parameters 1) = 5p, opt we get the following bound
RES($) == sup (F())) $4 - I) =0 (p-- DP+1
8 p- D
sup xEX
T
31

---

Proof. Consider (F(xx); 24 - r).
(F(re). uh - x) - (F(22) - Ppime (IA), a0 xx) + (9 (Irx), Ttk - x)
[[((x)) Pp. (11x) xi|1 1p-1 vall
12
valp
| uxll"* 11
p'
From definition of v prve (xxx) and triangle inequality we get
5hp-1
p 1
nio
[[F(xa)) Mpn. (Ix)) = [[x()))) - Spive (rx))l
I0 - 1xll
I Ux|l"
(p - 1)!
i!
i=
From this and 55 we get
[[F((z)) Pp.us (xw)ll
1p p!
10 22ll" 1
+
p-1
8,1113 - 1261' + 5lp-1
1,00 - 12 +
p
ne.
1
2x
i!
(p 1)1
i!
1=1
i= 1
(5p + 1))l.x L--1 p!
p-1
6: (1) + 1)11=x - ex
1xl1?
Thus,
(F(xx), IKk z)
1--1 1 (5p + 1)1l,x - Us 1211,
p
x1| +
(n) 1)1l=
vell"11> æl1
p!
i!
Lp-1 1| - Ux 1x11t11 +
6
+
||ax - cxllitt
p!
i!
T
8 ||a, ekll' exl1"(11 + 2)D.
1xll""(pp + 2)
p!
From second inequality of (38) and definition of Øky
we get
T
4 10" roll2 S 4D2
|aak 0k, 11
min I
1
vill2 S
|
- m& 1x
S
T
T
k=1
+ |,
Ukr
T
Combining all these results, we get
p-1
L |00 un
RES( = sup (F(zz), Ix x) S
2)D l5p
+
+
I - v + 2)
x
p!
1!
i=1
2D 25 + 2) Top DP+1
2'0; (m/ 2)
D++1
p!
T
à
11p-1 I De+1
8, Di+1
0
T
T
H Subproblem solution
For r-rank QN approximation J"' from
19
we can effectively compute F(x), where A, =
Jr + (175 + 5L using the Woodbury matrix identity 96 97
2 r)I = UT CV+ + (n +
5L
I
- CV + B and B J + (nō + 5L 2
7) by
2
F(')(z) = (B+U*) U CV) CVV F(z) B
(Fa) 1 F(x).
32

---

For Jo = :I, the identity could be simplified even more. Hence, B = = 54 T)
XI, where
X == - 176 + -/ Then,
F(x) (x
I Experiment details
We consider the cubic regularized bilinear min-mas problem of the form:
min max f(x, 3) y (Ar b) + =||=11, s #ER yER
(63)
where p >> 0, = 11,0
0] E R2 and A Rddd such that
0 1
-1
=
".
0
0
1
-1
0
0
1
To reformulate variational inequality, we define F(x) fz. Vv (2) Following
71 we plot the restricted primal-dual gap (65) written in closed form:
2 2 || B|1Az bll +
gap(z, B)
A yll +
3/ p
where = (x, y).
Setup. All methods and experiments were performed using Python 3.11.5, PyTorch 2.1.2, numpy 1.24.3 on a 16-inch MacBook Pro 2023 with an Apple M2 Pro and 32GB memory.
Parameters. For Figure 1 the dimension of the problem d 50. The regularizer is set to p le 3. The starting point (2). = (0, 0) is all zeroes. We present results of last iteration of each method opt=1 from Algorighm methods, we set memory size m = r = 20. We perform a total 100000 itcrations for all methods except Perseus2 with 1000 iterations. We plot each 500 iterations for better visualisation. In Figure 1 the left plot refers to the gap decrease per iteration and the right plot refers to the gap decrease per TVP/operator computations. EG, Perseusl, VIQA computes 2 operators per iteration and Perseus2 computes + 1 JVP/operators
The diameter 3 for the gap is set 8 1. For QN
We finetuned learning rate and presented the run with the best results. For EGI: Ir 0.5. For Perseusl: Lo = 0.2334. For Perseus2: L1 = 0.0001. For VIQA Broyden: L = 0.001, 5 j 0.4. For VIQA Damped Broyden: L1 = 0.001, 5 j 0.22. Note, that tuned L1 0.001 is actually a theoretical smoothness constant for the problem (63) and can be chosen with such value without finetuning. Also, Perseus2 is working with smaller constant than theoretical.
Application to minmax problems
J.1 Preliminaries
In this section, consider the problem of finding global saddle point of the following min-max optimization problem:
min [(x, v): #ER yER"
(64)
i.c., tuple (x", y²) E T _R such that
f(x",8) < f(x", ((""""")= S f(x,y"), for all x E Rm, E R",
where the continuously differentiable objective function f convex-concave: f(x, y) convex for all y Rn and concave in for all m
33

---

min Algorithm 4 VIJI-MinMax
Input: initial point 2o E parameters L1, ò, 17,
Initialization: set So = 0 E Rd.
for k .. do
Set Up++1 20 + 8k+11
Compute 2k++1 IR such that condition
68
holds true.
Compute Ak+1 such that TO I Ax+1
(
uktil 1l + 6)
Compute 5k+1 5k:
AR+1 (x+1F(ZE+1).
Output: ET EtSi de Σ dg2k.
Assumption J.1 The function f(x,y) C² has L-Lipschizz-comtiioous second-order derivative if f(=)) & L||= - v/l. for all E IR IR*+
Following [71]. we define the restricted gap function measure the optimality of point (i, 9)
gap(2, 3)
max wellw~b'lls 115.88
( v)
(xx 9)
(65)
-=||---> 11
where 3 is sufficiently large such that || 201 B.
Problem (64) a special case of VI defined by the following operator
Vxf(x, v) Vy Vxl(E
F(z)
(66)
The Jacobian of F is defined as follows
22 zg. (I,
V2 (2g((z)))
F²F(e)
(67)
V (x,
-V Va
The following lemma
80
provides properties of operator F.
Lemma J.2 Let Assumption J.7 hold. Then
The operator F is monotone, i.e. satisfies Assumption 1.1
2. The operator F is L-smooth, i.e. satisfies Assumption 1.2.
3. F(2*) = 0 for any global saddle point z" E R=+m of the function f.
We assume that inexact approximation of Jacobian satisfies Assumption 2.1
J.2 The method
Since consider unconstrained minmax optimization, Step 2 of VIJI simplifies uk+1 20 8k and the subproblem (1T) changes to
find 24+1 E 1a+ such that Ω7 2% (2x-1) 0.
Usually, to find the solution of this subproblem it is necessary to run some addition subroutine. Following the work (71. we introduce the following approximate condition:
1 (2++1)ll < min [1 u2+1ll + 5) 2++1 11
(68)
where 7 E (0, 1) is a tolerance parameter.
The version of VIII for unconstrained min-max problems is referred to VIJI-MinMax and is
detailed in Algorithm 4 This subproblem can solved by strategy proposed (71), resulting in
O ((n + e -2/3 + (n m -2/3 22/ log log(1/e)) complexity, where 2.3728 is the matrix multiplication constant.
34

---

J.3
Convergence analysis
The following theorem provides convergence rate for Algorithm
Theorem J.3 Let Assumptions J.7 2.7 hold. Then, after T 1 iterations of VIJI-MinMax with parameters = 5, we get the following bound
gap ēT, () -
1152v2L 20
576v26 20 20-2"
T3/2
where B = =0 21 x² = (x",
Now, let introduce additional assumption on 8, to obtain the convergence with optimal rate O(s 223)).
Theorem J.4 Let Assumptions 7.7 hold. Let
[(())(u)) J(2x))(2 uxll $ 6xl1=x - vell
hold for iterates (zu, v generated by Algorithm 4 where
6% S L/ -xll-
(69)
Then, after T 2 iterations of VIJI-MinMMo with parameters 5, get the following bound
gap(Er, 1944v/21.| -
73/2
where B = =5|120 21 x² = v²).
Note, that is also possible to change adaptive strategy for Å in this case 1 - L11= uull S (by introducing parameter /3 as Algorithm [b to eliminate the dependence on from the step size while achieving the same convergence rate.
Finally, let us show, that we mathch the convergence of under the same assumptions on Jacobian's 's inexactness and subproblem's solution.
Assumption J.5 ((71) Let
[(VV((v)) - (Fx))[E vxlll 8ullzE vull. [[](w)]] s
hold for iterates (zk, vi) generated by Algorithm where
5% < min
To. 4N46L
L(1-T)
[((W))))
(70)
where < 4.
Next, we show, that (69) follows from 770
Let consider cases. If || zι vxll < 1, then from 70 we get dæ S To||=ı vxll s 1/2 1| vxll
Otherwise, if || e 2 1, we obtain from (68)
[[F()))]l [J(*))] || - rull 21 exll
uxll - Vi (2x) s F(xx)) 5L
Using our assumptions, get
- (1=))([F(m21I1 s xl|= wxll 8||2 vxll 5T.[= mmll2 S (Is 55.]l vall
(N + 2 T.)l uxll-
Next,
8
-(l-r) F(u))l L| vxll. 4x
Thus, the assumptions of Theorem J.4 hold, and Algorithm achieves 2233 convergence.
35

---

J.4 Proof of Theorem J.3
Again, as in the proof of Theorem 3.2 we introduce the Lyapunov function
&
max R trm
(sk,
zu)
2 ||e 20ll?.
(71)
Note that the scalar product (sk, w' 20) can be omitted (see the proof of Theorems 3.1, 4.1]), which would also eliminate the somewhat redundant Step 2 of Algorithm However, we chose to retain it, as does not affect the method's performance. We retain
Lemma J.6 Let Assumptions 1. 2. hold. Then, for every integer T 2 1, we have
Σ (F((E))) 2) S Eg- ET (sT, 20)
1 rx rall?) for all RRt*..
Proof. Following the proof of Lemma B.I arrive (35). where the proofs begin slightly
diverge due to the changes in the subproblem. At this juncture, we have:
T
(F(x))) =k 2) s Eo Er + (ST, -00 da (F(z))) =k (k+1)
|1
Uk+ 11
II
(72)
Then.
(F(z*), 23 uk+1)
(F(zk) 22 (zx) + n70(2 Uk) + 5L 2x U/ 1xll(2k Uk): 2x Uk+1)
+ -,2 (Ex); 2h: Uk41) 5 |2 vs (zx Uk 24 Uk++)
116 (=x Uks 2h Uk+1)
Lem.
222
68
L
us 1| uk+1 |1 8||2, v 1l uk+ill + TL 1|2* 1x117112x 1k+1ll 1|
+T0|| zx
"M|llle*
uk+1l || 51||2
vxl(<z
Uk 2x vk+1) Uk 2x Uk+1) 7z(
Next, using (2k Uk: 2k 2k+1) 2 1 - uxl1 - 2| - vxlllluk Ue+1l || and | uk+il 5 ||
uxll + 110: uk+1ll. we get
(F(Ek), 2x - uk+1)
$ (r+ + 1) 1| uxl1 31|3 + (7 + 1), L.
T
1| =x113 110g 2k+1ll 1l + (T + 1)81(2 - 0% 12ll
2
+(T + 1) 2k 111111e - Uk+1l
5L 2x
uxll(zx Uks 2x: - Uk++1) n0
Uk: 2x Uk+1)
<<1
3
6T.|| 2x vxll 11 uktill -4T.|| =k wk l|
+ (m 1) 0||=
- on 11|ux -e+ill (17 1) 011 z/ U4 11
Next,
II
S
Σ (11l k=1
- ux [|]] u4
-1 1| - rxl12 -// 11102 - U2 113)
where the last inequality is due to the following choice of f) = 10 and A
1 S de (T ukll + 5) & 12 Then,
16
T
11 -ex vxllllu us
Allze -ull2 - -11l Ux+1l 12 < -- ( 1l vull))
k=1
(73)
Plugging
73 into
72
yields that
da (F(x)) 2) S Eo Ex (sr, 2 20) -1
Σ 1| 2x
36

---

Next, Lemma B.2 can be applied. Next Lemma is a counterpart of Lemma B.3 for the current choice of X.
Lemma J.7 Let Assumptions 17 2. hold. For every integer T 2 1, we have
2048L
20 1
51282
(74)
E
AL
T3
T2
where x² E X denotes the weak solution to the VI.
Proof. Without loss of generality, we assume that zn + x². We have
T
(Ax)
16
(As) (As (Lile2 uell + 8))²
(Lil uull + 6)²
h=
Lemma 8.
2L 2x 11 2T82
812112"
2011 + --2822
k=1
By the Hölder inequality, we have
1/3
2/3
Σ Σ ((N)) (Ax)2/3
[uw)
Σ
A
Putting these pieces together yields that
2/3
T s 188. =ol12 + 202T) $/
A
Plugging this into the above inequality yields that
1
2048T21122* - 201
51282
7 +
Ek Ax:
T
Next, by Lemma I.6 we have
Lem T
T
>a (F((z)
2k
2) + -
Σ
1|
vnll?)
Eo ET + (ST z0)
k=1
71
00g
2n
12
1
UT - zol12 + (eT - 20, v- vo)-
20.0"
2
2
By applying Young's 's ineqaulity and the fact that 20 Up. we get
0 2 1lee =0112 + 4 |ox =0ll2 + ||="" 20ll2 = -1luu zoll2 + || - -2
Thus, we have 1|ux =ol |l s 2||2= zoll From Lemma B.2 we also have that || vnl S 21|="~20)) =0ll- Thus,
|/ve =11 < ||ua =al + ||20- ="Il < 3 z²1 < 3
|| Iz - x" || < 1 us I + || - 21ll < 5||20 - == = 3.
Lemma B.2 also implies
Σ Aa - 2) F(zx) s 21100 2/12.
37

---

By Proposition 71
Proposition 2.9], we have
T
Au(2 - 22 F((N))
f(2r. v) - f(x, S
1
Emsr de
Putting these pieces together yields
(( f(x (T) 2( de)
120 =212?
This together with Lemma J.7 yields
((Tr,y) [1,, v 8v2l|1z0 - ==111|20 2|12
4v 20
=|1²
T3/2
T
Since ||= ==11 S B for all 0, we have || - 2z S B. By the definition of the restricted gap
function, we have
gap(er,8) S
32v2L|| 1[||=00 ||+
10v2 ||+8)
T3/2
1152 2102/2
T:/2
Therefore, conclude from the above inequality that there exists some T such that the output satisfies that g)
J.5 Proof of Theorem J.4
Lemma (J.6) hold with slight modification in d adaptive strategy. Lemma B.2 also holds. Next we need slight modification of Lemma B.3 for the current choice of A.
Lemma J.8 Let Assumption J.1 For every integer 2 1, we have
54L || 2- 2011
(II AR
73
where x² X denotes the weak solution to the VI.
Proof. Without loss of generality, we assume that 2a + x² We have
T
(Ax) (Ax) (Ae) (As (L|lzx uall + 6))² =
(L11Ex uall + 6)²
9r. 4 =| 1x
Lemma 91. ||
zol12
A=1
By the Hölder inequality, we have
T
T'
T
1/3
2'
2/3
& ((A)) (Ax)2/3
Σ
k=1
Putting these pieces together yields that
2/3
T T (2 20113)$
Σ
Plugging this into the above inequality yields that
54L 2- - 2011
ΣT R==l Av
73
Next, directly following the steps proof of Theorem J.3 we get the following rate
19.1v/L 1
gap($r, B) <
23/2
38

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
We proposed an algorithm for variational inequalities with inexact Jacobians in Section 3 supported optimality by establishing the lower bound in Section introduced Quasi- Newton updates in Section 5 studied strongly-convex case in Section 6 and discussed tensor approach.
generalization in Section Section provides experimental results to validate our proposed
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as 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: the assumptions used in this paper are classical for methods for variational inequalities [69 [2]]. Our methods include the solution of auxilarary subproblem (as other
globally convergent second-order methods for VIs [69 21), which requires subsolver or addditional subroutine, what we explicitly stated. Moreover, we introduced the way to reduce the complexity and provided the computational cost of the proposed procedure.
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 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 few datasets 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 is low 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 of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and 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
39

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
For all theoretical results, we provide proofs in the main paper and Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a 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 or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: our algorithm listed in the paper (Algorithm) D and the details are fully described (Sections and 5). The expereimantal details for reproducibility are describes in Section & and Appendix The code is attached.
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 novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it 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 instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS 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) If the contribution is primarily a new algorithm, the paper should make it 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 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).
40

---

(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 to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: describe experimental details in Section 8 and Appendix | The code is attached, where all the methods implemented as Py Torch optimizers. Our experiments do not include datasets, but we provide the explicit definition of test functions.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
polppiscc/uullicguuddeeses http:///guuieeeeeeeuetubiiiibiia /Ct///oooeeeeeeeeeeeeeee ssinnooicciiy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If 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/eetails
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: describe experimental details in Section g and Appendix | The code is attached.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core paper to a level 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, 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: [Yes]
Justification: we test our optimizer on deterministic functions. Hence, the iteration of the methods are deterministic and provide deterministic solution.
41

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at 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 run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: describe compute resourses in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the 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 the paper conform, in every respect, with the NeurlPS Code of Ethics https: http:://nnuiiu.eeee wttpppp....ppuuubp ccc//ublic/Bthhccsddideelll
Answer: [Yes]
Justification: Yes, the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
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., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
42

---

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

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.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, palasets.papersstt paperswi thcode. com con/datases 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 are encouraged reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does 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 Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
44

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere 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 as the institution conducting the review.
45


Reviews:
[{"review_id": "AQa2wlwrSg", "reviewer": "Reviewer_7Fy2", "summary": "This paper presents a new second-order algorithm for variational inequalities that is applicable to inexact Jacobian. The complete convergence analysis and a theoretical lower bound are provided in the paper.", "questions": "1. What is the advantage of the proposed method over [60] since the convergence rate is not improved? To my understanding, the assumption of Jacobian inexactness in [60] is not suitable for quasi-newton. But why \"suitable to quasi-newton\" can be claimed as an advantage? \n2. Will inexact Jacobian causes more iterations to converge than exact Jacobian, which eventually leads to a higher complexity than exact Jacobian?", "limitations": "I did not see any negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. A novel second-order algorithm is proposed for variational inequalities that is able to deal with inexact Jacobian.\n2. Solid convergence analysis and a theoretical lower bounded are established.", "weaknesses": "The advantages of the proposed method over some related works are not stated clearly (see question 1).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 7Fy2,\n\nThank you for your valuable feedback! We appreciate your acknowledgment of the strengths of our work, including the tightness of the proposed upper and lower bounds. We also value your constructive feedback regarding areas that need further discussion, particularly in relation to related work. Below we answer your questions, and we will improve the discussion in the paper accordingly.\n\n> **Question 1** What is the advantage of the proposed method over [60] since the convergence rate is not improved? To my understanding, the assumption of Jacobian inexactness in [60] is not suitable for quasi-newton. But why \"suitable to quasi-newton\" can be claimed as an advantage?\n\n**Response**\n\nIndeed, when the inexactness level $\\delta$ is controllable, the rate $O(\\varepsilon^{-2/3})$ is not improved. However, $\\Omega(\\varepsilon^{-2/3})$ is the lower bound for exact algorithms, meaning any exact or inexact second-order algorithm cannot exceed this rate. Our algorithm can converge with an *arbitrary* inexactness level $\\delta \\geq 0$. Unlike [60], we do not need additional assumptions on the Jacobian's inexactness, allowing us to apply any approximation strategy satisfying $||J - \\nabla F|| \\leq \\delta$. While [60] works only with controllable inexactness, so the accuracy of Jacobian approximation on last iterations is necessarily very high.\nOne example is the Quasi-Newton (QN) update, which is widely used in modern minimization due to its practicality. Since it is typically hard to estimate the convergence of QN updates to the true Jacobian, the inexactness assumption proposed in [60] may not hold. Our algorithm can run with the worst-case estimation of the inexactness level of the QN update (Theorem 5.1), resulting in $O(\\varepsilon^{-1})$  global convergence and significantly reduced iteration cost (Section 5). Thus, we got a globally convergent QN algorithm for VIs that, in practice, outperforms first-order methods using only first-order information. In summary, the advantages of QN updates include cheap iterations, theoretical global convergence, and practical performance.\nAnother difference with [60] is that our method is applicable to general VIs, not only min-max problems.\nWe will improve the discussion at the end of Section 1. \n\n> **Question 2** Will inexact Jacobian causes more iterations to converge than exact Jacobian, which eventually leads to a higher complexity than exact Jacobian?\n\n**Response**\n\nYes, theoretically, we obtain the rate $O(\\tfrac{\\delta D^2}{T} + \\tfrac{L_1D^3}{T^{3/2}})$, which matches the optimal convergence rate of second-order methods when $\\delta \\leq \\tfrac{L_1 D}{\\sqrt{T}}$​. In practice, we observe that the total number of iterations for the second-order Perseus is smaller than that for the inexact QN algorithm VIQA. However, computing the Jacobian and solving the second-order subproblem in each iteration can be expensive for exact second-order methods, especially in high-dimensional settings. This is where our proposed approach benefits.", "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": "yiMvDh454I", "reviewer": "Reviewer_jz9w", "summary": "This paper studies the impact of inexactness Jacobian in second-order methods for solving variational inequalities.\n\nThis article is very informative， including a novel inexact second-order framework which achieves a convergence rate that matches the proposed lower bound, feasible solution to the sub problem, combination of quasi-Newton methods, and the generalization to the higher-order inexactness.\n\nOverall, I found this paper well-written and the results are neat and  interesting.", "questions": "See weakness.\n\nIn related work for convex optimization [3, 4], they also show the influence of inexact gradient on the convergence, it seems also important to discuss the behavior when $F(\\cdot)$ is inexact.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper gives a novel second-order methods that allows the inexactness of the Jacobian. The convergence rate of the proposed methods  matches the lower bound given by the authors, which is a nice and neat result.\n\n2. This paper involves solving sub VI problem, and implementation to quasi-Newton methods, which is practical.\n\n3. This paper is generally well-written.", "weaknesses": "There may lack some discussion on the related work:\n\nIn terms of the inexact Jacobian: It is very necessary to discuss the relation with one that considers the inexact Jacobian for convex optimization, especially the technical difficulties over them [3, 4].\n\nIn terms of the quasi-Newton methods for solving VI, the author may need to discuss [A] which does not require the symmetric QN update for saddle point problems.\n\nI will also be happy to see discussion on the **technical difficulties** in comparison with optimal second-order methods for solving VI, especially [59], where Algorithm 1 use very similar framework to.\n\n\n[A]. Liu C, Luo L. Quasi-Newton methods for saddle point problems. NeurIPS 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer jz9w,\n\nThank you for your thorough and insightful review of our paper! We are grateful for your recognition of the strengths of our work. We greatly appreciate your constructive feedback on areas needing further discussion. Below, we try to address the related works that prompted your questions. We will adjust the content in the paper accordingly.\n\n**Weakness 1** \n> In terms of the inexact Jacobian: It is very necessary to discuss the relation with one that considers the inexact Jacobian for convex optimization, especially the technical difficulties over them [3, 4].\n\n**Response**\n\n1. *The nature of algorithms*. The methods in [3, 4] are inexact versions of  Cubic Newton, while our algorithm is based on Perseus, a high-order generalization of Nesterov’s dual extrapolation. This results in completely different theoretical analyses. Additionally, the minimization algorithms in [3, 4] are not optimal for the case of exact derivatives, whereas our VI algorithm is optimal. \n2. *Subproblem solving*. While the methods in [3, 4] have minimization problems as subproblems, our method has a VI subproblem. This necessitates the use of different subroutines to solve these subproblems.\n3. *Inaccuracy in Jacobians (Hessians)*. We use the same assumptions regarding the inexactness of the Jacobian/Hessian. Similar to [3, 4], we have included an additional regularization term inside the model (eq. 10). In the case of minimization, this term makes the objective's model convex and majorizes the objective. For VIs, this term is crucial for ensuring that the method’s subproblem has a solution.\n4. *Symmetric vs. non-symmetric approximations*. The Jacobian is not necessarily a symmetric matrix, unlike the Hessian, leading to different approximation techniques. It might not be optimal to apply symmetric QN updates, such as SR1 and LBFGS, which are designed for minimization, to VI problems.\n\n**Weakness 2** \n\n>  In terms of the quasi-Newton methods for solving VI, the author may need to discuss [A] which does not require the symmetric QN update for saddle point problems.\n\n**Response**\n\nThank you for pointing out this work. We will add the citation to our paper. Here are a few differences between our approaches:\n1. [A] considers only min-max problems, not general VI.\n2. [A] focuses on local convergence, whereas our approach addresses global convergence.\n3. [A] uses symmetric QN approximations for the square of the Jacobian, while we construct truly non-symmetric QN approximations. \n\n**Weakness 3** \n>  I will also be happy to see discussion on the technical difficulties in comparison with optimal second-order methods for solving VI, especially [59], where Algorithm 1 use very similar framework to.\n\n**Response**\n\n1. Model. To ensure that the method’s subproblem has a solution in the case of an inexact Jacobian, we have to construct a different model of the objective. To tackle this problem (Lemma 3.1), we introduce an additional regularization term  $\\eta \\delta (x-v)$  in the model of the objective (eq. 10).\n\n2. The strategy chosen in Perseus [59] might not be suitable for the case of an inexact Jacobian, as it can lead to aggressive steps, slowing down the method. Thus, in our approach, the level of inexactness also affects the strategy for selecting adaptive step sizes in the dual space $\\lambda_k$.\n\n3. Theoretical analysis. \nFor simplicity, let us start with second-order methods. We use the same Lyapunov function as in [59]. Due to the inexactness in the Jacobian, the bound on the difference between the objective and its model depends on the inexactness level $\\delta$ (Lemma 2.2) as well as a criterion on the subproblem's solution (12). This leads to different analyses in Lemma B.1 and the necessity of a different strategy for $\\lambda_k$ (line 589). Since we’ve changed the rule for $\\lambda_k$, the bound on the sum of step sizes (Lemma B.3) changes as well, which finally leads to a convergence rate with explicit dependence on $\\delta$. \nFor the case of high-order methods, we again change the criteria for the subproblem's solution (eq. 53) and the step size policy (Algorithm 3): they depend on all inaccuracy levels $\\delta_i$. This leads to Lemma G4, where we use Hölder and Jensen inequalities to derive the bound on the sum of step sizes.\n\n**Question 1** \n\n> In related work for convex optimization [3, 4], they also show the influence of inexact gradient on the convergence, it seems also important to discuss the behavior when F(⋅) is inexact. \n\nThank you for your insightful commentary. Indeed, the dependence of the convergence on inexactness in the operator itself is an interesting open problem, which lies outside the scope of this work. We leave it for future research, as even stochastic dual extrapolation and dual extrapolation with inexact operators have not been studied in the literature yet.", "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": "iaFgN8yF27", "reviewer": "Reviewer_Vnro", "summary": "The paper develops 2nd-order methods for variational inequalities under inexact Jacobian information. Existing methods requires exact derivative information which can be prohibitively expensive for large-problems limiting their practicality. To address this issue, the paper analyzes the impact of inexact derivatives on the convergence rate. When the objective is smooth and monotone, the paper establishes a lower-bound that depends upon the level inaccuracy and develop an optimal algorithm that attains this bound. The paper develops several inexact schemes based on a Quasi-Newton approximation that achieve a gloabl sublinear convergence rates.", "questions": "1) If the algorithms in this paper only have access to stochastic Jacobian information  and assuming they don't minibatch, do the authors believe the conclusions of the paper still hold modulo the fact that convergence will only occur up to the noise level in the Jacobian? If the answer is yes, then I don't think the weakness above is that significant. \n\n2)  For the experiments results in Figure 1, how well do the proposed methods perform in terms of wall-clock time? Although they require more iterations then Perseus, I would expect them to be faster due to their use of inexactness. I think inclusion of this information in a table would make a nice addition to the paper.", "limitations": "I think the authors have addressed the main limitations of the work at the end of the paper.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1.) The paper is the first to systematically explore the effect the impact of inexact Jacobian information on the global convergence rate of 2nd-order methods for variational inequalities. In particular, the established bounds demonstrate the precise impact of the level inexactness on the speed of convergence. \n\n2.) In the important special case when F is smooth and monotone, the paper provides a lower-bound on the convergence rate that explicitly depends upon the level of inexactness. They then provide an algorithm that achieves this lower-bound. Thus, the analysis in the paper is quite tight.\n\n3.) On a practical level the authors develop inexact 2nd-order schemes that achieve global sublinear convergence based on quasi-Newton schemes. \n\n4.) The theory is supported by numerical simulation and comparision with existing methods.\n\n5.) The paper is clear and easy to read.\n\nOverall, I think the paper provides a strong contribution to optimization theory and should be accepted.", "weaknesses": "The main weakness that I can see is that the paper focuses on deterministic inaccuracy in the Jacobian. Most practical ML algorithms use stochastic derivative information. Moreover, the batch size doesn't typically increase as the algorithm progresses, so generally only a noisy neighborhood of the optimum is reached. Thus, it is not immediately clear how relevant the algorithms and analysis in the paper are to this setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Vrno,\n\nThank you for your detailed and thoughtful review of our paper. We are pleased to hear that you found our theoretical analysis and practical developments compelling. Your positive feedback on the clarity and readability of the writing is greatly appreciated. We also value your insights regarding stochastic Jacobians. Below, we address your questions in detail.\n\n**Weakness 1**\n\n>  The main weakness that I can see is that the paper focuses on deterministic inaccuracy in the Jacobian. Most practical ML algorithms use stochastic derivative information. Moreover, the batch size doesn't typically increase as the algorithm progresses, so generally only a noisy neighborhood of the optimum is reached. Thus, it is not immediately clear how relevant the algorithms and analysis in the paper are to this setting.\n\n**Question 1**\n\n>  If the algorithms in this paper only have access to stochastic Jacobian information and assuming they don't minibatch, do the authors believe the conclusions of the paper still hold modulo the fact that convergence will only occur up to the noise level in the Jacobian? If the answer is yes, then I don't think the weakness above is that significant. \n\n**Response to Weakness 1 and Question 1**\n\nThank you for your insightful commentary. The application of our method to stochastic optimization remains an open question. To the best of our knowledge, there is not even a stochastic version of dual extrapolation, on which our method is based.\nThe problem of applying the current scheme to stochastic problems arises in Lemma B1, where we do not know how to apply expectation to the difference between the Jacobian and its approximation. We calculate the Jacobian at the point $v_k$, while in lines 588-589, where we want to apply expectation, we have terms $v_{k+1}$ and $x_k$, which depend on stochastisity from stochastic Jacobian in $v_k$. Thus, we leave true stochasticity for future work.\nWhat one can do is to show the convergence of the method with high probability if Assumption 2.1 is satisfied with high probability. For example, the mini-batch scenario can be included here by using concentration inequalities. This analysis might not require increasing the batch size during iterations, but it usually leads to very large batch sizes.\n  \n**Question 2** \n\n> For the experiments results in Figure 1, how well do the proposed methods perform in terms of wall-clock time? Although they require more iterations then Perseus, I would expect them to be faster due to their use of inexactness. I think inclusion of this information in a table would make a nice addition to the paper.\n\n**Response**\n\nThank you for your suggestion. You are correct that the exact second-order Perseus2 step takes more time than an iteration of VIQA. However, we did not include a time comparison because we specifically chose this example to allow for fast computation of the operator and the Jacobian due to the problem's structure, aiming to challenge the convergence of first-order methods in terms of iteration complexity. To demonstrate the benefits in wall-clock time, we will need to use more complex problems. Our ongoing experiments are addressing this, and we plan to include relevant plots in the final version of the paper.", "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:

Meta-review: The authors present second-order methods for variational inequalities that can handle inexact Jacobian information, along with lower bounds that depend on the amount of inexactness. The reviewers all agree that the work is interesting and impactful, and thereby worthy of acceptance.
Decision: Accept (spotlight)