Безградиентные методы решения седловых задач и не только / Gradient-Free Methods for Saddle-Point Problems and Beyond тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Безносиков Александр Николаевич

• Безносиков Александр Николаевич
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Безносиков Александр Николаевич

Contents

List of Figures viii

List of Tables x

1 Introduction

1.1 Relevance and Importance

1.1.1 Saddle-Point Problems

1.1.2 Gradient-Free Methods

1.2 Contribution and Scientific Novelty

1.3 Presentations and Validation of Research Results

1.4 Publications 4 1.4.1 Excluded Papers

1.5 Thesis Structure

2 Two-Point Feedback and Non-Smooth Saddle-Point Problems

2.1 Introduction 6 2.1.1 Our contributions

2.2 Notation and Definitions

2.3 Main Result

2.3.1 Non-smooth saddle-point problem

2.3.2 Admissible Set Analysis

2.4 Numerical Experiments

3 Two-Point Feedback and Smooth Saddle-Point Problems

3.1 Introduction 20 3.1.1 Our contribution and related works

3.2 Problem setup and assumptions

3.3 Notation and Definitions

3.4 Zeroth-Order Methods

3.5 1/2-Order Methods

3.5.1 Lagrange multiplier method

3.5.2 Universal approach with Full gradient method

3.6 Practice part

4 One-Point Feedback and (Non-)Smooth Saddle-Point Problems

4.1 Introduction

4.1.1 Related works

4.1.2 Our contribution

4.2 Preliminaries

4.2.1 Notation

4.2.2 Settings and assumptions

4.3 Theoretical results

4.3.1 Non-smooth case

4.3.2 Smooth case

4.3.3 Higher-order smooth case

4.4 Experiments

5 Gradient-Free Non-Smooth Problems via First-Order Methods for Smooth

Problems

5.1 Problem Formulation

5.2 Smoothing Scheme

5.3 Applications Of the Smoothing Scheme

5.3.1 Stochastic Optimization

5.3.2 Finite-sum Problems

5.3.3 Strongly Convex Problems

5.3.4 Saddle-point Problems

5.3.5 Distributed Optimization

5.4 Discussion

5.4.1 Superposition Of Different Techniques

5.4.2 Batching Technique

5.5 Experiments

5.5.1 Reinforcement Learning

5.5.2 Robust Linear Regression

5.5.3 Support Vector Machine

5.5.4 Conclusion On Experiments

References

A Appendix for Chapter

A.1 General facts

A.2 Proof for Section

A.3 Proof for Section

A.4 Additional experiments

B Appendix for Chapter

B.1 General facts and technical lemmas 92 B.2 Proof for Section 3.3 93 B.3 Proof for Section 3.4 99 B.4 Other approach for e in Algorithm

B.5 Proof for Section

C Appendix for Chapter

C.1 General facts 115 C.2 Proofs for Section 4.3.1 115 C.3 Proofs for Section 4.3.2 127 C.4 Proofs for Section

C.5 Kernel examples

D Appendix for Chapter

D.1 Additional Experiments 135 D.1.1 Adversarial Attack 135 D.1.2 RL Experiments 136 D.1.3 Robust Linear Regression 136 D.1.4 Support Vector Machine

D.2 Missing proofs

D.2.1 Reducing Variance under Batching in p-norm

D.2.2 Proof of Theorem 5.2.1 (Properties of fy)

D.2.3 Proof of Theorem 5.2.2 (Properties of (x, e))

D.2.4 Proof of Theorem

D.2.5 Lxy Estimate

D.2.6 Proof of Theorem

D.3 Noisy Value of Function

List of Figures

2.1 zoSPA with 0 - 40 % noise and Mirror Descent applied to solve saddle-problem

(2.19)

3.1 Different algorithms with Full coordinate and Random direction oracles applied to

solve saddle-problem (3.10)

