Eftersom tillämpningskraven för noll-order (gradientfri) optimering accelererar, ökar också behovet av variansminskande och snabbare konvergerande metoder. Detta papper behandlar dessa utmaningar genom att presentera: a) en omfattande teoretisk analys av varians reducerade noll-ordning (ZO) optimering, b) en ny varians reducerade ZO algoritm, kallas ZO-SVRG, och c) en experimentell utvärdering av vår strategi i samband med två övertygande tillämpningar, svart-box kemisk material klassificering och generering av kontradiktoriska exempel från svart-box djupa neurala nätverk modeller. Vår teoretiska analys avslöjar en väsentlig svårighet i analysen av ZO-SVRG: det opartiska antagandet om gradientberäkningar håller inte längre. Vi bevisar att jämfört med sin första ordningen motsvarighet, ZO-SVRG med en två-punkts slumpmässig gradient uppskattning kan lida ett ytterligare fel i ordning O(1/b), där b är mini-batch storlek. För att minska detta fel, föreslår vi två accelererade versioner av ZO-SVRG utnyttjar varians reducerade gradient estimatorer, som uppnår den bästa hastigheten känd för ZO stokastisk optimering (i termer av iterationer). Våra omfattande experimentella resultat visar att våra metoder överträffar andra toppmoderna ZO-algoritmer och balanserar konvergensgraden och funktionsförfrågans komplexitet.
REF förbättrade ytterligare ZOO med en noll-order stokastisk varians reducerad gradient uppskattning.
Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}