Proximal regularization for online and batch learning

Many learning algorithms rely on the curvature
(in particular, strong convexity) of regularized
objective functions to provide good theoretical
performance guarantees. In practice, the choice
of regularization penalty that gives the best testing
set performance may result in objective functions
with little or even no curvature. In these
cases, algorithms designed specifically for regularized
objectives often either fail completely or
require some modification that involves a substantial
compromise in performance.
We present new online and batch algorithms for
training a variety of supervised learning models
(such as SVMs, logistic regression, structured
prediction models, and CRFs) under conditions
where the optimal choice of regularization parameter
results in functions with low curvature.
We employ a technique called proximal regularization,
in which we solve the original learning
problem via a sequence of modified optimization
tasks whose objectives are chosen to have greater
curvature than the original problem. Theoretically,
our algorithms achieve low regret bounds
in the online setting and fast convergence in the
batch setting. Experimentally, our algorithms
improve upon state-of-the-art techniques, including
Pegasos and bundle methods, on medium and
large-scale SVM and structured learning tasks.