Back

Online Passive-Aggressive Algorithms

Koby CrammerOfer DekelJoseph KeshetShai Shalev‐ShwartzYoram Singer

article2003JMLR2,140 citations
Listen

Organizations increasingly rely on real-time data streams for critical decision-making, where predictive systems must continuously adapt to new observations without the computational overhead of retraining on historical data. However, standard online learning methods often struggle to balance fast adaptation with stability, particularly in noisy environments where incorrect data points can severely degrade model accuracy.

The article develops and evaluates a unified family of online margin-based learning algorithms, termed Passive-Aggressive algorithms, along with noise-tolerant variants. It aims to demonstrate that these methods provide strong theoretical guarantees and high empirical performance across diverse tasks—including binary classification, multiclass categorization, regression, and sequence prediction—while relying on simple, analytical update rules.

The authors evaluated the framework through theoretical relative loss analysis, synthetic controlled-noise simulations, and empirical benchmarks on standard optical character recognition datasets, specifically USPS and MNIST digit collections. Across these evaluations, the standard Passive-Aggressive update, which forces complete correction on each round, was compared alongside two regularized variants that introduce linear (PA-I) and quadratic (PA-II) penalties via an aggressiveness parameter, C, to handle noise gracefully.

The findings establish three primary outcomes. First, the noise-tolerant variants (PA-I and PA-II) substantially outperform the baseline Passive-Aggressive method as instance or label noise increases, avoiding erratic weight adjustments. Second, the aggressiveness parameter C governs a clear operational trade-off: higher C values allow faster initial error reduction but suffer higher ongoing loss in noisy settings, whereas lower C values provide stable long-term convergence. Third, on multiclass handwriting benchmarks, the Passive-Aggressive algorithms match the accuracy of advanced margin-based methods like MIRA while significantly outperforming the standard Multiclass Perceptron.

These results demonstrate that organizations can deploy high-performing, margin-based predictive systems at a fraction of the computational and financial cost associated with complex optimization routines. Because the updates possess closed-form analytical solutions, systems can operate in low-latency environments without expensive quadratic programming solvers. This reduction in complexity lowers runtime risk and operational compute costs while preserving robust worst-case loss guarantees.

Decision-makers should consider adopting Passive-Aggressive algorithms for streaming and online inference workloads. When implementing these algorithms, teams should tune the aggressiveness parameter C based on expected data hygiene: use lower C values for noisy production pipelines to preserve stability, and higher C values only in clean or rapidly shifting data regimes. For complex deployments requiring non-linear models, teams should explore kernel adaptations while planning for potential memory overhead.

A primary limitation of this framework is that kernelized implementations scale their memory requirements with the number of updates, potentially causing memory bloat during prolonged online operation. Furthermore, the synthetic experiments were limited to controlled two-dimensional Gaussian environments, though confidence in the core methodology remains high due to rigorous theoretical proofs and validation on real-world benchmark datasets.

binary classificationclosed-form expressiondata pointsonline passive-aggressive algorithmsonline learning algorithmonline binary classification
Crammer et al (2003).pdf

Topics

binary classificationclosed-form expressiondata pointsdata streamgaussiansinferencelinear modelsmulti-class classificationnoisy environmentonline learning

Keywords

online passive-aggressive algorithmsonline learning algorithmonline binary classificationcost-sensitive algorithmsrelative loss boundsMIRA algorithmNORMA algorithmoptimal linear classifieruniclass predictionconstrained optimization

Table of Contents

  • 2. Problem Setting
  • 3. Binary Classification Algorithms
  • 4. Analysis
  • 5. Regression
  • 6. Uniclass Prediction
  • 7. Multiclass Problems
  • 8. Cost-Sensitive Multiclass Classification
  • 9. Learning with Structured Output
  • 10. Experiments
  • 10.1 Robustness to Noise
  • 10.2 The Effect of C
  • 10.3 Multiclass Experiments
  • 11. Discussion
  • Acknowledgments
  • Appendix A. Derivation of the PA-I and PA-II Updates
  • References

