summaries: This paper proposes a new approach for continual learning that actively forgets the old knowledge when learning the new tasks. The approach uses Bayesian continual learning with synaptic expansion-convergence for active forgetting. The paper evaluates the new method on several continual learning benchmarks, including CIFAR10 regression, visual classification, and Atari reinforcement tasks.

summaries: This paper investigates how to avoid negative transfer in Bayesian continual learning setting. The main contribution is the proposition of an active forgetting mechanisms inspired by biological neural networks for mitigating negative transfer in CL. The experiments on CL benchmarks have been conducted to validate the performances of the proposed method.

summaries: The paper proposed a continual learning method that attempts to promote better forward transfer among similar tasks. Towards this, the authors attempt to suppress the negative knowledge, the knowledge that impedes learning a new task, from the previous task while learning a new task. This is done by forgetting such knowledge from the previous task without increasing the forgetting catastrophically. The authors claim that such “active forgetting” is biologically inspired. Similar to the Elastic Weight Consolidation (EWC), the authors derive the learning objective, by applying the laplace approximation to the posterior of a new task. The only difference is that the posterior of the previous task is replaced by a weighted product distribution, where a weight of ‘\beta’ is introduced to capture active forgetting. This change allowed them to derive a new regularization penalty whereby a separate model is trained for a new task and then subsequently merged with that of the previous one. It is in this merging that the negative knowledge of the previous task is eliminated. Experimentally, the authors show strong performance on regression, classification and RL tasks. The authors further show that their method can be added to other regularization- and memory-based methods to improve their performance.

summaries: This paper proposes a method for continual learning that aims to mitigate the problem of catastrophic forgetting by actively forgetting knowledge from previous tasks. The authors use a Bayesian continual learning framework to design their method. AFEC relies on identifying a set of expanded network parameters which are specific to the new task. The method incorporates a term in the loss function that considers the merge between these parameters and the network parameters being updated for the current task, therefore encouraging active forgetting. Catastrophic forgetting is also controlled by including a term that merges between parameters for old tasks and network parameters for the current task (i.e. the EWC term). Experimental results are reported for datasets on regression, classification and reinforcement learning tasks. These results show some advantages of the method in particular in the forward transfer setting.

abstractText: Continual learning aims to learn a sequence of tasks from dynamic data distributions. Without accessing to the old training samples, knowledge transfer from the old tasks to each new task is difficult to determine, which might be either positive or negative. If the old knowledge interferes with the learning of a new task, i.e., the forward knowledge transfer is negative, then precisely remembering the old tasks will further aggravate the interference, thus decreasing the performance of continual learning. By contrast, biological neural networks can actively forget the old knowledge that conflicts with the learning of a new experience, through regulating the learning-triggered synaptic expansion and synaptic convergence. Inspired by the biological active forgetting, we propose to actively forget the old knowledge that limits the learning of new tasks to benefit continual learning. Under the framework of Bayesian continual learning, we develop a novel approach named Active Forgetting with synaptic Expansion-Convergence (AFEC). Our method dynamically expands parameters to learn each new task and then selectively combines them, which is formally consistent with the underlying mechanism of biological active forgetting. We extensively evaluate AFEC on a variety of continual learning benchmarks, including CIFAR-10 regression tasks, visual classification tasks and Atari reinforcement tasks, where AFEC effectively improves the learning of new tasks and achieves the state-of-the-art performance in a plug-and-play way.

authors:
Rahaf Aljundi
Francesca Babiloni
Mohamed Elhoseiny
Marcus Rohrbach
Tinne Tuytelaars

title: Memory aware synapses: Learning what (not) to forget

venue: In Proceedings of the European Conference on Computer Vision (ECCV),

authors:
Arslan Chaudhry
Puneet K Dokania
Thalaiyasingam Ajanthan
Philip HS Torr

title: Riemannian walk for incremental learning: Understanding forgetting and intransigence

authors:
Xinyang Chen
Sinan Wang
Bo Fu
Mingsheng Long
Jianmin Wang

title: Catastrophic forgetting meets negative transfer: Batch spectral shrinkage for safe transfer learning

venue: In Advances in Neural Information Processing Systems,

authors:
Natalia Díaz-Rodríguez
Vincenzo Lomonaco
David Filliat
Davide Maltoni

title: Don’t forget, there is more than forgetting: new metrics for continual learning

venue: arXiv preprint arXiv:1810.13166,

authors:
Tao Dong
Jing He
Shiqing Wang
Lianzhang Wang
Yuqi Cheng
Yi Zhong

title: Inability to activate rac1-dependent forgetting contributes to behavioral inflexibility in mutants of multiple autism-risk genes

venue: Proceedings of the National Academy of Sciences,

authors:
Arthur Douillard
Matthieu Cord
Charles Ollion
Thomas Robert
Eduardo Valle

title: Podnet: Pooled outputs distillation for small-tasks incremental learning

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

title: Training products of experts by minimizing contrastive divergence

venue: Neural Computation,

authors:
Saihui Hou
Xinyu Pan
Chen Change Loy
Zilei Wang
Dahua Lin

title: Learning a unified classifier incrementally via rebalancing

authors:
Sangwon Jung
Hongjoon Ahn
Sungmin Cha
Taesup Moon

title: Continual learning with node-importance based adaptive group sparse regularization

title: Fundamentals of statistical signal processing

venue: Prentice Hall PTR,

authors:
James Kirkpatrick
Razvan Pascanu
Neil Rabinowitz
Joel Veness
Guillaume Desjardins
Andrei A Rusu
Kieran Milan
John Quan
Tiago Ramalho
Agnieszka Grabska-Barwinska

title: Overcoming catastrophic forgetting in neural networks

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks

title: The mnist database of handwritten digits. http://yann

venue: lecun. com/exdb/mnist/,

authors:
Yaoyao Liu
Bernt Schiele
Qianru Sun

title: Meta-aggregating networks for class-incremental learning

venue: arXiv preprint arXiv:2010.05063,

title: Gradient episodic memory for continual learning

authors:
Michael McCloskey
Neal J Cohen

title: Catastrophic interference in connectionist networks: The sequential learning problem

venue: In Psychology of Learning and Motivation,

authors:
Cuong V Nguyen
Yingzhen Li
Thang D Bui
Richard E Turner

title: Variational continual learning

venue: arXiv preprint arXiv:1710.10628,

authors:
Sylvestre-Alvise Rebuffi
Alexander Kolesnikov
Georg Sperl
Christoph H Lampert

title: icarl: Incremental classifier and representation learning

authors:
Matthew Riemer
Ignacio Cases
Robert Ajemian
Miao Liu
Irina Rish
Yuhai Tu
Gerald Tesauro

title: Learning to learn without forgetting by maximizing transfer and minimizing interference

authors:
Olga Russakovsky
Jia Deng
Hao Su
Jonathan Krause
Sanjeev Satheesh
Sean Ma
Zhiheng Huang
Andrej Karpathy
Aditya Khosla
Michael Bernstein

title: Imagenet large scale visual recognition challenge

venue: International Journal of Computer Vision,

authors:
John Schulman
Filip Wolski
Prafulla Dhariwal
Alec Radford
Oleg Klimov

title: Proximal policy optimization algorithms

venue: arXiv preprint arXiv:1707.06347,

authors:
Jonathan Schwarz
Wojciech Czarnecki
Jelena Luketina
Agnieszka Grabska-Barwinska
Yee Whye Teh
Razvan Pascanu
Raia Hadsell

title: Progress & compress: A scalable framework for continual learning

venue: In Proceedings of International Conference on Machine Learning,

authors:
Ramprasaath R Selvaraju
Michael Cogswell
Abhishek Das
Ramakrishna Vedantam
Devi Parikh
Dhruv Batra

title: Grad-cam: Visual explanations from deep networks via gradientbased localization

authors:
Hanul Shin
Jung Kwon Lee
Jaehong Kim
Jiwon Kim

title: Continual learning with deep generative replay

authors:
Yichun Shuai
Binyan Lu
Ying Hu
Lianzhang Wang
Kan Sun
Yi Zhong

title: Forgetting is regulated through rac activity in drosophila

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: arXiv preprint arXiv:1409.1556,

authors:
Shipeng Wang
Xiaorong Li
Jian Sun
Zongben Xu

title: Training networks in null space of covariance for continual learning

venue: arXiv preprint arXiv:2103.07113,

authors:
Shipeng Yan
Jiangwei Xie
Xuming He

title: Der: Dynamically expandable representation for class incremental learning

venue: arXiv preprint arXiv:2103.16788,

authors:
Jaehong Yoon
Saehoon Kim
Eunho Yang
Sung Ju Hwang

title: Scalable and order-robust continual learning with additive parameter decomposition

authors:
Friedemann Zenke
Ben Poole
Surya Ganguli

title: Continual learning through synaptic intelligence

heading: 1 Introduction

