{'fraction_non_alphanumeric': 0.05886011719645137, 'fraction_numerical': 0.015484335613971912, 'mean_word_length': 3.7523335407591785, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Solving smooth min-min and min-max problems by mixed oracle algorithms

In this paper, we consider two types of problems that have some similarity in their structure, namely, min-min problems and min-max saddle-point problems. Our approach is based on considering the outer minimization problem as a minimization problem with inexact oracle. This inexact oracle is calculated via inexact solution of the inner problem, which is either minimization or a maximization problem. Our main assumptions are that the problem is smooth and the available oracle is mixed: it is only possible to evaluate the gradient w.r.t. the outer block of variables which corresponds to the outer minimization problem, whereas for the inner problem only zeroth-order oracle is available. To solve the inner problem we use accelerated gradient-free method with zeroth-order oracle. To solve the outer problem we use either inexact variant of Vaydya's cutting-plane method or a variant of accelerated gradient method. As a result, we propose a framework that leads to non-asymptotic complexity bounds for both min-min and min-max problems. Moreover, we estimate separately the number of first- and zeroth-order oracle calls which are sufficient to reach any desired accuracy.


Introduction
In this paper, we consider smooth optimization problems in which the decision variable is decomposed into two blocks with minimization w.r.t. one block, which we call the outer block, and two types of operations w.r.t. the second block, which we call the inner block: minimization or maximization. In other words, we consider smooth min-min problems and min-max problems. The main difference of our setting with existing in the literature is that we assume that it is possible to evaluate the gradient w.r.t. the outer block of the variables, i.e. first-order oracle, and only function values, i.e. zeroth-order oracle, when we deal with the inner block of variables. Thus, we operate with mixed type of oracle: first-order in one block of variables and zeroth-order in the second block of variables.
Our motivation, firstly, comes from min-max saddle-point problems, which have recently became of an increased interest in machine learning community in application to training Generative Adversarial Networks [11], and other adversarial models [17], as well as to robust reinforcement learning [23]. The standard process is to simultaneously train neural network, find adversarial examples and learn the network to distinguish the true examples from the artificially generated. In the training process the gradient is available through the backpropagation, whereas for the generating adversarial examples the network is available as a black box and only zeroth-order oracle is available. Another close application area is Adversarial Attacks [12,29] on neural networks, in particular the Black-Box Adversarial Attacks [18]. Here the goal is for a trained network to find a perturbation of the data in such a way that the network outputs wrong prediction. Then the training is repeated to make the network robust to such attacks. Since the attacking model does not have access to the architecture of the main network, but only to the input and output of the network, the only available oracle for the attacker is the zeroth-order oracle for the loss function. The motivation for min-min problems comes from simulation optimization [8,27], where some parts of the optimized system can be given as a black box with unavailable or computationally expensive gradients, and other parts of the objective are differentiable.
Separately zeroth-order [5] and first-order [21] are very well developed areas of modern numerical optimization. There are also plenty of works on first-order [14,20,19,3] and zeroth-order methods [32,16,2,26] for saddle-point problems. Our main idea and contribution in this paper is to consider mixed oracles, which seems to be an underdeveloped area of optimization and saddle-point problems.
In [26] the authors consider methods with mixed oracle, but, unlike this work, only in the context of saddle-point problems and without acceleration techniques.
Notably, in this paper we develop a generic approach which is suitable for both types of problems: min-min and min-max, and is based on the same idea for both problems: we consider the minimization problem w.r.t. the outer group of variables as a minimization problem with inexact oracle. This inexact oracle is evaluated via inexact solution of the inner problem, which is either a minimization or a maximization problem. We carefully estimate with what accuracy one needs to solve the inner problem to be able to solve the outer problem with the desired accuracy. Moreover, we have to account for the random nature of the solution to the inner problem since we use randomized gradient-free methods with zeroth-order oracle to solve the inner problem. In our approach we consider two settings for the outer problem. If the dimension of the outer problem is small, we use Vaydya's cutting-plane method [31,30], for which we extend the analysis to the case of approximate subgradients. The drawback of this method is that it scales quite badly with the dimension. Thus, if the dimension of the outer problem is large, we exploit accelerated gradient method, for which we develop an analysis in the case when an inexact oracle is available only with some probability, which may be of independent interest. Our approach based on inner-outer loops allows also to separate complexities, i.e. the number of calls to each of the oracles: first-order oracle for the outer block of variables and zeroth-order oracle for the inner block of variables.
The rest of the paper is organized as follows. First we consider min-min problems in two settings: small and large dimension of the outer problem. In the first case we develop an inexact variant of the Vaydya's method use it in the outer loop in a combination with accelerated random gradient-free method in the inner loop. In the second case, we apply accelerated gradient method in the outer loop combined with the same method in the inner loop. After that we consider saddle-point min-max problems again in two settings. When the dimension of the outer problem is small, we use the same scheme with inexact Vaydya's method and accelerated random gradient-free method. The situation is more complicated when the dimension of the outer problem is large. In this case we use a three-loop structure with the Catalyst acceleration scheme [15] combined with accelerated gradient method with inexact oracle and accelerated random gradient-free method.
where X ⊆ R nx is a closed convex set, f (x, y) is a convex function equipped with a mixed oracle, i.e. we have access to a first-order oracle for the outer problem (minimization w.r.t. x) and a zeroth-order oracle for the inner problem (minimization w.r.t. y). In the sections below we will describe the two approaches to solving such problems together with additional assumptions they require. The general idea of the approaches is as follows. Let us introduce the function and rewrite the initial problem (1) as Using an iterative method for the outer problem (3) requires solving the inner problem (2) numerically on each iteration. An error of the solution of the inner problem results in an inexact oracle for the outer problem.

Small dimension of the outer problem
The approach described in the present subsection requires the following assumptions about the problem (1): 1. X ⊂ R nx is a compact convex set with nonempty interior; 2. n x is relatively small (up to a hundred); 3. f (x, y) is a continuous convex function which is also µ y -strongly convex in y; 4. for all x ∈ X the function f (x, ·) is L yy -smooth, i.e.
5. for any x ∈ X the minimization problem (2) has solution y(x).
The algorithms used in the proposed approach and related convergence theorems are given in the subsequent paragraphs. Our proposed approach goes as follows: The complexity of approach 1 is given in the following theorem: calls to the first-order oracle and O n x n y Lyy µy calls to the zeroth-order oracle. 6 Here and below instead of ARDDsc we can use Accelerated coordinate descent methods [22,10] with replacing partial derivatives by finite-differences. In this case we lost opportunity to play on the choice of the norm (that could save √ ny-factor in gradient-free oracle complexity estimate [7]), but, we gain a possibility to replace the wort case Lyy to the average one (that could be ny-times smaller [22]). At the end this could also save √ ny-factor in gradient-free oracle complexity estimate [22].

Remark 1.
As far as the arithmetic complexity of the iteration is concerned, Vaidya's cutting plane method involves inversions of n x × n x matrices, hence the assumption that n x is relatively small.
The complexity bounds from theorem 1 are derived in the paragraph Analysis of the approach which follows the description of algorithms.
Vaidya's cutting plane method Vaidya proposed a cutting plane method [30,31] for solving problems of the form where X ⊆ R n is a compact convex set with non-empty interior, and g : X → R is a continuous convex function.
We will now introduce the notation and describe the algorithm. Let P = {x ∈ R n : Ax ≥ b} be the bounded full-dimensional polytope, where A ∈ R m×n and b ∈ R m . The logarithmic barrier for P is defined as The Hessian of L(x) is given by and is positive definite for all x in the interior of P . The volumetric barrier for P is defined as where det H(x) denotes the determinant of H(x). The point ω that minimizes F (x) over P will be called the volumetric center of P . Let σ i (x) be defined as Now, let R be a radius of some Euclidean ball B R that contains X . W.l.o.g we will assume that B R is centered at the origin. The parameters of the method η > 0 and γ > 0 are small constants such that η 10 −4 , and γ 10 −3 η. The algorithm starts out with the simplex and produces a sequence of pairs (A k , b k ) ∈ R m k ×n × R m k , such that the corresponding polytope P k = {x ∈ R n : A k x ≥ b k } always contains a solution of the problem (4). At the beginning of each iteration k we have an approximation z k to the volumetric center of P k (for more details on computing the approximation see [31,30]). In particular, on the 0-th iteration we can compute the volumetric center explicitly: Proposition 1. The volumetric center for P 0 is ω = ω1 n , where ω := n−1 n+1 R and 1 n denotes the vector (1, . . . , 1) ⊤ ∈ R n .
For k ≥ 0, the next polytope (A k+1 , b k+1 ) is defined by either adding or removing a constraint to the current polytope, depending on the values {σ i (z k )} m i=1 associated to P k : is defined by removing the i th row from (A k , b k ). 2. Otherwise, i.e. if min 1≤j≤m σ j (z k ) ≥ γ, the oracle is called with the current point z k as input. If z k ∈ X , it returns a vector c k , such that −c k ∈ ∂g(z k ), i.e. −c k is a subgradient of g at z k . Otherwise, it returns a vector c k such that Then we define (A k+1 , b k+1 ) by adding the row given by c ⊤ k , β k to (A k , b k ).
After N iterations, the method returns a point x N := arg min 1≤k≤N g(z k ).
Now, let us introduce the concept of inexact subgradient.
Definition 1. The vector c ∈ R n is called a δ-subgradient of a convex function g at z ∈ dom f (we denote c ∈ ∂ δ g(z)), if In fact, a δ-subgradient can be used in Vaidya's method instead of the exact subgradient. In this case, we will call the algorithm Vaidya's method with δsubgradient. We will now present a theorem that justifies this claim.
Theorem 2. Let B ρ and B R be some Euclidean balls of radii ρ and R, respectively, such that B ρ ⊆ X ⊆ B R , and let a number B > 0 be such that γ ln n 1.5 R γρ + 1 γ ln π iterations Vaidya's method with δ-subgradient for the problem (4) returns a point x N such that where γ > 0 is the parameter of the algorithm and x * is a solution of the problem (4).
Accelerated Randomized Directional Derivative method We refer to the work [7]. For convenience, we present algorithms from this paper, taking into account that the problem will be a classical optimization problem: Gradient approximation: where e ∈ RS nx 2 (1), i.e. be a random vector uniformly distributed on the surface of the unit Euclidean sphere in R nx .
It is worth noting that in the case of p = 2, the prox-function d(x) looks like this For any two points x, x ′ ∈ R nx we define Bregman divergence V x (x ′ ) associated with d(x) as follows: It is worth noting that in the case of p = 2, the Bregman divergence V x (x ′ ) looks like this Let x * be fixed point and x be random vector such that where E x denotes the expectation with respect to random vector x and Ω p is defined as follows. We note that for p = 2 Ω p = 1
Moreover, the oracle complexity to achieve ε-accuracy of the solution is Analysis of the approach 1 Fix a point x ′ ∈ X . The following theorem gives the recipe to obtaining the δ-subgradient c ∈ ∂ δ g(x ′ ) for the outer problem (3): where D := max The theorem 4 is based on the two following lemmas: Then ∇h(ỹ),ỹ − y ≤ ỹ − y 2 2Lδ ∀y ∈ R ny .
Lemma 2 (see [9], p.12). Letỹ ∈ R ny satisfy then According to theorem 4, we need to solve the inner problem (2) with sufficient accuracy to obtain the δ-subgradient. In fact, we can simplify the formula (12) to Indeed, sinceỹ is anδ-solution of the inner problem (2), we can assume that ). If this inequality doesn't hold, we can always take 0 as an approximate solution of (2). Now, to derive the complexity of approach 1, we will use the theorem 2 and put i.e. Vaidya's method will perform steps (first-order oracle calls), and at each of them ARDDsc will perform . Thus, the number of zeroth-order oracle calls is which finishes the analysis of approach 1.

