Use of language models. The models Codex Astra 6 and Claude Opus 5.5 were used in obtaining the theoretical results of this work. They were also used to prepare and typeset the manuscript and to translate the original text into English. Nevertheless, every line of the paper, including every statement, every proof, and every computation, has been personally edited and checked by the authors. The authors bear sole responsibility for the correctness of all mathematical statements, proofs, and conclusions.
Introduction
We consider the problem of finding a point z ∈ R d z\in\mathbb{R}^d z ∈ R d such that F ( z ) = 0 F(z)=0 F ( z ) = 0 , where F : R d → R d F:\mathbb{R}^d\to\mathbb{R}^d F : R d → R d is a continuous monotone operator, that is, ⟨ F ( u ) − F ( v ) , u − v ⟩ ≥ 0 \langle F(u)-F(v),u-v\rangle\ge0 ⟨ F ( u ) − F ( v ) , u − v ⟩ ≥ 0 for all u , v ∈ R d u,v\in\mathbb{R}^d u , v ∈ R d . A point z ∗ ∈ Z z^*\in Z z ∗ ∈ Z is called a solution of the variational inequality on a convex set Z Z Z if $\langle F(z^),z-z^ \rangle\ge 0 for all z ∈ Z z \in Z z ∈ Z . For Z = R d Z = \mathbb{R}^d Z = R d , the substitution z = z ∗ − t F ( z ∗ ) z = z^* - tF(z^*) z = z ∗ − tF ( z ∗ ) , t > 0 t > 0 t > 0 , shows that this condition is equivalent to the equality F ( z ∗ ) = 0 F(z^*) = 0 F ( z ∗ ) = 0 . Therefore, finding a zero of the operator is a variational inequality on the whole space. The general theory of finite-dimensional variational inequalities is presented in the monograph Facchinei and Pang [8 ] . On the whole space, a solution may fail to exist. The constant operator F ≡ c ≠ 0 F \equiv c \ne0 F ≡ c = 0 is monotone and satisfies any smoothness conditions, but it has no zeros. On a compact set Z Z Z , a solution with the same operator exists: it is a minimizer of the linear function ⟨ c , z ⟩ \langle c,z\rangle ⟨ c , z ⟩ on Z Z Z , that is, a solution of a linear programming problem. Therefore, all bounds in this paper concern solvable problems: we assume that a solution exists.
The main source of monotone operators is saddle-point problems. If a function φ ( x , y ) \varphi(x,y) φ ( x , y ) is convex in x x x and concave in y y y , then the operator F ( x , y ) = ( ∇ x φ ( x , y ) , − ∇ y φ ( x , y ) ) F(x,y) = (\nabla_x\varphi(x,y),-\nabla_y\varphi(x,y)) F ( x , y ) = ( ∇ x φ ( x , y ) , − ∇ y φ ( x , y )) is monotone, and its zeros are the saddle points of φ \varphi φ . Nash equilibrium conditions in games where the loss function of each player is convex in the player’s own strategy are written in the same way: an equilibrium is a zero of the operator composed of the gradients of the players’ loss functions with respect to their strategies. If this operator is monotone, the game is called monotone. A condition of this type (diagonal strict concavity) was introduced by Rosen [22 ] . Some problems of training generative adversarial networks also reduce to monotone games ([10 ] ). Another classical source is traffic equilibria: the Wardrop equilibrium in the Beckmann model is written as a variational inequality with the path cost operator, which is monotone when the link cost functions are nondecreasing (Dafermos [5 ] ). Methods for finding equilibria in the Beckmann model and in the Nesterov–de Palma stable dynamics model are considered in Kubentayeva and Gasnikov [15 ] . The gradient of a convex function is a special case of a monotone operator, but in general F F F is not a gradient. For φ ( x , y ) = x y \varphi(x,y) = xy φ ( x , y ) = x y , we obtain the rotation F ( x , y ) = ( y , − x ) F(x,y) = (y,-x) F ( x , y ) = ( y , − x ) , and the step z − h F ( z ) z - hF(z) z − h F ( z ) moves the point away from the solution for every h > 0 h > 0 h > 0 : ∥ z − h F ( z ) ∥ 2 = ( 1 + h 2 ) ∥ z ∥ 2 \lVert z - hF(z)\rVert^2 = (1+h^2)\lVert z\rVert^2 ∥ z − h F ( z ) ∥ 2 = ( 1 + h 2 ) ∥ z ∥ 2 . Therefore, the main method for such problems is the extragradient method (Korpelevich [14 ] ), in which the operator is evaluated at an extrapolation point, and its variant with one operator evaluation per iteration (Popov [21 ] ).
For a monotone operator with Lipschitz constant L L L , the complexity is well studied. On a compact set Z Z Z , the accuracy of an approximate solution z ∈ Z z \in Z z ∈ Z is usually measured by the quantity sup u ∈ Z ⟨ F ( u ) , z − u ⟩ \sup_{u \in Z}\langle F(u),z-u\rangle sup u ∈ Z ⟨ F ( u ) , z − u ⟩ , which is also called the Minty gap, or the restricted gap function (Stonyakin et al. [25 ] ). For a continuous monotone operator, it is nonnegative and vanishes exactly at the solutions of the variational inequality (Minty [16 ] ). In the Russian-language literature, the inequality sup u ∈ Z ⟨ F ( u ) , z − u ⟩ ≤ η \sup_{u \in Z}\langle F(u),z-u\rangle\le\eta sup u ∈ Z ⟨ F ( u ) , z − u ⟩ ≤ η is used as an accuracy criterion for weak (Minty) variational inequalities (Gasnikov et al. [9 ] ). If the diameter of Z Z Z equals D D D , the method Mirror-Prox finds a point with Minty gap at most η \eta η in O ( L D 2 / η ) O(LD^2/\eta) O ( L D 2 / η ) iterations (Nemirovski [17 ] ), and for linear operators this order cannot be improved (Nemirovsky [18 ] ). For the unconstrained problem, that is, the variational inequality on the whole space, the natural accuracy criterion is the norm of the operator. The Halpern iteration (Halpern [13 ] ) constructs a new point as a convex combination of the starting point and a step of the method: z k + 1 = β k z 0 + ( 1 − β k ) T ( z k ) z_{k+1} = \beta_k z_0 + (1-\beta_k)T(z_k) z k + 1 = β k z 0 + ( 1 − β k ) T ( z k ) , where T T T is a nonexpansive map, for example, the resolvent of the operator F F F , and the weights β k \beta_k β k decrease to zero. The starting point keeps the iterates near itself, as an anchor holds a ship. This is why it is called an anchor, and such methods are called anchored methods. The meaning of the anchor is seen from the regularized problem F ( z ) + β ( z − z 0 ) = 0 F(z) + \beta(z-z_0) = 0 F ( z ) + β ( z − z 0 ) = 0 , β > 0 \beta> 0 β > 0 . By the monotonicity of F F F , its solution z β z_\beta z β satisfies ∥ z β − z 0 ∥ ≤ ∥ z ∗ − z 0 ∥ \lVert z_\beta-z_0\rVert\le\lVert z^*-z_0\rVert ∥ z β − z 0 ∥ ≤ ∥ z ∗ − z 0 ∥ , hence ∥ F ( z β ) ∥ = β ∥ z β − z 0 ∥ ≤ β ∥ z ∗ − z 0 ∥ \lVert F(z_\beta)\rVert= \beta\lVert z_\beta-z_0\rVert\le\beta\lVert z^*-z_0\rVert ∥ F ( z β )∥ = β ∥ z β − z 0 ∥ ≤ β ∥ z ∗ − z 0 ∥ . Anchored methods track z β z_\beta z β with β \beta β of order L / k L/k L / k , and the norm of the operator at the last point decreases as 1 / k 1/k 1/ k . The Halpern iteration made it possible to obtain a bound of order L R / ε LR/\varepsilon L R / ε up to a logarithm (Diakonikolas [7 ] ) and the accelerated anchored extragradient method EAG (Extra Anchored Gradient) [31 ] gives ∥ F ( z k ) ∥ 2 = O ( L 2 R 2 / k 2 ) \lVert F(z_k)\rVert^2 = O(L^2R^2/k^2) ∥ F ( z k ) ∥ 2 = O ( L 2 R 2 / k 2 ) , that is, O ( L R / ε ) O(LR/\varepsilon) O ( L R / ε ) oracle calls. Here R R R is the distance from the starting point to the solution. For monotone operators, the optimal complexity scales linearly with 1 / ε 1/\varepsilon 1/ ε , whereas for convex minimization it is of order L R 2 / ε \sqrt{LR^2/\varepsilon} L R 2 / ε .
All these bounds rely on a global Lipschitz constant L L L , which does not exist in many problems. For example, the function e x e^x e x has an unbounded second derivative, but it does not exceed the first one. Such growth, when the local Lipschitz constant is bounded in terms of the norm of the operator itself, is described by the ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -smoothness condition. It was proposed for functions [32 ] to explain the success of methods with gradient clipping: the local smoothness constant can grow together with the gradient norm. In the first two parts of the Descending Everest series of papers, we found the oracle complexity of minimizing a single convex ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -smooth function [23 ] and a sum of such functions [24 ] . For operators, the analogous condition ∥ D F ( z ) ∥ ≤ L 0 + L 1 ∥ F ( z ) ∥ \lVert DF(z)\rVert\le L_0+L_1\lVert F(z)\rVert ∥ D F ( z )∥ ≤ L 0 + L 1 ∥ F ( z )∥ was considered in [28 ] , where convergence of adaptive projection and extragradient methods was proved under the additional p p p -quasi-sharpness condition ⟨ F ( u ) , u − u ∗ ⟩ ≥ μ dist ( u , U ∗ ) p \langle F(u),u-u^*\rangle\ge\mu\operatorname{dist}(u,U^*)^p ⟨ F ( u ) , u − u ∗ ⟩ ≥ μ dist ( u , U ∗ ) p . For a monotone ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -Lipschitz operator without additional conditions, [3 {xrefext}] Theorem 3.6) showed that the extragradient method with stepsize inversely proportional to L 0 + L 1 ∥ F ( x k ) ∥ L_0+L_1\lVert F(x_k)\rVert L 0 + L 1 ∥ F ( x k )∥ finds a point with ∥ F ∥ ≤ ε \lVert F\rVert\le\varepsilon ∥ F ∥ ≤ ε in O ( 1 + ( L 0 R / ε + L 1 R ) 2 ) O(1+(L_0R/\varepsilon+L_1R)^2) O ( 1 + ( L 0 R / ε + L 1 R ) 2 ) oracle calls. The square arises because without an anchor the norm of the operator decreases as 1 / k 1/\sqrt{k} 1/ k , and while the norm is large, the steps have length of order 1 / L 1 1/L_1 1/ L 1 . Subsequent developments include the extragradient method with a moving anchor [1 ] , MAEG with a local stepsize test [26 ] , the method PolyakEG with Polyak-type stepsizes [30 ] , the method PF-AEG, which does not require knowledge of the parameters [4 ] , and an analysis of the extragradient method and Popov’s method in the presence of constraints [12 ] . For a monotone operator without additional conditions, all these bounds either have the same quadratic order or are not expressed in terms of L 0 , L 1 , R , ε L_0,L_1,R,\varepsilon L 0 , L 1 , R , ε alone. In the LongTails repository [27 ] , a Lean-verified bound O ( 1 + L 0 R / ε + ( L 1 R ) 4 / 3 ) O(1+L_0R/\varepsilon+(L_1R)^{4/3}) O ( 1 + L 0 R / ε + ( L 1 R ) 4/3 ) was obtained for the same class (theorem RadiusGeneralizedMonotone). We worked on this problem in parallel and independently and obtained a stronger bound with exponent 6 / 5 6/5 6/5 on L 1 R L_1R L 1 R , which is optimal up to logarithmic factors: it is matched by a lower bound for arbitrary randomized methods. A summary table of known bounds is given in Appendix § 11 .
The main difficulty in this setting is that the distance to the solution gives only an exponential bound on the norm of the operator at the starting point. Grönwall’s lemma implies only the bound ∥ F ( z 0 ) ∥ ≤ ( L 0 / L 1 ) ( e L 1 R − 1 ) \lVert F(z_0)\rVert\le(L_0/L_1)(e^{L_1R}-1) ∥ F ( z 0 )∥ ≤ ( L 0 / L 1 ) ( e L 1 R − 1 ) , and it is attained. The length of a safe step is inversely proportional to L 0 + L 1 ∥ F ( z ) ∥ L_0+L_1\lVert F(z)\rVert L 0 + L 1 ∥ F ( z )∥ , so the method has to pass through a region where the operator is exponentially large. For convex functions, in the first part of the series, the cost of passing through this region turned out to be L 1 R L_1R L 1 R up to logarithms. Thus, continuing our series of papers, we pose a natural question: how many oracle calls does it cost to pass through this region for a monotone operator if only an upper bound R R R on the distance to the solution is known? In this paper, we answer it.
Notation. Throughout, ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ denotes the Euclidean norm of a vector and the spectral norm of a matrix, [ x , y ] [x,y] [ x , y ] is the segment with endpoints x , y ∈ R d x,y\in\mathbb{R}^d x , y ∈ R d , B ( x , r ) B(x,r) B ( x , r ) is the closed ball of radius r r r centered at x x x , e i e_i e i is the i i i -th standard basis vector, 1 \mathbf{1} 1 is the all-ones vector, and D F DF D F is the Jacobian matrix of the operator F F F . The sum of the first k k k terms of a sequence is denoted by the corresponding capital letter, for example, Λ k = λ 1 + ⋯ + λ k \Lambda_k=\lambda_1+\cdots+\lambda_k Λ k = λ 1 + ⋯ + λ k and Λ 0 = 0 \Lambda_0=0 Λ 0 = 0 . The logarithm is natural, and log + t = max { 0 , log t } \log_+ t=\max\{0,\log t\} log + t = max { 0 , log t } .
Main result. We show that for L 0 R / ε ≥ 1 L_0R/\varepsilon\ge1 L 0 R / ε ≥ 1 the minimax number of oracle calls T ∗ T^* T ∗ required to find a point z ^ \hat{z} z ^ with ∥ F ( z ^ ) ∥ ≤ ε \lVert F(\hat{z})\rVert\le\varepsilon ∥ F ( z ^ )∥ ≤ ε satisfies the inequalities
c ( 1 + L 0 R ε + ( L 1 R ) 6 / 5 log 4 / 5 ( 2 + L 1 R ) ) ≤ 1 + T ∗ ≤ C ( 1 + L 0 R ε + ( L 1 R ) 6 / 5 ) c\left(1+\frac{L_0R}{\varepsilon}+\frac{(L_1R)^{6/5}}{\log^{4/5}(2+L_1R)}\right)\le1+T^*\le C\left(1+\frac{L_0R}{\varepsilon}+(L_1R)^{6/5}\right) c ( 1 + ε L 0 R + log 4/5 ( 2 + L 1 R ) ( L 1 R ) 6/5 ) ≤ 1 + T ∗ ≤ C ( 1 + ε L 0 R + ( L 1 R ) 6/5 )
with absolute constants c , C > 0 c,C>0 c , C > 0 (Theorem 2.8 ). The upper bound is attained by a deterministic method, and the lower bound holds for arbitrary randomized methods, which may query the operator at any points and output any point. The term L 0 R / ε L_0R/\varepsilon L 0 R / ε is known from the Lipschitz case. The term ( L 1 R ) 6 / 5 (L_1R)^{6/5} ( L 1 R ) 6/5 appears as the cost of passing through the region of large operator values. Thus, for monotone operators, this cost is larger than for gradients of convex functions, where it equals L 1 R L_1R L 1 R . The same bounds with L 0 R / ε L_0R/\varepsilon L 0 R / ε replaced by L 0 R 2 / η L_0R^2/\eta L 0 R 2 / η are obtained for the Minty gap computed over the ball of radius R R R around the starting point.
Upper bound. The method ABSEIL consists of two stages. At the first stage (the method GLISSADE), while ∥ F ( z ) ∥ > 2 L 0 R ( e ( L 1 R ) 2 / 5 − 1 ) / ( L 1 R ) 2 / 5 \lVert F(z)\rVert> 2L_0R(e^{(L_1R)^{2/5}}-1)/(L_1R)^{2/5} ∥ F ( z )∥ > 2 L 0 R ( e ( L 1 R ) 2/5 − 1 ) / ( L 1 R ) 2/5 , the method takes steps of length R / ( 2 ( L 1 R ) 3 / 5 ) R/(2(L_1R)^{3/5}) R / ( 2 ( L 1 R ) 3/5 ) along the direction − F ( z ) / ∥ F ( z ) ∥ -F(z)/\lVert F(z)\rVert − F ( z ) / ∥ F ( z )∥ . Near the solution, the operator is small by Grönwall’s lemma, so monotonicity guarantees that such a step decreases the squared distance to the solution by R 2 / ( 4 ( L 1 R ) 6 / 5 ) R^2/(4(L_1R)^{6/5}) R 2 / ( 4 ( L 1 R ) 6/5 ) (Lemma 3.1 ), and the first stage has at most 4 ( L 1 R ) 6 / 5 4(L_1R)^{6/5} 4 ( L 1 R ) 6/5 steps. At the second stage (the method BELAY), the extragradient method with moving anchor (Alcala et al., [1 ] ; Sun et al. [26 ] ) runs, in which the steps are computed by an explicit formula. Its cost is of order L 0 R / ε + ( L 1 R ) 6 / 5 L_0R/\varepsilon+(L_1R)^{6/5} L 0 R / ε + ( L 1 R ) 6/5 : the logarithm of ∥ F ∥ \lVert F\rVert ∥ F ∥ after the first stage enters the bound under the square root (Proposition 3.3 ). The step length of the first stage is chosen so that the costs of the two stages have the same order (§ 3.4 ).
Lower bound. The term L 0 R / ε L_0R/\varepsilon L 0 R / ε is obtained by a reduction to solving linear systems, for which a lower bound for randomized methods was proved in Dereziński et al. [6 ] . The nonlinear term is obtained on a chain (Nemirovsky and Yudin, [19 ] ; Nesterov [20 ] ): each oracle answer reveals at most one new coordinate. The worst-case operator is defined as the inverse of v ↦ ∂ ( Q + I K ) ( v ) + B v v\mapsto\partial(Q+I_K)(v)+Bv v ↦ ∂ ( Q + I K ) ( v ) + B v , where Q Q Q is a convex function on the weighted simplex K K K , and B B B is a skew-symmetric block matrix. The generalized strong monotonicity of ∂ Q \partial Q ∂ Q yields the ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -Lipschitz continuity of the inverse operator, and the shift and the matrix B B B force the coordinates to be revealed one at a time. To prevent the method from guessing the unrevealed coordinates, the chain is randomly embedded into a high-dimensional space, and outside a large ball the operator is replaced by a known linear one (Woodworth and Srebro, [29 ] ; Carmon et al. [2 ] ).
Bounded set. For a variational inequality on a compact set, a solution no longer has to be a zero of the operator. For each continuous operator, the norm of F ( z ∗ ) F(z^*) F ( z ∗ ) is finite, but it is not uniformly bounded over the class of operators with given L 0 L_0 L 0 , L 1 L_1 L 1 , and diameter of the set. We show that, as a consequence, the minimax complexity of this class is infinite (Theorem 5.1 ), and a uniform bound requires an additional parameter, for example, an upper bound on ∥ F ( z ∗ ) ∥ \lVert F(z^*)\rVert ∥ F ( z ∗ )∥ .
Organization of the paper. The problem setting and the main result are given in § 2 , the method and the upper bound in § 3 , and the lower bounds in § 4 . § 5 is devoted to variational inequalities on a bounded set, and § 6 to open questions. The proofs are deferred to Appendices § 7 –§ 10 , and Appendix § 11 contains a summary table of known results.
Problem setting and main result
We consider an operator F : R d → R d F:\mathbb{R}^{d}\to\mathbb{R}^{d} F : R d → R d . We are given numbers L 0 , R > 0 L_{0},R>0 L 0 , R > 0 , L 1 ≥ 0 L_{1}\ge0 L 1 ≥ 0 , and a starting point z 0 ∈ R d z_{0}\in\mathbb{R}^{d} z 0 ∈ R d . All general assumptions are collected below.
Assumption 2.1 (monotonicity). The operator F F F is continuous and ⟨ F ( u ) − F ( v ) , u − v ⟩ ≥ 0 \langle F(u)-F(v),u-v\rangle\ge0 ⟨ F ( u ) − F ( v ) , u − v ⟩ ≥ 0 for all u , v ∈ R d u,v\in\mathbb{R}^{d} u , v ∈ R d .
Assumption 2.2 ((L 0 , L 1 L_{0},L_{1} L 0 , L 1 )-Lipschitz continuity). For all u , v ∈ R d u,v\in\mathbb{R}^{d} u , v ∈ R d ,
∥ F ( u ) − F ( v ) ∥ ≤ ( L 0 + L 1 sup w ∈ [ u , v ] ∥ F ( w ) ∥ ) ∥ u − v ∥ . (1) \lVert F(u)-F(v)\rVert\le\left(L_{0}+L_{1}\sup_{w\in[u,v]}\lVert F(w)\rVert\right)\lVert u-v\rVert. \tag*{(1)} ∥ F ( u ) − F ( v )∥ ≤ ( L 0 + L 1 w ∈ [ u , v ] sup ∥ F ( w )∥ ) ∥ u − v ∥ . (1)
Assumption 2.3 (solution). There exists a point z ∗ z^{*} z ∗ such that F ( z ∗ ) = 0 F(z^{*})=0 F ( z ∗ ) = 0 and ∥ z ∗ − z 0 ∥ ≤ R \lVert z^{*}-z_{0}\rVert\le R ∥ z ∗ − z 0 ∥ ≤ R .
Assumption 2.3 singles out the class of solvable problems, and all bounds of this paper, upper and lower, refer to this class. Without it, the problem may have no solution, as for the constant operator F ≡ c ≠ 0 F\equiv c\ne0 F ≡ c = 0 .
Assumption 2.2 is the symmetric ( L 0 , L 1 ) (L_{0},L_{1}) ( L 0 , L 1 ) -smoothness condition [11 Assumption 1.3] , written for an operator instead of a gradient. For operators, it is called ( L 0 , L 1 ) (L_{0},L_{1}) ( L 0 , L 1 ) -Lipschitz continuity [3 , 12 ] . It coincides with the α \alpha α -symmetric generalized smoothness condition of Vankov et al. [28 ] for α = 1 \alpha=1 α = 1 . Inequality (1) is required on the whole space, since the method may query the operator outside the ball B ( z 0 , R ) B(z_{0},R) B ( z 0 , R ) . We assume neither strong monotonicity of the operator nor that it is a potential operator, that is, the gradient of some function. The following lemma shows that for continuously differentiable operators, condition (1) is equivalent to the Jacobian norm bound ∥ D F ( z ) ∥ ≤ L 0 + L 1 ∥ F ( z ) ∥ \lVert DF(z)\rVert\le L_{0}+L_{1}\lVert F(z)\rVert ∥ D F ( z )∥ ≤ L 0 + L 1 ∥ F ( z )∥ , by which ( L 0 , L 1 ) (L_{0},L_{1}) ( L 0 , L 1 ) -Lipschitz continuity of an operator is defined in the introduction.
Lemma 2.4 (characterization of the class). ▼ proof in Appendix § 7 .§ 1
(a) A continuous operator F F F satisfies (1) if and only if for any x , v ∈ R d x,v\in\mathbb{R}^{d} x , v ∈ R d the map t ↦ F ( x + t v ) t\mapsto F(x+tv) t ↦ F ( x + t v ) is locally absolutely continuous and for almost all t t t
∥ d d t F ( x + t v ) ∥ ≤ ( L 0 + L 1 ∥ F ( x + t v ) ∥ ) ∥ v ∥ . \left\lVert\frac{d}{dt}F(x+tv)\right\rVert\le\left(L_{0}+L_{1}\lVert F(x+tv)\rVert\right)\lVert v\rVert. d t d F ( x + t v ) ≤ ( L 0 + L 1 ∥ F ( x + t v )∥ ) ∥ v ∥ . (b) If F ∈ C 1 ( R d ) F\in C^{1}(\mathbb{R}^{d}) F ∈ C 1 ( R d ) , then F F F satisfies (1) if and only if ∥ D F ( z ) ∥ ≤ L 0 + L 1 ∥ F ( z ) ∥ \lVert DF(z)\rVert\le L_{0}+L_{1}\lVert F(z)\rVert ∥ D F ( z )∥ ≤ L 0 + L 1 ∥ F ( z )∥ for all z ∈ R d z\in\mathbb{R}^{d} z ∈ R d .
(c) If F F F is locally Lipschitz and ∥ D F ( z ) ∥ ≤ L 0 + L 1 ∥ F ( z ) ∥ \lVert DF(z)\rVert\le L_{0}+L_{1}\lVert F(z)\rVert ∥ D F ( z )∥ ≤ L 0 + L 1 ∥ F ( z )∥ for almost all z z z , then F F F satisfies (1) .
The main consequence of condition (1) is a bound on the rate of change of the operator along a segment. It replaces Lipschitz continuity in all proofs of this paper.
Lemma 2.5 (consequences of Grönwall’s lemma). ▼ proof in Appendix A.2
Let F F F satisfy (1) . Then for any u , v ∈ R d u,v \in\mathbb{R}^{d} u , v ∈ R d
(a) L 0 + L 1 ∥ F ( v ) ∥ ≤ ( L 0 + L 1 ∥ F ( u ) ∥ ) e L 1 ∥ u − v ∥ , (b) ∥ F ( v ) − F ( u ) ∥ ≤ ( L 0 + L 1 ∥ F ( u ) ∥ ) e L 1 ∥ u − v ∥ − 1 L 1 ≤ ( L 0 + L 1 ∥ F ( u ) ∥ ) ∥ u − v ∥ e L 1 ∥ u − v ∥ . \begin{aligned}
\text{(a)}\quad L_{0}+L_{1}\lVert F(v)\rVert&\leq\left(L_{0}+L_{1}\lVert F(u)\rVert\right)e^{L_{1}\lVert u-v\rVert},\\
\text{(b)}\quad\lVert F(v)-F(u)\rVert&\leq\left(L_{0}+L_{1}\lVert F(u)\rVert\right)\frac{e^{L_{1}\lVert u-v\rVert}-1}{L_{1}}\\
&\leq\left(L_{0}+L_{1}\lVert F(u)\rVert\right)\lVert u-v\rVert e^{L_{1}\lVert u-v\rVert}.
\end{aligned} (a) L 0 + L 1 ∥ F ( v )∥ (b) ∥ F ( v ) − F ( u )∥ ≤ ( L 0 + L 1 ∥ F ( u )∥ ) e L 1 ∥ u − v ∥ , ≤ ( L 0 + L 1 ∥ F ( u )∥ ) L 1 e L 1 ∥ u − v ∥ − 1 ≤ ( L 0 + L 1 ∥ F ( u )∥ ) ∥ u − v ∥ e L 1 ∥ u − v ∥ .
For L 1 = 0 L_{1}=0 L 1 = 0 , the fraction ( e L 1 ∥ u − v ∥ − 1 ) / L 1 (e^{L_{1}\lVert u-v\rVert}-1)/L_{1} ( e L 1 ∥ u − v ∥ − 1 ) / L 1 in Lemma 2.5 is understood as ∥ u − v ∥ \lVert u-v\rVert ∥ u − v ∥ . The proof of the lemma uses condition (1) only on the segment [ u , v ] [u,v] [ u , v ] . If the map t ↦ F ( u + t ( v − u ) ) t \mapsto F(u+t(v-u)) t ↦ F ( u + t ( v − u )) is absolutely continuous on [ 0 , 1 ] [0,1] [ 0 , 1 ] and the bound of Lemma 2.4 (a) with some constant A > 0 A>0 A > 0 in place of L 0 L_{0} L 0 holds only for points of the segment [ u , v ] [u,v] [ u , v ] , then (a) and (b) hold with A A A in place of L 0 L_{0} L 0 .
In particular, by Assumption 2.3 , Lemma 2.5 (b) with u = z ∗ u=z^{*} u = z ∗ gives ∥ F ( z 0 ) ∥ ≤ ( L 0 / L 1 ) ( e L 1 R − 1 ) \lVert F(z_{0})\rVert\leq(L_{0}/L_{1})(e^{L_{1}R}-1) ∥ F ( z 0 )∥ ≤ ( L 0 / L 1 ) ( e L 1 R − 1 ) . This bound is attained. For the convex function f ( z ) = L 0 L 1 − 2 ( e L 1 ∥ z ∥ − 1 − L 1 ∥ z ∥ ) f(z)=L_{0}L_{1}^{-2}(e^{L_{1}\lVert z\rVert}-1-L_{1}\lVert z\rVert) f ( z ) = L 0 L 1 − 2 ( e L 1 ∥ z ∥ − 1 − L 1 ∥ z ∥) , the operator F = ∇ f F=\nabla f F = ∇ f satisfies Assumptions 2.1 –2.3 with z ∗ = 0 z^{*}=0 z ∗ = 0 (Rudomanov et al., [23 ] ), and ∥ F ( z ) ∥ = ( L 0 / L 1 ) ( e L 1 ∥ z ∥ − 1 ) \lVert F(z)\rVert=(L_{0}/L_{1})(e^{L_{1}\lVert z\rVert}-1) ∥ F ( z )∥ = ( L 0 / L 1 ) ( e L 1 ∥ z ∥ − 1 ) . Thus, the norm of the operator at the starting point may be exponentially large in L 1 R L_{1}R L 1 R .
Oracle model. The algorithm knows L 0 L_{0} L 0 , L 1 L_{1} L 1 , R R R , z 0 z_{0} z 0 , and the required accuracy. It obtains information about the operator only from an oracle that, for a query z ∈ R d z\in\mathbb{R}^{d} z ∈ R d , returns the exact value F ( z ) F(z) F ( z ) . Queries are allowed anywhere in the space. The query points, the stopping time τ \tau τ , and the output point z ^ \hat{z} z ^ are measurable functions of the received oracle answers and the random variables of the algorithm. Complexity is measured by the number of oracle calls (Nesterov, [20 ] , Section 1.1). The word “randomized” refers to the algorithm: the oracle answers contain no noise.
Accuracy criteria. The main criterion is the norm of the operator at the output point: ∥ F ( z ^ ) ∥ ≤ ε \lVert F(\hat{z})\rVert\leq\varepsilon ∥ F ( z ^ )∥ ≤ ε . For comparison with the theory of variational inequalities, we also consider the Minty gap (Minty, [16 ] ) computed over the ball B ( z 0 , R ) B(z_{0},R) B ( z 0 , R ) :
Gap R ( z ) = sup u ∈ B ( z 0 , R ) ⟨ F ( u ) , z − u ⟩ . (2) \operatorname{Gap}_{R}(z)=\sup_{u\in B(z_{0},R)}\langle F(u),z-u\rangle. \tag*{(2)} Gap R ( z ) = u ∈ B ( z 0 , R ) sup ⟨ F ( u ) , z − u ⟩ . (2)
Here the ball only defines the set over which the supremum is taken: the queries and the output point may lie outside it. Since z ∗ ∈ B ( z 0 , R ) z^{*}\in B(z_{0},R) z ∗ ∈ B ( z 0 , R ) and ⟨ F ( z ∗ ) , z − z ∗ ⟩ = 0 \langle F(z^{*}),z-z^{*}\rangle=0 ⟨ F ( z ∗ ) , z − z ∗ ⟩ = 0 , the gap is nonnegative. The supremum cannot be taken over the whole space: for F ( z ) = S z F(z)=Sz F ( z ) = S z with a nonzero skew-symmetric matrix S S S , we have sup u ∈ R d ⟨ S u , z − u ⟩ = sup u ∈ R d ⟨ S u , z ⟩ = + ∞ \sup_{u\in\mathbb{R}^{d}}\langle Su,z-u\rangle=\sup_{u\in\mathbb{R}^{d}}\langle Su,z\rangle=+\infty sup u ∈ R d ⟨ S u , z − u ⟩ = sup u ∈ R d ⟨ S u , z ⟩ = + ∞ if S z ≠ 0 Sz\neq0 S z = 0 . A small norm of the operator implies a small Gap R ( z ) \operatorname{Gap}_{R}(z) Gap R ( z ) .
Lemma 2.6 (gap and the norm of F F F ). ▼ proof in Appendix A.3
Under Assumptions 2.1 and 2.3 , for any point z ∈ R d z\in\mathbb{R}^{d} z ∈ R d we have
0 ≤ Gap R ( z ) ≤ ( ∥ z − z 0 ∥ + R ) ∥ F ( z ) ∥ . 0\leq\operatorname{Gap}_{R}(z)\leq(\lVert z-z_{0}\rVert+R)\lVert F(z)\rVert. 0 ≤ Gap R ( z ) ≤ (∥ z − z 0 ∥ + R ) ∥ F ( z )∥ .
Oracle complexity. We denote by P d \mathcal{P}_{d} P d the set of operators F : R d → R d F:\mathbb{R}^{d}\to\mathbb{R}^{d} F : R d → R d satisfying Assumptions 2.1 –2.3 . Let τ M ( F ) \tau_{\mathrm{M}}(F) τ M ( F ) be the number of oracle calls made by the algorithm M on the operator F F F , and let z ^ M ( F ) \hat{z}_{\mathrm{M}}(F) z ^ M ( F ) be its output point.
Definition 2.7 (oracle complexity). An algorithm is called admissible if for any d d d and F ∈ P d F \in\mathcal{P}_d F ∈ P d it stops almost surely and
Pr { ∥ F ( z ^ M ( F ) ) ∥ ≤ ε } ≥ 2 3 . \Pr\{\lVert F(\hat{z}_{\mathsf{M}}(F))\rVert\le\varepsilon\} \ge\frac{2}{3}. Pr {∥ F ( z ^ M ( F ))∥ ≤ ε } ≥ 3 2 . The complexity of an algorithm and the minimax complexity are defined as
T ( M ) = sup d ≥ 1 sup F ∈ P d E τ M ( F ) , \mathcal{T}(\mathsf{M})=\sup_{d\ge1}\sup_{F\in\mathcal{P}_d}\mathbb{E}\tau_{\mathsf{M}}(F), T ( M ) = d ≥ 1 sup F ∈ P d sup E τ M ( F ) , T ∗ ( ε ) = inf M a d m i s s i b l e T ( M ) . (3) \mathcal{T}^{*}(\varepsilon)=\inf_{\mathsf{M}\ \mathrm{admissible}}\mathcal{T}(\mathsf{M}). \tag*{(3)} T ∗ ( ε ) = M admissible inf T ( M ) . (3)
We denote by T d e t ∗ ( ε ) \mathcal{T}^{*}_{\mathrm{det}}(\varepsilon) T det ∗ ( ε ) the same quantity where the infimum is taken over deterministic algorithms for which ∥ F ( z ^ M ( F ) ) ∥ ≤ ε \lVert F(\hat{z}_{\mathsf{M}}(F))\rVert\le\varepsilon ∥ F ( z ^ M ( F ))∥ ≤ ε on every operator. The quantities T G a p ∗ ( η ) \mathcal{T}^{*}_{\mathrm{Gap}}(\eta) T Gap ∗ ( η ) and T G a p , d e t ∗ ( η ) \mathcal{T}^{*}_{\mathrm{Gap,det}}(\eta) T Gap , det ∗ ( η ) are defined in the same way with the condition ∥ F ( z ^ ) ∥ ≤ ε \lVert F(\hat{z})\rVert\le\varepsilon ∥ F ( z ^ )∥ ≤ ε replaced by Gap R ( z ^ ) ≤ η \operatorname{Gap}_{R}(\hat{z}) \le\eta Gap R ( z ^ ) ≤ η .
Clearly, T ∗ ≤ T d e t ∗ \mathcal{T}^{*} \le\mathcal{T}^{*}_{\mathrm{det}} T ∗ ≤ T det ∗ . The class P d \mathcal{P}_d P d is invariant under shifts, so in the lower bounds we assume z 0 = 0 z_0=0 z 0 = 0 .
Theorem 2.8 (two-sided complexity bound). There exist absolute constants c , C > 0 c,C>0 c , C > 0 such that for L 0 R / ε ≥ 1 L_0R/\varepsilon\ge1 L 0 R / ε ≥ 1
c ( 1 + L 0 R ε + ( L 1 R ) 6 / 5 log 4 / 5 ( 2 + L 1 R ) ) ≤ 1 + T ∗ ( ε ) ≤ 1 + T d e t ∗ ( ε ) ≤ C ( 1 + L 0 R ε + ( L 1 R ) 6 / 5 ) . (4) c\left(1+\frac{L_0R}{\varepsilon}+\frac{(L_1R)^{6/5}}{\log^{4/5}(2+L_1R)}\right)\le1+\mathcal{T}^{*}(\varepsilon)\le1+\mathcal{T}^{*}_{\mathrm{det}}(\varepsilon)\le C\left(1+\frac{L_0R}{\varepsilon}+(L_1R)^{6/5}\right). \tag*{(4)} c ( 1 + ε L 0 R + log 4/5 ( 2 + L 1 R ) ( L 1 R ) 6/5 ) ≤ 1 + T ∗ ( ε ) ≤ 1 + T det ∗ ( ε ) ≤ C ( 1 + ε L 0 R + ( L 1 R ) 6/5 ) . (4) and for L 0 R 2 / η ≥ 1 L_0R^2/\eta\ge1 L 0 R 2 / η ≥ 1
c ( 1 + L 0 R 2 η + ( L 1 R ) 6 / 5 log 4 / 5 ( 2 + L 1 R ) ) ≤ 1 + T G a p ∗ ( η ) ≤ 1 + T G a p , d e t ∗ ( η ) ≤ C ( 1 + L 0 R 2 η + ( L 1 R ) 6 / 5 ) . (5) c\left(1+\frac{L_0R^2}{\eta}+\frac{(L_1R)^{6/5}}{\log^{4/5}(2+L_1R)}\right)\le1+\mathcal{T}^{*}_{\mathrm{Gap}}(\eta)\le1+\mathcal{T}^{*}_{\mathrm{Gap,det}}(\eta)\le C\left(1+\frac{L_0R^2}{\eta}+(L_1R)^{6/5}\right). \tag*{(5)} c ( 1 + η L 0 R 2 + log 4/5 ( 2 + L 1 R ) ( L 1 R ) 6/5 ) ≤ 1 + T Gap ∗ ( η ) ≤ 1 + T Gap , det ∗ ( η ) ≤ C ( 1 + η L 0 R 2 + ( L 1 R ) 6/5 ) . (5)
The lower bounds remain valid on the subclass of operators from C 2 ( R d ) C^2(\mathbb{R}^d) C 2 ( R d ) . The upper bounds are proved in Theorem 3.4. They are attained by the method ABSEIL (§ 3.1 ), which outputs a point from the ball B ( z 0 , 5 R ) B(z_0,5R) B ( z 0 , 5 R ) and uses the known L 0 L_0 L 0 , L 1 L_1 L 1 , R R R . The term L 0 R / ε L_0R/\varepsilon L 0 R / ε (respectively, L 0 R 2 / η L_0R^2/\eta L 0 R 2 / η ) in the lower bounds is obtained in Proposition 4.11 , and the nonlinear term in Theorem 4.12 . The two lower bounds are combined by the inequality max { x , y } ≥ ( x + y ) / 2 \max\{x,y\}\ge(x+y)/2 max { x , y } ≥ ( x + y ) /2 .
The upper and lower bounds differ only by the factor log 4 / 5 ( 2 + L 1 R ) \log^{4/5}(2+L_1R) log 4/5 ( 2 + L 1 R ) in the nonlinear term. In particular, if L 0 R / ε ≥ ( L 1 R ) 6 / 5 L_0R/\varepsilon\ge(L_1R)^{6/5} L 0 R / ε ≥ ( L 1 R ) 6/5 , then 1 + T ∗ 1+\mathcal{T}^{*} 1 + T ∗ and 1 + T d e t ∗ 1+\mathcal{T}^{*}_{\mathrm{det}} 1 + T det ∗ are equal to Θ ( 1 + L 0 R / ε ) \Theta(1+L_0R/\varepsilon) Θ ( 1 + L 0 R / ε ) , and for L 1 = 0 L_1=0 L 1 = 0 we recover the classical bound for Lipschitz operators. The condition L 0 R / ε ≥ 1 L_0R/\varepsilon\ge1 L 0 R / ε ≥ 1 is essential for the lower bound. If, for example, ( L 0 / L 1 ) ( e L 1 R − 1 ) ≤ ε (L_0/L_1)(e^{L_1R}-1)\le\varepsilon ( L 0 / L 1 ) ( e L 1 R − 1 ) ≤ ε , then by Lemma 2.5 the point z 0 z_0 z 0 is acceptable without any oracle calls.
All three quantities L 0 R / ε L_0R/\varepsilon L 0 R / ε , L 0 R 2 / η L_0R^2/\eta L 0 R 2 / η , and L 1 R L_1R L 1 R are dimensionless. If F ~ ( x ) = γ F ( z 0 + β x ) \widetilde{F}(x)=\gamma F(z_0+\beta x) F ( x ) = γ F ( z 0 + β x ) with γ , β > 0 \gamma,\beta>0 γ , β > 0 , then F ~ \widetilde{F} F satisfies the assumptions with the parameters γ β L 0 \gamma\beta L_0 γ β L 0 , β L 1 \beta L_1 β L 1 , R / β R/\beta R / β , and the accuracies become γ ε \gamma\varepsilon γ ε and γ η / β \gamma\eta/\beta γ η / β . Therefore, the complexity measured by ∥ F ∥ \lVert F\rVert ∥ F ∥ can depend only on L 0 R / ε L_0R/\varepsilon L 0 R / ε and L 1 R L_1R L 1 R , and the complexity measured by the gap only on L 0 R 2 / η L_0R^2/\eta L 0 R 2 / η and L 1 R L_1R L 1 R .
Upper bound
In this section, we construct a method that attains the upper bound of Theorem 2.8 . Throughout the section, Assumptions 2.1 –2.3 hold.
The method
The method ABSEIL consists of two stages2 . At the first stage, while the norm of the operator is large, the method GLISSADE (Algorithm 1) takes long steps along the direction − F ( z ) / ∥ F ( z ) ∥ -F(z)/\lVert F(z)\rVert − F ( z ) / ∥ F ( z )∥ . At the second stage, the method BELAY (Algorithm 2) runs. It is an extragradient method with a moving anchor. The moving anchor was proposed by Alcala et al. [1 ] , and for ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -Lipschitz operators such a method, called MAEG, was studied by Sun et al. [26 ] . In MAEG, a trial step is accepted after checking the stepsize condition at already computed points and is decreased if the condition fails, so rejected steps require additional oracle calls. In BELAY, the stepsize is computed before the oracle call from already known values of the operator, and this stepsize always satisfies the required condition (Proposition 3.3 ).
The method ABSEIL works as follows. If L 1 R ≥ 1 L_1R \ge1 L 1 R ≥ 1 , it runs GLISSADE from the point z 0 z_0 z 0 and obtains a point s s s . If L 1 R < 1 L_1R < 1 L 1 R < 1 , it sets s = z 0 s=z_0 s = z 0 and queries F ( z 0 ) F(z_0) F ( z 0 ) . If ∥ F ( s ) ∥ ≤ ε \lVert F(s)\rVert\le\varepsilon ∥ F ( s )∥ ≤ ε , the method outputs s s s . Otherwise, it runs BELAY from the point s s s and outputs the resulting point.
Algorithm 1 GLISSADE (first stage)
Input: z 0 z_0 z 0 , L 0 L_0 L 0 , L 1 L_1 L 1 , R R R , ε \varepsilon ε , where L 1 R ≥ 1 L_1R \ge1 L 1 R ≥ 1
z ← z 0 z \gets z_0 z ← z 0
query F ( z ) F(z) F ( z )
while ∥ F ( z ) ∥ > max { ε , 2 L 0 R ( e ( L 1 R ) 2 / 5 − 1 ) / ( L 1 R ) 2 / 5 } \lVert F(z)\rVert> \max\{\varepsilon,\;2L_0R(e^{(L_1R)^{2/5}}-1)/(L_1R)^{2/5}\} ∥ F ( z )∥ > max { ε , 2 L 0 R ( e ( L 1 R ) 2/5 − 1 ) / ( L 1 R ) 2/5 } do
z ← z − R 2 ( L 1 R ) 3 / 5 F ( z ) ∥ F ( z ) ∥ z \gets z-\dfrac{R}{2(L_1R)^{3/5}}\dfrac{F(z)}{\lVert F(z)\rVert} z ← z − 2 ( L 1 R ) 3/5 R ∥ F ( z )∥ F ( z )
query F ( z ) F(z) F ( z )
end while
return z z z
Long steps
Long steps are based on the following observation. Let ∥ x − z ∗ ∥ ≤ R \lVert x-z^*\rVert\le R ∥ x − z ∗ ∥ ≤ R and let the norm ∥ F ( x ) ∥ \lVert F(x)\rVert ∥ F ( x )∥ be large. Consider the point w = z ∗ + R ( L 1 R ) − 3 / 5 F ( x ) / ∥ F ( x ) ∥ w=z^*+R(L_1R)^{-3/5}F(x)/\lVert F(x)\rVert w = z ∗ + R ( L 1 R ) − 3/5 F ( x ) / ∥ F ( x )∥ , shifted from the solution in the direction F ( x ) F(x) F ( x ) . It lies at a distance R / ( L 1 R ) 3 / 5 R/(L_1R)^{3/5} R / ( L 1 R ) 3/5 from the solution, so by Lemma 2.5 (b) with u = z ∗ u=z^* u = z ∗
∥ F ( w ) ∥ ≤ L 0 L 1 ( e ( L 1 R ) 2 / 5 − 1 ) \lVert F(w)\rVert\le\frac{L_0}{L_1}\left(e^{(L_1R)^{2/5}}-1\right) ∥ F ( w )∥ ≤ L 1 L 0 ( e ( L 1 R ) 2/5 − 1 )
and this quantity is small compared to ∥ F ( x ) ∥ \lVert F(x)\rVert ∥ F ( x )∥ . By monotonicity, ⟨ F ( x ) , x − w ⟩ ≥ ⟨ F ( w ) , x − w ⟩ ≥ − ∥ F ( w ) ∥ ∥ x − w ∥ \langle F(x),x-w\rangle\ge\langle F(w),x-w\rangle\ge-\lVert F(w)\rVert\lVert x-w\rVert ⟨ F ( x ) , x − w ⟩ ≥ ⟨ F ( w ) , x − w ⟩ ≥ − ∥ F ( w )∥ ∥ x − w ∥ . Hence the projection of the vector x − z ∗ x-z^* x − z ∗ onto the direction F ( x ) / ∥ F ( x ) ∥ F(x)/\lVert F(x)\rVert F ( x ) / ∥ F ( x )∥ is at least R / ( L 1 R ) 3 / 5 R/(L_1R)^{3/5} R / ( L 1 R ) 3/5 up to a small correction. Therefore, a step of length R / ( 2 ( L 1 R ) 3 / 5 ) R/(2(L_1R)^{3/5}) R / ( 2 ( L 1 R ) 3/5 ) along − F ( x ) / ∥ F ( x ) ∥ -F(x)/\lVert F(x)\rVert − F ( x ) / ∥ F ( x )∥ brings the point closer to the solution, although the solution itself is unknown to the method. The precise statement is given in the following lemma.
Lemma 3.1 (long step). ▼ proof in Appendix § 8 .§ 1
Let ∥ x − z ∗ ∥ ≤ R \lVert x-z^*\rVert\le R ∥ x − z ∗ ∥ ≤ R and L 1 R ≥ 1 L_1R \ge1 L 1 R ≥ 1 . If ∥ F ( x ) ∥ > 2 L 0 R ( e ( L 1 R ) 2 / 5 − 1 ) / ( L 1 R ) 2 / 5 \lVert F(x)\rVert> 2L_0R(e^{(L_1R)^{2/5}}-1)/(L_1R)^{2/5} ∥ F ( x )∥ > 2 L 0 R ( e ( L 1 R ) 2/5 − 1 ) / ( L 1 R ) 2/5 , then
∥ x − R 2 ( L 1 R ) 3 / 5 F ( x ) ∥ F ( x ) ∥ − z ∗ ∥ 2 ≤ ∥ x − z ∗ ∥ 2 − R 2 4 ( L 1 R ) 6 / 5 . \left\lVert x-\frac{R}{2(L_1R)^{3/5}}\frac{F(x)}{\lVert F(x)\rVert}-z^*\right\rVert^2 \le\lVert x-z^*\rVert^2-\frac{R^2}{4(L_1R)^{6/5}}. x − 2 ( L 1 R ) 3/5 R ∥ F ( x )∥ F ( x ) − z ∗ 2 ≤ ∥ x − z ∗ ∥ 2 − 4 ( L 1 R ) 6/5 R 2 .
Algorithm 2 BELAY (second stage)
Input: s s s , F ( s ) F(s) F ( s ) , L 0 L_0 L 0 , L 1 L_1 L 1 , ε \varepsilon ε
u 0 ← s u_0 \leftarrow s u 0 ← s , y 0 ← s y_0 \leftarrow s y 0 ← s , Λ 0 ← 0 \Lambda_0 \leftarrow0 Λ 0 ← 0
for k = 1 , 2 , … k = 1, 2, \ldots k = 1 , 2 , … do
if k = 1 k = 1 k = 1 then
λ 1 ← 1 6 ( L 0 + L 1 ∥ F ( s ) ∥ ) \lambda_1 \leftarrow\frac{1}{6(L_0 + L_1\lVert F(s)\rVert)} λ 1 ← 6 ( L 0 + L 1 ∥ F ( s )∥) 1
else
B k ← ∥ F ( y k − 1 ) ∥ + 3 ∥ u k − 1 − y k − 1 ∥ 2 Λ k − 1 B_k \leftarrow\lVert F(y_{k-1})\rVert+ \frac{3\lVert u_{k-1} - y_{k-1}\rVert}{2\Lambda_{k-1}} B k ← ∥ F ( y k − 1 )∥ + 2 Λ k − 1 3 ∥ u k − 1 − y k − 1 ∥
λ k ← min { 4 λ k − 1 , 1 6 ( L 0 + L 1 B k ) } \lambda_k \leftarrow\min\left\{4\lambda_{k-1}, \frac{1}{6(L_0 + L_1B_k)}\right\} λ k ← min { 4 λ k − 1 , 6 ( L 0 + L 1 B k ) 1 }
end if
Λ k ← Λ k − 1 + λ k \Lambda_k \leftarrow\Lambda_{k-1} + \lambda_k Λ k ← Λ k − 1 + λ k
α k ← 3 λ k 2 Λ k − 1 + 3 λ k \alpha_k \leftarrow\frac{3\lambda_k}{2\Lambda_{k-1} + 3\lambda_k} α k ← 2 Λ k − 1 + 3 λ k 3 λ k
v k ← α k u k − 1 + ( 1 − α k ) y k − 1 v_k \leftarrow\alpha_k u_{k-1} + (1 - \alpha_k)y_{k-1} v k ← α k u k − 1 + ( 1 − α k ) y k − 1
x k ← v k − ( 1 − α k ) λ k F ( y k − 1 ) x_k \leftarrow v_k - (1 - \alpha_k)\lambda_kF(y_{k-1}) x k ← v k − ( 1 − α k ) λ k F ( y k − 1 )
query F ( x k ) F(x_k) F ( x k ) ▹ \triangleright ▹ for k = 1 k = 1 k = 1 we have x 1 = s x_1 = s x 1 = s , so no query is needed
y k ← v k − λ k F ( x k ) y_k \leftarrow v_k - \lambda_kF(x_k) y k ← v k − λ k F ( x k )
query F ( y k ) F(y_k) F ( y k )
u k ← u k − 1 − 1 6 λ k F ( y k ) u_k \leftarrow u_{k-1} - \frac{1}{6}\lambda_kF(y_k) u k ← u k − 1 − 6 1 λ k F ( y k )
if ∥ F ( y k ) ∥ ≤ ε \lVert F(y_k)\rVert\le\varepsilon ∥ F ( y k )∥ ≤ ε then
return y k y_k y k
end if
end for
Consequently, GLISSADE makes at most 4 ( L 1 R ) 6 / 5 4(L_1R)^{6/5} 4 ( L 1 R ) 6/5 steps, all its points remain in the ball B ( z ∗ , R ) B(z^*, R) B ( z ∗ , R ) , and the point s s s at which the second stage starts satisfies the inequalities
∥ s − z ∗ ∥ ≤ R , \lVert s - z^*\rVert\le R, ∥ s − z ∗ ∥ ≤ R ,
∥ s − z 0 ∥ ≤ 2 R , \lVert s - z_0\rVert\le2R, ∥ s − z 0 ∥ ≤ 2 R ,
∥ F ( s ) ∥ ≤ 2 L 0 R ( e ( L 1 R ) 2 / 5 − 1 ) ( L 1 R ) 2 / 5 . (6) \lVert F(s)\rVert\le2L_0R\frac{\left(e^{(L_1R)^{2/5}} - 1\right)}{(L_1R)^{2/5}}. \tag*{(6)} ∥ F ( s )∥ ≤ 2 L 0 R ( L 1 R ) 2/5 ( e ( L 1 R ) 2/5 − 1 ) . (6)
If L 1 R < 1 L_1R < 1 L 1 R < 1 , the first stage is skipped and s = z 0 s = z_0 s = z 0 .
Second stage: the method BELAY
In the method BELAY, at each iteration the anchor u k u_k u k is shifted by λ k F ( y k ) / 6 \lambda_kF(y_k)/6 λ k F ( y k ) /6 in the direction − F ( y k ) -F(y_k) − F ( y k ) , and the extragradient step is made from the point v k v_k v k , which is a convex combination of the anchor u k − 1 u_{k-1} u k − 1 and the previous point y k − 1 y_{k-1} y k − 1 with the weight α k \alpha_k α k . The analysis relies on two cumulative bounds. The first one is the bound for the Lyapunov function
⟨ u k − y k , F ( y k ) ⟩ − Λ k 3 ∥ F ( y k ) ∥ 2 \langle u_k - y_k, F(y_k)\rangle- \frac{\Lambda_k}{3}\lVert F(y_k)\rVert^2 ⟨ u k − y k , F ( y k )⟩ − 3 Λ k ∥ F ( y k ) ∥ 2
from Sun et al. [26 ] . It controls the norm of the operator via the distance from the anchor to the solution. The second bound controls the distance ∥ u k − y k ∥ \lVert u_k - y_k\rVert ∥ u k − y k ∥ from the current point to the anchor. It is this bound that allows us to choose the stepsize from the computable quantity B k B_k B k , which bounds the length of the trial step: ∥ x k − y k − 1 ∥ ≤ λ k B k \lVert x_k - y_{k-1}\rVert\le\lambda_kB_k ∥ x k − y k − 1 ∥ ≤ λ k B k .
Lemma 3.2 (two cumulative bounds). ▼ proof in Appendix § 8 .§ 2
Let the points of Algorithm 2 be constructed with arbitrary λ k > 0 \lambda_k > 0 λ k > 0 such that λ k ≤ 4 λ k − 1 \lambda_k \le4\lambda_{k-1} λ k ≤ 4 λ k − 1 for k ≥ 2 k \ge2 k ≥ 2 , and let ∥ s − z ∗ ∥ ≤ R \lVert s-z^*\rVert\le R ∥ s − z ∗ ∥ ≤ R . If for all i ≤ k i \le k i ≤ k
λ i ∥ F ( x i ) − F ( y i ) ∥ ≤ 1 4 ∥ x i − y i ∥ , (7) \lambda_i\lVert F(x_i)-F(y_i)\rVert\le\frac{1}{4}\lVert x_i-y_i\rVert, \tag*{(7)} λ i ∥ F ( x i ) − F ( y i )∥ ≤ 4 1 ∥ x i − y i ∥ , (7) then
∥ u k − z ∗ ∥ ≤ R , \lVert u_k-z^*\rVert\le R, ∥ u k − z ∗ ∥ ≤ R , ∥ F ( y k ) ∥ ≤ 3 R λ k , \lVert F(y_k)\rVert\le\frac{3R}{\lambda_k}, ∥ F ( y k )∥ ≤ λ k 3 R , ∑ i = 1 k λ i Λ i ∥ F ( y i ) ∥ 2 ≤ 9 R 2 , \sum_{i=1}^{k}\lambda_i\Lambda_i\lVert F(y_i)\rVert^2 \le9R^2, i = 1 ∑ k λ i Λ i ∥ F ( y i ) ∥ 2 ≤ 9 R 2 , ∥ u k − y k ∥ 2 + 5 ∥ u k − z ∗ ∥ 2 + ∑ i = 1 k α i ∥ u i − 1 − y i − 1 ∥ 2 ≤ 37 3 R 2 . \lVert u_k-y_k\rVert^2+5\lVert u_k-z^*\rVert^2+\sum_{i=1}^{k}\alpha_i\lVert u_{i-1}-y_{i-1}\rVert^2\le\frac{37}{3}R^2. ∥ u k − y k ∥ 2 + 5 ∥ u k − z ∗ ∥ 2 + i = 1 ∑ k α i ∥ u i − 1 − y i − 1 ∥ 2 ≤ 3 37 R 2 .
Condition (7) is the usual stepsize condition of the extragradient method. The following proposition shows that the stepsizes of BELAY satisfy it and bounds the number of its iterations. The ratio λ k / λ 1 \lambda_k/\lambda_1 λ k / λ 1 is not bounded here: the stepsize may both increase and decrease, but by at most a factor of four per iteration.
Proposition 3.3 (number of iterations of the second stage). ▼ proof in Appendix § 8 .§ 3
Let ∥ s − z ∗ ∥ ≤ R \lVert s-z^*\rVert\le R ∥ s − z ∗ ∥ ≤ R and
H = log ( 18 L 0 R / ε + 1 ) ( L 0 + L 1 ∥ F ( s ) ∥ ) L 0 . \mathcal{H}=\log\frac{(18L_0R/\varepsilon+1)(L_0+L_1\lVert F(s)\rVert)}{L_0}. H = log L 0 ( 18 L 0 R / ε + 1 ) ( L 0 + L 1 ∥ F ( s )∥) . Then the stepsizes of Algorithm 2 started from the point s s s satisfy condition (7) , and the algorithm stops after K K K iterations, where
K ≤ 3 + 36 L 0 R ε + 330 L 1 R H + H . K\le3+\frac{36L_0R}{\varepsilon}+330L_1R\sqrt{\mathcal{H}}+\mathcal{H}. K ≤ 3 + ε 36 L 0 R + 330 L 1 R H + H . The output point satisfies ∥ F ( y K ) ∥ ≤ ε \lVert F(y_K)\rVert\le\varepsilon ∥ F ( y K )∥ ≤ ε and ∥ y K − z ∗ ∥ < 4 R \lVert y_K-z^*\rVert<4R ∥ y K − z ∗ ∥ < 4 R .
The quantity H \mathcal{H} H is the logarithm of the ratio of the largest stepsize that may be needed to the initial stepsize λ 1 \lambda_1 λ 1 . Without the first stage, it may be of order L 1 R L_1R L 1 R , and then the term L 1 R H L_1R\sqrt{\mathcal{H}} L 1 R H is of order ( L 1 R ) 3 / 2 (L_1R)^{3/2} ( L 1 R ) 3/2 . The first stage reduces ∥ F ( s ) ∥ \lVert F(s)\rVert ∥ F ( s )∥ to 2 L 0 R ( e ( L 1 R ) 2 / 5 − 1 ) / ( L 1 R ) 2 / 5 2L_0R(e^{(L_1R)^{2/5}}-1)/(L_1R)^{2/5} 2 L 0 R ( e ( L 1 R ) 2/5 − 1 ) / ( L 1 R ) 2/5 , and then H ≲ 1 + ( L 1 R ) 2 / 5 + log ( 2 + L 0 R / ε ) + log ( 2 + L 1 R ) \mathcal{H}\lesssim1+(L_1R)^{2/5}+\log(2+L_0R/\varepsilon)+\log(2+L_1R) H ≲ 1 + ( L 1 R ) 2/5 + log ( 2 + L 0 R / ε ) + log ( 2 + L 1 R ) .
The final bound
Let us explain the choice of the step length at the first stage. Lemma 3.1 and its proof remain valid if ( L 1 R ) 2 / 5 (L_1R)^{2/5} ( L 1 R ) 2/5 is replaced by any number b ∈ [ 1 , L 1 R ] b\in[1,L_1R] b ∈ [ 1 , L 1 R ] : a step of length b / ( 2 L 1 ) b/(2L_1) b / ( 2 L 1 ) made when ∥ F ( x ) ∥ > 2 L 0 R ( e b − 1 ) / b \lVert F(x)\rVert>2L_0R(e^b-1)/b ∥ F ( x )∥ > 2 L 0 R ( e b − 1 ) / b reduces the squared distance to the solution by b 2 / ( 4 L 1 2 ) b^2/(4L_1^2) b 2 / ( 4 L 1 2 ) . Then the first stage costs at most 4 ( L 1 R ) 2 / b 2 4(L_1R)^2/b^2 4 ( L 1 R ) 2 / b 2 oracle calls. After it, H ≲ 1 + b + log ( 2 + L 0 R / ε ) + log ( 2 + L 1 R ) \mathcal{H}\lesssim1+b+\log(2+L_0R/\varepsilon)+\log(2+L_1R) H ≲ 1 + b + log ( 2 + L 0 R / ε ) + log ( 2 + L 1 R ) , and by Proposition 3.3 the second stage costs of order L 0 R / ε + L 1 R b L_0R/\varepsilon+L_1R\sqrt{b} L 0 R / ε + L 1 R b up to lower-order terms. The first quantity decreases in b b b , the second one increases, and for b = ( L 1 R ) 2 / 5 b=(L_1R)^{2/5} b = ( L 1 R ) 2/5 both are equal to ( L 1 R ) 6 / 5 (L_1R)^{6/5} ( L 1 R ) 6/5 .
Theorem 3.4 (upper bound). ▼ proof in Appendix § 8 .§ 4 The method ABSEIL outputs a point z ^ \hat{z} z ^ such that ∥ F ( z ^ ) ∥ ≤ ε \lVert F(\hat{z})\rVert\le\varepsilon ∥ F ( z ^ )∥ ≤ ε and ∥ z ^ − z 0 ∥ < 5 R \lVert\hat{z}-z_0\rVert< 5R ∥ z ^ − z 0 ∥ < 5 R after
O ( 1 + L 0 R ε + ( L 1 R ) 6 / 5 ) O\left(1+\frac{L_0R}{\varepsilon}+(L_1R)^{6/5}\right) O ( 1 + ε L 0 R + ( L 1 R ) 6/5 ) oracle calls. If it is run with the accuracy ε = η / ( 6 R ) \varepsilon=\eta/(6R) ε = η / ( 6 R ) , then Gap R ( z ^ ) ≤ η \operatorname{Gap}_R(\hat{z})\le\eta Gap R ( z ^ ) ≤ η , and the number of oracle calls is O ( 1 + L 0 R 2 / η + ( L 1 R ) 6 / 5 ) O(1+L_0R^2/\eta+(L_1R)^{6/5}) O ( 1 + L 0 R 2 / η + ( L 1 R ) 6/5 ) .
The method uses no projections, no line search, and no auxiliary subproblems. Every computed stepsize is accepted, and all oracle calls, including the evaluation of the operator at the output point, are counted in the bound. Theorem 4.12 shows that the exponent 6 / 5 6/5 6/5 cannot be decreased.
Lower bounds
In the model of Definition 2.7 , the algorithm queries values F ( u ) F(u) F ( u ) and must find a point where F F F is almost zero. For the lower bound, we construct an operator whose answers for a long time do not give enough information to find such a point with probability at least 2 / 3 2/3 2/3 .
For L 0 R / ε ≥ 1 L_0R/\varepsilon\ge1 L 0 R / ε ≥ 1 , the complexity in the paper has two different sources:
1 + T ∗ ( ε ) ≳ 1 + L 0 R ε + ( L 1 R ) 6 / 5 log 4 / 5 ( 2 + L 1 R ) . 1+T^*(\varepsilon)\gtrsim1+\frac{L_0R}{\varepsilon}+\frac{(L_1R)^{6/5}}{\log^{4/5}(2+L_1R)}. 1 + T ∗ ( ε ) ≳ 1 + ε L 0 R + log 4/5 ( 2 + L 1 R ) ( L 1 R ) 6/5 .
We first construct a chain and explain the origin of the nonlinear term. We then transfer the bound to the Minty gap, obtain the linear term, and consider a bounded set.
All constructed operators have a zero inside the ball of radius R R R (§ 4.4 ), that is, the problems are solvable in the sense of Assumption 2.3 . The difficulty in the lower bound comes not from the absence of a solution but from the fact that it cannot be found for a long time.
The worst-case operator must satisfy three requirements.
The operator has a solution z ∗ z^* z ∗ , F ( z ∗ ) = 0 F(z^*)=0 F ( z ∗ ) = 0 , with ∥ z ∗ ∥ ≤ R \lVert z^*\rVert\le R ∥ z ∗ ∥ ≤ R .
The operator is monotone: ⟨ F ( u ) − F ( u ′ ) , u − u ′ ⟩ ≥ 0 \langle F(u)-F(u'),u-u'\rangle\ge0 ⟨ F ( u ) − F ( u ′ ) , u − u ′ ⟩ ≥ 0 .
The operator is ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -Lipschitz in the sense of (1) . By Lemma 2.4 , for a smooth operator this is equivalent to ∥ D F ( u ) ∥ ≤ L 0 + L 1 ∥ F ( u ) ∥ \lVert DF(u)\rVert\le L_0+L_1\lVert F(u)\rVert ∥ D F ( u )∥ ≤ L 0 + L 1 ∥ F ( u )∥ , that is, the Jacobian norm may be large where the norm of the operator is large.
We distinguish two spaces: u u u is a query of the algorithm, and v = Φ ( u ) v=\Phi(u) v = Φ ( u ) is the oracle answer. We will restrict the geometry of the answers v v v , although the algorithm chooses the queries u u u freely.
The worst-case operator is chosen before the random decisions of the algorithm. The success requirement is probability at least 2 / 3 2/3 2/3 on every operator of the class. The complexity T ∗ T^* T ∗ is measured by the worst-case expected number of queries, and the dimension is unbounded.
Throughout this section, we move the starting point to the origin, that is, we set z 0 = 0 z_0=0 z 0 = 0 .
What the chain must hide
We construct an operator whose answers reveal coordinates only one at a time: if the query does not yet use the coordinates after k k k , the answer can reveal at most coordinate k + 1 k+1 k + 1 . This is a property of the constructed operator, not a restriction on the algorithm. The queries u u u remain arbitrary, and against arbitrary randomized algorithms the property is transferred by the random embedding of § 4.6 .
Let θ > 0 \theta> 0 θ > 0 be a smallness threshold. After choosing the parameters, we want to obtain
∣ u i ∣ ≤ θ for i ≥ j ⟹ Φ i ( u ) = 0 for i > j , |u_i| \le\theta\text{ for } i \ge j \quad\Longrightarrow\quad\Phi_i(u) = 0 \text{ for } i > j, ∣ u i ∣ ≤ θ for i ≥ j ⟹ Φ i ( u ) = 0 for i > j ,
∣ u n ∣ ≤ θ ⟹ ∥ Φ ( u ) ∥ > 2 ε . |u_n| \le\theta\quad\Longrightarrow\quad\lVert\Phi(u) \rVert> 2\varepsilon. ∣ u n ∣ ≤ θ ⟹ ∥ Φ ( u )∥ > 2 ε .
Moreover, the values of the nonzero coordinates of the answer must also depend only on u 1 , … , u j u_1,\ldots,u_j u 1 , … , u j .
Thus, the chain must have two properties. First, each answer reveals at most one new coordinate. Second, as long as the last coordinate is not revealed, the norm of the answer is greater than 2 ε 2\varepsilon 2 ε . In § 4.2 , we construct an operator with the second property, and in Section 4.3 we verify the first.
Geometry of the answers and the inverse operator
Weighted simplex
Let G 1 ≥ ⋯ ≥ G n > 0 G_1 \ge\cdots\ge G_n > 0 G 1 ≥ ⋯ ≥ G n > 0 . We force all answers to lie in the weighted simplex
K = { v ≥ 0 : ∑ i = 1 n v i G i ≤ 1 } . K = \left\{v \ge0 : \sum_{i=1}^{n} \frac{v_i}{G_i} \le1\right\}. K = { v ≥ 0 : i = 1 ∑ n G i v i ≤ 1 } .
This is the convex hull of 0 , G 1 e 1 , … , G n e n 0,G_1e_1,\ldots,G_ne_n 0 , G 1 e 1 , … , G n e n . Zero belongs to this simplex but not to its outer face ∑ i v i / G i = 1 \sum_i v_i/G_i = 1 ∑ i v i / G i = 1 .
Lemma 4.1 (outer face). If v ≥ 0 v \ge0 v ≥ 0 and ∑ i v i / G i = 1 \sum_i v_i/G_i = 1 ∑ i v i / G i = 1 , then ∥ v ∥ ≥ G n / n \lVert v \rVert\ge G_n/\sqrt{n} ∥ v ∥ ≥ G n / n .
Indeed,
1 = ∑ i v i G i ≤ 1 G n ∑ i v i ≤ n G n ∥ v ∥ . 1 = \sum_i \frac{v_i}{G_i} \le\frac{1}{G_n}\sum_i v_i \le\frac{\sqrt{n}}{G_n}\lVert v\rVert. 1 = i ∑ G i v i ≤ G n 1 i ∑ v i ≤ G n n ∥ v ∥ .
The task is now concrete: as long as u n u_n u n is small, we must keep the answer v v v on the outer face of the simplex.
Inverse operator
In the first part of the series [23 ] , the worst-case functions were constructed via conjugation. Here we use an analogous technique of inverting a monotone operator. It is hard to give an explicit formula v = Φ ( u ) v = \Phi(u) v = Φ ( u ) with all the required properties. It is more convenient to describe, for each admissible answer v ∈ K v \in K v ∈ K , the queries u u u for which the oracle returns this answer:
u + σ ∈ ∂ ( Q + I K ) ( v ) + B v . (8) u + \sigma\in\partial(Q + I_K)(v) + Bv. \tag*{(8)} u + σ ∈ ∂ ( Q + I K ) ( v ) + B v . (8)
Here Q Q Q is convex, B T = − B B^{\mathsf{T}} = -B B T = − B , σ \sigma σ is a shift, and I K I_K I K is the indicator function of the set K K K : I K = 0 I_K = 0 I K = 0 on K K K and I K = + ∞ I_K = +\infty I K = + ∞ outside K K K .
We denote the ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -Lipschitz constants of the intermediate operator by ℓ 0 , ℓ 1 > 0 \ell_0,\ell_1 > 0 ℓ 0 , ℓ 1 > 0 . At the end, we choose them based on L 0 , L 1 L_0,L_1 L 0 , L 1 .
At a smooth point, (8) means u + σ = ∇ Q ( v ) + B v + y u+\sigma= \nabla Q(v)+Bv+y u + σ = ∇ Q ( v ) + B v + y with y ∈ N K ( v ) y \in N_K(v) y ∈ N K ( v ) . The normal cone N K ( v ) N_K(v) N K ( v ) consists of the y y y for which ⟨ y , w − v ⟩ ≤ 0 \langle y,w-v\rangle\le0 ⟨ y , w − v ⟩ ≤ 0 for all w ∈ K w \in K w ∈ K : these are the outer normals to the feasible directions. In the interior of K K K , only y = 0 y=0 y = 0 remains, and additional normals appear on the boundary.
The function Q
For v ≥ 0 v \ge0 v ≥ 0 , v ≠ 0 v \ne0 v = 0 , set s = ∑ i v i s = \sum_i v_i s = ∑ i v i . Define Q Q Q as
Q ( v ) = 2 ℓ 1 ∫ 0 s log ( 1 + ℓ 1 t ℓ 0 ) d t + 4 ℓ 1 ∥ v ∥ log n ∥ v ∥ s , (9) Q(v) = \frac{2}{\ell_1}\int_0^s \log\left(1+\frac{\ell_1 t}{\ell_0}\right)\,\mathrm{d}t + \frac{4}{\ell_1}\lVert v\rVert\log\frac{\sqrt{n}\lVert v\rVert}{s}, \tag*{(9)} Q ( v ) = ℓ 1 2 ∫ 0 s log ( 1 + ℓ 0 ℓ 1 t ) d t + ℓ 1 4 ∥ v ∥ log s n ∥ v ∥ , (9)
and Q ( 0 ) = 0 Q(0)=0 Q ( 0 ) = 0 .
Decompose ξ ∈ R n \xi\in\mathbb{R}^n ξ ∈ R n as ξ = α v / s + ξ ⊥ \xi= \alpha v/s + \xi_\perp ξ = α v / s + ξ ⊥ , where α = 1 T ξ \alpha= \mathbf{1}^{\mathsf{T}}\xi α = 1 T ξ and 1 T ξ ⊥ = 0 \mathbf{1}^{\mathsf{T}}\xi_\perp= 0 1 T ξ ⊥ = 0 . The computation in Appendix § 9 .§ 1 gives
D 2 Q ( v ) [ ξ , ξ ] ≥ 2 α 2 ℓ 0 + ℓ 1 s + 4 ∥ ξ ⊥ ∥ 2 ℓ 1 ∥ v ∥ ≥ ∥ ξ ∥ 2 ℓ 0 + ℓ 1 ∥ v ∥ . D^2Q(v)[\xi,\xi] \ge\frac{2\alpha^2}{\ell_0+\ell_1s}+\frac{4\lVert\xi_\perp\rVert^2}{\ell_1\lVert v\rVert} \ge\frac{\lVert\xi\rVert^2}{\ell_0+\ell_1\lVert v\rVert}. D 2 Q ( v ) [ ξ , ξ ] ≥ ℓ 0 + ℓ 1 s 2 α 2 + ℓ 1 ∥ v ∥ 4 ∥ ξ ⊥ ∥ 2 ≥ ℓ 0 + ℓ 1 ∥ v ∥ ∥ ξ ∥ 2 .
Integration along a segment turns this bound into generalized strong monotonicity of the subdifferential: for a ∈ ∂ ( Q + I K ) ( v ) a \in\partial(Q+I_K)(v) a ∈ ∂ ( Q + I K ) ( v ) and a ′ ∈ ∂ ( Q + I K ) ( v ′ ) a' \in\partial(Q+I_K)(v') a ′ ∈ ∂ ( Q + I K ) ( v ′ ) ,
⟨ a − a ′ , v − v ′ ⟩ ≥ ∥ v − v ′ ∥ 2 ℓ 0 + ℓ 1 max { ∥ v ∥ , ∥ v ′ ∥ } . \langle a-a',v-v'\rangle\ge\frac{\lVert v-v'\rVert^2}{\ell_0+\ell_1\max\{\lVert v\rVert,\lVert v'\rVert\}}. ⟨ a − a ′ , v − v ′ ⟩ ≥ ℓ 0 + ℓ 1 max {∥ v ∥ , ∥ v ′ ∥} ∥ v − v ′ ∥ 2 .
The skew-symmetric B B B does not change it, since ⟨ B h , h ⟩ = 0 \langle Bh,h\rangle= 0 ⟨ B h , h ⟩ = 0 . After inversion, it yields monotonicity and ( ℓ 0 , ℓ 1 ) (\ell_0,\ell_1) ( ℓ 0 , ℓ 1 ) -Lipschitz continuity of Φ \Phi Φ .
The order of the coordinates is set by the matrix B B B and the shift σ \sigma σ .
Blocks
Let H ≥ 2 H \ge2 H ≥ 2 and m ≥ 1 m \ge1 m ≥ 1 be integers. We split the n = H m n=Hm n = H m coordinates into H H H consecutive blocks of m m m . Denote by bl ( i ) \operatorname{bl}(i) bl ( i ) the index of the block of coordinate i i i , and by pos ( i ) \operatorname{pos}(i) pos ( i ) its index within the block. Within a block the weight is the same, and between blocks it decreases geometrically:
G i = ℓ 0 ℓ 1 n 3 e H − bl ( i ) . G_i=\frac{\ell_0}{\ell_1}n^3 e^{H-\operatorname{bl}(i)}. G i = ℓ 1 ℓ 0 n 3 e H − bl ( i ) .
The large G n = ( ℓ 0 / ℓ 1 ) n 3 G_n=(\ell_0/\ell_1)n^3 G n = ( ℓ 0 / ℓ 1 ) n 3 ensures a large error even on the last block. The geometric decrease in the weights allows us to enforce the order in which the blocks are revealed.
The matrix B B B is defined as follows:
B i j = { 5 m log ( e n ) ℓ 1 G i sign ( i − j ) , bl ( i ) = bl ( j ) , 0 , bl ( i ) ≠ bl ( j ) . B_{ij} =
\begin{cases}
\frac{5\sqrt{m}\log(e\sqrt{n})}{\ell_1G_i}\operatorname{sign}(i-j), & \operatorname{bl}(i)=\operatorname{bl}(j),\\
0, & \operatorname{bl}(i)\ne\operatorname{bl}(j).
\end{cases} B ij = { ℓ 1 G i 5 m l o g ( e n ) sign ( i − j ) , 0 , bl ( i ) = bl ( j ) , bl ( i ) = bl ( j ) .
Since G i = G j G_i=G_j G i = G j within a block, the matrix is skew-symmetric.
Below we choose a shift σ i \sigma_i σ i that decreases within a block. The matrix B B B links the coordinates within a block. The decrease of σ i \sigma_i σ i gives an advantage to the earlier coordinate. The different weights G i G_i G i forbid transitions between blocks. The blocks are needed so that the cost of the internal order depends on m \sqrt{m} m rather than on n \sqrt{n} n .
Why the chain is revealed one coordinate at a time
For v ∈ K v \in K v ∈ K , v ≠ 0 v \ne0 v = 0 , differentiating Q Q Q gives ∇ i Q ( v ) = ϑ ( v ) + γ ( v ) v i \nabla_i Q(v) = \vartheta(v) + \gamma(v)v_i ∇ i Q ( v ) = ϑ ( v ) + γ ( v ) v i , where
ϑ = 2 ℓ 1 log ( 1 + ℓ 1 s ℓ 0 ) − 4 ∥ v ∥ ℓ 1 s , γ = 4 ℓ 1 ∥ v ∥ ( 1 + log n ∥ v ∥ s ) . (10) \vartheta= \frac{2}{\ell_1}\log\left(1+\frac{\ell_1s}{\ell_0}\right)-\frac{4\|v\|}{\ell_1s},
\qquad
\gamma= \frac{4}{\ell_1\|v\|}\left(1+\log\frac{\sqrt{n}\|v\|}{s}\right). \tag*{(10)} ϑ = ℓ 1 2 log ( 1 + ℓ 0 ℓ 1 s ) − ℓ 1 s 4∥ v ∥ , γ = ℓ 1 ∥ v ∥ 4 ( 1 + log s n ∥ v ∥ ) . (10)
The common term ϑ \vartheta ϑ is the same for all coordinates. On K K K , we have ∥ v ∥ ≤ s ≤ G 1 \|v\| \le s \le G_1 ∥ v ∥ ≤ s ≤ G 1 and 1 ≤ n ∥ v ∥ / s ≤ n 1 \le\sqrt{n}\|v\|/s \le\sqrt{n} 1 ≤ n ∥ v ∥/ s ≤ n . Therefore, ϑ ≤ A \vartheta\le A ϑ ≤ A , γ v i + ( B v ) i ≤ C \gamma v_i + (Bv)_i \le C γ v i + ( B v ) i ≤ C , and
0 ≤ γ ≤ 4 log ( e n ) ℓ 1 ∥ v ∥ . (11) 0 \le\gamma\le\frac{4\log(e\sqrt{n})}{\ell_1\|v\|}. \tag*{(11)} 0 ≤ γ ≤ ℓ 1 ∥ v ∥ 4 log ( e n ) . (11)
where
A = 2 ℓ 1 log ( 1 + n 3 e H − 1 ) , C = ( 5 m + 4 ) log ( e n ) ℓ 1 . (12) A = \frac{2}{\ell_1}\log(1+n^3e^{H-1}),
\qquad
C = \frac{(5\sqrt{m}+4)\log(e\sqrt{n})}{\ell_1}. \tag*{(12)} A = ℓ 1 2 log ( 1 + n 3 e H − 1 ) , C = ℓ 1 ( 5 m + 4 ) log ( e n ) . (12)
The derivation of these bounds is given in Appendix § 9 .§ 1 . The smallness threshold equals δ = 1 / ( 4 ℓ 1 m ) \delta= 1/(4\ell_1\sqrt{m}) δ = 1/ ( 4 ℓ 1 m ) , and the shift is σ i = A + 2 C + 4 ( m − pos ( i ) ) δ \sigma_i = A + 2C + 4(m-\operatorname{pos}(i))\delta σ i = A + 2 C + 4 ( m − pos ( i )) δ .
Lemma 4.3 (membership in the class). ▼ proof in Appendix C.1
For each u ∈ R n u \in\mathbb{R}^n u ∈ R n , inclusion (8) has a unique solution v = Φ ( u ) ∈ K v = \Phi(u) \in K v = Φ ( u ) ∈ K . The operator Φ \Phi Φ is monotone, satisfies condition (1) with constants ℓ 0 , ℓ 1 \ell_0,\ell_1 ℓ 0 , ℓ 1 , ∥ Φ ( u ) ∥ ≤ G 1 \|\Phi(u)\| \le G_1 ∥Φ ( u ) ∥ ≤ G 1 for all u u u , and Φ ( − σ ) = 0 \Phi(-\sigma)=0 Φ ( − σ ) = 0 .
Lemma 4.4 (revealing one coordinate at a time). ▼ proof in Appendix C.2
For any u ∈ R n u \in\mathbb{R}^n u ∈ R n , the following properties hold.
(a) If ∣ u n ∣ ≤ δ |u_n| \le\delta ∣ u n ∣ ≤ δ , then ∑ i Φ i ( u ) / G i = 1 \sum_i \Phi_i(u)/G_i = 1 ∑ i Φ i ( u ) / G i = 1 and ∥ Φ ( u ) ∥ ≥ G n / n \|\Phi(u)\| \ge G_n/\sqrt{n} ∥Φ ( u ) ∥ ≥ G n / n .
(b) If ∣ u i ∣ ≤ δ |u_i| \le\delta ∣ u i ∣ ≤ δ for all i ≥ j i \ge j i ≥ j , then Φ i ( u ) = 0 \Phi_i(u)=0 Φ i ( u ) = 0 for i > j i>j i > j , and Φ ( u ) \Phi(u) Φ ( u ) depends only on u 1 , … , u j u_1,\ldots,u_j u 1 , … , u j . In particular, if ∣ u i ∣ ≤ δ |u_i| \le\delta ∣ u i ∣ ≤ δ for all i i i , then Φ ( u ) = G 1 e 1 \Phi(u)=G_1e_1 Φ ( u ) = G 1 e 1 .
How the radius determines the chain length
The zero of the constructed operator is located at u ∗ = − σ u^*=-\sigma u ∗ = − σ : there v = 0 v=0 v = 0 solves the inclusion, since Q ≥ Q ( 0 ) = 0 Q \ge Q(0)=0 Q ≥ Q ( 0 ) = 0 . Hence, we need to fit σ \sigma σ into the ball of radius R R R .
Each coordinate of the shift is of order ℓ 1 σ i = Θ ( H + m log n ) \ell_1\sigma_i = \Theta(H+\sqrt{m}\log n) ℓ 1 σ i = Θ ( H + m log n ) . The term H H H comes from log G 1 \log G_1 log G 1 : the first answers are exponentially large in the number of blocks. There are n n n coordinates, so
ℓ 1 ∥ σ ∥ = Θ ( H n ⏟ many blocks + n log n H ⏟ many coordinates per block ) . \ell_1\|\sigma\| = \Theta\left(
\underbrace{H\sqrt{n}}_{\text{many blocks}}
+
\underbrace{\frac{n\log n}{\sqrt{H}}}_{\text{many coordinates per block}}
\right). ℓ 1 ∥ σ ∥ = Θ many blocks H n + many coordinates per block H n log n .
We choose m = h 2 m=h^2 m = h 2 , H = ⌈ h log ( 4 h ) ⌉ H=\lceil h\log(4h)\rceil H = ⌈ h log ( 4 h )⌉ , and the largest admissible h h h . Then n = Θ ( h 3 log h ) n=\Theta(h^3\log h) n = Θ ( h 3 log h ) and ℓ 1 R = Θ ( h 5 / 2 log 3 / 2 h ) \ell_1R=\Theta(h^{5/2}\log^{3/2}h) ℓ 1 R = Θ ( h 5/2 log 3/2 h ) . Hence ( ℓ 1 R ) 6 / 5 = Θ ( h 3 log 9 / 5 h ) (\ell_1R)^{6/5}=\Theta(h^3\log^{9/5}h) ( ℓ 1 R ) 6/5 = Θ ( h 3 log 9/5 h ) , so
n = Θ ( ( ℓ 1 R ) 6 / 5 log 4 / 5 ( 2 + ℓ 1 R ) ) . n=\Theta\left(\frac{(\ell_1R)^{6/5}}{\log^{4/5}(2+\ell_1R)}\right). n = Θ ( log 4/5 ( 2 + ℓ 1 R ) ( ℓ 1 R ) 6/5 ) .
Next, we make the construction smooth and bound the useful radius of the queries.
Smoothing preserves the chain
The resulting Φ \Phi Φ is Lipschitz but not necessarily twice differentiable. We take a very small ball of radius ρ \rho ρ and average the values over it:
Φ ρ ( u ) = ∫ Φ ( u − y ) k ρ ( y ) d y , \Phi_{\rho}(u)=\int\Phi(u-y)k_{\rho}(y)\,dy, Φ ρ ( u ) = ∫ Φ ( u − y ) k ρ ( y ) d y ,
where k ρ ≥ 0 k_{\rho} \ge0 k ρ ≥ 0 , the integral of the kernel equals 1, and the kernel itself is smooth.
Lemma 4.5 (smoothing). ▼ proof in Appendix § 9 .§ 4
Let the support of the kernel k ρ ∈ C ∞ k_{\rho} \in C^{\infty} k ρ ∈ C ∞ lie in the ball of radius
0 < ρ ≤ min { δ 2 , ℓ 0 2 ℓ 1 ( ℓ 0 + ℓ 1 G 1 ) , G n 2 ℓ 1 ( G 1 + G n ) , R 16 n } . (13) 0 < \rho\le\min\left\{\frac{\delta}{2},\frac{\ell_{0}}{2\ell_{1}(\ell_{0}+\ell_{1}G_{1})},\frac{G_{n}}{2\ell_{1}(G_{1}+G_{n})},\frac{R}{16\sqrt{n}}\right\}. \tag*{(13)} 0 < ρ ≤ min { 2 δ , 2 ℓ 1 ( ℓ 0 + ℓ 1 G 1 ) ℓ 0 , 2 ℓ 1 ( G 1 + G n ) G n , 16 n R } . (13) Then Φ ρ ∈ C ∞ \Phi_{\rho} \in C^{\infty} Φ ρ ∈ C ∞ is monotone, satisfies condition (1) with constants 2 ℓ 0 2\ell_{0} 2 ℓ 0 , ℓ 1 \ell_{1} ℓ 1 , ∥ Φ ρ ∥ ≤ G 1 \lVert\Phi_{\rho}\rVert\le G_{1} ∥ Φ ρ ∥ ≤ G 1 , and Φ ρ ( − σ − ρ 1 ) = 0 \Phi_{\rho}(-\sigma-\rho\mathbf{1})=0 Φ ρ ( − σ − ρ 1 ) = 0 . The statements of Lemma 4.4 hold for Φ ρ \Phi_{\rho} Φ ρ with the threshold θ = δ / 2 \theta=\delta/2 θ = δ /2 instead of δ \delta δ .
The face of the simplex is given by a linear equation, so an average of answers lying on the face also lies on it. Averaging the norm inequality itself would not be possible: large vectors can cancel out.
Coordinate hiding
Hiding the coordinates
If we hide the coordinates without additional protection, the algorithm may query a vector all of whose coordinates are greater than θ \theta θ . Then the chain condition does not apply.
Coordinates were hidden under a bounded norm of the queries by Woodworth and Srebro [29 ] and Carmon et al. [2 ] . Here we additionally need to preserve ( L 0 , L 1 ) (L_{0},L_{1}) ( L 0 , L 1 ) -Lipschitz continuity with constants that do not depend on the magnitude of the operator. To this end, we multiply the operator by a smooth approximation of the indicator of the segment [ 0 , 1 ] [0,1] [ 0 , 1 ] , for example,
χ ( t ) = { 1 , t ≤ 1 , 1 − 10 ( t − 1 ) 3 + 15 ( t − 1 ) 4 − 6 ( t − 1 ) 5 , 1 < t < 2 , 0 , t ≥ 2. \chi(t)=
\begin{cases}
1, & t\le1,\\
1-10(t-1)^{3}+15(t-1)^{4}-6(t-1)^{5}, & 1<t<2,\\
0, & t\ge2.
\end{cases} χ ( t ) = ⎩ ⎨ ⎧ 1 , 1 − 10 ( t − 1 ) 3 + 15 ( t − 1 ) 4 − 6 ( t − 1 ) 5 , 0 , t ≤ 1 , 1 < t < 2 , t ≥ 2.
This function is twice continuously differentiable, 0 ≤ χ ≤ 1 0\le\chi\le1 0 ≤ χ ≤ 1 , and ∣ χ ′ ∣ ≤ 15 / 8 |\chi'|\le15/8 ∣ χ ′ ∣ ≤ 15/8 .
Lemma 4.6. ▼ proof in Appendix § 9 .§ 5
Let F F F satisfy Assumptions 2.1 2.1 2.1 –2.3 2.3 2.3 with z 0 = 0 z_{0}=0 z 0 = 0 and ∥ F ( z ) ∥ ≤ M \lVert F(z)\rVert\le M ∥ F ( z )∥ ≤ M for all z z z . Let L = max { 4 R , 32 M / μ } L=\max\{4R,32M/\mu\} L = max { 4 R , 32 M / μ } and
0 < μ ≤ L 0 8 ( 1 + L 1 R ) . 0<\mu\le\frac{L_{0}}{8(1+L_{1}R)}. 0 < μ ≤ 8 ( 1 + L 1 R ) L 0 . Then the operator
F ~ ( z ) = χ ( ∥ z ∥ / L ) F ( z ) + μ z (14) \widetilde{F}(z)=\chi(\lVert z\rVert/L)F(z)+\mu z \tag*{(14)} F ( z ) = χ (∥ z ∥ / L ) F ( z ) + μ z (14) is μ / 2 \mu/2 μ /2 -strongly monotone, has a unique zero z μ ∗ z_{\mu}^{*} z μ ∗ with ∥ z μ ∗ ∥ ≤ ∥ z ∗ ∥ \lVert z_{\mu}^{*}\rVert\le\lVert z^{*}\rVert ∥ z μ ∗ ∥ ≤ ∥ z ∗ ∥ , and satisfies condition (1) with constants 2 L 0 2L_{0} 2 L 0 , 2 L 1 2L_{1} 2 L 1 . For ∥ z ∥ ≤ L \lVert z\rVert\le L ∥ z ∥ ≤ L it equals F ( z ) + μ z F(z)+\mu z F ( z ) + μ z , and for ∥ z ∥ ≥ 2 L \lVert z\rVert\ge2L ∥ z ∥ ≥ 2 L it equals the known operator μ z \mu z μ z . If F ∈ C 2 F\in C^{2} F ∈ C 2 , then also F ~ ∈ C 2 \widetilde{F}\in C^{2} F ∈ C 2 .
Lemma 4.7 (preservation of the success condition). ▼ proof in Appendix C.5
Let the conditions of Lemma 4.6 hold.
(a) If μ ≤ ε / ( 16 R ) \mu\le\varepsilon/(16R) μ ≤ ε / ( 16 R ) , M ≥ ε M \ge\varepsilon M ≥ ε , and ∥ F ~ ( z ) ∥ ≤ ε \lVert\widetilde{F}(z)\rVert\le\varepsilon ∥ F ( z )∥ ≤ ε , then ∥ z ∥ < L \lVert z\rVert< L ∥ z ∥ < L and ∥ F ( z ) ∥ ≤ 2 ε \lVert F(z)\rVert\le2\varepsilon ∥ F ( z )∥ ≤ 2 ε .
(b) If ∥ z ∗ ∥ ≤ R / 4 \lVert z^*\rVert\le R/4 ∥ z ∗ ∥ ≤ R /4 , μ ≤ η / ( 16 R 2 ) \mu\le\eta/(16R^2) μ ≤ η / ( 16 R 2 ) , M ≥ η / R M \ge\eta/R M ≥ η / R , and Gap R F ~ ( z ) ≤ η \operatorname{Gap}^{\widetilde{F}}_{R}(z) \le\eta Gap R F ( z ) ≤ η , then ∥ z ∥ ≤ L / 4 \lVert z\rVert\le L/4 ∥ z ∥ ≤ L /4 and Gap R F ( z ) < 4 η \operatorname{Gap}^{F}_{R}(z) < 4\eta Gap R F ( z ) < 4 η .
Random embedding
We choose in advance random distinct positions π ( 1 ) , … , π ( n ) \pi(1),\ldots,\pi(n) π ( 1 ) , … , π ( n ) among the d d d coordinates. The matrix U = ( e π ( 1 ) , … , e π ( n ) ) U=(e_{\pi(1)},\ldots,e_{\pi(n)}) U = ( e π ( 1 ) , … , e π ( n ) ) simply places the coordinates of the short chain at these positions: ( U T z ) i = z π ( i ) (U^{\mathsf{T}}z)_i=z_{\pi(i)} ( U T z ) i = z π ( i ) . The full operator has the form F U ( z ) = χ ( ∥ z ∥ / L ) U Φ ρ ( U T z ) + μ z F_U(z)=\chi(\lVert z\rVert/L)U\Phi_{\rho}(U^{\mathsf{T}}z)+\mu z F U ( z ) = χ (∥ z ∥ / L ) U Φ ρ ( U T z ) + μ z . The embedding preserves the norms of the chain vectors and monotonicity. For ∥ z ∥ ≥ 2 L \lVert z\rVert\ge2L ∥ z ∥ ≥ 2 L , the oracle answer μ z \mu z μ z does not depend on U U U at all.
Proposition 4.8 (random embedding). ▼ proof in Appendix C.6
Let n ≥ 2 n \ge2 n ≥ 2 , let the operator Φ : R n → R n \Phi:\mathbb{R}^{n}\to\mathbb{R}^{n} Φ : R n → R n satisfy Assumptions 2.1–2.3 with z 0 = 0 z_0=0 z 0 = 0 and ∥ Φ ( u ) ∥ ≤ M \lVert\Phi(u)\rVert\le M ∥ Φ ( u )∥ ≤ M for all u u u , and let the numbers μ \mu μ and L L L satisfy the conditions of Lemmas 4.6 and 4.7. Suppose that for some θ > 0 \theta>0 θ > 0
(a) if ∣ u i ∣ ≤ θ \lvert u_i\rvert\le\theta ∣ u i ∣ ≤ θ for all i ≥ j i\ge j i ≥ j , then Φ i ( u ) = 0 \Phi_i(u)=0 Φ i ( u ) = 0 for i > j i>j i > j , and Φ ( u ) \Phi(u) Φ ( u ) depends only on u 1 , … , u j u_1,\ldots,u_j u 1 , … , u j ,
(b) if ∣ u n ∣ ≤ θ \lvert u_n\rvert\le\theta ∣ u n ∣ ≤ θ , then ∥ Φ ( u ) ∥ > 2 ε \lVert\Phi(u)\rVert> 2\varepsilon ∥ Φ ( u )∥ > 2 ε (respectively, Gap R Φ ( u ) > 4 η \operatorname{Gap}^{\Phi}_{R}(u)>4\eta Gap R Φ ( u ) > 4 η ).
Let N = ⌊ n / 2 ⌋ N=\lfloor n/2\rfloor N = ⌊ n /2 ⌋ , d ≥ n + 48 ( N + 1 ) n L 2 / θ 2 d\ge n+48(N+1)nL^2/\theta^2 d ≥ n + 48 ( N + 1 ) n L 2 / θ 2 , and let U ∈ R d × n U\in\mathbb{R}^{d\times n} U ∈ R d × n be a random matrix whose columns are distinct standard basis vectors of R d \mathbb{R}^{d} R d chosen uniformly. Then the operators F U ( z ) = χ ( ∥ z ∥ / L ) U Φ ( U T z ) + μ z F_U(z)=\chi(\lVert z\rVert/L)U\Phi(U^{\mathsf{T}}z)+\mu z F U ( z ) = χ (∥ z ∥ / L ) U Φ ( U T z ) + μ z belong to P d \mathcal{P}_d P d with constants 2 L 0 , 2 L 1 2L_0,2L_1 2 L 0 , 2 L 1 . If an algorithm, on every operator F U F_U F U , outputs with probability at least 2 / 3 2/3 2/3 a point z ^ \widehat{z} z with ∥ F U ( z ^ ) ∥ ≤ ε \lVert F_U(\widehat{z})\rVert\le\varepsilon ∥ F U ( z )∥ ≤ ε (respectively, with Gap R F U ( z ^ ) ≤ η \operatorname{Gap}^{F_U}_{R}(\widehat{z})\le\eta Gap R F U ( z ) ≤ η ), then on one of the operators F U F_U F U it makes at least 7 ( N + 1 ) / 12 7(N+1)/12 7 ( N + 1 ) /12 oracle calls in expectation.
Choice of parameters and the lower bound for the norm
It remains to verify that, for the required n n n , the error is indeed greater than ε \varepsilon ε , the zero is close enough, and the ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -Lipschitz constants coincide with the original ones.
For L 1 = 0 L_1=0 L 1 = 0 there is no nonlinear term, so from now on L 1 > 0 L_1>0 L 1 > 0 . Let x = L 1 R x=L_1R x = L 1 R and q = L 0 R / ε ≥ 1 q=L_0R/\varepsilon\ge1 q = L 0 R / ε ≥ 1 . We choose ℓ 0 = L 0 / 4 \ell_0=L_0/4 ℓ 0 = L 0 /4 , ℓ 1 = L 1 / 2 \ell_1=L_1/2 ℓ 1 = L 1 /2 , m = h 2 m=h^2 m = h 2 , H = ⌊ h log ( 4 h ) ⌋ H=\lfloor h\log(4h)\rfloor H = ⌊ h log ( 4 h )⌋ , and n = m H n=mH n = m H , where h ≥ 256 h\ge256 h ≥ 256 is the largest integer such that
2048 h 5 / 2 log 3 / 2 ( 4 h ) ≤ x . (15) 2048h^{5/2}\log^{3/2}(4h)\le x. \tag*{(15)} 2048 h 5/2 log 3/2 ( 4 h ) ≤ x . (15)
If no such h h h exists, then x x x is bounded by an absolute constant and the nonlinear term is absorbed into the constant term 1 1 1 in 1 + T ∗ 1+T^* 1 + T ∗ . Lemma C.1 and the maximality of h h h give ∥ σ ∥ ≤ R / 8 \lVert\sigma\rVert\le R/8 ∥ σ ∥ ≤ R /8 , n 5 / 2 > 4 x n^{5/2}>4x n 5/2 > 4 x , and n 3 > 4 x 2 n^3>4x^2 n 3 > 4 x 2 . After smoothing, the zero moves by at most R / 16 R/16 R /16 . Hence, it remains within R / 4 R/4 R /4 .
When the last coordinate is small, the smoothed chain has norm
∥ Φ ρ ( u ) ∥ ≥ G n n = L 0 2 L 1 n 5 / 2 > 2 L 0 R ≥ 2 ε . \lVert\Phi_{\rho}(u)\rVert\ge\frac{G_n}{\sqrt{n}}=\frac{L_0}{2L_1}n^{5/2}>2L_0R\ge2\varepsilon. ∥ Φ ρ ( u )∥ ≥ n G n = 2 L 1 L 0 n 5/2 > 2 L 0 R ≥ 2 ε .
This is the required large error. We choose L = max { 4 R , 32 G 1 / μ } L=\max\{4R,32G_1/\mu\} L = max { 4 R , 32 G 1 / μ } ,
μ = L 0 64 ( 1 + q + x ) . \mu=\frac{L_0}{64(1+q+x)}. μ = 64 ( 1 + q + x ) L 0 .
and the dimension from Proposition 4.8. The conditions of Lemmas 4.6 and 4.7 hold, and the verification of the inequalities is given in Appendix C.3.
The ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -Lipschitz constants go through three stages:
( ℓ 0 , ℓ 1 ) → smoothing ( 2 ℓ 0 , ℓ 1 ) → coordinate hiding ( 4 ℓ 0 , 2 ℓ 1 ) = ( L 0 , L 1 ) . (\ell_0,\ell_1) \xrightarrow{\text{smoothing}} (2\ell_0,\ell_1) \xrightarrow{\text{coordinate hiding}} (4\ell_0,2\ell_1)=(L_0,L_1). ( ℓ 0 , ℓ 1 ) smoothing ( 2 ℓ 0 , ℓ 1 ) coordinate hiding ( 4 ℓ 0 , 2 ℓ 1 ) = ( L 0 , L 1 ) .
We have obtained admissible C 2 C^2 C 2 operators. For every algorithm, among them there is a worst-case operator with T ≳ n T \gtrsim n T ≳ n . Therefore,
1 + T ∗ ( ε ) ≳ 1 + ( L 1 R ) 6 / 5 log 4 / 5 ( 2 + L 1 R ) . 1+T^*(\varepsilon) \gtrsim1+\frac{(L_1R)^{6/5}}{\log^{4/5}(2+L_1R)}. 1 + T ∗ ( ε ) ≳ 1 + log 4/5 ( 2 + L 1 R ) ( L 1 R ) 6/5 .
The exponent 6 / 5 6/5 6/5 arises entirely from the radius constraint. Smoothing, hiding, and the probabilistic reduction change only absolute factors and the dimension.
Passing to the Minty gap
The gap equals Gap R ( u ) = sup ∥ w ∥ ≤ R ⟨ Φ ( w ) , u − w ⟩ \operatorname{Gap}_R(u)=\sup_{\lVert w\rVert\le R}\langle\Phi(w),u-w\rangle Gap R ( u ) = sup ∥ w ∥ ≤ R ⟨ Φ ( w ) , u − w ⟩ . To bound it from below, it suffices to substitute one suitable point w w w into the supremum.
We choose a query w w w whose answer is the last vertex of the simplex, G n e n G_ne_n G n e n . Then the inner product becomes one-dimensional: ⟨ Φ ( w ) , u − w ⟩ = G n ( u n − w n ) \langle\Phi(w),u-w\rangle=G_n(u_n-w_n) ⟨ Φ ( w ) , u − w ⟩ = G n ( u n − w n ) . It only remains to place w n w_n w n noticeably to the left of zero while u n u_n u n stays small. The definition of the inverse operator directly suggests the required query: to − σ + ∇ Q ( G n e n ) + G n B e n -\sigma+\nabla Q(G_ne_n)+G_nBe_n − σ + ∇ Q ( G n e n ) + G n B e n we add the outer normal e n / ℓ 1 e_n/\ell_1 e n / ℓ 1 at the vertex G n e n G_ne_n G n e n .
Lemma 4.9 (test point for the gap). ▼ proof in Appendix C.4
Let
w = − σ + ∇ Q ( G n e n ) + G n B e n + e n ℓ 1 , w=-\sigma+\nabla Q(G_ne_n)+G_nBe_n+\frac{e_n}{\ell_1}, w = − σ + ∇ Q ( G n e n ) + G n B e n + ℓ 1 e n , and let ρ \rho ρ satisfy (4.6). Then Φ ρ ( w ) = G n e n \Phi_\rho(w)=G_ne_n Φ ρ ( w ) = G n e n , w n ≤ − 3 / ℓ 1 w_n\le-3/\ell_1 w n ≤ − 3/ ℓ 1 , and ⟨ Φ ρ ( w ) , u − w ⟩ ≥ G n / ℓ 1 \langle\Phi_\rho(w),u-w\rangle\ge G_n/\ell_1 ⟨ Φ ρ ( w ) , u − w ⟩ ≥ G n / ℓ 1 for ∣ u n ∣ ≤ δ \lvert u_n\rvert\le\delta ∣ u n ∣ ≤ δ . With the parameters of Section 4.7, also ∥ w ∥ ≤ R / 8 \lVert w\rVert\le R/8 ∥ w ∥ ≤ R /8 .
Hence, for small u n u_n u n ,
Gap R Φ ρ ( u ) ≥ G n ℓ 1 = L 0 L 1 2 n 3 > 4 L 0 R 2 ≥ 4 η . \operatorname{Gap}^{\Phi_\rho}_R(u)\ge\frac{G_n}{\ell_1}=\frac{L_0}{L_1^2}n^3>4L_0R^2\ge4\eta. Gap R Φ ρ ( u ) ≥ ℓ 1 G n = L 1 2 L 0 n 3 > 4 L 0 R 2 ≥ 4 η .
Here we require L 0 R 2 / η ≥ 1 L_0R^2/\eta\ge1 L 0 R 2 / η ≥ 1 .
In the choice of μ \mu μ , we replace q q q by L 0 R 2 / η L_0R^2/\eta L 0 R 2 / η . Then the conditions of Lemma 4.7(b) hold, and the same random embedding gives the same cost of order n n n for the gap.
The final bound
Lipschitz operators belong to the class under consideration for any L 1 ≥ 0 L_1\ge0 L 1 ≥ 0 . For deterministic methods, lower bounds have long been known [18 ] . For our randomized model, we need the following fact: for symmetric A A A with spectrum in [ − κ , − 1 ] ∪ [ 1 , κ ] [-\kappa,-1]\cup[1,\kappa] [ − κ , − 1 ] ∪ [ 1 , κ ] , an arbitrary randomized solver with relative residual 1 / 2 1/2 1/2 requires 1 + T ≳ κ 1+T\gtrsim\kappa 1 + T ≳ κ matrix–vector multiplications in expectation.
Lemma 4.10 (solving linear systems). ▼ proof in Appendix C.7
Suppose that an algorithm using arbitrary adaptive multiplications v ↦ A v v \mapsto Av v ↦ A v , for every symmetric matrix A A A with spectrum in [ − κ , − 1 ] ∪ [ 1 , κ ] [-\kappa,-1] \cup[1,\kappa] [ − κ , − 1 ] ∪ [ 1 , κ ] and every vector b ≠ 0 b \ne0 b = 0 , almost surely stops and outputs x ^ \hat{x} x ^ with
Pr { ∥ A x ^ − b ∥ ≤ ∥ b ∥ / 2 } ≥ 2 3 . \Pr\{\|A\hat{x}-b\| \le\|b\|/2\} \ge\frac{2}{3}. Pr { ∥ A x ^ − b ∥ ≤ ∥ b ∥/2 } ≥ 3 2 . If T T T is the largest expected number of multiplications over A A A , b b b and the dimension, then
1 + T ≳ κ . 1+T \gtrsim\kappa. 1 + T ≳ κ .
The lemma follows from the result of Dereziński et al. [6 ] . The passage to success probability 2 / 3 2/3 2/3 and to a bound on the expected number of multiplications is proved in Appendix C.7.
We embed the system into a monotone problem. Take
F ( x , y ) = a ( A y , s b ∥ b ∥ − A x ) . F(x,y)=a\left(Ay,\frac{sb}{\|b\|}-Ax\right). F ( x , y ) = a ( A y , ∥ b ∥ s b − A x ) .
The two blocks with opposite signs give a skew-symmetric linear part. Therefore, F F F is monotone, ∥ D F ∥ = a ∥ A ∥ ≤ a κ \|DF\|=a\|A\|\le a\kappa ∥ D F ∥ = a ∥ A ∥ ≤ aκ , and its zero
z ∗ = ( s A − 1 b ∥ b ∥ , 0 ) z^*=\left(\frac{sA^{-1}b}{\|b\|},0\right) z ∗ = ( ∥ b ∥ s A − 1 b , 0 )
satisfies ∥ z ∗ ∥ ≤ s \|z^*\|\le s ∥ z ∗ ∥ ≤ s . Each query of F F F costs two multiplications by A A A .
For the norm, we choose a = 2 ε / R a=2\varepsilon/R a = 2 ε / R , s = R s=R s = R , and κ = L 0 R / ( 2 ε ) \kappa=L_0R/(2\varepsilon) κ = L 0 R / ( 2 ε ) . If ∥ F ( x , y ) ∥ ≤ ε \|F(x,y)\|\le\varepsilon ∥ F ( x , y ) ∥ ≤ ε , then
∥ ∥ b ∥ R A x − b ∥ ≤ ∥ b ∥ R ε a = ∥ b ∥ 2 . \left\|\frac{\|b\|}{R}Ax-b\right\|\le\frac{\|b\|}{R}\frac{\varepsilon}{a}=\frac{\|b\|}{2}. R ∥ b ∥ A x − b ≤ R ∥ b ∥ a ε = 2 ∥ b ∥ .
Consequently, 1 + T ∗ ( ε ) ≳ L 0 R / ε 1+T^*(\varepsilon)\gtrsim L_0R/\varepsilon 1 + T ∗ ( ε ) ≳ L 0 R / ε .
For the gap, we take a = 16 η / R 2 a=16\eta/R^2 a = 16 η / R 2 , s = R / 4 s=R/4 s = R /4 , and κ = L 0 R 2 / ( 16 η ) \kappa=L_0R^2/(16\eta) κ = L 0 R 2 / ( 16 η ) . For an affine skew-symmetric operator,
Gap R F ( z ) = R ∥ F ( z ) ∥ + ⟨ F ( z ) , z ∗ ⟩ ≥ 3 R 4 ∥ F ( z ) ∥ . \operatorname{Gap}^{F}_{R}(z)=R\|F(z)\|+\langle F(z),z^*\rangle\ge\frac{3R}{4}\|F(z)\|. Gap R F ( z ) = R ∥ F ( z ) ∥ + ⟨ F ( z ) , z ∗ ⟩ ≥ 4 3 R ∥ F ( z ) ∥.
The condition Gap R F ≤ η \operatorname{Gap}^{F}_{R}\le\eta Gap R F ≤ η gives a relative residual of the system of at most 1 / 3 1/3 1/3 , so 1 + T G a p ∗ ( η ) ≳ L 0 R 2 / η 1+T^*_{\mathrm{Gap}}(\eta)\gtrsim L_0R^2/\eta 1 + T Gap ∗ ( η ) ≳ L 0 R 2 / η . The details of the identity for the gap are given in Appendix C.7.
Two different problems give two lower bounds, and their maximum is at least half of their sum. Therefore, the linear problem and the chain together give the claimed bound. When these ratios are bounded, the corresponding lower bounds follow from 1 + T ∗ ≥ 1 1+T^*\ge1 1 + T ∗ ≥ 1 .
Proposition 4.11 (the term L 0 R / ε L_0R/\varepsilon L 0 R / ε ). ▼ proof in Appendix C.7
If L 0 R / ε ≥ 1 L_0R/\varepsilon\ge1 L 0 R / ε ≥ 1 , then
1 + T ∗ ( ε ) ≳ L 0 R ε . 1+T^*(\varepsilon)\gtrsim\frac{L_0R}{\varepsilon}. 1 + T ∗ ( ε ) ≳ ε L 0 R . If L 0 R 2 / η ≥ 1 L_0R^2/\eta\ge1 L 0 R 2 / η ≥ 1 , then
1 + T G a p ∗ ( η ) ≳ L 0 R 2 η . 1+T^*_{\mathrm{Gap}}(\eta)\gtrsim\frac{L_0R^2}{\eta}. 1 + T Gap ∗ ( η ) ≳ η L 0 R 2 .
Theorem 4.12 (lower bound with exponent 6 / 5 6/5 6/5 ). For L 0 R / ε ≥ 1 L_0R/\varepsilon\ge1 L 0 R / ε ≥ 1 ,
1 + T ∗ ( ε ) ≥ c ( 1 + L 0 R ε + ( L 1 R ) 6 / 5 log 4 / 5 ( 2 + L 1 R ) ) . 1+T^*(\varepsilon) \ge c\left(1+\frac{L_0R}{\varepsilon}+\frac{(L_1R)^{6/5}}{\log^{4/5}(2+L_1R)}\right). 1 + T ∗ ( ε ) ≥ c ( 1 + ε L 0 R + log 4/5 ( 2 + L 1 R ) ( L 1 R ) 6/5 ) . and the same bound with L 0 R / ε L_0R/\varepsilon L 0 R / ε replaced by L 0 R 2 / η L_0R^2/\eta L 0 R 2 / η holds for T G a p ∗ ( η ) T^*_{\mathrm{Gap}}(\eta) T Gap ∗ ( η ) when L 0 R 2 / η ≥ 1 L_0R^2/\eta\ge1 L 0 R 2 / η ≥ 1 . The worst-case operators can be chosen from C 2 ( R d ) C^2(\mathbb{R}^d) C 2 ( R d ) .
Completion of the proof of Theorem 4.12. In Sections 4.7 and 4.8, we constructed admissible C 2 C^2 C 2 operators for which Proposition 4.8 gives a lower bound of order n n n . By Lemma C.1 and the maximality of h h h , this is of order ( L 1 R ) 6 / 5 / log 4 / 5 ( 2 + L 1 R ) (L_1R)^{6/5}/\log^{4/5}(2+L_1R) ( L 1 R ) 6/5 / log 4/5 ( 2 + L 1 R ) . Proposition 4.11 independently gives the Lipschitz term. Hence, there exist absolute constants c 1 , c 2 > 0 c_1,c_2>0 c 1 , c 2 > 0 for which
1 + T ≥ c 1 L 0 R ε , 1+T \ge c_1\frac{L_0R}{\varepsilon}, 1 + T ≥ c 1 ε L 0 R ,
1 + T ≥ c 2 ( L 1 R ) 6 / 5 log 4 / 5 ( 2 + L 1 R ) . 1+T \ge c_2\frac{(L_1R)^{6/5}}{\log^{4/5}(2+L_1R)}. 1 + T ≥ c 2 log 4/5 ( 2 + L 1 R ) ( L 1 R ) 6/5 .
Adding these inequalities to 1 + T ≥ 1 1+T\ge1 1 + T ≥ 1 , we obtain
1 + T ≥ min { 1 , c 1 , c 2 } 3 ( 1 + L 0 R ε + ( L 1 R ) 6 / 5 log 4 / 5 ( 2 + L 1 R ) ) . 1+T\ge\frac{\min\{1,c_1,c_2\}}{3}\left(1+\frac{L_0R}{\varepsilon}+\frac{(L_1R)^{6/5}}{\log^{4/5}(2+L_1R)}\right). 1 + T ≥ 3 min { 1 , c 1 , c 2 } ( 1 + ε L 0 R + log 4/5 ( 2 + L 1 R ) ( L 1 R ) 6/5 ) .
For the gap, the argument is the same with L 0 R / ε L_0R/\varepsilon L 0 R / ε replaced by L 0 R 2 / η L_0R^2/\eta L 0 R 2 / η . When L 1 R L_1R L 1 R is bounded, including L 1 = 0 L_1=0 L 1 = 0 , the nonlinear term is bounded by an absolute constant and is absorbed into the constant term 1. Taking the infimum over admissible algorithms, we obtain both statements.
The exponent 6 / 5 6/5 6/5 and the logarithmic factor arise from the relation between the chain length n n n and the distance ∥ σ ∥ \lVert\sigma\rVert ∥ σ ∥ from the starting point to the solution: with n n n coordinates, the shift σ \sigma σ that defines the solution u ∗ = − σ u^*=-\sigma u ∗ = − σ has norm of order n ( H + m log n ) / ℓ 1 \sqrt{n}(H+\sqrt{m}\log n)/\ell_1 n ( H + m log n ) / ℓ 1 , and this norm must not exceed R R R . Smoothing and coordinate hiding change only absolute constants and the dimension, without reducing the required number of queries. The initial norm of the worst-case operator equals G 1 = ( L 0 / ( 2 L 1 ) ) n 3 e H − 1 G_1=(L_0/(2L_1))n^3e^{H-1} G 1 = ( L 0 / ( 2 L 1 )) n 3 e H − 1 and can be exponentially large in the number of blocks.
Variational inequalities on a bounded set
In this section, Z ⊂ R d Z\subset\mathbb{R}^d Z ⊂ R d is a convex compact set of diameter D D D onto which the exact projection P Z P_Z P Z is available, and the output point must belong to Z Z Z . A solution of the variational inequality is a point z ∗ ∈ Z z^*\in Z z ∗ ∈ Z such that ⟨ F ( z ∗ ) , z − z ∗ ⟩ ≥ 0 \langle F(z^*),z-z^*\rangle\ge0 ⟨ F ( z ∗ ) , z − z ∗ ⟩ ≥ 0 for all z ∈ Z z\in Z z ∈ Z . In other words, − F ( z ∗ ) -F(z^*) − F ( z ∗ ) lies in the normal cone
N Z ( z ∗ ) = { ξ ∈ R d : ⟨ ξ , z − z ∗ ⟩ ≤ 0 for all z ∈ Z } , N_Z(z^*)=\{\xi\in\mathbb{R}^d:\langle\xi,z-z^*\rangle\le0\text{ for all }z\in Z\}, N Z ( z ∗ ) = { ξ ∈ R d : ⟨ ξ , z − z ∗ ⟩ ≤ 0 for all z ∈ Z } ,
so F ( z ∗ ) F(z^*) F ( z ∗ ) need not be zero. Accuracy is measured by the Minty gap and the strong gap
Gap Z M ( z ) = sup u ∈ Z ⟨ F ( u ) , z − u ⟩ , \operatorname{Gap}^{\mathrm{M}}_Z(z)=\sup_{u\in Z}\langle F(u),z-u\rangle, Gap Z M ( z ) = u ∈ Z sup ⟨ F ( u ) , z − u ⟩ ,
Gap Z S ( z ) = sup u ∈ Z ⟨ F ( z ) , z − u ⟩ . \operatorname{Gap}^{\mathrm{S}}_Z(z)=\sup_{u\in Z}\langle F(z),z-u\rangle. Gap Z S ( z ) = u ∈ Z sup ⟨ F ( z ) , z − u ⟩ .
For a monotone operator, 0 ≤ Gap Z M ≤ Gap Z S 0\le\operatorname{Gap}^{\mathrm{M}}_Z\le\operatorname{Gap}^{\mathrm{S}}_Z 0 ≤ Gap Z M ≤ Gap Z S , and the equality Gap Z M ( z ) = 0 \operatorname{Gap}^{\mathrm{M}}_Z(z)=0 Gap Z M ( z ) = 0 means that z z z is a solution [16 ] . The relation between these gaps and the residuals used by projection methods is given in Appendix § 10 .
Why the parameters L 0 L_0 L 0 , L 1 L_1 L 1 , and D D D are not sufficient
On the whole space, a solution requires F ( z ∗ ) = 0 F(z^*) = 0 F ( z ∗ ) = 0 . On a compact set, the feasible directions may lie only on one side of a boundary point, so a nonzero component of F ( z ∗ ) F(z^*) F ( z ∗ ) opposite to the outward normal may persist at the solution. Its inner product with any vector z − z ∗ z-z^* z − z ∗ , z ∈ Z z \in Z z ∈ Z , is nonnegative. For each operator this component is finite, but its magnitude is not bounded in terms of L 0 L_0 L 0 , L 1 L_1 L 1 , and D D D . If it is large, condition (1) admits a Jacobian of large norm with the same L 0 L_0 L 0 , L 1 L_1 L 1 .
Fix L 0 L_0 L 0 , L 1 L_1 L 1 , D D D , η \eta η with L 1 > 0 L_1 > 0 L 1 > 0 . We introduce a new parameter of the construction, an arbitrary real number Γ > 0 \Gamma> 0 Γ > 0 , which we will regard as arbitrarily large. We add the constant component Γ / L 1 \Gamma/L_1 Γ/ L 1 to the worst-case linear problem of § 4.9 . Then ∥ F ∥ ≥ Γ / L 1 \lVert F\rVert\ge\Gamma/L_1 ∥ F ∥ ≥ Γ/ L 1 implies L 0 + L 1 ∥ F ∥ ≥ Γ L_0 + L_1\lVert F\rVert\ge\Gamma L 0 + L 1 ∥ F ∥ ≥ Γ . Therefore, condition (1) admits a Jacobian of norm Γ \Gamma Γ with the same L 0 L_0 L 0 , L 1 L_1 L 1 .
Choose Γ ≥ 72 η / D 2 \Gamma\ge72\eta/D^2 Γ ≥ 72 η / D 2 , set κ = Γ D 2 / ( 72 η ) \kappa= \Gamma D^2/(72\eta) κ = Γ D 2 / ( 72 η ) , and take a symmetric matrix A A A with spectrum in [ − κ , − 1 ] ∪ [ 1 , κ ] [-\kappa,-1]\cup[1,\kappa] [ − κ , − 1 ] ∪ [ 1 , κ ] and b ≠ 0 b \ne0 b = 0 from Lemma 4.10 . On the set Z = B ( 0 , D / 3 ) × [ 0 , D / 3 ] × B ( 0 , D / 3 ) Z = B(0,D/3)\times[0,D/3]\times B(0,D/3) Z = B ( 0 , D /3 ) × [ 0 , D /3 ] × B ( 0 , D /3 ) of diameter D D D , we construct
F ( x , t , y ) = ( 72 η D 2 A y , Γ L 1 , 72 η D 2 ( D b 12 ∥ b ∥ − A x ) ) . F(x,t,y)=\left(\frac{72\eta}{D^2}Ay,\frac{\Gamma}{L_1},\frac{72\eta}{D^2}\left(\frac{Db}{12\lVert b\rVert}-Ax\right)\right). F ( x , t , y ) = ( D 2 72 η A y , L 1 Γ , D 2 72 η ( 12 ∥ b ∥ D b − A x ) ) .
The exact verification in Appendix § 10 .§ 2 reduces a small gap to solving a linear system and yields the lower bound T ≳ Γ D 2 / η T \gtrsim\Gamma D^2/\eta T ≳ Γ D 2 / η . Since Γ \Gamma Γ can be chosen arbitrarily large, we obtain the following result.
Theorem 5.1 (no uniform bound). ▼ proof in Appendix § 10 .§ 2
Let L 0 ≥ 0 L_0 \ge0 L 0 ≥ 0 and L 1 , D , η > 0 L_1,D,\eta> 0 L 1 , D , η > 0 be fixed. For any Γ ≥ 72 η / D 2 \Gamma\ge72\eta/D^2 Γ ≥ 72 η / D 2 , there exist a dimension d d d , a set Z Z Z of diameter D D D that is the product of two balls and a segment, and a family of affine monotone operators F F F satisfying condition (1) on the whole R d \mathbb{R}^d R d such that any randomized algorithm that outputs, with probability at least 2 / 3 2/3 2/3 , a point z ^ ∈ Z \hat z \in Z z ^ ∈ Z with Gap Z M ( z ^ ) ≤ η \operatorname{Gap}^{\mathrm{M}}_Z(\hat z) \le\eta Gap Z M ( z ^ ) ≤ η makes at least c Γ D 2 / η c\Gamma D^2/\eta c Γ D 2 / η oracle calls in expectation. The same holds for Gap Z S \operatorname{Gap}^{\mathrm{S}}_Z Gap Z S .
In particular, the minimax complexity of the class specified only by the numbers L 0 L_0 L 0 , L 1 L_1 L 1 , and D D D is infinite.
Thus, on a bounded set, a uniform complexity bound requires an additional parameter, for example an upper bound on ∥ F ( z ∗ ) ∥ \lVert F(z^*)\rVert ∥ F ( z ∗ )∥ .
Conclusion
For finding a zero of a monotone ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -Lipschitz operator with a known radius R R R , we determined the oracle complexity up to the factor log 4 / 5 ( 2 + L 1 R ) \log^{4/5}(2+L_1R) log 4/5 ( 2 + L 1 R ) : it is of order 1 + L 0 R / ϵ + ( L 1 R ) 6 / 5 1+L_0R/\epsilon+(L_1R)^{6/5} 1 + L 0 R / ϵ + ( L 1 R ) 6/5 . The upper bound is deterministic, and the lower bound holds for arbitrary randomized methods. For gradients of convex functions, the price of traversing the region of large operator values is L 1 R L_1R L 1 R ([23 ] ), while for monotone operators it grows to ( L 1 R ) 6 / 5 (L_1R)^{6/5} ( L 1 R ) 6/5 .
Open questions
Saddle-point problems. What is the complexity for operators of saddle-point problems F ( x , y ) = ( ∇ x φ ( x , y ) , − ∇ y φ ( x , y ) ) F(x,y)=(\nabla_x\varphi(x,y),-\nabla_y\varphi(x,y)) F ( x , y ) = ( ∇ x φ ( x , y ) , − ∇ y φ ( x , y )) with a convex–concave function φ \varphi φ ? For this class, ABSEIL yields a complexity bound with exponent 6 / 5 6/5 6/5 in L 1 R L_1R L 1 R . The operator in our lower bound is not constructed as the operator of a saddle-point problem, while minimization of a convex function is a special case of a saddle-point problem for which the price of traversing the region of large values equals L 1 R L_1R L 1 R ([23 ] ). Thus, for saddle-point problems the optimal exponent lies between 1 1 1 and 6 / 5 6/5 6/5 , and its exact value remains open.
Unknown parameters. Can the same order be achieved by a method that does not know L 0 L_0 L 0 , L 1 L_1 L 1 , and R R R , counting all oracle calls spent on stepsize tuning and on checking the stopping criterion? The steps of our method are adaptive, but they use the known L 0 L_0 L 0 , L 1 L_1 L 1 , and R R R .
Properties of the class
Characterization of the class
Proof of Lemma 2.4 ▲.
▷ Necessity in (a). A continuous F F F is bounded on each ball by some number M M M . If the segment [ x , y ] [x,y] [ x , y ] lies in such a ball, then by (1) ∥ F ( x ) − F ( y ) ∥ ≤ ( L 0 + L 1 M ) ∥ x − y ∥ \lVert F(x)-F(y)\rVert\le(L_0+L_1M)\lVert x-y\rVert ∥ F ( x ) − F ( y )∥ ≤ ( L 0 + L 1 M ) ∥ x − y ∥ . Hence, t ↦ F ( x + t v ) t \mapsto F(x+tv) t ↦ F ( x + t v ) is locally Lipschitz, locally absolutely continuous, and differentiable for almost all t t t . At such a point t t t , we apply (1) to the points x + t v x+tv x + t v and x + ( t + h ) v x+(t+h)v x + ( t + h ) v , divide by ∣ h ∣ \lvert h\rvert ∣ h ∣ , and let h h h tend to zero. By continuity of F F F , the supremum in (1) tends to ∥ F ( x + t v ) ∥ \lVert F(x+tv)\rVert ∥ F ( x + t v )∥ .
▷ Sufficiency in (a). Let v = y − x v=y-x v = y − x . By the Newton–Leibniz formula,
∥ F ( y ) − F ( x ) ∥ ≤ ∫ 0 1 ∥ d d t F ( x + t v ) ∥ d t ≤ ∫ 0 1 ( L 0 + L 1 ∥ F ( x + t v ) ∥ ) ∥ v ∥ d t ≤ ( L 0 + L 1 sup w ∈ [ x , y ] ∥ F ( w ) ∥ ) ∥ x − y ∥ . \begin{aligned}
\lVert F(y)-F(x)\rVert&\le\int_0^1 \left\lVert\frac{\mathrm{d}}{\mathrm{d}t}F(x+tv)\right\rVert\mathrm{d}t \le\int_0^1 \left(L_0+L_1\lVert F(x+tv)\rVert\right)\lVert v\rVert\mathrm{d}t \\
&\le\left(L_0+L_1\sup_{w\in[x,y]}\lVert F(w)\rVert\right)\lVert x-y\rVert.
\end{aligned} ∥ F ( y ) − F ( x )∥ ≤ ∫ 0 1 d t d F ( x + t v ) d t ≤ ∫ 0 1 ( L 0 + L 1 ∥ F ( x + t v )∥ ) ∥ v ∥ d t ≤ ( L 0 + L 1 w ∈ [ x , y ] sup ∥ F ( w )∥ ) ∥ x − y ∥ .
▷ Claim (b). For F ∈ C 1 F\in C^1 F ∈ C 1 , the derivative of the map t ↦ F ( x + t v ) t\mapsto F(x+tv) t ↦ F ( x + t v ) equals D F ( x + t v ) v DF(x+tv)v D F ( x + t v ) v and is continuous in t t t . Therefore, condition (a) is equivalent to the inequality ∥ D F ( z ) v ∥ ≤ ( L 0 + L 1 ∥ F ( z ) ∥ ) ∥ v ∥ \lVert DF(z)v\rVert\le(L_0+L_1\lVert F(z)\rVert)\lVert v\rVert ∥ D F ( z ) v ∥ ≤ ( L 0 + L 1 ∥ F ( z )∥) ∥ v ∥ for all z , v z,v z , v , that is, to the bound ∥ D F ( z ) ∥ ≤ L 0 + L 1 ∥ F ( z ) ∥ \lVert DF(z)\rVert\le L_0+L_1\lVert F(z)\rVert ∥ D F ( z )∥ ≤ L 0 + L 1 ∥ F ( z )∥ .
▷ Claim (c). By Rademacher’s theorem, F F F is differentiable almost everywhere. Fix a direction v v v . By Fubini’s theorem, for almost all x x x in the orthogonal complement of v v v , the derivative D F ( x + t v ) DF(x+tv) D F ( x + t v ) exists for almost all t t t and equals d d t F ( x + t v ) \frac{\mathrm{d}}{\mathrm{d}t}F(x+tv) d t d F ( x + t v ) . On such lines, condition (a) holds, and by what has been proved, (1) holds for segments parallel to v v v and lying on these lines. An arbitrary segment with direction v v v is approximated by such segments, and (1) passes to the limit by continuity of F F F . □
Grönwall’s lemma
Proof of Lemma 2.5 ▲. Let s = ∥ u − v ∥ > 0 s=\lVert u-v\rVert>0 s = ∥ u − v ∥ > 0 , w ( t ) = u + t ( v − u ) / s w(t)=u+t(v-u)/s w ( t ) = u + t ( v − u ) / s , and ϕ ( t ) = L 0 + L 1 ∥ F ( w ( t ) ) ∥ \phi(t)=L_0+L_1\lVert F(w(t))\rVert ϕ ( t ) = L 0 + L 1 ∥ F ( w ( t ))∥ for t ∈ [ 0 , s ] t\in[0,s] t ∈ [ 0 , s ] . By Lemma 2.4(a), the function ϕ \phi ϕ is absolutely continuous, and for almost all t t t ,
ϕ ′ ( t ) ≤ L 1 ∥ d d t F ( w ( t ) ) ∥ ≤ L 1 ϕ ( t ) . \phi'(t)\le L_1\left\lVert\frac{\mathrm{d}}{\mathrm{d}t}F(w(t))\right\rVert\le L_1\phi(t). ϕ ′ ( t ) ≤ L 1 d t d F ( w ( t )) ≤ L 1 ϕ ( t ) .
Therefore, ( e − L 1 t ϕ ( t ) ) ′ ≤ 0 (e^{-L_1t}\phi(t))'\le0 ( e − L 1 t ϕ ( t ) ) ′ ≤ 0 and ϕ ( t ) ≤ ϕ ( 0 ) e L 1 t \phi(t)\le\phi(0)e^{L_1t} ϕ ( t ) ≤ ϕ ( 0 ) e L 1 t , which for t = s t=s t = s gives (a). Further,
∥ F ( v ) − F ( u ) ∥ ≤ ∫ 0 s ∥ d d t F ( w ( t ) ) ∥ d t ≤ ∫ 0 s ϕ ( t ) d t ≤ ϕ ( 0 ) ∫ 0 s e L 1 t d t = ϕ ( 0 ) e L 1 s − 1 L 1 ≤ ϕ ( 0 ) s e L 1 s , \lVert F(v)-F(u)\rVert\le\int_0^s\left\lVert\frac{\mathrm{d}}{\mathrm{d}t}F(w(t))\right\rVert\mathrm{d}t\le\int_0^s\phi(t)\mathrm{d}t\le\phi(0)\int_0^s e^{L_1t}\mathrm{d}t=\phi(0)\frac{e^{L_1s}-1}{L_1}\le\phi(0)se^{L_1s}, ∥ F ( v ) − F ( u )∥ ≤ ∫ 0 s d t d F ( w ( t )) d t ≤ ∫ 0 s ϕ ( t ) d t ≤ ϕ ( 0 ) ∫ 0 s e L 1 t d t = ϕ ( 0 ) L 1 e L 1 s − 1 ≤ ϕ ( 0 ) s e L 1 s ,
where (a) is the inequality e x − 1 ≤ x e x e^x-1\le xe^x e x − 1 ≤ x e x . If the derivative bound holds only on the segment [ u , v ] [u,v] [ u , v ] and with a constant A A A in place of L 0 L_0 L 0 , then the same argument goes through with ϕ ( t ) = A + L 1 ∥ F ( w ( t ) ) ∥ \phi(t)=A+L_1\lVert F(w(t))\rVert ϕ ( t ) = A + L 1 ∥ F ( w ( t ))∥ . □
Gap and the norm of F F F
Proof of Lemma 2.6 ▲. For u = z ∗ u=z^* u = z ∗ , we have ⟨ F ( z ∗ ) , z − z ∗ ⟩ = 0 \langle F(z^*),z-z^*\rangle=0 ⟨ F ( z ∗ ) , z − z ∗ ⟩ = 0 , hence Gap R ( z ) ≥ 0 \operatorname{Gap}_R(z)\ge0 Gap R ( z ) ≥ 0 . For any u ∈ B ( z 0 , R ) u\in B(z_0,R) u ∈ B ( z 0 , R ) ,
⟨ F ( u ) , z − u ⟩ ≤ ( a ) ⟨ F ( z ) , z − u ⟩ ≤ ∥ F ( z ) ∥ ∥ z − u ∥ ≤ ( b ) ∥ F ( z ) ∥ ( ∥ z − z 0 ∥ + R ) , \langle F(u),z-u\rangle\underset{\mathrm{(a)}}{\le}\langle F(z),z-u\rangle\le\lVert F(z)\rVert\lVert z-u\rVert\underset{\mathrm{(b)}}{\le}\lVert F(z)\rVert(\lVert z-z_0\rVert+R), ⟨ F ( u ) , z − u ⟩ ( a ) ≤ ⟨ F ( z ) , z − u ⟩ ≤ ∥ F ( z )∥ ∥ z − u ∥ ( b ) ≤ ∥ F ( z )∥ (∥ z − z 0 ∥ + R ) ,
where (a) is monotonicity and (b) is the inequality ∥ u − z 0 ∥ ≤ R \lVert u-z_0\rVert\le R ∥ u − z 0 ∥ ≤ R . □
Proofs of the upper bound
Throughout this appendix, Assumptions 2.1–2.3 hold.
Long step
Proof of Lemma 3.1 . We prove the lemma for an arbitrary b ∈ [ 1 , L 1 R ] b \in[1,L_1R] b ∈ [ 1 , L 1 R ] , in the form used in § 3.4 . Assume that ∥ F ( x ) ∥ > 2 L 0 R ( e b − 1 ) / b \lVert F(x)\rVert> 2L_0R(e^b-1)/b ∥ F ( x )∥ > 2 L 0 R ( e b − 1 ) / b . We need to show that a step of length b / ( 2 L 1 ) b/(2L_1) b / ( 2 L 1 ) decreases the squared distance to the solution by b 2 / ( 4 L 1 2 ) b^2/(4L_1^2) b 2 / ( 4 L 1 2 ) . Lemma 3.1 is obtained for b = ( L 1 R ) 2 / 5 b=(L_1R)^{2/5} b = ( L 1 R ) 2/5 .
Consider the point w = z ∗ + b F ( x ) / ( L 1 ∥ F ( x ) ∥ ) w=z^*+bF(x)/(L_1\lVert F(x)\rVert) w = z ∗ + b F ( x ) / ( L 1 ∥ F ( x )∥) . Since ∥ w − z ∗ ∥ = b / L 1 \lVert w-z^*\rVert=b/L_1 ∥ w − z ∗ ∥ = b / L 1 , Lemma 2.5 (b) with u = z ∗ u=z^* u = z ∗ gives ∥ F ( w ) ∥ ≤ ( L 0 / L 1 ) ( e b − 1 ) \lVert F(w)\rVert\leq(L_0/L_1)(e^b-1) ∥ F ( w )∥ ≤ ( L 0 / L 1 ) ( e b − 1 ) . We show that ⟨ F ( x ) , x − z ∗ ⟩ > b ∥ F ( x ) ∥ / ( 2 L 1 ) \langle F(x),x-z^*\rangle>b\lVert F(x)\rVert/(2L_1) ⟨ F ( x ) , x − z ∗ ⟩ > b ∥ F ( x )∥ / ( 2 L 1 ) . Suppose the contrary. Then
b L 1 − ⟨ F ( x ) , x − z ∗ ⟩ ∥ F ( x ) ∥ ≥ b 2 L 1 > 0 \frac{b}{L_1}-\frac{\langle F(x),x-z^*\rangle}{\lVert F(x)\rVert}\geq\frac{b}{2L_1}>0 L 1 b − ∥ F ( x )∥ ⟨ F ( x ) , x − z ∗ ⟩ ≥ 2 L 1 b > 0
and
∥ x − w ∥ 2 = ∥ x − z ∗ ∥ 2 − 2 b ⟨ F ( x ) , x − z ∗ ⟩ L 1 ∥ F ( x ) ∥ + b 2 L 1 2 ≤ R 2 − b 2 L 1 2 + 2 b L 1 ( b L 1 − ⟨ F ( x ) , x − z ∗ ⟩ ∥ F ( x ) ∥ ) ≤ 4 R 2 L 1 2 b 2 ( b L 1 − ⟨ F ( x ) , x − z ∗ ⟩ ∥ F ( x ) ∥ ) 2 . \begin{aligned}
\lVert x-w\rVert^2
&=\lVert x-z^*\rVert^2-\frac{2b\langle F(x),x-z^*\rangle}{L_1\lVert F(x)\rVert}+\frac{b^2}{L_1^2}\\
&\leq R^2-\frac{b^2}{L_1^2}+\frac{2b}{L_1}\left(\frac{b}{L_1}-\frac{\langle F(x),x-z^*\rangle}{\lVert F(x)\rVert}\right)\\
&\leq\frac{4R^2L_1^2}{b^2}\left(\frac{b}{L_1}-\frac{\langle F(x),x-z^*\rangle}{\lVert F(x)\rVert}\right)^2.
\end{aligned} ∥ x − w ∥ 2 = ∥ x − z ∗ ∥ 2 − L 1 ∥ F ( x )∥ 2 b ⟨ F ( x ) , x − z ∗ ⟩ + L 1 2 b 2 ≤ R 2 − L 1 2 b 2 + L 1 2 b ( L 1 b − ∥ F ( x )∥ ⟨ F ( x ) , x − z ∗ ⟩ ) ≤ b 2 4 R 2 L 1 2 ( L 1 b − ∥ F ( x )∥ ⟨ F ( x ) , x − z ∗ ⟩ ) 2 .
where (a) is the condition ∥ x − z ∗ ∥ ≤ R \lVert x-z^*\rVert\leq R ∥ x − z ∗ ∥ ≤ R , and (b) is the inequality R 2 − ρ 2 + 2 ρ σ ≤ 4 R 2 σ 2 / ρ 2 R^2-\rho^2+2\rho\sigma\leq4R^2\sigma^2/\rho^2 R 2 − ρ 2 + 2 ρ σ ≤ 4 R 2 σ 2 / ρ 2 , which holds for σ ≥ ρ / 2 \sigma\geq\rho/2 σ ≥ ρ /2 and ρ ≤ R \rho\leq R ρ ≤ R , since the difference of its sides equals ( 2 σ − ρ ) ( 2 R 2 σ + R 2 ρ − ρ 3 ) / ρ 2 ≥ 0 (2\sigma-\rho)(2R^2\sigma+R^2\rho-\rho^3)/\rho^2\geq0 ( 2 σ − ρ ) ( 2 R 2 σ + R 2 ρ − ρ 3 ) / ρ 2 ≥ 0 . It is applied with ρ = b / L 1 \rho=b/L_1 ρ = b / L 1 and σ = b / L 1 − ⟨ F ( x ) , x − z ∗ ⟩ / ∥ F ( x ) ∥ \sigma=b/L_1-\langle F(x),x-z^*\rangle/\lVert F(x)\rVert σ = b / L 1 − ⟨ F ( x ) , x − z ∗ ⟩ / ∥ F ( x )∥ . By monotonicity and the Cauchy–Schwarz inequality,
∥ F ( x ) ∥ ( b L 1 − ⟨ F ( x ) , x − z ∗ ⟩ ∥ F ( x ) ∥ ) = ⟨ F ( x ) , w − x ⟩ ≤ ⟨ F ( w ) , w − x ⟩ ≤ ∥ F ( w ) ∥ ∥ x − w ∥ ≤ L 0 L 1 ( e b − 1 ) 2 R L 1 b ( b L 1 − ⟨ F ( x ) , x − z ∗ ⟩ ∥ F ( x ) ∥ ) . \begin{aligned}
\lVert F(x)\rVert\left(\frac{b}{L_1}-\frac{\langle F(x),x-z^*\rangle}{\lVert F(x)\rVert}\right)=\langle F(x),w-x\rangle\leq\langle F(w),w-x\rangle\leq\lVert F(w)\rVert\lVert x-w\rVert\\
&\leq\frac{L_0}{L_1}(e^b-1)\frac{2RL_1}{b}\left(\frac{b}{L_1}-\frac{\langle F(x),x-z^*\rangle}{\lVert F(x)\rVert}\right).
\end{aligned} ∥ F ( x )∥ ( L 1 b − ∥ F ( x )∥ ⟨ F ( x ) , x − z ∗ ⟩ ) = ⟨ F ( x ) , w − x ⟩ ≤ ⟨ F ( w ) , w − x ⟩ ≤ ∥ F ( w )∥ ∥ x − w ∥ ≤ L 1 L 0 ( e b − 1 ) b 2 R L 1 ( L 1 b − ∥ F ( x )∥ ⟨ F ( x ) , x − z ∗ ⟩ ) .
Dividing by the positive factor, we obtain ∥ F ( x ) ∥ ≤ 2 L 0 R ( e b − 1 ) / b \lVert F(x)\rVert\leq2L_0R(e^b-1)/b ∥ F ( x )∥ ≤ 2 L 0 R ( e b − 1 ) / b , which contradicts the assumption. Consequently,
∥ x − b 2 L 1 F ( x ) ∥ F ( x ) ∥ − z ∗ ∥ 2 = ∥ x − z ∗ ∥ 2 − b L 1 ⟨ F ( x ) , x − z ∗ ⟩ ∥ F ( x ) ∥ + b 2 4 L 1 2 < ∥ x − z ∗ ∥ 2 − b 2 4 L 1 2 . \left\lVert x-\frac{b}{2L_1}\frac{F(x)}{\lVert F(x)\rVert}-z^*\right\rVert^2
=\lVert x-z^*\rVert^2-\frac{b}{L_1}\frac{\langle F(x),x-z^*\rangle}{\lVert F(x)\rVert}+\frac{b^2}{4L_1^2}
<\lVert x-z^*\rVert^2-\frac{b^2}{4L_1^2}. x − 2 L 1 b ∥ F ( x )∥ F ( x ) − z ∗ 2 = ∥ x − z ∗ ∥ 2 − L 1 b ∥ F ( x )∥ ⟨ F ( x ) , x − z ∗ ⟩ + 4 L 1 2 b 2 < ∥ x − z ∗ ∥ 2 − 4 L 1 2 b 2 .
Two cumulative bounds
Proof of Lemma 3.2 . Denote by
L k = ⟨ u k − y k , F ( y k ) ⟩ − Λ k 3 ∥ F ( y k ) ∥ 2 \mathcal{L}_k=\langle u_k-y_k,F(y_k)\rangle-\frac{\Lambda_k}{3}\lVert F(y_k)\rVert^2 L k = ⟨ u k − y k , F ( y k )⟩ − 3 Λ k ∥ F ( y k ) ∥ 2
the Lyapunov function from Sun et al. [26 ] . For k = 1 k=1 k = 1 , the factor 1 − α 1 1-\alpha_1 1 − α 1 equals zero, and the value F ( y 0 ) F(y_0) F ( y 0 ) does not enter any formula. From the definition of Algorithm 2, we obtain
y k − y k − 1 = α k ( u k − 1 − y k − 1 ) − λ k F ( x k ) , u k − y k = ( 1 − α k ) ( u k − 1 − y k − 1 ) + λ k ( F ( x k ) − F ( y k ) ) + 5 6 λ k F ( y k ) , x k − y k = λ k ( F ( x k ) − ( 1 − α k ) F ( y k − 1 ) ) , λ k ( 1 − α k ) α k = 2 Λ k − 1 3 . (16) \begin{aligned}
y_k-y_{k-1}&=\alpha_k(u_{k-1}-y_{k-1})-\lambda_kF(x_k),\\
u_k-y_k&=(1-\alpha_k)(u_{k-1}-y_{k-1})+\lambda_k(F(x_k)-F(y_k))+\frac{5}{6}\lambda_kF(y_k),\\
x_k-y_k&=\lambda_k(F(x_k)-(1-\alpha_k)F(y_{k-1})),\\
\frac{\lambda_k(1-\alpha_k)}{\alpha_k}&=\frac{2\Lambda_{k-1}}{3}. \tag*{(16)}
\end{aligned} y k − y k − 1 u k − y k x k − y k α k λ k ( 1 − α k ) = α k ( u k − 1 − y k − 1 ) − λ k F ( x k ) , = ( 1 − α k ) ( u k − 1 − y k − 1 ) + λ k ( F ( x k ) − F ( y k )) + 6 5 λ k F ( y k ) , = λ k ( F ( x k ) − ( 1 − α k ) F ( y k − 1 )) , = 3 2 Λ k − 1 . (16)
▷ Lyapunov function. Substituting (B.1) into the definition of L k \mathcal{L}_k L k , by direct computation we obtain the identity
L k − ( 1 − α k ) L k − 1 = λ k 2 α k ( ∥ F ( x k ) − ( 1 − α k ) F ( y k − 1 ) ∥ 2 − ∥ F ( x k ) − F ( y k ) ∥ 2 ) + 1 − α k α k ⟨ F ( y k ) − F ( y k − 1 ) , y k − y k − 1 ⟩ . \mathcal{L}_k-(1-\alpha_k)\mathcal{L}_{k-1}
=\frac{\lambda_k}{2\alpha_k}\left(\lVert F(x_k)-(1-\alpha_k)F(y_{k-1})\rVert^2-\lVert F(x_k)-F(y_k)\rVert^2\right)
+\frac{1-\alpha_k}{\alpha_k}\langle F(y_k)-F(y_{k-1}),y_k-y_{k-1}\rangle. L k − ( 1 − α k ) L k − 1 = 2 α k λ k ( ∥ F ( x k ) − ( 1 − α k ) F ( y k − 1 ) ∥ 2 − ∥ F ( x k ) − F ( y k ) ∥ 2 ) + α k 1 − α k ⟨ F ( y k ) − F ( y k − 1 ) , y k − y k − 1 ⟩ .
The second term is nonnegative by monotonicity, and by (7) and (B.1),
∥ F ( x k ) − ( 1 − α k ) F ( y k − 1 ) ∥ = ∥ x k − y k ∥ λ k ≥ 4 ∥ F ( x k ) − F ( y k ) ∥ . \lVert F(x_k)-(1-\alpha_k)F(y_{k-1})\rVert=\frac{\lVert x_k-y_k\rVert}{\lambda_k}\ge4\lVert F(x_k)-F(y_k)\rVert. ∥ F ( x k ) − ( 1 − α k ) F ( y k − 1 )∥ = λ k ∥ x k − y k ∥ ≥ 4 ∥ F ( x k ) − F ( y k )∥ .
Consequently, L k ≥ ( 1 − α k ) L k − 1 \mathcal{L}_k\ge(1-\alpha_k)\mathcal{L}_{k-1} L k ≥ ( 1 − α k ) L k − 1 , and L 1 ≥ 0 \mathcal{L}_1\ge0 L 1 ≥ 0 since α 1 = 1 \alpha_1=1 α 1 = 1 . By induction, L k ≥ 0 \mathcal{L}_k\ge0 L k ≥ 0 for all k k k .
▷ Distance from the anchor to the solution. We have
⟨ u k − z ∗ , F ( y k ) ⟩ = L k + Λ k 3 ∥ F ( y k ) ∥ 2 + ⟨ F ( y k ) − F ( z ∗ ) , y k − z ∗ ⟩ ≥ ( a ) Λ k 3 ∥ F ( y k ) ∥ 2 , \langle u_k-z^*,F(y_k)\rangle=\mathcal{L}_k+\frac{\Lambda_k}{3}\lVert F(y_k)\rVert^2+\langle F(y_k)-F(z^*),y_k-z^*\rangle\underset{(a)}{\ge}\frac{\Lambda_k}{3}\lVert F(y_k)\rVert^2, ⟨ u k − z ∗ , F ( y k )⟩ = L k + 3 Λ k ∥ F ( y k ) ∥ 2 + ⟨ F ( y k ) − F ( z ∗ ) , y k − z ∗ ⟩ ( a ) ≥ 3 Λ k ∥ F ( y k ) ∥ 2 ,
where (a) is the inequality L k ≥ 0 \mathcal{L}_k\ge0 L k ≥ 0 together with monotonicity. Since u k − 1 = u k + λ k F ( y k ) / 6 u_{k-1}=u_k+\lambda_kF(y_k)/6 u k − 1 = u k + λ k F ( y k ) /6 ,
∥ u k − z ∗ ∥ 2 = ∥ u k − 1 − z ∗ ∥ 2 − λ k 3 ⟨ u k − z ∗ , F ( y k ) ⟩ − λ k 2 36 ∥ F ( y k ) ∥ 2 ≤ ∥ u k − 1 − z ∗ ∥ 2 − λ k Λ k 9 ∥ F ( y k ) ∥ 2 . \begin{aligned}
\lVert u_k-z^*\rVert^2=\lVert u_{k-1}-z^*\rVert^2-\frac{\lambda_k}{3}\langle u_k-z^*,F(y_k)\rangle-\frac{\lambda_k^2}{36}\lVert F(y_k)\rVert^2 \\
&\le\lVert u_{k-1}-z^*\rVert^2-\frac{\lambda_k\Lambda_k}{9}\lVert F(y_k)\rVert^2.
\end{aligned} ∥ u k − z ∗ ∥ 2 = ∥ u k − 1 − z ∗ ∥ 2 − 3 λ k ⟨ u k − z ∗ , F ( y k )⟩ − 36 λ k 2 ∥ F ( y k ) ∥ 2 ≤ ∥ u k − 1 − z ∗ ∥ 2 − 9 λ k Λ k ∥ F ( y k ) ∥ 2 .
Summing and using ∥ u 0 − z ∗ ∥ = ∥ s − z ∗ ∥ ≤ R \lVert u_0-z^*\rVert=\lVert s-z^*\rVert\le R ∥ u 0 − z ∗ ∥ = ∥ s − z ∗ ∥ ≤ R , we obtain
∥ u k − z ∗ ∥ 2 + 1 9 ∑ i = 1 k λ i Λ i ∥ F ( y i ) ∥ 2 ≤ R 2 . (17) \lVert u_k-z^*\rVert^2+\frac{1}{9}\sum_{i=1}^{k}\lambda_i\Lambda_i\lVert F(y_i)\rVert^2\le R^2. \tag*{(17)} ∥ u k − z ∗ ∥ 2 + 9 1 i = 1 ∑ k λ i Λ i ∥ F ( y i ) ∥ 2 ≤ R 2 . (17)
These are the first and third bounds of the lemma. The second one follows from
R ∥ F ( y k ) ∥ ≥ ∥ u k − z ∗ ∥ ∥ F ( y k ) ∥ ≥ ⟨ u k − z ∗ , F ( y k ) ⟩ ≥ Λ k 3 ∥ F ( y k ) ∥ 2 . R\lVert F(y_k)\rVert\ge\lVert u_k-z^*\rVert\lVert F(y_k)\rVert\ge\langle u_k-z^*,F(y_k)\rangle\ge\frac{\Lambda_k}{3}\lVert F(y_k)\rVert^2. R ∥ F ( y k )∥ ≥ ∥ u k − z ∗ ∥ ∥ F ( y k )∥ ≥ ⟨ u k − z ∗ , F ( y k )⟩ ≥ 3 Λ k ∥ F ( y k ) ∥ 2 .
▷ Errors of the extragradient step. By (7) and (B.1),
4 λ k ∥ F ( x k ) − F ( y k ) ∥ ≤ ∥ x k − y k ∥ ≤ λ k ( ∥ F ( y k ) ∥ + ∥ F ( x k ) − F ( y k ) ∥ + ( 1 − α k ) ∥ F ( y k − 1 ) ∥ ) , \begin{aligned}
4\lambda_k\lVert F(x_k)-F(y_k)\rVert\le\lVert x_k-y_k\rVert\\
&\le\lambda_k\bigl(\lVert F(y_k)\rVert+\lVert F(x_k)-F(y_k)\rVert+(1-\alpha_k)\lVert F(y_{k-1})\rVert\bigr),
\end{aligned} 4 λ k ∥ F ( x k ) − F ( y k )∥ ≤ ∥ x k − y k ∥ ≤ λ k ( ∥ F ( y k )∥ + ∥ F ( x k ) − F ( y k )∥ + ( 1 − α k ) ∥ F ( y k − 1 )∥ ) ,
whence
∥ F ( x k ) − F ( y k ) ∥ 2 ≤ 2 9 ( ∥ F ( y k ) ∥ 2 + ( 1 − α k ) 2 ∥ F ( y k − 1 ) ∥ 2 ) . \lVert F(x_k)-F(y_k)\rVert^2\le\frac{2}{9}\bigl(\lVert F(y_k)\rVert^2+(1-\alpha_k)^2\lVert F(y_{k-1})\rVert^2\bigr). ∥ F ( x k ) − F ( y k ) ∥ 2 ≤ 9 2 ( ∥ F ( y k ) ∥ 2 + ( 1 − α k ) 2 ∥ F ( y k − 1 ) ∥ 2 ) .
Keeping the factor ( 1 − α k ) 2 (1-\alpha_k)^2 ( 1 − α k ) 2 , for k ≥ 2 k\ge2 k ≥ 2 we obtain λ k 2 / α k ≤ λ k Λ k \lambda_k^2/\alpha_k\le\lambda_k\Lambda_k λ k 2 / α k ≤ λ k Λ k and
λ k 2 ( 1 − α k ) 2 α k = 4 λ k Λ k − 1 2 3 ( 2 Λ k − 1 + 3 λ k ) ≤ 2 3 λ k Λ k − 1 ≤ ( b ) 8 3 λ k − 1 Λ k − 1 , \frac{\lambda_k^2(1-\alpha_k)^2}{\alpha_k}=\frac{4\lambda_k\Lambda_{k-1}^2}{3(2\Lambda_{k-1}+3\lambda_k)}\le\frac{2}{3}\lambda_k\Lambda_{k-1}\underset{(b)}{\le}\frac{8}{3}\lambda_{k-1}\Lambda_{k-1}, α k λ k 2 ( 1 − α k ) 2 = 3 ( 2 Λ k − 1 + 3 λ k ) 4 λ k Λ k − 1 2 ≤ 3 2 λ k Λ k − 1 ( b ) ≤ 3 8 λ k − 1 Λ k − 1 ,
where (b) is the condition λ k ≤ 4 λ k − 1 \lambda_k\le4\lambda_{k-1} λ k ≤ 4 λ k − 1 . Therefore,
∑ i = 1 k λ i 2 α i ∥ F ( x i ) − F ( y i ) ∥ 2 ≤ 2 9 ( 9 + 8 3 ⋅ 9 ) R 2 = 22 3 R 2 . (18) \sum_{i=1}^{k}\frac{\lambda_i^2}{\alpha_i}\lVert F(x_i)-F(y_i)\rVert^2\le\frac{2}{9}\left(9+\frac{8}{3}\cdot9\right)R^2=\frac{22}{3}R^2. \tag*{(18)} i = 1 ∑ k α i λ i 2 ∥ F ( x i ) − F ( y i ) ∥ 2 ≤ 9 2 ( 9 + 3 8 ⋅ 9 ) R 2 = 3 22 R 2 . (18)
▷ Distance from the point to the anchor. A direct computation using (B.1) gives
( ∥ u k − y k ∥ 2 + 5 ∥ u k − z ∗ ∥ 2 ) − ( ∥ u k − 1 − y k − 1 ∥ 2 + 5 ∥ u k − 1 − z ∗ ∥ 2 ) = ∥ ( 1 − α k ) ( u k − 1 − y k − 1 ) + λ k ( F ( x k ) − F ( y k ) ) ∥ 2 − ∥ u k − 1 − y k − 1 ∥ 2 − 5 3 λ k ⟨ F ( y k ) , y k − z ∗ ⟩ − 5 6 λ k 2 ∥ F ( y k ) ∥ 2 ≤ ( c ) λ k 2 α k ∥ F ( x k ) − F ( y k ) ∥ 2 − α k ∥ u k − 1 − y k − 1 ∥ 2 , \begin{aligned}
&\bigl(\lVert u_k-y_k\rVert^2+5\lVert u_k-z^*\rVert^2\bigr)-\bigl(\lVert u_{k-1}-y_{k-1}\rVert^2+5\lVert u_{k-1}-z^*\rVert^2\bigr)\\
&=\lVert(1-\alpha_k)(u_{k-1}-y_{k-1})+\lambda_k(F(x_k)-F(y_k))\rVert^2-\lVert u_{k-1}-y_{k-1}\rVert^2\\
&\qquad-\frac{5}{3}\lambda_k\langle F(y_k),y_k-z^*\rangle-\frac{5}{6}\lambda_k^2\lVert F(y_k)\rVert^2\\
&\underset{(c)}{\le}\frac{\lambda_k^2}{\alpha_k}\lVert F(x_k)-F(y_k)\rVert^2-\alpha_k\lVert u_{k-1}-y_{k-1}\rVert^2,
\end{aligned} ( ∥ u k − y k ∥ 2 + 5 ∥ u k − z ∗ ∥ 2 ) − ( ∥ u k − 1 − y k − 1 ∥ 2 + 5 ∥ u k − 1 − z ∗ ∥ 2 ) = ∥( 1 − α k ) ( u k − 1 − y k − 1 ) + λ k ( F ( x k ) − F ( y k )) ∥ 2 − ∥ u k − 1 − y k − 1 ∥ 2 − 3 5 λ k ⟨ F ( y k ) , y k − z ∗ ⟩ − 6 5 λ k 2 ∥ F ( y k ) ∥ 2 ( c ) ≤ α k λ k 2 ∥ F ( x k ) − F ( y k ) ∥ 2 − α k ∥ u k − 1 − y k − 1 ∥ 2 ,
where (c) is the convexity of the squared norm, ∥ ( 1 − α ) a + α b ∥ 2 ≤ ( 1 − α ) ∥ a ∥ 2 + α ∥ b ∥ 2 \lVert(1-\alpha)a+\alpha b\rVert^2\le(1-\alpha)\lVert a\rVert^2+\alpha\lVert b\rVert^2 ∥( 1 − α ) a + α b ∥ 2 ≤ ( 1 − α ) ∥ a ∥ 2 + α ∥ b ∥ 2 with b = λ k ( F ( x k ) − F ( y k ) ) / α k b=\lambda_k(F(x_k)-F(y_k))/\alpha_k b = λ k ( F ( x k ) − F ( y k )) / α k , together with the inequality ⟨ F ( y k ) , y k − z ∗ ⟩ ≥ 0 \langle F(y_k),y_k-z^*\rangle\ge0 ⟨ F ( y k ) , y k − z ∗ ⟩ ≥ 0 . Summing and using u 0 = y 0 = s u_0=y_0=s u 0 = y 0 = s and (B.3), we obtain
∥ u k − y k ∥ 2 + 5 ∥ u k − z ∗ ∥ 2 + ∑ i = 1 k α i ∥ u i − 1 − y i − 1 ∥ 2 ≤ 5 R 2 + 22 3 R 2 = 37 3 R 2 . \lVert u_k-y_k\rVert^2+5\lVert u_k-z^*\rVert^2+\sum_{i=1}^{k}\alpha_i\lVert u_{i-1}-y_{i-1}\rVert^2\le5R^2+\frac{22}{3}R^2=\frac{37}{3}R^2. ∥ u k − y k ∥ 2 + 5 ∥ u k − z ∗ ∥ 2 + i = 1 ∑ k α i ∥ u i − 1 − y i − 1 ∥ 2 ≤ 5 R 2 + 3 22 R 2 = 3 37 R 2 .
Number of iterations of the second stage
Proof of Proposition 3.3 ▲. By construction, λ 1 ( L 0 + L 1 ∥ F ( s ) ∥ ) = 1 / 6 \lambda_1(L_0+L_1\lVert F(s)\rVert)=1/6 λ 1 ( L 0 + L 1 ∥ F ( s )∥) = 1/6 and λ k ( L 0 + L 1 B k ) ≤ 1 / 6 \lambda_k(L_0+L_1B_k)\le1/6 λ k ( L 0 + L 1 B k ) ≤ 1/6 for k ≥ 2 k\ge2 k ≥ 2 . We use the inequalities e 1 / 6 < 6 / 5 e^{1/6}<6/5 e 1/6 < 6/5 and e 1 / 5 < 5 / 4 e^{1/5}<5/4 e 1/5 < 5/4 .
▷ Admissibility of the step. For k = 1 k=1 k = 1 , we have x 1 = s x_1=s x 1 = s and ∥ x 1 − y 1 ∥ = λ 1 ∥ F ( s ) ∥ \lVert x_1-y_1\rVert=\lambda_1\lVert F(s)\rVert ∥ x 1 − y 1 ∥ = λ 1 ∥ F ( s )∥ , hence by Lemma 2.5 ,
λ 1 ∥ F ( x 1 ) − F ( y 1 ) ∥ ≤ e 1 / 6 6 ∥ x 1 − y 1 ∥ < 1 5 ∥ x 1 − y 1 ∥ . \lambda_1\lVert F(x_1)-F(y_1)\rVert\le\frac{e^{1/6}}{6}\lVert x_1-y_1\rVert<\frac{1}{5}\lVert x_1-y_1\rVert. λ 1 ∥ F ( x 1 ) − F ( y 1 )∥ ≤ 6 e 1/6 ∥ x 1 − y 1 ∥ < 5 1 ∥ x 1 − y 1 ∥ .
For k ≥ 2 k\ge2 k ≥ 2 , we have α k ≤ 3 λ k / ( 2 Λ k − 1 ) \alpha_k\le3\lambda_k/(2\Lambda_{k-1}) α k ≤ 3 λ k / ( 2 Λ k − 1 ) , hence the equality x k − y k − 1 = α k ( u k − 1 − y k − 1 ) − ( 1 − α k ) λ k F ( y k − 1 ) x_k-y_{k-1}=\alpha_k(u_{k-1}-y_{k-1})-(1-\alpha_k)\lambda_kF(y_{k-1}) x k − y k − 1 = α k ( u k − 1 − y k − 1 ) − ( 1 − α k ) λ k F ( y k − 1 ) implies ∥ x k − y k − 1 ∥ ≤ λ k B k \lVert x_k-y_{k-1}\rVert\le\lambda_kB_k ∥ x k − y k − 1 ∥ ≤ λ k B k , and L 1 λ k B k ≤ 1 / 6 L_1\lambda_kB_k\le1/6 L 1 λ k B k ≤ 1/6 . Applying Lemma 2.5 twice, we obtain
∥ F ( x k ) − F ( y k − 1 ) ∥ ≤ e 1 / 6 6 B k < 1 5 B k , \lVert F(x_k)-F(y_{k-1})\rVert\le\frac{e^{1/6}}{6}B_k<\frac{1}{5}B_k, ∥ F ( x k ) − F ( y k − 1 )∥ ≤ 6 e 1/6 B k < 5 1 B k ,
∥ F ( x k ) ∥ ≤ 6 5 B k , \lVert F(x_k)\rVert\le\frac{6}{5}B_k, ∥ F ( x k )∥ ≤ 5 6 B k ,
∥ x k − y k ∥ ≤ 6 5 λ k B k , \lVert x_k-y_k\rVert\le\frac{6}{5}\lambda_kB_k, ∥ x k − y k ∥ ≤ 5 6 λ k B k ,
λ k ∥ F ( x k ) − F ( y k ) ∥ ≤ 1 5 e 1 / 5 ∥ x k − y k ∥ < 1 4 ∥ x k − y k ∥ . \lambda_k\lVert F(x_k)-F(y_k)\rVert\le\frac{1}{5}e^{1/5}\lVert x_k-y_k\rVert<\frac{1}{4}\lVert x_k-y_k\rVert. λ k ∥ F ( x k ) − F ( y k )∥ ≤ 5 1 e 1/5 ∥ x k − y k ∥ < 4 1 ∥ x k − y k ∥ .
Thus, Lemma 3.2 applies.
▷ Change of the stepsize. For k ≥ 2 k\ge2 k ≥ 2 , the previous bounds give
∥ F ( y k ) ∥ ≤ 5 4 ⋅ 6 5 B k = 3 2 B k , \lVert F(y_k)\rVert\le\frac{5}{4}\cdot\frac{6}{5}B_k=\frac{3}{2}B_k, ∥ F ( y k )∥ ≤ 4 5 ⋅ 5 6 B k = 2 3 B k ,
∥ F ( x k ) − F ( y k ) ∥ + 5 6 ∥ F ( y k ) ∥ ≤ ( 3 10 + 5 4 ) B k = 31 20 B k . \lVert F(x_k)-F(y_k)\rVert+\frac{5}{6}\lVert F(y_k)\rVert\le\left(\frac{3}{10}+\frac{5}{4}\right)B_k=\frac{31}{20}B_k. ∥ F ( x k ) − F ( y k )∥ + 6 5 ∥ F ( y k )∥ ≤ ( 10 3 + 4 5 ) B k = 20 31 B k .
Let t = λ k / Λ k − 1 t=\lambda_k/\Lambda_{k-1} t = λ k / Λ k − 1 . Since λ k ≤ 4 λ k − 1 ≤ 4 Λ k − 1 \lambda_k\le4\lambda_{k-1}\le4\Lambda_{k-1} λ k ≤ 4 λ k − 1 ≤ 4 Λ k − 1 , we have t ≤ 4 t\le4 t ≤ 4 . By (B.1) and the inequality ∥ u k − 1 − y k − 1 ∥ ≤ 2 Λ k − 1 B k / 3 \lVert u_{k-1}-y_{k-1}\rVert\le2\Lambda_{k-1}B_k/3 ∥ u k − 1 − y k − 1 ∥ ≤ 2 Λ k − 1 B k /3 ,
B k + 1 B k ≤ 3 2 + 1 ( 1 + 3 t / 2 ) ( 1 + t ) + 93 40 ⋅ t 1 + t < 4 , \frac{B_{k+1}}{B_k}\le\frac{3}{2}+\frac{1}{(1+3t/2)(1+t)}+\frac{93}{40}\cdot\frac{t}{1+t}<4, B k B k + 1 ≤ 2 3 + ( 1 + 3 t /2 ) ( 1 + t ) 1 + 40 93 ⋅ 1 + t t < 4 ,
where for t ≤ 1 / 2 t\le1/2 t ≤ 1/2 the right-hand side is at most 3 / 2 + 1 + 31 / 40 3/2+1+31/40 3/2 + 1 + 31/40 , and for 1 / 2 ≤ t ≤ 4 1/2\le t\le4 1/2 ≤ t ≤ 4 it is at most 3 / 2 + 8 / 21 + 93 / 50 3/2+8/21+93/50 3/2 + 8/21 + 93/50 . For k = 1 k=1 k = 1 ,
∥ F ( y 1 ) ∥ ≤ 6 5 ∥ F ( s ) ∥ , \lVert F(y_1)\rVert\le\frac{6}{5}\lVert F(s)\rVert, ∥ F ( y 1 )∥ ≤ 5 6 ∥ F ( s )∥ ,
∥ u 1 − y 1 ∥ = λ 1 ∥ 5 6 F ( s ) − F ( y 1 ) − F ( s ) 6 ∥ ≤ 13 15 λ 1 ∥ F ( s ) ∥ , \lVert u_1-y_1\rVert=\lambda_1\left\lVert\frac{5}{6}F(s)-\frac{F(y_1)-F(s)}{6}\right\rVert\le\frac{13}{15}\lambda_1\lVert F(s)\rVert, ∥ u 1 − y 1 ∥ = λ 1 6 5 F ( s ) − 6 F ( y 1 ) − F ( s ) ≤ 15 13 λ 1 ∥ F ( s )∥ ,
hence B 2 ≤ 5 2 ∥ F ( s ) ∥ B_2\le\frac{5}{2}\lVert F(s)\rVert B 2 ≤ 2 5 ∥ F ( s )∥ . Both arguments of the minimum at the next iteration are at least λ k / 4 \lambda_k/4 λ k /4 , that is, λ k + 1 ≥ λ k / 4 \lambda_{k+1}\ge\lambda_k/4 λ k + 1 ≥ λ k /4 .
▷ Sum of the stepsizes. The function log ( 1 + t ) / t \log(1+t)/t log ( 1 + t ) / t is decreasing, hence log ( 1 + t ) ≥ ( log 5 / 4 ) t ≥ 2 t / 5 \log(1+t)\ge(\log5/4)t\ge2t/5 log ( 1 + t ) ≥ ( log 5/4 ) t ≥ 2 t /5 for 0 ≤ t ≤ 4 0\le t\le4 0 ≤ t ≤ 4 and
∑ k = 2 K λ k Λ k − 1 ≤ 5 2 log Λ K λ 1 . \sum_{k=2}^{K}\frac{\lambda_k}{\Lambda_{k-1}}\le\frac{5}{2}\log\frac{\Lambda_K}{\lambda_1}. k = 2 ∑ K Λ k − 1 λ k ≤ 2 5 log λ 1 Λ K .
Moreover, λ k / Λ k − 1 = ( 2 / 3 + λ k / Λ k − 1 ) α k ≤ 14 α k / 3 \lambda_k/\Lambda_{k-1}=(2/3+\lambda_k/\Lambda_{k-1})\alpha_k\le14\alpha_k/3 λ k / Λ k − 1 = ( 2/3 + λ k / Λ k − 1 ) α k ≤ 14 α k /3 and λ k Λ k − 1 ≤ 4 λ k − 1 Λ k − 1 \lambda_k\Lambda_{k-1}\le4\lambda_{k-1}\Lambda_{k-1} λ k Λ k − 1 ≤ 4 λ k − 1 Λ k − 1 . By Lemma 3.2 and the Cauchy–Schwarz inequality,
∑ k = 2 K λ k ∥ F ( y k − 1 ) ∥ ≤ ( ∑ k = 2 K λ k Λ k − 1 ∥ F ( y k − 1 ) ∥ 2 ) 1 / 2 ( ∑ k = 2 K λ k Λ k − 1 ) 1 / 2 ≤ 6 R 5 2 log Λ K λ 1 , \sum_{k=2}^{K}\lambda_k\lVert F(y_{k-1})\rVert\le\left(\sum_{k=2}^{K}\lambda_k\Lambda_{k-1}\lVert F(y_{k-1})\rVert^2\right)^{1/2}\left(\sum_{k=2}^{K}\frac{\lambda_k}{\Lambda_{k-1}}\right)^{1/2}\le6R\sqrt{\frac{5}{2}\log\frac{\Lambda_K}{\lambda_1}}, k = 2 ∑ K λ k ∥ F ( y k − 1 )∥ ≤ ( k = 2 ∑ K λ k Λ k − 1 ∥ F ( y k − 1 ) ∥ 2 ) 1/2 ( k = 2 ∑ K Λ k − 1 λ k ) 1/2 ≤ 6 R 2 5 log λ 1 Λ K ,
∑ k = 2 K λ k Λ k − 1 ∥ u k − 1 − y k − 1 ∥ ≤ ( 14 3 ⋅ 37 3 R 2 ) 1 / 2 ( 5 2 log Λ K λ 1 ) 1 / 2 ≤ 12 R log Λ K λ 1 . \sum_{k=2}^{K}\frac{\lambda_k}{\Lambda_{k-1}}\lVert u_{k-1}-y_{k-1}\rVert\le\left(\frac{14}{3}\cdot\frac{37}{3}R^2\right)^{1/2}\left(\frac{5}{2}\log\frac{\Lambda_K}{\lambda_1}\right)^{1/2}\le12R\sqrt{\log\frac{\Lambda_K}{\lambda_1}}. k = 2 ∑ K Λ k − 1 λ k ∥ u k − 1 − y k − 1 ∥ ≤ ( 3 14 ⋅ 3 37 R 2 ) 1/2 ( 2 5 log λ 1 Λ K ) 1/2 ≤ 12 R log λ 1 Λ K .
Let N A N_A N A be the number of iterations k ≥ 2 k \ge2 k ≥ 2 with λ k = 1 / ( 6 ( L 0 + L 1 B k ) ) \lambda_k = 1/(6(L_0 + L_1B_k)) λ k = 1/ ( 6 ( L 0 + L 1 B k )) . Then
N A ≤ 6 ∑ k = 2 K λ k ( L 0 + L 1 B k ) N_A \le6\sum_{k=2}^{K}\lambda_k(L_0+L_1B_k) N A ≤ 6 k = 2 ∑ K λ k ( L 0 + L 1 B k )
≤ 6 L 0 Λ K + 6 L 1 R ( 6 5 2 + 3 2 ⋅ 12 ) log Λ K λ 1 ≤ 6 L 0 Λ K + 165 L 1 R log Λ K λ 1 , \le6L_0\Lambda_K + 6L_1R\left(6\sqrt{\frac{5}{2}}+\frac{3}{2}\cdot12\right)\sqrt{\log\frac{\Lambda_K}{\lambda_1}} \le6L_0\Lambda_K + 165L_1R\sqrt{\log\frac{\Lambda_K}{\lambda_1}}, ≤ 6 L 0 Λ K + 6 L 1 R ( 6 2 5 + 2 3 ⋅ 12 ) log λ 1 Λ K ≤ 6 L 0 Λ K + 165 L 1 R log λ 1 Λ K ,
since 6 5 / 2 < 19 / 2 6\sqrt{5/2}<19/2 6 5/2 < 19/2 . On each of the remaining K − 1 − N A K-1-N_A K − 1 − N A iterations, the stepsize increases fourfold, and on iterations of the first type it decreases at most fourfold. Therefore,
( K − 1 − N A ) log 4 − N A log 4 ≤ log λ K λ 1 ≤ log Λ K λ 1 , (K-1-N_A)\log4-N_A\log4\le\log\frac{\lambda_K}{\lambda_1}\le\log\frac{\Lambda_K}{\lambda_1}, ( K − 1 − N A ) log 4 − N A log 4 ≤ log λ 1 λ K ≤ log λ 1 Λ K ,
whence
K ≤ 1 + 2 N A + 1 log 4 log Λ K λ 1 . K\le1+2N_A+\frac{1}{\log4}\log\frac{\Lambda_K}{\lambda_1}. K ≤ 1 + 2 N A + log 4 1 log λ 1 Λ K .
Termination. As long as Λ K − 1 < 3 R / ε \Lambda_{K-1}<3R/\varepsilon Λ K − 1 < 3 R / ε , we have
Λ K < 3 R ε + 1 6 L 0 , \Lambda_K<\frac{3R}{\varepsilon}+\frac{1}{6L_0}, Λ K < ε 3 R + 6 L 0 1 ,
log Λ K λ 1 ≤ H . \log\frac{\Lambda_K}{\lambda_1}\le\mathcal{H}. log λ 1 Λ K ≤ H .
Substitution gives
K ≤ 1 + 2 ( 18 L 0 R ε + 1 + 165 L 1 R H ) + H log 4 ≤ 3 + 36 L 0 R ε + 330 L 1 R H + H . K\le1+2\left(\frac{18L_0R}{\varepsilon}+1+165L_1R\sqrt{\mathcal{H}}\right)+\frac{\mathcal{H}}{\log4}\le3+\frac{36L_0R}{\varepsilon}+330L_1R\sqrt{\mathcal{H}}+\mathcal{H}. K ≤ 1 + 2 ( ε 18 L 0 R + 1 + 165 L 1 R H ) + log 4 H ≤ 3 + ε 36 L 0 R + 330 L 1 R H + H .
Infinitely many iterations with Λ K < 3 R / ε \Lambda_K<3R/\varepsilon Λ K < 3 R / ε would contradict this bound. When Λ K ≥ 3 R / ε \Lambda_K\ge3R/\varepsilon Λ K ≥ 3 R / ε , Lemma 3.2 guarantees termination.
Location of the point. By the inequality ( x + y ) 2 ≤ 6 5 x 2 + 6 y 2 (x+y)^2\le\frac{6}{5}x^2+6y^2 ( x + y ) 2 ≤ 5 6 x 2 + 6 y 2 and Lemma 3.2,
∥ y K − z ∗ ∥ 2 ≤ 6 5 ( ∥ y K − u K ∥ 2 + 5 ∥ u K − z ∗ ∥ 2 ) ≤ 74 5 R 2 < 16 R 2 . \lVert y_K-z^*\rVert^2\le\frac{6}{5}\left(\lVert y_K-u_K\rVert^2+5\lVert u_K-z^*\rVert^2\right)\le\frac{74}{5}R^2<16R^2. ∥ y K − z ∗ ∥ 2 ≤ 5 6 ( ∥ y K − u K ∥ 2 + 5 ∥ u K − z ∗ ∥ 2 ) ≤ 5 74 R 2 < 16 R 2 .
Final bound
Proof of Theorem 3.4. If ABSEIL outputs the point s s s without running BELAY, then it satisfies ∥ F ( s ) ∥ ≤ ε \lVert F(s)\rVert\le\varepsilon ∥ F ( s )∥ ≤ ε and ∥ s − z ∗ ∥ ≤ R \lVert s-z^*\rVert\le R ∥ s − z ∗ ∥ ≤ R by (6) , and therefore ∥ s − z 0 ∥ ≤ 2 R \lVert s-z_0\rVert\le2R ∥ s − z 0 ∥ ≤ 2 R . Otherwise, the output is the point y K y_K y K of the second stage, and by Proposition 3.3 and (6) , ∥ y K − z 0 ∥ ≤ ∥ y K − z ∗ ∥ + ∥ z ∗ − z 0 ∥ < 4 R + R = 5 R \lVert y_K-z_0\rVert\le\lVert y_K-z^*\rVert+\lVert z^*-z_0\rVert<4R+R=5R ∥ y K − z 0 ∥ ≤ ∥ y K − z ∗ ∥ + ∥ z ∗ − z 0 ∥ < 4 R + R = 5 R . We now bound the number of oracle calls. The first stage makes J J J steps, and the second one makes K K K iterations, so the total number of calls is at most 1 + J + 2 K 1+J+2K 1 + J + 2 K .
Case L 1 R < 1 L_1R<1 L 1 R < 1 . Then J = 0 J=0 J = 0 , s = z 0 s=z_0 s = z 0 , and by Lemma 2.5(b), L 1 ∥ F ( z 0 ) ∥ ≤ L 0 ( e L 1 R − 1 ) ≤ 2 L 0 L_1\lVert F(z_0)\rVert\le L_0(e^{L_1R}-1)\le2L_0 L 1 ∥ F ( z 0 )∥ ≤ L 0 ( e L 1 R − 1 ) ≤ 2 L 0 . Therefore, H ≤ log ( 3 + 54 L 0 R / ε ) \mathcal{H}\le\log(3+54L_0R/\varepsilon) H ≤ log ( 3 + 54 L 0 R / ε ) and
K ≤ 3 + 36 L 0 R ε + 330 H + H ≲ 1 + L 0 R ε . K\le3+\frac{36L_0R}{\varepsilon}+330\sqrt{\mathcal{H}}+\mathcal{H}\lesssim1+\frac{L_0R}{\varepsilon}. K ≤ 3 + ε 36 L 0 R + 330 H + H ≲ 1 + ε L 0 R .
Case L 1 R ≥ 1 L_1R\ge1 L 1 R ≥ 1 . By Lemma 3.1, J ≤ 4 ( L 1 R ) 6 / 5 J\le4(L_1R)^{6/5} J ≤ 4 ( L 1 R ) 6/5 . By (6) , L 0 + L 1 ∥ F ( s ) ∥ ≤ L 0 ( 1 + 4 L 1 R e ( L 1 R ) 2 / 5 ) L_0+L_1\lVert F(s)\rVert\le L_0(1+4L_1Re^{(L_1R)^{2/5}}) L 0 + L 1 ∥ F ( s )∥ ≤ L 0 ( 1 + 4 L 1 R e ( L 1 R ) 2/5 ) , hence
H ≤ log ( 1 + 18 L 0 R ε ) + log ( 1 + 4 L 1 R ) + ( L 1 R ) 2 / 5 . \mathcal{H}\le\log\left(1+\frac{18L_0R}{\varepsilon}\right)+\log(1+4L_1R)+(L_1R)^{2/5}. H ≤ log ( 1 + ε 18 L 0 R ) + log ( 1 + 4 L 1 R ) + ( L 1 R ) 2/5 .
Using x + y + z ≤ x + y + z \sqrt{x+y+z}\le\sqrt{x}+\sqrt{y}+\sqrt{z} x + y + z ≤ x + y + z and the inequality
log ( 1 + 18 L 0 R ε ) ≤ log 19 + log + L 0 R ε ≤ log 19 + log ( L 1 R ) + L 0 R ε L 1 R , \log\left(1+\frac{18L_0R}{\varepsilon}\right)\le\log19+\log_+\frac{L_0R}{\varepsilon}\le\log19+\log(L_1R)+\frac{L_0R}{\varepsilon L_1R}, log ( 1 + ε 18 L 0 R ) ≤ log 19 + log + ε L 0 R ≤ log 19 + log ( L 1 R ) + ε L 1 R L 0 R ,
which follows from log x ≤ x \log x\le x log x ≤ x with x = L 0 R / ( ε L 1 R ) x=L_0R/(\varepsilon L_1R) x = L 0 R / ( ε L 1 R ) , we obtain
L 1 R H ≤ L 1 R log 19 + log ( L 1 R ) + L 0 R ε L 1 R + L 1 R log ( 1 + 4 L 1 R ) + ( L 1 R ) 6 / 5 L_1R\sqrt{\mathcal{H}}\le L_1R\sqrt{\log19+\log(L_1R)}+\sqrt{\frac{L_0R}{\varepsilon}L_1R+L_1R\sqrt{\log(1+4L_1R)}+(L_1R)^{6/5}} L 1 R H ≤ L 1 R log 19 + log ( L 1 R ) + ε L 0 R L 1 R + L 1 R log ( 1 + 4 L 1 R ) + ( L 1 R ) 6/5
≲ ( a ) L 0 R ε + ( L 1 R ) 6 / 5 , \lesssim_{(a)}\frac{L_0R}{\varepsilon}+(L_1R)^{6/5}, ≲ ( a ) ε L 0 R + ( L 1 R ) 6/5 ,
where (a) consists of the inequalities x y ≤ ( x + y ) / 2 \sqrt{xy} \le(x+y)/2 x y ≤ ( x + y ) /2 and log ( 1 + 4 x ) ≲ x 2 / 5 \log(1+4x) \lesssim x^{2/5} log ( 1 + 4 x ) ≲ x 2/5 for x ≥ 1 x \ge1 x ≥ 1 . Similarly, H ≲ 1 + L 0 R / ε + ( L 1 R ) 2 / 5 \mathcal{H} \lesssim1 + L_0R/\varepsilon+ (L_1R)^{2/5} H ≲ 1 + L 0 R / ε + ( L 1 R ) 2/5 . Therefore,
1 + J + 2 K ≲ 1 + L 0 R ε + ( L 1 R ) 6 / 5 . 1 + J + 2K \lesssim1 + \frac{L_0R}{\varepsilon} + (L_1R)^{6/5}. 1 + J + 2 K ≲ 1 + ε L 0 R + ( L 1 R ) 6/5 .
Finally, for ε = η / ( 6 R ) \varepsilon= \eta/(6R) ε = η / ( 6 R ) , we have L 0 R / ε = 6 L 0 R 2 / η L_0R/\varepsilon= 6L_0R^2/\eta L 0 R / ε = 6 L 0 R 2 / η , and by Lemma 2.6 ,
Gap R ( z ^ ) ≤ ( ∥ z ^ − z 0 ∥ + R ) ∥ F ( z ^ ) ∥ ≤ 6 R ⋅ η 6 R = η . \operatorname{Gap}_R(\hat{z}) \le(\|\hat{z}-z_0\| + R)\|F(\hat{z})\| \le6R \cdot\frac{\eta}{6R} = \eta. Gap R ( z ^ ) ≤ ( ∥ z ^ − z 0 ∥ + R ) ∥ F ( z ^ ) ∥ ≤ 6 R ⋅ 6 R η = η .
Proofs of the lower bounds
The proofs follow the order of the construction in § 4 : curvature and inversion, revelation of one coordinate at a time, the radius, smoothing and the test point, coordinate hiding, and then the linear term. Below, f = Q + I K f = Q + I_K f = Q + I K , s = 1 T v s = \mathbf{1}^{\mathsf{T}}v s = 1 T v and r = ∥ v ∥ r = \|v\| r = ∥ v ∥ .
Curvature of Q and properties of the inverse operator
Bounds {(4.4)} and the inequalities ϑ ≤ A \vartheta\le A ϑ ≤ A , γ v i + ( B v ) i ≤ C \gamma v_i + (Bv)_i \le C γ v i + ( B v ) i ≤ C from § 4.3 are verified as follows.
Gradient formula. For v ≠ 0 v \ne0 v = 0 , the derivative of the first term of Q Q Q with respect to each coordinate equals 2 log ( 1 + ℓ 1 s / ℓ 0 ) / ℓ 1 2\log(1+\ell_1s/\ell_0)/\ell_1 2 log ( 1 + ℓ 1 s / ℓ 0 ) / ℓ 1 . For the second term, ∂ i r = v i / r \partial_i r = v_i/r ∂ i r = v i / r and ∂ i s = 1 \partial_i s = 1 ∂ i s = 1 give
∂ i [ r log n r s ] = v i r ( 1 + log n r s ) − r s , \partial_i\left[r\log\frac{\sqrt{nr}}{s}\right]
= \frac{v_i}{r}\left(1+\log\frac{\sqrt{nr}}{s}\right)-\frac{r}{s}, ∂ i [ r log s n r ] = r v i ( 1 + log s n r ) − s r ,
which yields {(4.3)}.
Bounds on ϑ \vartheta ϑ and γ \gamma γ . On K K K we have r ≤ s ≤ G 1 r \le s \le G_1 r ≤ s ≤ G 1 and 1 ≤ n r / s ≤ n 1 \le\sqrt{nr}/s \le\sqrt{n} 1 ≤ n r / s ≤ n . Therefore, the first term of ϑ \vartheta ϑ is at most 2 log ( 1 + ℓ 1 G 1 / ℓ 0 ) / ℓ 1 = A 2\log(1+\ell_1G_1/\ell_0)/\ell_1 = A 2 log ( 1 + ℓ 1 G 1 / ℓ 0 ) / ℓ 1 = A , and the second one is nonpositive. Moreover, 0 ≤ γ v i ≤ γ r ≤ 4 log ( e n ) / ℓ 1 0 \le\gamma v_i \le\gamma r \le4\log(e\sqrt{n})/\ell_1 0 ≤ γ v i ≤ γ r ≤ 4 log ( e n ) / ℓ 1 , which implies {(4.4)}.
Bound on B v Bv B v . We have ∣ ( B v ) i ∣ ≤ 5 m log ( e n ) / ℓ 1 |(Bv)_i| \le5\sqrt{m}\log(e\sqrt{n})/\ell_1 ∣ ( B v ) i ∣ ≤ 5 m log ( e n ) / ℓ 1 . The last bound follows from the fact that the sum of the coordinates of v v v belonging to one block does not exceed the weight of this block: ∑ b ℓ ( k ) = b ℓ ( i ) v k ≤ G i \sum_{b\ell(k)=b\ell(i)} v_k \le G_i ∑ b ℓ ( k ) = b ℓ ( i ) v k ≤ G i . Together with the previous item, this gives γ v i + ( B v ) i ≤ C \gamma v_i + (Bv)_i \le C γ v i + ( B v ) i ≤ C .
Proof of Lemma 4.3 ▲.
Hessian of the second part. Let p = v / s p = v/s p = v / s , α = 1 T ξ \alpha= \mathbf{1}^{\mathsf{T}}\xi α = 1 T ξ and ξ ⊥ = ξ − p α \xi_\perp= \xi- p\alpha ξ ⊥ = ξ − p α . Then 1 T p = 1 \mathbf{1}^{\mathsf{T}}p = 1 1 T p = 1 , ∥ p ∥ ≤ 1 \|p\| \le1 ∥ p ∥ ≤ 1 and ξ = p α + ξ ⊥ \xi= p\alpha+ \xi_\perp ξ = p α + ξ ⊥ . The second part of Q Q Q equals s a ( p ) s\,a(p) s a ( p ) , where a ( p ) = 4 ∥ p ∥ log ( n ∥ p ∥ ) / ℓ 1 a(p) = 4\|p\|\log(\sqrt{n}\|p\|)/\ell_1 a ( p ) = 4∥ p ∥ log ( n ∥ p ∥ ) / ℓ 1 . For the radial function a ( p ) = b ( ∥ p ∥ ) a(p) = b(\|p\|) a ( p ) = b ( ∥ p ∥ ) with r p = ∥ p ∥ r_p = \|p\| r p = ∥ p ∥ , we have
∇ 2 a ( p ) = b ′ ( r p ) r p ( I − p p T r p 2 ) + b ′ ′ ( r p ) p p T r p 2 . \nabla^2a(p) = \frac{b'(r_p)}{r_p}\left(I-\frac{pp^{\mathsf{T}}}{r_p^2}\right)+b''(r_p)\frac{pp^{\mathsf{T}}}{r_p^2}. ∇ 2 a ( p ) = r p b ′ ( r p ) ( I − r p 2 p p T ) + b ′′ ( r p ) r p 2 p p T .
Here b ′ ( r p ) = 4 ( 1 + log ( n r p ) ) / ℓ 1 b'(r_p) = 4(1+\log(\sqrt{n}r_p))/\ell_1 b ′ ( r p ) = 4 ( 1 + log ( n r p )) / ℓ 1 and b ′ ′ ( r p ) = 4 / ( ℓ 1 r p ) b''(r_p) = 4/(\ell_1r_p) b ′′ ( r p ) = 4/ ( ℓ 1 r p ) , hence
∇ 2 a ( p ) = 4 ℓ 1 r p [ I + log ( n r p ) ( I − p p T r p 2 ) ] ⪰ 4 ℓ 1 r p I . \nabla^2a(p) = \frac{4}{\ell_1r_p}\left[I+\log(\sqrt{n}r_p)\left(I-\frac{pp^{\mathsf{T}}}{r_p^2}\right)\right] \succeq\frac{4}{\ell_1r_p}I. ∇ 2 a ( p ) = ℓ 1 r p 4 [ I + log ( n r p ) ( I − r p 2 p p T ) ] ⪰ ℓ 1 r p 4 I .
The inequality holds because the logarithm is nonnegative and the matrix in parentheses after it is an orthogonal projector.
Second derivative along a line. Let v ( t ) = v + t ξ v(t) = v + t\xi v ( t ) = v + t ξ , s ( t ) = s + t α s(t) = s + t\alpha s ( t ) = s + t α and p ( t ) = v ( t ) / s ( t ) p(t) = v(t)/s(t) p ( t ) = v ( t ) / s ( t ) . Then p ′ ( 0 ) = ξ ⊥ / s p'(0) = \xi_\perp/s p ′ ( 0 ) = ξ ⊥ / s and p ′ ′ ( 0 ) = − 2 α ξ ⊥ / s 2 p''(0) = -2\alpha\xi_\perp/s^2 p ′′ ( 0 ) = − 2 α ξ ⊥ / s 2 . The second derivative of s ( t ) a ( p ( t ) ) s(t)a(p(t)) s ( t ) a ( p ( t )) at zero equals
2 α ⟨ ∇ a , p ′ ⟩ + s ⟨ ∇ 2 a p ′ , p ′ ⟩ + s ⟨ ∇ a , p ′ ′ ⟩ = 1 s ⟨ ∇ 2 a ξ ⊥ , ξ ⊥ ⟩ , 2\alpha\langle\nabla a,p'\rangle+s\langle\nabla^2a\,p',p'\rangle+s\langle\nabla a,p''\rangle
=\frac{1}{s}\langle\nabla^2a\,\xi_\perp,\xi_\perp\rangle, 2 α ⟨ ∇ a , p ′ ⟩ + s ⟨ ∇ 2 a p ′ , p ′ ⟩ + s ⟨ ∇ a , p ′′ ⟩ = s 1 ⟨ ∇ 2 a ξ ⊥ , ξ ⊥ ⟩ ,
since the first and third terms cancel. Hence,
D 2 Q ( v ) [ ξ , ξ ] ≥ 2 α 2 ℓ 0 + ℓ 1 s + 4 ∥ ξ ⊥ ∥ 2 ℓ 1 ∥ v ∥ . D^2Q(v)[\xi,\xi] \ge\frac{2\alpha^2}{\ell_0+\ell_1s}+\frac{4\|\xi_\perp\|^2}{\ell_1\|v\|}. D 2 Q ( v ) [ ξ , ξ ] ≥ ℓ 0 + ℓ 1 s 2 α 2 + ℓ 1 ∥ v ∥ 4∥ ξ ⊥ ∥ 2 .
Lower bound on the curvature. Let D v = ℓ 0 + ℓ 1 s ∥ p ∥ D_v=\ell_0+\ell_1s\lVert p\rVert D v = ℓ 0 + ℓ 1 s ∥ p ∥ . Since 0 ≤ ∥ p ∥ ≤ 1 0\leq\lVert p\rVert\leq1 0 ≤ ∥ p ∥ ≤ 1 ,
D v − ∥ p ∥ 2 ( ℓ 0 + ℓ 1 s ) = ℓ 0 ( 1 − ∥ p ∥ 2 ) + ℓ 1 s ( ∥ p ∥ − ∥ p ∥ 2 ) ≥ 0. D_v-\lVert p\rVert^2(\ell_0+\ell_1s)=\ell_0(1-\lVert p\rVert^2)+\ell_1s(\lVert p\rVert-\lVert p\rVert^2)\geq0. D v − ∥ p ∥ 2 ( ℓ 0 + ℓ 1 s ) = ℓ 0 ( 1 − ∥ p ∥ 2 ) + ℓ 1 s (∥ p ∥ − ∥ p ∥ 2 ) ≥ 0.
Moreover, 4 / ( ℓ 1 ∥ v ∥ ) ≥ 2 / D v 4/(\ell_1\lVert v\rVert)\geq2/D_v 4/ ( ℓ 1 ∥ v ∥) ≥ 2/ D v . Therefore,
D 2 Q ( v ) [ ξ , ξ ] ≥ 2 ∥ p ∥ 2 α 2 + 2 ∥ ξ ⊥ ∥ 2 D v ≥ ( a ) ∥ ξ ∥ 2 ℓ 0 + ℓ 1 ∥ v ∥ , D^2Q(v)[\xi,\xi]\geq\frac{2\lVert p\rVert^2\alpha^2+2\lVert\xi_{\perp}\rVert^2}{D_v}\overset{(a)}{\geq}\frac{\lVert\xi\rVert^2}{\ell_0+\ell_1\lVert v\rVert}, D 2 Q ( v ) [ ξ , ξ ] ≥ D v 2 ∥ p ∥ 2 α 2 + 2 ∥ ξ ⊥ ∥ 2 ≥ ( a ) ℓ 0 + ℓ 1 ∥ v ∥ ∥ ξ ∥ 2 ,
where (a) is the inequality ∥ a + b ∥ 2 ≤ 2 ∥ a ∥ 2 + 2 ∥ b ∥ 2 \lVert a+b\rVert^2\leq2\lVert a\rVert^2+2\lVert b\rVert^2 ∥ a + b ∥ 2 ≤ 2 ∥ a ∥ 2 + 2 ∥ b ∥ 2 .
Generalized strong monotonicity. The notation a ∈ ∂ f ( v ) a\in\partial f(v) a ∈ ∂ f ( v ) means f ( w ) ≥ f ( v ) + ⟨ a , w − v ⟩ f(w)\geq f(v)+\langle a,w-v\rangle f ( w ) ≥ f ( v ) + ⟨ a , w − v ⟩ for all w w w . The function Q Q Q is convex by the Hessian bound just proved. It is nonnegative and continuous at zero: the first term is O ( s 2 ) O(s^2) O ( s 2 ) , and the second one is at most 4 ∥ v ∥ log n / ℓ 1 4\lVert v\rVert\log\sqrt{n}/\ell_1 4 ∥ v ∥ log n / ℓ 1 . For v , v ′ ∈ K v,v'\in K v , v ′ ∈ K , set V = max { ∥ v ∥ , ∥ v ′ ∥ } V=\max\{\lVert v\rVert,\lVert v'\rVert\} V = max {∥ v ∥ , ∥ v ′ ∥} . On the segment between them the norm is at most V V V , so integrating the curvature gives the strong convexity inequality with coefficient 1 / ( ℓ 0 + ℓ 1 V ) 1/(\ell_0+\ell_1V) 1/ ( ℓ 0 + ℓ 1 V ) . At a boundary point we use the one-sided derivative, and at zero the continuous extension along the segment. For any a ∈ ∂ f ( v ) a\in\partial f(v) a ∈ ∂ f ( v ) and a ′ ∈ ∂ f ( v ′ ) a'\in\partial f(v') a ′ ∈ ∂ f ( v ′ ) , we obtain
f ( v ′ ) ≥ f ( v ) + ⟨ a , v ′ − v ⟩ + ∥ v − v ′ ∥ 2 2 ( ℓ 0 + ℓ 1 V ) , f(v')\geq f(v)+\langle a,v'-v\rangle+\frac{\lVert v-v'\rVert^2}{2(\ell_0+\ell_1V)}, f ( v ′ ) ≥ f ( v ) + ⟨ a , v ′ − v ⟩ + 2 ( ℓ 0 + ℓ 1 V ) ∥ v − v ′ ∥ 2 ,
f ( v ) ≥ f ( v ′ ) + ⟨ a ′ , v − v ′ ⟩ + ∥ v − v ′ ∥ 2 2 ( ℓ 0 + ℓ 1 V ) . f(v)\geq f(v')+\langle a',v-v'\rangle+\frac{\lVert v-v'\rVert^2}{2(\ell_0+\ell_1V)}. f ( v ) ≥ f ( v ′ ) + ⟨ a ′ , v − v ′ ⟩ + 2 ( ℓ 0 + ℓ 1 V ) ∥ v − v ′ ∥ 2 .
Adding these inequalities, we obtain
⟨ a − a ′ , v − v ′ ⟩ ≥ ∥ v − v ′ ∥ 2 ℓ 0 + ℓ 1 V . (19) \langle a-a',v-v'\rangle\geq\frac{\lVert v-v'\rVert^2}{\ell_0+\ell_1V}. \tag*{(19)} ⟨ a − a ′ , v − v ′ ⟩ ≥ ℓ 0 + ℓ 1 V ∥ v − v ′ ∥ 2 . (19)
Existence of a solution. Define
prox f ( x ) = arg min w ∈ K { Q ( w ) + 1 2 ∥ w − x ∥ 2 } . \operatorname{prox}_f(x)=\mathop{\arg\min}_{w\in K}\left\{Q(w)+\frac{1}{2}\lVert w-x\rVert^2\right\}. prox f ( x ) = arg min w ∈ K { Q ( w ) + 2 1 ∥ w − x ∥ 2 } .
The minimum exists by compactness and is unique because the quadratic term is strictly convex. The optimality condition x − prox f ( x ) ∈ ∂ f ( prox f ( x ) ) x-\operatorname{prox}_f(x)\in\partial f(\operatorname{prox}_f(x)) x − prox f ( x ) ∈ ∂ f ( prox f ( x )) and the monotonicity of the subdifferential imply that this map is nonexpansive and hence continuous. By Brouwer’s theorem, the continuous map v ↦ prox f ( v − B v + u + σ ) v\mapsto\operatorname{prox}_f(v-Bv+u+\sigma) v ↦ prox f ( v − B v + u + σ ) from K K K into itself has a fixed point. This is exactly a solution of (8) .
Uniqueness, monotonicity and Lipschitz continuity. For solutions v , v ′ v,v' v , v ′ corresponding to queries u , u ′ u,u' u , u ′ , substitute a = u + σ − B v a=u+\sigma-Bv a = u + σ − B v and a ′ = u ′ + σ − B v ′ a'=u'+\sigma-Bv' a ′ = u ′ + σ − B v ′ into (C.1). Skew-symmetry eliminates B B B :
⟨ u − u ′ , v − v ′ ⟩ ≥ ∥ v − v ′ ∥ 2 ℓ 0 + ℓ 1 V . \langle u-u',v-v'\rangle\geq\frac{\lVert v-v'\rVert^2}{\ell_0+\ell_1V}. ⟨ u − u ′ , v − v ′ ⟩ ≥ ℓ 0 + ℓ 1 V ∥ v − v ′ ∥ 2 .
For u = u ′ u=u' u = u ′ we obtain v = v ′ v=v' v = v ′ , that is, uniqueness. For different queries this is the monotonicity of Φ \Phi Φ . By the Cauchy–Schwarz inequality, we also have
∥ Φ ( u ) − Φ ( u ′ ) ∥ ≤ ( ℓ 0 + ℓ 1 max { ∥ Φ ( u ) ∥ , ∥ Φ ( u ′ ) ∥ } ) ∥ u − u ′ ∥ . \lVert\Phi(u)-\Phi(u')\rVert\leq\bigl(\ell_0+\ell_1\max\{\lVert\Phi(u)\rVert,\lVert\Phi(u')\rVert\}\bigr)\lVert u-u'\rVert. ∥ Φ ( u ) − Φ ( u ′ )∥ ≤ ( ℓ 0 + ℓ 1 max {∥ Φ ( u )∥ , ∥ Φ ( u ′ )∥} ) ∥ u − u ′ ∥ .
The maximum at the endpoints does not exceed the supremum over the segment, so condition (1) holds. Finally, ∥ Φ ∥ ≤ G 1 \lVert\Phi\rVert\leq G_1 ∥ Φ ∥ ≤ G 1 and Φ ( − σ ) = 0 \Phi(-\sigma)=0 Φ ( − σ ) = 0 , since 0 ∈ ∂ f ( 0 ) 0\in\partial f(0) 0 ∈ ∂ f ( 0 ) .
KKT conditions from the geometry of the simplex
At a point v ≠ 0 v\neq0 v = 0 we have ∂ f ( v ) = ∇ Q ( v ) + N K ( v ) \partial f(v)=\nabla Q(v)+N_K(v) ∂ f ( v ) = ∇ Q ( v ) + N K ( v ) . Let y ∈ N K ( v ) y\in N_K(v) y ∈ N K ( v ) . The maximum of the linear function ⟨ y , w ⟩ \langle y,w\rangle ⟨ y , w ⟩ over K K K equals ζ = max { 0 , G 1 y 1 , … , G n y n } \zeta=\max\{0,G_1y_1,\ldots,G_ny_n\} ζ = max { 0 , G 1 y 1 , … , G n y n } , since it suffices to check the vertices. It is attained at v v v . Set λ i = ζ / G i − y i ≥ 0 \lambda_i=\zeta/G_i-y_i\geq0 λ i = ζ / G i − y i ≥ 0 . Then
ζ = ⟨ y , v ⟩ = ζ ∑ i v i G i − ∑ i λ i v i , \zeta=\langle y,v\rangle=\zeta\sum_i\frac{v_i}{G_i}-\sum_i\lambda_iv_i, ζ = ⟨ y , v ⟩ = ζ i ∑ G i v i − i ∑ λ i v i ,
whence ζ ( 1 − ∑ i v i / G i ) + ∑ i λ i v i = 0 \zeta\left(1-\sum_i v_i/G_i\right)+\sum_i\lambda_i v_i=0 ζ ( 1 − ∑ i v i / G i ) + ∑ i λ i v i = 0 . All terms are nonnegative, so each of them is zero. We obtain y i = ζ / G i − λ i y_i=\zeta/G_i-\lambda_i y i = ζ / G i − λ i , λ i v i = 0 \lambda_i v_i=0 λ i v i = 0 and the complementary slackness condition. Substituting into inclusion (8) and taking (10) into account gives the KKT conditions: for some ζ ≥ 0 \zeta\geq0 ζ ≥ 0 ,
u i + σ i − ϑ − γ v i − ( B v ) i − ζ / G i { = 0 , v i > 0 , ≤ 0 , v i = 0 , (20) u_i+\sigma_i-\vartheta-\gamma v_i-(Bv)_i-\zeta/G_i
\begin{cases}
=0, & v_i>0,\\
\leq0, & v_i=0,
\end{cases} \tag*{(20)} u i + σ i − ϑ − γ v i − ( B v ) i − ζ / G i { = 0 , ≤ 0 , v i > 0 , v i = 0 , (20)
and ζ ( 1 − ∑ i v i / G i ) = 0 \zeta\left(1-\sum_i v_i/G_i\right)=0 ζ ( 1 − ∑ i v i / G i ) = 0 . If ζ > 0 \zeta>0 ζ > 0 , the answer lies on the outer face.
Revelation of one coordinate at a time
Proof of Lemma 4.4 ▲.
▷ Part (a). Let ∣ u n ∣ ≤ δ |u_n|\leq\delta ∣ u n ∣ ≤ δ and v = Φ ( u ) v=\Phi(u) v = Φ ( u ) . The answer v = 0 v=0 v = 0 is impossible. Otherwise, by the definition of the subgradient along t e n te_n t e n ,
A + 2 C − δ ≤ u n + σ n ≤ lim t → 0 Q ( t e n ) t = 4 ℓ 1 log n < C , A+2C-\delta\leq u_n+\sigma_n\leq\lim_{t\to0}\frac{Q(te_n)}{t}=\frac{4}{\ell_1}\log\sqrt{n}<C, A + 2 C − δ ≤ u n + σ n ≤ t → 0 lim t Q ( t e n ) = ℓ 1 4 log n < C ,
which contradicts A ≥ 0 A\geq0 A ≥ 0 and C > δ C>\delta C > δ . If ζ = 0 \zeta=0 ζ = 0 , then condition (C.2) for coordinate n n n gives
A + 2 C − δ ≤ u n + σ n ≤ ϑ + γ v n + ( B v ) n ≤ A + C , A+2C-\delta\leq u_n+\sigma_n\leq\vartheta+\gamma v_n+(Bv)_n\leq A+C, A + 2 C − δ ≤ u n + σ n ≤ ϑ + γ v n + ( B v ) n ≤ A + C ,
where (a) is given by the bounds of § 4.3 . This contradicts C > δ C>\delta C > δ . Hence, ζ > 0 \zeta>0 ζ > 0 , the answer lies on the outer face, and by Lemma 4.1 ∥ Φ ( u ) ∥ ≥ G n / n \|\Phi(u)\|\geq G_n/\sqrt{n} ∥Φ ( u ) ∥ ≥ G n / n .
▷ Part (b), a jump within a block. Let ∣ u i ∣ ≤ δ |u_i|\leq\delta ∣ u i ∣ ≤ δ for i ≥ j i\geq j i ≥ j , and let l l l be the last nonzero coordinate of v = Φ ( u ) v=\Phi(u) v = Φ ( u ) . Suppose that l > j l>j l > j . By Part (a), the answer lies on the outer face. Assume first that the block of coordinate l l l contains a coordinate t ≥ j t\geq j t ≥ j preceding it, and let β = 5 m log ( e n ) / ( ℓ 1 G l ) \beta=5\sqrt{m}\log(e\sqrt{n})/(\ell_1G_l) β = 5 m log ( e n ) / ( ℓ 1 G l ) . Subtract condition (C.2) for t t t from the equality for l l l . The terms ζ / G i \zeta/G_i ζ / G i cancel, since G t = G l G_t=G_l G t = G l . We obtain
− 2 δ ≥ (a) ( u l + σ l ) − ( u t + σ t ) ≥ γ ( v l − v t ) + ( B v ) l − ( B v ) t -2\delta\underset{\text{(a)}}{\geq}(u_l+\sigma_l)-(u_t+\sigma_t)\geq\gamma(v_l-v_t)+(Bv)_l-(Bv)_t − 2 δ (a) ≥ ( u l + σ l ) − ( u t + σ t ) ≥ γ ( v l − v t ) + ( B v ) l − ( B v ) t
= (b) ( γ + β ) v l + ( β − γ ) v t + 2 β ∑ t < i < l v i ≥ (c) 0 , \underset{\text{(b)}}{=}(\gamma+\beta)v_l+(\beta-\gamma)v_t+2\beta\sum_{t<i<l}v_i\underset{\text{(c)}}{\geq}0, (b) = ( γ + β ) v l + ( β − γ ) v t + 2 β t < i < l ∑ v i (c) ≥ 0 ,
where (a) follows from the inequalities σ t − σ l ≥ 4 δ \sigma_t-\sigma_l\geq4\delta σ t − σ l ≥ 4 δ and ∣ u t ∣ , ∣ u l ∣ ≤ δ |u_t|,|u_l|\leq\delta ∣ u t ∣ , ∣ u l ∣ ≤ δ , (b) follows from the sign pattern of B B B , under which the terms before t t t and after l l l cancel, and (c) follows from the inequality γ ≤ β \gamma\leq\beta γ ≤ β . The latter follows from (11) and the bound
1 = ∑ i < l v i G i ≤ ∥ v ∥ ( ∑ i ≤ l G i − 2 ) 1 / 2 ≤ ∥ v ∥ m G l 1 − e − 2 . 1=\sum_{i<l}\frac{v_i}{G_i}\leq\|v\|\left(\sum_{i\leq l}G_i^{-2}\right)^{1/2}\leq\|v\|\frac{\sqrt{m}}{G_l\sqrt{1-e^{-2}}}. 1 = i < l ∑ G i v i ≤ ∥ v ∥ ( i ≤ l ∑ G i − 2 ) 1/2 ≤ ∥ v ∥ G l 1 − e − 2 m .
This is impossible.
▷ Part (b), a transition to another block. Otherwise, l l l is the first coordinate of a block strictly after the block containing j j j . After l l l the answer is zero, so ( B v ) l = 0 (Bv)_l=0 ( B v ) l = 0 . Let r = G l / G j ≤ 1 / e r=G_l/G_j\leq1/e r = G l / G j ≤ 1/ e . Conditions (C.2) for j j j and l l l give ζ ≥ G j ( A + C − δ − ϑ ) \zeta\geq G_j(A+C-\delta-\vartheta) ζ ≥ G j ( A + C − δ − ϑ ) and ζ ≤ G l ( A + 2 C + 4 ( m − 1 ) δ + δ − ϑ ) \zeta\leq G_l(A+2C+4(m-1)\delta+\delta-\vartheta) ζ ≤ G l ( A + 2 C + 4 ( m − 1 ) δ + δ − ϑ ) . Comparing these bounds and dividing by G j G_j G j , we obtain
0 ≥ ( 1 − r ) ( A − ϑ ) + ( 1 − 2 r ) C − 4 r ( m − 1 ) δ − ( 1 + r ) δ 0\geq(1-r)(A-\vartheta)+(1-2r)C-4r(m-1)\delta-(1+r)\delta 0 ≥ ( 1 − r ) ( A − ϑ ) + ( 1 − 2 r ) C − 4 r ( m − 1 ) δ − ( 1 + r ) δ
≥ (a) 1 ℓ 1 [ ( 1 − 2 e ) ( 5 m + 4 ) − m e − 1 2 ] > (b) 0 , \underset{\text{(a)}}{\geq}\frac{1}{\ell_1}\left[\left(1-\frac{2}{e}\right)(5\sqrt{m}+4)-\frac{\sqrt{m}}{e}-\frac{1}{2}\right]\underset{\text{(b)}}{>}0, (a) ≥ ℓ 1 1 [ ( 1 − e 2 ) ( 5 m + 4 ) − e m − 2 1 ] (b) > 0 ,
where (a) follows from the inequalities ϑ ≤ A \vartheta\leq A ϑ ≤ A , r ≤ 1 / e r\leq1/e r ≤ 1/ e , log ( e n ) ≥ 1 \log(e\sqrt{n})\geq1 log ( e n ) ≥ 1 and the definition of δ \delta δ , and (b) follows from the fact that the expression in brackets equals ( 5 − 11 / e ) m + 7 / 2 − 8 / e > 0 (5-11/e)\sqrt{m}+7/2-8/e>0 ( 5 − 11/ e ) m + 7/2 − 8/ e > 0 . This is a contradiction.
▷ Dependence on the prefix. Hence, l ≤ j l\leq j l ≤ j . The remaining coordinates of the answer solve the same inclusion on the first j j j coordinates, where the solution is unique. Therefore, they depend only on u 1 , … , u j u_1,\ldots,u_j u 1 , … , u j . For j = 1 j=1 j = 1 , only the first coordinate remains, and the equation defining the outer face gives Φ ( u ) = G 1 e 1 \Phi(u)=G_1e_1 Φ ( u ) = G 1 e 1 .
Exact choice of the length and control of the radius
Lemma C.1 (chain length and radius). ▼ proof in Appendix C.3
Let h ≥ 2 h \ge2 h ≥ 2 be an integer, m = h 2 m=h^2 m = h 2 , H = ⌈ h log ( 4 h ) ⌉ H=\lceil h\log(4h)\rceil H = ⌈ h log ( 4 h )⌉ and n = m H n=mH n = m H . Then
max { ∥ σ ∥ , ∥ w ∥ } ≤ 128 ℓ 1 h 5 / 2 log 3 / 2 ( 4 h ) . (21) \max\{\lVert\sigma\rVert,\lVert w\rVert\}\le\frac{128}{\ell_1}h^{5/2}\log^{3/2}(4h). \tag*{(21)} max {∥ σ ∥ , ∥ w ∥} ≤ ℓ 1 128 h 5/2 log 3/2 ( 4 h ) . (21) and h 3 log ( 4 h ) ≤ n ≤ 2 h 3 log ( 4 h ) h^3\log(4h)\le n\le2h^3\log(4h) h 3 log ( 4 h ) ≤ n ≤ 2 h 3 log ( 4 h ) .
Proof of Lemma C.1 ▲. Let λ = log ( 4 h ) \lambda=\log(4h) λ = log ( 4 h ) .
Chain length and logarithms. We have h 3 λ ≤ n ≤ 2 h 3 λ h^3\lambda\le n\le2h^3\lambda h 3 λ ≤ n ≤ 2 h 3 λ , log ( n + 1 ) ≤ 6 λ \log(n+1)\le6\lambda log ( n + 1 ) ≤ 6 λ and log ( e n ) ≤ 3 λ \log(e\sqrt{n})\le3\lambda log ( e n ) ≤ 3 λ . The last bounds follow, for example, from λ ≤ 2 h \lambda\le2h λ ≤ 2 h and n ≤ 4 h 3 n\le4h^3 n ≤ 4 h 3 .
2 log ( 1 + n 3 e H − 1 ) ≤ 6 log ( n + 1 ) + 2 H ≤ 22 h λ , 2\log(1+n^3e^{H-1})\le6\log(n+1)+2H\le22h\lambda, 2 log ( 1 + n 3 e H − 1 ) ≤ 6 log ( n + 1 ) + 2 H ≤ 22 hλ ,
2 ( 5 h + 4 ) log ( e n ) ≤ 44 h λ , 2(5h+4)\log(e\sqrt{n})\le44h\lambda, 2 ( 5 h + 4 ) log ( e n ) ≤ 44 hλ ,
4 ℓ 1 ( m − pos ( i ) ) δ ≤ h ≤ h λ . 4\ell_1(m-\operatorname{pos}(i))\delta\le h\le h\lambda. 4 ℓ 1 ( m − pos ( i )) δ ≤ h ≤ hλ .
Therefore, ℓ 1 max i σ i ≤ 67 h λ \ell_1\max_i\sigma_i\le67h\lambda ℓ 1 max i σ i ≤ 67 hλ .
Bound on the test point. For the point w w w from Lemma 4.9 and i < n i<n i < n , the gradient at the vertex is at least − 4 / ℓ 1 -4/\ell_1 − 4/ ℓ 1 , and the term G n ( B e n ) i G_n(Be_n)_i G n ( B e n ) i is either zero or equal to − 5 h log ( e n ) / ℓ 1 -5h\log(e\sqrt{n})/\ell_1 − 5 h log ( e n ) / ℓ 1 . All w i w_i w i are negative. For i = n i=n i = n this is seen from the explicit formula in the proof of Lemma 4.9. Hence, ℓ 1 max i ∣ w i ∣ ≤ 67 h λ + 4 + 15 h λ ≤ 83 h λ \ell_1\max_i|w_i|\le67h\lambda+4+15h\lambda\le83h\lambda ℓ 1 max i ∣ w i ∣ ≤ 67 hλ + 4 + 15 hλ ≤ 83 hλ .
max { ∥ σ ∥ , ∥ w ∥ } ≤ 128 ℓ 1 h 5 / 2 λ 3 / 2 . (22) \max\{\lVert\sigma\rVert,\lVert w\rVert\}\le\frac{128}{\ell_1}h^{5/2}\lambda^{3/2}. \tag*{(22)} max {∥ σ ∥ , ∥ w ∥} ≤ ℓ 1 128 h 5/2 λ 3/2 . (22)
The largest admissible parameter and the resulting order
Now ℓ 0 = L 0 / 4 \ell_0=L_0/4 ℓ 0 = L 0 /4 , ℓ 1 = L 1 / 2 \ell_1=L_1/2 ℓ 1 = L 1 /2 , x = L 1 R x=L_1R x = L 1 R , and h ≥ 256 h\ge256 h ≥ 256 is the largest integer such that 2048 h 5 / 2 λ 3 / 2 ≤ x 2048h^{5/2}\lambda^{3/2}\le x 2048 h 5/2 λ 3/2 ≤ x .
Lower bounds on n n n . When passing from h h h to h + 1 h+1 h + 1 , the expression h 5 / 2 log 3 / 2 ( 4 h ) h^{5/2}\log^{3/2}(4h) h 5/2 log 3/2 ( 4 h ) increases by a factor of less than 4, so x < 8192 h 5 / 2 λ 3 / 2 x<8192h^{5/2}\lambda^{3/2} x < 8192 h 5/2 λ 3/2 . Hence,
n 5 / 2 x > h 5 λ 8192 > 4 , \frac{n^{5/2}}{x}>\frac{h^5\lambda}{8192}>4, x n 5/2 > 8192 h 5 λ > 4 ,
n 3 x 2 > h 4 8192 2 > 4. \frac{n^3}{x^2}>\frac{h^4}{8192^2}>4. x 2 n 3 > 819 2 2 h 4 > 4.
Both strict bounds hold for h ≥ 256 h\ge256 h ≥ 256 .
Order of n n n . Also, x 6 / 5 = Θ ( h 3 λ 9 / 5 ) x^{6/5}=\Theta(h^3\lambda^{9/5}) x 6/5 = Θ ( h 3 λ 9/5 ) and log ( 2 + x ) = Θ ( λ ) \log(2+x)=\Theta(\lambda) log ( 2 + x ) = Θ ( λ ) , whence n = Θ ( x 6 / 5 / log 4 / 5 ( 2 + x ) ) n=\Theta\left(x^{6/5}/\log^{4/5}(2+x)\right) n = Θ ( x 6/5 / log 4/5 ( 2 + x ) ) .
Verification of the coordinate hiding parameters
For the norm we set q = L 0 R / ε q=L_0R/\varepsilon q = L 0 R / ε , and for the gap q = L 0 R 2 / η q=L_0R^2/\eta q = L 0 R 2 / η . We take μ = L 0 / [ 64 ( 1 + q + x ) ] \mu=L_0/[64(1+q+x)] μ = L 0 / [ 64 ( 1 + q + x )] . After smoothing, the constants are a 0 = L 0 / 2 a_0=L_0/2 a 0 = L 0 /2 and a 1 = L 1 / 2 a_1=L_1/2 a 1 = L 1 /2 .
Conditions of Lemma 4.7. We have μ ≤ L 0 / ( 64 q ) \mu\le L_0/(64q) μ ≤ L 0 / ( 64 q ) , that is, μ ≤ ε / ( 16 R ) \mu\le\varepsilon/(16R) μ ≤ ε / ( 16 R ) for the norm and μ ≤ η / ( 16 R 2 ) \mu\le\eta/(16R^2) μ ≤ η / ( 16 R 2 ) for the gap. For the norm, M = G 1 ≥ G n / n > 2 ε M=G_1\ge G_n/\sqrt{n}>2\varepsilon M = G 1 ≥ G n / n > 2 ε . For the gap, G n / ℓ 1 > 4 η G_n/\ell_1>4\eta G n / ℓ 1 > 4 η , so in the regime of large x x x under consideration, M ≥ G n > 2 L 1 η ≥ η / R M\ge G_n>2L_1\eta\ge\eta/R M ≥ G n > 2 L 1 η ≥ η / R .
Smoothing and the test point
Proof of Lemma 4.5 .
⟨ Φ ρ ( u ) − Φ ρ ( u ′ ) , u − u ′ ⟩ = ∫ ⟨ Φ ( u − y ) − Φ ( u ′ − y ) , u − u ′ ⟩ k ρ ( y ) d y ≥ 0. \langle\Phi_{\rho}(u)-\Phi_{\rho}(u'),u-u'\rangle=\int\langle\Phi(u-y)-\Phi(u'-y),u-u'\rangle k_{\rho}(y)\,dy\ge0. ⟨ Φ ρ ( u ) − Φ ρ ( u ′ ) , u − u ′ ⟩ = ∫ ⟨ Φ ( u − y ) − Φ ( u ′ − y ) , u − u ′ ⟩ k ρ ( y ) d y ≥ 0.
Solution. If u ≤ − σ u\le-\sigma u ≤ − σ coordinatewise, then ⟨ u + σ , v ⟩ ≤ 0 ≤ Q ( v ) \langle u+\sigma,v\rangle\le0\le Q(v) ⟨ u + σ , v ⟩ ≤ 0 ≤ Q ( v ) on K K K , so u + σ ∈ ∂ f ( 0 ) u+\sigma\in\partial f(0) u + σ ∈ ∂ f ( 0 ) and Φ ( u ) = 0 \Phi(u)=0 Φ ( u ) = 0 . For u = − σ − ρ 1 u=-\sigma-\rho\mathbf{1} u = − σ − ρ 1 , all u − y u-y u − y on the support of the kernel satisfy this condition. Therefore, Φ ρ ( u ) = 0 \Phi_{\rho}(u)=0 Φ ρ ( u ) = 0 .
Chain properties. If ∣ u i ∣ ≤ θ = δ / 2 |u_i|\le\theta=\delta/2 ∣ u i ∣ ≤ θ = δ /2 for i ≥ j i\ge j i ≥ j , then ∣ u i − y i ∣ ≤ θ + ρ ≤ δ |u_i-y_i|\le\theta+\rho\le\delta ∣ u i − y i ∣ ≤ θ + ρ ≤ δ . Each answer under the integral has a zero tail after j j j , depends only on the prefix, and lies on the outer face when u n u_n u n is small. Integration preserves all three properties.
( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -Lipschitz continuity. Set K L i p = ℓ 0 + ℓ 1 G 1 K_{\mathrm{Lip}}=\ell_0+\ell_1G_1 K Lip = ℓ 0 + ℓ 1 G 1 . The original Φ \Phi Φ is globally K L i p K_{\mathrm{Lip}} K Lip -Lipschitz, and almost everywhere ∥ D Φ ∥ ≤ ℓ 0 + ℓ 1 ∥ Φ ∥ \|D\Phi\|\le\ell_0+\ell_1\|\Phi\| ∥ D Φ∥ ≤ ℓ 0 + ℓ 1 ∥Φ∥ by Lemma 2.4 . For y y y in the support,
∥ Φ ( u − y ) − Φ ρ ( u ) ∥ ≤ ∫ K L i p ∥ y − t ∥ k ρ ( t ) d t ≤ 2 K L i p ρ . \|\Phi(u-y)-\Phi_{\rho}(u)\|\le\int K_{\mathrm{Lip}}\|y-t\|k_{\rho}(t)\,dt\le2K_{\mathrm{Lip}}\rho. ∥Φ ( u − y ) − Φ ρ ( u ) ∥ ≤ ∫ K Lip ∥ y − t ∥ k ρ ( t ) d t ≤ 2 K Lip ρ .
Differentiating the convolution gives
∥ D Φ ρ ( u ) ∥ ≤ ℓ 0 + ℓ 1 ∥ Φ ρ ( u ) ∥ + 2 ℓ 1 K L i p ρ ≤ 2 ℓ 0 + ℓ 1 ∥ Φ ρ ( u ) ∥ . \|D\Phi_{\rho}(u)\|\le\ell_0+\ell_1\|\Phi_{\rho}(u)\|+2\ell_1K_{\mathrm{Lip}}\rho\le2\ell_0+\ell_1\|\Phi_{\rho}(u)\|. ∥ D Φ ρ ( u ) ∥ ≤ ℓ 0 + ℓ 1 ∥ Φ ρ ( u ) ∥ + 2 ℓ 1 K Lip ρ ≤ 2 ℓ 0 + ℓ 1 ∥ Φ ρ ( u ) ∥.
Proof of Lemma 4.9.
The answer in a neighborhood of w w w . At the vertex G n e n G_ne_n G n e n , the normal cone consists of the y y y for which y n ≥ 0 y_n\ge0 y n ≥ 0 and y i G i ≤ y n G n y_iG_i\le y_nG_n y i G i ≤ y n G n for i < n i<n i < n . This follows from comparing the values of the linear function at all vertices. Let r w = G n / [ 2 ℓ 1 ( G 1 + G n ) ] r_w=G_n/[2\ell_1(G_1+G_n)] r w = G n / [ 2 ℓ 1 ( G 1 + G n )] and ∥ ξ ∥ ≤ r w \|\xi\|\le r_w ∥ ξ ∥ ≤ r w . Then y = e n / ℓ 1 + ξ y=e_n/\ell_1+\xi y = e n / ℓ 1 + ξ belongs to this cone, since y n ≥ 1 / ℓ 1 − r w > 0 y_n\ge1/\ell_1-r_w>0 y n ≥ 1/ ℓ 1 − r w > 0 and y i G i ≤ r w G 1 ≤ ( 1 / ℓ 1 − r w ) G n ≤ y n G n y_iG_i\le r_wG_1\le(1/\ell_1-r_w)G_n\le y_nG_n y i G i ≤ r w G 1 ≤ ( 1/ ℓ 1 − r w ) G n ≤ y n G n . Consequently, Φ ( w + ξ ) = G n e n \Phi(w+\xi)=G_ne_n Φ ( w + ξ ) = G n e n in the whole ball. Since ρ ≤ r w \rho\le r_w ρ ≤ r w , we obtain Φ ρ ( w ) = G n e n \Phi_{\rho}(w)=G_ne_n Φ ρ ( w ) = G n e n .
ℓ 1 w n = 2 log 1 + n 3 1 + n 3 e H − 1 + 4 log n + 1 − 2 ( 5 m + 4 ) log ( e n ) ≤ − 3 , \ell_1w_n=2\log\frac{1+n^3}{1+n^3e^{H-1}}+4\log\sqrt{n}+1-2(5\sqrt{m}+4)\log(e\sqrt{n})\le-3, ℓ 1 w n = 2 log 1 + n 3 e H − 1 1 + n 3 + 4 log n + 1 − 2 ( 5 m + 4 ) log ( e n ) ≤ − 3 ,
since the first logarithm is nonpositive and 4 log n < 4 log ( e n ) 4\log\sqrt{n}<4\log(e\sqrt{n}) 4 log n < 4 log ( e n ) . Therefore, for ∣ u n ∣ ≤ δ |u_n|\le\delta ∣ u n ∣ ≤ δ , we have ⟨ Φ ρ ( w ) , u − w ⟩ = G n ( u n − w n ) ≥ G n ( 3 / ℓ 1 − δ ) ≥ G n / ℓ 1 \langle\Phi_{\rho}(w),u-w\rangle=G_n(u_n-w_n)\ge G_n(3/\ell_1-\delta)\ge G_n/\ell_1 ⟨ Φ ρ ( w ) , u − w ⟩ = G n ( u n − w n ) ≥ G n ( 3/ ℓ 1 − δ ) ≥ G n / ℓ 1 .
Coordinate hiding preserves the class and the success condition
Proof of Lemma 4.6 . Denote the original ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -Lipschitz constants by a 0 , a 1 a_0,a_1 a 0 , a 1 . Since F F F is bounded, condition (1) makes it globally Lipschitz with constant a 0 + a 1 M a_0+a_1M a 0 + a 1 M . The derivatives below exist almost everywhere.
Strong monotonicity. We have D F ~ = χ D F + F ∇ χ T + μ I D\widetilde{F}=\chi DF+F\nabla\chi^{\mathsf T}+\mu I D F = χD F + F ∇ χ T + μ I . The monotonicity of F F F gives ⟨ D F ξ , ξ ⟩ ≥ 0 \langle DF\xi,\xi\rangle\ge0 ⟨ D F ξ , ξ ⟩ ≥ 0 almost everywhere. The middle term has norm at most 2 M / L 2M/L 2 M / L , hence
⟨ D F ~ ξ , ξ ⟩ ≥ ( μ − 2 M / L ) ∥ ξ ∥ 2 ≥ μ 2 ∥ ξ ∥ 2 . \langle D\widetilde{F}\xi,\xi\rangle\ge(\mu-2M/L)\|\xi\|^2\ge\frac{\mu}{2}\|\xi\|^2. ⟨ D F ξ , ξ ⟩ ≥ ( μ − 2 M / L ) ∥ ξ ∥ 2 ≥ 2 μ ∥ ξ ∥ 2 .
Integration over almost all parallel segments and passage to the limit, as in Lemma 2.4 , give μ / 2 \mu/2 μ /2 -strong monotonicity.
0 ≤ ⟨ F ( z μ ∗ ) − F ( z ∗ ) , z μ ∗ − z ∗ ⟩ = − μ ⟨ z μ ∗ , z μ ∗ − z ∗ ⟩ . 0\le\langle F(z_\mu^*)-F(z^*),z_\mu^*-z^*\rangle=-\mu\langle z_\mu^*,z_\mu^*-z^*\rangle. 0 ≤ ⟨ F ( z μ ∗ ) − F ( z ∗ ) , z μ ∗ − z ∗ ⟩ = − μ ⟨ z μ ∗ , z μ ∗ − z ∗ ⟩ .
Hence, ∥ z μ ∗ ∥ ≤ ∥ z ∗ ∥ ≤ R < L \|z_\mu^*\|\le\|z^*\|\le R<L ∥ z μ ∗ ∥ ≤ ∥ z ∗ ∥ ≤ R < L , so χ = 1 \chi=1 χ = 1 at this point, and it is also a zero of F ~ \widetilde{F} F .
For 2 R ≤ ∥ z ∥ ≤ L 2R\le\lVert z\rVert\le L 2 R ≤ ∥ z ∥ ≤ L , monotonicity with respect to z ∗ z^* z ∗ gives ⟨ F ( z ) , z ⟩ ≥ ⟨ F ( z ) , z ∗ ⟩ ≥ − R ∥ F ( z ) ∥ \langle F(z),z\rangle\ge\langle F(z),z^*\rangle\ge-R\lVert F(z)\rVert ⟨ F ( z ) , z ⟩ ≥ ⟨ F ( z ) , z ∗ ⟩ ≥ − R ∥ F ( z )∥ . For a = ∥ F ( z ) ∥ a=\lVert F(z)\rVert a = ∥ F ( z )∥ and b = μ ∥ z ∥ b=\mu\lVert z\rVert b = μ ∥ z ∥ we obtain 2 μ R a ≤ a b 2\mu Ra\le ab 2 μ R a ≤ ab and
∥ F ( z ) + μ z ∥ 2 ≥ a 2 + b 2 − a b ≥ ( a + b ) 2 / 4. (23) \lVert F(z)+\mu z\rVert^2\ge a^2+b^2-ab\ge(a+b)^2/4. \tag*{(23)} ∥ F ( z ) + μ z ∥ 2 ≥ a 2 + b 2 − ab ≥ ( a + b ) 2 /4. (23) The last inequality is equivalent to 3 ( a − b ) 2 ≥ 0 3(a-b)^2\ge0 3 ( a − b ) 2 ≥ 0 . Therefore, ∥ F ∥ ≤ 2 ∥ F ~ ∥ \lVert F\rVert\le2\lVert\widetilde{F}\rVert ∥ F ∥ ≤ 2 ∥ F ∥ and ∥ D F ~ ∥ ≤ a 0 + μ + 2 a 1 ∥ F ~ ∥ \lVert D\widetilde{F}\rVert\le a_0+\mu+2a_1\lVert\widetilde{F}\rVert ∥ D F ∥ ≤ a 0 + μ + 2 a 1 ∥ F ∥ .
In all four cases, ∥ D F ~ ∥ ≤ 2 a 0 + 2 a 1 ∥ F ~ ∥ \lVert D\widetilde{F}\rVert\le2a_0+2a_1\lVert\widetilde{F}\rVert ∥ D F ∥ ≤ 2 a 0 + 2 a 1 ∥ F ∥ almost everywhere. By Lemma 2.4 , this implies condition (1) with constants 2 a 0 , 2 a 1 2a_0,2a_1 2 a 0 , 2 a 1 . If the original F ∈ C 2 F\in C^2 F ∈ C 2 , then also F ~ ∈ C 2 \widetilde{F}\in C^2 F ∈ C 2 : in a neighborhood of zero the factor χ \chi χ is constant, so the nondifferentiability of the norm at zero causes no difficulty.
Proof of Lemma 4.7 ▲.
Part (a). Let μ ≤ ε / ( 16 R ) \mu\le\varepsilon/(16R) μ ≤ ε / ( 16 R ) , M ≥ ε M\ge\varepsilon M ≥ ε and ∥ F ~ ( z ) ∥ ≤ ε \lVert\widetilde{F}(z)\rVert\le\varepsilon ∥ F ( z )∥ ≤ ε . For L ≤ ∥ z ∥ ≤ 2 L L\le\lVert z\rVert\le2L L ≤ ∥ z ∥ ≤ 2 L the norm of F ~ \widetilde{F} F is at least 31 M > ε 31M>\varepsilon 31 M > ε , and for ∥ z ∥ ≥ 2 L \lVert z\rVert\ge2L ∥ z ∥ ≥ 2 L it is at least 64 M > ε 64M>\varepsilon 64 M > ε . Therefore, ∥ z ∥ < L \lVert z\rVert<L ∥ z ∥ < L . If ∥ z ∥ ≤ 2 R \lVert z\rVert\le2R ∥ z ∥ ≤ 2 R , then ∥ F ( z ) ∥ ≤ ε + μ ∥ z ∥ ≤ ε + ε / 8 < 2 ε \lVert F(z)\rVert\le\varepsilon+\mu\lVert z\rVert\le\varepsilon+\varepsilon/8<2\varepsilon ∥ F ( z )∥ ≤ ε + μ ∥ z ∥ ≤ ε + ε /8 < 2 ε . If 2 R ≤ ∥ z ∥ < L 2R\le\lVert z\rVert<L 2 R ≤ ∥ z ∥ < L , then by (C.5) ∥ F ( z ) ∥ ≤ 2 ∥ F ~ ( z ) ∥ ≤ 2 ε \lVert F(z)\rVert\le2\lVert\widetilde{F}(z)\rVert\le2\varepsilon ∥ F ( z )∥ ≤ 2 ∥ F ( z )∥ ≤ 2 ε .
Part (b), bound on ∥ z ∥ \lVert z\rVert ∥ z ∥ . Let ∥ z ∗ ∥ ≤ R / 4 \lVert z^*\rVert\le R/4 ∥ z ∗ ∥ ≤ R /4 , μ ≤ η / ( 16 R 2 ) \mu\le\eta/(16R^2) μ ≤ η / ( 16 R 2 ) , M ≥ η / R M\ge\eta/R M ≥ η / R and Gap R F ~ ( z ) ≤ η \operatorname{Gap}_{R}^{\widetilde{F}}(z)\le\eta Gap R F ( z ) ≤ η . Let r = ∥ z − z μ ∗ ∥ ≥ R / 2 r=\lVert z-z_\mu^*\rVert\ge R/2 r = ∥ z − z μ ∗ ∥ ≥ R /2 and u = z μ ∗ + ( R / 2 ) ( z − z μ ∗ ) / r u=z_\mu^*+(R/2)(z-z_\mu^*)/r u = z μ ∗ + ( R /2 ) ( z − z μ ∗ ) / r . Then ∥ u ∥ ≤ 3 R / 4 \lVert u\rVert\le3R/4 ∥ u ∥ ≤ 3 R /4 , and F ~ = F + μ I \widetilde{F}=F+\mu I F = F + μ I on the relevant segment. Therefore,
η ≥ ⟨ F ~ ( u ) , z − u ⟩ = r − R / 2 R / 2 ⟨ F ~ ( u ) − F ~ ( z μ ∗ ) , u − z μ ∗ ⟩ \eta\ge\langle\widetilde{F}(u),z-u\rangle=\frac{r-R/2}{R/2}\langle\widetilde{F}(u)-\widetilde{F}(z_\mu^*),u-z_\mu^*\rangle η ≥ ⟨ F ( u ) , z − u ⟩ = R /2 r − R /2 ⟨ F ( u ) − F ( z μ ∗ ) , u − z μ ∗ ⟩ ≥ r − R / 2 R / 2 μ R 2 4 = μ R 2 ( r − R / 2 ) . \ge\frac{r-R/2}{R/2}\frac{\mu R^2}{4}=\frac{\mu R}{2}(r-R/2). ≥ R /2 r − R /2 4 μ R 2 = 2 μ R ( r − R /2 ) . Hence, r ≤ R / 2 + 2 η / ( μ R ) r\le R/2+2\eta/(\mu R) r ≤ R /2 + 2 η / ( μ R ) , and for r < R / 2 r<R/2 r < R /2 this bound also holds. Consequently,
∥ z ∥ ≤ 3 R / 4 + 2 η / ( μ R ) ≤ 3 L / 16 + 2 M / μ ≤ L / 4. (24) \lVert z\rVert\le3R/4+2\eta/(\mu R)\le3L/16+2M/\mu\le L/4. \tag*{(24)} ∥ z ∥ ≤ 3 R /4 + 2 η / ( μ R ) ≤ 3 L /16 + 2 M / μ ≤ L /4. (24)
Random embedding
Proof of Proposition 4.8 ▲.
Membership in the class. Denote F 0 ( z ) = U Φ ( U T z ) F_0(z)=U\Phi(U^{\mathsf T}z) F 0 ( z ) = U Φ ( U T z ) . Since U T U = I U^{\mathsf T}U=I U T U = I , we have ∥ F 0 ( z ) ∥ = ∥ Φ ( U T z ) ∥ \lVert F_0(z)\rVert=\lVert\Phi(U^{\mathsf T}z)\rVert ∥ F 0 ( z )∥ = ∥ Φ ( U T z )∥ , ∥ U T ( z − z ′ ) ∥ ≤ ∥ z − z ′ ∥ \lVert U^{\mathsf T}(z-z')\rVert\le\lVert z-z'\rVert ∥ U T ( z − z ′ )∥ ≤ ∥ z − z ′ ∥ and ⟨ F 0 ( z ) − F 0 ( z ′ ) , z − z ′ ⟩ = ⟨ Φ ( U T z ) − Φ ( U T z ′ ) , U T z − U T z ′ ⟩ ≥ 0 \langle F_0(z)-F_0(z'),z-z'\rangle=\langle\Phi(U^{\mathsf T}z)-\Phi(U^{\mathsf T}z'),U^{\mathsf T}z-U^{\mathsf T}z'\rangle\ge0 ⟨ F 0 ( z ) − F 0 ( z ′ ) , z − z ′ ⟩ = ⟨ Φ ( U T z ) − Φ ( U T z ′ ) , U T z − U T z ′ ⟩ ≥ 0 . Therefore, F 0 F_0 F 0 is monotone, satisfies condition (1) with the same constants, is bounded by M M M , and has the zero U u ∗ Uu^* U u ∗ with norm ∥ u ∗ ∥ ≤ R \lVert u^*\rVert\le R ∥ u ∗ ∥ ≤ R . By Lemma 4.6, the operator F U F_U F U belongs to P d \mathcal{P}_d P d with constants 2 L 0 , 2 L 1 2L_0,2L_1 2 L 0 , 2 L 1 .
▷ The gap under the embedding. Restricting the points in the supremum to vectors of the form U u Uu U u , we obtain
Gap R F 0 ( z ) ≥ sup ∥ u ∥ ≤ R ⟨ U Φ ( u ) , z − U u ⟩ = Gap R Φ ( U ⊤ z ) . \operatorname{Gap}^{F_0}_{R}(z) \ge\sup_{\lVert u\rVert\le R} \langle U\Phi(u),z-Uu\rangle= \operatorname{Gap}^{\Phi}_{R}(U^{\top}z). Gap R F 0 ( z ) ≥ ∥ u ∥ ≤ R sup ⟨ U Φ ( u ) , z − U u ⟩ = Gap R Φ ( U ⊤ z ) .
▷ The ideal process. Fix the randomness of the algorithm. After t t t revelations, the auxiliary oracle knows only the first t t t positions. For a query with ∥ z ∥ ≥ 2 L \lVert z\rVert\ge2L ∥ z ∥ ≥ 2 L , it returns μ z \mu z μ z without revealing coordinates. For a query with ∥ z ∥ < 2 L \lVert z\rVert< 2L ∥ z ∥ < 2 L , it reveals π ( t + 1 ) \pi(t+1) π ( t + 1 ) and returns χ ( ∥ z ∥ / L ) U Φ ( u ~ ) + μ z \chi(\lVert z\rVert/L)U\Phi(\widetilde{u})+\mu z χ (∥ z ∥ / L ) U Φ ( u ) + μ z , where
u ~ i = { z π ( i ) , i ≤ t , clip [ − θ , θ ] ( z π ( t + 1 ) ) , i = t + 1 , 0 , i > t + 1. \widetilde{u}_i =
\begin{cases}
z_{\pi(i)}, & i\le t,\\
\operatorname{clip}_{[-\theta,\theta]}(z_{\pi(t+1)}), & i=t+1,\\
0, & i>t+1.
\end{cases} u i = ⎩ ⎨ ⎧ z π ( i ) , clip [ − θ , θ ] ( z π ( t + 1 ) ) , 0 , i ≤ t , i = t + 1 , i > t + 1.
and clip [ − θ , θ ] ( a ) = max { − θ , min { a , θ } } \operatorname{clip}_{[-\theta,\theta]}(a)=\max\{-\theta,\min\{a,\theta\}\} clip [ − θ , θ ] ( a ) = max { − θ , min { a , θ }} . By condition (a), the vector Φ ( u ~ ) \Phi(\widetilde{u}) Φ ( u ) has a zero tail after t + 1 t+1 t + 1 , so the ideal answer depends only on the revealed positions. Clipping is needed for this to hold on any history, including histories with a large value of the new coordinate. If, on the other hand, all unrevealed coordinates in the query are at most θ \theta θ in absolute value, then by condition (a) the ideal answer coincides with the real one.
▷ Probability of guessing. A vector z z z with ∥ z ∥ < 2 L \lVert z\rVert<2L ∥ z ∥ < 2 L has at most 4 L 2 / θ 2 4L^2/\theta^2 4 L 2 / θ 2 coordinates exceeding θ \theta θ in absolute value: each such coordinate contributes more than θ 2 \theta^2 θ 2 to ∥ z ∥ 2 < 4 L 2 \lVert z\rVert^2<4L^2 ∥ z ∥ 2 < 4 L 2 . In the ideal process, conditionally on the past history, the unrevealed positions are uniform among the at least d − n d-n d − n remaining ones. Therefore, for one unrevealed position,
Pr { ∣ z π ( i ) ∣ > θ ∣ ideal history } ≤ 4 L 2 ( d − n ) θ 2 . \Pr\{|z_{\pi(i)}|>\theta\mid\text{ideal history}\}\le\frac{4L^2}{(d-n)\theta^2}. Pr { ∣ z π ( i ) ∣ > θ ∣ ideal history } ≤ ( d − n ) θ 2 4 L 2 .
We call guessing the following event: among the first min { τ , N } \min\{\tau,N\} min { τ , N } queries of the ideal process and, if τ ≤ N \tau\le N τ ≤ N , the returned point, there is a point z z z with ∥ z ∥ < 2 L \lVert z\rVert<2L ∥ z ∥ < 2 L and an unrevealed position π ( i ) \pi(i) π ( i ) such that ∣ z π ( i ) ∣ > θ |z_{\pi(i)}|>\theta ∣ z π ( i ) ∣ > θ . The algorithm may not have queried the returned point, but this point can also guess a hidden coordinate. Summing over at most n n n unrevealed positions and at most N + 1 N+1 N + 1 points, we obtain
p b a d ≤ 4 ( N + 1 ) n L 2 ( d − n ) θ 2 ≤ 1 12 . p_{\mathrm{bad}}\le\frac{4(N+1)nL^2}{(d-n)\theta^2}\le\frac{1}{12}. p bad ≤ ( d − n ) θ 2 4 ( N + 1 ) n L 2 ≤ 12 1 .
We condition on the ideal history, without the additional condition “there has been no guessing before”. Otherwise, the uniformity of the unrevealed positions could be violated.
▷ Success is impossible without guessing. Suppose there was no guessing and τ ≤ N \tau\le N τ ≤ N . Then the real answers coincide with the ideal ones, and at most N < n N<n N < n positions are revealed, so the position π ( n ) \pi(n) π ( n ) is not revealed. If ∥ z ^ ∥ < 2 L \lVert\widehat{z}\rVert<2L ∥ z ∥ < 2 L , then ∣ z ^ π ( n ) ∣ ≤ θ |\widehat{z}_{\pi(n)}|\le\theta ∣ z π ( n ) ∣ ≤ θ , and by condition (b) ∥ U Φ ( U ⊤ z ^ ) ∥ > 2 ϵ \lVert U\Phi(U^{\top}\widehat{z})\rVert>2\epsilon ∥ U Φ ( U ⊤ z )∥ > 2 ϵ . If success means a small gap, then the previous item gives Gap R F 0 ( z ^ ) ≥ Gap R Φ ( U ⊤ z ^ ) > 4 η \operatorname{Gap}^{F_0}_{R}(\widehat{z})\ge\operatorname{Gap}^{\Phi}_{R}(U^{\top}\widehat{z})>4\eta Gap R F 0 ( z ) ≥ Gap R Φ ( U ⊤ z ) > 4 η . In both cases, by Lemma 4.7 , the point z ^ \widehat{z} z is not a successful output. If ∥ z ^ ∥ ≥ 2 L \lVert\widehat{z}\rVert\ge2L ∥ z ∥ ≥ 2 L , the same lemma rules out success. Therefore, Pr { success } ≤ Pr { τ > N } + p b a d \Pr\{\text{success}\}\le\Pr\{\tau>N\}+p_{\mathrm{bad}} Pr { success } ≤ Pr { τ > N } + p bad .
▷ Number of queries. Let T = sup U E T ( F U ) T=\sup_U\mathbb{E}_{T}(F_U) T = sup U E T ( F U ) . After averaging over U U U and the randomness of the algorithm, Markov’s inequality gives
2 3 ≤ Pr { τ > N } + p b a d ≤ T N + 1 + 1 12 , \frac{2}{3}\le\Pr\{\tau>N\}+p_{\mathrm{bad}}\le\frac{T}{N+1}+\frac{1}{12}, 3 2 ≤ Pr { τ > N } + p bad ≤ N + 1 T + 12 1 ,
whence T ≥ 7 ( N + 1 ) / 12 T\ge7(N+1)/12 T ≥ 7 ( N + 1 ) /12 . The distribution of the embedding is chosen independently of the randomness of the algorithm, so there exists a fixed matrix U U U on which the algorithm makes at least 7 ( N + 1 ) / 12 7(N+1)/12 7 ( N + 1 ) /12 oracle calls in expectation.
□
Linear systems: accuracy, probability and expected running time
Proof of Lemma 4.10.
External result. For κ ≥ 2 \kappa\ge2 κ ≥ 2 and a sufficiently large dimension d d d , achieving relative residual 1 / d 1/d 1/ d with probability 5 / 6 5/6 5/6 for all symmetric matrices with spectrum in [ − κ , − 1 ] ∪ [ 1 , κ ] [-\kappa,-1] \cup[1,\kappa] [ − κ , − 1 ] ∪ [ 1 , κ ] requires Ω ( κ log d ) \Omega(\kappa\log d) Ω ( κ log d ) arbitrary adaptive multiplications under a hard budget. This is the form of Theorems 2.6–2.8 of Dereziński et al. [6 ] that we use. The spectral subclass is preserved in their proof.
Guaranteed success. Suppose that a solver for relative residual 1 / 2 1/2 1/2 succeeds with probability 2 / 3 2/3 2/3 and uses at most T T T multiplications in expectation on any system. After each run, we check the residual with an additional multiplication and repeat an independent run in case of failure. The probability of reaching the j j j th run is at most ( 1 / 3 ) j − 1 (1/3)^{j-1} ( 1/3 ) j − 1 , so the expected cost of a verified success is at most
∑ j ≥ 1 ( 1 / 3 ) j − 1 ( T + 1 ) = 3 2 ( T + 1 ) . \sum_{j \ge1}(1/3)^{j-1}(T+1)=\frac{3}{2}(T+1). j ≥ 1 ∑ ( 1/3 ) j − 1 ( T + 1 ) = 2 3 ( T + 1 ) .
The cost of a run may depend on its success. What matters is only that the event of reaching it depends on the previous runs.
Refinement. Start with x = 0 x=0 x = 0 and r = b r=b r = b . We solve A u = r Au=r A u = r with the verified procedure and update x ← x + u x \leftarrow x+u x ← x + u , r ← r − A u r \leftarrow r-Au r ← r − A u . The residual norm decreases by at least a factor of two. After ⌈ log 2 d ⌉ \lceil\log_2 d\rceil ⌈ log 2 d ⌉ corrections, the relative residual is at most 1 / d 1/d 1/ d , and the expected cost is at most C ( T + 1 ) log d C(T+1)\log d C ( T + 1 ) log d . If r = 0 r=0 r = 0 earlier, we stop.
Hard budget. We truncate the whole procedure after ⌈ 6 C ( T + 1 ) log d ⌉ \lceil6C(T+1)\log d\rceil ⌈ 6 C ( T + 1 ) log d ⌉ multiplications. By Markov’s inequality, the probability of not finishing in time is at most 1 / 6 1/6 1/6 . The external result gives C ( T + 1 ) log d ≥ c κ log d C(T+1)\log d \ge c\kappa\log d C ( T + 1 ) log d ≥ c κ log d , whence 1 + T ≳ κ 1+T \gtrsim\kappa 1 + T ≳ κ . For 1 ≤ κ < 2 1 \le\kappa< 2 1 ≤ κ < 2 , the bound follows from 1 + T ≥ 1 1+T \ge1 1 + T ≥ 1 . The dimension can be chosen sufficiently large, since the complexity is taken uniformly over all dimensions.
Proof of Proposition 4.11.
Membership in the class. For the reductions of § 4.9 , the linear part of the operator is S = a ( − A 0 0 A ) S=a\begin{pmatrix} -A & 0 \\ 0 & A \end{pmatrix} S = a ( − A 0 0 A ) . Since A = A T A=A^{\mathsf T} A = A T , we have S T = − S S^{\mathsf T}=-S S T = − S and ∥ S ∥ = a ∥ A ∥ \lVert S\rVert=a\lVert A\rVert ∥ S ∥ = a ∥ A ∥ . This verifies monotonicity and ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -Lipschitz continuity. Two queries to A A A simulate one value of F F F .
Bound for the norm. For a = 2 ε / R a=2\varepsilon/R a = 2 ε / R and s = R s=R s = R , ∥ F ( x , y ) ∥ ≤ ε \lVert F(x,y)\rVert\le\varepsilon ∥ F ( x , y )∥ ≤ ε implies ∥ A ( ∥ b ∥ / R ) x − b ∥ ≤ ∥ b ∥ / 2 \lVert A(\lVert b\rVert/R)x-b\rVert\le\lVert b\rVert/2 ∥ A (∥ b ∥ / R ) x − b ∥ ≤ ∥ b ∥ /2 . Therefore, Lemma 4.10 gives the first bound of the proposition.
Gap of an affine operator. For F ( z ) = S z + c F(z)=Sz+c F ( z ) = S z + c with S T = − S S^{\mathsf T}=-S S T = − S , we have ⟨ F ( u ) , z − u ⟩ = ⟨ c , z ⟩ + ⟨ u , − S z − c ⟩ \langle F(u),z-u\rangle=\langle c,z\rangle+\langle u,-Sz-c\rangle ⟨ F ( u ) , z − u ⟩ = ⟨ c , z ⟩ + ⟨ u , − S z − c ⟩ . The maximum over the ball equals ⟨ c , z ⟩ + R ∥ F ( z ) ∥ \langle c,z\rangle+R\lVert F(z)\rVert ⟨ c , z ⟩ + R ∥ F ( z )∥ . Since ⟨ S z , z ⟩ = 0 \langle Sz,z\rangle=0 ⟨ S z , z ⟩ = 0 and F ( z ) = S ( z − z ∗ ) F(z)=S(z-z^*) F ( z ) = S ( z − z ∗ ) , we have ⟨ c , z ⟩ = ⟨ F ( z ) , z ⟩ = ⟨ F ( z ) , z ∗ ⟩ \langle c,z\rangle=\langle F(z),z\rangle=\langle F(z),z^*\rangle ⟨ c , z ⟩ = ⟨ F ( z ) , z ⟩ = ⟨ F ( z ) , z ∗ ⟩ . If ∥ z ∗ ∥ ≤ R / 4 \lVert z^*\rVert\le R/4 ∥ z ∗ ∥ ≤ R /4 , we obtain Gap R ( z ) ≥ 3 R ∥ F ( z ) ∥ / 4 \operatorname{Gap}_{R}(z)\ge3R\lVert F(z)\rVert/4 Gap R ( z ) ≥ 3 R ∥ F ( z )∥ /4 .
∥ A 4 ∥ b ∥ R x − b ∥ ≤ 4 ∥ b ∥ R ∥ F ( x , y ) ∥ a ≤ 4 ∥ b ∥ R 4 η 3 R R 2 16 η = ∥ b ∥ 3 . \left\lVert A\frac{4\lVert b\rVert}{R}x-b\right\rVert
\le\frac{4\lVert b\rVert}{R}\frac{\lVert F(x,y)\rVert}{a}
\le\frac{4\lVert b\rVert}{R}\frac{4\eta}{3R}\frac{R^2}{16\eta}
=\frac{\lVert b\rVert}{3}. A R 4 ∥ b ∥ x − b ≤ R 4 ∥ b ∥ a ∥ F ( x , y )∥ ≤ R 4 ∥ b ∥ 3 R 4 η 16 η R 2 = 3 ∥ b ∥ .
For the norm and the gap, we apply Lemma 4.10 to the resulting solver, which uses at most 2 T 2T 2 T multiplications in expectation. When the chosen κ < 1 \kappa<1 κ < 1 , the corresponding ratio satisfies L 0 R / ε < 2 L_0R/\varepsilon<2 L 0 R / ε < 2 or L 0 R 2 / η < 16 L_0R^2/\eta<16 L 0 R 2 / η < 16 , so the constant term 1 1 1 suffices for the corresponding lower bound.
Bounded set
Relation between the criteria
Projection methods control the residual r γ ( z ) = ∥ z − P Z ( z − γ F ( z ) ) ∥ / γ r_\gamma(z) = \lVert z - P_Z(z - \gamma F(z))\rVert/\gamma r γ ( z ) = ∥ z − P Z ( z − γ F ( z ))∥ / γ , while the natural measure of nonoptimality is the tangential residual r tan ( z ) = dist ( 0 , F ( z ) + N Z ( z ) ) r_{\tan}(z) = \operatorname{dist}(0, F(z) + N_Z(z)) r t a n ( z ) = dist ( 0 , F ( z ) + N Z ( z )) .
Lemma D.1 (gaps and residuals). Let Z Z Z be a convex compact set of diameter D D D , z ∈ Z z \in Z z ∈ Z , γ > 0 \gamma> 0 γ > 0 , and p = P Z ( z − γ F ( z ) ) p = P_Z(z - \gamma F(z)) p = P Z ( z − γ F ( z )) . Then
r γ ( z ) ≤ r tan ( z ) , r_\gamma(z) \le r_{\tan}(z), r γ ( z ) ≤ r t a n ( z ) , Gap Z S ( z ) ≤ D r tan ( z ) , \operatorname{Gap}^{\mathrm{S}}_Z(z) \le D r_{\tan}(z), Gap Z S ( z ) ≤ D r t a n ( z ) , γ r γ ( z ) 2 ≤ Gap Z S ( z ) . \gamma r_\gamma(z)^2 \le\operatorname{Gap}^{\mathrm{S}}_Z(z). γ r γ ( z ) 2 ≤ Gap Z S ( z ) . If F F F is Lipschitz on [ z , p ] [z,p] [ z , p ] with constant L z p L_{zp} L z p , then ξ p = ( z − p ) / γ − F ( z ) ∈ N Z ( p ) \xi_p = (z-p)/\gamma- F(z) \in N_Z(p) ξ p = ( z − p ) / γ − F ( z ) ∈ N Z ( p ) and ∥ F ( p ) + ξ p ∥ ≤ ( 1 + γ L z p ) r γ ( z ) \lVert F(p) + \xi_p\rVert\le(1+\gamma L_{zp})r_\gamma(z) ∥ F ( p ) + ξ p ∥ ≤ ( 1 + γ L z p ) r γ ( z ) .
Proof. Let ξ ∈ N Z ( z ) \xi\in N_Z(z) ξ ∈ N Z ( z ) . Then P Z ( z + γ ξ ) = z P_Z(z + \gamma\xi) = z P Z ( z + γ ξ ) = z , and by nonexpansiveness of the projection,
γ r γ ( z ) = ∥ P Z ( z + γ ξ ) − P Z ( z − γ F ( z ) ) ∥ ≤ γ ∥ F ( z ) + ξ ∥ . \gamma r_\gamma(z) = \lVert P_Z(z + \gamma\xi) - P_Z(z - \gamma F(z))\rVert\le\gamma\lVert F(z) + \xi\rVert. γ r γ ( z ) = ∥ P Z ( z + γ ξ ) − P Z ( z − γ F ( z ))∥ ≤ γ ∥ F ( z ) + ξ ∥ .
For u ∈ Z u \in Z u ∈ Z , we have ⟨ ξ , z − u ⟩ ≥ 0 \langle\xi, z-u\rangle\ge0 ⟨ ξ , z − u ⟩ ≥ 0 , hence ⟨ F ( z ) , z − u ⟩ ≤ ⟨ F ( z ) + ξ , z − u ⟩ ≤ D ∥ F ( z ) + ξ ∥ \langle F(z), z-u\rangle\le\langle F(z) + \xi, z-u\rangle\le D\lVert F(z) + \xi\rVert ⟨ F ( z ) , z − u ⟩ ≤ ⟨ F ( z ) + ξ , z − u ⟩ ≤ D ∥ F ( z ) + ξ ∥ . Minimizing over ξ \xi ξ , we obtain the first two inequalities. The projection inequality at the point u = z u=z u = z gives ⟨ z − γ F ( z ) − p , z − p ⟩ ≤ 0 \langle z-\gamma F(z)-p,z-p\rangle\le0 ⟨ z − γ F ( z ) − p , z − p ⟩ ≤ 0 , that is, γ Gap Z S ( z ) ≥ γ ⟨ F ( z ) , z − p ⟩ ≥ ∥ z − p ∥ 2 \gamma\operatorname{Gap}^{\mathrm{S}}_Z(z) \ge\gamma\langle F(z),z-p\rangle\ge\lVert z-p\rVert^2 γ Gap Z S ( z ) ≥ γ ⟨ F ( z ) , z − p ⟩ ≥ ∥ z − p ∥ 2 . Finally, ξ p ∈ N Z ( p ) \xi_p \in N_Z(p) ξ p ∈ N Z ( p ) by the definition of the projection, and
∥ F ( p ) + ξ p ∥ ≤ ∥ F ( p ) − F ( z ) ∥ + ∥ z − p ∥ γ ≤ ( L z p + 1 / γ ) ∥ z − p ∥ . \lVert F(p) + \xi_p\rVert\le\lVert F(p)-F(z)\rVert+ \frac{\lVert z-p\rVert}{\gamma} \le(L_{zp}+1/\gamma)\lVert z-p\rVert. ∥ F ( p ) + ξ p ∥ ≤ ∥ F ( p ) − F ( z )∥ + γ ∥ z − p ∥ ≤ ( L z p + 1/ γ ) ∥ z − p ∥ .
The reverse inequality r tan ( z ) ≲ r γ ( z ) r_{\tan}(z) \lesssim r_\gamma(z) r t a n ( z ) ≲ r γ ( z ) fails: for Z = [ 0 , 1 ] Z=[0,1] Z = [ 0 , 1 ] , F ≡ 1 F \equiv1 F ≡ 1 , and 0 < z < γ 0<z<\gamma 0 < z < γ , we have r tan ( z ) = 1 r_{\tan}(z)=1 r t a n ( z ) = 1 and r γ ( z ) = z / γ r_\gamma(z)=z/\gamma r γ ( z ) = z / γ . The last claim of the lemma concerns the point p p p , not z z z .
Verification of the example on a bounded set
Proof of Theorem 5.1 ▲. Let Γ ≥ 72 η / D 2 \Gamma\ge72\eta/D^2 Γ ≥ 72 η / D 2 , κ = Γ D 2 / ( 72 η ) \kappa= \Gamma D^2/(72\eta) κ = Γ D 2 / ( 72 η ) , and A = A T A=A^{\mathsf T} A = A T with spectrum in [ − κ , − 1 ] ∪ [ 1 , κ ] [-\kappa,-1]\cup[1,\kappa] [ − κ , − 1 ] ∪ [ 1 , κ ] . Denote a = 72 η / D 2 a=72\eta/D^2 a = 72 η / D 2 , s = D b / ( 12 ∥ b ∥ ) s=Db/(12\lVert b\rVert) s = D b / ( 12 ∥ b ∥) , and x ∗ = A − 1 s x^*=A^{-1}s x ∗ = A − 1 s . The set Z = B ( 0 , D / 3 ) × [ 0 , D / 3 ] × B ( 0 , D / 3 ) Z=B(0,D/3)\times[0,D/3]\times B(0,D/3) Z = B ( 0 , D /3 ) × [ 0 , D /3 ] × B ( 0 , D /3 ) has diameter ( 2 D / 3 ) 2 + ( D / 3 ) 2 + ( 2 D / 3 ) 2 = D \sqrt{(2D/3)^2+(D/3)^2+(2D/3)^2}=D ( 2 D /3 ) 2 + ( D /3 ) 2 + ( 2 D /3 ) 2 = D .
The operator F ( x , t , y ) = ( a A y , Γ / L 1 , a ( s − A x ) ) F(x,t,y)=(aAy,\Gamma/L_1,a(s-Ax)) F ( x , t , y ) = ( a A y , Γ/ L 1 , a ( s − A x )) is monotone: its linear part is skew-symmetric. On the whole space, ∥ D F ∥ = a ∥ A ∥ ≤ Γ ≤ L 1 ∥ F ∥ ≤ L 0 + L 1 ∥ F ∥ \lVert DF\rVert=a\lVert A\rVert\le\Gamma\le L_1\lVert F\rVert\le L_0+L_1\lVert F\rVert ∥ D F ∥ = a ∥ A ∥ ≤ Γ ≤ L 1 ∥ F ∥ ≤ L 0 + L 1 ∥ F ∥ . The norm of x ∗ x^* x ∗ is at most D / 12 D/12 D /12 .
For the point z ∗ = ( x ∗ , 0 , 0 ) z^*=(x^*,0,0) z ∗ = ( x ∗ , 0 , 0 ) , we obtain F ( z ∗ ) = ( 0 , Γ / L 1 , 0 ) F(z^*)=(0,\Gamma/L_1,0) F ( z ∗ ) = ( 0 , Γ/ L 1 , 0 ) and ⟨ F ( z ∗ ) , z − z ∗ ⟩ = Γ t / L 1 ≥ 0 \langle F(z^*),z-z^*\rangle=\Gamma t/L_1\ge0 ⟨ F ( z ∗ ) , z − z ∗ ⟩ = Γ t / L 1 ≥ 0 for all z ∈ Z z\in Z z ∈ Z .
For a skew-symmetric linear part, ⟨ F ( u ) , z − u ⟩ = ⟨ F ( z ) , z − u ⟩ \langle F(u),z-u\rangle=\langle F(z),z-u\rangle ⟨ F ( u ) , z − u ⟩ = ⟨ F ( z ) , z − u ⟩ . Hence, the Minty gap coincides with the strong gap. Over the product of balls and a segment, the supremum is computed coordinatewise:
Gap Z M ( x , t , y ) = a ⟨ A x ∗ , y ⟩ + Γ t L 1 + a D 3 ∥ A y ∥ + a D 3 ∥ A x − s ∥ ≥ a D 3 ∥ A x − s ∥ = 24 η D ∥ A x − s ∥ . \begin{aligned}
\operatorname{Gap}^{\mathrm{M}}_Z(x,t,y)=a\langle Ax^*,y\rangle+\frac{\Gamma t}{L_1}+\frac{aD}{3}\lVert Ay\rVert+\frac{aD}{3}\lVert Ax-s\rVert\\
&\ge\frac{aD}{3}\lVert Ax-s\rVert=\frac{24\eta}{D}\lVert Ax-s\rVert.
\end{aligned} Gap Z M ( x , t , y ) = a ⟨ A x ∗ , y ⟩ + L 1 Γ t + 3 a D ∥ A y ∥ + 3 a D ∥ A x − s ∥ ≥ 3 a D ∥ A x − s ∥ = D 24 η ∥ A x − s ∥ .
The last line uses t ≥ 0 t\ge0 t ≥ 0 and ⟨ A x ∗ , y ⟩ = ⟨ x ∗ , A y ⟩ ≥ − ( D / 12 ) ∥ A y ∥ \langle Ax^*,y\rangle=\langle x^*,Ay\rangle\ge-(D/12)\lVert Ay\rVert ⟨ A x ∗ , y ⟩ = ⟨ x ∗ , A y ⟩ ≥ − ( D /12 ) ∥ A y ∥ : the negative term is absorbed by the positive term D ∥ A y ∥ / 3 D\lVert Ay\rVert/3 D ∥ A y ∥ /3 . A gap ≤ η \le\eta ≤ η implies ∥ A x − s ∥ ≤ D / 24 \lVert Ax-s\rVert\le D/24 ∥ A x − s ∥ ≤ D /24 , and therefore
∥ A 12 ∥ b ∥ D x − b ∥ ≤ 12 ∥ b ∥ D D 24 = ∥ b ∥ 2 . \left\lVert A\frac{12\lVert b\rVert}{D}x-b\right\rVert\le\frac{12\lVert b\rVert}{D}\frac{D}{24}=\frac{\lVert b\rVert}{2}. A D 12 ∥ b ∥ x − b ≤ D 12 ∥ b ∥ 24 D = 2 ∥ b ∥ .
Two multiplications by A A A simulate one query. Therefore, 1 + 2 T ≳ κ 1+2T\gtrsim\kappa 1 + 2 T ≳ κ .
To remove the additive one for bounded κ \kappa κ , we take A = I A=I A = I and b = ± e 1 b=\pm e_1 b = ± e 1 in the same dimension. A successful answer requires ∥ x ∓ ( D / 12 ) e 1 ∥ ≤ D / 24 \lVert x\mp(D/12)e_1\rVert\le D/24 ∥ x ∓ ( D /12 ) e 1 ∥ ≤ D /24 , respectively. These two balls are disjoint. Before the first query, the algorithm cannot distinguish the instances. If the probability of making at least one query equals p p p , the average success probability over the two instances is at most p + ( 1 − p ) / 2 p+(1-p)/2 p + ( 1 − p ) /2 . Success probability ≥ 2 / 3 \ge2/3 ≥ 2/3 requires p ≥ 1 / 3 p\ge1/3 p ≥ 1/3 , hence T ≥ 1 / 3 T\ge1/3 T ≥ 1/3 . Together with the large-κ \kappa κ bound, this gives T ≳ κ = Θ ( Γ D 2 / η ) T\gtrsim\kappa=\Theta(\Gamma D^2/\eta) T ≳ κ = Θ ( Γ D 2 / η ) for all κ ≥ 1 \kappa\ge1 κ ≥ 1 .
The exact projection onto Z \mathbb{Z} Z does not help to extract information about A , b A,b A , b : the geometry of Z \mathbb{Z} Z does not depend on them. Since Γ \Gamma Γ is arbitrarily large, the complexity of the class without control of the norm at the solution is infinite. □ \square □
Summary of known bounds
Table 1. Monotone operators: number of calls to the operator oracle.
Notation. R = ∥ z 0 − z ∗ ∥ R=\lVert z_0-z^*\rVert R = ∥ z 0 − z ∗ ∥ , D D D is the diameter of the compact set Z Z Z , U ∗ U^* U ∗ is the solution set, and O ( ⋅ ) O(\cdot) O ( ⋅ ) and Ω ( ⋅ ) \Omega(\cdot) Ω ( ⋅ ) hide absolute constants. The operator is monotone and the problem is posed on the whole R d \mathbb{R}^d R d unless stated otherwise.
Smoothness. L L L : the operator is L L L -Lipschitz. sym.: symmetric ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -Lipschitz continuity (1) , ∥ F ( u ) − F ( v ) ∥ ≤ ( L 0 + L 1 sup w ∈ [ u , v ] ∥ F ( w ) ∥ ) ∥ u − v ∥ \lVert F(u)-F(v)\rVert\le\left(L_0+L_1\sup_{w\in[u,v]}\lVert F(w)\rVert\right)\lVert u-v\rVert ∥ F ( u ) − F ( v )∥ ≤ ( L 0 + L 1 sup w ∈ [ u , v ] ∥ F ( w )∥ ) ∥ u − v ∥ . For C 1 C^1 C 1 operators, this is equivalent to ∥ D F ( z ) ∥ ≤ L 0 + L 1 ∥ F ( z ) ∥ \lVert DF(z)\rVert\le L_0+L_1\lVert F(z)\rVert ∥ D F ( z )∥ ≤ L 0 + L 1 ∥ F ( z )∥ .
α \alpha α -sym.: α \alpha α -symmetric generalized smoothness Vankov et al. [28 ] , which coincides with sym. for α = 1 \alpha=1 α = 1 .