  Many important computer vision tasks are naturally formulated to have a
non-differentiable objective. Therefore, the standard, dominant training
procedure of a neural network is not applicable since back-propagation requires
the gradients of the objective with respect to the output of the model. Most
deep learning methods side-step the problem sub-optimally by using a proxy loss
for training, which was originally designed for another task and is not
tailored to the specifics of the objective. The proxy loss functions may or may
not align well with the original non-differentiable objective. An appropriate
proxy has to be designed for a novel task, which may not be feasible for a
non-specialist. This thesis makes four main contributions toward bridging the
gap between the non-differentiable objective and the training loss function.
Throughout the thesis, we refer to a loss function as a surrogate loss if it is
a differentiable approximation of the non-differentiable objective. Note that
we use the terms objective and evaluation metric interchangeably.
  The contributions of this thesis make the training of neural networks more
scalable -- to new tasks in a nearly labor-free manner when the evaluation
metric is decomposable, which will help researchers with novel tasks. For
non-decomposable evaluation metrics, the differentiable components developed
for the recall@k surrogate, such as sorting and counting, can also be used for
creating new surrogates.
