Support Vector Machines (SVMs) are foundational tools in machine learning, but extending them from binary to multiclass classification introduces significant computational challenges. Among the various multiclass extensions, the Weston-Watkins (WW-SVM) is frequently cited as one of the best-performing models in terms of accuracy.
However, training a WW-SVM efficiently has historically been a bottleneck. In the ICML 2021 paper "An Exact Solver for the Weston-Watkins SVM Subproblem," researchers Yutong Wang and Clayton Scott introduce Walrus, the first algorithm to exactly solve the subproblems within the WW-SVM in $O(k \log k)$ time. By replacing previous approximate, iterative methods with this exact analytic solver, the authors achieved significant speedups for datasets with many classes and provided the first formal proof of linear convergence for this popular SVM variant.
The Challenge of Multiclass SVMs
State-of-the-art solvers for large-scale linear classification typically use Block Coordinate Descent (BCD). This approach breaks the massive overall optimization problem into thousands of tiny "subproblems"—essentially one for each data point in the training set.
For other SVM variants, like the Crammer-Singer SVM, researchers have developed fast, exact ways to solve these subproblems. But for the WW-SVM, the complex multiclass constraints meant that practitioners had to rely on iterative, approximate solvers (such as the one implemented in the Shark machine learning library). These approximations suffer from two major drawbacks:
- They are slow when the number of classes ($k$) is large.
- They make it theoretically difficult to prove how fast the overall training algorithm will converge.
The Walrus Algorithm
To overcome these limitations, the authors propose Walrus (WW-subproblem analytic log-linear runtime solver). The key technical innovation is a novel reparametrization of the WW dual problem.
- Simplification: The authors transform the complex multiclass constraints of the WW-SVM into a simpler quadratic program.
- The "Sweep" Strategy: They demonstrate that the optimal solution to the subproblem can be found by examining a finite set of "discontinuity points." By sorting these points—which takes $O(k \log k)$ time—the algorithm can "sweep" through them to find the exact minimizer analytically.
- Integration: Walrus was implemented in C++ and integrated into the LIBLINEAR framework, the industry standard for large-scale linear classification, making it immediately useful for practical applications.
Empirical Results
The researchers evaluated Walrus on eight standard multiclass benchmark datasets from the LIBSVM repository, spanning a wide range of class counts ($k$), from small (e.g., SATIMAGE with $k=6$) to massive (e.g., ALOI with $k=1,000$).
Scaling with Classes
The most significant finding is that the performance gap between Walrus and iterative solvers grows as the number of classes increases. For small $k$, the solvers are comparable. However, Walrus becomes the clear winner as the problem becomes more complex.
On the ALOI dataset ($k=1,000$), Walrus was more than twice as fast as the previous state-of-the-art solver (Shark), reducing training time from 393 seconds to 188 seconds. Furthermore, Walrus tends to be much faster during the early iterations of training, which is often where the bulk of the "learning" happens in practical applications.
Theoretical Contributions & Future Work
Beyond empirical speedups, Walrus closes a significant gap in optimization theory. Because Walrus provides an exact solution to the subproblem, the authors were able to rigorously prove linear convergence for the overall BCD algorithm. This confirms a long-standing assertion in the field that BCD for WW-SVM should converge linearly—a fact that could not be proven while relying on approximate sub-solvers.
While Walrus represents a major step forward, the authors note a few limitations and avenues for future research:
- Linear vs. Kernel: This work focuses specifically on linear SVMs. Adapting the Walrus solver for kernel WW-SVMs (used for non-linear decision boundaries) remains a primary goal for future research.
- Late-Stage Optimization: In the very final stages of optimization, when trying to reach extreme precision, iterative solvers can sometimes be faster because they can "warm start" from the previous iteration's guess. Walrus, being an exact solver, performs the same $O(k \log k)$ sorting work every time.
- Complexity Bounds: A remaining theoretical question is whether a solver can be built that runs even faster than $O(k \log k)$, perhaps by avoiding the sorting step entirely.
Ultimately, Walrus provides both a practical tool for faster multiclass classification and a theoretical foundation that solidifies our understanding of the Weston-Watkins SVM.
Summary updated