A Quasi-Newton Approach to Nonsmooth Convex Optimization Problems in Machine Learning

By Jin Yu, S. V. N. Vishwanathan, Simon Günter, N. Schraudolph. 2008

81 citations recorded by the source corpus.

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 L2-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 L1-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 data sets. An open source implementation of our algorithms is freely available.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “OWN-QN (Yu et al., 2010) is a quasi-Newton method optimized in Spark’s spark.ml package (Meng et al., 2016).”
An Introduction to Conditional Random Fields (2010, background): “A disadvantage of the L1 regularizer is that it is not differentiable at 0, which complicates numerical parameter estimation somewhat [37, 3, 138].”
Sub-Sampled Newton Methods I: Globally Convergent Algorithms (2016, methodology): “In such methods a subset S ⊂ { 1 , 2 , · · · , n } is chosen at random and the update is obtained by”
The Self-Normalized Estimator for Counterfactual Learning (2015, background): “The choice of L-BFGS for non-convex and non-smooth optimization is well supported [25, 26].”
A Comparison of Optimization Methods and Software for Large-scale L1-regularized Linear Classification (2010, unknown): “Yu et al. (2010) proposed a quasi Newton approach to solve non-smooth convex optimization problems.”
Counterfactual Risk Minimization (2015, methodology): “While the objective in Equation (7) is not convex in w (even for λ = 0), prior work (Yu et al., 2010), (Lewis & Overton, 2013) has established theoretically sound modifications to L-BFGS for non-zmooth non-convex optimization.”
Batch learning from logged bandit feedback through counterfactual risk minimization (2015, background): “In particular, prior work (Yu et al., 2010; Lewis and Overton, 2013) has established theoretically sound modiﬁcations to L-BFGS for non-smooth non-convex optimization.”