text:
The ability to continually learn numerous tasks from dynamic data distributions is critical for deep neural networks, which needs to remember the old tasks by avoiding catastrophic forgetting [18] while effectively learn each new task by improving forward knowledge transfer [17]. Due to the dynamic data distributions, forward knowledge transfer might be either positive or negative, and is difficult to determine without accessing to the old training samples. If the forward knowledge transfer is negative, i.e., learning a new task from the old knowledge is worse than learning the new task on a randomly-initialized network [36, 17], then precisely remembering the old tasks will severely interfere with the learning of the new task, thus decreasing the performance of continual learning.
⇤Corresponding author: J. Zhu and Y. Zhong.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
By contrast, biological neural networks can effectively learn a new experience on the basis of remembering the old experiences, even if they conflict with each other [18, 5]. This advantage, called memory flexibility, is achieved by active forgetting of the old knowledge that interferes with the learning of a new experience [29, 5]. The latest data suggested that the underlying mechanism of biological active forgetting is to regulate the learning-triggered synaptic expansion and synaptic convergence (Fig. 1, see Appendix A for neuroscience background and our biological data). Specifically, the biological synapses expand additional functional connections to learn a new experience together with the previously-learned functional connections (synaptic expansion). Then, all the functional connections are pruned to the amount before learning (synaptic convergence).
Inspired by the biological active forgetting, we propose to actively forget the old knowledge that interferes with the learning of new tasks without significantly increasing catastrophic forgetting, so as to benefit continual learning. Specifically, we adopt Bayesian continual learning and actively forget the posterior distribution that absorbs all the information of the old tasks with a forgetting
factor to better learn each new task. Then, we derive a novel method named Active Forgetting with synaptic Expansion-Convergence (AFEC), which is formally consistent with the underlying mechanism of biological active forgetting at synaptic structures. Beyond regular weight regularization approaches [12, 1, 35, 2], which selectively penalize changes of the important parameters for the old tasks, AFEC dynamically expands parameters only for each new task to avoid potential negative transfer from the main network, while the forgetting factor regulates a penalty to selectively merge the main network parameters with the expanded parameters, so as to learn a better overall representation of both the old tasks and the new task.
We extensively evaluate AFEC on continual learning of CIFAR-10 regression tasks, a variety of visual classification tasks, and Atari reinforcement tasks [10], where AFEC achieves the state-of-theart (SOTA) performance. We empirically validate that the performance improvement results from effectively improving the learning of new tasks without increasing catastrophic forgetting. Further, AFEC can be a plug-and-play method that significantly boosts the performance of representative continual learning strategies, such as weight regularization [12, 1, 35, 2] and memory replay [21, 9, 6].
Our contributions include: (1) We draw inspirations from the biological active forgetting and propose a novel approach to actively forget the old knowledge that interferes with the learning of new tasks for continual learning; (2) Extensive evaluation on a variety of continual learning benchmarks shows that our method effectively improves the learning of new tasks and achieves the SOTA performance in a plug-and-play way; and (3) To the best of our knowledge, we are the first to model the biological active forgetting and its underlying mechanism at synaptic structures, which suggests a potential theoretical explanation of how the underlying mechanism of biological active forgetting achieves its function of forgetting the past and continually learning conflicting experiences [29, 5].

heading: 2 Related Work

text:
Continual learning needs to minimize catastrophic forgetting and maximize forward knowledge transfer. Existing work in continual learning mainly focuses on mitigating catastrophic forgetting. Representative approaches include: weight regularization [12, 1, 35, 2], which selectively penalizes changes of the previously-learned parameters; parameter isolation [24, 10], which allocates a dedicated parameter subspace for each task; and memory replay [21, 28, 9], which approximates and recovers the old data distributions through storing old training data, their embedding or learning a generative model. In particular, Adaptive Group Sparsity based Continual Learning (AGS-CL) [10] proposed to regularize the group sparsity with separation of the important nodes for the old tasks to prevent catastrophic forgetting, which takes advantages of weight regularization and parameter isolation, and achieved the SOTA performance on various continual learning benchmarks.
Several studies suggested that forward knowledge transfer is critical for continual learning [17, 4], which might be either positive or negative due to the dynamic data distributions. Although it is highly nontrivial to mitigate potential negative transfer while overcoming catastrophic forgetting, the efforts that specifically consider this challenging issue are limited. [3] developed a method to mitigate negative transfer when fine-tuning tasks on a pretrained network. For the scenario where the old tasks can be learned again, [26] learned an additional active column to better exploit potential positive transfer. [22] tried to maximize transfer and minimize interference from a memory buffer containing a few old training data. Similarly, [6, 16, 33] attempted to more effectively balance stability and plasticity with the memory buffer in class incremental learning, while [32] stored and updated the old features. By contrast, since pretraining or old training data might not be available in continual learning, we mainly focus on a more restrict yet realistic setting that a neural network incrementally learns a sequence of tasks from scratch, without storing old training data. Further, we extend our method to the scenarios where pretraining or memory buffer can be used, as well as the scenarios other than classification tasks, such as regression tasks and reinforcement tasks.

heading: 3 Method

text: In this section, we first describe the framework of Bayesian continual learning [12, 20]. Under such framework, we propose an active forgetting strategy, which is formally consistent with the underling mechanism of biological active forgetting at synaptic structures.

heading: 3.1 Basics of Bayesian Continual Learning

text:
Continual learning needs to remember the old tasks and learn each new task effectively. Let’s consider a simple case that a neural network with parameter ✓ continually learns two independent tasks, task A and task B, from their training datasets DtrainA and D train B [12]. The training dataset of each task is only available when learning the task.
Bayesian Learning: After learning DtrainA , the posterior distribution
p(✓|DtrainA ) = p(DtrainA |✓)p(✓)
p(DtrainA )
incorporates the knowledge of task A. Then, we can get the predictive distribution for the test data of task A:
p(DtestA |DtrainA ) = Z p(DtestA |✓)p(✓|DtrainA )d✓.
As the posterior p(✓|DtrainA ) is generally intractable (except very special cases), we must resort to approximation methods, such as the Laplace approximation [12] or other approaches of approximate inference [20]. Let’s take Laplace approximation as an example. If p(✓|DtrainA ) is smooth and majorly peaked around the mode ✓⇤A = argmax✓ log p(✓|DtrainA ), we can approximate it with a Gaussian distribution whose mean is ✓⇤A and covariance is the inverse Hessian of the negative log posterior (detailed in Appendix B.1).
Bayesian Continual Learning: Next, we want to incorporate the new task into the posterior, which uses the posterior p(✓|DtrainA ) as the prior of the next task [12]:
p(✓|DtrainA , DtrainB ) = p(DtrainB |✓) p(✓|DtrainA )
p(DtrainB ) . (1)
Then we can test the performance of continual learning by evaluating
p(DtestA , D test B |DtrainA , DtrainB ) = Z p(DtestA , D test B |✓)p(✓|DtrainA , DtrainB )d✓. (2)
Similarly, p(✓|DtrainA , DtrainB ) can be approximated by a Gaussian using Laplace approximation whose mean is the mode of the posterior:
✓⇤A,B = argmax ✓ log p(✓|DtrainA , DtrainB ) (3)
= argmax ✓ log p(DtrainB |✓) + log p(✓|DtrainA ) log p(DtrainB )| {z } const. . (4)
This MAP estimation is also known as the Elastic Weight Consolidation (EWC) [12]:
LEWC(✓) = LB(✓) +
2
X
i
FA,i(✓i ✓⇤A,i)2, (5)
where LB(✓) is the loss for task B and i is the label of each parameter. FA is the Fisher Information matrix (FIM) of ✓⇤A on D train A (the computation is detailed in Appendix B.1), which indicates the “importance” of parameter i for task A. The hyperparameter explicitly controls the penalty that selectively merges each ✓i to ✓⇤A,i to alleviate catastrophic forgetting.

heading: 3.2 Active Forgetting with Synaptic Expansion-Convergence

text:
However, if precisely remembering task A interferes with the learning of task B, e.g., task A and task B are too different, it might be useful to actively forget the original data, similar to the biological strategy of active forgetting. Based on this inspiration, we introduce a forgetting factor and replace p(✓|DtrainA ) that absorbs all the information of DtrainA with a weighted product distribution [8, 19]:
pm(✓|DtrainA , ) = p(✓|DtrainA )(1 )p(✓)
Z , (6)
where we use m to denote that we are ‘mixing’ p(✓|DtrainA ) and p(✓) to produce the new distribution pm. Z is the normalizer that depends on , which keeps pm(✓|DtrainA , ) following a Gaussian distribution if p(✓|DtrainA ) and p(✓) are both Gaussian (detailed in Appendix B.2). When ! 0, pm will be dominated by p(✓|DtrainA ) and remember all the information about task A. When ! 1, pm will actively forget all the information about task A. Modified from Eqn. (2), our target becomes:
p(DtestA , D test B |DtrainA , DtrainB , ) = Z p(DtestA , D test B |✓)p(✓|DtrainA , DtrainB , )d✓. (7)
We first need to determine , which decides how much information from task A is forgotten to maximize the probability of learning task B well. A good should be as follows:
⇤ = argmax p(DtrainB |DtrainA , ) = argmax Z p(DtrainB |✓)pm(✓|DtrainA , )d✓. (8)
Since the integral is difficult to solve, we can make a grid search to determine , which should be between 0 and 1. Next, p(✓|DtrainA , DtrainB , ) can also be approximated by a Gaussian using Laplace approximation (the proof is detailed in Appendix B.3), and the MAP estimation is
✓⇤A,B = argmax ✓ log p(✓|DtrainA , DtrainB , )
= argmax ✓
(1 ) (log p(DtrainB |✓) + log p(✓|DtrainA )) + log p(✓|DtrainB ) + const.. (9)
Then we obtain the loss function of Active Forgetting with synaptic Expansion-Convergence (AFEC):
LAFEC(✓) =LB(✓) +
2
X
i
FA,i(✓i ✓⇤A,i)2 + e 2
X
i
Fe,i(✓i ✓⇤e,i)2. (10)
✓⇤e are the optimal parameters for the new task and Fe is the FIM of ✓⇤e (the computation is detailed in Appendix B.1). As shown in Fig. 2, we first learn a set of expanded parameters ✓e with LB(✓e) to obtain ✓⇤e and Fe. Then we can optimize Eqn. (10), where two weight-merging regularizers selectively merge ✓i with ✓⇤A,i for the old tasks and ✓ ⇤ e,i for the new task. The forgetting factor is integrated into a hyperparameter e / /(1 ) to control the penalty that promotes active forgetting. Therefore, derived from active forgetting of the original posterior in Eqn. (6), we obtain an algorithm that dynamically expands parameters to learn a new task and then selectively converges the expanded parameters to the main network. Intriguingly, this algorithm is formally consistent with the underlying mechanism of biological active forgetting (the neuroscience evidence is detailed in Appendix A), which also expands additional functional connections for a new experience (synaptic expansion) and then prunes them to the amount before learning (synaptic convergence).
As the proposed active forgetting is integrated into the third term, our method can be used in a plug-and-play way to improve continual learning (detailed in Appendix E, F). Here we use Laplace approximation to approximate the intractable posteriors, which can be other strategies of approximate inference [20] in further work. Note that ✓⇤e and Fe are not stored in continual learning, and the architecture of the main network is fixed. Thus, AFEC does not cause additional storage cost compared with regular weight regularization approaches such as [12, 35, 1, 2]. Further, it is straightforward to extend our method to continual learning of more than two tasks. We discuss it in Appendix B.4 with a pseudocode.
Now we conceptually analyze how AFEC mitigates potential negative transfer in continual learning (see Fig. 2). When learning task B on the basis of task A, regular weight regularization approaches [12, 35, 1, 2] selectively penalize changes of the old
parameters learned for task A, which will severely interfere with the learning of task B if they conflict with each other. In contrast, AFEC learns a set of expanded parameters only for task B to avoid potential negative transfer from task A. Then, the main network parameters selectively merge with both the old parameters and the expanded parameters, depending on their contributions to the overall representations of task A and task B.