Knowls

  1. Knowl 1 — Passive-Aggressive Algorithm Family for Online Binary Classification

    algorithm

    The Passive-Aggressive (PA) algorithm family consists of margin-based online learning algorithms for binary classification. Given a sequence of examples (xt,yt)(\mathbf{x}_t, y_t) where instance xt∈Rn\mathbf{x}_t \in \mathbb{R}^n and label yt∈{−1,+1}y_t \in \{-1, +1\}, the learner maintains a weight vector wt∈Rn\mathbf{w}_t \in \mathbb{R}^n initialized to w1=0\mathbf{w}_1 = \mathbf{0}. On round tt, the algorithm predicts y^t=sign⁡(wt⋅xt)\hat{y}_t = \operatorname{sign}(\mathbf{w}_t \cdot \mathbf{x}_t) and suffers hinge loss ℓt=max⁡{0,1−yt(wt⋅xt)}\ell_t = \max\{0, 1 - y_t(\mathbf{w}_t \cdot \mathbf{x}_t)\}.

    The three variants formulate updates as constrained optimization problems balancing conservatism (staying close to wt\mathbf{w}_t) with progress (satisfying the margin constraint on (xt,yt)(\mathbf{x}_t, y_t)):

    • Basic PA (hard constraint):
    wt+1=argmin⁡w∈Rn12∥w−wt∥2s.t.ℓ(w;(xt,yt))=0\mathbf{w}_{t+1} = \operatorname*{argmin}_{\mathbf{w} \in \mathbb{R}^n} \frac{1}{2}\|\mathbf{w} - \mathbf{w}_t\|^2 \quad \text{s.t.} \quad \ell(\mathbf{w}; (\mathbf{x}_t, y_t)) = 0
    • PA-I (soft margin with linear slack penalty, parameterized by aggressiveness parameter C>0C > 0):
    wt+1=argmin⁡w∈Rn,ξ≥012∥w−wt∥2+Cξs.t.ℓ(w;(xt,yt))≤ξ\mathbf{w}_{t+1} = \operatorname*{argmin}_{\mathbf{w} \in \mathbb{R}^n, \xi \ge 0} \frac{1}{2}\|\mathbf{w} - \mathbf{w}_t\|^2 + C\xi \quad \text{s.t.} \quad \ell(\mathbf{w}; (\mathbf{x}_t, y_t)) \le \xi
    • PA-II (soft margin with quadratic slack penalty, parameterized by aggressiveness parameter C>0C > 0):
    wt+1=argmin⁡w∈Rn,ξ12∥w−wt∥2+Cξ2s.t.ℓ(w;(xt,yt))≤ξ\mathbf{w}_{t+1} = \operatorname*{argmin}_{\mathbf{w} \in \mathbb{R}^n, \xi} \frac{1}{2}\|\mathbf{w} - \mathbf{w}_t\|^2 + C\xi^2 \quad \text{s.t.} \quad \ell(\mathbf{w}; (\mathbf{x}_t, y_t)) \le \xi

    All three variants share the analytical update rule wt+1=wt+τtytxt\mathbf{w}_{t+1} = \mathbf{w}_t + \tau_t y_t \mathbf{x}_t, differing only in the step size τt\tau_t.

    Input: Aggressiveness parameter C>0C > 0 (for PA-I and PA-II)
    Initialize w1=0∈Rn\mathbf{w}_1 = \mathbf{0} \in \mathbb{R}^n
    for t=1,2,…t = 1, 2, \dots do
        Receive instance xt∈Rn\mathbf{x}_t \in \mathbb{R}^n
        Predict y^t=sign⁡(wt⋅xt)\hat{y}_t = \operatorname{sign}(\mathbf{w}_t \cdot \mathbf{x}_t)
        Receive correct label yt∈{−1,+1}y_t \in \{-1, +1\}
        Compute loss ℓt=max⁡{0,1−yt(wt⋅xt)}\ell_t = \max\{0, 1 - y_t(\mathbf{w}_t \cdot \mathbf{x}_t)\}
        if variant is PA then
            τt=ℓt∥xt∥2\tau_t = \frac{\ell_t}{\|\mathbf{x}_t\|^2}
        else if variant is PA-I then
            τt=min⁡{C,ℓt∥xt∥2}\tau_t = \min\left\{C, \frac{\ell_t}{\|\mathbf{x}_t\|^2}\right\}
        else if variant is PA-II then
            τt=ℓt∥xt∥2+12C\tau_t = \frac{\ell_t}{\|\mathbf{x}_t\|^2 + \frac{1}{2C}}
        end if
        Update wt+1=wt+τtytxt\mathbf{w}_{t+1} = \mathbf{w}_t + \tau_t y_t \mathbf{x}_t
    end for

    The algorithms generalize to nonlinear classifiers by expressing wt⋅xt=∑i=1t−1τiyiK(xi,xt)\mathbf{w}_t \cdot \mathbf{x}_t = \sum_{i=1}^{t-1} \tau_i y_i K(\mathbf{x}_i, \mathbf{x}_t) using a Mercer kernel K(xi,xj)K(\mathbf{x}_i, \mathbf{x}_j).

  2. Knowl 2 — Master Relative Loss Lemma for Online Passive-Aggressive Updates

    theoretical result

    Let (x1,y1),…,(xT,yT)(\mathbf{x}_1, y_1), \dots, (\mathbf{x}_T, y_T) be an arbitrary sequence of examples where xt∈Rn\mathbf{x}_t \in \mathbb{R}^n and yt∈{−1,+1}y_t \in \{-1, +1\} for all t∈{1,…,T}t \in \{1, \dots, T\}. Let w1=0\mathbf{w}_1 = \mathbf{0}, and let wt+1=wt+τtytxt\mathbf{w}_{t+1} = \mathbf{w}_t + \tau_t y_t \mathbf{x}_t, where τt≥0\tau_t \ge 0 is the step size computed by the PA, PA-I, or PA-II algorithm.

    Let ℓt=max⁡{0,1−yt(wt⋅xt)}\ell_t = \max\{0, 1 - y_t(\mathbf{w}_t \cdot \mathbf{x}_t)\} denote the instantaneous hinge loss suffered by the algorithm on round tt, and let ℓt∗=max⁡{0,1−yt(u⋅xt)}\ell_t^* = \max\{0, 1 - y_t(\mathbf{u} \cdot \mathbf{x}_t)\} denote the hinge loss of an arbitrary fixed reference vector u∈Rn\mathbf{u} \in \mathbb{R}^n on round tt.

    Then for any reference vector u∈Rn\mathbf{u} \in \mathbb{R}^n, the following bound holds:

    ∑t=1Tτt(2ℓt−τt∥xt∥2−2ℓt∗)≤∥u∥2\sum_{t=1}^T \tau_t \left(2\ell_t - \tau_t \|\mathbf{x}_t\|^2 - 2\ell_t^*\right) \le \|\mathbf{u}\|^2

    This single inequality serves as the unified foundation for proving cumulative loss and mistake bounds for the PA variants across binary classification, regression, uniclass prediction, and structured prediction.

  3. Knowl 3 — Relative Loss and Mistake Bounds for Binary Passive-Aggressive Algorithms

    theoretical result

    Let (x1,y1),…,(xT,yT)(\mathbf{x}_1, y_1), \dots, (\mathbf{x}_T, y_T) be a sequence of examples with xt∈Rn\mathbf{x}_t \in \mathbb{R}^n, yt∈{−1,+1}y_t \in \{-1, +1\}, and ∥xt∥≤R\|\mathbf{x}_t\| \le R for all t∈{1,…,T}t \in \{1, \dots, T\}. Let ℓt=max⁡{0,1−yt(wt⋅xt)}\ell_t = \max\{0, 1 - y_t(\mathbf{w}_t \cdot \mathbf{x}_t)\} denote the instantaneous hinge loss on round tt, and let ℓt∗=max⁡{0,1−yt(u⋅xt)}\ell_t^* = \max\{0, 1 - y_t(\mathbf{u} \cdot \mathbf{x}_t)\} denote the hinge loss of an arbitrary comparator vector u∈Rn\mathbf{u} \in \mathbb{R}^n.

    1. Basic PA (Separable Case): If there exists u∈Rn\mathbf{u} \in \mathbb{R}^n such that ℓt∗=0\ell_t^* = 0 for all t∈{1,…,T}t \in \{1, \dots, T\}, the cumulative squared hinge loss of basic PA is bounded by:
    ∑t=1Tℓt2≤∥u∥2R2\sum_{t=1}^T \ell_t^2 \le \|\mathbf{u}\|^2 R^2

    Since ℓt≥1\ell_t \ge 1 whenever a mistake occurs (sign⁡(wt⋅xt)≠yt\operatorname{sign}(\mathbf{w}_t \cdot \mathbf{x}_t) \ne y_t), this inequality also bounds the total number of prediction mistakes.

    1. Basic PA (Normalized Non-Separable Case): If ∥xt∥=1\|\mathbf{x}_t\| = 1 for all tt, then for any arbitrary u∈Rn\mathbf{u} \in \mathbb{R}^n:
    ∑t=1Tℓt2≤(∥u∥+2∑t=1T(ℓt∗)2)2\sum_{t=1}^T \ell_t^2 \le \left(\|\mathbf{u}\| + 2\sqrt{\sum_{t=1}^T (\ell_t^*)^2}\right)^2
    1. PA-I Mistake Bound: For any arbitrary comparator u∈Rn\mathbf{u} \in \mathbb{R}^n, the total number of prediction mistakes M=∑t=1TI[sign⁡(wt⋅xt)≠yt]M = \sum_{t=1}^T \mathbb{I}[\operatorname{sign}(\mathbf{w}_t \cdot \mathbf{x}_t) \ne y_t] made by PA-I with aggressiveness parameter C>0C > 0 satisfies:
    M≤max⁡{R2,1C}(∥u∥2+2C∑t=1Tℓt∗)M \le \max\left\{R^2, \frac{1}{C}\right\} \left(\|\mathbf{u}\|^2 + 2C \sum_{t=1}^T \ell_t^*\right)
    1. PA-II Cumulative Squared Loss Bound: For any arbitrary comparator u∈Rn\mathbf{u} \in \mathbb{R}^n, the cumulative squared loss of PA-II with parameter C>0C > 0 satisfies:
    ∑t=1Tℓt2≤(R2+12C)(∥u∥2+2C∑t=1T(ℓt∗)2)\sum_{t=1}^T \ell_t^2 \le \left(R^2 + \frac{1}{2C}\right) \left(\|\mathbf{u}\|^2 + 2C \sum_{t=1}^T (\ell_t^*)^2\right)

    Setting C=∥u∥2R∑t=1T(ℓt∗)2C = \frac{\|\mathbf{u}\|}{2R\sqrt{\sum_{t=1}^T (\ell_t^*)^2}} minimizes the bound to (R∥u∥+∑t=1T(ℓt∗)2)2\left(R\|\mathbf{u}\| + \sqrt{\sum_{t=1}^T (\ell_t^*)^2}\right)^2.

  4. Knowl 4 — Passive-Aggressive Online Regression with Epsilon-Insensitive Hinge Loss

    model/method

    In online regression, at round tt, the algorithm receives xt∈Rn\mathbf{x}_t \in \mathbb{R}^n, predicts a real-valued target y^t=wt⋅xt\hat{y}_t = \mathbf{w}_t \cdot \mathbf{x}_t, receives the true value yt∈Ry_t \in \mathbb{R}, and suffers the ϵ\epsilon-insensitive hinge loss:

    ℓϵ(w;(x,y))={0∣w⋅x−y∣≤ϵ∣w⋅x−y∣−ϵotherwise\ell_\epsilon(\mathbf{w}; (\mathbf{x}, y)) = \begin{cases} 0 & |\mathbf{w} \cdot \mathbf{x} - y| \le \epsilon \\ |\mathbf{w} \cdot \mathbf{x} - y| - \epsilon & \text{otherwise} \end{cases}

    where ϵ>0\epsilon > 0 is a user-specified sensitivity parameter.

    Geometrically, the Passive-Aggressive regression algorithm projects wt\mathbf{w}_t onto the hyper-slab of width 2ϵ2\epsilon defined by {w∈Rn:∣w⋅xt−yt∣≤ϵ}\{\mathbf{w} \in \mathbb{R}^n : |\mathbf{w} \cdot \mathbf{x}_t - y_t| \le \epsilon\}.

    The analytical weight update is:

    wt+1=wt+sign⁡(yt−y^t)τtxt\mathbf{w}_{t+1} = \mathbf{w}_t + \operatorname{sign}(y_t - \hat{y}_t) \tau_t \mathbf{x}_t

    where ℓt=ℓϵ(wt;(xt,yt))\ell_t = \ell_\epsilon(\mathbf{w}_t; (\mathbf{x}_t, y_t)), and the step size τt\tau_t is defined as:

    • PA: τt=ℓt∥xt∥2\tau_t = \frac{\ell_t}{\|\mathbf{x}_t\|^2}
    • PA-I: τt=min⁡{C,ℓt∥xt∥2}\tau_t = \min\left\{C, \frac{\ell_t}{\|\mathbf{x}_t\|^2}\right\}
    • PA-II: τt=ℓt∥xt∥2+12C\tau_t = \frac{\ell_t}{\|\mathbf{x}_t\|^2 + \frac{1}{2C}}

    The master inequality ∑t=1Tτt(2ℓt−τt∥xt∥2−2ℓt∗)≤∥u∥2\sum_{t=1}^T \tau_t (2\ell_t - \tau_t \|\mathbf{x}_t\|^2 - 2\ell_t^*) \le \|\mathbf{u}\|^2 holds for regression, ensuring that the cumulative loss bounds derived for classification transfer directly to online regression.

  5. Knowl 5 — Passive-Aggressive Uniclass Prediction and Variable Radius Learning

    model/method

    In uniclass prediction (online center-point estimation), the learner sequentially predicts points yt∈Rn\mathbf{y}_t \in \mathbb{R}^n without observing input features. Maintaining a center vector wt∈Rn\mathbf{w}_t \in \mathbb{R}^n initialized to w1=0\mathbf{w}_1 = \mathbf{0}, the learner predicts wt\mathbf{w}_t, observes yt\mathbf{y}_t, and incurs the ϵ\epsilon-insensitive loss:

    ℓϵ(w;y)={0∥w−y∥≤ϵ∥w−y∥−ϵotherwise\ell_\epsilon(\mathbf{w}; \mathbf{y}) = \begin{cases} 0 & \|\mathbf{w} - \mathbf{y}\| \le \epsilon \\ \|\mathbf{w} - \mathbf{y}\| - \epsilon & \text{otherwise} \end{cases}

    The update projects wt\mathbf{w}_t onto a Euclidean ball of radius ϵ\epsilon centered at yt\mathbf{y}_t:

    wt+1=wt+τtyt−wt∥yt−wt∥\mathbf{w}_{t+1} = \mathbf{w}_t + \tau_t \frac{\mathbf{y}_t - \mathbf{w}_t}{\|\mathbf{y}_t - \mathbf{w}_t\|}

    where ℓt=ℓϵ(wt;yt)\ell_t = \ell_\epsilon(\mathbf{w}_t; \mathbf{y}_t), with τt=ℓt\tau_t = \ell_t for PA, τt=min⁡{C,ℓt}\tau_t = \min\{C, \ell_t\} for PA-I, and τt=ℓt1+12C\tau_t = \frac{\ell_t}{1 + \frac{1}{2C}} for PA-II.

    When the radius ϵ\epsilon is unknown and must be learned online alongside the center w\mathbf{w} subject to an upper bound B≥ϵB \ge \epsilon, the task reduces to a fixed-radius uniclass problem of radius BB in Rn+1\mathbb{R}^{n+1}:

    1. Augment each observation vector to y~t=(yt,0)∈Rn+1\tilde{\mathbf{y}}_t = (\mathbf{y}_t, 0) \in \mathbb{R}^{n+1}.
    2. Initialize w1=(0,B)∈Rn+1\mathbf{w}_1 = (\mathbf{0}, B) \in \mathbb{R}^{n+1}, corresponding to initial radius ϵ1=0\epsilon_1 = 0.
    3. Update wt+1∈Rn+1\mathbf{w}_{t+1} \in \mathbb{R}^{n+1} using the fixed-radius BB uniclass PA update.
    4. Extract the active radius on round tt as ϵt=B2−wt,n+12\epsilon_t = \sqrt{B^2 - w_{t, n+1}^2}.

    Because wt,n+1w_{t, n+1} is monotonically non-increasing and bounded in (0,B](0, B], ϵt\epsilon_t increases monotonically from 00, naturally favoring small enclosing balls. The relative loss bounds hold with competitor norm ∥u∥2+ϵ2\|\mathbf{u}\|^2 + \epsilon^2 replacing ∥u∥2\|\mathbf{u}\|^2.

  6. Knowl 6 — Passive-Aggressive Multiclass and Multilabel Categorization via Most-Violated Constraint

    model/method

    In multiclass multilabel classification, each instance xt∈X\mathbf{x}_t \in \mathcal{X} is associated with a subset of relevant labels Yt⊆Y={1,…,k}Y_t \subseteq \mathcal{Y} = \{1, \dots, k\}. A joint feature mapping Φ(x,y)∈Rd\Phi(\mathbf{x}, y) \in \mathbb{R}^d assigns a score w⋅Φ(x,y)\mathbf{w} \cdot \Phi(\mathbf{x}, y) to each label yy. The ranking margin is:

    γ(w;(x,Y))=min⁡r∈Yw⋅Φ(x,r)−max⁡s∉Yw⋅Φ(x,s)\gamma(\mathbf{w}; (\mathbf{x}, Y)) = \min_{r \in Y} \mathbf{w} \cdot \Phi(\mathbf{x}, r) - \max_{s \notin Y} \mathbf{w} \cdot \Phi(\mathbf{x}, s)

    and the hinge loss is ℓMC(w;(x,Y))=max⁡{0,1−γ(w;(x,Y))}\ell_{\text{MC}}(\mathbf{w}; (\mathbf{x}, Y)) = \max\{0, 1 - \gamma(\mathbf{w}; (\mathbf{x}, Y))\}.

    Instead of solving a quadratic program over all ∣Yt∣(k−∣Yt∣)|Y_t|(k - |Y_t|) margin constraints simultaneously, the Passive-Aggressive update focuses on the single pair corresponding to the most-violated constraint:

    rt=argmin⁡r∈Ytwt⋅Φ(xt,r),st=argmax⁡s∉Ytwt⋅Φ(xt,s)r_t = \operatorname*{argmin}_{r \in Y_t} \mathbf{w}_t \cdot \Phi(\mathbf{x}_t, r), \quad s_t = \operatorname*{argmax}_{s \notin Y_t} \mathbf{w}_t \cdot \Phi(\mathbf{x}_t, s)

    Treating Φ(xt,rt)−Φ(xt,st)\Phi(\mathbf{x}_t, r_t) - \Phi(\mathbf{x}_t, s_t) as a virtual binary instance with label +1+1, the closed-form update is:

    wt+1=wt+τt(Φ(xt,rt)−Φ(xt,st))\mathbf{w}_{t+1} = \mathbf{w}_t + \tau_t \left(\Phi(\mathbf{x}_t, r_t) - \Phi(\mathbf{x}_t, s_t)\right)

    where ℓt=ℓMC(wt;(xt,Yt))\ell_t = \ell_{\text{MC}}(\mathbf{w}_t; (\mathbf{x}_t, Y_t)) and:

    • PA: τt=ℓt∥Φ(xt,rt)−Φ(xt,st)∥2\tau_t = \frac{\ell_t}{\|\Phi(\mathbf{x}_t, r_t) - \Phi(\mathbf{x}_t, s_t)\|^2}
    • PA-I: τt=min⁡{C,ℓt∥Φ(xt,rt)−Φ(xt,st)∥2}\tau_t = \min\left\{C, \frac{\ell_t}{\|\Phi(\mathbf{x}_t, r_t) - \Phi(\mathbf{x}_t, s_t)\|^2}\right\}
    • PA-II: τt=ℓt∥Φ(xt,rt)−Φ(xt,st)∥2+12C\tau_t = \frac{\ell_t}{\|\Phi(\mathbf{x}_t, r_t) - \Phi(\mathbf{x}_t, s_t)\|^2 + \frac{1}{2C}}

    In the multi-prototype setting where each label r∈Yr \in \mathcal{Y} maintains an individual weight vector wr∈Rn\mathbf{w}^r \in \mathbb{R}^n, the update simplifies to wt+1rt=wtrt+τtxt\mathbf{w}_{t+1}^{r_t} = \mathbf{w}_t^{r_t} + \tau_t \mathbf{x}_t and wt+1st=wtst−τtxt\mathbf{w}_{t+1}^{s_t} = \mathbf{w}_t^{s_t} - \tau_t \mathbf{x}_t, with ∥Φ(xt,rt)−Φ(xt,st)∥2=2∥xt∥2\|\Phi(\mathbf{x}_t, r_t) - \Phi(\mathbf{x}_t, s_t)\|^2 = 2\|\mathbf{x}_t\|^2.

  7. Knowl 7 — Cost-Sensitive Multiclass Passive-Aggressive Classification

    model/method

    In cost-sensitive multiclass classification, predicting label y^\hat{y} when the true label is y∈Y={1,…,k}y \in \mathcal{Y} = \{1, \dots, k\} incurs a non-negative cost ρ(y,y^)\rho(y, \hat{y}), with ρ(y,y)=0\rho(y, y) = 0. The model predicts y^t=argmax⁡y∈Y(wt⋅Φ(xt,y))\hat{y}_t = \operatorname*{argmax}_{y \in \mathcal{Y}} (\mathbf{w}_t \cdot \Phi(\mathbf{x}_t, y)) and aims to enforce the margin constraints:

    w⋅Φ(xt,yt)−w⋅Φ(xt,r)≥ρ(yt,r)∀r∈Y∖{yt}\mathbf{w} \cdot \Phi(\mathbf{x}_t, y_t) - \mathbf{w} \cdot \Phi(\mathbf{x}_t, r) \ge \sqrt{\rho(y_t, r)} \quad \forall r \in \mathcal{Y} \setminus \{y_t\}

    Two Passive-Aggressive updates select a single constraint to satisfy per round:

    1. Prediction-Based (PB) Update: Uses the predicted label y^t\hat{y}_t, with loss:
    ℓPB(wt;(xt,yt))=wt⋅Φ(xt,y^t)−wt⋅Φ(xt,yt)+ρ(yt,y^t)\ell_{\text{PB}}(\mathbf{w}_t; (\mathbf{x}_t, y_t)) = \mathbf{w}_t \cdot \Phi(\mathbf{x}_t, \hat{y}_t) - \mathbf{w}_t \cdot \Phi(\mathbf{x}_t, y_t) + \sqrt{\rho(y_t, \hat{y}_t)}
    1. Max-Loss (ML) Update: Uses the loss-maximizing label y~t=argmax⁡r∈Y(wt⋅Φ(xt,r)−wt⋅Φ(xt,yt)+ρ(yt,r))\tilde{y}_t = \operatorname*{argmax}_{r \in \mathcal{Y}} \left(\mathbf{w}_t \cdot \Phi(\mathbf{x}_t, r) - \mathbf{w}_t \cdot \Phi(\mathbf{x}_t, y_t) + \sqrt{\rho(y_t, r)}\right), with loss:
    ℓML(wt;(xt,yt))=wt⋅Φ(xt,y~t)−wt⋅Φ(xt,yt)+ρ(yt,y~t)\ell_{\text{ML}}(\mathbf{w}_t; (\mathbf{x}_t, y_t)) = \mathbf{w}_t \cdot \Phi(\mathbf{x}_t, \tilde{y}_t) - \mathbf{w}_t \cdot \Phi(\mathbf{x}_t, y_t) + \sqrt{\rho(y_t, \tilde{y}_t)}

    For selected label qt∈{y^t,y~t}q_t \in \{\hat{y}_t, \tilde{y}_t\} and loss ℓt\ell_t, the update is:

    wt+1=wt+τt(Φ(xt,yt)−Φ(xt,qt))\mathbf{w}_{t+1} = \mathbf{w}_t + \tau_t (\Phi(\mathbf{x}_t, y_t) - \Phi(\mathbf{x}_t, q_t))

    where τt=ℓt∥Φ(xt,yt)−Φ(xt,qt)∥2\tau_t = \frac{\ell_t}{\|\Phi(\mathbf{x}_t, y_t) - \Phi(\mathbf{x}_t, q_t)\|^2} for PA, τt=min⁡{C,ℓt∥Φ(xt,yt)−Φ(xt,qt)∥2}\tau_t = \min\left\{C, \frac{\ell_t}{\|\Phi(\mathbf{x}_t, y_t) - \Phi(\mathbf{x}_t, q_t)\|^2}\right\} for PA-I, and τt=ℓt∥Φ(xt,yt)−Φ(xt,qt)∥2+12C\tau_t = \frac{\ell_t}{\|\Phi(\mathbf{x}_t, y_t) - \Phi(\mathbf{x}_t, q_t)\|^2 + \frac{1}{2C}} for PA-II.

    For max-loss PA-I with ∥Φ(xt,yt)−Φ(xt,y~t)∥≤1\|\Phi(\mathbf{x}_t, y_t) - \Phi(\mathbf{x}_t, \tilde{y}_t)\| \le 1 and parameter C≥ρ(yt,y^t)C \ge \sqrt{\rho(y_t, \hat{y}_t)}, the cumulative cost is bounded by:

    ∑t=1Tρ(yt,y^t)≤∥u∥2+2C∑t=1TℓML(u;(xt,yt))\sum_{t=1}^T \rho(y_t, \hat{y}_t) \le \|\mathbf{u}\|^2 + 2C \sum_{t=1}^T \ell_{\text{ML}}(\mathbf{u}; (\mathbf{x}_t, y_t))

  8. Knowl 8 — Structured Output Sequence Prediction with Markovian Passive-Aggressive Updates

    model/method

    In structured sequence prediction, an input instance xt\mathbf{x}_t is mapped to an output sequence yt=(yt,1,…,yt,m)∈Ym\mathbf{y}_t = (y_{t,1}, \dots, y_{t,m}) \in \mathcal{Y}^m of length mm over alphabet Y={1,…,k}\mathcal{Y} = \{1, \dots, k\}. The model predicts:

    y^t=argmax⁡y∈Ym(wt⋅Φ(xt,y))\hat{\mathbf{y}}_t = \operatorname*{argmax}_{\mathbf{y} \in \mathcal{Y}^m} (\mathbf{w}_t \cdot \Phi(\mathbf{x}_t, \mathbf{y}))

    and receives feedback with sequence cost ρ(yt,y^t)≥0\rho(\mathbf{y}_t, \hat{\mathbf{y}}_t) \ge 0.

    To make inference over the kmk^m possible sequences computationally feasible, feature representations are decomposed into first-order Markovian components:

    ϕj(x,y)=ψj0(y1,x)+∑i=2mψj(yi,yi−1,x)\phi_j(\mathbf{x}, \mathbf{y}) = \psi_j^0(y_1, \mathbf{x}) + \sum_{i=2}^m \psi_j(y_i, y_{i-1}, \mathbf{x})

    where ψj0\psi_j^0 represents initial state features and ψj\psi_j represents transition and emission features.

    This structure enables computing y^t\hat{\mathbf{y}}_t in O(mk2)O(m k^2) time using dynamic programming (Viterbi decoding). Weights are updated via the prediction-based Passive-Aggressive rule:

    wt+1=wt+τt(Φ(xt,yt)−Φ(xt,y^t))\mathbf{w}_{t+1} = \mathbf{w}_t + \tau_t (\Phi(\mathbf{x}_t, \mathbf{y}_t) - \Phi(\mathbf{x}_t, \hat{\mathbf{y}}_t))

    with step size:

    τt=min⁡{C,wt⋅Φ(xt,y^t)−wt⋅Φ(xt,yt)+ρ(yt,y^t)∥Φ(xt,yt)−Φ(xt,y^t)∥2}\tau_t = \min\left\{C, \frac{\mathbf{w}_t \cdot \Phi(\mathbf{x}_t, \hat{\mathbf{y}}_t) - \mathbf{w}_t \cdot \Phi(\mathbf{x}_t, \mathbf{y}_t) + \sqrt{\rho(\mathbf{y}_t, \hat{\mathbf{y}}_t)}}{\|\Phi(\mathbf{x}_t, \mathbf{y}_t) - \Phi(\mathbf{x}_t, \hat{\mathbf{y}}_t)\|^2}\right\}

    The prediction-based formulation is essential because inference depends solely on wt⋅Φ(xt,y)\mathbf{w}_t \cdot \Phi(\mathbf{x}_t, \mathbf{y}), bypassing the combinatorial intractability of maximizing non-decomposable costs ρ\rho over all kmk^m sequences during the update.

  9. Knowl 9 — Noise Robustness and Convergence Trade-Offs Governed by Aggressiveness Parameter C

    empirical result

    Synthetic 2D Gaussian classification experiments evaluating basic PA, PA-I, and PA-II across 4,000-example sequences (averaged over 10 repetitions) demonstrate distinct noise robustness and convergence behaviors:

    1. Robustness to Noise: Under zero or low instance noise (covariance σI\sigma \mathbf{I} with σ∈[0,2]\sigma \in [0, 2]) or label flip noise (probability p∈[0,0.3]p \in [0, 0.3]), all three variants (PA, PA-I, PA-II) perform similarly with near-identical average mistake rates and hinge losses. In high-noise regimes, soft-margin variants PA-I and PA-II (with C=0.001C = 0.001) significantly outperform basic PA, which suffers large error and loss due to excessively aggressive updates on mislabeled samples. PA-I and PA-II achieve virtually identical performance across all noise levels.

    2. Aggressiveness Parameter CC Behavior: For noisy data (p∈{0.0,0.1,0.2}p \in \{0.0, 0.1, 0.2\}), small values of CC (log⁡(C)≤−4\log(C) \le -4) limit the influence of outliers and prevent severe degradation, whereas large values (log⁡(C)≥0\log(C) \ge 0) cause the algorithms to over-react to noise, degrading test performance.

    3. Convergence Rate vs. Asymptotic Error: On long sequences (T=104T = 10^4 examples with p=0.02p = 0.02 label noise), setting C=100C = 100 produces rapid early error reduction (T<1000T < 1000) but plateaus at an inferior asymptotic error rate (≈4%\approx 4\%). Conversely, setting C=0.001C = 0.001 yields slower early progress but achieves a substantially lower asymptotic error rate (≈2%\approx 2\%).

  10. Knowl 10 — Multiclass Benchmark Classification of Handwritten Digits: PA vs MIRA and Perceptron

    empirical result

    In evaluations on standard multiclass handwritten digit benchmarks—the USPS data set (7,291 instances, using polynomial kernel K(xi,xj)=(xi⋅xj)3K(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i \cdot \mathbf{x}_j)^3) and the MNIST data set (60,000 instances, using polynomial kernel K(xi,xj)=(0.5+xi⋅xj)5K(\mathbf{x}_i, \mathbf{x}_j) = (0.5 + \mathbf{x}_i \cdot \mathbf{x}_j)^5):

    1. Classification Accuracy: Multiclass PA-I and PA-II (with parameter C=100C = 100) achieve online error rates substantially lower than the uniform-update multiclass Perceptron across all rounds. On USPS, PA-I attains an online cumulative error rate of approximately 3.9% versus 6.4% for Perceptron. On MNIST, PA-I attains an error rate of approximately 2.2% versus 4.5% for Perceptron.

    2. Comparison with MIRA: The online performance of PA-I and PA-II is virtually indistinguishable from basic PA and closely matches the Margin Infused Relaxed Algorithm (MIRA), with MIRA having only a marginal advantage (<0.2%< 0.2\% difference in error).

    3. Algorithmic Efficiency: Whereas MIRA requires solving a complex quadratic programming problem over all class constraints at every online update, the multiclass PA updates isolate the single most-violated constraint pair and execute in closed form via elementary arithmetic operations, providing significant computational speedup and implementation simplicity without loss of prediction accuracy.

Coverage note — No substantial contributed material was omitted; all core algorithms (binary classification, regression, uniclass, multiclass, cost-sensitive, structured sequence), theoretical bounds, and empirical findings are covered.

References

  1. 1.S. Agmon. The relaxation method for linear inequalities. Canadian Journal of Mathematics, 6(3): 382–392, 1954.
  2. 2.Y. Altun, I. Tsochantaridis, and T. Hofmann. Hidden markov support vector machines. In Proceedings of the Twentieth International Conference on Machine Learning, 2003.
  3. 3.S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
  4. 4.M. Collins. Discriminative reranking for natural language parsing. In Machine Learning: Proceedings of the Seventeenth International Conference, 2000.
  5. 5.K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector machines. Jornal of Machine Learning Research, 2:265–292, 2001.
  6. 6.K. Crammer and Y. Singer. A new family of online algorithms for category ranking. Jornal of Machine Learning Research, 3:1025–1058, 2003a.
  7. 7.K. Crammer and Y. Singer. Ultraconservative online algorithms for multiclass problems. Jornal of Machine Learning Research, 3:951–991, 2003b.
  8. 8.N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines. Cambridge University Press, 2000.
  9. 9.O. Dekel, J. Keshet, and Y. Singer. Large margin hierarchical classification. In Proceedings of the Twenty-First International Conference on Machine Learning, 2004a.
  10. 10.O. Dekel, S. Shalev-Shwartz, and Y. Singer. The power of selective memory: Self-bounded learning of prediction suffix trees. In Advances in Neural Information Processing Systems 17, 2004b.
  11. 11.A. Elisseeff and J. Weston. A kernel method for multi-labeled classification. In Advances in Neural Information Processing Systems 14, 2001.
  12. 12.Y. Freund and R. E. Schapire. Large margin classification using the perceptron algorithm. Machine Learning, 37(3):277–296, 1999.
  13. 13.C. Gentile. A new approximate maximal margin classification algorithm. Journal of Machine Learning Research, 2:213–242, 2001.
  14. 14.C. Gentile. The robustness of the p-norm algorithms. Machine Learning, 53(3), 2002.
  15. 15.D.P Helmbold, J. Kivinen, and M. Warmuth. Relative loss bounds for single neurons. IEEE Transactions on Neural Networks, 10(6):1291–1304, 1999.
  16. 16.M. Herbster. Learning additive models online with fast evaluating kernels. In Proceedings of the Fourteenth Annual Conference on Computational Learning Theory, pages 444–460, 2001.
  17. 17.J. Kivinen, A. J. Smola, and R. C. Williamson. Online learning with kernels. IEEE Transactions on Signal Processing, 52(8):2165–2176, 2002.
  18. 18.J. Kivinen and M. Warmuth. Exponentiated gradient versus gradient descent for linear predictors. Information and Computation, 132(1):1–64, January 1997.
  19. 19.N. Klasner and H.U. Simon. From noise-free to noise-tolerant and from on-line to batch learning. In Proceedings of the Eighth Annual Conference on Computational Learning Theory, pages 250–264, 1995.
  20. 20.Y. Li and P. M. Long. The relaxed online maximum margin algorithm. Machine Learning, 46(1–3): 361–387, 2002.
  21. 21.N. Littlestone. Mistake bounds and logarithmic linear-threshold learning algorithms. PhD thesis, U. C. Santa Cruz, March 1989.
  22. 22.A. B. J. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposium on the Mathematical Theory of Automata, volume XII, pages 615–622, 1962.
  23. 23.J. Rocchio. Relevance feedback information retrieval. In Gerard Salton, editor, The Smart retrieval system—experiments in automatic document processing, pages 313–323. Prentice-Hall, Englewood Cliffs, NJ, 1971.
  24. 24.F. Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65:386–407, 1958. (Reprinted in Neurocomputing (MIT Press, 1988).).
  25. 25.G. Salton and C. Buckley. Term weighting approaches in automatic text retrieval. Information Processing and Management, 24(5), 1988.
  26. 26.R.E. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated predictions. In Proceedings of the Eleventh Annual Conference on Computational Learning Theory, pages 80–91, 1998. To appear, Machine Learning.
  27. 27.R.E. Schapire and Y. Singer. BoosTexter: A boosting-based system for text categorization. Machine Learning, 32(2/3), 2000.
  28. 28.B. Schölkopf and A. J. Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization and Beyond. MIT Press, 2002.
  29. 29.S. Shalev-Shwartz, J. Keshet, and Y. Singer. Learning to align polyphonic music. In Proceedings of the 5th International Conference on Music Information Retrieval, 2004a. http://www.cs.huji.ac.il/~shais/.
  30. 30.S. Shalev-Shwartz, Y. Singer, and A. Ng. Online and batch learning of pseudo-metrics. In Proceedings of the Twenty-First International Conference on Machine Learning, 2004b.
  31. 31.B. Taskar, C. Guestrin, and D. Koller. Max-margin markov networks. In Advances in Neural Information Processing Systems 17, 2003.
  32. 32.I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun. Support vector machine learning for interdependent and structured output spaces. In Proceedings of the Twenty-First International Conference on Machine Learning, 2004.
  33. 33.V. N. Vapnik. Statistical Learning Theory. Wiley, 1998.
  34. 34.J. Weston and C. Watkins. Support vector machines for multi-class pattern recognition. In Proceedings of the Seventh European Symposium on Artificial Neural Networks, April 1999.

Citation

MLA
Crammer, K., et al. “Online Passive-Aggressive Algorithms”. 2003, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.330.6895.
APA
Crammer, K., Dekel, O., Keshet, J., Shalev‐Shwartz, S., & Singer, Y. (2003). Online Passive-Aggressive Algorithms. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.330.6895
Chicago
Crammer, K., O. Dekel, J. Keshet, S. Shalev‐Shwartz, and Y. Singer. 2003. “Online Passive-Aggressive Algorithms”. Preprint. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.330.6895.
Harvard
Crammer, K. et al. (2003) “Online Passive-Aggressive Algorithms”. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.330.6895.
Vancouver
1. Crammer K, Dekel O, Keshet J, Shalev‐Shwartz S, Singer Y (2003) Online Passive-Aggressive Algorithms.

BibTeX

@article{crammer2003online,
  title = {Online Passive-Aggressive Algorithms},
  author = {Crammer, Koby and Dekel, Ofer and Keshet, Joseph and Shalev‐Shwartz, Shai and Singer, Yoram},
  year = {2003},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.330.6895}
}
Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/