We provide a variable metric stochastic approximation theory. In doing so, we
provide a convergence theory for a large class of online variable metric
methods including the recently introduced online versions of the BFGS algorithm
and its limited-memory LBFGS variant. We also discuss the implications of our
results for learning from expert advice.

本文提出了可变度量随机逼近理论，其中包括了在线 BFGS 算法及其有限内存 LBFGS 变体，并讨论了这一结果对学习专家建议的影响。

变量度量随机逼近理论

Variable Metric Stochastic Approximation Theory

We extend the well-known BFGS quasi-Newton method and its memory-limited
variant LBFGS to the optimization of nonsmooth convex objectives. This is done
in a rigorous fashion by generalizing three components of BFGS to
subdifferentials: the local quadratic model, the identification of a descent
direction, and the Wolfe line search conditions. We prove that under some
technical conditions, the resulting subBFGS algorithm is globally convergent in
objective function value. We apply its memory-limited variant (subLBFGS) to
L_2-regularized risk minimization with the binary hinge loss. To extend our
algorithm to the multiclass and multilabel settings, we develop a new,
efficient, exact line search algorithm. We prove its worst-case time complexity
bounds, and show that our line search can also be used to extend a recently
developed bundle method to the multiclass and multilabel settings. We also
apply the direction-finding component of our algorithm to L_1-regularized risk
minimization with logistic loss. In all these contexts our methods perform
comparable to or better than specialized state-of-the-art solvers on a number
of publicly available datasets. An open source implementation of our algorithms
is freely available.

本研究将众所周知的 BFGS 拟牛顿方法及其内存限制变种 LBFGS 扩展到非平滑凸目标的优化，提出了 subBFGS 算法，其全局收敛，并使用其记忆限制变体（subLBFGS）来最小化 L2 正则化风险并开发了新的多类和多标签设置下的准确搜索算法。