  We consider minimizing functions for which it is expensive to compute the
(possibly stochastic) gradient. Such functions are prevalent in reinforcement
learning, imitation learning and adversarial training. Our target optimization
framework uses the (expensive) gradient computation to construct surrogate
functions in a \emph{target space} (e.g. the logits output by a linear model
for classification) that can be minimized efficiently. This allows for multiple
parameter updates to the model, amortizing the cost of gradient computation. In
the full-batch setting, we prove that our surrogate is a global upper-bound on
the loss, and can be (locally) minimized using a black-box optimization
algorithm. We prove that the resulting majorization-minimization algorithm
ensures convergence to a stationary point of the loss. Next, we instantiate our
framework in the stochastic setting and propose the $SSO$ algorithm, which can
be viewed as projected stochastic gradient descent in the target space. This
connection enables us to prove theoretical guarantees for $SSO$ when minimizing
convex functions. Our framework allows the use of standard stochastic
optimization algorithms to construct surrogates which can be minimized by any
deterministic optimization method. To evaluate our framework, we consider a
suite of supervised learning and imitation learning problems. Our experiments
indicate the benefits of target optimization and the effectiveness of $SSO$.
