In our discussion this week, we looked at a "fast and principled working set algorithm" called BlitzWS proposed by Johnson and Guestrin.
Paper link, Johnson and Guestrin, 2018
BlitzWS is a working set algorithm designed for optimizing a piecewise objective function, where each piece and also the objective function is assumed to have nice convexity properties. BlitzWS is an iterative algorithm, where during each iteration, it optimizes a relaxed objective function which is generally a simpler sub-problem to solve. By solving a sequence of such subproblems, BlitzWS converges to the original problem’s solution.
The highlight of the paper is that BlitzWS carefully constructs the relaxed objective function at each step so as to guarantee a specified amount of progress in each iteration. Further BlitzWS can be applied to a wide range of practical problems including SVM, Lasso et al.
Optimization problem and shape of the objective function
Find the minimizer of the function where
- All functions are from
- Each is a piecewise function, i.e. there is a partition so that on the j-th partition ,
- Convexity and continuity assumptions about
Assume , , are all convex and lower semicontinuous
Assume is 1-strongly-convex, i.e.
How to measure progress
In the -th iteration
- is the relaxed objective function that is minimized, which will be arranged so that
- BlitzWS computes two iterates
- which is the argmin of
- A second iterate
- Sub-optimality gap for the -th iteration is defined to be
- Let be the minimizer of . Then note that and so
- and hence decrease is progress!
In the -th iteration:
- Select progress parameter
(Note that a larger will imply a guarantee of more progress - see theorem below)
- Determine relaxed objective function which will be of the shape
where will either be or one of the pieces
- Compute , the minimizer of (i.e. solve subproblem )
- Compute second iterate to be minimizer of subject to the constraint that it lies on the line segment joining and
In the -th iteration:
- Choose any and any so that
- Run algorithm till . At this point, return
Theoretical guarantee and results
- At any time-step , BlitzWS guarantees a decrease in the sub-optimality gap controlled by the progress parameter as follows :
- BlitzWS can also be modified to accommodate approximate solutions to subproblems (instead of finding precise minimizers of )
If you like applying these kinds of methods practical ML problems, join our team.