4.1 Algorithm 5 with (4.5) (ZO Std) and (4.14) (ZO RF) approximations, Algorithm 6 (ZO Ker) and Mirror Descent (FO) applied to solve saddle-problem (4.27) with noise level: (a) 5%, (b) 10%. The experiment was carried out 10 times for each method: the bold line denotes the mean trajectory, the shaded area denotes the standard deviation from the mean trajectory

5.1 Actor's reward for ADAM with Forward and Central differences for various " and exact gradient ADAM. lr= 10"5

5.2 Loss for abalone scale dataset with batch size = 100, learning rate is 0.1 and " = 10_5

5.3 Loss for a9a dataset with n = 10_5, batch size = 100, Ir = 0.1. " = 10_5

A.1 zoSPA with noise, Mirror Descent applied to solve saddle-problem (2.19) size of: (a)

- 200 x 200, (b) - 500 x

A.2 zoSPA, Mirror Descent applied to solve saddle-problem (2.19): (a) - with different

random seeds for matrix, (b) - with different "saddle sizes", (c) - with other oracle

A.3 zoSPA, Mirror Descent applied to solve saddle-problem: (a)(A.16), (b) (A.17),

(c)(A.19)

A.4 zoSPA, Mirror Descent applied to solve saddle-problem (A.19): (a) zero start, (b)

zero start (scaled), (c) close start

C.1 Examples of kernels from (C.40)

D.1 Comparison of different zeroth-order algorithms for generating n = 50 adversarial examples for digit class "4" with A = 0.1. Left: Loss (D.2) with Central, Forward, Central Coord and Forward Coord where Ir = 0.01 and " = 0.01. Right: Distortion(1J2n=1 ||afdv — ai||2) average in n = 50 generated adversarial examples

D.2 Left: Actor's reward for ADAM with Forward and Central with various " and true gradient ADAM, where Ir = 0.001. Right: Actor's reward for ADAM with Forward and Central with various " and true gradient ADAM, where Ir =

D.3 Left: Actor's reward for true gradient ADAM with different learning rates. Right: Actor's reward for 25000 iterations of ADAM with Forward and Central finite difference with various " = 10_5 and true gradient ADAM, where Ir =

D.4 Left: Actor's reward for ADAM with Forward and Central for " = 10_3 and true gradient ADAM, where Ir = 0.001. Middle: Actor's reward for ADAM with Forward and Central for for " = 10_5 and true gradient ADAM, where Ir = 0.001. Right: Actor's reward for ADAM with Forward and Central for " = 10_7 and true gradient ADAM, where Ir =

D.5 Left: Loss for abalone scale dataset with Ir = 0.4 batch size = 100, " = 10_5, and different ¡i. Right: Loss for abalone scale dataset with Ir = 0.4 batch size = 100, i = 0. and different "

D.6 Left: Loss for abalone scale dataset with Ir = 0.4 batch size = 100, " = 10_5, and different Ir. Right: Loss for abalone scale dataset with Ir = 0.4, i = 0., " = 10_5, and different batch size

D.7 Left: Loss for a9a dataset with i = 10_5, batch size = 100, Ir = 0.1 and different ".

Right: Loss for a9a dataset with i = 10_5, batch size = 100, " = 10_5 and different lr.140 D.8 Loss for a9a dataset with i = 10_5, batch size = 100, Ir = 0.1, " = 10_5 and different

i

D.9 Loss for a9a dataset with i = 10_5, Ir = 0.1, " = 10_5 and different batch size

List of Tables

2.1 Summary of convergence estimation for non-smooth case: p = 2 and p =

2.2 Summary of the part

2.3 • and A in Corollary 2.3.7 in different c&ses