Solving Min-Max Saddle-Point Problems
Consider the problem min convex in x and concave in y) equipped with a mixed oracle, i.e. we have access to a first-order oracle for the outer problem (minimization w.r.t. x) and a zerothorder oracle for the inner problem (maximization w.r.t. y). In the subsections below we describe the two approaches for solving such problems together with additional assumptions they require. The general idea of the approaches is as follows. Let us introduce the function and rewrite the initial problem (15) as Using an iterative method for the outer problem (17) requires solving the inner problem (16) numerically in each iteration. An error of the solution of the inner problem results in an inexact oracle for the outer problem.

Small dimension of the outer problem
The approach described in the present section requires the following assumptions about the problem (15): 1. X ⊂ R nx is a compact convex set with nonempty interior; 2. n x is relatively small (up to a hundred); 3. f (x, y) is a continuous function which is convex in x and µ y -strongly concave in y; 5. for any x ∈ X the maximization problem (16) has solution y(x).
The algorithms used in the approach and related convergence theorems are given in the previous section. The approach goes as follows: Approach 2. The outer problem (17) is solved via Vaidya's cutting plane method. The inner problem (2) is solved via ARDDsc, see Algorithm 2.
Complexity of the approach is given in the following theorem: calls to the first-order oracle and O n x n y Lyy µy calls to the zeroth-order oracle.
Remark 2. As far as the arithmetic complexity of the iteration is concerned, Vaidya's cutting plane method involves inversions of n x × n x matrices, hence the assumption that n x is relatively small.
Complexity bounds from theorem 5 are derived in the following paragraph.
Analysis of the approach 2 Fix a point x ′ ∈ X . The following lemma gives the recipe to obtaining the δ-subgradient c ∈ ∂ δ g(x ′ ) for the outer problem (17): According to lemma 3, we need to solve the inner problem (16) with accuracy δ to obtain the δ-subgradient. Now, to derive the complexity of approach 2, we will use the theorem 2 and put i.e. Vaidya's method will perform steps (first-order oracle calls), and at each of them ARDDsc will perform N y = O n y L yy µ y iterations (see theorem 3). Thus, the number of zeroth-order oracle calls is which finishes the analysis of approach 2.

