Learning A Minimax Optimizer: A Pilot Study
Authors: Jiayi Shen
Xiaohan Chen
Howard Heaton
Tianlong Chen
Jialin Liu
Wotao Yin
Zhangyang Wang
Venue: ICLR 2021 Poster (2021)
Keywords: Learning to Optimize
Minimax Optimization

Abstract: Solving continuous minimax optimization is of extensive practical interest, yet notoriously unstable and difficult. This paper introduces the learning to optimize(L2O) methodology to the minimax problems for the first time and addresses its accompanying unique challenges. We first present Twin-L2O, the first dedicated minimax L2O method consisting of two LSTMs for updating min and max variables separately. The decoupled design is found to facilitate learning, particularly when the min and max variables are highly asymmetric. Empirical experiments on a variety of minimax problems corroborate the effectiveness of Twin-L2O. We then discuss a crucial concern of Twin-L2O, i.e., its inevitably limited generalizability to unseen optimizees. To address this issue, we present two complementary strategies. Our first solution, Enhanced Twin-L2O, is empirically applicable for general minimax problems, by improving L2O training via leveraging curriculum learning. Our second alternative, called Safeguarded Twin-L2O, is a preliminary theoretical exploration stating that under some strong assumptions, it is possible to theoretically establish the convergence of Twin-L2O. We benchmark our algorithms on several testbed problems and compare against state-of-the-art minimax solvers. The code is available at:  https://github.com/VITA-Group/L2O-Minimax.

Published as a conference paper at ICLR 2021
LEARNING A MINIMAX OPTIMIZER: A PILOT STUDY
Jiay Shen',, Xiaohan Chen?", Howard Heaton", Tianlong Chen', Jialin Liu², Wotao Yin Zhangyang Wang 'Texas A&M University, University of Texas at Austin, UUniversity of California, Los Angeles, *Alibaba US, Damo Academy
as 71ttamm edu, (xiachan, chen, tianlong chen, at atsaswgg Butexas edd,, (heaton, wetaoyin n @math ucla edu, jialin. 1 liuaal bbbba- larba-ine inc. com
ABSTRACT
Solving continuous minimax optimization is of extensive practical interest, yet notoriously unstable and difficult. This paper introduces the learning to optimize (I.20) methodology the minimax problems for the first time and addresses its accompanying unique challenges. We first present Twin-L2O, the first dedicated minimax L20 framework consisting of two LSTMs for updating min and max vari- ables separately. The decoupled design is found to facilitate learning, particularly when the min and max variables are highly asymmetric. Empirical experiments on variety of minimax problems corroborate the effectiveness of Twin-L20. We then discuss a crucial concern of Twin-L20, i.e., its inevitably limited generalizability to unseen optimizees. To address this issue, present two complementary strategies. Our first solution, Enhanced Twin-L20, empirically applicable for general mini- max problems, by improving L2O training via leveraging curriculum learning. Our second alternative, called Safeguarded Twin-1120, a preliminary theoretical ex- ploration stating that under some strong assumptions, it is possible to theoretically establish the convergence of Twin-L2O. We benchmark our algorithms on several testbed problems and compare against state-of-the-art minimax solvers. The code is available at: https:://qttie wot. wtt.v/tt htt.://www.....tt.a.aaoooooooo/a
INTRODUCTION
Many popular applications can be formulated into solving continuous minimax optimization, such as generative adversarial networks (GAN) (Goodfellow al., 20014), distributionally robust learning (Globerson & Roweis| (206)), domain adaptation (Ganin & Lempitsky 20144, distributed computing
(Shammal [008] Mateos al,, 2010), privacy protection (Wu al. 2018 2020), among many more.
This paper studies such problems: we consider a cost function f:: 18mh R - IR and the min-max
game min, max,, (x, 3). We aim to find the saddle point (a" (u",9") of f:
f(x" .y) S s(" .V") S ((xV"", V(r,)) E Xx
where X' C In and y R If X ITM and y R", (a*, ,y") called a global saddle point; X' x )' is a neighborhood near (z" ), (x", v²)) is local saddle point.
)
The main challenge to solve problem (I) is the unstable dynamics of iterative algorithms. Simplest algorithms such as gradient descent ascent (GDA) can cycle around the saddle point or even diverge (Benam Hirsch 1999: Mertikopoulos et 2018b; [in et al. 2019). Plenty of works have been developed recently to address this issue (Daskalakis et al. 2018
Daskalakis & Panageas [0188] Liang Mokhtari et a 2019). However, the convergence is still sensitive to the parameters in these algorithms. Even if the cost function is only changed by scaling, those parameters have to be re-tuned to ensure convergence.
& Stokes, 2019 Mertikopoulos et al. 2018aj Gidel et al. 2018
A recent trend of learning to optimize (L20) parameterizes training algorithms to be learnable from data, such that the meta-learned optimizers can be adapted to a special class of functions and outperform general-purpont large number of yet similar optimization problems repeatedly and quickly. Specifically, for existing L20 methods that operate in the space of continuous optimization, almost all of them solve some
optimizers. That is particularly meaningful, when has to solve
"Equal Contribution.

---

Published as a conference paper at ICLR 2021
minimization problem (Andrychowicz al., 2016 Chen et al. 2017 Li & Malik 2016), leveraging an LSTM or a reinforcement learner to model their optimizer Different from classic optimization results that often provide worst-case convergence, most L20 methods have little or no convergence guarantees, especially on problem or data instances distinct from what is seen in training, leaving their generalizability in practice questionable (Heaton et al.) 2020). Motivated by I.20's success in learning efficient minimization solvers from data, this paper seeks to answer: whether we could accomplish strong minimax L20 solvers as well; and if yes, how generalizable they could be?
As it might look straightforward at first glance, such extension is highly nontrivial due to facing several unique challenges. Firstly, while continuous minimization has a magnitude of mature and empirically stable solvers, for general minimax optimization, even sfate-of-the-an art analytical algorithms can exhibit instability or even divergence. To the best of our knowledge, most state-of-the- art convergence analysis of minimax optimization is built on the convex-concave assumption (Gidel al., 2018: Mokhtari et al.] 2019 Ryu et al. 2019), and some recent works relax the assumption to nonconvex-concave (Lin et al. 2019 2020 Convergence for general minimax problems is still open. That makes a prominent concern on whether a stable minimax L20 is feasible. Secondly, given the two groups of min and max variables simultaneously, it is unclear to what extent their optimization strategies can be modeled and interact within one unified framework a new question that would never be met in minimization. Thirdly, the noisy and sometimes cyclic dynamics of minimax optimization will provide noisier guidance (e.g., reward) to I.20; not to say that, it is not immediately clear how to define the reward: for minimization, the reward is typically defined as the negative cumulative objective values along the history (Li & Malik (016)) However, for minimax optimization the objective cannot simply be decreased or increased monotonically.
Contribution:
This paper is a pilot study into minimax L20. We start by establishing the first dedicated minimax L20 framework, called Twin-L20. It is composed of two LSTMs sharing one objective-basse based reward, separately responsible for updating min and max variables. By ablations of the design options, we find this decoupled design facilitate meta-learning most, particularly when the min and max updates are highly non-symmetric. We demonstrate the superior convergence of Twin-L20 on several testbed problems, compared against a number of analytical solvers.
On top of that, we further investigate how to enhance the generalizability of the learned mini- max solver] and discuss two complementary alternatives with experimental validations. The first alternative is an empirical toolkit that is applicable for general minimax L20. We introduce curricu- lum learning to training L20 models for the first time, by recognizing that not all problem instances the same difficult to learn solve. After plugging in that idea, show that Twin-I.20 can be trained to stably solve a magnitude more problem instances (in terms of parameter varying range). The second alternative explores theoretical mechanism called safeguarding, particularly for the important special case of convex-concave problems. When solving a testing instance, safeguarding identifies when an L20 failure would occur and provides an analytical fall-back option (Diakonikolas) 2020). That guarantees convergence for convex-concave problems and, in practice, converges faster even when the problem parameters are drawn from different distribution from training.
RELATED WORK
2.1 MINIMAX OPTIMIZATION
Following (Neumann 1928), the problem 1 has been studied for decades due to its wide applicability. Simultancous gradient descent (SimGD) or gradient descent ascent (GDA) (Nedić & Ozdaglar lar 2009
Du & Hu 2019; 101900n Din et al.] Lin 2019) is one of the simplest minimax algorithms, conducting gradient descent over variable and gradient ascent over variable y. However, the dynamics of SimGD or GDA can converge to limit cycles or even diverge (Benaim & Hirsch 1999] Mertikopollss
ct al. 2018b: Lin et al. 2019). To address this issue, Optimistic gradient descent ascent (OGDA)
simply modifies the dynamics of GDA and shows more stable performance (Daskalakis et al.
2018
Daskalakis & Panageas
2018 Liang & Stokes 2019; Mertikopoulos et al. 2018a Gidel et al. 2018
Mokhtari et al. 2019). OGDA attracts more attention because of its empirical success in training
GANs. (Ryu et al. 2019) theoretically studies OGDA by analyzing its continuous time dynamic and
We differentiate the usages of two terms: parameters and variables, throughout the paper. For example. min, max, a - hyf, we call o, b parameters and y variables. For simplicity, this paper only discusses the 1.20 generalizability when the testing instances' parameter distrihution differs from the training.
2

