  The task of approximating an arbitrary convex function arises in several
learning problems such as convex regression, learning with a difference of
convex (DC) functions, and learning Bregman or $f$-divergences. In this paper,
we develop and analyze an approach for solving a broad range of convex function
learning problems that is faster than state-of-the-art approaches. Our approach
is based on a 2-block ADMM method where each block can be computed in closed
form. For the task of convex Lipschitz regression, we establish that our
proposed algorithm converges with iteration complexity of $
O(n\sqrt{d}/\epsilon)$ for a dataset $\bm X \in \mathbb R^{n\times d}$ and
$\epsilon > 0$. Combined with per-iteration computation complexity, our method
converges with the rate $O(n^3 d^{1.5}/\epsilon+n^2 d^{2.5}/\epsilon+n
d^3/\epsilon)$. This new rate improves the state of the art rate of
$O(n^5d^2/\epsilon)$ if $d = o( n^4)$. Further we provide similar solvers for
DC regression and Bregman divergence learning. Unlike previous approaches, our
method is amenable to the use of GPUs. We demonstrate on regression and metric
learning experiments that our approach is over 100 times faster than existing
approaches on some data sets, and produces results that are comparable to state
of the art.