heading: 4 Experiment

text: In this section, we evaluate AFEC on a variety of continual learning benchmarks, including: CIFAR10 regression tasks, which is a toy experiment to validate our idea about negative transfer in continual learning; visual classification tasks, where the forward knowledge transfer might be either positive or negative; and Atari reinforcement tasks, where the forward knowledge transfer is severely negative. All the experiments are averaged by 5 runs with different random seeds and task orders.

heading: 4.1 CIFAR-10 Regression Tasks

text:
First, we propose CIFAR-10 regression tasks to explicitly show how negative transfer affects continual learning, and how AFEC effectively addresses this challenging issue. CIFAR-10 dataset [13] contains 50,000 training samples and 10,000 testing samples of 10-class colored images of size 32⇥ 32. The regression task is to evenly map the ten classes around the origin of the two-dimensional coordinates and train the neural network to predict the angle of the origin to each class (see Fig. 3). We change the relative position of the ten classes to construct different regres-
sion tasks with mutual negative transfer, in which remembering the old knowledge will severely interfere with the learning of a new task.
As shown in Fig. 4 for continual learning of two different regression tasks, regular weight regularization approaches, such as MAS [1] and EWC [12], can effectively remember the old tasks, but limits the learning of new tasks. In particular, larger strength of the weight regularization results in better performance of the
first task but worse performance of the second task. In contrast, AFEC improves the learning of new tasks on the basis of remembering the old tasks, so as to achieve better averaged accuracy. Note that EWC is equal to the ablation of active forgetting in AFEC, i.e., = 0, so the performance improvement of AFEC on EWC validates the effectiveness of our proposal. We further demonstrate the efficacy of AFEC on a variety of architectures and a larger amount of tasks (see Table 1).
In addition, we evaluate the ability of transfer learning after continual learning of two different regression tasks. We fix the feature extractor of the neural network and only fine-tune a linear classifier to predict a new task that is similar to the first task. Specifically, the similar task applies the same relative position as the first task, but rotates by 60 , 120 , 180 , 240 or 300 . Therefore, if the neural network effectively remembers and transfers the relative position learned in the first task, it will be able to learn the similar task well. As shown in Table 1, AFEC can more effectively learn the similar task, while EWC is even worse than sequentially fine-tuning without weight regularization.

heading: 4.2 Visual Classification Tasks

text:
Dataset: We evaluate continual learning on a variety of benchmark datasets for visual classification, including CIFAR-100, CUB-200-2011 and ImageNet-100. CIFAR-100 [13] contains 100-class colored images of the size 32⇥ 32, where each class includes 500 training samples and 100 testing samples. CUB-200-2011 [31] is a large-scale dataset including 200 classes and 11,788 colored images of birds, split as 30 images per class for training while the rest for testing. ImageNet-100 [9] is a subset of iILSVRC-2012 [23], consisting of randomly selected 100 classes of images and 1300 samples per class. We follow the regular preprocessing pipeline of CUB-200-2011 and ImageNet-100 as [10], which randomly resizes and crops the images to the size of 224⇥ 224 before experiment. Benchmark: We consider five representative benchmarks of visual classification tasks to evaluate continual learning in different aspects. The first three are on CIFAR-100, with forward knowledge transfer from more negative to more positive (detailed in Fig. 5), while the second two are on largescale images. (1) CIFAR-100-SC [34]: CIFAR-100 can be split as 20 superclasses (SC) with 5 classes per superclass dependent on semantic similarity, where each superclass is a classification task. Since the superclasses are semantically different, forward knowledge transfer in such a task sequence is
relatively more negative. (2) CIFAR-100 [21]: The 100 classes in CIFAR-100 are randomly split as 20 classification tasks with 5 classes per task. (3) CIFAR-10/100 [10]: The 10-class CIFAR-10 are randomly split as 2 classification tasks with 5 classes per task, followed by 20 tasks with 5 classes per task randomly split from CIFAR-100. This benchmark is adapted from [10] to keep the number of classes per task the same as benchmark (1, 2), where the large amounts of training data in the first two CIFAR-10 tasks bring a relatively more positive transfer. (4) CUB-200 [10]: The 200 classes in CUB-200-2011 are randomly split as 10 classification tasks with 20 classes per task. (5) ImageNet-100 [21]: The 100 classes in ImageNet-100 are randomly split as 10 classification tasks with 10 classes per task.
Architecture: We follow [10] to use a CNN architecture with 6 convolution layers and 2 fully connected layers for benchmark (1, 2, 3), and AlexNet [14] for benchmark (4, 5). Since continual learning needs to quickly learn a usable model from incrementally collected data, we mainly consider learning the network from scratch. Following [10], we also try AlexNet with ImageNet pretraining for CUB-200.
Baseline: First, we consider a restrict yet realistic setting of continual learning without access to the old training data, and perform multi-head evaluation [2]. Since AFEC is a weight regularization approach, we mainly compare with representative approaches that follow a similar idea, such as EWC [12], MAS [1], SI [35] and RWALK [2]. We also compare with AGS-CL [10], the SOTA method that takes advantage of weight regularization and parameter isolation, and P&C [26], which learns an additional active column on the basis of EWC to improve forward knowledge transfer. We reproduce the results of all the baselines from the officially released code of [10], where we do an extensive hyperparameter search and report the best performance for fair comparison (detailed in Appendix C). Then, we relax the restriction of using old training data and plug AFEC in representative memory replay approaches, where we perform single-head evaluation [2] (detailed in Appendix F).
Averaged Accuracy: In Table 2, we summarize the averaged accuracy of all the tasks learned so far during continual learning of visual classification tasks. AFEC achieves the best performance on all the continual learning benchmarks and is much better than EWC [12], i.e., the ablation of active forgetting in AFEC. In particular, AGS-CL [10] is the SOTA method on relatively small-scale images and on CUB-200 with ImageNet pretraining (CUB-200 w/ PT). While, AFEC achieves a better performance than AGS-CL on small-scale images from scratch and CUB-200 w/ PT, and substantially outperforms AGS-CL on the two benchmarks of large-scale images from scratch. Further, since regular weight regularization approaches are generally in a re-weighted weight decay form, AFEC can be easily adapted to such approaches (the adaptation is detailed in Appendix E) and effectively boost their performance on the benchmarks above.
Knowledge Transfer: Next, we evaluate knowledge transfer in the three continual learning benchmarks developed on CIFAR-100 in Fig. 5. We first present the accuracy of learning each new task
in continual learning, where AFEC learns each new task much better than other baselines. Since continual learning of more tasks leads to less network resources for a new task, the overall trend of all the baselines is declining, indicating the necessity to improve forward knowledge transfer on the basis of overcoming catastrophic forgetting. Then we calculate forward transfer (FWT) [17], i.e., the averaged influence that learning the previous tasks has on a future task, and backward transfer (BWT) [17], i.e., the averaged influence that learning a new task has on the previous tasks (detailed in Appendix D). FWT is from more negative to more positive in CIFAR-100-SC, CIFAR-100 and CIFAR-10/100, while AFEC achieves the highest FWT among all the baselines. The BWT of AFEC is comparable as EWC, indicating that the proposed active forgetting does not cause additional catastrophic forgetting. Therefore, the performance improvement of AFEC in Table 2 is achieved by effectively improving the learning of new tasks in continual learning. In particular, AFEC achieves a much larger improvement on the learning of new tasks than P&C, which attempted to improve forward transfer of EWC through learning an additional active column. Due to the progressive
parameter isolation, although AGS-CL achieves the best BWT, its ability of learning each new task drops more rapidly than other baselines. Thus, it underperforms AFEC in Table 2.
Visual Explanation: To explicitly show how AFEC improves continual learning, in Fig. 6 we use Grad-CAM [27] to visualize predictions of the latest task after continual learning on CIFAR-100-SC, where FWT is more negative as discussed above. The predictions of EWC overfit the background information since it attempts to best remember the old tasks with severe negative transfer, which limits the learning of new tasks. In contrast, the visual explanation of AFEC is much more reasonable than EWC, indicating the efficacy of active forgetting to address potential negative transfer and benefit the learning of new tasks.
Plugging-in Memory Replay: We further implement AFEC in representative memory replay approaches in Appendix F, where we perform single-head evaluation [2]. On CIFAR-100 and ImageNet100 datasets, we follow [9, 6] that first learn 50 classes and then continually learn the other 50 classes by 5 phases (10 classes per phase) or 10 phases (5 classes per phase), using a small memory buffer of 20 images per class. AFEC substantially boosts the performance of representative memory replay approaches such as iCaRL [21], LUCIR [9] and PODNet [6].

