summaries: This paper studies the nonconvex strongly-concave min-max optimization problem. It improves the analysis of an existing method SREDA to make it allow larger step size and less initialization computation. Besides, it extends the algorithm to the case where the objective function is non-differentiable. The authors claimed it is the first zeroth-order variance-reduced method for the min-max problem. Experiments are conducted to demonstrate the improved algorithm is better than existing methods.

summaries: The paper proposes a SREDA-Boost, which builds upon SREDA for nonconvex-strongly-concave minimax problem. The SREDA-Boost algorithm is less restrictive to initialization and has an accuracy-independent and larger step size. Thus it can run substantially faster than SREDA. The main contribution to the first-order optimization story is a new analytical framework that builds upon the previous analysis in SREDA and overcomes the dependence of highly accurate initialization via bounding the tracking error and gradient estimation error separately. It also proposes a zeroth-order variance reduction algorithm for the same optimization problem, which has the largest possible step size so far and also improves the complexity of the state-of-the-art in some cases. Various experiments have validated the superiority. The theoretical analysis and empirical results look good to me.

summaries: The paper proposes a variant SREDA-Boost of the variance reduction method SEDRA for solving nonconvex-strongly-concave min-max problem. The first contribution of the paper is to relax the conditions on the initialization  of SEDRA and moreover enable larger stepsizes ($\epsilon$-independent stepsizes). As SEDRA is already optimal, such modification does not improve the theoretical convergence rate, but it is beneficial from the practical perspective. The second contribution is to adapt the method to zero order oracle, achieving the state-of-the-art convergence rate.

abstractText: Min-max optimization captures many important machine learning problems such as robust adversarial learning and inverse reinforcement learning, and nonconvexstrongly-concave min-max optimization has been an active line of research. Specifically, a novel variance reduction algorithm SREDA was proposed recently by (Luo et al. 2020) to solve such a problem, and was shown to achieve the optimal complexity dependence on the required accuracy level . Despite the superior theoretical performance, the convergence guarantee of SREDA requires stringent initialization accuracy and an -dependent stepsize for controlling the per-iteration progress, so that SREDA can run very slowly in practice. This paper develops a novel analytical framework that guarantees the SREDA’s optimal complexity performance for a much enhanced algorithm SREDA-Boost, which has less restrictive initialization requirement and an accuracy-independent (and much bigger) stepsize. Hence, SREDA-Boost runs substantially faster in experiments than SREDA. We further apply SREDA-Boost to propose a zeroth-order variance reduction algorithm named ZO-SREDA-Boost for the scenario that has access only to the information about function values not gradients, and show that ZO-SREDA-Boost outperforms the best known complexity dependence on . This is the first study that applies the variance reduction technique to zeroth-order algorithm for min-max optimization problems.

title: Natasha: faster non-convex stochastic optimization via strongly non-convex parameter

venue: In Proc. International Conference on Machine Learning (ICML),

authors:
Zeyuan Allen-Zhu
Elad Hazan

title: Variance reduction for faster non-convex optimization

authors:
Yossi Arjevani
Yair Carmon
John C Duchi
Dylan J Foster
Nathan Srebro
Blake Woodworth

title: Lower bounds for non-convex stochastic optimization

authors:
Ilija Bogunovic
Jonathan Scarlett
Stefanie Jegelka
Volkan Cevher

title: Adversarially robust optimization with gaussian processes

venue: In Proc. Advances in Neural Information Processing Systems (NeurIPS),

authors:
C. Chang
C. Lin

title: LIBSVM: A library for support vector machines

venue: ACM Transactions on Intelligent Systems and Technology,

authors:
Tatjana Chavdarova
Gauthier Gidel
François Fleuret
Simon Lacoste-Julien

title: Reducing noise in GAN training with variance reduced extragradient

venue: In Proc. Advances in Neural Information Processing Systems (NIPS),

authors:
Aaron Defazio
Francis Bach
Simon Lacoste-Julien

title: SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives

authors:
Simon S Du
Wei Hu

title: Linear convergence of the primal-dual gradient method for convex-concave saddle point problems without strong convexity

venue: In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS),

authors:
Simon S Du
Jianshu Chen
Lihong Li
Lin Xiao
Dengyong Zhou

title: Stochastic variance reduction methods for policy evaluation

authors:
Cong Fang
Chris Junchi Li
Zhouchen Lin
Tong Zhang

title: SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator

venue: In Advances in Neural Information Processing Systems (NeurIPS),

authors:
Saeed Ghadimi
Guanghui Lan

title: Stochastic first-and zeroth-order methods for nonconvex stochastic programming

venue: SIAM Journal on Optimization,

authors:
Ian Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron Courville
Yoshua Bengio

title: Generative adversarial nets

authors:
Jonathan Ho
Stefano Ermon

title: Generative adversarial imitation learning

authors:
Kaiyi Ji
Zhe Wang
Yi Zhou
Yingbin Liang

title: Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization

venue: In Proc. International Conference on Machine Learning,

authors:
Chi Jin
Praneeth Netrapalli
Michael I Jordan

title: Minmax optimization: stable limit points of gradient descent ascent are locally optimal

authors:
Rie Johnson
Tong Zhang

title: Accelerating stochastic gradient descent using predictive variance reduction

authors:
Yuan-Chuan Li
Cheh-Chih Yeh

title: Some equivalent forms of Bernoulli’s inequality: A survey

venue: Applied Mathematics,

authors:
Tianyi Lin
Chi Jin
Michael I Jordan

title: On gradient descent ascent for nonconvex-concave minimax problems

venue: arXiv preprint arXiv:1906.00331,

authors:
Sijia Liu
Songtao Lu
Xiangyi Chen
Yao Feng
Kaidi Xu
Abdullah Al-Dujaili
Minyi Hong
Una-May

title: Obelilly. Min-max optimization without gradients: convergence and applications to adversarial ML

authors:
Songtao Lu
Ioannis Tsaknakis
Mingyi Hong
Yongxin Chen

title: Hybrid block successive approximation for one-sided non-convex min-max problems: algorithms and applications

venue: IEEE Transactions on Signal Processing, PP:1–1,

authors:
Luo Luo
Cheng Chen
Yujun Li
Guangzeng Xie
Zhihua Zhang

title: A stochastic proximal point algorithm for saddle-point problems

authors:
Luo Luo
Haishan Ye
Tong Zhang

title: Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-concave minimax problems

venue: arXiv preprint arXiv:2001.03724,

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks

venue: In Proc. International Conference on Learning Representations (ICLR),

authors:
Matt Menickelly
Stefan M Wild

title: Derivative-free robust optimization by outer approximations

venue: Mathematical Programming,

title: Introductory Lectures on Convex Optimization: A Basic Course, volume 87

venue: Springer Science & Business Media,

authors:
Yurii Nesterov
Vladimir Spokoiny

title: Random gradient-free minimization of convex functions

venue: Foundations of Computational Mathematics,

authors:
Lam M Nguyen
Jie Liu
Katya Scheinberg
Martin Takáč

title: SARAH: A novel method for machine learning problems using stochastic recursive gradient

title: Stochastic recursive gradient algorithm for nonconvex optimization

venue: arXiv preprint arXiv:1705.07261,

authors:
Lam M Nguyen
Katya Scheinberg
Martin Takáč

title: Inexact SARAH algorithm for stochastic optimization

venue: arXiv preprint arXiv:1811.10105,

authors:
Maher Nouiehed
Maziar Sanjabi
Tianjian Huang
Jason D Lee
Meisam Razaviyayn

title: Solving a class of non-convex min-max games using iterative first order methods

authors:
Balamurugan Palaniappan
Francis Bach

title: Stochastic variance reduction methods for saddle-point problems

title: Gradient methods for minimizing functionals

venue: Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki,

authors:
Hassan Rafique
Mingrui Liu
Qihang Lin
Tianbao Yang

title: Non-convex min-max optimization: provable algorithms and applications in machine learning

authors:
Sashank J. Reddi
Ahmed Hefny
Suvrit Sra
Barnabas Poczos
Alex Smola

title: Stochastic variance reduction for nonconvex optimization

authors:
Abhishek Roy
Yifang Chen
Krishnakumar Balasubramanian
Prasant Mohapatra

title: Online and bandit algorithms for nonstationary stochastic saddle-point optimization

authors:
Kiran K Thekumparampil
Prateek Jain
Praneeth Netrapalli
Sewoong Oh

title: Efficient algorithms for smooth minimax optimization

authors:
Hoi-To Wai
Mingyi Hong
Zhuoran Yang
Zhaoran Wang
Kexin Tang

title: Variance reduced policy evaluation with smooth function approximation

authors:
Zhe Wang
Kaiyi Ji
Yi Zhou
Yingbin Liang
Vahid Tarokh

title: SpiderBoost: A class of faster variance-reduced algorithms for nonconvex optimization

venue: In Proc. Advances Neural Information Processing Systems (NeurIPS),

authors:
Zhongruo Wang
Krishnakumar Balasubramanian
Shiqian Ma
Meisam Razaviyayn

title: Zerothorder algorithms for nonconvex minimax problems with improved complexities

venue: arXiv preprint arXiv:2001.07819,

