<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>A Catalyst Framework for Minimax Optimization</title></titleStmt>
			<publicationStmt>
				<publisher></publisher>
				<date>2021</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10430816</idno>
					<idno type="doi"></idno>
					<title level='j'>Advances in neural information processing systems</title>
<idno>1049-5258</idno>
<biblScope unit="volume"></biblScope>
<biblScope unit="issue"></biblScope>					

					<author>J. Yang</author><author>S. Zhang</author><author>N. Kiyavash</author><author>N. He</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[We introduce a generic two-loop scheme for smooth minimax optimization with strongly-convex-concave objectives. Our approach applies the accelerated proximal point framework (or Catalyst) to the associated dual problem and takes full advantage of existing gradient-based algorithms to solve a sequence of well-balanced strongly-convex-strongly-concave minimax problems. Despite its simplicity, this leads to a family of near-optimal algorithms with improved complexity over all existing methods designed for strongly-convex-concave minimax problems. Additionally, we obtain the first variance-reduced algorithms for this class of minimax problems with finite-sum structure and establish faster convergence rate than batch algorithms. Furthermore, when extended to the nonconvex-concave minimax optimization, our algorithm again achieves the state-of-the-art complexity for finding a stationary point. We carry out several numerical experiments showcasing the superiority of the Catalyst framework in practice.
AlgorithmsOracle Complexity number of loops prefix MINIMAX-APPA [24] O / √ µ log 3 (1/ ) 3 Yescan be attained by some existing algorithms. For example, extragradient method (EG) achieves the optimal O(1/ ) complexity for smooth convex-concave minimax problems, and the optimal O(κ log(1/ )) complexity for well-balanced strongly-convex-strongly-concave minimax problems, where the x-component and y-component of the objective share the same condition number κ [50].]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1">Introduction</head><p>Minimax optimization has been extensively studied in past decades in the communities of mathematics, economics, and operations research. Recent years have witnessed a surge of its applications in machine learning, including generative adversarial networks <ref type="bibr">[16]</ref>, adversarial training <ref type="bibr">[47,</ref><ref type="bibr">28]</ref>, distributionally robust optimization <ref type="bibr">[31,</ref><ref type="bibr">1]</ref>, reinforcement learning <ref type="bibr">[8,</ref><ref type="bibr">9]</ref>, and many others. The problem of interest in such applications is often a smooth minimax optimization problem (also referred to as saddle point problems):</p><p>where the function f : R d1 &#215; R d2 &#8594; R is smooth (i.e., gradient Lipschitz), X is a convex set in R m , and Y is a convex and compact set in R n . In many machine learning applications, f has a finite sum structure, that is f (x, y) = 1 n n i=1 f i (x, y), where each component corresponds to a loss associated with single observation.</p><p>A significant body of first-order algorithms for minimax optimization exists in the literature, ranging from the classical projection method <ref type="bibr">[42]</ref>, Korpelevich's extragradient method <ref type="bibr">[20]</ref>, Nemirovski's Mirror Prox algorithm <ref type="bibr">[32]</ref>, Nesterov's dual extrapolation method <ref type="bibr">[34]</ref>, Tseng's accelerated proximal gradient algorithm <ref type="bibr">[46]</ref>, to many recent hybrid or randomized algorithms, e.g., <ref type="bibr">[30,</ref><ref type="bibr">17,</ref><ref type="bibr">38,</ref><ref type="bibr">19,</ref><ref type="bibr">6,</ref><ref type="bibr">25]</ref>, just to name a few. Most of these existing work and theoretical analyses are limited to the following settings (i) the strongly-convex-strongly-concave setting (e.g., <ref type="bibr">[45,</ref><ref type="bibr">29,</ref><ref type="bibr">15]</ref>), (ii) the general convexconcave setting (e.g., <ref type="bibr">[32,</ref><ref type="bibr">34]</ref>), and (iii) the special bilinear convex-concave setting (e.g., <ref type="bibr">[5,</ref><ref type="bibr">48,</ref><ref type="bibr">7]</ref>. The lower complexity bounds for these three settings established in <ref type="bibr">[50]</ref>, <ref type="bibr">[33]</ref>, <ref type="bibr">[37]</ref>, respectively, Table <ref type="table">1</ref>: Comparison with other algorithms for general strongly-convex-concave setting. For simplicity, we ignore the dependency on and &#181; inside log. The lower complexity bound is &#8486; / &#8730; &#181; <ref type="bibr">[37]</ref>.</p><p>Last column indicates whether the algorithm requires the knowledge of target accuracy in advance.</p><p>All algorithms here have the &#213;(D Y ) dependency on the diameter of Y in oracle complexity.</p><p>However, there are relatively few results outside of these settings. Of particular interests are the following two settings: f (x, &#8226;) is concave but not strongly-concave for any x &#8712; X , while f (&#8226;, y) could be strongly-convex or even nonconvex. Strongly-convex-concave minimax optimization covers broad applications in game theory, imaging, distributionally robust optimization, etc. While the special bilinear case of this setting has been studied extensively in the literature, the general case is less explored. In fact, strongly-convex-concave minimax optimization has also been routinely used as a building block for solving nonconvex-concave minimax problems <ref type="bibr">[40,</ref><ref type="bibr">44]</ref>. Hence, we mainly focus on the strongly-convex-concave setting.</p><p>For strongly-convex-concave minimax problems, the lower complexity bound of first-order algorithms is &#8486; / &#8730; &#181; for achieving an -duality-gap <ref type="bibr">[37]</ref>, where is the smoothness constant and &#181; is the strong convexity constant. Recently, <ref type="bibr">[44]</ref> proposed the so-called dual implicit accelerated gradient algorithm (DIAG) that achieves the first-order oracle complexity of O 3/2 /(&#181; &#8730; ) log 2 (1/ ) . A similar complexity bound was obtained from the primal-dual smoothing method in <ref type="bibr">[51]</ref>. More recently, <ref type="bibr">[24]</ref> introduced the MINIMAX-APPA algorithm that further improves the complexity by shaving off a factor of O( /&#181;), yielding a near-optimal convergence rate up to the logarithmic factor. However, these algorithms are fairly complicated as they stack several procedures including accelerated gradient descent on x, accelerated gradient ascent on y, and accelerated proximal point algorithm, in different manners, thus requiring at least three loops. In addition to the complicated procedure, the latter two algorithms require an additional layer of smoothing, and solve the surrogate problem min x&#8712;X max y&#8712;Y f (x, y)+O( ) y 2 . In practice, how to select a good smoothing parameter of order O( ) remains elusive.</p><p>Meanwhile, it is unclear how these sophisticated algorithms can be integrated with variance-reduction techniques to solve strongly-convex-concave minimax problems with finite-sum structure efficiently. Most existing variance-reduced algorithms in minimax optimization focus on strongly-convexstrongly-concave setting, e.g., SVRG and SAGA <ref type="bibr">[38]</ref>, SPD1-VR <ref type="bibr">[43]</ref>, SVRE <ref type="bibr">[6]</ref>, Point-SAGA <ref type="bibr">[26]</ref>, primal-dual SVRG <ref type="bibr">[11]</ref>, variance reduced prox-method <ref type="bibr">[4]</ref>, etc. These algorithms typically preserve the linear convergence of batch algorithms, yet with cheaper per-iteration cost and improved complexity. Outside of this regime, few results are known <ref type="bibr">[27,</ref><ref type="bibr">49]</ref>. To the best of our knowledge, the design of efficient variance reduction methods for finite-sum structured minimax problems under the strongly-convex-concave or nonconvex-concave settings remains largely unexplored. This raises the question: can we simply leverage the rich off-the-shelf methods designed for stronglyconvex-strongly-concave minimax problems to these unexplored settings of interest? Inspired by the success of the Catalyst framework and accelerated APPA that use gradient-based algorithms originally designed for strongly convex minimization problems to minimize convex/nonconvex objectives <ref type="bibr">[22,</ref><ref type="bibr">21,</ref><ref type="bibr">39,</ref><ref type="bibr">13]</ref>, we introduce a generic Catalyst framework for minimax optimization. Rooted in an inexact accelerated proximal point framework, the idea is to repeatedly solve the following auxiliary strongly-convex-strongly-concave problem using an existing method M:</p><p>While the algorithmic extension looks straightforward, selecting appropriate proximal parameters &#964; x , &#964; y , the prox centers xt , z t , and the method M for solving the auxiliary problems, are critical and make a huge difference in the overall complexity. Our key insight is that when the condition numbers of the auxiliary problems are well balanced, they become relatively easy to solve and simply applying existing algorithms such as extragradient method as M would suffice. For instance, in the strongly-convex-concave setting, we set &#964; x = 0, &#964; y = &#181;. In sharp contrast, the MINIMAX-APPA algorithm <ref type="bibr">[24]</ref> uses &#964; x = 1 and &#964; y = O( ), which results in extra complications (i.e., a two-loop algorithm) in solving the auxiliary problems.</p><p>Based on the generic Catalyst framework, we establish a number of interesting results:</p><p>(i) For strongly-convex-concave minimax optimization, we develop a family of two-loop algorithms with near-optimal complexity and reduced order of the logarithmic factor. In fact, simply combing Catalyst with extragradient method yields the complexity, O / &#8730; &#181; log(1/ ) , which improves over all existing methods, as shown in Table <ref type="table">1</ref>.</p><p>(ii) For nonconvex-concave minimax optimization, we provide a simple two-time-scale inexact proximal point algorithm for finding an -stationary point that matches the state-of-the-art complexity of &#213; 2 -3 .</p><p>(iii) For minimax problems with finite-sum structure, we provide a family of variance-reduced algorithms for the strongly-convex-concave setting, improving the &#213; n &#175; / &#8730; &#181; complexity of the best batch algorithm to &#213; &#175; 2 / &#181; 3 &#8744;n</p><p>&#8730; , and to &#213; &#175; / &#8730; &#181; &#8744;n</p><p>&#8730; with additional assumption on cocoercive gradient. When extending to the nonconvex-concave setting, we improve the &#213; n &#175; 2 -3 complexity of the best batch algorithm to &#213; n  For the ease of notation, we refer to the strongly-convex-strongly-concave setting as SC-SC for short, or (&#181; 1 , &#181; 2 )-SC-SC if the strong convexity and strong concavity constants are given by &#181; 1 , &#181; 2 . Similarly, SC-C or &#181;-SC-C refers to the strongly-convex-concave setting, and NC-C to the nonconvexconcave setting. Throughout the paper, &#8226; stands for the standard 2 -norm.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2">A Catalyst Framework for SC-C Minimax Optimization</head><p>In this section, we focus on solving strongly-convex-concave minimax problems and introduce a general Catalyst scheme. We formally make the following assumptions.</p><p>and f (x, &#8226;) is concave for all x in X . X and Y are convex and closed sets, and Y is bounded with diameter D Y = max y,y &#8712;Y y -y . There exists at least one saddle point</p><p>Assumption 2 (Lipschitz gradient). There exists a positive constant such that</p><p>holds for all</p><p>The goal is to find an -saddle point (x, &#563;) such that gap f (x, &#563;) := max y&#8712;Y f (x, y)min x&#8712;X f (x, &#563;) &#8804; . We call gap f (x, &#563;) the primal-dual gap, which implies both primal optimality gap and dual optimality gap. If = 0, then (x, &#563;) is a saddle point.</p><p>We present a generic Catalyst scheme in Algorithm 1. Analogous to its prototype <ref type="bibr">[22,</ref><ref type="bibr">39]</ref>, this scheme consists of several important components: an inexact accelerated proximal point step as the wrapper, a linearly-convergent first-order method M as the workhorse, as well as carefully chosen parameters and stopping criteria.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Algorithm 1 Catalyst for SC-C Minimax Optimization</head><p>1: Input: initial point (x 0 , y 0 ), parameter &#964; &gt; 0 2: Initialization:</p><p>Find an inexact solution (x t , y t ) to the following problem with algorithm M</p><p>v t = y t-1 + 1 &#945;t (y t -y t-1 );</p><p>Choose</p><p>8: end for 9: Output:</p><p>Inexact accelerated proximal point step. The main idea is to repeatedly solve a series of regularized problems by adding a quadratic term in y to the original problem:</p><p>where &#964; &gt; 0 is a regularization parameter (to be specified later) and z t is the prox-center. The prox-centers {z t } t are built on extrapolation steps of Nesterov <ref type="bibr">[35]</ref>. Noticeably, this step can also be viewed as applying the original Catalyst scheme <ref type="bibr">[22]</ref> to the dual function h(y) := min x&#8712;X f (x, y).</p><p>The major distinction is that we do not have access to the closed-form dual function, which causes difficulty in measuring the inexactness of auxiliary problems and evaluating the solution performance in terms of the primal-dual gap, instead of dual optimality.</p><p>Linearly-convergent algorithm M. By construction, the series of auxiliary problems ( ) are (&#181;, &#964; )-SC-SC. Thus, they can be solved by a wide spectrum of first-order algorithms established in the literature, at a linear convergence rate, including gradient descent ascent (GDA), extra-gradient method (EG), optimistic gradient descent ascent (OGDA), SVRG, to name a few. Yet, the dependence on the condition number may vary across different algorithms. We assume that any deterministic algorithm M when solving the (&#181;, &#964; )-SC-SC minimax problem has a linear convergence rate such that</p><p>and any stochastic algorithm M satisfies</p><p>where &#8710; M,&#964; depends on &#964; and algorithm M. For instance, when EG or OGDA is adopted,</p><p>, provided that the objective has the finite-sum structure and each component is -smooth <ref type="bibr">[38]</ref>.</p><p>Stopping criteria. To guarantee the overall convergence in terms of primal-dual gap, it is necessary to approximately solve the auxiliary problem ( ) to moderate accuracy and ensure the entire pair (x, y) converges properly. For the sake of generalization, we adopt the criterion specified in (3) in our generic scheme. The stopping criterion can be achieved by most existing minimax optimization algorithms after sufficient iterations. Yet, it could still be hard to check in practice because min x&#8712;X f (x, y t ) and max y&#8712;Y &#8711; y ft (x t , y t ) T (y -y t ) are not always computable. The following lemma shows that this issue can be alleviated, at the minor cost of a full gradient evaluation and a projection step. Lemma 2.1. Consider a function f (x, y) that is (&#181; 1 , &#181; 2 )-SC-SC and has &#732; -Lipschitz gradient on X &#215; Y. Let z * = (x * , y * ) be the saddle point, i.e, the solution to the minimax optimization</p><p>to be the point after one step of projected gradient descent ascent:</p><p>where</p><p>Based on this observation, we can therefore use the following easy-to-check criterion:</p><p>x</p><p>Note that many algorithms such as EG or GDA, already compute ([x] &#946; , [y] &#946; ) with &#946; being the stepsize, so there is no additional computation cost to check criterion <ref type="bibr">(6)</ref>.</p><p>Choice of regularization parameter. As we can see, the smaller &#964; is, the auxiliary problem is closer to the original problem. However, smaller &#964; will give rise to worse conditions of the auxiliary problems, making them harder to solve. We will discuss the dependence of the inner and outer loop complexities on &#964; and provide a guideline for choosing &#964; for different M.</p><p>As a final remark, we stress that the idea of using (accelerated) proximal point algorithm for minimax optimization is by no means new. Similar ideas have appeared in different contexts. However, they differ from our scheme in one way or the other. To list a few: <ref type="bibr">[41,</ref><ref type="bibr">30,</ref><ref type="bibr">23,</ref><ref type="bibr">38]</ref> considered the inexact PPA for C-C or NC-NC minimax problems by adding quadratic terms in both x and y; <ref type="bibr">[40,</ref><ref type="bibr">44]</ref> considered the inexact PPA for NC-C minimax problems, by adding a quadratic term in x; <ref type="bibr">[24]</ref> considered the inexact accelerated PPA for SC-SC minimax problems by adding a quadratic term in x. On the other hand, a number of work, e.g., <ref type="bibr">[19,</ref><ref type="bibr">24,</ref><ref type="bibr">51</ref>] also add a quadratic term in y to the minimax optimization, but in the form O( ) y 2 , which is completely different from PPA. Besides these differences, the subroutines used to solve the auxiliary minimax problems and choices of regularization parameters in these work are quite distinct from ours. Lastly, we point out that the proposed framework is closely related to the inexact accelerated augmented Lagrangian method designed for linearly constrained optimization problems <ref type="bibr">[18]</ref>, which can be viewed as a special case by setting f (x, y) as the Lagrangian dual. In spite of this, approaches for solving the auxiliary problems are completely different, as is theoretical analysis.</p><p>3 Main Results</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.1">Convergence Analysis</head><p>In order to derive the total complexity, we first establish the complexity of the outer loop and then combine it with the inner loop complexity from algorithm M. We then discuss the optimal choice of the regularization parameter &#964; for different settings. Theorem 3.1 (Outer-loop complexity). Suppose function f satisfies Assumptions 1 and 2. The output (x T , y T ) from Algorithm 1 satisfies</p><p>where D Y = max y,y &#8712;Y y -y is the diameter of Y. If we further choose,</p><p>) Remark 1. The above result is true without requiring strong convexity in x; only convexity-concavity of f (x, y) is sufficient. In addition, the regularization parameter &#964; can be any positive value. Hence, Algorithm 1 is quite flexible. Because 2/(t + 2) 2 &#8804; &#945; 2 t &#8804; 4/(t + 1) 2 [39], Theorem 3.1 implies that the algorithm finds a point with primal-dual gap within O( &#964; / D Y ) outer-loop iterations. Notice that the outer-loop complexity decreases as &#964; decreases.</p><p>We now turn to the inner loop complexity. By construction, the auxiliary problem ( ) is (&#181;, &#964; )-SC-SC and &#732; smooth with &#732; = + &#964; , which can be solved by many existing first-order algorithms at a linear convergence rate. Below we present the complexity of the inner loop with warm start. Proposition 3.1 (Inner-loop complexity). Suppose we apply a linearly convergent algorithm M described by ( <ref type="formula">4</ref>) or <ref type="bibr">(5)</ref> to solve the auxiliary problem ( ) and set the initial point to be (x t-1 , z t ) at iteration t. Let K( (t) ) denote the number of iterations (expected number of iterations if M is stochastic) for M to find a point satisfying <ref type="bibr">(6)</ref>. Then K(</p><p>In practice, choosing a good initial point to warm start algorithm M can be helpful in accelerating the convergence. The above proposition shows that in theory, using a simple warm start strategy helps alleviate the logarithmic dependence on the distance from the initial point to the optimal point. Without the warm start strategy, one would require X to be bounded and K(</p><p>) .</p><p>Here we do not require boundedness on X .</p><p>As we can see, the choice of &#964; plays a crucial role since it affects both inner-loop and outer-loop complexities. Combining the above two results immediately leads to the total complexity: Corollary 3.2 (Total complexity). Suppose Assumptions 1, 2 hold, and the subproblems are solved by a linearly convergent algorithm M to satisfy the stopping criterion (3) or ( <ref type="formula">6</ref>) with accuracy (t)  as specified in Theorem 3.1. For Algorithm 1 to find an -saddle point, the total number of gradient evaluations (expected number if M is stochastic) is</p><p>For any choice of linearly-convergent method M and any regularization parameter &#964; , the oracle complexity is guaranteed to be O (D Y / &#8730; log(D Y / )), which is optimal both in and D Y up to a logarithmic factor <ref type="bibr">[37]</ref>. The dependence on the condition number will solely be determined by the term &#8710; M,&#964; &#8730; &#964; , which we analyze in detail below for specific algorithms.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.2">Specific Algorithms and Complexities</head><p>In order to minimize the total complexity, we should choose the regularization parameter &#964; that min &#964; &gt;0 &#8710; M,&#964; &#8730; &#964; . Below we derive the choice of optimal &#964; for different algorithms M and present the corresponding total complexity. Table <ref type="table">2</ref> summarizes this for several algorithms we consider.</p><p>Deterministic first-order algorithms. If we adopt the simplest gradient descent ascent (GDA) as M for solving the subproblem, then &#8710; M,&#964; = +&#964; 2 min{&#181;,&#964; } 2 <ref type="bibr">[12]</ref>. If M is extra-gradient method (EG) or optimistic gradient descent ascent (OGDA), then &#8710; M,&#964; = +&#964; 4 min{&#181;,&#964; } <ref type="bibr">[45,</ref><ref type="bibr">15,</ref><ref type="bibr">2]</ref>. Minimizing &#8710; M,&#964; &#8730; &#964; for both cases yields that the optimal choice for &#964; is &#181;. In particular, when using EG or OGDA, the total complexity becomes</p><p>Remark 2. This complexity matches the lower complexity bound for this class of problems <ref type="bibr">[37]</ref> in , , &#181; and D Y , up to a logarithmic factor. In addition, it improves over the best-known result, which was recently established in <ref type="bibr">[24]</ref>, which has a cubic order on the logarithmic factor and requires boundedness of X .</p><p>A key observation is that by setting &#964; = &#181;, the auxiliary problem ( ) becomes (&#181;, &#181;)-SC-SC, and it is known that simple EG or OGDA achieves the optimal complexity for solving this class of well-balanced SC-SC problems <ref type="bibr">[50]</ref>. Unlike <ref type="bibr">[44,</ref><ref type="bibr">24]</ref> , their subproblems are harder to solve because of ill-balanced condition numbers, thus leading to an inferior complexity.</p><p>Besides the complexity improvement, our algorithm is significantly simpler and easier to implement than the current state-of-the-arts. The DIAG algorithm in <ref type="bibr">[44]</ref> applies Nesterov's accelerated gradient ascent to the dual function and an additional two-loop algorithm to solve their subproblems. The MINIMAX-APPA algorithm in <ref type="bibr">[24]</ref> adds a smoothing term in y and applies a triple-loop algorithm to solve the auxiliary SC-SC problem. In contrast, our algorithm only requires two loops, does not require to prefix accuracy , and has fewer tuning parameters. Results are summarized in Table <ref type="table">1</ref>. </p><p>Stochastic variance-reduced algorithms. We now consider finite-sum-structure minimax problems, min x&#8712;X max y&#8712;Y f (x, y)</p><p>where each component f i has i -Lipschitz gradients. Denote &#175; =<ref type="foot">foot_0</ref> n n i=1 i as the average of smoothness constants. The resulting SC-SC subproblem ( ) also has the finite-sum structure and can be solved by a number of linearly-convergent variance-reduced algorithms, such as SVRG, SAGA <ref type="bibr">[38]</ref>, and SVRE <ref type="bibr">[6]</ref>.</p><p>If using SVRG or SAGA as M, we have</p><p>min{&#181;,&#964; } , assuming that the gradients are also i -cocoercive <ref type="bibr">[6]</ref>. Particularly, when using SVRE, the optimal &#964; is &#181; if &#175; /&#181; &#8805; n and &#175; /n otherwise. Therefore, the total complexity is</p><p>Remark 3. In either case, our result improves over the complexity</p><p>when using the batch extra-gradient method as M. To the best of our knowledge, this is the best complexity established so far for this class of SC-C minimax optimization problems. Results are summarized in Table <ref type="table">2</ref>.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4">Nonconvex-Concave Minimax Optimization</head><p>We now turn to nonconvex-concave minimax problems (1), and formally make Assumption 3. Denote g(x) = max y&#8712;Y f (x, y) as the primal function, which is -weakly-convex <ref type="bibr">[44]</ref>. The goal is to find an -stationary point of g(x). For any x, consider the Moreau envelop of g: &#968; 1/&#964;x (x) := min x&#8712;X g &#964;x (x; x) := g(x) + &#964;x 2 x -x 2 . The norm of the gradient &#8711;&#968; 1/&#964;x (x) is commonly used to measure the quality of a solution x <ref type="bibr">[10]</ref>. We call x -stationary point of g if &#8711;&#968; 1/&#964;x (x) &#8804; . Assumption 3. f (x, &#8226;) is concave for any x in X . X and Y are convex and closed sets, and Y is bounded with diameter D Y = max y,y &#8712;Y y -y .</p><p>Our modified Catalyst framework is described in 2, which further applies the proximal point algorithm to the primal function g(x), by adding a quadratic term in x, in the same spirit as <ref type="bibr">[40,</ref><ref type="bibr">44,</ref><ref type="bibr">24]</ref>. The main difference lies in that we use Algorithm 1 to solve subproblems in form of min x&#8712;X g &#964;x (x; x t ). Now we use &#964; y to denote the parameter in Algorithm 1 in order to distinguish from &#964; x . Algorithm 2 can be considered as a two-time-scale inexact proximal point algorithm, which repeatedly solves the subproblem min x&#8712;X max y&#8712;Y f (x, y)</p><p>We call it two-time-scale, not only because &#964; x and &#964; y differ, but also because the prox center of y comes from the extrapolation step of acceleration and is updated more frequently than the prox center of x. The subproblem ( <ref type="formula">9</ref>) is (&#964; x -, &#964; y )-SC-SC if &#964; x &gt; , thus can be efficiently solved.</p><p>Algorithm 2 Catalyst for NC-C Minimax Optimization </p><p>and &#175; = (&#964;x-) 2 2&#964; 2</p><p>x</p><p>, then E &#8711;&#968; 1/&#964;x (x T ) &#8804; .</p><p>Theorem 4.1 implies that the outer-loop complexity is O( -2 ). In the following corollaries, we specify the choices of &#964; x , &#964; y , and M for solving subproblems and the total complexity. Corollary 4.2 shows that simply using Catalyst-EG/OGDA achieves the complexity &#213; 2 -3 . This matches with the current state-of-the-art complexity for nonconvex-concave minimization <ref type="bibr">[24,</ref><ref type="bibr">44,</ref><ref type="bibr">51,</ref><ref type="bibr">36]</ref>. Note that our algorithm is much simpler than the existing algorithms, e.g., Prox-DIAG <ref type="bibr">[44]</ref> requires a four-loop procedure, whereas MINIMAX-APPA <ref type="bibr">[24]</ref> requires a smoothing step. For problems with finite-sum structure, as shown in Corollary 4.3, using Catalyst-SVRG attains the overall complexity &#213; n 3 4 &#175; 2 -3 , improving over all existing results. For instance, PG-SVRG proposed in <ref type="bibr">[40]</ref> gives &#213; n -2 + -6 , which has a much worse dependence on and n.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5">Numerical Experiments</head><p>We consider the wireless communication problem in <ref type="bibr">[3]</ref>. Given n communications channels with signal power p &#8712; R n and noise power &#963; &#8712; R n , the capacity of channel i is proportional to log(1 +</p><p>, where &#946; i &gt; 0 and &#963; 0 i are known constants. We would like to maximize the channel capacity under the adversarially chosen noise <ref type="bibr">[14]</ref>. This can be formulated as an SC-C minimax problem:</p><p>We generate two datasets with (1) &#946; = 1 and &#963; 0 &#8712; R 1000 uniformly from [0, 100] 1000 , (2) &#946; = 1 and &#963; 0 &#8712; R 500 uniformly from [0, 10] 500 . In Figure <ref type="figure">1</ref>, we apply the same stepsizes to EG and subroutine in Catalyst-EG, and we compare their convergence results with stepsizes from small to large. In Figure <ref type="figure">2</ref>, we compare four algorithms: extragradient (EG), SVRG, Catalyst-EG, Catalyst-SVRG with besttuned stepsizes, and evaluate their errors based on (a) distance to the limit point: p t -p * + &#963; t -&#963; * ; (b) norm of gradient mapping: &#8711; p f (p t , &#963; t )) + &#963; t -P &#931; (&#963; t + &#946;&#8711; &#963; f (p t , &#963; t )) /&#946;. In Figure <ref type="figure">3</ref>, we compare EG, Catalyst-EG and DIAG with best-tuned stepsizes.</p><p>Although EG with average iterates has an optimal complexity of O(1/ ) for solving convex-concave minimax problems <ref type="bibr">[32]</ref>, its convergence behavior for SC-C minimax optimization remains unknown.  ) . Here we use the same stepsize for primal and dual variables in EG and its counterpart with Catalyst. In Catalyst, we use x t -P X (x t -&#946;&#8711; x f (x t , y t )) /&#946; + y t -P Y (y t + &#946;&#8711; y f (x t , y t )) /&#946; as stopping criterion for subproblem, which is discussed in Section 2. We control the subroutine accuracy (t) as max{c/t 8 , &#732; }, where c is a constant and &#732; is a prefixed threshold. In contrast, DIAG does not provide a easy-toverify stopping criterion for subroutine. We stop the subroutine of DIAG based on the criterion:</p><p>where k indexes the subroutine iterations. We note that there is no theoretical convergence analysis for SVRG under SC-C setting. To form a fair comprison with SVRG, we report last iterate error in Catalyst-SVRG rather than averaged iterates.</p><p>We observe that Catalyst-EG performs better than EG and DIAG. Under the same stepsize, Catalyst framework significantly speed up EG. SVRG, albeit without theoretical guarantee in the SC-C setting, converges much faster than batch algorithms. Catalyst-SVRG also greatly improves over SVRG and outperforms all other algorithms.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Broader Impact</head><p>Our work provides a family of simple and efficient algorithms for some classes of minimax optimization. We believe our theoretical results advance many applications in ML which requires minimax optimization. Of particular interests are deep learning and fair machine learning.</p><p>Deep learning is used in many safety-critical environments, including self-driving car, biometric authentication, and so on. There is growing evidence that shows deep neural networks are vulnerable to adversarial attacks. Since adversarial attacks and defenses are often considered as two-player games, progress in minimax optimization will definitely empower both. Furthermore, minimax optimization problems provide insights and understanding into the balance and equilibrium between attacks and defenses. As a consequence, making good use of those techniques will boost the robustness of deep learning models and strengthen the security of its applications.</p><p>Fairness in machine learning has attracted much attention, because it is directly relevant to policy design and social welfare. For example, courts use COMPAS for recidivism prediction. Researchers have shown that bias is introduced into many machine learning systems through skewed data, limited features, etc. One approach to mitigate this is adding constraints into the system, which naturally gives rise to minimax problems.</p></div><note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="1" xml:id="foot_0"><p>SVRE requires assuming each component has i-cocoercive gradient, which is a stronger assumption than assuming i-Lipschitz gradient.</p></note>
		</body>
		</text>
</TEI>
