acceptodds
Under review as a conference paper at ICLR 2027

SOPA-DoS: Second-Order Passive-Aggressive Difference-of-Squares Learning in Open Feature Spaces

Abstract

Online learning algorithms are essential for processing high-speed data streams, yet most classical algorithms assume that each sample is represented within a fixed feature space. Open-feature streams violate this assumption: features can emerge, disappear, and reappear while the learner must predict in one pass. Existing open-feature methods primarily rely on linear passive-aggressive updates, feature reconstruction, sparsity, or evolving ensembles, whereas recent nonlinear difference-of-squares (DoS) passive-aggressive learning assumes a fixed representation and does not exploit second-order feature geometry. To the end, we propose a second-order passive-aggressive framework SOPA-DoS for low-rank DoS classification in open feature spaces. The key construction replaces Euclidean parameter proximity by a positive-definite right metric that accumulates streaming feature curvature. A whitening argument converts the resulting metric-constrained nonconvex QCQP exactly into the tractable one-constraint DoS passive-aggressive problem, yielding a unique scalar step and closed-form rank-one updates along the preconditioned direction . Dynamic block expansion makes the metric and DoS factors compatible with newly appearing features, while zero embedding handles unobserved features; diagonal and sketched variants trade curvature fidelity for scalability. The construction reduces to the original DoS-PA update when and is equivariant to feature reindexing. Experimental results on the WDBC stream under increment-decrement and capricious feature protocols demonstrate that curvature-aware variants can substantially reduce cumulative error when feature scales are heterogeneous.

Primary area:
learning on time series and dynamical systems
Keywords:
Second-Order Learning, Passive-Aggressive, Difference-of-Squares, Online Learning, Data Streams

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_RiuYOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper extends Saul's (2021) passive-aggressive algorithm for difference-of-squares (DoS) classifiers, i.e. low-rank quadratic models with score ∣Uz∣2−∣Vz∣2\\|U z\\|^2-\\|V z\\|^2, to open feature spaces where features can appear, vanish and reappear. Instead of Euclidean proximity, the PA step measures parameter changes under a feature-side metric HtH_t built up from ztzt⊤z_t z_t^{\top} over the stream. The core trick is that right-multiplying UU and VV by Ht1/2H_t^{1 / 2} (and whitening ztz_t ) maps this nonconvex QCQP exactly back to the original DoS-PA problem. So the same one-dimensional problem gives the step size, and the rank-one update just moves along Ht−1zt/(zt⊤Ht−1zt)H_t^{-1} z_t /\left(z_t^{\top} H_t^{-1} z_t\right) instead of zt/∣zt∣2z_t /\\|z_t\\|^2. Missing features are zero-filled, new ones are added by padding U,VU, V and HtH_t, and the metric comes in full, diagonal and sketched versions. Experiments show clear gains over PA and DoS-PA on WDBC with synthetic feature masking, and on the natural IMDB and Crowdsense streams the full variant is competitive with existing open-feature methods.

Critical strengths

The paper is clean to read, and the FULL result on WDBC inc-dec is also a sizable reported gain.

Critical weaknesses

The algorithm is not fully specified for its own setting. Prop. 1 assumes ∣Utzt∣,∣Vtzt∣>\\|U_t z_t\\|,\\|V_t z_t\\|> 0 , but sec. 4.4 solves eq. (8) whenever the margin is violated. With r=1,H=I,z=(1,1)⊤r=1, H=I, z=(1,1)^{\top}, y=+1,U0=(1,−1),V0=(1,0)y=+1, U_0=(1,-1), V_0=(1,0), Eq. (8) is min⁡0<ν<1[11+ν−ν]\min _{0<\nu<1}\left[\frac{1}{1+\nu}-\nu\right]: strictly decreasing, no minimizer. The QCQP is still solvable (boundary branch v+=v0/2,u+=1+∥v0∥2/4ev_{+}=v_0 / 2, u_{+}=\sqrt{1+\left\|v_0\right\|^2 / 4} e ), but that branch isn't in the paper and the initialization of U1,V1U_1, V_1 is never stated. This matters because of an unmentioned invariant: Eq. (10) is Ut+1=Ut(I+αy−αzw⊤)U_{t+1}=U_t(I+\frac{\alpha}{y-\alpha} z w^{\top}) with w=p/κw=p / \kappa, det⁡=1/(1−yα)>0\operatorname{det}=1 /(1-y \alpha)>0, and zero-column expansion preserves rank, so rank Ut,rank⁡Vt≤U_t, \operatorname{rank} V_t \leq min⁡(r,Dinit )\min (r, D_{\text {init }}) forever. In the 30-dim synthetic inc-dec run, block 1 exposes 3 features plus bias, so the factors may be rank ≤4\leq 4 despite r=8r=8. Prop. 1 isn't broken, but "new features expand the model" is not what the specified procedure does.

