Abstract: We consider the question of unconstrained optimization in certain settings, e.g., stochastic optimization, where the objective function f is unknown but can be estimated using an inexact oracle such as quasi-Monte Carlo (QMC) or numerical quadrature. The inexact oracle is assumed to yield function estimates whose error decays with an increase in oracle effort. For solving such optimization problems, we present the adaptive gradient method (AGM) in two flavors called Constant Step AGM and Backtracking Line Search AGM. AGM's salient feature is the adaptive manner in which it constructs gradient estimates — since gradient information is unavailable, AGM estimates the gradient adaptively, by exerting (only) enough oracle effort to keep the error in the gradient estimate in "lock-step" with the true gradient. We show that AGM's iterates converge to a stationary point of f under minimal conditions. We also prove two sets of results on AGM's work complexity. (i) When f is twice differentiable with Lipschitz first derivative, AGM's work complexity is shown to be arbitrarily close to O(?^{-2 - (1 / ?(?))}), where ?(?) is the error decay rate of the gradient estimate expressed as a function of the error decay rate ? of the objective function estimate. (ii) When f is twice differentiable and strongly convex with Lipschitz first derivative, AGM's work complexity is shown to be arbitrarily close to O(?^-1/?(?)). The corresponding rates in (i) and (ii) when an exact oracle for f and its gradient is available are known to be O(?^-2) and O(-log ?) respectively. We illustrate the calculation of ? and ?(?) for common choices, e.g., QMC with finite difference gradients; we also illustrate AGM through a numerical example.