3.1 Comparison of oracle complexity in deterministic setup of different zeroth-order methods with different assumptions on target function f (x, y): C-C - convex-concave, SC-SC - strongly-convex-strongly-concave, NC-SC - nonconvex-strongly-concave; Cst - optimizaation set is constrained, UCst - unconstrained; S - smooth, FS -firmly smooth (see (3.9)), BG - bounded gradients. Here e means the accuracy of the solution, D - the diameter of the optimization set, i - strong convexity constant (see (3.7)), L - smoothness constant (see (3.8)), k = LM - bound of the gradient (||Vxf (x,y)||2 < M, ||Vy f (x, y)||2 < M), n - the sum of the dimensions of the variables x and y, q = 2 for the Euclidean case and q = to for setup of || ■ || i-norm. *convergence on N q^ E (xk, yk) - F(x*,y*)W^\, where F(x, y) = (Vxf (x, y),-Vy f (x, y))

3.2 Comparison of oracle complexity for stochastic part of different first- and zeroth-order methods with different assumptions on f (x,y): see notation in Table 3.1. Here a2

the bound of variance (see (3.3))

4.1 Comparison of oracle complexity of one-point/two-point Oth-order methods for non-smooth/smooth convex minimization (Min) and convex-concave saddle-point (SP) problems under different assumptions. e means the accuracy of the solution, n -dimension of the problem, q = 2 for the Euclidean case and q = to for setup of || ■ ||i-norm.

4.2 Comparison of oracle complexity of one-point/two-point Oth-order methods for non-smooth/smooth strongly-convex minimization (Min) and strongly-convex-strongly-concave saddle-point (SP) problems under different assumptions.

4.3 Summary of convergence estimation for non-smooth case: p = 2 and p =

D.1 Generated adversarial examples for digit "1" class from a random batch of n =

images, where image distortion is defined as 1J2i=1 Watdv — a«||

35

36

138

2

Введение диссертации (часть автореферата) на тему «Безградиентные методы решения седловых задач и не только / Gradient-Free Methods for Saddle-Point Problems and Beyond»

Introduction

In1 this chapter, we give a general introduction with an overview of the developed results in this thesis. All subsequent chapters also contain their own detailed introductions.

1.1 Relevance and Importance 1.1.1 Saddle-Point Problems

In this thesis, we primarily focus on the saddle point or min-max problem:

min max w(x, y). xex yey ,yj

This problem is more complex and more general than the minimization one. Meanwhile, as well as the minimization problem, the saddle point problem has a lot of practical applications. One of the first such applications were tasks from economics and game theory, which have been actively researched since the middle of the previous century [120, 82, 58]. Saddle-point problems also find their application in robust optimization [11, 115, 113], signal processing [140], and, in the last 10 years, they also actively appears in machine learning. Here we can note the already classical stories in supervised learning (with non-separable loss [85]; with non-separable regularizer [4]), unsupervised learning (discriminative clustering [164]; matrix factorization [5]), image denoising [56, 35]. With the rapid development of machine learning, new examples of saddle-point problems that need to be solved have also arisen. One can highlight examples from reinforcement learning [123, 84], adversarial training [105], and GANs [74]. These applications have particularly inspired researchers in recent years. A whole series of papers by various authors builds a bridge between the theory for convex-concave saddle-point problems and learning tasks based on solving non-convex saddle-point problems [44, 70, 108, 37, 101, 124].

Due to the appearance of more and more new practical examples of saddle-point problems, the methods of solving them were also actively developed. The first and the simplest method for solving saddle-point problems is gradient descent. But since we have also maximization group of

xThe work on this thesis was partially supported by Russian Science Foundation (project No. 23-11-00229) and was partially supported by the Ministry of Science and Higher Education of the Russian Federation (Goszadaniye) 075-00337-20-03, project no. 0714-2020-0005.

1

variables, we need to make additional ascent step:

xk+1 = xk - "Vx^(xk, yk),

yk+l = yk + ^(xk ,yk ),

where " > 0 is a step size. The convergence results of the method to the unique solution for strongly convex - strongly concave and smooth problems was obtained in [ , L3 , 14 ], for non-smooth convex-concave problems on bounded domain - in [1( ]. However, in the general unbounded convex-concave case, convergence is lacking [127].