Large dimension of the outer problem
For a detailed study of the convergence of the methods, we introduce some assumptions about the objective function f (x, y).
It means that f (·, y) is convex for all y and f (x, ·) is concave for all x.
Assumption 1(s). f (x, y) is strongly-convex-strongly-concave. It means that f (·, y) is µ x -strongly convex for all y and f (x, ·) is µ y -strongly concave for all x w.r.t. · 2 , i.e. for all x 1 , x 2 ∈ X and for all y 1 , y 2 ∈ R ny we have As mentioned above, we have access to a first-order oracle ∇ x f (x, y) for the outer problem (minimization problem with variables x) and a zeroth-order oracle f (x, y) for the inner problem (maximization problem with variables y). Since we do not have access to the values of the gradient ∇ y f (x, y), it is logical to approximate it using finite differences using the value of the function f (x, y) at two close points as follows where e ∈ RS ny 2 (1), i.e. is a random vector uniformly distributed on the surface of the unit Euclidean sphere in R ny . So we get a mixed oracle Using the mixed oracle (21), we provide our approach for solving the initial saddle-point problem (15). First, we can use the following trick with the help of Sion's theorem: For the new problem, we apply the Catalyst algorithm [15] to the outer maximization problem:

5:
Compute α k ∈ (0, 1) from equation Now the question arises how to solve the auxiliary problem (23). This subproblem is equivalent to solving the following problem: for which we again use the Sion's theorem and rewrite equivalently the problem as: For convenience, we denote Thus, to solve the auxiliary problem (23), we first solve the following saddle-point problem This saddle-point problem (25) can be considered as an optimization problem for a certain function. Indeed, let us introduce a function and rewrite the initial problem (25) as follows: To solve problem (25), we solve the outer minimization problem with respect to the variable x by the fast adaptive gradient method with inexact oracle. In each iteration of this method, to find the inexact first-order oracle for the outer problem, we solve the inner problem (26). Since for this inner problem we have access only to the zeroth-order oracle, we use accelerated gradient-free method ARDDsc [7]. Our approach is summarized as follows. Analysis of fast adaptive gradient method with (δ, σ, L, µ)-oracle (Algorithm 4) For our analysis, due to the fact that Algorithm 2 is randomized, we need not just a fast gradient method for solving the outer problem (27), but a fast adaptive gradient method for (δ, σ, L, µ)-oracle. This is the extension of the fast adaptive gradient method from [28]. To understand this problem in depth and in detail, we need to carefully consider the concept of (δ, σ, L, µ)-oracle and perform a deep and thorough convergence analysis of the fast gradient method using such a seemingly unusual oracle. To that end, we consider the following general minimization problem: Definition 4 ((δ, σ, L, µ)-oracle). Let function f be convex on convex set X . We say that it is equipped with a first-order (δ, σ, L, µ)-oracle if, for any x ′ ∈ X , we can compute a pair (f δ,L,µ (x ′ ), g δ,L,µ (x ′ )) ∈ R×R nx such that with probability at least 1 − σ Definition 5 ((ε, σ)-solution). Let ε > 0 be the target accuracy of the solution and σ ∈ (0, 1) be the target confidence level. We say that a random pointx ∈ X is (ε, σ)-solution to problem (28) if If σ = 0, we say thatx ∈ X is an ε-solution to problem (28).
Note that the problem argmin x∈X φ k+1 (x) is solved exactly in each iteration.
Theorem 6. Let function f be convex on convex set X and be equipped with a first-order (δ, σ, L, µ)-oracle. Then, after N iterations of Algorithm 4 applied to problem (28), we have that with probability at least (1 − N σ): where R 2 is such that 1 2 x 0 − x * 2 2 ≤ R 2 2 and x 0 is the starting point.
Corollary 1. Let function f be convex on convex set X and be equipped with a first-order (δ, σ N , L, µ)-oracle. If the sequence {δ} k≥0 is bounded by δ, we have with probability at least (1 − σ): where R 2 is such that 1 2 x 0 − x * 2 2 ≤ R 2 2 and x 0 is the starting point. Proof. To prove this statement, we give an auxiliary lemma We get the result of the Corollary immediately using (31) and Lemma 1.