authors:
Zi Wang
Stefanie Jegelka

title: Max-value entropy search for efficient bayesian optimization

authors:
Chen-Yu Wei
Yi-Te Hong
Chi-Jen Lu

title: Online reinforcement learning in stochastic games

authors:
Junchi Yang
Negar Kiyavash
Niao He

title: Global convergence and variance-reduced optimization for a class of nonconvex-nonconcave minimax problems

venue: arXiv preprint arXiv:2002.09621,

authors:
Kaiqing Zhang
Zhuoran Yang
Tamer Başar

title: Multi-agent reinforcement learning: a selective overview of theories and algorithms

venue: arXiv preprint arXiv:1911.10635,

heading: 1 INTRODUCTION

text:
Min-max optimization has attracted significant growth of attention in machine learning as it captures several important machine learning models and problems including generative adversarial networks (GANs) Goodfellow et al. (2014), robust adversarial machine learning Madry et al. (2018), imitation learning Ho & Ermon (2016), etc. Min-max optimization typically takes the following form
min x∈Rd1 max y∈Rd2 f(x, y), where f(x, y) , { E[F (x, y; ξ)] (online case) 1 n ∑n i=1 F (x, y; ξi) (finite-sum case)
(1)
where f(x, y) takes the expectation form if data samples ξ are taken in an online fashion, and f(x, y) takes the finite-sum form if a dataset of training samples ξi for i = 1, . . . , n are given in advance.
This paper focuses on the nonconvex-strongly-concave min-max problem, in which f(x, y) is nonconvex with respect to x for all y ∈ Rd2 , and f(x, y) is µ-strongly concave with respect to y for all x ∈ Rd1 . The problem then takes the following equivalent form:
min x∈Rd1
{ Φ(x) , max
y∈Rd2 f(x, y)
} . (2)
The objective function Φ(·) in eq. (2) is nonconvex in general, and hence algorithms for solving eq. (2) are expected to attain an approximate (i.e., -accurate) first-order stationary point. The convergence of deterministic algorithms for solving eq. (2) has been established in Jin et al. (2019); Nouiehed et al. (2019); Thekumparampil et al. (2019); Lu et al. (2020). SGD-type of stochastic algorithms have also been proposed to solve such a problem more efficiently, including SGDmax Jin et al. (2019),
PGSMD Rafique et al. (2018), and SGDA Lin et al. (2019), which respectively achieve the overall complexity of O(κ3 −4 log(1/ ))1, O(κ3 −4), and O(κ3 −4). Furthermore, several variance reduction methods have been proposed for solving eq. (2) for the nonconvex-strongly-concave case. PGSVRG Rafique et al. (2018) adopts a proximally guided SVRG method and achieves the overall complexity of O(κ3 −4) for the online case and O(κ2n −2) for the finite-sum case. Wai et al. (2019) converted the value function evaluation problem to a specific minmax problem and applied SAGA to achieve the overall complexity of O(κn −2) for the finite-sum case. More recently, Luo et al. (2020) proposed a novel nested-loop algorithm named Stochastic Recursive Gradient Descent Ascent (SREDA), which adopts SARAH/SPIDER-type Nguyen et al. (2017a); Fang et al. (2018) of recursive variance reduction method (originally designed for solving the minimization problem) for designing gradient estimators to update both x and y. Specifically, x takes the normalized gradient update in the outer-loop and each update of x is followed by an entire innerloop updates of y. Luo et al. (2020) showed that SREDA achieves an overall complexity ofO(κ3 −3) for the online case in eq. (1), which attains the optimal dependence on Arjevani et al. (2019). For the finite-sum case, SREDA achieves the complexity of O(κ2 √ n −2 + n+ (n+ k) log(κ/ )) for n ≥ κ2, and O((κ2 + κn) −2) for n ≤ κ2. Although SREDA achieves the optimal complexity performance in theory, two issues may substantially degrade its practice performance. (1) SREDA has a stringent requirement on the initialization accuracy ζ = κ−2 2, which hence requires O(κ2 −2 log(κ/ )) gradient estimations in the initialization, and is rather costly in the high accuracy regime (i.e., for small ). (2) The convergence of SREDA requires the stepsize to be substantially small, i.e., at the -level with αt = O(min{ /(κ` ‖vt‖2), 1/(κ`)}), which restricts each iteration to make only -level progress with ‖xt+1 − xt‖2 = O( /κ`). Consequently, SREDA can run very slowly in practice. • Thus, a vital question arising here is whether we can guarantee the same optimal complexity
performance of SREDA even if we considerably relax its initialization (i.e., much bigger than O( 2)) and enlarge its stepsize (i.e., much bigger than O( )). The answer is highly nontrivial because the original analysis framework for SREDA in Luo et al. (2020) critically relies on these restrictions. The first focus of this paper is on developing a novel analytical framework to guarantee that such enhanced SREDA continues to hold the SREDA’s optimal complexity performance.
Furthermore, in many machine learning scenarios, min-max optimization problems need to be solved without the access of the gradient information, but only the function values, e.g., in multi-agent reinforcement learning with bandit feedback Wei et al. (2017); Zhang et al. (2019) and robotics Wang & Jegelka (2017); Bogunovic et al. (2018). This motivates the design of zeroth-order (i.e., gradient-free) algorithms. For nonconvex-strongly-concave min-max optimization, Liu et al. (2019) studied a constrained problem and proposed ZO-min-max algorithm that achieves the computational complexity of O((d1 + d2) −6). Wang et al. (2020) designed ZO-SGDA and ZO-SGDMSA, where ZO-SGDMA achieves the best known query complexity of O((d1 + d2)κ2 −4 log(1/ )) among the zeroth-order algorithms for this problem. All of the above studies are of SGD-type, and no efforts have been made on developing variance reduction zeroth-order algorithms for nonconvex-strongly-concave min-max optimization to further improve the query complexity.
• The second focus of this paper is on applying the aforementioned enhanced SREDA algorithm to design a zeroth-order variance reduced algorithm for nonconvex-strongly-concave min-max problems, and further characterizing its complexity guarantee which we anticipate to be orderwisely better than that of the existing stochastic algorithms.

heading: 1.1 MAIN CONTRIBUTIONS

text:
This paper first studies an enhanced SREDA algorithm, called SREDA-Boost, which improves SREDA from two aspects. (1) For the initialization, SREDA-Boost requires only an accuracy of ζ = κ−1, which is much less stringent than that of ζ = κ−2 2 required by SREDA. (2) SREDABoost allows an accuracy-independent stepsize α = O(1/(κ`)), which is much larger than the -level stepsize α = O(min{ /(κ` ‖vt‖2), 1/(κ`)}) adopted by SREDA. Hence, SREDA-Boost can run much faster than SREDA.
1The constant κ = `/µ, where µ is the strong concavity parameter of f(x, ·), and ` is the Lipschitz constant of the gradient of f(x, y) as defined in Assumption 2. Typically, κ is much larger than one.
The first contribution of this paper lies in developing a new analysis technique to provide the computational complexity guarantee for SREDA-Boost, establishing that even with considerably relaxed conditions on the initialization and stepsize, SREDA-Boost achieves the same optimal complexity performance as SREDA. The analysis technique of SREDA in Luo et al. (2020) does not handle such a case, because the proof highly relies on the stringent initialization and stepsize requirements. Central to our new analysis framework is the novel approach for bounding two interconnected stochastic error processes: tracking error and gradient estimation error (see Section 4 for their formal definitions), which take three steps: bounding the two error processes accumulatively over the entire algorithm execution, decoupling these two inter-related stochastic error processes, and establishing each of their relationships with the accumulative gradient estimators.
The second contribution of this paper lies in proposing the zeroth-order variance reduced algorithm ZO-SREDA-Boost for nonconvex-strongly-conconve min-max optimization when the gradient information is not accessible. For the online case, we show that ZO-SREDA-Boost achieves an overall query complexity of O((d1 + d2)κ3 −3), which outperforms the best known complexity (achieved by ZO-SGDMSA Wang et al. (2020)) in the case with ≤ κ−1. For the finite-sum case, we show that ZO-SREDA-Boost achieves an overall query complexity of O((d1 +d2)(κ2 √ n −2 +n) +d2(κ
2 +κn) log(κ)) when n ≥ κ2, andO((d1 +d2)(κ2 +κn)κ −2) when n ≤ κ2. This is the first study that applies the variance reduction method to zeroth-order nonconvex-stronlgy-concave min-max optimization.

heading: 1.2 RELATED WORK