heading: 4.3 Atari Reinforcement Tasks

text:
Next, we evaluate AFEC in continual learning of Atari reinforcement tasks (Atari games). We follow the implementation of [10] to sequentially learn eight randomly selected Atari games. Specifically, we applies a CNN architecture consisting of 3 convolution layers with 2 fully connected layers and identical PPO [25] for all the methods (detailed in Appendix G). The evaluation metric is the normalized accumulated reward: the evaluated rewards are normalized with the maximum reward of fine-tuning on each task, and accumulated. We present the results of three different orders of task sequence, averaged by five runs with different random initialization.
For continual learning of Atari reinforcement tasks, forward knowledge transfer is severely negative, possibly because the optimal policies of each Atari games are highly different. We first measure the normalized rewards of learning each task with a randomly initialized network, which are 2.16, 1.44 and 1.68 on the three task sequences,
respectively. That is to say, the initialization learned from the old tasks results in an averaged performance decline by 53.67%, 30.66% and 40.56%, compared with random initialization. Then, we evaluate the maximum reward of learning each new task in Table 3, and the normalized accumulated reward of continual learning in Fig. 7. AFEC effectively improves the learning of new tasks and thus boosts the performance of EWC and MAS, particularly when learning more incremental tasks. AFEC also achieves a much better performance than the reproduced results of AGS-CL on its officially released code [10] (see Appendix G for an extensive analysis).

heading: 5 Conclusion

text:
In this work, we draw inspirations from the biological active forgetting and propose a novel approach to mitigate potential negative transfer in continual learning. Our method achieves the SOTA performance on a variety of continual learning benchmarks through effectively improving the learning of new tasks, and boosts representative continual learning strategies in a plug-and-play way. Intriguingly, derived from active forgetting of the past with Bayesian continual learning, we obtain the algorithm that is formally consistent with the synaptic expansion and synaptic convergence (detailed Appendix A), and is functionally consistent with the advantage of biological active forgetting in memory flexibility [5]. This connection provides a potential theoretical explanation of how the underlying mechanism of biological active forgetting achieves its function of forgetting the past and continually learning conflicting experiences. We will further explore it with artificial neural networks and biological neural networks in the future.
Limitation and Social Impact
The potential limitations of our work include three aspects: First, we propose a method to mitigate potential negative transfer in continual learning, so the efficacy of our method might be influenced by the level of negative transfer in a task sequence. Second, following [12], we assume that all the incremental tasks are independent, which might limit the application of our method to other scenarios such as continual learning of smoothly-changed data distributions. Third, our method needs to learn an additional set of parameters, resulting in more computational cost. Since our work is a fundamental research in machine learning, the negative social impacts are not obvious at this stage.

heading: Acknowledgements

text: This work was supported by NSF of China Projects (Nos. 62061136001, 61620106010, U19B2034, U181146, 62076145), Beijing NSF Project (No. JQ19016), Tsinghua-Peking Center for Life Sciences, Beijing Academy of Artificial Intelligence (BAAI), Tsinghua-Huawei Joint Research Program, a grant from Tsinghua Institute for Guo Qiang, and the NVIDIA NVAIL Program with GPU/DGX Acceleration.

title: AFEC: Active Forgetting of Negative Transfer in Continual Learning


summaries: The paper provides a convergence analysis of a class of prior-guided zeroth-order (ZO) optimization algorithms and gives a prior-guided variant of the accelerated random search (ARS) algorithm.  Contribution: 1. Provides a complete convergence on some prior-guided zeroth-order optimization algorithms. 2. Provides a prior-guided variant of the ARS algorithm.

summaries: This work studies the problem of zeroth-order optimization in a deterministic setting, where the exact function values at each point can be observed but the gradient of the function is not accessible. The main approach for solving such problems is first to estimate the gradient of the function and then apply a gradient method by plugging in this estimator instead of the gradient. The main goal of this work is to provide convergence guarantee for prior guided zeroth order algorithms.  Assumptions on the objective function: The objective function is (strongly) convex and smooth.  Approach: Since the paper assumes a deterministic setting, at each step by two function evaluations and choosing a small enough perturbation term, roughly they can observe the gradient of the function towards any arbitrary direction (page 3, equation 1). Also, they assume that at each step they can observe $q$ random directions of the gradient, which are given priorly (or they estimate them by $2q$ additional function evaluations). Then, they take advantage of these $q$ given directions and $g_{I}$s to construct $g_t$, where $g_t$ is the gradient estimator at step $t$, and $I<t$.   Contributions: Their results in Theorems 3 and 4 outline the convergence guarantees and robustness to the learning rate.

summaries: This work analyzes the convergence rates of several existing prior guided zero order optimization methods. The zero order methods studied use statistical methods to provide an estimate of the function gradient using only function evaluations. This works studies the trade offs between gradient estimation accuracy and function evaluations as well as the effect of learning rate selection for the various estimates. This work also proposes a prior guided version of accelerated random search and studies its convergence. All algorithms studied are then numerically compared on benchmark functions as well as black box adversarial attacks.

summaries: This paper studies the performance of zeroth order optimization algorithms where gradient estimation uses prior information. They provide a bound on the convergence analysis for such prior guided algorithms in terms of expected alignment of the gradient estimates to the true gradient. They use this framework to study historical priors and show that such a prior may counter the effects of using a sub-optimal learning rate. They also provide a new accelerated random search algorithm that incorporates prior information.

abstractText: Zeroth-order (ZO) optimization is widely used to handle challenging tasks, such as query-based black-box adversarial attacks and reinforcement learning. Various attempts have been made to integrate prior information into the gradient estimation procedure based on finite differences, with promising empirical results. However, their convergence properties are not well understood. This paper makes an attempt to fill up this gap by analyzing the convergence of prior-guided ZO algorithms under a greedy descent framework with various gradient estimators. We provide a convergence guarantee for the prior-guided random gradient-free (PRGF) algorithms. Moreover, to further accelerate over greedy descent methods, we present a new accelerated random search (ARS) algorithm that incorporates prior information, together with a convergence analysis. Finally, our theoretical results are confirmed by experiments on several numerical benchmarks as well as adversarial attacks. Our code is available at https://github.com/csy530216/pg-zoo.

authors:
Marcin Andrychowicz
Misha Denil
Sergio Gomez
Matthew W Hoffman
David Pfau
Tom Schaul
Brendan Shillingford
Nando De Freitas

title: Learning to learn by gradient descent by gradient descent

venue: arXiv preprint arXiv:1606.04474,

authors:
Albert S Berahas
Liyuan Cao
Krzysztof Choromanski
Katya Scheinberg

title: A theoretical and empirical comparison of gradient approximations in derivative-free optimization

venue: Foundations of Computational Mathematics,

authors:
El Houcine Bergou
Eduard Gorbunov
Peter Richtarik

title: Stochastic three points method for unconstrained smooth minimization

venue: SIAM Journal on Optimization,

authors:
Thomas Brunner
Frederik Diehl
Michael Truong Le
Alois Knoll

title: Guessing smart: Biased sampling for efficient black-box adversarial attacks

venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,

title: Convex optimization: Algorithms and complexity

venue: arXiv preprint arXiv:1405.4980,

authors:
Nicholas Carlini
David Wagner

title: Towards evaluating the robustness of neural networks

venue: In 2017 ieee symposium on security and privacy (sp),

authors:
Pin-Yu Chen
Huan Zhang
Yash Sharma
Jinfeng Yi
Cho-Jui Hsieh

title: Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models

venue: In Proceedings of the 10th ACM workshop on artificial intelligence and security,

authors:
Shuyu Cheng
Yinpeng Dong
Tianyu Pang
Hang Su
Jun Zhu

title: Improving black-box adversarial attacks with a transfer-based prior

authors:
Krzysztof Choromanski
Mark Rowland
Vikas Sindhwani
Richard Turner
Adrian Weller

title: Structured evolution with compact architectures for scalable policy optimization

venue: In International Conference on Machine Learning,

authors:
Daniel Golovin
John Karro
Greg Kochanski
Chansoo Lee
Xingyou Song
Qiuyi Zhang

title: Gradientless descent: High-dimensional zeroth-order optimization

authors:
Nikolaus Hansen
Andreas Ostermeier

title: Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation

venue: In Proceedings of IEEE international conference on evolutionary computation,

authors:
Nikolaus Hansen
Steffen Finck
Raymond Ros
Anne Auger

title: Real-parameter black-box optimization benchmarking 2009: Noiseless functions definitions

venue: PhD thesis,

authors:
Andrew Ilyas
Logan Engstrom
Anish Athalye
Jessy Lin

title: Black-box adversarial attacks with limited queries and information

authors:
Andrew Ilyas
Logan Engstrom
Aleksander Madry

title: Prior convictions: Black-box adversarial attacks with bandits and priors

venue: arXiv preprint arXiv:1807.07978,

authors:
David Kozak
Stephen Becker
Alireza Doostan
Luis Tenorio

title: A stochastic subspace approach to gradient-free optimization in high dimensions

venue: Computational Optimization and Applications,

authors:
Niru Maheswaranathan
Luke Metz
George Tucker
Dami Choi
Jascha Sohl-Dickstein

title: Guided evolutionary strategies: Augmenting random search with surrogate gradients

authors:
Horia Mania
Aurelia Guy
Benjamin Recht