There were many other attempts to recover convergence of gradient-like methods for saddle-point problems [72, 127, 7, 107, 130]. The breakthrough for solving smooth convex-concave saddle-point problems was made in [89], where the idea of the extrapolation for the gradient method was exploited. In particular, the following method (which is called Extragradient) was presented:

xk+1/2 = xk - "Vxp(xk, yk),

yk+1/2 = yk - "Vy^(xk,yk),

xk+1 = xk - "VxV(xk+1/2,yk+1/2), yk+1 = yk - "Vy^(xk+1/2,yk+1/2).

Subsequently, a more rigorous theory [109, 160] and different modifications [128, 113] were obtained later for this method. We can also note other approaches for solving saddle-point problems [161, 116, 106]. Due to the increasing complexity of applied problems, stochastic versions of the mentioned methods had become particularly important (see survey [22] on stochastic optimization of saddle-point problems for more details).

Among such a variety of methods, they all use gradients of the target function, but gradientfree methods for solving saddle-point problems not investigated in any way before this work. Meanwhile, the zero-order methods themselves and with application to saddle-point problems are of great theoretical and practical interest.

1.1.2 Gradient-Free Methods

The concept when only a zero-order oracle is available for the target function is is sometimes referred to as a black-box. It arises when the calculation of gradient is expensive (here we can highlight examples in adversarial training [38], optimization [119], structured-prediction [154]) or impossible (one can note issues in reinforcement learning [59, 39, 138], bandit problem [33, 143], black-box ensemble learning [100]). To make the problem statement even more practical and close to modern applications we assume that we have access inexact values of function <^(x,y, >) with some random noise >. With the help of this oracle, it is possible to make some approximation of the gradient in terms of finite differences. Next we highlight two main approaches for such gradient estimates. The first approach is called a two-point feedback. With this approach, one

can approximate Vxty as follows

n

—(ty(x + • ex, y, >) — <p(x — tex, y, >))ex,

where ex is uniformly distributed on the unit euclidean sphere. For two-point feedback and minimization problems there are a lot of papers with theoretical analysis [49, 119, 66, 143, 54, 80]. An important thing of this approach is the assumption that we were able to obtain the values of the function in points two different points with the same realization of the noise >. But from a practical point of view, this is a very strong and idealistic assumption. Therefore, it is proposed

to consider the concept of one-point feedback [66, 3, 122]:

n

— (<p(x + • ex, y, >+) — — tex, y, >~))ex,

In general >+ = .

In this thesis, we deal with both two-point and one-point feedback for saddle-point problems. In more detail, the contribution of the thesis is outlined in the next section.

1.2 Contribution and Scientific Novelty

All of the results of this work are new and extend the community's knowledge in the field of research. In particular, the results can be summarized as follows:

• We propose the first gradient-free method for solving non-smooth convex-concave saddle-point problems and provide its theoretical convergence analysis. We use the Mirror Descent method with arbitrary Bregman divergence as the base. This allows us to take into account the geometry of the problem and move away from the Euclidean setup. Moreover, in some situations the use of the Bregman divergence suitable for the problem can significantly reduce the total number of zero-order oracle calls. In particular, in the case when the problem on a probability simplex is considered, one can achieve that the oracle complexity of the proposed gradient-free method does not depend on the dimension of the problem, which is unusual for the Euclidean setting where the complexity is directly proportional to the dimension.

• We present several new zero-order methods for smooth saddle-point problems. Moreover, the proposed methods are not only new but also the first in the literature. We consider both classical smooth problems and firmly smooth problems, for each class of problems we give a different method and convergence results. As in the previous point on non-smooth problems, the consideration of the geometry of the problem and the use of the corresponding Bregman divergence help to improve the theoretical guarantees for the estimate on the oracle complexity of the methods.

