Quantum annealing is a heuristic quantum algorithm which exploits quantum resources
to minimize an objective function embedded as the energy levels of a programmable
physical system. To take advantage of a potential quantum advantage, one needs to
be able to map the problem of interest to the native hardware with reasonably low
overhead. Because experimental considerations constrain our objective function to
take the form of a low degree PUBO (polynomial unconstrained binary optimization),
we employ non-convex loss functions which are polynomial functions of the margin.
We show that these loss functions are robust to label noise and provide a clear
advantage over convex methods. These loss functions may also be useful for
classical approaches as they compile to regularized risk expressions which can be
evaluated in constant time with respect to the number of training examples.