title: Simple random search of static linear policies is competitive for reinforcement learning

venue: In Proceedings of the 32nd International Conference on Neural Information Processing Systems,

title: Random optimization

venue: Automation and Remote control, 26(2):246–253

authors:
Florian Meier
Asier Mujika
Marcelo Matheus Gauy
Angelika Steger

title: Improving gradient estimation in evolutionary strategies with past descent directions

title: Efficiency of coordinate descent methods on huge-scale optimization problems

authors:
Yurii Nesterov
Vladimir Spokoiny

title: Random gradient-free minimization of convex functions

authors:
Tim Salimans
Jonathan Ho
Xi Chen
Szymon Sidor
Ilya Sutskever

title: Evolution strategies as a scalable alternative to reinforcement learning

venue: arXiv preprint arXiv:1703.03864,

authors:
Jasper Snoek
Hugo Larochelle
Ryan P Adams

title: Practical bayesian optimization of machine learning algorithms

venue: arXiv preprint arXiv:1206.2944,

authors:
Sebastian U Stich
Christian L Muller
Bernd Gartner

title: Optimization of convex functions with random pursuit

authors:
Chun-Chen Tu
Paishun Ting
Pin-Yu Chen
Sijia Liu
Huan Zhang
Jinfeng Yi
Cho-Jui Hsieh
Shin- Ming Cheng

title: Autozoom: Autoencoder-based zeroth order optimization method for attacking black-box neural networks

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

heading: 1 Introduction

text:
Zeroth-order (ZO) optimization [18] provides powerful tools to deal with challenging tasks, such as query-based black-box adversarial attacks [7, 13], reinforcement learning [22, 17, 9], meta-learning [1], and hyperparameter tuning [23], where the access to gradient information is either not available or too costly. ZO methods only assume an oracle access to the function value at any given point, instead of gradients as in first-order methods. The primary goal is to find a solution with as few queries to the function value oracle as possible. Recently, various ZO methods have been proposed in two main categories. One type is to obtain a gradient estimator and plug in some gradient-based methods. [21] analyzes the convergence of such methods with a random gradient-free (RGF) estimator obtained via finite difference along a random direction. The other type is directed search, where the update only depends on comparison between function values at different points. Such methods are robust against monotone transform of the objective function [24, 10, 3]. However, as they do not directly utilize function values, their query complexity is often higher than that of finite difference methods. Therefore, we focus on the first type of methods in this paper. Other methods exist such as CMA-ES [11] which is potentially better on objective functions with a rugged landscape, but lacks a general convergence guarantee.
ZO methods are usually less efficient than first-order algorithms, as they typically take O(d) queries to reach a given precision, where d is the input dimension (see Table 1 in [10]). Specifically, for the methods in [21], the oracle query count is O(d) times larger than that of their corresponding schemes using gradients. This inefficiency stems from random search along uniformly distributed directions. To improve, various attempts have been made to augment random search with (extra) ∗J.Z. is the Corresponding Author. G.W. is now with School of Software, Shandong University.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
prior information. For instance, [14, 19] use a time-dependent prior (i.e., the gradient estimated in the last iteration), while [16, 8, 4] use surrogate gradients obtained from other sources.2 Among these methods, [14, 16, 8, 19] propose objective functions to describe the quality of a gradient estimator for justification or optimizing its hyperparameters; for example, [19] uses a subspace estimator that maximizes its squared cosine similarity with the true gradient as the objective, and finds a better descent direction than both the prior direction and the randomly sampled direction. However, all these methods treat gradient estimation and the optimization algorithm separately, and it remains unclear whether are these gradient estimators and the corresponding prior-exploiting optimization methods theoretically sound? and what role does the prior play in accelerating convergence?
In this paper, we attempt to answer these questions by establishing a formal connection between convergence rates and the quality of gradient estimates. Further, we develop a more efficient ZO algorithm with prior inspired by a theoretical analysis. First, we present a greedy descent framework of ZO methods and provide its convergence rate under smooth convex optimization, which is positively related to the squared cosine similarity between the gradient estimate and true gradient. As shown by [19] and our results, given some finite-difference queries, the optimal estimator maximizing the squared cosine similarity is the projection of true gradient on the subspace spanned by those queried directions. In the case with prior information, a natural such estimator is in the same form as the one in [19]. We call it PRGF estimator and analyze its convergence rate.3 Our results show that no matter what the prior is, the convergence rate of PRGF is at least the same as that of the RGF baseline [21, 15], and it could be significantly improved if given a useful prior.4 Such results shed light on exploring prior information in ZO optimization to accelerate convergence.
Then, as a concrete example, we apply the analysis to History-PRGF [19], which uses historical information (i.e., gradient estimate in the last iteration) as the prior. [19] presents an analysis on linear functions, yet still lacking a convergence rate. We analyze on general L-smooth functions, and find that when the learning rate is smaller than the optimal value 1/L in smooth optimization, the expected squared cosine similarity could converge to a larger value, which compensates for the slowdown of convergence brought by the inappropriate choice of learning rate. We also show that History-PRGF admits a convergence rate independent of learning rate as long as it is in a fairly wide range.
Finally, to further accelerate greedy descent methods, we present Prior-Guided ARS (PARS), a new variant of Accelerated Random Search (ARS) [21] to utilize prior information. Technically, PARS is a non-trivial extension of ARS, as directly replacing the gradient estimator in ARS by the PRGF estimator would lose the convergence analysis. Thus, we present necessary extensions to ARS, and show that PARS has a convergence rate no worse than that of ARS and admits potential acceleration given a good prior. In particular, when the prior is chosen as the historical information, the resulting History-PARS is robust to learning rate in experiments. To our knowledge, History-PARS is the first ARS-based method that is empirically robust while retaining the convergence rate as ARS. Our experiments on numerical benchmarks and adversarial attacks confirm the theoretical results.

heading: 2 Setups