text:
Due to the vast amount of studies on min-max optimization and the variance reduced algorithms, we include below only the studies that are highly relevant to this work.
Variance reduction methods for min-max optimization are highly inspired by those for conventional minimization problems, including SAGA Defazio et al. (2014); Reddi et al. (2016), SVRG Johnson & Zhang (2013); Allen-Zhu & Hazan (2016); Allen-Zhu (2017), SARAH Nguyen et al. (2017a;b; 2018), SPIDER Fang et al. (2018), SpiderBoost Wang et al. (2019), etc. But the convergence analysis for min-max optimization is much more challenging, and is typically quite different from their counterparts in minimization problems.
For strongly-convex-strongly-concave min-max optimization, Palaniappan & Bach (2016) applied SVRG and SAGA to the finite-sum case and established a linear convergence rate, and Chavdarova et al. (2019) proposed SVRE later to obtain a better bound. When the condition number of the problem is very large, Luo et al. (2019) proposed a proximal point iteration algorithm to improve the
performance of SAGA. For some special cases, Du et al. (2017); Du & Hu (2019) showed that the linear convergence rate of SVRG can be maintained without the strongly-convex or strongly concave assumption. Yang et al. (2020) applied SVRG to study the min-max optimization under the two-sided Polyak-Lojasiewicz condition.
Nonconvex-strongly-concave min-max optimization is the focus of this paper. As we discuss at the beginning of the introduction, the SGD-type algorithms have been developed and studied, including SGDmax Jin et al. (2019), PGSMD Rafique et al. (2018), and SGDA Lin et al. (2019). Several variance reduction methods have also been proposed to further improve the performance, including PGSVRG Rafique et al. (2018), the SAGA-type algorithm for min-max optimization Wai et al. (2019), and SREDA Luo et al. (2020). Particularly, SREDA has been shown in Luo et al. (2020) to achieve the optimal complexity dependence on . This paper further provides the convergence guarantee for SREDA-Boost (which enhances SREDA with relaxed initialization and much larger stepsize) by developing a new analysis technique.
While SGD-type zeroth-order algorithms have been studied for min-max optimization, such as Menickelly & Wild (2020); Roy et al. (2019) for convex-concave min-max problems and Liu et al. (2019); Wang et al. (2020) for nonconvex-strongly-concave min-max problems, variance reduced algorithms have not been developed for zeroth-order min-max optimization so far. This paper proposes the first such an algorithm named ZO-SREDA-Boost for nonconvex-strongly-concave min-max optimization, and established its complexity performance that outperforms the existing comparable algorithms (see Table 1).

heading: 2 NOTATION AND PRELIMINARIES

text:
In this paper, we use ‖·‖2 to denote the Euclidean norm of vectors. For a finite set S, we denote its cardinality as |S|. For a positive integer n, we denote [n] = {1, · · · , n}. We assume that the min-max problem eq. (2) satisfies the following assumptions, which have also been adopted by Luo et al. (2020) for SREDA. We slightly abuse the notation ξ below to represent the random index in both the online and finite-sum cases, where in the finite-sum case, Eξ[·] is with respect to the uniform distribution over {ξ1, · · · , ξn}. Assumption 1. The function Φ(·) is lower bounded, i.e., we have Φ∗ = infx∈Rd1 Φ(x) > −∞. Assumption 2. The component function F has an averaged `-Lipschitz gradient, i.e., for all (x, y), (x′, y′) ∈ Rd1 ×Rd2 , we have Eξ [ ‖∇F (x, y; ξ)−∇F (x′, y′; ξ)‖22 ] ≤ `2(‖x− x′‖22 + ‖y − y′‖ 2 2).
Assumption 3. The function f is µ-strongly-concave in y for any x ∈ Rd1 , and the component function F is concave in y, i.e., for any x ∈ Rd1 , y, y′ ∈ Rd2 and ξ, we have f(x, y) ≤ f(x, y′) + 〈∇yf(x, y′), y − y′〉 − µ2 ‖y − y ′‖2, and F (x, y; ξ) ≤ F (x, y′; ξ) + 〈 ∇yF (x, y′; ξ), y − y′ 〉 . Assumption 4. The gradient of each component function F (x, y; ξ) has a bounded variance, i.e., there exists a constant σ > 0 such that for any (x, y) ∈ Rd1×d2 , we have Eξ [ ‖∇F (x, y; ξ)−∇f(x, y)‖22 ] ≤ σ2 <∞.
Since Φ is nonconvex in general, it is NP-hard to find its global minimum. The goal here is to develop stochastic gradient algorithms that output an -stationary point as defined below. Definition 1. The point x̄ is called an -stationary point of the differentiable function Φ if ‖∇Φ(x̄)‖2 ≤ , where is a positive constant.

heading: 3 SREDA AND SREDA-BOOST ALGORITHMS

text:
We first introduce the SREDA algorithm proposed in Luo et al. (2020), and then describe an enhanced algorithm SREDA-Boost that we study in this paper.
SREDA (see Option I in Algorithm 1) utilizes the variance reduction techniques proposed in SARAH Nguyen et al. (2017a) and SPIDER Fang et al. (2018) for minimization problems to construct the gradient estimator recursively for min-max optimization. Specifically, the parameters xt and yt are updated in a nested loop fashion: each update of xt in the outer-loop is followed by (m + 1) updates of yt over one entire inner loop. Furthermore, the outer-loop updates of xt is divided into epochs for variance reduction. Consider a certain outer-loop epoch t = {(nt − 1)q, · · · , ntq − 1} (1 ≤ nt < dT/qe is a positive integer). At the beginning of such an epoch, the gradients are evaluated
with a large batch size S1 (see line 6 in Algorithm 1). Then, for each subsequent outer-loop iteration, an inner loop of ConcaveMaximizer (see Algorithm 2) recursively updates the gradient estimators for ∇xf(x, y) and ∇yf(x, y) with a small batch size S2. Note that although the inner loop does not update x, the gradient estimator ∇xf(x, y) is updated in the inner loop. With such a variance reduction technique, SREDA outperforms all previous algorithms for nonconvex-strongly-concave min-max problems (see Table 1), and was shown to achieve the optimal dependency on in complexity Luo et al. (2020).
Algorithm 1 SREDA and SREDA-Boost
1: Input: x0, initial accuracy ζ, learning rate αt, β = O( 1` ), batch size S1, S2 and periods q,m. 2: Option I (SREDA): ζ = κ−2 2; Option II (SREDA-Boost): ζ = κ−1 3: Initialization: y0 = iSARAH(−f(x0, ·), ζ) (see Appendix B.2 for iSARAH(·)) 4: for t = 0, 1, ..., T − 1 do 5: if mod(t, q) = 0 then draw S1 samples {ξ1, · · · , ξS1} 6: vt = 1S1 ∑S1 i=1∇xF (xt, yt, ξi), ut = 1 S1 ∑S1 i=1∇yF (xt, yt, ξi) 7: else 8: vt = ṽt−1,m̃t−1 , ut = ũt−1,m̃t−1 9: end if
10: Option I (SREDA): αt = min{ `‖vt‖2 , 1 2` }O( 1 κ ); Option II (SREDA-Boost): αt = α = O( 1κ` ) 11: xt+1 = xt − αtvt 12: yt+1 = ConcaveMaximizer(t,m,S2) 13: end for 14: Output: x̂ chosen uniformly at random from {xt}T−1t=0
Algorithm 2 ConcaveMaximizer(t,m,S2)
1: Initialization: x̃t,−1 = xt, ỹt,−1 = yt, x̃t,0 = xt+1, ỹt,0 = yt, ṽt,−1 = vt, ũt,−1 = ut 2: Draw S2 samples {ξ1, · · · , ξS2} 3: ṽt,0 = ṽt,−1 + 1S2 ∑S2 i=1∇xF (x̃t,0, ỹt,0, ξi)− 1 S2 ∑S2 i=1∇xF (x̃t,−1, ỹt,−1, ξi)
4: ũt,0 = ũt,−1 + 1S2 ∑S2 i=1∇yF (x̃t,0, ỹt,0, ξi)− 1 S2 ∑S2 i=1∇yF (x̃t,−1, ỹt,−1, ξi) 5: x̃t,1 = x̃t,0, ỹt,1 = ỹt,0 + βũt,0 6: for k = 1, 2, ...,m− 1 do 7: draw S2 samples {ξ1, · · · , ξS2} 8: ṽt,k = ṽt,k−1 + 1S2 ∑S2 i=1∇xF (x̃t,k, ỹt,k, ξi)− 1 S2 ∑S2 i=1∇xF (x̃t,k−1, ỹt,k−1, ξi)
9: ũt,k = ũt,k−1 + 1S2 ∑S2 i=1∇yF (x̃t,k, ỹt,k, ξi)− 1 S2 ∑S2 i=1∇yF (x̃t,k−1, ỹt,k−1, ξi)
10: x̃t,k+1 = x̃t,k, ỹt,k+1 = ỹt,k + βũt,k 11: end for 12: Output: yt+1 = ỹt,m̃t with m̃t chosen uniformly at random from {0, 1, · · · ,m}
Although SREDA achieves the optimal complexity performance in theory, two issues can substantially slow down its practical performance. (a) Its initialization y0 needs to satisfy a stringent 2-level requirement on the accuracy E[‖∇yf(x0, y0)‖22] ≤ κ
−2 2 (see line 2 in Algorithm 1), which requires as large as O(κ2 −2 log(κ/ )) stochastic gradient computations Luo et al. (2020). This is quite costly. (b) SREDA uses an -dependent stepsize and applies normalized gradient descent, so that each outer-loop update makes only -level progress given by ‖xt+1 − xt‖2 = O( /(κ`)). This substantially slows down SREDA. By following the analysis of SREDA, it appears that such choices for initialization and stepsize are necessary to obtain the guaranteed convergence rate.
In this paper, we study SREDA-Boost (see Option II in Algorithm 1) that enhances SREDA over the above two issues. (a) SREDA-Boost relaxes the initialization requirement to be E[‖∇yf(x0, y0)‖22] ≤ κ−1, which requires only O(κ log κ) gradient computations. This improves the computational cost upon SREDA by a factor of Õ(κ −2). (b) SREDA-Boost adopts an -independent stepsize αt = α = O(1/(κ`)) for xt so that each outer-loop update can make much bigger progress than SREDA. As our experiments in Section 6 demonstrate, SREDA-Boost runs much faster than SREDA.
To provide the convergence guarantee for SREDA-Boost, the analysis of SREDA in Luo et al. (2020) does not apply, because the proof highly depends on the stringent requirements on the
initialization and the stepsize. Thus, this paper provides a new analysis technique for establishing the complexity performance guarantee for SREDA-Boost and further applies it to the gradient-free min-max problems.

