版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、From Complexity to Simplicity: Adaptive ES-Active Subspaces for Blackbox Optimization Krzysztof Choromanski Google Brain Robotics kchoro Aldo Pacchiano UC Berkeley Jack Parker-Holder University of Oxford jackphrobots.ox.ac.uk Yunhao Tang Columbia University V
2、ikas Sindhwani Google Brain Robotics sindhwani Abstract We present a new algorithm (ASEBO) for optimizing high-dimensional blackbox functions.ASEBOadapts to the geometry of the function and learns optimal sets of sensing directions, which are used to probe it, on-the-fl y. It addresses the explorati
3、on-exploitation trade-off of blackbox optimization with expensive black- box queries by continuously learning the bias of the lower-dimensional model used to approximate gradients of smoothings of the function via compressed sensing and contextual bandits methods. To obtain this model, it leverages
4、techniques from the emerging theory of active subspaces 8 in a novel ES blackbox optimization con- text. As a result,ASEBOlearns the dynamically changing intrinsic dimensionality of the gradient space and adapts to the hardness of different stages of the optimiza- tion without external supervision.
5、Consequently, it leads to more sample-effi cient blackbox optimization than state-of-the-art algorithms. We provide theoretical results and testASEBOadvantages over other methods empirically by evaluating it on the set of reinforcement learning policy optimization tasks as well as functions from the
6、 recently open-sourced Nevergrad library. 1Introduction Consider a high-dimensional functionF : Rd! R. We assume that querying it is expensive. Examples include reinforcement learning (RL) blackbox functions taking as inputs vectorsencoding policies : S ! Amapping states to actions and outputting to
7、tal (expected/discounted) rewards obtained by agents applyingin given environments 6. For this class of functions evaluations usually require running a simulator. Other examples include wind confi guration design optimization problems for high speed civil transport aircrafts, optimizing computer cod
8、es (e.g. NASA synthetic toolFLOPS/ENGENNused to size the aircraft and propulsion system 2), crash tests, medical and chemical reaction experiments 37. Evolution strategy (ES) methods have traditionally been used in low-dimensional regimes (e.g. hyperparameter tuning), and considered ill-equipped for
9、 higher dimensional problems due to poor sampling complexity 27 . However, a fl urry of recent work has shown they can scale better than previously believed 33, 11, 29, 25, 7, 30, 21. This is thanks to a couple of reasons. First of all, new ES methods apply several effi cient heuristics (fi ltering,
10、 various normalization techniques as in 25 and new exploration strategies as in 11) in order to substantially improve Equal contribution. 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada. sampling complexity. Other recent methods 29,7 are based on more accur
11、ate Quasi Monte Carlo (MC) estimators of the gradients of Gaussian smoothings of blackbox functions with theoretical guarantees. These approaches provide better quality gradient sensing mechanisms. Additionally, in applications such as RL, new compact structured policy architectures (such as low-dis
12、placement rank neural networks from 7 or even linear policies 14) are used to reduce the number of policies parameters and dimensionality of the optimization problem. Recent research also shows that ES-type blackbox optimization in RL leads to more stable policies than policy gradient methods since
13、ES methods search for parameters that are robust to perturbations 19 . Unlike policy gradient methods, ES aims to fi nd parameters maximizing expected reward (rather than just a reward) in respect to Gaussian perturbations. Finally, pure ES methods as opposed to state-of-the-art policy optimization
14、techniques (TRPO,PPO orARS32,15,31,25), can be applied also for blackbox optimization problems that do not exhibit MDP structure required for policy gradient methods and cannot benefi t from state normalization algorithm central toARS. This has led to their recent popularity for non-differentiable t
15、asks 17,14. In this paper we introduce a new adaptive sample-effi cient blackbox optimization algorithm.ASEBO adapts to the geometry of blackbox functions and learns optimal sets of sensing directions, which are used to probe them, on-the-fl y. To do this, it leverages techniques from the emerging t
16、heory of active subspaces 8,10,9,20 in a novel ES blackbox optimization context. Active subspaces and their extensions are becoming popular as effective techniques for dimensionality reduction (see for instance: active manifolds 5 or ResNets for learning isosurfaces 36). However, to the best of our
17、knowledge we are the fi rst to apply active subspace ideas for ES optimization. ASEBOaddresses the exploration-exploitation trade-off of blackbox optimization with expensive function queries by continuously learning the bias of the lower-dimensional model used to approx- imate gradients of smoothing
18、s of the function with compressed sensing and contextual bandits methods. The adaptiveness is what distinguishes it from some recently introduced guided ES methods such as 24 that rely on fi xed hyperparameters that are hard to tune in advance (e.g. the length of the buffer defi ning lower dimension
19、al space for gradient search). We provide theoretical results and empirically evaluateASEBOon a set of RL blackbox optimization tasks as well as non-RL blackbox functions from the recently open-sourcedNevergradlibrary 34, showing that it consistently learns optimal inputs with fewer queries to a bla
20、ckbox function than other methods. ASEBOversusCMA-ES:Therehavebeenavarietyofworksseekingtoreducesamplingcomplexity for ES methods through the use of metric learning. The prominent class of the covariance matrix adaptation evolution strategy (CMA-ES) methods derives state-of-the-art derivative free b
21、lackbox optimization algorithms, which seek to learn and maintain a fully parameterized Gaussian distribution. CMA-ES suffers from quadratic time complexity for each evaluation which can be limiting for high dimensional problems. As such, a series of attempts have been made to produce scalable varia
22、nts of CMA-ES, by restricting the covariance matrix to the diagonal (sep-CMA-ES 28) or a low rank approximation as in VD-CMA-ES 3 and LM-CMA-ES 22. Two recent algorithms, VkD-CMA-ES 4 and LM-MA-ES 23, seek to combine the above ideas and have been shown to be successful in large-scale settings, inclu
23、ding RL policy learning 26. Although these methods are able to quickly learn and adapt the covariance matrix, they are heavily dependent on hyperparameter selection 4,35 and lack the means to avoid learning a bias. As our experiments show, this can severely hurt their performance. The best CMA-ES va
24、riants often struggle with RL tasks of challenging objecive landscapes, displaying inconsistent performance across tasks. Furthermore, they require careful hyperparameter tuning for good performance (see: analysis in Section 4, Fig. 3). 2 Adaptive Sample-Effi cient Blackbox Optimization Before we de
25、scribeASEBO, we explain key theoretical ideas behind the algorithm.ASEBOuses onlinePCA to maintain and update on-the-fl y subspaces which we call ES-active subspacesLES active, accurately approximating the gradient data space at a given phase of the algorithm. The bias of the obtained gradient estim
26、ators is measured by sensing the length of its component from the orthogonal complementLES,? activevia compressed sensing or computing optimal probabilities for exploration (e.g. sensing fromLES,? active) via contextual bandits methods 1. The algorithm corrects its probabilistic distributions used f
27、or choosing directions for gradient sensing based on these measurements. As we show, we can measure that bias accurately using only a constant number of additional function 2 (a) HC: active subspace(b)SW:active subspace(c) HC: # of samples(d) SW: # of samples Figure 1: The motivation behindASEBO . T
28、wo fi rst plots: ES baseline forHalfCheetahand Swimmertasks from theOpenAI Gymlibrary for212-dimensional policies - the plot shows how the dimensionality of the space capturing a given percentage of variance of approximate gradient data depends on the iteration of the algorithm. This information is
29、never exploited by the algorithm, even though99.5%of the variance resides in the much lower-dimensional space (100dimensions). Two last plots: ASEBO taking advantage of this information (# of sample/sensing directions refl ects the hardness of the optimization at each iteration and is strongly corre
30、lated with thePCAdimensionality. queries, regardless of the dimensionality. This in turn determines an exploration strategy, as we explain later. Estimated gradients are then used to update parameters. 2.1Preliminaries Consider a blackbox functionF : Rd! R. We do not assume thatFis differentiable. T
31、he Gaussian smoothing 27F?ofFparameterized by smoothing parameter? 0is given as: F?() = Eg2N(0,Id)F( +?g) = (2)? d 2 R Rd F( +?g)e? kgk2 2 dg.The gradient of the Gaussian smoothing of F is given by the formula: rF?() = 1 ? EgN(0,Id)F( + ?g)g.(1) Formula 1 onrF?()leads straightforwardly to several un
32、biased Monte Carlo (MC) estimators ofrF?() , where the most popular ones are: the forward fi nite difference estimator 7 defi ned as: b rFD MCF?() = 1 k? Pk i=1(F( + ?gi) ? F()gi,and an antithetic ES gradient estimator 30 given as: b rAT MCF?() = 1 2k? Pk i=1(F( + ?gi) ? F( ? ?gi)gi, where typically
33、g1,.,gkare taken independently at random fromN(0,Id)of from more complex joint distributions for variance reduction (see: 7). We call samplesg1,.,gkthe sensing directions since they are used to sense gradientsrF?(). The antithetic formula can be alternatively rationalized as giving the renormalized
34、gradient ofF(ifFis smooth), if not taking into account cubic and higher-order terms of the Taylor expansionF( +v) = F()+rFv+ 1 2v H()v (whereH()stands for the Hessian ofFin). Standard ES methods apply different gradient-based techniques such asSGDorAdam, fed with the above MC estimators ofrF?to cond
35、uct blackbox optimization. The number of sampleskper iteration of the optimization procedure is usually of the orderO(d). This becomes a computational bottleneck for high-dimensional blackbox functionsF(for instance, even for relatively small RL tasks with policies encoded by compact neural networks
36、 we still have d 100 parameters). 2.2ES-active subspaces via online PCA with decaying weights The fi rst idea leading to theASEBOalgorithm is that in practice one does not need to estimate the gradient ofFaccurately (after all ES-type methods do not even aim to compute the gradient ofF, but rather f
37、ocus onrF?). Poor scalability of ES-type blackbox optimization algorithms is caused by high- dimensionality of the gradient vector. However, during the optimization process the space spanned by gradients may be locally well approximated by a lower-dimensional subspaceLand sensing the gradient in tha
38、t subspace might be more effective. In some recent papers such as 24 such a subspace is defi ned simply asL = spanbrAT MCF?(i), b rAT MCF?(i?1),., b rAT MCF?(i?s+1), where brAT MCF?(i), b rAT MCF?(i?1),., b rAT MCF?(i?s+1) stands for the batch of lastsapproximated gradients during the optimization p
39、rocess ands is a fi xed hyperparameter. Even thoughLwill dynamically change during the optimization, such an approach has several disadvantages in practice. Tuning parameters is very diffi cult or almost impossible and the assumption that the dimensionality ofLshould be constant during optimization
40、is usually false. In our approach, dimensionality ofL varies and depends on the hardness of the optimization in different optimization stages. 3 We apply Principal Component Analysis (PCA, 18) to create a subspaceLcapturing particular variance? 0of the approximate gradients data. This data is either
41、: the approximate gradients computed in previous iterations from the antithetic formula or: the elements of the sum from that equation that are averaged over to obtain these gradients. For clarity of the exposition, from now on we will assume the former, but both variants are valid. Choosing ? is in
42、 practice much easier than s and leads to subspacesLof varying dimensionalities throughout the optimization procedure, called by us from now on ES-active subspaces LES active. Algorithm 1 ASEBO Algorithm Hyperparameters:number of iterations of full samplingl, smoothing parameter? 0, step size, PCA t
43、hreshold , decay rate ?, total number of iterations T. Input: blackbox function F, vector 02 Rdwhere optimization starts. Cov02 0dd, p0= 0. Output: vector T. for t = 0,.,T ? 1 do if t ) and with probability ptfrom N(0,Uact(Uact). 4. Renormalize g1,.,gntsuch that marginal distributions kgik2are ?(d).
44、 1. Compute b rAT MCF(t) as: b rAT MCF(t) = 1 2nt? Pnt j=1(F(t+ gj) ? F(t? gj)gj. 2. Set Covt+1= ?Covt+ (1 ? ?)?, where ? = b rAT MCF?(t)(b rAT MCF?(t) . 3. Set pt+1= poptfor poptoutput by Algorithm 2 and: t+1 t+ brAT MCF(t). These will be in turn applied to defi ne covariance matrices encoding prob
45、abilistic distributions applied to construct sensing directions used for estimatingrF?(). The additional advantage of our approach is that PCA automatically fi lters out gradient noise. We use our own online version ofPCA with decaying weights (decay rate is defi ned by parameter ? 0). By tuning? we
46、 can defi ne the rate at which historical approximate gradient data is used to choose the right sensing directions, which will continuously decay. We consider a stream of approximate gradients b rAT MCF?(0),.b rAT MCF?(i),.obtained during the optimization procedure. We maintain and update on-the-fl
47、y the covariance matrixCovt, wheretstands for the number of completed iterations, in the form of the symmetric matrixSVD-decompositionCovt= Q t tQt2 Rd. When the new approximate gradient b rAT MCF?(t)arrives, the update of the covariance matrix is driven by the following equation, refl ecting data d
48、ecay process, where xt= b rAT MCF?(t): Q t+1t+1Qt+1= ?Q t tQt+ (1 ? ?)xtx t ,(2) To conduct the update cheaply, it suffi ces to observe that the RHS of Equation 2 can be rewritten as:?Q t tQt+ (1 ? ?)xtx t = Q t (?t+ (1 ? ?)Qtxt(Qtxt)Qt. Now, using the fact that for a matrix of the formD + uu, we ca
49、n get its decomposition in timeO(d2)13, we obtain an algorithm performing updates in quadratic time. That in practice suffi ces since the bottleneck of the computations is in querying F and additional overhead related to updating LES activeis negligible. ES-active subspaces versus active subspaces:O
50、ur mechanism for constructingLES activeis inspired by the recent theory of active subspaces 8, developed to determine the most important directions in the space of input parameters of high-dimensional blackbox functions such as computer simulations. The active subspace of a differentiable functionF
51、: Rd! R, square-integrable with respect to the given probabilistic density function : Rd! R, is given as a linear subspaceLactive defi ned by the 4 fi rst r (for a fi xed r (x)dx(3) Density functiondetermines where compact representation ofFis needed. In our approach we do not assume that rF exists,
52、 but the key difference between LES activeand Lactivelies somewhere else. The goal ofASEBOis to avoid approximating the exact gradientrF(x) 2 Rdwhich is what makes standard ES methods very expensive and which is done in 9 via gradient sketching techniques combined with fi nite difference approaches
53、(standard methods of choice for ES baselines). Algorithm 2 Explore estimator via exponentiated sampling Hyperparameters:smoothing parameter?, horizonC, learning rate, probability regularizer?, initial probability parameter qt 02 (0,1). Input: subspaces: LES active, L ES,? active, function F, vector
54、t Output: for l = 1, ,C + 1 do 1. Compute pt l?1 = (1 ? 2?)qt l?1+ ? and sample a t l Ber(pt l). 3. If at l = 1, sample gl N(0,?ILES active), otherwise sample gl N(0,?ILES,? active). 4. Compute vl= 1 2? (F(t+ gl) ? F(t? gl). 5. Set el= (1 ? 2?) 2 4 ?a t l(dim(L ES active)+2) (pt l)3 ? (1?at l)(dim(L
55、 ES,? active)+2) (1?pt l)3 3 5v2 l. 6. Set qt l = qt l?1exp(?el(1) qt l?1exp(?el(1)+(1?q t l?1)exp(?el(2). Return: pC. Instead, inASEBOan ES-active subspaceLES active is itself used to defi ne sensing directions and the number of chosen sampleskis given by the dimensionality ofLES active. This drast
56、ically reduces sampling complexity, but comes at a price of risking the optimization to be trapped in the fi xed lower-dimensional space that will not be representative for gradient data as optimization progresses. We propose a solution requiring only a constant number of extra queries to F in the n
57、ext sections. 2.3Exploration-exploitation trade-off: Adaptive Exploration Mechanism The procedure described above needs to be accompanied with an exploration strategy that will determine how frequently to choose sensing directions outside the constructed on-the-fl y lower- dimensional ES-subspaceLES
58、 active. Our exploration strategies will be encoded by hybrid probabilistic distributions for sampling sensing directions. The frequency of sensing from the distributions with covariance matrices obtained fromLES active(corresponding to exploitation) and from its orthogonal complementLES,? activeor
59、entire space (corresponding to exploration) will be given by weights encoding the importance of exploitation versus exploration in any given iteration of the optimization. For a vectorx 2 Rddenote byxactiveits projection ontoLES active and byx?its projection ontoLES,? active. The useful metric that can be used to update the above weights in an online manner in thetthit
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学五年级语文《驴子和它的影子》教学设计
- 高中一年级思想政治新学期新征程新成长主题班会教学设计
- 高中信息技术必修2《第二单元 信息系统的硬件与软件 项目三 分析电子点餐信息系统-认识计算机与移动终端》教学设计
- 小学一年级德育教案:美丽的祖国主题班会深度教学设计
- 高中政治选择性必修三《逻辑与思维》第6.3节 复合判断的演绎推理方法 教学设计
- 高中地理必修第二册“人类面临的环境问题与可持续发展”单元教学设计
- 统编版小学六年级语文上册《开国大典》教学设计
- 高中化学必修第一册《物质的量与摩尔质量》教学设计
- 初中语文七年级《赫耳墨斯和雕像者》寓言教学创新设计
- 小学五年级英语Unit1 Different friends分层语境教学设计
- 应急维修动力照明火灾自动报警施工方案
- 2025宁波银行总行金融科技部校园招聘笔试历年典型考题及考点剖析附带答案详解
- TCCAATB 0080-2025民用机场旅客随身携带行李的卡控服务
- 反恐防范宣传课件
- 脑卒中神经内科诊疗与防治要点
- 肿瘤药物给药顺序及解毒剂
- 上海奉贤区区属国有企业招聘笔试题库2025
- 建筑挡烟垂壁设计图集
- 设计素描分割重构方法
- 教育部人文社会科学重大项目标书3
- 风光储储能项目PCS舱、电池舱吊装方案
评论
0/150
提交评论