text:
Assumptions on the problem class We consider unconstrained optimization, where the objective function f : Rd → R is convex and L-smooth for L ≥ 0. Optionally, we require f to be τ -strongly convex for τ > 0. We leave definitions of these concepts to Appendix A.1.
Directional derivative oracle In ZO optimization, we follow the finite difference approach, which makes more use of the queried function values than direct search and provides better gradient approximations than alternatives [2]. In particular, we consider the forward difference method:
gµ(v;x) := f(x+ µv)− f(x)
µ ≈ ∇f(x)>v, (1)
2Some work [7, 14, 25] restricts the random search to a more effective subspace reflecting the prior knowledge. But, this eliminates the possibility of convergence to the optimal solution.
3Note that the estimator is different from the P-RGF estimator in [8]. 4In this paper, RGF and PRGF could refer to either a gradient estimator or the greedy descent algorithm with
the corresponding estimator, depending on the context.
Algorithm 1 Greedy descent framework
Input: L-smooth convex function f ; initialization x0; upper bound L̂ (L̂ ≥ L); iteration number T . Output: xT as the approximate minimizer of f .
1: for t = 0 to T − 1 do 2: Let vt be a random vector s.t. ‖vt‖ = 1; 3: xt+1 ← xt − 1L̂gt, where gt ← ∇f(xt)
>vt · vt; 4: end for 5: return xT .
where v is a vector with unit `2 norm ‖v‖ = 1 and µ is a small positive step. As long as the objective function is smooth, the error between the finite difference and the directional derivative could be uniformly bounded, as shown in the following proposition (see Appendix A.2 for its proof). Proposition 1. If f is L-smooth, then for any (x, v) with ‖v‖ = 1, |gµ(v;x)−∇f(x)>v| ≤ 12Lµ. Thus, in smooth optimization, the error brought by finite differences to the convergence bound can be analyzed in a principled way, and its impact tends to zero as µ→ 0. We also choose µ as small as possible in practice. Hence, in the following analysis we directly assume the directional derivative oracle: suppose that we can obtain∇f(x)>v for any (x, v) in which ‖v‖ = 1 with one query.

heading: 3 Greedy descent framework and PRGF algorithm

text: We now introduce a greedy descent framework in ZO optimization which can be implemented with various gradient estimators. We first provide a general analysis, followed by a concrete example.

heading: 3.1 The greedy descent framework and general analysis

text:
In first-order smooth convex optimization, a sufficient single-step decrease of the objective can guarantee convergence (see Chapter 3.2 in [5]). Inspired by this fact, we design the update in an iteration to greedily seek for maximum decrease. Suppose we are currently at x, and want to update along the direction v. Without loss of generality, assume ‖v‖ = 1 and∇f(x)>v > 0. To choose a suitable step size η that minimizes f(x− ηv), we note that
f(x− ηv) ≤ f(x)− η∇f(x)>v + 1 2 Lη2 := F (η) (2)
by smoothness of f . For the r.h.s, we have F (η) = f(x)− (∇f(x) >v)2 2L when η = ∇f(x)>v
L , which minimizes F (η). Thus, choosing such η could lead to a largest guaranteed decrease of f(x−ηv) from f(x). In practice, the value of L is often unknown, but we can verify that as long as 0 < η ≤ ∇f(x)
>v L ,
then f(x− ηv) ≤ F (η) < f(x), i.e., we can guarantee decrease of the objective (regardless of the direction of v if∇f(x)>v > 0). Based on the above discussion, we further allow v to be random and present the greedy descent framework in Algorithm 1. Remark 1. If vt ∼ U(Sd−1), i.e. vt is uniformly sampled from Sd−1 (the unit sphere in Rd), then Algorithm 1 is similar to the simple random search in [21] except that vt is sampled from a Gaussian distribution there. Remark 2. In general, vt could depend on the history (i.e., the randomness before sampling vt). For example, vt can be biased towards a vector pt that corresponds to prior information, and pt depends on the history since it depends on xt or the optimization trajectory.
Theoretically speaking, vt is sampled from the conditional probability distribution Pr(·|Ft−1) where Ft−1 is a sub σ-algebra modelling the historical information. Ft−1 is important in our theoretical analysis since it tells how to perform conditional expectation given the history.
We always require that Ft−1 includes all the randomness before iteration t to ensure that Lemma 1 (and thus Theorems 1 and 2) and Theorem 5 hold. For further theoretical analysis of various implementations of the framework, Ft−1 remains to be specified by possibly also including some randomness in iteration t (see e.g. Example 2 as an implementation of Algorithm 1).5
5In mathematical language, if Ft−1 includes (and only includes) the randomness brought by random vectors {x1, x2, . . . , xn}, then Ft−1 is the σ-algebra generated by {x1, x2, . . . , xn}: Ft−1 is the smallest σ-algebra s.t. xi is Ft−1-measurable for all 1 ≤ i ≤ n.
By Remark 2, we introduce Et[·] := E[·|Ft−1] to denote the conditional expectation given the history. In Algorithm 1, under a suitable choice of Ft−1, Et[·] roughly means only taking expectation w.r.t. vt. We let v := v/‖v‖ denote the `2 normalization of vector v. We let x∗ denote one of the minimizers of f (we assume such minimizer exists), and δt := f(xt)− f(x∗). Thanks to the descent property in Algorithm 1, we have the following lemma on single step progress.
Lemma 1 (Proof in Appendix B.1). Let Ct := ( ∇f(xt) > vt )2 and L′ := L
1−(1−L L̂
)2 , then in
Algorithm 1, we have
Et[δt+1] ≤ δt − Et[Ct]
2L′ ‖∇f(xt)‖2. (3)
We note that L′ = L̂/(2−L/L̂), so L̂2 ≤ L ′ ≤ L̂ and L′ ≥ L.
To obtain a bound on E[δT ], one of the classical proofs (see e.g., Theorem 1 in [20]) requires us to take expectation on both sides of Eq. (3). Allowing the distribution of vt to be dependent on the history leads to additional technical difficulty: in the r.h.s of Eq. (3), Et[Ct] becomes a random variable that is not independent of ‖∇f(xt)‖2. Thus, we cannot simplify the term E[Et[Ct]‖∇f(xt)‖2] if we take expectation.6 By using other techniques, we obtain the following main theorems on convergence rate. Theorem 1 (Algorithm 1, smooth and convex; proof in Appendix B.1). Let R := maxx:f(x)≤f(x0) ‖x− x∗‖ and suppose R <∞. Then, in Algorithm 1, we have
E[δT ] ≤ 2L′R2
∑T−1 t=0 E [ 1
Et[Ct] ] T (T + 1) . (4)
Theorem 2 (Algorithm 1, smooth and strongly convex; proof in Appendix B.1). If f is also τ -strongly convex, then we have
E  δT exp ( − τL′ ∑T−1 t=0 Et[Ct] )  ≤ δ0. (5)
Remark 3. In our results, the convergence rate depends on Et[Ct] in a more complicated way than only depending on E[Ct] = E[Et[Ct]]. For concrete cases, one may need to study the concentration properties of Et[Ct] besides its expectation, as in the proofs of Theorems 3 and 4 when we analyze History-PRGF, a special implementation in the greedy descent framework.
In the strongly convex case, currently we cannot directly obtain a final bound of E[δT ]. However, the form of Eq. (5) is still useful since it roughly tells us that δT converges as the denominator exp ( − τL′ ∑T−1 t=0 Et[Ct] ) . For History-PRGF, we will turn this intuition into a rigorous theorem (Theorem 4) since in that case we can prove that the denominator has a nice concentration property. Remark 4. If we have a lower bound of Et[Ct], e.g. Et[Ct] ≥ a > 0, then we directly obtain that E[δT ] ≤ 2L ′R2 a(T+1) for Theorem 1, and E[δT ] ≤ δ0 exp(− τ L′ aT ) for Theorem 2. These could recover the ideal convergence rate for RGF estimator and the worst-case convergence rate for PRGF estimator, as explained in Examples 1 and 2.
From Theorems 1 and 2, we see that a larger value of Ct would lead to a better bound. To find a good choice of vt in Algorithm 1, it becomes natural to discuss the following problem. Suppose in an iteration in Algorithm 1, we query the directional derivative oracle at xt along q directions {ui}qi=1 (maybe randomly chosen) and obtain the values of {∇f(xt)>ui}qi=1. We could use this information to construct a vector vt. What is the vt that maximizes Ct s.t. ‖vt‖ = 1? To answer this question, we give the following proposition based on Proposition 1 in [19] and additional justification. Proposition 2 (Optimality of subspace estimator; proof in Appendix B.2). In one iteration of Algorithm 1, if we have queried {∇f(xt)>ui}qi=1, then the optimal vt maximizing Ct s.t. ‖vt‖ = 1 should be in the following form: vt = ∇f(xt)A, where A := span{u1, u2, . . . , uq} and ∇f(xt)A denotes the projection of∇f(xt) onto A.
6It is also the difficulty we faced in our very preliminary attempts of the theoretical analysis when f is not convex, and we leave its solution or workaround in the non-convex case as future work.
Note that in Line 3 of Algorithm 1, we have gt = ∇f(xt)>∇f(xt)A · ∇f(xt)A = ∇f(xt)A. Therefore, the gradient estimator gt is equivalent to the projection of the gradient to the subspace A, which justifies its name of subspace estimator. Next we discuss some special cases of the subspace estimator. We leave detailed derivation in following examples to Appendix B.3.
Example 1 (RGF). ui ∼ U(Sd−1) for i = 1, 2, . . . , q. Without loss of generality, we assume they are orthonormal (e.g., via Gram-Schmidt orthogonalization).7 The corresponding estimator gt = ∑q i=1∇f(xt)>ui · ui (vt = gt). When q = 1, the estimator is similar to the random gradientfree oracle in [21]. With q ≥ 1, it is essentially the same as the stochastic subspace estimator with columns from Haar-distributed random orthogonal matrix [15] and similar to the orthogonal ES estimator [9]. In theoretical analysis, we let Ft−1 only include the randomness before iteration t, and then we can prove that Et[Ct] = qd . By Theorems 1 and 2, the convergence rate is E[δT ] ≤ 2L′R2 dq T+1 for smooth convex case, and E[δT ] ≤ δ0 exp(− τL′ q dT ) for smooth and strongly convex case. The bound is the same as that in [15]. Since the query complexity in each iteration is proportional to q, the bound for total query complexity is indeed independent of q.
Example 2 (PRGF). With slight notation abuse, we assume the subspace in Proposition 2 is spanned by {p1, . . . , pk, u1, . . . , uq}, so each iteration takes q + k queries. Let p1, · · · , pk be k non-zero vectors corresponding to the prior message (e.g. the historical update, or the gradient of a surrogate model), and ui ∼ U(Sd−1) for i = 1, 2, . . . , q. We note that intuitively we cannot construct a better subspace since the only extra information we know is the k priors. In our analysis, we assume k = 1 for convenience, and we change the original notation p1 to pt to explicitly show the dependence of pt on the history. We note that pt could also depend on extra randomness in iteration t (see e.g. the specification of pt in Appendix D.1.1). For convenience of theoretical analysis, we require that pt is determined before sampling {u1, u2, . . . , uq}, and let Ft−1 also include the extra randomness of pt in iteration t (not including the randomness of {u1, u2, . . . , uq}) besides the randomness before iteration t. Then pt is always Ft−1-measurable, i.e. determined by the history. Without loss of generality, we assume {pt, u1, . . . , uq} are orthonormal (e.g., via Gram-Schmidt orthogonalization). The corresponding estimator gt = ∇f(xt)>pt · pt + ∑q i=1∇f(xt)>ui · ui (vt = gt), which is similar to the estimator in [19]. By [19] (the expected drift of X2t in its Theorem 1), we have Lemma 2 (Proof in Appendix B.3.4). In Algorithm 1 with PRGF estimator, Et[Ct] = Dt + qd−1 (1−
Dt) where Dt := ( ∇f(xt) > pt )2 .
Hence Et[Ct] ≥ qd holds. By Remark 4, PRGF admits a guaranteed convergence rate of RGF and is potentially better given a good prior (if Dt is large), but it costs an additional query per iteration. This shows soundness of the PRGF algorithm. For further theoretical analysis, we need to bound Dt. This could be done when using the historical prior introduced in Section 3.2 (see Lemma 3). Bounding Dt is usually challenging when a general prior is adopted, but if the prior is an approximate gradient (such case appears in [16]), it may be possible. We leave related investigation as future work.

heading: 3.2 Analysis on the PRGF algorithm with the historical prior