heading: 4 CONVERGENCE ANALYSIS OF SREDA-BOOST

text:
The following theorem provides the computational complexity of SREDA-Boost for finding a firstorder stationary point of Φ(·) with accuracy.
Theorem 1. Apply SREDA-Boost to solve the online case of the problem eq. (1). Suppose Assumptions 1-4 hold. Let ζ = κ−1, α = O(κ−1`−1), β = O(`−1), q = O( −1), m = O(κ), S1 = O(σ2κ2 −2) and S2 = O(κ −1). Then for T to be at least at the order of O(κ −2), Algorithm 1 outputs x̂ that satisfies E[‖∇Φ(x̂)‖2] ≤ with stochastic gradient complexity O(κ3 −3).
Furthermore, SREDA-Boost is also applicable to the finite-sum case of the problem eq. (1) by replacing the large batch S1 of samples used in line 6 of Algorithm 1 with the full set of samples.
Corollary 1. Apply SREDA-Boost described above to solve the finite-sum case of the problem eq. (1). Suppose Assumption 1-4 hold. Under appropriate parameter settings given in Appendix B.4, the overall gradient complexity to attain an -stationary point is O(κ2 √ n −2 + n+ (n+ κ) log(κ)) for n ≥ κ2, and O((κ2 + κn) −2) for n ≤ κ2.
To compare with SREDA, as shown in Luo et al. (2020), SREDA requires stringent initialization and stepsize selection to achieve the optimal complexity performance. In constrast, Theorem 1 and Corollary 1 show that those strict requirements are not necessary for achieving the optimal performance, and establish that SREDA-Boost achieves the same optimal complexity as SREDA under more relaxed initialization and a much bigger and accuracy-independent stepsize α.
The convergence analysis of SREDA-Boost in Theorem 1 is very different from the proof of SREDA in Luo et al. (2020). At a high level, such analysis mainly focuses on bounding two inter-related errors: tracking error δt = E[‖∇yf(xt, yt)‖22] that captures how well the output yt of the inner loop approximates the optimal point y∗(xt) for a given xt, and gradient estimation error ∆t = E[‖vt −∇xf(xt, yt)‖22 + ‖ut −∇yf(xt, yt)‖ 2 2] that captures how well the stochastic gradient estimators approximate the true gradients. In the analysis of SREDA in Luo et al. (2020), the stringent requirements for initialization and stepsize and the -level normalized gradient descent update substantially help to bound both errors δt and ∆t separately at the level for each iteration so that the convergence bound follows. In contrast, this is not applicable to SREDA-Boost which has relaxed and accuracy-independent initialization and stepsize. Hence, we develop a novel analysis framework to bound the accumulative errors ∑T−1 t=0 δt and ∑T−1 t=0 ∆t over the entire algorithm execution, and then decouple these two inter-related stochastic error processes and establish their relationships with the accumulative gradient estimators ∑T−1 i=0 E[‖vt‖ 2 2]. The following proof sketch of Theorem 1 further illustrates our ideas.
The analysis of SREDA-Boost for min-max problems is inspired by that for SpiderBoost in Wang et al. (2019) for minimization problems, but the analysis here is much more challenging due to the complicated mathematical nature of min-max optimization. Specifically, SpiderBoost needs to handle only one type of the gradient estimation error, whereas SREDA-Boost requires to handle two strongly coupled errors in min-max problems. Hence, the novelty for analyzing SREDA-Boost mainly lies in bounding and decoupling the two errors in order to characterize their impact on the convergence bound.

heading: 5 ZO-SREDA-BOOST AND CONVERGENCE ANALYSIS

text: In this section, we study the min-max problem when the gradient information is not available, but only function values can be used for designing algorithms. Based on the first-order SREDA-Boost algorithm, we first propose the zeroth-order variance reduced algorithm called ZO-SREDA-Boost and then provide the convergence analysis for such an algorithm.

heading: 5.1 ZO-SREDA-BOOST ALGORITHM

text:
The ZO-SREDA-Boost algorithm (see Algorithm 4 in Appendix C.1) shares the same update scheme as SREDA-Boost, but makes the following changes.
(1) In line 3 of SREDA-Boost, instead of using iSARAH, ZO-SREDA-Boost utilizes a zeroth-order algorithm ZO-iSARAH (Algorithm 6 in Appendix C.4) to search an initialization y0.
(2) At the beginning of each epoch in the outer loop (line 6 of SREDA-Boost), ZOSREDA-Boost utilizes coordinate-wise gradient estimators with a large batch S1 given by vt = (1/S1) ∑S1 i=1 ∑d1 j=1(F (xt + δej , yt, ξi) − F (xt − δej , yt, ξi))ej/(2δ) and ut =
(1/S1) ∑S1 i=1 ∑d2 j=1(F (xt, yt + δej , ξi) − F (xt, yt − δej , ξi))ej/(2δ), where ej denotes the j-th canonical unit basis vector. Note that the coordinate-wise gradient estimator is commonly taken in the zeroth-order variance reduce algorithms such as in Ji et al. (2019) for minimization problems.
(3) ZO-SREDA-Boost replaces ConcaveMaximizer (line 12 of SREDA) by ZO-ConcaveMaximizer (see Algorithm 5), in which the zeroth-order gradient estimators are recursively updated with small batches S2,x (for update of x) and S2,y (for update of y) based on the Gaussian estimators given by Gµ1(x, y, νM1,x , ξMx) = (1/S2,x) ∑ i∈[S2,x][F (x + µ1νi, y, ξi) − F (x, y, ξi)]νi/µ1
and Hµ2(x, y, ωM2,y , ξMy ) = (1/S2,y) ∑ i∈[S2,y ][F (x, y + µ2ωi, ξi) − F (x, y, ξi)]ωi/µ2, where νi ∼ N(0,1d1), ωi ∼ N(0,1d2) with 1d denoting the identity matrices with sizes d× d.

heading: 5.2 CONVERGENCE ANALYSIS OF ZO-SREDA-BOOST