---

Published as a conference paper at ICLR 2021
proposes Anchored simultaneous gradient descent that shows good performance. Follow-the-Ride [Wang et al. 2019) also addresses the limit cycling problem by introducing second information into the dynamic of GDA. Lately, K-Beam (Hamm & Noh 2018) stabilizes the convergence of GDA by duplicating variable y. yielding strong performance. At each iteration, it performs gradient ascent independently on K copies of and greedily chooses the copy that leads large function value f. then it updates x based on the selected copies.
2.2 LEARNING TO OPTIMIZE
As special instance of meta- meta-learning, L20 has been studied in multiple contexts, with continuous optimization being one of its main playgrounds so far. The first L,20 framework is introduced in (Andrychowicz et al.] 2016), where both the optimizee's gradients and loss function values are formulated as the input features for an RNN optimizer. Due the enormous number of parameters, coordinate-wise design of RNN optimizer is adopted, where all optimization coordinates share the same updating strategy. (Li & Malik 2016) uses the gradient history and objective values as observations and step vectors actions in their reinforcement learning framework. (Chen et al. (017)) leverages RNN to train a meta-optimizes to optimize black-box functions. Two effective training tricks, random scaling and objective convexifying, are presented in (Lv et al. 2017). Wichrowska et al. (011 presents an optimizer of multi-level hierarchical RNN architecture augmented with additional architectural features. [i et al. (2020) introduces Jacobian regularization L20 and enhances the domain adaptation performance of optimizees. Chen et al. (2020a) proposes several improved training techniques to stabilize L20 training and ameliorate performance. Youu al. (2020); Chen et al. 2020b c) extend the application scope of L20 into various practical problems such as graph neural network training, domain generalization, and noisy label training.
The above works address continuous minimization problems using single optimizer models. One exception, (Cao al. 2019), extends L.20 to solving Bayesian swarm optimization. The author presents novel architecture where multiple LSTMs jointly learn iterative update formulas for the swarm of particles, coordinated by attention mechanisms. We also notice that two recent efforts (Jiang al. 2018 Xiong & Hsich 2020) introduce L20 to adversarial training, a renowned application of minimax optimization. However, both of them merely utilize L20 to solve the inner minimization of their minimax problems (i.e., generating attacks). while the outer maximization is still solved analytically. Neither of the two directly solves the full minimax optimization.
METHOD
3.1
MAIN FRAMEWORK: TWIN LEARNABLE OPTIMIZERS (TWIN-L2O)
The main L20 framework we proposed is named T20, where we use two learnable optimizers to alternate between min and max updates. Our design adopts the basic idea of (Andrychowicz et al., 2016) to use Long Short-Term Memory (LSTTM) model learnable optimizers, for solving target problems known optimizees. At each step, LSTM outputs the update of the optimizee variables. The LSTM inputs are typically the current zero-order or first-order information of the optimizee (Andrychowicz et al. 2016 Lee & Choi 2018), plus the historic optimization trajectory information.
In Twin-L20, two LSTMs separately update x and y and record historical trajectory information of their own variables respectively. Formally, we consider the minimax problem min, max,, fæz y). We use two LSTM optimizers, LSTM-Min and LSTM-Max, to updates the min variable x and the max variable y respectively. LSTM-Min is parameterized by dimin and LSTM-Max is parameterized At each iteration f, Twin-L20 updates x and y in turns and yields the following rule:
by m
1 =t Arc, where (Ar,, m LSTM-Min [V (Z). V (It, (II, min
(2)
2i-1 By + Aye, where (Aye, ( = LST yf (#441 Bc), V (# 3:]], max max
where hmiin and hquax are the historical trajectory information of LSTM-Min and LSTM-Max at time
step& t. This formulation is inspired by the SimGD/GDA algorithms (Neii & Ozdaglar 2009
Du & Hul [219]] Jin et al.] 2019 Lin et al. 2019) that conduct simultaneous/alermaaii gradient descent over 2: and ascent over y. Figure A4 (Appendix A1] conceptually illustrates the framework.
The next question is to design the L20 reward. To train the LSTM optimizers, the loss function is often to penalize some type of cost, accumulated along the optimization trajectory for horizon of T
3

---

Published as a conference paper at ICLR 2021
steps (also known the unrolling length for LSTM (Sherstinsky 2018
E,
Σ we R(S Ne, ve)
We is chosen to be all following the basic setting in (Andrychowicz et al. 2016), that might be tuned for better performance in future work.
As a key design option, R(J) represents the reward to guide the L20 training. In existing L.0 methods for continuous minimization (Andrychowiez et al. 2016, Lv al. 2017). R(J) is usually simply set to R(f,=z)) xt)) J (x²) to encourage fast decrease of objective values over time. To extend this existing reward to the minimax scenario, we cannot directly penalize the overall objective function value either way, since the min and max objectives are entangled. Also, different from pure minimization problems, the Twin-L20 updates (2) consist of two alternating steps governed by two different LSTM optimizers: each accounts for its own subproblem goal (min max updates), but the two also have to collaborate to explore/exploit the minimax landscape. We specifically design the following reward that implicitly addresses the above issue by setting a new reward function:
L(owin o maxx = E,
Σ (f(( far, well + Ve-) - (11-11 (4)
Analysis of the reward design In Equ. the first and second terms always characterize two consecutive min and max updates. In more details, the value of f (I.. - (Iz, V/- V/-1) solely reflects how effectively the t-step max update increases the objective f while f (I,, Be-1) f (zz-1 9t-1) reflects the effectiveness of 1-step min update in decreasing the objective f. Our goal is then to maximize the weighted accumulated sum for f (It, Mt) - (st, Vt-1), while minimizing the weighted accumulated sum for f (Iz, yt) ff (It, 3t-1), = 1, 2..,, T. Combining the two sub-goals together (with a sign change turn max into min) yields our reward. One may also alternatively interpret Eqn. 4 as penalizing the loss change from f (Ize Me) along both x and y updating directions, which would encourage yielding stationary points.
For the reward design, we provide a more detailed discussion in Appendix A6 Specifically, we provide a comparison between the objective-basel reward Eqn. + and another possible gradient- based reward. The latter was found to be ineffective in solving the problems presented in Section 4
Rationale of the framework selection Another important design question is to what extent learn- ing the min and max updates should be (dis)entangled: on the one hand, the two steps obviously interact with each other they jointly explore the minimax landscape; on the other hand, min and max steps commonly have asymmetric difficulty levels, that have been leveraged by previous algorithms. For example, (Hamm & Noh, 2018) demonstrates the failure of alternating gradient descent in minimax optimization due to the multiple solution discontinuity of the inner maximization, and addresses that by simultaneously tracking K candidate solutions for the step, while the outer minimization remains to take one descent step. Besides the joint reward (4), the default Twin-L20 design leverages two independent LSTMs in Eqn. (2). each dedicatedly handling min or max updates. In comparison, we also consider two other more "entangled" ways: (a) fully entangling the two optimizers, i.e. using one LSTM simultaneously generate min and max outputs; (b) weakly entangling the two optimizers, by using two LSTMSs sharing weights, yet allowing either to maintain its own temporal hidden states. Our ablation experiments (see Section 4.1 find that the default decoupled design in Eqn. 2 seems to facilitate the L20 learning most.
3.2 IMPROVING GENERALIZABBI.TT OF TWIN-L.20
Despite the empirical success of I.20, it unfortunately impossible to ensure that any I.20 algorithm always converges. Assuming the objective function type keep unchanged, the testing instances' parameter distribution may differ from the one of training, and L20 can catastrophically fail. For the Twin-L20, we diseuss two remedies partially fix this issue and boost its generalizability.
We first propose curriculum L20 training scheme as a practical L20 training technique such that Twin-L20 can be trained to work on much wider coverage of problem parameters than its vanilla versions. That would empirically help the generalizability due to broader coverage by training instance, but would still inevitably fail when meeting unseen testing instances. We then present
4

---

Published as a conference paper at ICLR 2021
preliminary exploration of the safeguard mechanism on minimax under special case, i... solving convex-concave problems. We demonstrate that with such strong assumptions, it is possible to theoretically establish the "perfect" convergence of Twin-L20 any unseen optimizee.
Curriculum L20 Training When it comes to general minimax problems, is unlikely to exist an ideal theory to fully ensure Twin-L20 convergence all instances. Therefore, seek empirical L20 success of as many instances as possible. Specifically: can we train Twin-L20 better, so that it can work on instances at a broader parameter range?
We find a curriculum learning (CL) strategy (Bengio et al. 2009) particularly useful. CL was first adopted to train neural networks by first focusing the training on an "easy" training subset (often adaptively selected), that is then gradually grown to the full set. It is known to be effective to stabilize training. especially when the training set highly varied or noisy (Jiang et al. (017). Since minimax optimization is notoriously unstable no matter via analytical or learned optimizers, we conjecture that the noisy minimax dynamics might challenge Twin-L20 by providing unreliable guidance and impede its training. Considering that our Twin-L22 is modeled using LSTMs, it is natural to think of whether CL can bring additional gains if applied to meta-training. Previously it was also found effective in L20 for minimization problems (Chen al. 2020a).
Specifically, in one epoch, we will rank all op- timizee instances by their cumulative losses (3) from low to high, and only select the top C' in- stances to count into the total reward. In that way, only the instances that exhibit "good train- ing behaviors" (smaller gradients & more likely to get close to stationary points) will be initially used for updating the Twin-L2O. That prevents the learned optimizer being misled by random
Method Safeguarded Twin-L20 for Convex- Concave Saddle Point Problems
1: Initialize u. E IR C' E oo), a E (0,,
(Me] {I/(E + 1)), k t 2, weights {
2: function SADDLEHALPERNGS
3:
u² (u' Jaao(u'))-
4:
while 1 -Jnos(u))l > do
5:
k + LSTM(u"; ot) Apply L20 operator
failures and outliers, which are commonly found in the early epochs of Twin-L20 training. We by default set the percentage C' to start from 20%. then growing linearly every epoch until reaching 100% in the later training stage.
6:
7:
if Ea+1 (u S
k++
8:
A Verify safeguard condition
9:
k+1 t xt1
Up our best knowledge, this is the first effort to incorporate CL with L20 training. We can this Twin-L20 trained with CL as Enhanced 12:
Use L20 update
11:
else
u k+1 f- Aou + +(1 Jan (w²)
Twin-L22:: note that it is the same model struc-
13:
< Use fallbuck update
ture, just trained in different and better way.
14:
k k k +1
More details can be found in Appendix [44.
15:
return t
Safeguard Twin-I.20: Preliminary Theo- retical Exploration Most L220 methods have little or no convergence guarantees. Very recently, a safeguarding mechanism has been introduced to L20 for convex minimization problems with gradient and/or proximal oracles (Heaton et al. 2022)) Conceptually, a safeguard is anything that identifies when a "bad" L20 update would occur and what "fallback" update to apply in place that bad L20 update. In this section, we establish a safeguarding theory and algorithm. specifically for learned convex-concad safeguard takes the form of an energy inequality (c.f. Line 6 in Method
16:
end function
saddle point algorithms. Here the
In this section, we write u (x. 4) E R x T and let > 0. We use the resolvent, defined by Ja y) (Id adf)
(5)
where we note - f). For simple (e.g., quadratic functions), closed formula exists for Jasy. Otherwise, one may use an iterative method to approximate this quantity. In addition, define the residual operator
-
F(u) = (u - (u))
(6)
2
and, for each l E N, the energy E : IR" m x Rm IR by
d
Ey(u) [(u)l12
(F(u), u² -2)
1- d
5

---

Published as a conference paper at ICLR 2021
where {Ax} is a sequence of step sizes. The full method is outlined in the Method update is denoted by LSTM(u", x²) and the fallback method is a Halpem iteration Halpem 1967). Our main result for minimax safeguarding theory is formally stated below:
1 where the L20
Theorem 3.1. If the sequence {u²} is generated by Algorithm
then
1 d1 2 k +
d
40
|/u² - Jaos(a")) $
+V
for all k 2 2,
(8)
k
where d1 := min - w²1l: : { is the distance from the initial iterate u' to the set of
saddle points and C 2 0 is an arbitrary constant. In particular, this implies each limit point of {ul) is a saddle point.
Our proof draws and integrates two sources of ideas: (1) the safeguarded L,20 technique that has recently just been introduced to convex minimization (Heaton et al. 2020); and (2) Halpern iteration (Diakonikolas) 2020) that is adopted for analytical minimax optimization with favorable theoretical properties. The full proof is provided in Appendix A3 Note that this work is not intended as a theory innovation on (classical) minimax optimization. Instead, our aim is to extend the emerging idea of safeguarded L20 from convex minimization to convex-concal minimax problems of interest, and shows this idea be helpful for minimax 1.20 too: see experiments in Section 4
4 EXPERIMENTS
4.1 ABLATION STUDY ON THE DESIGN OF TWIN-L20
We first investigate the design choices for Twin-L20 that we discussed in Section 3.1
We mainly
investigate two aspects: (i) whether to share the weights in the two LSTM solvers or not: (ti) whether to share the hidden states between the two LSTM solvers or not. That leads us four options, Saaiee--S---wwooo--oe
denoted as (with self-explanatory names): Swo-LSTMMSShae ChireeHHddeen, and Two-LSSTM-Tww Te--Twoddddd We use the seasaw problem, formulated as below, as the testbed for our ablation study (note that the ranges of a, b are picked only to make L20 easy to converge, while more will be investigated in Section 4.3
Saaae--STTM-Shae---l
Seesaw: min max by sin((an)) ~ (00.,, 11.b ~~ U
(Seesaw)
The Scesaw problem is conccve,, and is considered challenging (Hamm & Nohl 2018) due to its non-differentiabiiiyy arising from that the solutions of the state equation or the adjoint state equation not unique (Danskin 1966). The L20 training routine follows (Andrychowicz et al. 2016): we use 128 optimizee instances for training; each of them has its parameters i.i.d. sampled, and variables ær, y randomly initialized by i.i.d. sampling from U[-0.5, 0.5J. validation set of 20 optimizees is used with parameters and variables sampled in the same way; and similarly we generate a hold-out testing set of another 100 instances. For each epoch, an L20 optimizer will update the optimizee parameters for 1000 iterations, with its unrolling length T = 10. When the next epoch starts, all x, y as well as LSTM hidden states are reset. We train the L20 solvers for 200 epochs, using Adam with a constant learning rate 10-1 We pick the model checkpoint at the epoch when its validation performance reaches the peak. Figure compares the convergence results of the four options, evaluated on the same testing set. We measure the & distances between the solved variables and their corresponding ground-truth solutions (or the closet one, if multiple exist). It is obvious that only the Two-LSTM- TWOMM-TTooFP Two-Hidden can successfully converge to the correct solution (x* y²" (0. 0), which is also the equilibrium. Our major observation from the above experiments is that for minimax L20 optimization, especially for asymmetric problems such Seesaw, would be better choice to use decoupled two LSTM solvers and let them take care of their own trajectory information. We will hence stick to this option and use it as our default Twin-L220.
All experiments in this and following sections are conducted using the GeForce GTX 1080 Ti GPUs.
4.2 COMPARISON WITH STATE-OF-THE-ART ANALYTICAL OPTIMIZERS
In this section, we apply Twin-I-20 to more test problems besides Seesaw:

---

Published as a conference paper at ICLR 2021
10a
Distarce to Ground Trubh
10
Divisenc Ground Traih
(wo-Hidden One One-LSMM- Dww.-S--DD--elooe
TeoL51MN IwaLSIM.Gne-titte
20-4
10-1
Ore- STM--vo-llizzen
LSTM
10-a
100
Iteraioo
Iberation
(a) Convergence of
(h) Convergence of
Figure I: Convergence curves on the ablation study of Twin-L20 design options.
Rotated Saddle
ming maxy ax² by² + 2ry, ~ b U/0.,, 1]
Matrix Game; ming maxy x" Ay, R5x5 A Bernuuli(00.)) 1[]
On all three problems, compare Twin-L.20 with several state-of-the-art algorithms: Gradient Descent Ascent (GDA) (Lin et al. 2019). Optimistic Mirror Descent (OMD) (Daskalakis et al.] 2018) and GD with anchoring (GD-Anchoring) (Ryu et al. 2019). On Rotated Saddle and Seesaw we will compare with K-beam (Hamm & Noh 2018) in addition. For matrix game, we also compare it with the standard Halpern Iteration (Diakonikolas) 2020) that is designed for convex convex-concave concave minimax problems. For these analytical methods, all parameters are tuned with careful grid search. We train, validate and test Twin-1.20 models following the protocol described Section 4.1
Figure 2 plots the convergence curves of all methods, averaged across all testing problems (and each with trials of random x, y initialization). Several observations are drawn below:
L20 does not show superiority over well-tuned analytical algorithms the simplest Rotated
Saddle problem (and similarly Saddle). The problem is very gradient-frient and therefore OMD already achieves the best convergence speed well as solution quality.
On Matrix Game, Twin-L20 starts to show competitive edges over analytical solvers with faster convergence speed and higher-precision solutions.
On the Seesaw problem, Twin-L20 largely outperforms all carefully-tuned analytical algo- rithms, achieving one-magnitude higher-precision solutions with comparable convergence speed. That shows and can contribute most significantly to those hard problems. That makes minimax L20 a highly meaningful complement existing analytical minimax solvers. More analysis comparing the actual computational costs (MAC numbers) can be found in Appendix
take-home message: L20 work for minimax optimization,
GBA
GDA
320
GD-Anchoring
Dbsence
DMD
CD-Anchoning
2..0
0.25
GD Anchordg
215
K-beam
1.0
Helpern
K-beam
210
Twin-L20
Twin-120
Twin-120
305-
0.5
sw0
Iteration
Rotated Saddle
(b) Matrix Game
Scesaw
Figure 2: Convergence comparison of variable r between Twin-L20 and state-of- analytical minimax optimizers (GDA, OMD, Anchhrrrn,, and K K-beam), for three test problems. For results of variable, please see the Appendix A2
We also test on the classical Saddle problem, but its hehaviors and conclusions are almost identical to the Rotated Saddle. We hence report Rotated Saddle due the space limit.
7

---

Published as a conference paper at ICLR 2021
4.3 ENHANCED TWIN-L20: CURRICULUM LEARNING EVALUATION
We again use the Seesaw problem as an example in this section. Its two parameters a and b, i.e. the problem period and the scale, are sampled independently from two uniform distributions U U[L Lza]. U[L L- In Section 4.1 both are chosen as U/0..9 1] for the ease of L20 convergence. We now stretch both parameter ranges and test whether an L20 model can still solve the resultant broader range of problems. All other training protocols follow Section identically.
Sections 4.1 and 4.2 evaluate the average solution distances over the testing set (100 instances), which worked fine in the small [a, b] range then. However, when we extend the [a, b] range, we find that the L20 behaviors can differ vastly across testing instances, i.e., some converging quickly while others suffering from heavy fluctuations or even divergence, which is an artifact of inefficient L20 training that leaves it unable to cover the full large problem range. That motivates us to carefully re-design evaluation metrics here, to reflect both the solution quality and its variation/stability..
For p-th testing instance, we record its solution distance l2 Df, at epoch t = 2,,2.... Given two thresholds Éace and Estd (chosen by multi-fold validation; we use default Ea = 2 x 10-2 and Estd 10 10-4), we define two forms of success rate (SR):
SR Σp-1 (e(e)))<
SR2 ΣE [(Sta(D")
where d(DP)= = Eiet, D.
To Std( Std (D)) 0.L. 100 is the number of testing instances; = 1000 is the total iteration number that each instance (optimizee) is trained by L20. Intuitively, SR, emphasizes the average solution precision from the last 20 iterations; and SR₂ measures how large solution variation is seen in the last 20 iterations.
Table compares Twin-I.20 and Enhanced Twin-1.20 multiple combinations to stretch the ranges of a and l, starting to the original [0.9. 1] x [0.9, 1]. up to as large as [0, 5) x [0, 2] : the parameter coverage increase by 1,000 times. Adding CL. evidently helps Twin-I.20 stay effective to train over a broader instance range, under both SR metrics. Vanilla Twin-L20 performs perfectly at
[0.9, 1] x [0.9, 1]. yet begins to drop [0. 1] [0.9, 1] (mainly showing higher instability, as indicated by lower SR2), and hardly succeeds beyond [0, 3.5) x [0.9, 1]. In contrast, Enhanced Twin-L20
obtains nontrivial results even at [0, 5] [0, 1] (tens of times wider than the vanilla one).
Table 1: Success rate (SR) of different ranges of a.b on the Seesaw problem
Ranges
a
[0.9, 1.0)
[0.0, 1.0)
3050,3.5]
5.0
0.99, 1.0)
[0.0, 5.0)
[0.0, 5.0)
Settings
b [0.9, 1.0]
[0.9, 1.0]
[0.9, 1]
00.,, 1.0]
0.00, 1.0
[0.0, 1.0
[0.0, 2.0)
SR, (Twin-L20)
100.0%
96.6%
0.0%
0.0%
97.8%
11.6%
22.8%
SR, (Twin-L20)
100.0%
89.6%
17.4%
16.0%
96.2%
31.4%
71.6%
SR, (Hnhanced Twin-1-200
100.0%
96.6%
64,8%
82.8%
98.0%%
85.0%
62.6%
SR, (Enhanced Twin-120)
100.0%
96.0%
87.8%
91.2%
97.4%
86.2%
53.8%
4.4 SAFEGUARDED TwIN-L20 EXPERIMENTS
Here we use the matrix game as the example to evaluate the above established safeguard mechanism for convex-concat minimax optimization. We directly take well-trained Twin-L20 model for matrix game in Section 4.2 where the matrix A E 5 and A ~ Bernoull((O.5) - [[[11,1 1]. and the coordinates of initial optimization variables x and y are independently sampled from 1]. During testing. in addition to testing the Twin-L22 model on the testing data from this seen distribution, we also evaluate it on unseen data, whose A is now sampled from intentionally very distinct distribution: Ai, ~ Bernoulli(1.0) U|-8, 8). x and y are initialized in the same manner.
We compare Safeguarded Twin-120 (denoted Safe-Twin-L20) with standard Halper iter- ation (Diakonikolas) 2020) as the fallback update, when the 1,20 update is disapproved in Method [ We also compare with OMD and GD-Anchoring on both seen and unseen testing data (GDA fails to converge in both cases, even we tune its hyperparameters to our best ef- forts). The results are shown in Figure 3 When tested on the aggressively varied unseen data, the vanilla Twin-L20 model fails and diverges, but Safe-Twer Twin-L20 remains to converge suc- cessfully: even faster than Halpern iteration and OMD, and much better than GD-Anchoring.
8

---

Published as a conference paper at ICLR 2021
CONCLUSION
CMD C0-Anchoring
This paper studies L20 for minimax optimization for the first time. We present the Twin-L20 model, and further improve its generalizability by introduc- ing theoretically grounded safeguarding frame- work (for convex-concave problems), well as an empirical curriculum training strategy (for gen- eral problems). Extensive simulations endorse the promise of our algorithms. This pilot study sug- gests and paves the way for extending L20 beyond continuous minimization problems.
Halpor
Distance
Twin-L20
10
Safe Twin L20
Iteration 10'
(a) Seen Data
10P
CMD
6D-Anchoring
The entire L20 field faces challenges to scale up to larger-scale optimization (Andrychow icz et al. 2016), and our study has not yet made an exception. Despite very promising gains from chal- lenging cases such as the Seasaw and Matrix Game problems, the current work only proves the first concept of minimax I.20, on relatively basic and low-dimensional test problems. Our immediate next step is to scale up Twin-L20, and to explore its potential in solving the minimax application problems of practical interest, such as adversarial training (Jiang et al.) 2018 Xiong & Hsieh] 2020) and GANs
Limitation:
Distance
Twin L20
10"
Safe-Twin L20
10a2
107
Iteration 10a
107
(b) Unseen Data
Figure 3: Evaluation Safe-Twin-L20.
(Gulrajani et al., 2017). potential idea might leverage the memory-effiiient hieracciccl RNN
structure in (Wichrowska et al. 2017).
REFERENCES
Marein Andrychowiez, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. Advances in neural information processing systems, 2016.
Heinz H Bauschke, Patrick L Combettes, et al. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer. 2011.
Michel Benam and Morris W Hirsch. Mixed equilibria and dynamical systems arising from fictitious play in perturbed games. Games and Economic Behavior, 29(1 (11-)3)36677, 1999.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference machine learning, 2009.
Yue Cao, Tianlong Chen, Zhangyang Wang, and Yang Shen. Learning optimize in swarms. In Advances in Neural Information Processing Systems, pp. 15018-15028, 2019.
Tianlong Chen, Weiyi Zhang, Jingyang Zhou, Shiyu Chang, Sijia Liu, Lisa Amini, and Zhangyang Wang. Training stronger baselines for learning to optimize. arXiv preprint arXiv:2010.09003 2020a.
Wuyang Chen, Zhiding Yu, Zhangyang Wang, and Animashree Anandkumar. Automated synthetic- to-real generalization. In International Conference on Machine Learning, pp. 1756-1756. PMLR, 2020b.
Xuxi Chen, Wuyang Chen, Tianlong Chen, Ye Yuan, Chen Gong, Kewei Chen, and Zhangyang Wang. Self-pu: Self boosted and calibrated positive-unlabeled training. In International Conference on Machine Learning, pp. 1510-1519. PMLR, 2020c.
Yutian Chen, Matthew W Hoffman, Sergio Gómez Colmenarejo, Misha Denil, Timothy P Lillicrap, Matt Botvinick. and Nando De Freitas. Learning learn without gradient descent by gradient descent. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 748-756. JMLR. org, 2017.

---

Published as a conference paper at ICLR 2021
John M Danskin. The theory of max-min, with applications. SIAM Journal Applied Mathematics, (4(4):641-66, 1966.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, 2018.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In International Conference Learning Representations (ICLR 2018), 2018.
Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. arXiv preprint arXiv:2002.008872, 2020.
Simon S Du and Wei Hu. Linear convergence of the primal-dual gradient method for convex-concave saddle point problems without strong convexity. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 196-205 2019.
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. arXiv preprint arXiv:1409. 7495, 2014.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A varia- tional inequality perspective on generative adversarial networks. arXiv preprint 180.:1880..05555 2018.
Amir Globerson and Sam Roweis. Nightmare at test time: robust learning by feature deletion. In Proceedings of the 23rd international conference on Machine learning, pp. 353-360, 2006.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances neural informa- fion processing systems. pp. 2672-2680, 2014.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. In Advances in neural information processing systems, pp. 5767-5777, 2017.
Benjamin Halpern. Fixed points of nonexpanding maps. Society, 73(6)9957-961, 1967.
Bulletin of the American Mathematical
Jihun Hamm and Yung-Kyun Noh. K-beam minimax: Efficient optimization for deep adversarial learning. arXiv preprint arXiv:1805. 11640, 2018.
Howard Heaton, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. Safeguarded learned convex optimization. arXiv preprint arXiv:2003.01880 2020.
Haoming Jiang, Zhehui Chen, Yuyang Shi, Bo Dai, and Tuo Zhao. Learning to defense by learning to attack. arXiv preprint arXiv: 1.01213, 2018
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Learning data-driven curriculum for very deep neural networks corrupted labels. arXiv preprint arXiv:1712.05055, 2017.
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. What is local optimality in nonconvex-noncoocaae minimax optimization? arXiv preprint 4rXiv:1902.006611 2019.
Yoonho Lee and Seungjin Choi. Gradient-based meta-learning with learned layerwise metric and 2018.
subspace. arXiv preprint
Chaojian Li, Tianlong Chen, Haoran You, Zhangyang Wang, and Yingyan Lin. Halo: Hardware-awan learning to optimize. In European Conference on Computer Vision, pp. 500-518. Springer, 2020,
Ke L.i and Jitendra Malik. Learning to optimize. arXiv preprint arXiv: a60iv 1606.0185.. 2016.
Tengyuan Liang and James Stokes. Interaction matters: A note non-asymptotic local convergence of generative adversarial networks. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 907-915, 2019.
10

---

Published as a conference paper at ICLR 2021
Tianyi Lin, Chi Jin, and Michael I Jordan. On gradient descent ascent for nonconvex-coneave minimax problems. arXiv preprint arXiv:1906.0033.. 2019.
Tianyi Lin, Chi Jin, Michael Jordan, et al. Near-optimal algorithms for minimax optimization. arXiv preprint arXiv:2002.00 2002:20002.22117, 2020.
Kaifeng Lv, Shunhua Jiang, and Jian Li. Learning gradient descent: Better generalization and longer horizons. In Proceedings of the 34th International Conference on Machine Learning- Dearning-Volume 70, pp. 2247-2255. JMLR. org, 2017.
Gonzalo Mateos, Juan Andrés Bazerque, and Georgios B Giannakis. Distributed sparse linear regression. IEEE Transactions Signal Processing, 58(10):5262-2277 2010.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprint arXiv:1807.0220 02629, 2018a.
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2703-2717. SIAM, 2018b.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. unified analysis of extra- grara-gradietttt and optimistic gradient methods for saddle point problems: Proximal point approach. arXiv preprint arXiv: 2019.
Angelia Nedić and Asuman Ozdaglar. Subgradient methods for saddle-point problems. Journal of optimization theory and applications, 142(1):205 228-228, 2009.
J Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1):295-320, 1928.
Arvind Raghunathan, Anoop Cherian, and Devesh Jha. Game theoretic optimization via gradient- based nikaido-isoda function. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Pro- ceedings of the 36th International Conference on Machine Learning, volume 97 of Proceed- ings of Machine Learning Research, pp. 5291-5300. PMLR, 09-15 Jun 2019. URL http:
Ernest K Ryu, Kun Yuan, and Wotao Yin. Ode analysis of stochastic gradient methods with optimism and anchoring for minimax problems and gans, arXiv: 10899, 2019.
Jeff Shamma. Cooperative control of distributed multi-agent systems. John Wiley & Sons, 2008
Alex Sherstinsky. Fundamentals of recurrent neural network (rnn) and long short-term memory (Istm)
network. arXiv preprint arXiv:1808.03:33 2018.
Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridge approach. arXiv preprint arXiv: 1900.0751, 2019.
Olga Wichrowska, Niru Maheswaranathan, Matthew W Hoffman, Sergio Gomez Colmenarejo, Misha Denil, Nando de Freitas, and Jascha Sohl-Dickstein. Learned optimizers that scale and generalize. In Proceedings of the 34th International Conference Machine Learning, 2017.
Zhenyu Wu, Zhangyang Wang, Zhaowen Wang, and Hailin Jin. Towards prenacyprreserving visual recognition via adversarial training: A pilot study. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 0064624,77 2018.
Zhenyu Wu, Haotao Wang, Zhaowen Wang. Hailin Jin, and Zhangyang Wang. Privacy-preserving deep action recognition: An adversarial learning framework and a new dataset. IEEE Transactions on Pottern Analysis and Machine Intelligence, 2020.
Yuanhao Xiong and Cho-Jui Hsieh. Improved adversarial training via learned optimizer, 2020.
Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. L2-gen: Layer-wise and learned efficient training of graph convolutional networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2127-2135, 2020.

---

Published as a conference paper at ICLR 2021
A1
TWIN-L2O FRAMEWORK
Stin-Structured Learning to Optimize (Twin-L20)
Ande
LSTM-Min
Ante
LSTM-Min
Ant
guan
gain
A
RC (sL 11
RIS (2).2))
R(S (2112:
21-1
2tt
F++1
Y--1
yt
yt++1
Ay--1
Rif (=
Ay:
RIf (#1-1.8))
Ayes Rlf (atess Bl-1))
M.s max
LSTM-Max df
LSTM-Max X
A
Attaz
Twin-LSTM Optimizer
Minimax Optimizee
+ Apply Updating Rule Pass Input Information Twin-LSTM
Pass Updated
Variable
Figure A4: Architecture of Twin-L20. We let LSTM-Min and LSTTM-Max parameterized by o and r update z and y respectively. As shown by curved dashed lines, Twin-LSTM keeps being updated about the latest variable values of x and y when computing input information and the reward. When constructing the computational graph and training the Twin-LSTM, the solid lines allow gradients to flow while the dashed lines do not pass any gradient (Andrychowicz et al.) 2016).
A2 COMPARISON WITH STATE-OF-THE-A -RRTTRT ANALYTICAL OPTIMIZERS
Figure AS shows the performance of y variable in Rotated Saddle, Matrix Game and Seesaw. The analyses of the results generally align with those in the paper.
3.2
0.4
GDA
OMD
1.5
OMD
3.15
beam
Anchoring
Distance
1.0
OMD
(D--Achoring
Distance
8.22
GDDAnchoring
3.10
Twin L20
Halpem
Twin-L20
3.55
2.0
30
htration
10' Iteration
Iteration
(a) Rotated Saddle
(b) Matrix Game
(c) Seesaw
Figure A5: Convergence comparison of variable between Twin-L20 and satte-of-thee fft-thh-rr art analytical minimax optimizers (GDA, OMD, GD-Anchoring, and K-beam), for three test problems.
A3 PROOF OF SAFEGUARDING RESULT
Below a proof of the main result, Theorem 4.1:
Proof. We proceed 2020). First verify inequality with the energy sequence {E₃ (u*)))) (Step 1). This is used to obtain the convergence rate (Step 2). Resulting implications about limit points are established last (Step 3).
following manner, with much credit due to the analysis (Diakonikolas
Step 1. We claim
Eg Eg(u") < C
for all & 2
(9)
k.
A12

---

Published as a conference paper at ICLR 2021
We proceed by induction. First note Jaay is firmly nonexpansive, and so 2F IId Jaas is also
firmly nonexpansive (Bauschke et al. (011). which implies
[22(u) - 221(v)) < (2F(u)-
2F(v).u- v), for all V R x R.
(10)
Using 10 with u 12 and = u together with our choice of step sizes {}t}, J we find
E²(u²) ||F(u>)] - X
1 (F(u"), u²)
(11)
|F(u2)](-(F(u))) u''-u")
(12)
-(u²)
(13)
[F[(2)) - = (F(u)), - F(u"))
(14)
S 1 (1I2((u)) ( F(u?) - FF('))
(15)
S (F(u²)- ul) F(u²) F(
(16)
= - [(() F(u²) F(("))
(17)
(18)
Thus, Eg(u²) S C/2, and the base case holds. Inductively, suppose 99) holds taking k n for
some n 2 2. uf = =z"-1 then (9) holds, taking k = n - 1. by the conditional statement in Line
of Method 1. Alternatively, suppose un+1 # z z=+1, Applying (10) with u u=+1 and v yields
[F(u*))- F(u")ll 21|FF
S (F(u*t1)- F(u))l F(u"), un u²) (19)
Upon expansion of the left hand side, we discover
|F(u*+))| )| > (F(u*+)). _ n 2F(1")) (F(n"), nn -- F(u"))
(20)
Algebraic manipulations of the update formula for u=+1 yield the relations
An
u n+1 n +2F(u") = -- Ay
(u- - 11 1=+1);
(21a)
n + F(u")= >i An 1²") (1-2Xx)F(u'))
(21b)
Substituting 21 in 20 gives
An (F(u u² a 1
|F(u [[( < 1 An
(22)
An (F(u"), u² - -n) + (1 2A,, F(u
(23)
and we collect terms with F(u on the left hand side to obtain
M12 An Xm (F(u"t1), u² u t < (1 -1- 2A. | An (F(u"), u²)) -u)).
(24)
Furthermore, by our choice of step size sequence {2x)
71 1
1 1-2An
(25)
n + 1
and, for n 2 2,
1
An-1
An
(26)
n +
n n n -
Combining 24
255 and 266 with the definition of E,, in (7) yields
1
Fu
n (u")
(27)
Applying the inductive hypothesis, we deduce
C
C
C
Enti(u +1)
(28)
n a
n
n
71
+
n
+
A13

---

Published as a conference paper at ICLR 2021
and this inequality closes the induction. Thus, 9 holds by the principle of mathematical induction.
Step 2. Let u² be the projection of u' onto Fix(Jaos) so that
Iu' u"] || = arg min min(llu' ull Fix(Jaas)) d1.
(29)
Note this projection is well defined since the set of saddle points is convex. By for 2, ||F(u*)]1
A (F(u*), n' -++++ C
(30)
2k
A
(F(ut),, - -u> + (F("*) - F(u") ) u u²)
C
+
(31)
Ak
k
1/k
1 (F(u"), uu -u*) ) C
(32)
h
1 [I )Illu u² + C
(33)
b
k.
where the third line holds since F(u*) = 0 and F monotone. Using the quadratic formula with the fact that |[ 2 obtain (8), desired.
Step 3. Let ú be a limit point of {u²}. This implies there exists subsequence {u**} that converges to u. Since Japy is l-Lipschitz and norms are continuous, it follows that
1
d1 n1k
dP
4C
0 < - (a)l( lim I Jaaf(u S lim
0.
(34)
k-000
k-+00
2
7kk
By the squeeze lemma, we deduce ú E Fix(Jaar) ), i.., ū is saddle point of f. Because ú was an arbitrarily chosen limit point, each limit point of {u*} is a saddle point of f.
A4 DETAILS ON CURRICULUM LEARNING
In L20 framework, the reward for training the optimizer is defined as:
(()) = E3 Σ W. (f (a+))
(35)
where f is a distribution of functions. The Enhanced Twin-I20 using Curriculum Learning(CL) selects portion of instances that demonstrate "good training behaviors" (smaller gradients & more likely to get close to stationary points) to be counted into the reward, with the portion C' increasing linearly from 20% to 100% as the training epoch increases. In our experiments, the detailed scheme of C is:
= min (20 + epoch index, 1003%
(36)
where epoch index denotes the index of epoch when training, starting from and ending with 199 in our case. When applying CL, the actual reward becomes
T
[(0) = E, Σ wi (f)
(37)
where q(f) = 1 the value m(f) ΣT= we V v:)l ranks top of all sampled functions, and qf)) = 0 otherwise.
This process does not change the structure of Twin-L20, and essentially acts as adding masks to those training instances that demonstrate poor behavior and ignoring them in the actual training phase. Combining this trick with the existing framework, the Twin-L20 can achieve a higher success rate when solving problems with larger range of parameters.
A14

---

Published as a conference paper at ICLR 2021
A5 COMPUTATIONAL COST ANALYSIS
We analyze the number of the multipier-accummlltee operation (MAC) of Twin-L20 and K-beam (Hamm & Nohl 2018) for Seasaw problem testing instance with 20 trials of random x, y initialization, each trial lasting for 1000 iterations. As for K- K-beam, the numbers of MAC are 2.36M (Million), 3.8M, 8.11 M, 15.31M for K 2, 10 respectively. For Twin-L20, the total number of MAC is 3.86M.
We use K = 5 in K-beam for experiments in our paper whose number of MAC costs 2.1 times more than that of Twin--L20, yet its solution quality in terms of both the converging speed and the precision fails to beat it.
A6 MORE DISCUSSIONS ON THE DESIGN OF TWIN-L20 REWARD
We term the reward function in Eqn. 4 as abjective-based reward, since it penalizes the objective change from f (x y/) along both x and y updating directions. It is naturally inherited and extends the reward functions prevailing in most prior L20 works for minimization (Andrychowicz al. 2016 Li & Malik, 2016). whose default reward is to minimize a weighted sum of the past function values.
One may also design the following rewards, which we name as cradient-basedd rewards:
L(
m E,
V (It vi)l WV (z,, wtll
(38)
L(amin min
, mmaxx)
= Es
Σ
(a1,91-1) (ste, m/)
+
[ 1. (Ize, me)
(39)
1lye y1-11
x1-1
Eqn. 39 is the gradient-based Nikaido-Isoda function introduced by Raghunathan et al. (0019)
For minimax optimization, is not immediately clear whether the objective-based or the gradient- based might work practically better. Intuitively by definition, the former is likely lead towards a saddle point (defined in Eqn. [ and the latter to a stationary point. They do not always coincide in general, e.g, stationary point might not be a saddle point. But for all specific test problems we studied in Section 4 stationary point is also saddle point.
We try several experiments on the challenging seesaw problem as a specific example, to provide close comparison between the gradient- based in Eqn. 38 and the objective- abjective-based reward. We re-do Twin-1.20 by only replacing Eqn. 4 with the gradient-based reward, and our observations are: a) the gradient-based reward solves the seesaw problem worse than the objective- based one; b) the minimization variable x diverges on testing problem instances; c) the maximization variable y will converge to solution of precision magnitude 0.04 (for reference, converges to have magnitude less than 0.01 when using the objective- based loss). We further identify one possible cause after analyzing the gradient behaviors. Note here the madient-bbsedd reward could be expressed as:
/f (II + IV wfff(, = 2 cos(((xz) + sin' (ATZ)
n2
(40)
Because a, b ~ U [0.9, 1]. the first term often dominates during training due to the x² multiplier, unless y is sufficiently close to zero. The imbalance could be cause of instability. For example, this reward could sometimes penalize cos2 (axtr) to be close to zero, which is the opposite direction the true solution sin? 2 (ATx) = 0. Although this is just a very specific problem example, it reveals that the gradient-based loss may sometimes not work well as expected, due to the instability asymmetry of min/max gradients.
Besides, we have also tried the second gradient-based reward in Eqn. 39 and find it ineffective. It is mainly because the denominator (consecutive variable differences) can become very small and the loss will then explode and break training.
Back to the objective-bart bbaeed reward used in this paper, we have not observed oscillation empirically from all experiments far. Our hypothesis is that the recurrent structure of the proposed Twin-I.20
A15

---

Published as a conference paper at ICLR 2021
framework (shown in Eqn. plays role here. Although updates respectively, the LSTM of one variable actually takes in the information of the other LSTM implicitly, because it takes the output of the other input. When value of one LSTM update, all previous min and max updates can (in principle) be taken into account due to the effect of unrolled hack-propagation, e.g., the min and max updates each take reference not only its own, but also the other's 's higher-order past trajectory information. While this is a tentative explanation, think more in-depth analysis of why oscillation may or may not happen in L20 could be a really interesting future work.
two LSTMs for the min and max
penalize the objective function
Another implicit intuition that leads to prioritizing the use of objective-based over gradient-based is that, in classic minimization, objective change is summable (i.e., having a finite accumulation), but gradient change not summable general (unless with properties such as strong convexity). While summability is itself not guarantee for good training/testing performance, lack of summability means the loss may have an overly large dynamic range.
To summarize, our function-based objective naturally extends previous L20 convention, works better than other alternatives, and observes no oscillation yet. However, we emphasize that there is intention to claim the current reward in Eqn. is is the best choice for minimax L20 it is one of plausible options. We do concur the gradient- based reward designs in Eqn. 38 and Equ. 39 complicated yet interesting question, especially when considering more complicated minimax problems. Again, as this paper is intended only as the first work and pilot study towards understanding the profound challenges and rich possibilities for minimax L20, believe everything discussed and proposed here, including the loss function, has large room of improvement.
A16


Reviews:
[{"review_id": "koBe7DwJVmi", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper’s main contribution is to extend the L2O framework to solving minimax problems for the first time. \n\nMinimax optimization is in general unstable and harder to solve, challenging whether an L2O model can indeed figure out effective learning rules from data. Further, in order to design L2O for minimax problems, one has to decide to what extent the learning models for min and max updates should be coupled, and what reward shall be used (minimizing the negative cumulative objective value is no longer viable)\n\nBy discussing and comparing a number of design options, the authors find that two decoupled LSTMs sharing one variation-based reward is the best empirical design. They show this minimax L2O can display favorable empirical convergence speed on several testbed problems, compared against a number of analytical solvers.\n\nMore importantly, most L2O methods have little or no convergence guarantees, which constitutes another roadblock for broadening their practical usage, such as people often questioning whether they will diverge on some even slightly different problem or data. The authors presented Safeguarded Twin L2O, a preliminary theory effort saying that under some strong assumptions, it is possible to theoretically establish the general worst-case convergence of Twin-L2O. \n\nThe proof draws and integrate two sources of ideas: (1) the safeguarded L2O technique recently developed for convex minimization (Heaton et al., 2020); and (2) Halpern iteration. For this part, it is unclear to me why Halpern iteration was chosen as the fallback method in their safeguarded L2O, since it is not a current popular or fast minimax solver. Is the safeguarded L2O framework also compatible with other convergent minimax solvers?\n\nIn Section 4.4, the authors said on unseen data, their safe-Twin-L2O remains to converge successfully and even faster than Halpern iteration. Is this really correct? As far as I understand, on an unseen distribution the optimization should “fall back” to exactly the Halpern iteration; so shouldn’t safeguarded L2O behave identically with Halpern on unseen data?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "XQoqbxsWkL7", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the learning to optimize (L2O) for minimax optimization. Since L2O has been studied in a few works, extending L2O from continuous minimization to minimax is a straightforward idea and not super-novel. But it also is a non-trivial effort, as minimax problems are much harder and unstable to solve. \n\nThe authors proposed to use two LSTMs with one shared reward, for updating min and max variables respectively. They presented a careful ablation study of design options such as (semi-)weight sharing between the two and their reward function, which is valuable for helping us understand what matters for L2O to work in minimax L2O.\n\nThe authors then presented two extensions to improve the generalization of Twin-L2O. The first one is based on curriculum learning to focus the meta-training gradually from easy to hard instances.  The second one is a minimax safeguard mechanism under a special case of solving convex-concave problems; the theory part seems to be a direct extension of (Heaton et al., 2020). \n\nThe following suggestions are for the authors:\n\n-\tIt is impressive to see that on relatively challenging minimax problems such as Seesaw, Twin-L2O can achieve one-magnitude higher-precision solutions than carefully tuned analytical algorithms. The number of iterations and MAC numbers needed for convergence are also comparable. I wonder whether the authors could also make a fair comparison on their running clock time? \n\n-\tOne further suggestion is that, it would be natural (and to the authors’ good) to combine enhanced L2O and safeguarded L2O together for solving convex-concave problems, so that we can get an impression on how large benefits it can lead to if we combine the best of the two L2O improvement ideas.\n\n-\tI appreciate the authors clearly and openly discussed the current work’s limitations by end of the paper. Although the paper was positioned as “proof of concept”, it could also be strengthened if some real problem can be demonstrated, e.g., training of a very simple GAN or so.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NtvKdU-MLi_", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Classical iterative minimax optimization algorithms display the unstable dynamics. Their convergence is often sensitive to the parameters and needs to be re-tuned for different problems to ensure convergence. Therefore, there is a practical motivation to develop L2O for minimax problems, so that we could meta-learn and adapt optimization rules to a special class of functions. \n\nTo extend L2O from minimization to minimax where two groups of variables need be updated, the authors designed and explored a variety of model options. They find that using two LSTMs, with only their reward function shared, to benefit meta-learning most, particularly when the min and max updates are highly non-symmetric. The decoupled design is aligned with the experience in classical optimizers, e.g., the max step often needs for solution tracking. The authors also described both a curriculum training strategy, and a preliminary theory called safeguarding, to make L2O models be able to solve a wider range of problems. \n\nThis paper’s contribution mainly lies in the engineering side, i.e., demonstrating meta learning or L2O can handle more complicated tasks/objectives than conventionally solving minimization. It is an interesting empirical study and is also done solidly. I believe this paper could attract interest and generate follow-up ideas from the L2O community.\n\nOn the math side, even though the authors tried to motivate their work from the limitation of classical minimax algorithms, I feel its impact may be limited for the optimization field, as it does not reveal many insights on how to design new minimax algorithms or providing better theory guarantees. \n\nRegarding the experiments, the authors demonstrated three simple testbed functions. As an empirical paper, it would definitely become stronger if the authors can prove their concept on some real minimax problems such as GAN or robust/private training.\n\nThe paper is in general well-written. With a lot of contents packed, the authors managed to organize and lay out their logic flow smoothly and clearly. I found just some typos: meta-learing -> meta-learning, draws and integrate -> draws and integrate, recently just introduce -> recently just introduced.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "GjYwFiDYZ-Q", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nThe paper introduces the _learning to optimize_ (L2O) framework into the solution of minimax problems. The base model is composed of two decoupled LSTMs with a shared objective, with the two LSTMs being respectively responsible for the update of the min and max variables. On top of this, the authors further investigate two possible improvements.  One consists in applying curriculum learning to improve the generalization capability of the solver while the other uses safeguarding to guarantee convergence in convex-concave problems.\nNumerical experiments are presented to justify the design choices of the base model and demonstrate the potential of minimax L2O.\n\n---\n### Pros\nThe paper is well-organized, easy to follow and provides a clear context for the problem that is studied.\nThis problem is particularly challenging and the authors manage to obtain some preliminary results.\n\n---\n### Score justification\n\nI do not think the paper meets the acceptance criteria mainly due to the following reasons (all together):\n1. Lack of clear motivation.\n2. Lack of groundbreaking idea.\n3. The definition of the loss function is not convincing.\n4. The experiments do not provide strong evidence of the utility of the method either.\n\nAlthough I fully understand this paper is just intended to be a proof of concept study that demonstrates the usefulness of L2O in minimax problems, I believe the authors should justify more the framework and their algorithmic choices (as done for the decoupled design).\n\n---\n### In more detail\n\n1. While finding efficient algorithms for solving minimax problems is without doubt of increasing importance in machine learning today, in the paper there seems to be a lack of justification for the use of L2O in minimax problems.\nIn the literature, the L2O methodology has been mostly applied to relatively well-studied problems, such as sparse coding and function minimization. On the contrary, minimax optimization is much less well understood and there is little consensus on which optimization algorithm should be used when solving a particular minimax problem. In a sense, while meta learning approaches search for a universal solution to different problems, in minimax optimization people have not even agreed on the solution of a single problem.\nTherefore, it would be beneficial if the authors could provide concrete examples for which they believe minimax L2O can really help.\n2. In terms of the originality of the paper, the proposed models are basically combinations of existing ideas. While minimax L2O poses unprecedented challenges as claimed by the authors, this work does not seem to propose any dedicated solutions to address these challenges.\n3. More importantly, I do not find what the authors propose as the loss function of the solver convincing. The definition of this loss function is probably one of the most important things in the framework. Nonetheless, I fail to see why encouraging stepwise progress in the two variables will necessarily lead to a solution of the problem. In my opinion, the objective (4) may lead to an unstable behavior of the generated iterates.\n4. To finish, the experiments do not provide a strong motivation for the use of minimax L2O either.\n5. A minor point: the proximal point of the safeguarding mechanism is not always computable so even for convex-concave problems safeguard Twin-L2O does not really offer a practical algorithm.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed Twin L2O (learning to optimize) for extending L2O from minimization to minimax problems. The authors honestly discussed the limitation of Twin L2O and proposed two improvements upon it with better generalization/transferability. While some reviewer had some concerns on the motivation of applying L2O to solve minimax problems and the motivation of the loss-function design (why objective-based one is chosen but not gradient-based one), the authors have done a particularly good job in the rebuttal. Even though this is more a proof-of-concept paper, it indeed has novel and solid contributions, and should be accept for publication.
Decision: Accept (Poster)