Abstract
This paper summarizes the doctoral research of Andrew Cotter at the Toyota Technological Institute at Chicago on stochastic optimization techniques for large-scale machine learning. The work focuses on two primary areas: improving the training and deployment efficiency of Support Vector Machines (SVMs) through the Stochastic Batch Perceptron (SBP) and optimizing Principal Component Analysis (PCA) via the Capped Matrix Stochastic Gradient (MSG) algorithm. The proposed methods achieve state-of-the-art accuracy with reduced computational overhead and improved model sparsity.
1. Introduction
In the era of Big Data, traditional "batch" processing algorithms face significant bottlenecks in training time and deployment efficiency. For Support Vector Machines (SVMs), model complexity often scales with dataset size, leading to "heavy" models unsuitable for resource-constrained environments. Similarly, principled PCA algorithms often suffer from high memory requirements. This research addresses these challenges by refining stochastic optimization techniques to bridge the gap between theoretical rigor and practical efficiency.
2. Support Vector Machines: The Stochastic Batch Perceptron
The first part of the research introduces the Stochastic Batch Perceptron (SBP) for training SVMs. Unlike traditional methods that use fixed penalty weights for errors, SBP employs a "slack-constrained" objective.
2.1 Slack-Constrained Optimization
By maximizing the classification margin while maintaining the total error (slack) within a predefined budget, SBP achieves a convergence rate of $1/\epsilon$ in separable or "easy" regimes. This represents a significant improvement over the $1/\epsilon^2$ rate of standard methods like Pegasos, providing a massive speedup for datasets that are mostly separable.
2.2 Optimal Sparsification
To address deployment bottlenecks, a post-processing step is introduced. By applying subgradient descent to a "slant-loss" function, a dense SVM can be compressed into a sparse model with fewer support vectors. Crucially, this sparsification does not compromise generalization accuracy, proving that model sparsity can be decoupled from the desired error level ($\epsilon$). This allows for highly accurate models that remain extremely lightweight for use on mobile or embedded devices.
3. Principal Component Analysis: Capped MSG
The second part of the thesis focuses on PCA, introducing the Capped Matrix Stochastic Gradient (MSG) algorithm.
3.1 Addressing Memory Bottlenecks
Standard principled PCA algorithms track large internal matrices, making them computationally expensive. Capped MSG introduces a hard rank constraint, keeping the internal state small and fast. This approach mimics the speed of heuristic incremental algorithms while maintaining the stability and reliability of convex optimization. By "capping" the rank, the algorithm discards noise early in the process, focusing computational resources on the true principal components.
4. Experimental Evaluation
The proposed algorithms were evaluated against several benchmark datasets, including Reuters, Adult, MNIST, Forest, and TIMIT for SVMs, and simulated/MNIST data for PCA.
4.1 SVM Performance and Compression
On the "Adult" census dataset, SBP converged significantly faster than standard SGD or dual decomposition methods. Furthermore, the sparsification procedure yielded models with support sizes orders of magnitude smaller than those from standard solvers, facilitating deployment on low-power devices.
4.2 PCA Stability and Efficiency
On the MNIST dataset, Capped MSG demonstrated a "best of both worlds" performance. It matched the speed of the fastest heuristic methods while avoiding the stability issues (e.g., getting stuck in local minima) that often affect simpler incremental approaches.
5. Conclusion and Future Work
This research demonstrates that stochastic optimization can significantly enhance the practicality of fundamental machine learning tools. While Capped MSG performs well, its non-convex nature presents theoretical challenges for formal convergence proofs. Future work includes developing methods to generate sparse models directly without a reference model and extending these "slack-constrained" and "capped" philosophies to non-linear models and deep learning architectures.
Summary updated