Analysis of Approach 3 For further analysis, we present the main lemma of this subsection
Lemma 4 (see [1]). We denote Under assumption 1(s), 2 we have -Let y δ (x) be a (δ, σ)-solution to problem max y∈R ny f (x, y). Then, for any x ′ , x ∈ X , with probability at least 1 − σ we have:

Now we are ready to present the main result of this section
Theorem 7. Let ε > 0 be the target accuracy of the solution to the problem (15) and σ ∈ (0, 1) be the target confidence level. Let the auxiliary problems (16), (17) be solved with accuracies that is, a (ε x , σ x )−solution to the problem (17) and a (ε y , σ y )−solution to the problem (16) are found (see Definition 5). Then, under assumptions 1(s), 2, the proposed Approach 3 guarantees to find an (ε, σ)-solution to the problem (15). Moreover, the required number of calls to the first-order oracle ∇ x f (x, y) and the zeroth-order oracle f (x, y) satisfy the following bounds  A Proofs for Section 2 (Solving Min-Min Problems) Proposition 1. The volumetric center for P 0 is ω = ω1 n , where ω := n−1 n+1 R and 1 n denotes the vector (1, . . . , 1) ⊤ ∈ R n .
Proof. P 0 can be viewed as It is known that the analytic center of simplex (i.e. minimizer of L(x)) is also its volumetric center [25]. Note that L(x) is a convex function.
Theorem 2. Let B ρ and B R be some Euclidean balls of radii ρ and R, respectively, such that B ρ ⊆ X ⊆ B R , and let a number B > 0 be such that After N ≥ 2n γ ln n 1.5 R γρ + 1 γ ln π iterations Vaidya's method with δ-subgradient for the problem (4) returns a point x N such that where γ > 0 is the parameter of the algorithm and x * is a solution of the problem (4).
Proof. The proof goes as follows. First, we consider the set X ε := {(1 − ε)x * + εx, x ∈ X } for some ε ∈ [0, 1]. Then, we calculate the number of iterations N sufficient for the volume of the polytope P N to go below the volume of X ε . Finally, we show that after N iterations the algorithm arrives at a (Bε + δ)suboptimal point. Fix ε ∈ [0, 1] and consider the set The lower bound on the volume of n-ball [4] is We will now derive an upper bound on the volume of polytope P N at the beginning of the N -th iteration. According to the Vaidya's paper [30], the following inequality holds: where γ is the parameter of the algorithm and ρ 0 denotes the minimum of the volumetric barrier at the beginning of the 0-th iteration. To calculate it, we will use proposition 1, which states that ω = ω1 n , where ω := n−1 n+1 R. Observe that Let us calculate H(ω) and F (ω): Using the formulas (37) and (39), we obtain ln (vol P N ) ≤ n ln 4n 2 R γ(n + 1) Putting together (35), (36) and (40), we will determine a sufficient number of iterations to assure vol P N < vol X ε : γN > 2n ln 4n 2.5 R γ(n + 1) √ 2πeερ + ln π n + e 2 − 1 n + 1 .
It is sufficient to do iterations. Since vol P N < vol X ε , there will be an iteration j ∈ {0, ..., N −1} and a point x ε ∈ X ε such that x ε ∈ P j and x ε / ∈ P j+1 . Thus, on the j-th iteration we added a new constraint to the polytope. There exists a point x ∈ X such that x ε = (1 − ε)x * + εx, therefore it follows from the convexity of g that We will now show that the following inequality holds for the query point z j at the j-th iteration: First, note that z j belongs to X , otherwise we would cut out a part of P j that doesn't intersect with X , which is a contradiction since x ε ∈ P j \ P j+1 and x ε ∈ X . Recall that the constraint c ⊤ j x ≥ β j was added to the polytope on the j-th iteration, where −c j ∈ ∂ δ g(z j ) and β j ≤ c ⊤ j z j . According to the definition of δ-subgradient, Therefore, which results in (45) since x ε ∈ (P j \ P j+1 ) ∩ X . Combining (43), (44) and (45), we conclude the proof.
where D := max Proof. Using Lemmas 1, 2 and triangle inequality, we get ∂ x f (x ′ ,ỹ) ∈ ∂ δ g(x ′ ) with Let us bound the two terms in parentheses. For any x ∈ X , it follows from the strong convexity of f (x, ·) that In particular, putting y ′ = 0 leads to is a continuous function defined on the compact set X . Therefore, it is bounded, i.e. ∆(x) ≤ D for some D < +∞. Thus, Finally, let us bound ỹ 2 by again using triangle inequality, then inequalities (47), (48) and f (x ′ ,ỹ) − g (x ′ ) ≤δ: The statement of the theorem immediately follows from (46), (48) and (49).

