zbMATH — the first resource for mathematics

Efficient online and batch learning using forward backward splitting. (English) Zbl 1235.62151
Summary: We describe, analyze, and experiment with a framework for empirical loss minimization with regularization. Our algorithmic framework alternates between two phases. On each iteration we first perform an unconstrained gradient descent step. We then cast and solve an instantaneous optimization problem that trades off minimization of a regularization term while keeping close proximity to the result of the first phase. This view yields a simple yet effective algorithm that can be used for batch penalized risk minimization and online learning. Furthermore, the two phase approach enables sparse solutions when used in conjunction with regularization functions that promote sparsity, such as \(l_{1}\). We derive concrete and very simple algorithms for minimization of loss functions with \(l_{1}\), \(l_{2}\), \(l_{2}^{2}\), and \(l_{\infty}\) regularization. We also show how to construct efficient algorithms for mixed-norm \(l_{1}/l_{q}\) regularization. We further extend the algorithms and give efficient implementations for very high-dimensional data with sparsity. We demonstrate the potential of the proposed framework in a series of experiments with synthetic and natural data sets.

62P99 Applications of statistics
68T05 Learning and adaptive systems in artificial intelligence
90C25 Convex programming
65C60 Computational problems in statistics (MSC2010)
90C90 Applications of mathematical programming
Full Text: Link