  


The Adaptive Sampling Gradient Method: Optimizing Smooth Functions with an Inexact Oracle
Fatemeh Hashemi(fatemehvt.edu) Abstract: Consider settings such as stochastic optimization where a smooth objective function $f$ is unknown but can be estimated with an \emph{inexact oracle} such as quasiMonte Carlo (QMC) or numerical quadrature. The inexact oracle is assumed to yield function estimates having error that decays with increasing oracle effort. For solving such problems, we present the Adaptive Sampling Gradient Method (ASGM) in two flavors depending on whether the step size used within ASGM is constant or determined through a backtracking line search. ASGM's salient feature is the adaptive manner in which it constructs gradient estimates (henceforth called \emph{gradient approximates}), by exerting just enough oracle effort at each iterate to keep the error in the gradient approximate within a constant factor of the norm of the gradient approximate. ASGM applies to both derivativebased and derivativefree contexts, and generates iterates that globally convergence to a firstorder critical point. We also prove two sets of results on ASGM's \emph{work complexity} with respect to the gradient norm: (i) when $f$ is nonconvex, ASGM's work complexity is arbitrarily close to $\mathcal{O}(\epsilon^{2  \frac{1}{\mu(\alpha)}})$, where $\mu(\alpha)$ is the error decay rate of the gradient approximate expressed in terms of the error decay rate $\alpha$ of the objective function approximate; (ii) when $f$ is strongly convex, ASGM's work complexity is arbitrarily close to $\mathcal{O}(\epsilon^{ \frac{1}{\mu(\alpha)}})$. We compare these complexities to those obtained from methods that use traditional random sampling. We also illustrate the calculation of $\alpha$ and $\mu(\alpha)$ for common choices, e.g., QMC with finitedifference derivatives. Keywords: Adaptive Sampling, Stochastic Gradient, Stochastic Optimization Category 1: Stochastic Programming Category 2: Other Topics (Optimization of Simulated Systems ) Category 3: Nonlinear Optimization (Other ) Citation: Download: [PDF] Entry Submitted: 05/29/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  