Lemma 1.
Let h : R ny → R be an L-smooth convex function, and let the point y ∈ R ny satisfy h(ỹ) − h(y * ) ≤δ for somedelta > 0, where y * ∈ Argmin y∈R ny h(y).

B Proofs for Section 3 (Solving Min-Max Saddle-Point Problems)
Theorem 6. Let function f be convex on convex set X and be equipped with a first-order (δ, σ, L, µ)-oracle. Then, after N iterations of Algorithm 4 applied to problem (28), we have that with probability at least (1 − N σ): where R 2 is such that 1 2 x 0 − x * 2 2 ≤ R 2 2 and x 0 is the starting point.
Proof. We almost completely repeat the proof of result from [28].
Lemma 2 (see [28]). Let φ(x) be convex function on the convex set X and y = argmin where β ≥ 0, γ ≥ 0. Then Lemma 3 (see [28]). For all x ∈ X we have with probability with 1 − σ Proof Using definition of (δ, σ, L, µ)-oracle (29), we have with probability . Then with probability at least 1 − σ: Using definitions of sequences x k+1 and y k+1 , we have with probability at least 1 − σ: Due to u k+1 is the solution to argmin x∈X φ k+1 (x), using (52) we have for any x ∈ X with probability at least 1 − σ: Then for all x ∈ X we have with probability at least 1 − σ: Then for all x ∈ X we have with probability at least 1 − σ: Now we prove the statement of this theorem. First, we note that if we sum the inequality (53) by k from 0 to N − 1, for any x ∈ X we get Then using the resulting inequality above for any x ∈ X we get In this way, for any x ∈ X with probability at least (1 − N σ) we have We finish proof with next inequality (see [28]): Lemma 4 (see [1]). We denote Under assumption 1(s), 2 we have -Let y δ (x) be a (δ, σ)-solution to problem max y∈R ny f (x, y). Then, for any x ′ , x ∈ X , with probability at least 1 − σ we have: Letx be (ε x , σ x )-solution of problem min x∈X g(x), let y εy (x) be (ε y , σ y )-solution Proof. To justify the statement of the lemma, we give a more general statement.