text:
We apply the above analysis to a concrete example of the History-PRGF estimator [19], which considers the historical prior in the PRGF estimator. In this case, Lemma 1, Theorem 1 and Theorem 2 will manifest themselves by clearly stating the convergence rate which is robust to the learning rate.
Specifically, History-PRGF considers the historical prior as follows: we choose pt = gt−1, i.e., we let the prior be the direction of the previous gradient estimate.8 This is equivalent to letting pt = vt−1. Thus, in Algorithm 1, vt = ∇f(xt)A = ∇f(xt)>vt−1 · vt−1 + ∑q i=1∇f(xt)>ui · ui. In this form we require {vt−1, u1, . . . , uq} to be orthonormal, so we first determine vt−1, and then
7The computational complexity of Gram-Schmidt orthogonalization over q vectors in Rd is O(q2d). Therefore, with a moderate value of q (e.g. q ∈ [10, 20] in our experiments), its cost is usually much smaller than that brought by O(q) function evaluations used to approximate the directional derivatives. We note that when using a numerical computing framework, for orthogonalization one could also adopt an efficient implementation, by calling the QR decomposition procedure such as torch.linalg.qr in PyTorch.
8One can also utilize multiple historical priors (e.g. the last k updates with k > 1, as proposed and experimented in [19]), but here we only analyze the k = 1 case.
sample {ui}qi=1 in A⊥, the (d− 1)-dimensional subspace of Rd perpendicular to vt−1, and then do Gram-Schmidt orthonormalization on {ui}qi=1. To study the convergence rate, we first study evolution of Ct under a general L-smooth function. This extends the analysis on linear functions (corresponding to L = 0) in [19]. Under the framework of Algorithm 1, intuitively, the change of the gradient should be smaller when the objective function is very smooth (L is small) or the learning rate is small (L̂ is large). Since we care about the cosine similarity between the gradient and the prior, we prove the following lemma:
Lemma 3 (Proof in Appendix B.4). In History-PRGF (pt = vt−1), we have Dt ≥ (1− L/L̂)2 Ct−1.
When L̂ = L, i.e., using the optimal learning rate, Lemma 3 does not provide a useful bound, since an optimal learning rate in smooth optimization could find an approximate minimizer along the update direction, so the update direction may be useless in next iteration. In this case, the historical prior does not provide acceleration. Hence, Lemma 3 explains the empirical findings in [19] that past directions can be less useful when the learning rate is larger. However, in practice we often use a conservative learning rate, for the following reasons: 1) We usually do not know L, and the cost of tuning learning rate could be large; 2) Even if L is known, it only provides a global bound, so a fixed learning rate could be too conservative in the smoother local regions. In scenarios where L̂ is too conservative (L̂ > L), History-PRGF could bring more acceleration over RGF.
By Lemma 3, we can assume Dt = (1− L/L̂)2 Ct−1 to obtain a lower bound of quantities about Ct. Meanwhile, since Dt means quality of the prior, the construction in Example 2 tells us relationship between Ct and Dt. Then we have full knowledge of the evolution of Ct, and thus Et[Ct]. In Appendix B.4, we discuss about evolution of E[Ct] and show that E[Ct]→ O( qd L′ L ) if q d ≤ L L̂ ≤ 1. Therefore, by Lemma 1, assuming Et[Ct] concentrates well around E[Ct] and hence Et[Ct]L′ ≈ q dL , PRGF could recover the single step progress with optimal learning rate (L̂ = L), since Eq. (3) only depends on Et[Ct]L′ which is constant w.r.t. L
′ now. While the above discussion is informal, based on Theorems 1 and 2, we prove following theorems which show that convergence rate of History-PRGF is robust to choice of learning rate.
Theorem 3 (History-PRGF, smooth and convex; proof in Appendix B.5.1). In the setting of Theorem 1, assuming d ≥ 4, qd−1 ≤ L L̂ ≤ 1 and T > ⌈ d q ⌉ (d·e denotes the ceiling function), we have
E[δT ] ≤ ( 32
q + 2
) 2LdqR 2
T − ⌈ d q ⌉ + 1 . (6)
Sketch of the proof. The idea of the proof of Theorem 3 is to show that for the random variable Et[Ct], its standard deviation √ Var[Et[Ct]] is small relative to its expectation E[Et[Ct]] = E[Ct].
By Chebyshev’s inequality, we can bound E [
1 Et[Ct] ] in Theorem 1 with 1E[Et[Ct]] = 1 E[Ct] . In the
actual proof we replace Ct that appears above with a lower bound Et.
Theorem 4 (History-PRGF, smooth and strongly convex; proof in Appendix B.5.3). Under the same conditions as in Theorem 2, then assuming d ≥ 4, qd−1 ≤ L L̂ ≤ 1, qd ≤ 0.2 L τ , and T ≥ 5 d q , we have
E[δT ] ≤ 2 exp ( −0.1 q
d
τ L T ) δ0. (7)
This result seems somewhat surprising since Theorem 2 does not directly give a bound of E[δT ]. Sketch of the proof. The goal is to show that the denominator in the l.h.s of Eq. (5) in Theorem 2, exp(− τ
L̃
∑T−1 t=0 Et[Ct]), concentrates very well. Indeed, the probability that exp(− τ L̃ ∑T−1 t=0 Et[Ct])
is larger than exp(−0.1 qd τ LT ) is very small so that its influence can be bounded by another exp(−0.1 qd τ LT )δ0, leading to the coefficient 2 in Eq. (7). In our actual analysis we replace Ct that appears above with a lower bound Et.
Remark 5. As stated in Example 2, using RGF with the optimal learning rate, we have E[δT ] ≤ 2L dqR 2 T+1 for smooth and convex case, and E[δT ] ≤ exp ( − qd τ LT ) δ0 for smooth and strongly convex
case. Therefore, History-PRGF with a suboptimal learning rate 1 L̂ under the condition qd−1 1 L ≤ 1 L̂ ≤ 1 L could reach similar convergence rate to RGF with optimal learning rate (up to constant factors), which indicates that History-PRGF is more robust to learning rate than RGF. Remark 6. We note that the constants in the bounds are loose and have a large potential to be improved in future work, and empirically the convergence rate of History-PRGF is often not worse than RGF using the optimal learning rate (see Fig. 2).
As a sidenote, we discuss how to set q in History-PRGF. The iteration complexity given by Theorems 3 and 4 is proportional to 1q if we ignore the constants such as 32 q +2 in Eq. (6) by Remark 6. Meanwhile, we recall that each iteration of PRGF requires q + 1 queries to the directional derivative oracle, so the total query complexity is roughly proportional to q+1q . Hence, a very small q (e.g. q = 1) is
suboptimal. On the other hand, Theorems 3 and 4 require 1 L̂ ∈ [ q d−1 1 L , 1 L ] , so to enable robustness of History-PRGF to a wider range of the choice of learning rate, q should not be too large. In summary, it is desirable to set q to a moderate value.
Note that if we adopt line search in Algorithm 1, then one can adapt the learning rate in a huge range and reach the convergence guarantee with the optimal learning rate under weak assumptions. Nevertheless, it is still an intriguing fact that History-PRGF could perform similarly to methods adapting the learning rate, while its mechanism is very different. Meanwhile, History-PRGF is easier to be implemented and parallelized compared with methods like line search, since its implementation is the same as that of the RGF baseline except that it records and uses the historical prior.

heading: 4 Extension of ARS framework and PARS algorithm

text:
To further accelerate greedy descent methods, we extend our analysis to a new variant of Accelerated Random Search (ARS) [21] by incorporating prior information, under the smooth and convex setting.9
By delving into the proof in [21], we present our extension to ARS in Algorithm 2, state its convergence guarantee in Theorem 5 and explain its design in the proof sketch in Appendix C.1.
Algorithm 2 Extended accelerated random search framework10
Input: L-smooth convex function f ; initialization x0; L̂ ≥ L; iteration number T ; γ0 > 0. Output: xT as the approximate minimizer of f . 1: m0 ← x0; 2: for t = 0 to T − 1 do
3: Find a θt > 0 such that θt ≤ Et [ (∇f(yt)>vt) 2 ]
L̂·Et[‖g2(yt)‖2] where yt, vt and g2(yt) are defined in following steps:
4: Step 1: yt ← (1 − αt)xt + αtmt, where αt is a positive root of the equation α2t = θt(1 − αt)γt; γt+1 ← (1− αt)γt; 5: Step 2: Let vt be a random vector s.t. ‖vt‖ = 1; g1(yt)← ∇f(yt)>vt · vt; 6: Step 3: Let g2(yt) be an unbiased estimator of∇f(yt), i.e., Et[g2(yt)] = ∇f(yt); 7: xt+1 ← yt − 1
L̂ g1(yt), mt+1 ← mt − θtαt g2(yt);
8: end for 9: return xT .
Theorem 5 (Proof in Appendix C.1). In Algorithm 2, if θt is Ft−1-measurable (see Appendix C.1 for more explanation), then we have
E (f(xT )− f(x∗))(1 + √γ0 2 T−1∑ t=0 √ θt )2 ≤ f(x0)− f(x∗) + γ0 2 ‖x0 − x∗‖2. (8)
9The procedure of ARS requires knowledge of the strong convexity parameter τ (τ can be 0), but for clarity we only discuss the case τ = 0 here (i.e., we do not consider strong convexity), and leave the strongly convex case to Appendix C.6.
10Keys in this extension are: 1) We require Et[g2(yt)] = ∇f(yt). Thus, g2(yt) could not be the PRGF estimator as it is biased towards the prior; 2) To accelerate convergence, we need to find an appropriate θt since it appears in Eq. (8). If we set θt to the value in ARS baseline, then no potential acceleration is guaranteed.
Remark 7. If we let g1(yt) be the RGF estimator in Example 1 and let g2(yt) = d/q · g1(yt), we can
show that E[g2(yt)] = ∇f(yt) and θt could be chosen as q 2
L̂d2 since
Et [ (∇f(yt)>vt) 2 ]
L̂·Et[‖g2(yt)‖2] = q
2
L̂d2 . Then
roughly, the convergence rate ∝ q, so the total query complexity is independent of q. When q = 1, ARS baseline is recovered. For convenience we call the algorithm ARS regardless of the value of q. Remark 8. If we have a uniform constant lower bound θ > 0 such that ∀t, θt ≥ θ, then we have
E [f(xT )− f(x∗)] ≤ ( 1 + √ γ0
2 T √ θ
)−2 ( f(x0)− f(x∗) +
γ0 2 ‖x0 − x∗‖2
) . (9)
Next we present Prior-Guided ARS (PARS) by specifying the choice of g1(yt) and g2(yt) in Algorithm 2 when prior information pt ∈ Rd is available. Since we want to maximize the value of θt, regarding g1(yt) we want to maximize Et [( ∇f(yt)>vt )2] . By Proposition 2 and Exam-
ple 2, it is natural to let g1(yt) be the PRGF estimator for ∇f(yt). Then by Lemma 2, we have Et [( ∇f(yt)>vt )2] = ‖∇f(yt)‖2(Dt + qd−1 (1−Dt)), where Dt := ( ∇f(yt) > pt )2 . The remaining problem is to construct g2(yt), an unbiased estimator of ∇f(yt) (Et[g2(yt)] = ∇f(yt)), and make Et[‖g2(yt)‖2] as small as possible. We leave the construction of g2(yt) in Appendix C.2. Finally, we calculate the following expression which appears in Line 3 of Algorithm 2 to complete the description of PARS:
Et [( ∇f(yt)>vt )2] L̂ · Et[‖g2(yt)‖2] = Dt + q d−1 (1−Dt) L̂ ( Dt + d−1 q (1−Dt)
) . (10) Since Dt ≥ 0, the right-hand side is larger than q2/L̂d2 (by Remark 7, this value corresponds to the value of θt in ARS), so by Remark 8 PARS is guaranteed a convergence rate of ARS.
In implementation of PARS, we note that there remain two problems to solve. The first is that Dt is not accessible through one oracle query, since Dt = (∇f(yt) > pt) 2 = ( ∇f(yt)>pt/‖∇f(yt)‖ )2 , and ‖∇f(yt)‖ requires estimation. Fortunately, the queries used to construct g1(yt) and g2(yt) can also be used to estimate Dt. With a moderate value of q, we can prove that considering the error brought by estimation of Dt, a modified version of PARS is guaranteed to converge with high probability. We leave related discussion to Appendix C.3. The second is that Line 3 of Algorithm 2 has a subtlety that
yt depends on θt, so we cannot directly determine an optimal θt satisfying θt ≤ Et [ (∇f(yt)>vt) 2 ]
L̂·Et[‖g2(yt)‖2] .
Theoretically, we can guess a conservative estimate of θt and verify this inequality, but in practice we adopt a more aggressive strategy to find an approximate solution of θt. We leave the actual implementation, named PARS-Impl, in Appendix C.4.
In PARS, if we adopt the historical prior as in Section 3.2, i.e., letting pt be the previous PRGF gradient estimator g1(yt−1), then we arrive at a novel algorithm named History-PARS. Here, we note that unlike the case in History-PRGF, it is more difficult to derive the evolution of θt theoretically, so we currently cannot prove theorems corresponding to Theorem 3. However, History-PARS can be guaranteed the convergence rate of ARS, which is desirable since if we adopt line search in ARS to reach robustness against learning rate (e.g. in [24]), currently there is no convergence guarantee. We present the actual implementation History-PARS-Impl in Appendix C.5 and empirically verify that History-PARS-Impl is robust to learning rate in Section 5.