text:
The following theorem provides the query complexity of ZO-SREDA-Boost for finding a first-order stationary point of Φ(·) with accuracy. Theorem 2. Apply ZO-SREDA-Boost in Algorithm 4 to solve the online case of the problem eq. (1). Suppose Assumptions 1-4 hold. Let ζ = κ−1, α = O(κ−1`−1), β = O(`−1), q = O( −1), m = O(κ), S1 = O(σ2κ2 −2), S2,x = O(d1κ −1), S2,y = O(d2κ −1), δ = O((d1 + d2)0.5κ−1`−1 ), µ1 = O(d−1.51 κ−2.5`−1 ) and µ2 = O(d −1.5 2 κ
−2.5`−1 ). Then for T to be at least at the order of O(κ −2), Algorithm 4 outputs x̂ that satisfies E[‖∇Φ(x̂)‖2] ≤ with the overall function query complexity O((d1 + d2)κ3 −3).
Furthermore, ZO-SREDA-Boost is also applicable to the finite-sum case of the problem eq. (1), by replacing the large batch sample S1 used in line 6 of Algorithm 4 with the full set of samples.
Corollary 2. Apply ZO-SREDA-Boost described above to solve the finite-sum case of the problem eq. (1). Suppose Assumptions 1-4 hold. Under appropriate parameter settings given in Appendix C.6, the function query complexity to attain an -stationary point isO((d1 +d2)( √ nκ2 −2 +n)+d2(κ
2 + κn) log(κ)) for n ≥ κ2, and O((d1 + d2)(κ2 + κn) −2) for n ≤ κ2.
Theorem 2 and Corollary 2 provide the first convergence analysis and the query complexity for the variance-reduced zeroth-order algorithms for min-max optimization. These two results indicate that the query complexity of ZO-SREDA-Boost matches the optimal dependence on of the first-order algorithm SREDA-Boost in Theorem 1 and Corollary 1. The dependence on d1 and d2 typically arises in zeroth-order algorithms due to the estimation of gradients with dimensions d1 and d2. Furthermore, in the online case, ZO-SREDA-Boost outperforms the best known query complexity dependence on among the existing zeroth-order algorithms by a factor of O(1/ ). Including the conditional number κ into consideration, SREDA-Boost outperforms the best known query complexity achieved by ZO-SGDMA in the case with ≤ κ−1 (see Table 1). Furthermore, Corollary 2 provides the first query complexity for the finite-sum zeroth-order min-max problems.
As a by-product, our analysis of ZO-SREDA-Boost also yields the convergence rate and the query complexity (see Lemma 21) for ZO-iSARAH for the conventional minimization problem, which provides the first complexity result for the zeroth-order recursive variance reduced algorithm SARAH/SPIDER for strongly convex optimization (see Appendix C.4 for detail).

heading: 6 EXPERIMENTS

text:
Our experiments focus on two types of comparisons. First, we compare SREDA-Boost with SREDA to demonstrate the practical advantage of SREDA-Boost. Second, we compare our proposed zeroth-
order variance reduction algorithm ZO-SREDA-Boost with the other existing zeroth-order stochastic algorithms and demonstrate the superior performance of ZO-SREDA-Boost.
Our experiments solve a distributionally robust optimization problem, which is commonly used for studying min-max optimization Lin et al. (2019); Rafique et al. (2018). We conduct the experiments on three datasets from LIBSVM Chang & Lin (2011). The details of the problem and the datasets are provided in Appendix A.
Comparison between SREDA-Boost and SREDA: We set = 0.001 for both algorithms. For SREDA, we set αt = min{ / ‖vt‖2 , 0.005} as specified by the algorithm, and for SREDA-Boost, we set αt = 0.005 as the algorithm allows. It can be seen in Figure 1 that SREDA-Boost enjoys a much faster convergence speed than SREDA due to the allowance of a large stepsize.
Comparison among zeroth-order Algorithms: We compare the performance of our proposed ZOSREDA-Boost with that of two existing stochastic algorithms ZO-SGDA Wang et al. (2020) and ZO-SGDMSA Wang et al. (2020) designed for nonconvex-strongly-concave min-max problems. For ZO-SGDA and ZO-SGDMSA, as suggested by the theorem, we set the mini-batch size B = Cd1/ 2 and B = Cd2/ 2 for updating the variables x and y, respectively. For ZO-SREDA-Boost, based on our theory, we set the mini-batch size B = Cd1/ and B = Cd2/ for updating the variables x and y, and set S1 = n for the large batch, where n is the number of data samples in the dataset. We set C = 0.1 and = 0.1 for all algorithms. We further set the stepsize η = 0.01 for ZO-SREDA-Boost and ZO-SGDMSA. Since ZO-SGDA is a two time-scale algorithm, we set η = 0.01 as the stepsize for the fast time scale, and η/κ3 as the stepsize for slow time scale (based on the theory) where κ3 = 10. It can be seen in Figure 2 that ZO-SREDA-Boost substantially outperforms the other two algorithms in terms of the function query complexity (i.e., the running time).

heading: 7 CONCLUSION

text: In this work, we have proposed enhanced variance reduction algorithms, which we call SREDA-Boost and ZO-SREDA-Boost, for solving nonconvex-strongly-concave min-max problems. In specific, SREDA-Boost requires less initialization effort and allows a large stepsize. Moreover, The complexity of SREDA-Boost and ZO-SREDA-Boost achieves the best complexity dependence on the targeted accuracy among their same classes of algorithms. We have also developed a novel analysis framework to characterize the convergence and computational complexity for the variance reduction algorithms. We expect such a framework will be useful for studying various other stochastic min-max problems such as proximal, momentum, and manifold optimization.


summaries: This paper studies one-shot 2D object detections. The major conclusion is that when keeping the number of training images fixed, increasing the number of training categories can significantly increase the one-shot performance.  This paper demonstrated this conclusion empirically by doing controlled experiments on COCO, Objects365, and LIVS.   Inspired by this observation, this paper improves the state-of-the-art one-shot detection performance on COCO from 22.0 to 27.5 AP50 by training on LIVS.  Other two related conclusions in this paper: - PASCAL VOC is not suitable for evaluating one-shot object detection algorithms. The reason may be that the number of instances per image is low(2.9 ins/img on average). The algorithm only needs to recognize foreground objects rather than objects of target categories.  - Only when the training data is challenging enough, increasing the model size and training time can help improve one-shot performance.

summaries: - The paper considers the problem of one-shot object detection, meaning, the model is asked to detect unseen categories, based on only one provided a template.  - The main discovery made by the authors is that, to generalise better, the model should be trained with data from as many categories as possible, given the same budget on number of samples for training.  - Architecture-wise, a Siamese Faster R-CNN is adapted.

summaries: This paper studies the effect of category number in the one-shot object detection task. In the testing of one-shot detection, there exists a performance gap between the base (training) classes and held-out classes. It is claimed that this performance gap can be largely closed by increasing the number of categories used for training. And the number of categories is more crucial than the number of samples per category. Experiments are conducted on VOC, COCO, Object365, and LVIS using a Siamese-style detector to verify the claims.

summaries: This paper shows that the key to reduce the generalization gap between base classes and novel classes is to increase the number of training categories, instead of training samples. The authors did many experiments on four existing datasets (PASCAL, COCO, Objects365, and LVIS) with Siamese Faster R-CNN to verify this point. Experiments show that with more categories in the training set, the generalization gap will be nearly closed. Finally, the author proposes that future data sets should focus on the diversity of categories.

abstractText:
Is it possible to detect arbitrary objects from a single example? A central problem of all existing attempts at one-shot object detection is the generalization gap: Object categories used during training are detected much more reliably than novel ones. We here show that this generalization gap can be nearly closed by increasing the number of object categories used during training. Doing so allows us to improve generalization from seen to unseen classes from 45% to 89% and improve the state-of-the-art on COCO by 5.4 %AP50 (from 22.0 to 27.5). We verify that the effect is caused by the number of categories and not the number of training samples, and that it holds for different models, backbones and datasets. This result suggests that the key to strong few-shot detection models may not lie in sophisticated metric learning approaches, but instead simply in scaling the number of categories. We hope that our findings will help to better understand the challenges of few-shot learning and encourage future data annotation efforts to focus on wider datasets with a broader set of categories rather than gathering more samples per category. Example based object detection Successful Detection of Novel Objects! A broad training dataset Re la tiv e pe rfo rm an ce
 no ve l/k no w n ob je ct s Categories 80 365 1203 46% 76% 89%

authors:
Christopher Berner
Greg Brockman
Brooke Chan
Vicki Cheung
Przemysław Debiak
Christy Dennison
David Farhi
Quirin Fischer
Shariq Hashme
Chris Hesse

title: Dota 2 with large scale deep reinforcement learning

authors:
Sujoy Kumar Biswas
Peyman Milanfar

title: One shot detection with laplacian object and fast matrix cosine similarity

authors:
Tom B Brown
Benjamin Mann
Nick Ryder
Melanie Subbiah
Jared Kaplan
Prafulla Dhariwal
Arvind Neelakantan
Pranav Shyam
Girish Sastry
Amanda Askell

title: Language models are few-shot learners

authors:
Nicolas Carion
Francisco Massa
Gabriel Synnaeve
Nicolas Usunier
Alexander Kirillov
Sergey Zagoruyko

title: End-to-end object detection with transformers

authors:
Ding-Jie Chen
He-Yen Hsieh
Tyng-Luh Liu

title: Adaptive image transformer for one-shot object detection

venue: In CVPR,

authors:
Kai Chen
Jiaqi Wang
Jiangmiao Pang
Yuhang Cao
Yu Xiong
Xiaoxiao Li
Shuyang Sun
Wansen Feng
Ziwei Liu
Jiarui Xu
Zheng Zhang
Dazhi Cheng
Chenchen Zhu
Tianheng Cheng
Qijie Zhao
Buyu Li
Xin Lu
Rui Zhu
Yue Wu
Jifeng Dai
Jingdong Wang
Jianping Shi
Wanli Ouyang
Chen Change Loy
Dahua Lin

title: MMDetection: Open mmlab detection toolbox and benchmark. arXiv:1906.07155, 2019a

authors:
Wei-Yu Chen
Yen-Cheng Liu
Zsolt Kira
Yu-Chiang Frank Wang
Jia-Bin Huang

title: A closer look at few-shot classification

authors:
Guneet S Dhillon
Pratik Chaudhari
Avinash Ravichandran
Stefano Soatto

title: A baseline for few-shot image classification

authors:
Mark Everingham
Luc Van Gool
Christopher K.I. Williams
John Winn
Andrew Zisserman

title: The Pascal Visual Object Classes (VOC) Challenge

venue: International Journal of Computer Vision,

authors:
Qi Fan
Wei Zhuo
Chi-Keung Tang
Yu-Wing Tai

title: Few-shot object detection with attention-rpn and multi-relation detector

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks

venue: In ICML,

authors:
Robert Geirhos
Jörn-Henrik Jacobsen
Claudio Michaelis
Richard Zemel
Wieland Brendel
Matthias Bethge
Felix A Wichmann

title: Shortcut learning in deep neural networks

authors:
Ross Girshick
Jeff Donahue
Trevor Darrell
Jitendra Malik

title: Rich Feature Hierarchies for Accurate Object Detection and Semantic Segmentation

authors:
Agrim Gupta
Piotr Dollar
Ross Girshick

title: LVIS: A dataset for large vocabulary instance segmentation

authors:
Alon Halevy
Peter Norvig
Fernando Pereira

title: The unreasonable effectiveness of data

venue: Intelligent Systems,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Ting-I Hsieh
Yi-Chen Lo
Hwann-Tzong Chen
Tyng-Luh Liu

title: One-shot object detection with co-attention and co-excitation

venue: In NeurIPS,

authors:
Shuqiang Jiang
Yaohui Zhu
Chenlong Liu
Xinhang Song
Xiangyang Li
Weiqing Min

title: Dataset bias in few-shot image recognition

authors:
Bingyi Kang
Zhuang Liu
Xin Wang
Fisher Yu
Jiashi Feng
Trevor Darrell

title: Few-shot object detection via feature reweighting

authors:
Gregory Koch
Richard Zemel
Ruslan Salakhutdinov

title: Siamese Neural Networks for One-shot Image Recognition

authors:
Alexander Kolesnikov
Lucas Beyer
Xiaohua Zhai
Joan Puigcerver
Jessica Yung
Sylvain Gelly
Neil Houlsby

title: Large scale learning of general visual representations for transfer

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks

authors:
Xiang Li
Lin Zhang
Yau Pun Chen
Yu-Wing Tai
Chi-Keung Tang

title: One-shot object detection without fine-tuning

authors:
Tsung-Yi Lin
Michael Maire
Serge Belongie
James Hays
Pietro Perona
Deva Ramanan
Piotr Dollár
C. Lawrence Zitnick

title: Microsoft COCO: Common Objects in Context

venue: In ECCV,

authors:
Tsung-Yi Lin
Piotr Dollár
Ross Girshick
Kaiming He
Bharath Hariharan
Serge Belongie

title: Feature Pyramid Networks for Object Detection

authors:
Tsung-Yi Lin
Priya Goyal
Ross Girshick
Kaiming He
Piotr Dollár

title: Focal loss for dense object detection

venue: In ICCV,

authors:
Claudio Michaelis
Matthias Bethge
Alexander S. Ecker

title: One-Shot segmentation in clutter

authors:
Claudio Michaelis
Ivan Ustyuzhaninov
Matthias Bethge
Alexander S. Ecker

title: One-Shot instance segmentation

authors:
Akihiro Nakamura
Tatsuya Harada

title: Revisiting fine-tuning for few-shot learning

authors:
Gerhard Neuhold
Tobias Ollmann
Samuel Rota Bulò
Peter Kontschieder

title: The mapillary vistas dataset for semantic understanding of street scenes

venue: In International Conference on Computer Vision (ICCV),

authors:
Anton Osokin
Denis Sumin
Vasily Lomakin

title: Os2d: One-stage one-shot object detection by matching anchor features

authors:
Alec Radford
Jong Wook Kim
Chris Hallacy
Aditya Ramesh
Gabriel Goh
Sandhini Agarwal
Girish Sastry
Amanda Askell
Pamela Mishkin
Jack Clark

title: Learning transferable visual models from natural language supervision

authors:
Shaoqing Ren
Kaiming He
Ross Girshick
Jian Sun

title: Faster r-cnn: Towards real-time object detection with region proposal networks

venue: In NIPS,

authors:
Andrei A Rusu
Dushyant Rao
Jakub Sygnowski
Oriol Vinyals
Razvan Pascanu
Simon Osindero
Raia Hadsell

title: Meta-learning with latent embedding optimization

authors:
Othman Sbai
Camille Couprie
Mathieu Aubry

title: Impact of base dataset design on few-shot image classification

authors:
Amirreza Shaban
Shray Bansal
Zhen Liu
Irfan Essa
Byron Boots

title: One-Shot Learning for Semantic Segmentation

authors:
Shuai Shao
Zeming Li
Tianyuan Zhang
Chao Peng
Gang Yu
Xiangyu Zhang
Jing Li
Jian Sun

title: Objects365: A large-scale, high-quality dataset for object detection

authors:
Jake Snell
Kevin Swersky
Richard Zemel

title: Prototypical Networks for Few-shot Learning

authors:
Chen Sun
Abhinav Shrivastava
Saurabh Singh
Abhinav Gupta

title: Revisiting unreasonable effectiveness of data in deep learning era

title: The bitter lesson

venue: Incomplete Ideas (blog),

authors:
Oriol Vinyals
Charles Blundell
Tim Lillicrap
Koray Kavukcuoglu
Daan Wierstra

title: Matching networks for one shot learning

authors:
Xin Wang
Thomas E Huang
Trevor Darrell
Joseph E Gonzalez
Fisher Yu

title: Frustratingly simple few-shot object detection

authors:
Yu-Xiong Wang
Deva Ramanan
Martial Hebert

title: Meta-learning to detect rare objects

authors:
Saining Xie
Ross Girshick
Piotr Dollár
Zhuowen Tu
Kaiming He

title: Aggregated residual transformations for deep neural networks

authors:
Xiaopeng Yan
Ziliang Chen
Anni Xu
Xiaoxi Wang
Xiaodan Liang
Liang Lin

title: Meta r-cnn: Towards general solver for instance-level low-shot learning

authors:
Tengfei Zhang
Yue Zhang
Xian Sun
Hao Sun
Menglong Yan
Xue Yang
Kun Fu

title: Comparison network for one-shot conditional object detection

authors:
Bolei Zhou
Hang Zhao
Xavier Puig
Sanja Fidler
Adela Barriuso
Antonio Torralba

title: Scene parsing through ade20k dataset

heading: 1 INTRODUCTION

text:
It’s January 2021 and your long awaited household robot finally arrives. Equipped with the latest “Deep Learning Technology”, it can recognize over 21,000 objects. Your initial excitement quickly vanishes as you realize that your casserole is not one of them. When you contact customer service they ask you to send some pictures of the casserole so they can fix this. They tell you that the fix will be some time, though, as they need to collect about a thousand images of casseroles to retrain the neural network. While you are making the call your robot knocks over the olive oil because the steam coming from the pot of boiling water confused it. You start filling out the return form ...
While not 100% realistic, the above story highlights an important obstacle towards truly autonomous agents: such systems should be able to detect novel, previously unseen objects and learn to recognize them based on (ideally) a single example. Solving this one-shot object detection problem can
be decomposed into three subproblems: (1) designing a class-agnostic object proposal mechanism that detects both known and previously unseen objects; (2) learning a suitably general visual representation (metric) that supports recognition of the detected objects; (3) continuously updating the classifier to accommodate new object classes or training examples of existing classes. In this paper, we focus on the detection and representation learning part of the pipeline, and we ask: what does it take to learn a visual representation that allows detection and recognition of previously unseen object categories based on a single example?
We operationalize this question using an example-based visual search task (figure 1) that has been investigated before using handwritten characters (Omniglot; Michaelis et al. (2018a)) and real-world image datasets (Pascal VOC, COCO; Michaelis et al. (2018b); Hsieh et al. (2019); Zhang et al. (2019); Fan et al. (2020); Li et al. (2020)). Our central hypothesis is that scaling up the number of object categories used for training should improve the generalization capabilities of the learned representation. This hypothesis is motivated by the following observations. On (cluttered) Omniglot (Michaelis et al., 2018a), recognition of novel characters works almost as well as for characters seen during training. In this case, sampling enough categories during training relative to the visual complexity of the objects is sufficient to learn a metric that generalizes to novel categories. In contrast, models trained on visually more complex datasets like Pascal VOC and COCO exhibit a large generalization gap: novel categories are detected much less reliably than ones seen during training. This result suggests that on the natural image datasets, the number of categories is too small given the visual complexity of the objects and the models retreat to a shortcut (Geirhos et al., 2020) – memorizing the training categories.
To test the hypothesis that wider datasets improve generalization, we increase the number of object categories during training by using datasets (LVIS, Objects365) that have a larger number of categories annotated. Our experiments support this hypothesis and suggest the following conclusions:
• The generalization gap between training and novel categories is a key problem in one-shot object detection.
• This generalization gap can be almost closed by increasing the number of categories used for training: going from 80 classses in COCO to 1200 in LVIS improves relative performance from 45% to 89%.
• A detailed analysis shows that number of categories, not the amount of data, is the driving force behind this effect.
• Closing the generalization gap allows using established methods from the object detection community (like e.g. stronger backbones) to improve performance on known and novel categories alike.
• We use these insights to improve state-of-the-art performance on COCO by 5.4 %AP50 (from 22 %AP50 to 27.5 %AP50) using annotations from LVIS.

heading: 2 RELATED WORK

text:
Object detection Object detection - the task of detecting objects in complex, cluttered scenes - has seen huge progress since the widespread adoption of DNNs Girshick et al. (2014); Ren et al. (2015); He et al. (2017); Lin et al. (2017a); Chen et al. (2019a); Wu et al. (2019); Carion et al. (2020). Similarly the number of datasets has grown steadily, fueled by the importance this task has for computer vision applications Everingham et al. (2010); Russakovsky et al. (2015); Lin et al. (2014); Zhou et al. (2017); Neuhold et al. (2017); Krasin et al. (2017); Gupta et al. (2019); Shao et al. (2019). However most models and datasets focus on scenarios where abundant examples per category are available.
Few-shot learning Algorithms for few-shot learning - learning a model from only a few examples - can broadly be separated into two categories: Metric learningKoch et al. (2015); Vinyals et al. (2016); Snell et al. (2017) - learn a good representation and metric that generalizes to new data. And meta learning Finn et al. (2017); Rusu et al. (2018) - learn a good way to learn a new task. However, recent work has shown that complex algorithmic approaches can be rivaled by improving and scaling simple approaches like transfer learning Chen et al. (2019b); Nakamura & Harada (2019); Dhillon et al. (2019); Kolesnikov et al. (2019).
Few-shot & one-shot object detection Recently, several groups have started to tackle few-shot learning for object detection. Two training and evaluation paradigms have emerged. The first is inspired by continual learning: incorporate a set of new categories with only a few labeled images per category into an existing classifier Kang et al. (2018); Yan et al. (2019); Wang et al. (2019; 2020). The second one phrases the problem as an example-based visual search: detect objects based on a single example image (Michaelis et al., 2018b; Hsieh et al., 2019; Zhang et al., 2019; Fan et al., 2020; Li et al., 2020, figure 1 left). We refer to the former (continual learning) as few-shot object detection, since typically 10–30 images are used for experiments on COCO. In contrast, we refer to the latter (visual search) as one-shot object detection, since the focus is on the setting with a single example. In the present paper we work with this latter paradigm, since it focuses on the representation learning part of the problem and avoids the additional complexity of continual learning.
Methods for one-shot object detection Existing methods for one-shot object detection usually combine a standard object detection architecture with metric or meta-learning methods Biswas & Milanfar (2015); Michaelis et al. (2018b); Hsieh et al. (2019); Zhang et al. (2019); Fan et al. (2020); Osokin et al. (2020); Li et al. (2020). To better handle complex scenes and pose changes methods such as spatial awareness Li et al. (2020) or pose transforms Biswas & Milanfar (2015); Osokin et al. (2020) have been proposed. A recent method uses a transformer to solve the matching problem Chen et al. (2021). We here use one of the most straightforward models, Siamese Faster R-CNN Michaelis et al. (2018b), to demonstrate that a change of the training data rather than the model architecture is sufficient to substantially reduce the generalization gap between known and novel categories.
Number of categories in few-shot learning Most of the few-shot learning literature focuses on developing algorithmic solutions to a set of existing small-scale benchmarks. In contrast a lot less attention has been payed to exploring new tasks or datasets. The influence of the training data was mostly observed indirectly, e.g. through better performance on datasets with more categories such as tieredImageNet vs. miniImageNet. We here flip the focus demonstrating that significant progress can be made by keeping the algorithm the same and only changing the training data. Concurrent studies confirm this finding that more categories help few-shot object detection Fan et al. (2020) and few-shot image classification Sbai et al. (2020); Jiang et al. (2020). We add to this by not only looking at few-shot performance but comparing it with performance on known categories (generalization gap). This allows us to uncover the functional relationship behind the effect (closing a shortcut).

heading: 3 EXPERIMENTS

text:
Models We mainly use Siamese Faster R-CNN, an example-based version of Faster R-CNN Ren et al. (2015) similar to Siamese Mask R-CNN Michaelis et al. (2018b). Briefly, it consists of a feature extractor, a matching step and a standard region proposal network and bounding box head (figure 2). The feature extractor (called backbone in object detection) is a standard ResNet-50 with feature pyramid networks He et al. (2016); Lin et al. (2017a) which is applied to the image and reference with weight sharing. In the matching step the reference representation is compared to the image representation in a sliding window approach by computing a feature-wise L1 difference. The resulting similarity encoding representation is concatenated to the image representation and passed on to the region proposal network (RPN). The RPN proposes a set of bounding boxes which potentially contain objects. These boxes are then classified as containing an object from the reference
class or something else (other object or background). Box coordinates are refined by bounding box regression and overlapping boxes are removed using non-maximum suppression.
We additionally developed Siamese RetinaNet, a single-stage detector based on RetinaNet Lin et al. (2017b). The feature extraction and matching steps are identical to Siamese Faster R-CNN, but it uses the unified RetinaHead to jointly propose and classify bounding boxes. To counter the effect of too many negative samples, the classifier is trained with focal loss Lin et al. (2017b).
Training & Evaluation The example-based training is slightly different from the traditional object detection training paradigm. For each image a reference category is randomly chosen by picking a category with at least one instance in the image. A reference is retrieved by randomly selecting one instance from this category in another image and tightly cropping it. The labels for each bounding box are changed to 0 or 1 depending on whether the object is from the reference category or not. Annotations for objects from the held-out categories are removed from the dataset before training. At test time a similar procedure is chosen but instead of picking one category for each image, all categories with at least one object in the image are chosen Michaelis et al. (2018b) and one (1-shot) or five (5-shot) reference images are provided. Predictions are assigned their corresponding category label and evaluation is performed using standard tools and metrics.
Implementation We implemented Siamese Faster R-CNN and Siamese RetinaNet in mmdetection v1.0rc Chen et al. (2019a), which improved performance by more than 30% over the original Siamese Mask R-CNN (Michaelis et al., 2018b, Table 4). We keep all hyperparameters the same as in the standard Faster R-CNN implementation of mmdetection. Due to resource constraints we reduce the number of samples per epoch to 120k for Objects365.
Hyperparameters Our model is derived from mmdetection v1.0rc Chen et al. (2019a) and uses the same hyperparameters as used for Faster R-CNN and RetinaNet1. Please note that the default settings for Pascal VOC differ slightly from those for COCO training. We use the COCO hyperparameters for experiments on COCO, LVIS and Objects365 and Pascal VOC settings for Pascal VOC.
Datasets We use the four datasets shown in Table 1: COCO Lin et al. (2014), Objects365 Shao et al. (2019), LVIS Gupta et al. (2019) and Pascal VOC Everingham et al. (2010). We use standard splits and test on the validation sets except for Pascal VOC where we test on the 2007 test set. Due to resource constraints, we evaluate Objects365 on a fixed subset of 10k images from the validation set.
Category splits Following common protocol for example-based detection Michaelis et al. (2018b); Shaban et al. (2017) we split the categories in each dataset into four splits using every fourth category as hold-out set and the other 3/4 categories for training. So on Pascal VOC there are 15 categories for training in each split, on COCO there are 60, on Objects365 274 and on LVIS 902. We train and test four models (one for each split) and report the mean over those four models, so performance is always measured on all categories. Computing performance in this way across all categories is preferable to using a fixed subset as some categories may be harder than others. During evaluation, the reference images are chosen randomly. We therefore run the evaluation five times, reporting the average AP50 over splits. The 95% confidence intervals for the average AP50 is below ±0.2%AP50 for all experiments.
1All details can be found in the respective configs: https://github.com/open-mmlab/ mmdetection/tree/5bf935e1b7621b234ddb34ef6c32b2b524243995/configs

heading: 4 RESULTS

heading: 4.1 GENERALIZATION GAP ON COCO AND PASCAL VOC

text: We start by showing that objects of held-out categories are detected less reliably on COCO and Pascal VOC. On both datasets, Siamese Faster R-CNN shows strong signs of overfitting to the training categories (figure 4 & Table 2): despite setting a new stat-of-the-art performance is much higher than for categories held-out during training (COCO: 49.7 → 22.8 %AP50; Pascal VOC: 82.7→ 37.6 %AP50). We refer to this drop in performance as the generalization gap. This result is consistent with the literature: Hsieh et al. (2019) – the previous state-of-the-art – report performance dropping 40.9→ 22.0 %AP50 on COCO (see Table 4 below). Some newer models reportedly close the gap on Pascal VOC Zhang et al. (2019); Hsieh et al. (2019); Li et al. (2020); we will discuss Pascal VOC further in the next section. Example predictions show good localization (bounding boxes) even for unknown objects in cluttered scenes while classification errors make up the majority of mistakes (figure 3).

heading: 4.2 PASCAL VOC IS TOO EASY TO EVALUATE ONE-SHOT OBJECT DETECTION MODELS

text:
Having identified this large generalization gap, we ask whether the models have learned a useful metric for one-shot detection at all or whether they rely on simple dataset statistics. Pascal VOC contains, on average, only 1.6 categories and 2.9 instances per image. In this case, simply detecting all foreground objects may be a viable strategy. To test how well such a trivial strategy would perform, we provide the model with uninformative references (we use all-black images). Interestingly, this baseline performs very well, achieving 59.6 %AP50 on training and 33.2 %AP50 on held-out categories (Table 2). For held-out categories, the difference to an example-based search is marginal (33.2 → 37.6 %AP50). This result demonstrates that on Pascal VOC the model mostly follows a shortcut and uses basic dataset statistics to solve the task.
In contrast, COCO represents a drastic increase in image complexity compared with Pascal VOC: it contains, on average, 2.9 categories and 7.3 instances per image. As expected, in this case the trivial baseline with uninformative references performs substantially worse than the example-based search (training: 49.7 → 10.1 %AP50; held-out: 22.8 → 4.4 %AP50; Table 2). Thus, the added image complexity in COCO forces the model to use the reference image for classification but the small set of categories is not sufficient to prevent memorizing the training categories.

heading: 4.3 TRAINING ON MORE CATEGORIES REDUCES THE GENERALIZATION GAP

text:
We now turn to our main hypothesis that increasing the number of categories used during training could close the generalization gap identified above. To this end we use Objects365 and LVIS, two fairly new datasets with 365 and 1203 categories, respectively (much more than the 20/80 in Pascal VOC/COCO). Indeed, training on these wider datasets improves the relative performance on the held-out categories from 46% on COCO to 76% on Objects365 and up to 89% on LVIS (figure 1). In absolute numbers this means going from a 26.9 %AP50 gap on COCO to a 4.6 %AP50 gap on Objects365 and a 3.5 %AP50 gap on LVIS (Table 3) in the one-shot setting. Increasing the number of references to five (5-shot) improves performance on all datasets but leaves relative performance unchanged (Table 3, right columns).
This effect is not caused simply by differences between the datasets, as the following experiment shows: For both datasets (LVIS and Objects365), we train models on progressively more categories. When training on less than 100 categories (resembling training on COCO), a clear generalization gap is visible on both LVIS and Objects365 (figure 5A: leftmost data points). Increasing the number of training categories leads to better performance on the held-out categories, while performance on the training categories stays the same (LVIS) or decreases (Objects365). The effect is the same in the 5-shot setting but with a better baseline performance (figure A.1 in Appendix).

heading: 4.4 THE NUMBER OF CATEGORIES IS THE CRUCIAL FACTOR

text:
The results so far show that increasing the number of categories used during training reduces the generalization gap and improves performance. However, this effect could also be caused by the fact that with more categories there is also more data available. Consider the situation where we train on 10% of the categories (90 in the case of LVIS). As we sample these categories uniformly from the dataset, we use only approximately 10% of the total number of instances. To control for this confound, we created training sets that match the number of instances: in this case we use only 10% of the instances in the dataset but sample them uniformly from all 900 training categories.
The results can be seen in figure 5B. Our example from above with 10% of the data corresponds to the leftmost datapoint in both plots. The model trained with more categories (green) clearly outperforms the model with more instances per category (blue). The same performance gap can be seen for any fraction of the data. Thus, for a given budget of instances (labels) it is better to cover more categories than to collect as many samples per category as possible.

heading: 4.5 ONCE THE GENERALIZATION GAP IS CLOSED MORE POWERFUL MODELS BENEFIT NOVEL CATEGORIES

text:
If models indeed learn the distribution over categories, stronger models that can learn more powerful representations should perform better on known and novel categories alike. We test this hypothesis in two ways: first, by replacing the standard ResNet-50 He et al. (2016) backbone with a more expressive ResNeXt-101 Xie et al. (2017); second, by using a three times longer training schedule.
The larger backbone does not improve performance on the held-out categories on COCO (Table 3). Instead the additional capacity is used to memorize the training categories, which is evident from the large improvement (6.7%AP50) in performance on the training categories, but only a small improvement (0.7%AP50) on the held-out categories. In contrast, on LVIS and Objects365 the gains of the bigger backbone are not confined to the training categories but apply to the one-shot setting as well. Only a small difference remains on Objects365 (3.0%AP50 vs. 1.4%AP50).
Longer training schedules show the same pattern. For COCO, performance on the training categories improves while performance on held-out categories even gets a bit worse on a 3x schedule (Table 3). In contrast, performance on LVIS and Objects365 improves for both training and held-out categories alike, suggesting that the models do not overfit only the training categories.

heading: 4.6 RESULTS HOLD FOR DIFFERENT MODEL CONFIGURATIONS

text:
To test if our findings apply to single-stage detectors as well, we train and test Siamese RetinaNet on COCO, LVIS and Objects365 (Table 3). Results are very similar to Siamese Faster R-CNN. Siamese RetinaNet shows a slightly larger generalization gap on COCO (relative performance: Retina: 37%
vs. FRCNN: 46%) but results are very similar on LVIS (Retina: 87% vs. FRCNN: 89%) and Objects365 (Retina: 74% vs. FRCNN: 76%).
Taken together we observe the same patterns for single- and two-stage detectors with different backbones and learning rate schedules on two datasets (Objects365 and LVIS) for 1-shot and 5-shot evaluation. This suggests that our conclusions may extend to most object detection models and we can expect to significantly boost performance using the large toolboxes which exist for traditional object detection.

heading: 4.7 STATE-OF-THE-ART ON COCO USING LVIS

text: Using the insights from above, we now demonstrate state-of-the-art one-shot detection performance on COCO by training on a large number of categories. We use LVIS and create four splits which leave out all categories that have a correspondence in the respective COCO split. As LVIS is a re-annotation of COCO, this means that we expand the categories in the training set while training on the same set of images. Training with the more diverse LVIS annotations leads to a noticeable performance improvement from 22.8 to 25.0%AP50, which can be improved even further to 27.4%AP50 by using the stronger ResNeXt-101 backbone, outperforming the previous best model by 5.4%AP50 (Table 4). In relative terms that means going from 45% relative performance to 65%, thus substantially outperforming the previous best method (55% relative performance Hsieh et al. (2019)) both in absolute and relative terms. Visual inspection of the results (figure 6) shows cleaner predictions with less false positives especially for difficult reference images.

heading: 5 DISCUSSION

text:
It has long been assumed and recently shown (Sbai et al., 2020; Jiang et al., 2020; Fan et al., 2020) that training with more categories improves few-shot learning performance. However the question whether this is due to better overall model performance or better generalization has not been answered so far. Our results show that the underlying mechanism is an improvement in generalization from 45% relative performance on COCO to 89% on LVIS. The effect is consistent for different detectors, backbone architectures and training schedules which suggests that the effect will hold for almost any model. If this trend continues with more categories object detection that generalizes to any object is within reach. This, however, does not mean that one-shot object detection is “solved”. There are at least three important steps to take:
First and foremost the performance of example-based object detectors has to improve significantly. Our experiments outline a path forward, demonstrating that methods that profit general object detection transfer to novel categories when the generalization gap is closed. Secondly, we have to better understand the mechanisms that lead to the generalization gap. Our results indicate that one of the main reasons is a shortcut Geirhos et al. (2020) - memorizing the training categories. That stronger models also perform better on novel categories with progressive closing of the gap is an indicator that the key issue was indeed overfitting. However more investigation will be required to determine which factors are important. Is it the sheer number of categories or is it their diversity, granularity, frequency? Or is the main factor semantic relationship as results from Sbai et al. (2020) and Jiang et al. (2020) suggest? Finally we have to find a way to transfer this success to smaller datasets with less categories. While we achieve a new state-of-the-art on COCO the generalization gap there (69%) is still larger than on LVIS (89%).

heading: 5.1 FUTURE DATASETS SHOULD FOCUS ON THE DIVERSITY OF CATEGORIES.

text:
Our findings have important implications for the design of future datasets. For the goal of generalization a broader range of categories is helpful at any dataset size (figure 5B: green curve above blue curve at any data fraction), while from a certain point onward more examples per category lead to diminishing returns (figure 5B: green curve flattens out). At a time where few-shot and long-tail problems become more important in computer vision this suggest that future data collection and annotation efforts should focus more on a broad set of categories and less on the number of instances for each of those categories.
An open question is, how broad datasets have to be. Despite being a big step forward, training on LVIS still leaves a small generalization gap that widens when using stronger models. In other words: some amount of overfitting on the training categories remains. The good news is that we don’t see a saturation (figure 5B: dark blue curves still rise at the maximum number of categories) so further increasing the number of categories should reduce the remaining gap.

heading: 5.2 THE BIGGER PICTURE

text: Our insight that applying existing methods on larger and more diverse datasets can lead to unexpected capabilities is mirrored in other areas. This phenomenon has been observed time and again and was termed the “unreasonable effectiveness of data” Halevy et al. (2009); Sun et al. (2017) or the “bitter lesson” Sutton (2019). It played a key role in the breakthrough of DNNs thanks to ImageNet Russakovsky et al. (2015); Krizhevsky et al. (2012) as well as recent results on gameplay Berner et al. (2019) or language modelling Brown et al. (2020). Recently Kolesnikov et al. (2019) and Radford et al. (2021) achieve impressive results demonstrating strong performance at one-shot and zero-shot ImageNet classification. As in our study, simple methods (transfer learning in Kolesnikov et al. (2019) and unsupervised image captioning in Radford et al. (2021)) on large and diverse datasets led to results that are far better than what one would have expected: Achieving ResNet performance with 10 Kolesnikov et al. (2019) respectively zero Radford et al. (2021) annotated samples per class in their case; 89% relative performance on LVIS in our case. We hope that by building on this insight we can soon move from trying to solve few-shot learning towards using few-shot learning to solve other problems.

heading: A APPENDIX

text:
A.1 ADDITIONAL FEW-SHOT RESULTS
We provide five-shot results for the experiments in figure 5 in figure A.1.