Lemma 4 (see lemma 4 ).
We denote Under assumption 1(s) for · px and · py norms, assumption 2 for · px and · py norms we have is -Let y δ (x) -(δ, σ) be solution to problem max y∈R ny f (x, y). Then for any x ′ , x ∈ X with probability at least 1 − σ we have: In thus way, we have We have 3. Consider the following value ∇g(x) − ∇g(x ′ ) qx : Then we have: Let y δ (x) -(δ, σ) be solution to problem max y∈R ny f (x, y), and y * (x) be exact solution. We prove the left side of inequality. For any x, x ′ ∈ X we have Now we prove the left side of inequality. For any x, x ′ ∈ X we have with probability at least 1 − σ Estimate ∇ x f (x, y δ (x)) − ∇g(x) qx . we have with probability at least 1 − σ Then for any x, x ′ ∈ X we have with probability at least 1 − σ I this way, we have function g(x) equips (2δ, σ, 2L g , µ x )-oracle.
5. According to µ x -strong convexity of function g(x), we have with probability According to µ x -strong concavity of function h(x), using union bound we have with probability at least 1 − σ y − σ x We have with probability at least Theorem 7. Let ε > 0 be the target accuracy of the solution to the problem (15) and σ ∈ (0, 1) be the target confidence level. Let the auxiliary problems (16), (17) be solved with accuracies and confidence levels σ x = O σ µ y L yy ; that is, a (ε x , σ x )−solution to the problem (17) and a (ε y , σ y )−solution to the problem (16) are found (see Definition 5). Then, under assumptions 1(s), 2, the proposed Approach 3 guarantees to find an (ε, σ)-solution to the problem (15). Moreover, the required number of calls to the first-order oracle ∇ x f (x, y) and the zeroth-order oracle f (x, y) satisfy the following bounds 2. Now we need to determine the number of iterations of the M method to solve the problem (23). According to theorem 3, the number of iterations of algorithm 2 required to find the solution with accuracy ε y is 3. Now we solve the outer problem (27) with the algorithm 4. We need to determine the Lipschitz constant and the strong convexity constant. The strong convexity constant remains the same, the Lipschitz constant, according to Lemma 4, is Complexity of solution of the outer problem (27) (number of calculations of the gradient value ∇ x f (x, y)) with accuracy ε x : 4. Thus, the total complexity of calls of zeroth-order oracle f (x, y), solving the inner problem (15) by the algorithm 2 with accuracy ε, taking H 1 = L yy , is equal to xy µ x (µ y + H 1 ) = O n y L yy + L yy µ y + L yy L yy µ y L xx µ x + 2L 2 xy µ x (µ y + L yy ) = O n y L yy + L yy L yy L xx L yy µ x µ y + 2L 2 xy L yy µ x µ y L yy = O n y L xx L yy µ x µ y + 2L 2 xy µ x µ y

Inexactness Complexities Analysis
Now it remains to determine with what accuracy ε x , ε y it is necessary to solve inner (26) and outer (27) problems, so that the number of calls to the oracles satisfies this ratio (??). In order to answer this question, we will introduce new designations and redefine some things. First, we denote ξ(x) = max y∈R ny ψ(x, y), ζ(y) = min x∈X ψ(x, y) Letx ∈ X be (ε x , σ x )-solution to problem min x∈X ξ(x), in other words, we have with probability at least 1 − σ x : Let y εy (x) -(ε y , σ y )-solution to problem max y∈R ny ψ(x, y), in other words, we have with probability at least 1 − σ y : 0 ≤ ψ(x, y * (x)) − ψ(x, y εy (x)) ≤ ε y First, according to corollary 1 for min x∈X ξ(x), we have a limit on noise ε y : Thus, we have It remains only to understand how to define ε x via ε.To answer this question using the main lemma 4, replacing µ y with µ y + H 1 and L yy with L yy + H 1 , we obtain inequality:  Having obtained this ratio, we now need to determine how they relate to each other. Using the catalyst algorithm and the convergence proof, one can easily show that Thus we have