Overview
Pegasos (Primal Estimated sub-GrAdient SOlver for SVM) is a stochastic subgradient descent algorithm for efficiently training linear Support Vector Machines (SVMs). Developed by Shai Shalev-Shwartz, Yoram Singer, and Nathan Srebro in 2007, it solves the primal formulation of the SVM optimization problem using a constant learning rate and a projection step to enforce the margin constraint. Pegasos is known for its simplicity, low per-iteration cost, and strong theoretical convergence guarantees, making it a popular choice for large-scale binary classification tasks in applied machine learning.
1 Background
1.1 Support Vector Machines
A Support Vector Machine (SVM) is a supervised learning model used for binary classification. It finds a hyperplane in the feature space that separates data points of two classes with the largest possible margin. SVM training involves solving a convex optimization problem that balances margin maximization against a penalty for misclassified points.
1.1.1 Primal vs Dual Formulation
The SVM problem can be expressed in two equivalent forms. The primal formulation directly minimizes a regularized risk function over the weight vector w and bias *b*:
\[
| \min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \max(0, 1 - y_i (\mathbf{w}^\top \mathbf{x}_i + b)) |
|---|
\]
where \(C\) is a regularization parameter and \(y_i \in \{-1, +1\}\). The dual formulation introduces Lagrange multipliers and expresses the decision function in terms of dot products between support vectors. Traditionally, dual solvers (e.g., SMO) were preferred because they enable the use of kernels. However, for linear SVMs, the primal formulation is often more efficient when data is high-dimensional or large-scale, as it can be solved directly without kernel expansions.
1.2 Subgradient Optimization
Subgradient optimization is a generalization of gradient descent for minimizing non‑differentiable convex functions. An SVM loss term (hinge loss) is convex but not differentiable at points where the margin is exactly one. Subgradient methods replace the true gradient with any subgradient at the current point. This approach is simple, robust, and particularly suitable for large-scale problems because each iteration requires only a single data sample (stochastic subgradient).
2 Algorithm Description
Pegasos solves the primal SVM problem in the form:
\[
| \min_{\mathbf{w}} \frac{\lambda}{2} \|\mathbf{w}\|^2 + \frac{1}{n} \sum_{i=1}^n \max(0, 1 - y_i \mathbf{w}^\top \mathbf{x}_i) |
|---|
\]
where \(\lambda = 1/(Cn)\). The algorithm operates in iterations, each processing a randomly chosen training example.
2.1 Core Update Rule
At iteration \(t\), a single example \((\mathbf{x}_i, y_i)\) is drawn uniformly from the training set. The update proceeds in two steps:
2.1.1 Stochastic Gradient Step
If the example is misclassified or lies within the margin (i.e., \(y_i \mathbf{w}_t^\top \mathbf{x}_i < 1\)), the subgradient of the objective is taken, yielding:
\[ \mathbf{w}_{t+1} = (1 - \eta_t \lambda) \, \mathbf{w}_t + \eta_t \, y_i \mathbf{x}_i \]
where \(\eta_t = 1/(\lambda t)\) is the learning rate. If the example is correctly classified with a margin of at least 1, the subgradient includes only the regularization term:
\[ \mathbf{w}_{t+1} = (1 - \eta_t \lambda) \, \mathbf{w}_t \]
2.1.2 Projection onto the Norm Ball
After the gradient step, the weight vector is projected onto a ball of radius \(1/\sqrt{\lambda}\):
\[
| \mathbf{w}_{t+1} = \min\left(1, \frac{1/\sqrt{\lambda}}{\|\mathbf{w}_{t+1}\|}\right) \mathbf{w}_{t+1} |
|---|
\]
This projection enforces the constraint implied by the regularizer and prevents the norm from growing unbounded, which is crucial for convergence.
2.2 Stepsize and Learning Rate Schedule
Pegasos uses a constant learning rate schedule of the form \(\eta_t = 1/(\lambda t)\). The rate decreases inversely with the iteration number, which is a standard choice for stochastic subgradient descent to guarantee convergence. The constant \(\lambda\) controls the trade‑off between regularization and loss and is typically set via cross‑validation.
2.3 Mini-batch Variant
Instead of processing a single example at each iteration, Pegasos can be extended to mini-batches of size \(k > 1\). At each step, a set of \(k\) examples is drawn uniformly, and the average subgradient is computed. The update rule becomes:
\[ \mathbf{w}_{t+1} = (1 - \eta_t \lambda) \, \mathbf{w}_t + \frac{\eta_t}{k} \sum_{i \in B} y_i \mathbf{x}_i \]
followed by the same projection step. Mini‑batches reduce noise in the gradient estimate and improve parallel efficiency while preserving the theoretical convergence rate.
3 Theoretical Properties
3.1 Convergence Rate Analysis
Pegasos provides strong theoretical guarantees for finding an \(\varepsilon\)-optimal solution of the primal SVM problem.
3.1.1 O(1/ε) Iterations for ε-Suboptimality
Under standard assumptions, Pegasos converges to an \(\varepsilon\)-accurate solution in \(O(1/\varepsilon)\) iterations. More precisely, after \(T\) iterations, the expected objective value is within \(O(1/(\lambda T))\) of the optimal value. This rate is optimal for first‑order stochastic methods and holds for both the single‑example and mini‑batch variants.
3.2 Runtime Complexity
The per‑iteration cost of Pegasos is dominated by the dot product \(\mathbf{w}^\top \mathbf{x}_i\), which scales linearly with the number of features \(d\). For datasets with many features (e.g., text classification), this is extremely efficient.
3.2.1 Linear Scaling with Dataset Size
Because each iteration uses only one (or a few) examples, the total runtime to reach a fixed accuracy grows linearly with the number of examples \(n\). In contrast, batch solver time often grows superlinearly. This linear scaling makes Pegasos suitable for massive datasets where a full pass through the data is impractical.
4 Extensions and Variations
4.1 Non-linear Pegasos via Feature Maps
The original Pegasos is restricted to linear SVMs. However, it can be extended to non‑linear decision boundaries by first mapping input data into a high‑dimensional feature space.
4.1.1 Kernel Approximations (e.g., Random Fourier Features)
Explicit feature maps, such as random Fourier features for the RBF kernel, approximate the kernel’s inner product. Pegasos is applied directly on the mapped vectors. This preserves linear scalability while capturing non‑linear patterns, though accuracy depends on the quality of the approximation.
4.2 Pegasos for Multi-class Classification
Multiple one‑vs‑all or one‑vs‑one binary classifiers can be trained concurrently using Pegasos. Alternatively, a multi‑class extension modifies the hinge loss to a multi‑class margin formulation and updates the weight vectors for all classes simultaneously. The update rule remains a stochastic subgradient step with a projection.
4.3 Pegasos with Regularization Tuning
The regularization parameter \(\lambda\) directly controls the step size schedule and the projection radius. Variants automatically tune \(\lambda\) during training (e.g., via online cross‑validation) to adapt to the data. This can reduce the need for expensive grid search.
5 Applications
5.1 Text Classification (Spam Filtering, Sentiment Analysis)
Pegasos’s linear scaling makes it ideal for high‑dimensional sparse text data. Common applications include spam detection and sentiment analysis, where each document is represented as a bag‑of‑words or TF‑IDF vector. The algorithm can process millions of documents efficiently.
5.2 Image Recognition (Large-scale Object Detection)
After applying feature extraction (e.g., histogram of oriented gradients, SIFT), image patches can be classified with a linear SVM. Pegasos has been used in large‑scale detection pipelines where training must be fast and memory‑efficient.
5.3 Bioinformatics (Gene Expression Classification)
Gene expression datasets often have thousands of features but relatively few samples. Pegasos’s strong regularization and fast iterations have been applied to classify tissue types or predict disease outcomes from microarray data.
6 Comparison with Other SVM Solvers
6.1 SMO (Sequential Minimal Optimization)
SMO solves the dual SVM problem by selecting and optimizing two Lagrange multipliers at each step. For non‑linear kernels, SMO is often the method of choice, but it requires \(O(n^2)\) memory in the kernel matrix. For linear SVMs, SMO is much slower than Pegasos because it makes repeated passes over the data and does not leverage sparsity.
6.2 LIBLINEAR (Coordinate Descent)
LIBLINEAR implements a coordinate descent solver for the primal L2‑regularized SVM. It is also designed for large‑scale linear problems and often converges faster than Pegasos in terms of wall‑clock time on medium‑sized datasets. However, LIBLINEAR requires a full pass over the data per iteration, whereas Pegasos can update after each example, making it more suitable for streaming or online settings.
6.3 Stochastic Gradient Descent (SGD) for Logistic Regression
Both Pegasos and SGD for logistic regression are online linear classifiers. Logistic regression replaces the hinge loss with the logistic loss, producing probabilistic outputs. Pegasos typically yields a sparser solution (fewer support vectors) and has a simpler projection step. The two algorithms have similar computational costs and convergence properties, and the choice often depends on whether a margin‑based or probabilistic model is preferred.