Questions for authors
  • How were U1,V1U_1, V_1 and new-feature columns initialized, what is the numerical rank of Ut,VtU_t, V_t at the end of the r=8r=8 run, and what does the code do when Utzt=0U_t z_t=0 (resp. Vtzt=0V_t z_t=0 ) with a violated margin?

  • figure 1 shows the update before the prediction and a slack constraint, could you confirm all numbers are test-then-train with the hard-margin update?

Reviewer_SVWMOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SOPA-DoS, a second-order passive-aggressive learning framework for nonlinear classification in open feature spaces, where features can dynamically appear, disappear, and reappear. By incorporating a positive-definite curvature metric and applying a whitening transformation, the proposed method preserves the tractability of DoS-PA updates while adapting to evolving feature dimensions. Experimental results on synthetic and real-world data streams demonstrate improvements in cumulative error rates over several existing methods.

Critical strengths

1 The paper addresses online nonlinear classification in open feature spaces, a practically relevant setting where dynamically evolving features introduce challenges for traditional fixed-dimensional learning algorithms.

2 The proposed framework integrates second-order feature information into DoS-PA learning and derives a tractable update through an exact whitening transformation. The paper also provides theoretical results on feature-index equivariance and reduction to the original DoS-PA formulation.

3 The proposed method achieves improvements in cumulative error rates on several evaluated data streams, particularly with the full second-order metric, suggesting the potential benefits of exploiting feature correlations in open-feature online learning.

Critical weaknesses

1 The framework figure is low-resolution and lacks vector-based rendering, making it difficult to read. Its AI-generated appearance also raises concerns about the clarity and precision of the presentation.

2 The technical components of SOPA-DoS, including the DoS nonlinear classifier, second-order online optimization, whitening transformation, and dynamic feature expansion via zero initialization, feature registration, and matrix expansion, are largely based on existing techniques. Therefore, the main contribution appears to lie in their integration and the derivation of exact update rules, rather than in fundamentally new algorithmic principles. Moreover, recent studies have directly investigated online learning under evolving feature spaces. For example, EPAM [1] extends passive-aggressive (PA) learning to settings where both feature and class spaces evolve. Tthe paper needs to more clearly establish its novelty beyond combining existing techniques and replacing the original DoS-PA update with a second-order metric.

[1] Zhou H, Matsushima S. Online Learning from Capricious Feature Data Streams[J]. IEEE Transactions on Knowledge and Data Engineering, 2026.

3 The theoretical analysis mainly establishes the equivalence of the metric-constrained optimization problem to the original DoS-PA formulation and the invariance to feature reindexing. However, no regret or mistake bounds are provided to characterize online learning performance under evolving feature spaces.

4 The full second-order metric requires quadratic memory and computational complexity in the feature dimension, which may limit its applicability to high-dimensional data streams. Although the paper introduces diagonal and sketched approximations, it provides no experimental results for the SKETCH variant and does not report runtime, memory consumption, or throughput.

Questions for authors

1 Will the source code and datasets be made publicly available in the future?

Reviewer_MGBjOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses an interesting and genuinely under-explored intersection: online learning in open feature spaces combined with a nonlinear difference-of-squares classifier and a second-order update. Particlarly, it proposed a second-order passive-aggressive framework SOPA-DOS for low-rank DoS classification in open feature spaces. The key construction replaces Euclidean parameter proximity by a positive-definite right metric that accumulates streaming feature curvature. This paper is well motivated, technically sound, and clearly written.

Critical strengths

This paper makes four contributions: (i) A formulation of second-order PA learning for low-rank DoS classifiers in an open feature space, together with an exact metric-aware update derived by whitening rather than through an ad-hoc learning-rate rule; (ii) A dynamic feature-expansion mechanism with proofs of feature-index equivariance and of exact reduction to fixed-space DoS-PA; (iv) An evaluation protocol spanning trapezoidal, increment-decrement, capricious, and natural open-feature streams, with baselines selected from both the open-feature and the second-order online-learning literature.

Critical weaknesses

i. In Table 4, more state-of-the-art second-order methods should be compared applied to the same nonlinear model. ii. Most of the comparative methods and baselines were published before 2023 or 2024, which cannot prove the superiority of the proposed method.

Questions for authors

i. Please provide more detailed expalnations for the core formulas from Eq. (1) to Eq. (7). ii. Does the method still reduce to DoS-PA exactly in the presence of the new-feature expansion when Ht=cIH_t=cI before expansion? Corollary 1 should be stated for the expanded metric.

Comments on the paper

1 comment

Dear Reviewers,

Could you take a moment to review the authors' responses and let them know whether any concerns remain or require further clarification?

Best,

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.