Bundle Methods for Regularized Risk Minimization

by Choon Hui Teo, S.V.N. Vishwanathan, Alex Smola and Quoc V. Le

This paper introduces a bundle methods for RRM. In optimization, the standard optimization technique that derives bundle method is cutting plane method.

In cutting plane methods, the convex functions are bounded from below by a series of cutting planes, constructed via subgradients. If we have many of them, they may reduce the space to search for optima. And actually, we select the next point using w_t = \arg\min_w J_t^\text{CP} (w) where J_t^\text{CP}(w) = \max_{i} J(w_{i-1}) + \langle w - w_{i-1}, s_i \rangle.

The cutting plane method suffers from slow convergence. Bundle methods improve it with proximal functions (basically quadratic functions to approximate the objective function). There are several ways of constructing the proximal functions:

• proximal: w_t = \arg\min_w \frac{\zeta_t}{2} \| w - \hat{w}_{t-1} \|^2 + J_t^\text{CP} (w)
• trust region: w_t = \arg\min_w \{ J_t^\text{CP}(w) \mid \frac{1}{2} \|w - \hat{w}_{t-1} \|^2 \leq \kappa_t\}
• level set: w_t = \arg\min_w \{ \frac{1}{2} \| w - \hat{w}_{t-1} \|^2 \mid J_t^\text{CP} (w) \leq \tau_t\}

This paper proposed another bundle methods, yielding a O(log(1/\epsilon)) convergence bound. It has several variant, one of which doesn't involve line search.

Unfortunately, yourequation.com is down due to heavy request. I have to switch to another equation rendering method ASAP.