• The methods from the first two points of contribution use a two-point feedback. But as noted earlier, the one-point feedback is closer to practical problems. Motivated by this, we

propose the first methods for solving non-smooth and smooth convex-concave saddle-point problems using one-point feedback. Here we also consider an arbitrary geometric setting via an arbitrary Bregman divergence, and hence obtain bonuses in terms of the dependence of theoretical convergence on the dimension of the problem. Moreover, we focus not only on the non-smooth and smooth cases, but also on the setup with high-order smoothness, in which we additionally use the kernel technique to approximate the gradient. Theoretical and experimental analyses are included.

• Following the idea that the theoretical analysis of gradient-free methods for non-smooth problems uses an artificial stochastic smoothing technique, we present a unified approach that allows adapting any stochastic gradient method for smooth problems to solve non-smooth optimization problems using only zero-order oracles. As a special case of our general analysis, we consider variance reduction techniques, parallelization of the gradient approximation batching process, and methods for non-smooth saddle point problem.

1.3 Presentations and Validation of Research Results

The results of this thesis were presented at the following conferences and seminars.

• 39th International Conference on Machine Learning (ICML 2022), "The power of first-order smooth optimization for black-box non-smooth problems", Baltimore, 20 July, 2022.

• International conference "Mathematical Optimization Theory and Operations Research", "Gradient-free methods with inexact oracle for convex-concave stochastic saddle-point problem", online, 7 July, 2020.

• International conference "Mathematical Optimization Theory and Operations Research", "Zeroth-order algorithms for smooth saddle-point problems", Irkutsk, 7 July, 2021.

• International conference "Mathematical Optimization Theory and Operations Research", "One-point gradient-free methods for smooth and non-smooth saddle-point problems", Irkutsk, 8 July, 2021.

1.4 Publications

Chapters 2-5 are based on the following papers, respectively:

[25] Aleksandr Beznosikov, Abdurakhmon Sadiev, and Alexander Gasnikov. Gradient-free methods with inexact oracle for convex-concave stochastic saddle-point problem. In International Conference on Mathematical Optimization Theory and Operations Research, pages 105-119. Springer, 2020.

[136] Abdurakhmon Sadiev, Aleksandr Beznosikov, Pavel Dvurechensky, and Alexander Gasnikov. Zeroth-order algorithms for smooth saddle-point problems. In International Conference

on Mathematical Optimization Theory and Operations Research, pages 71-85. Springer, 2021.

[21] Aleksandr Beznosikov, Vasilii Novitskii, and Alexander Gasnikov. One-point gradient-free methods for smooth and non-smooth saddle-point problems. In Mathematical Optimization Theory and Operations Research: 20th International Conference, MOTOR 2021, Irkutsk, Russia, July 5-10, 2021, Proceedings 20, pages 144-158. Springer, 2021.

[65] Alexander Gasnikov, Anton Novitskii, Vasilii Novitskii, Farshed Abdukhakimov, Dmitry Kamzolov, Aleksandr Beznosikov, Martin Takac, Pavel Dvurechensky, and Bin Gu. The power of first-order smooth optimization for black-box non-smooth problems. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 7241-7265. PMLR, 17-23 July 2022.

1.4.1 Excluded Papers

During my PhD studies, I also explored distributed algorithms with compression [20, 23, 16, 17], problems under similarity assumption [27, 91, 16, 17], local steps technique [26, 15], decentralized optimization [26, 132, 24, 29, 27, 137, 81, 92], methods for variational inequalities and saddle point problems [26, 132, 24, 29, 27, 14, 91, 92, 13, 18], variance reduction approach [28, 135, 92, 18].

1.5 Thesis Structure

The thesis consists of an introduction, 4 main chapters, list of 170 references, and 4 chapters in the Appendix with technical details, some proofs, and auxiliary results.

Chapter

Two-Point Feedback and Non-Smooth Saddle-Point Problems