heading: 5 Experiments

heading: 5.1 Numerical benchmarks

text:
We first experiment on several closed-form test functions to support our theoretical claims. We leave more details of experimental settings to Appendix D.1.
First, we present experimental results when a general useful prior is provided. The prior-guided methods include PRGF, PARS (refers to PARS-Impl) and PARS-Naive (simply replacing the RGF estimator in ARS with the PRGF estimator). We adopt the setting in Section 4.1 of [16] in which the
prior is a biased version of the true gradient. Our test functions are as follows: 1) f1 is the “worst-case smooth convex function” used to construct the lower bound complexity of first-order optimization, as in [21]; 2) f2 is a simple smooth and strongly convex function with a worst-case initialization: f2(x) = 1 d ∑d i=1 ( i · (x(i))2 ) , where x(1)0 = d, x (i) 0 = 0 for i ≥ 2; and 3) f3 is the Rosenbrock function (f8 in [12]) which is a well-known non-convex function used to test the performance of optimization problems. For f1 and f2, we set L̂ to ground truth value L; for f3, we search L̂ for best performance for each algorithm. We set d = 256 for all test functions and set q such that each iteration of these algorithms costs 11 queries11 to the directional derivative oracle.12 We plot the experimental results in Fig. 1, where the horizontal axis represents the number of iterations divided by bd/11c, and the vertical axis represents log10 f(xcurrent)−f(x∗) f(x0)−f(x∗) . Methods without using the prior information are shown with dashed lines. We also plot the 95% confidence interval in the colored region. The results show that for these functions (which have ill-conditioned Hessians), ARS-based methods perform better than the methods based on greedy descent. Importantly, the utilization of the prior could significantly accelerate convergence for both greedy descent and ARS. We note that the performance of our proposed PARS algorithm is better than PARS-Naive which naively replaces the gradient estimator in the original ARS with the PRGF estimator, demonstrating the value of our algorithm design with convergence analysis.
Next, we verify the properties of History-PRGF and History-PARS, i.e., the historical-prior-guided algorithms. In this part we set d = 500. We first verify that they are robust against learning rate on f1 and f2, and plot the results in Fig. 2(a)(b).13 In the legend, for example, ‘RGF’ means RGF using the optimal learning rate (L̂ = L), and ‘RGF-0.02’ means that the learning rate is set to 0.02 times of the optimal one (L̂ = 50L). We note that for PRGF and PARS, q = 10, so qd = 0.02. From Fig. 2(a)(b), we see that: 1) when using the optimal learning rate, the performance of prior-guided algorithms is not worse than that of its corresponding baseline; and 2) the performance of prior-guided algorithms under the sub-optimal learning rate such that qd ≤ L L̂ ≤ 1 is at least comparable to that of its corresponding baseline with optimal learning rate. However, for baseline algorithms (RGF and ARS), the convergence rate significantly degrades if a smaller learning rate is set. In summary, we verify our claims that History-PRGF and History-PARS are robust to learning rate if qd ≤ L L̂ ≤ 1. Moreover, we show that they can provide acceleration over baselines with optimal learning rate on functions with varying local smoothness. We design a new test function as follows:
f4(x) =
{ 1 2r
2, r ≤ 1 r − 12 , r > 1
, r = √ f2(x), where x (1) 0 = 5 √ d, x (i) 0 = 0 for i ≥ 2. (11)
We note that f4 in regions far away from the origin is more smooth than in the region near the origin, and the global smoothness parameter is determined by the worst-case situation (the region near the origin). Therefore, baseline methods using an optimal learning rate could also manifest sub-optimal performance. Fig. 2(c) shows the results. We can see that when utilizing the historical prior, the algorithm could show behaviors of adapting to the local smoothness, thus accelerating convergence when the learning rate is locally too conservative.
11That is, for prior-guided algorithms we set q = 10, and for other algorithms (RGF and ARS) we set q = 11. 12The directional derivative is approximated by finite differences. In PARS, 2 additional queries to the directional derivative oracle per iteration are required to find θt (see Appendix C.4). 13In Fig. 2, the setting of ARS-based methods are different from that in Fig. 1 as explained in Appendix D.1, which leads to many differences of the ARS curves between Fig. 1 and Fig. 2.

heading: 5.2 Black-box adversarial attacks

text:
In this section, we perform ZO optimization on real-world problems. We conduct score-based blackbox targeted adversarial attacks on 500 images from MNIST and leave more details of experimental settings to Appendix D.2. In view of optimization, this corresponds to performing constrained maximization over {fi}500i=1 respectively, where fi denotes the loss function to maximize in attacks. For each image i, we record the number of queries of fi used in optimization until the attack succeeds (when using the C&W loss function [6], this means fi > 0). For each optimization method, we report the median query number over these images (smaller is better) in Table 1. The subscript of the method name indicates the learning rate 1/L̂. For all methods we set q to 20. Since [8] has shown that using PRGF estimator with transfer-based prior significantly outperforms using RGF estimator in adversarial attacks, for prior-guided algorithms here we only include the historical prior case.
We found that in this task, ARS-based methods perform comparably to RGF-based ones. This could be because 1) the numbers of iterations until success of attacks are too small to show the advantage of ARS; 2) currently ARS is not guaranteed to converge faster than RGF under non-convex problems. We leave more evaluation of ARS-based methods in adversarial attacks and further improvement of their performance as future work. Experimental results show that History-PRGF is more robust to learning rate than RGF. However, a small learning rate could still lead to its deteriorated performance due to non-smoothness of the objective function. The same statement holds for ARS-based algorithms.

heading: 6 Conclusion and discussion

text:
In this paper, we present a convergence analysis on existing prior-guided ZO optimization algorithms including PRGF and History-PRGF. We further propose a novel prior-guided ARS algorithm with convergence guarantee. Experimental results confirm our theoretical analysis.
Our limitations lie in: 1) we adopt a directional derivative oracle in our analysis, so the error on the convergence bound brought by finite-difference approximation has not been clearly stated; and 2) our implementation of PARS in practice requires an approximate solution of θt, and the accuracy and influence of this approximation is not well studied yet. We leave these as future work. Other future work includes extension of the theoretical analysis to non-convex cases, and more empirical studies in various application tasks.

heading: Acknowledgements

text: This work was supported by the National Key Research and Development Program of China (No. 2020AAA0104304), NSFC Projects (Nos. 61620106010, 62061136001, 61621136008, 62076147, U19B2034, U19A2081, U1811461), Beijing NSF Project (No. JQ19016), Beijing Academy of Artificial Intelligence (BAAI), Tsinghua-Huawei Joint Research Program, a grant from Tsinghua Institute for Guo Qiang, Tiangong Institute for Intelligent Computing, and the NVIDIA NVAIL Program with GPU/DGX Acceleration.

title: On the Convergence of Prior-Guided Zeroth-Order Optimization Algorithms