Adaptive Passive-Aggressive Framework for Online Regression with Side Information
Authors: Runhao Shi
Jiaxi Ying
Daniel P. Palomar
Venue: NeurIPS 2024 poster (2024)
Keywords: passive-aggressive
online learning
adaptive method
online regression problem
side information
financial engineering
Primary area: online_learning
TL;DR: We introduce an adaptive Passive-Aggressive (PA) framework that leverages side information for optimal threshold selection, ensuring low tracking error and improved performance in online regression tasks.

Abstract: The Passive-Aggressive (PA) method is widely used in online regression problems for handling large-scale streaming data, typically updating model parameters in a passive-aggressive manner based on whether the error exceeds a predefined threshold. However, this approach struggles with determining optimal thresholds and adapting to complex scenarios with side information, where tracking accuracy is not the sole metric in the regression model. To address these challenges, we introduce a novel adaptive framework that allows finer adjustments to the weight vector in PA using side information. This framework adaptively selects the threshold parameter in PA, theoretically ensuring convergence to the optimal setting. Additionally, we present an efficient implementation of our algorithm that significantly reduces computational complexity. Numerical experiments show that our model achieves outstanding performance associated with the side information while maintaining low tracking error, demonstrating marked improvements over traditional PA methods across various scenarios.

Adaptive Passive-Aggressive Framework for Online Regression with Side Information
Runhao Shi, Jiaxi Ying, Daniel P. Palomar The Hong Kong University of Science and Technology (rshiaf, ying @connect ust.uk, hk, palomar@ust. hk
Abstract
The PassiveAggresssvee (PA) method is widely used in online regression problems for handling large-scale streaming data, typically updating model parameters passive-aggressive manner based on whether the error exceeds a predefined threshold. However, this approach struggles with determining optimal thresholds and adapting complex scenarios with side information, where tracking accu- racy is not the sole metric in the regression model. To address these challenges, we introduce novel adaptive framework that allows finer adjustments the weight vector in PA using side information. This framework adaptively selects the threshold parameter in PA, theoretically ensuring convergence to the optimal setting. Additionally, we present an efficient implementation of our algorithm that significantly reduces computational complexity. Numerical experiments show that our model achieves outstanding performance associated with the side information while maintaining low tracking error, demonstrating marked improvements over traditional PA methods across various scenarios.
Introduction
Online learning techniques, initially introduced by Zinkevich 2003),, have gained significant popular- ity due to their robustness in adversarial environments and efficiency in processing large streaming data (Shalev-Shwarte et al. 20122] Orabonal 2019 Hazan 2022). In the online learning framework, an online player continuously makes decisions and receives corresponding losses, aiming to minimize regret. Regret, in this context, refers the worst-case discrepancy in performance compared to the best-fixed decision hindsight, measuring the overhead of identifying the best-fixed decision.
These techniques have found widespread application in modeling regression problems for streaming data, enabling practical applications across various fields (Herbster) 2001 Crammer et al. 2006 Shalev-Shwartz and BeviD 2014). They are extensively applied in diverse domains such as
portfolio selection (Li al. 2012: 22 Li and Hoi 2012). malicious URL detection (Ma et al. 2009
Zhao and Hoi 2013), and time series prediction (Anava al. 2013 2015 Hazan et al. 2018 Lale ct al. 2020 siamis and Pappas 2022 Zhang et 2024)) Without relying on strong assumptions, online regression models demonstrate robustness with regret guarantees challenging scenarios.
Furthermore, their incremental learning schemes make them highly adaptable to streaming data, eliminating the need to retrain the entire dataset and resulting in significant efficiency advantages.
One well-known online regression method the Passive- Sassive-Agressiveee (PA) algorithm (Crammer et al., 2006). PA employs a passive-aggressive updating scheme to learn a weight vector for linear regression problems. It passively maintains the previous weight below certain threshold and aggressively updates the weight when the loss exceeds the threshold. However, determining appropriate threshold can be challenging. small threshold prioritizes real-time tracking accuracy but may lead to overfitting and sensitivity noise, compromising long-term tracking accuracy. Additionally, the selected weight may impact factors beyond accuracy in practical model performance. When
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

additional metrics and side information are available for evaluating performance, PA may struggle to achieve more nuanced weight selection.
To address the aforementioned challenges, we propose an Adaptive Passive-Aggressive online regression framework with Side information (APAS) achieve the following objectives:
Novel APAS framework: We introduce novel APAS framework that integrates side information into PA enhance weight evaluation and selection. This framework adaptively selects the threshold parameter in PA, enabling it to achieve outstanding performance associated with the side information while maintaining a low tracking error.
Efficient algorithm: We develop efficient algorithm using the successive convex approximation (SCA, (SCA,,ccutari et al. (013) to accelerate the computation of APAS. This algorithm rapidly converges to the optimal point, allowing flexibility in selecting measurements integrate side information.
We derive an ((vT) regret bound for our APAS framework for non-convex loss functions, ensuring the robustness and effectiveness of APAS theoretically. This regret bound matches the optimal regret bound for non-convex loss functions.
Regret bound:
Extensive experiments: We conduct an enhanced index tracking task on both synthetic and real financial datasets to validate the effectiveness and efficiency of APAS, which demonstrates the impressive performance of APAS achieving high returns while maintaining small tracking errors.
Notation: Matrices and vectors are represented by bold letters. [T] denotes the set 21, T). The weight vector at time denoted by w, W. The instance and target in an online regression problem are denoted by envelope associated with Xh are denoted as proxĄ* and MA respectively. The Euclidean projection of vector RN onto the set W denoted by [w = arg min ||w ull3. For a continuous function fxr), the set of subderivatives at point a is denoted as 0 The left derivative at is denoted by 0_ f(a) lim f(x)
R&N and E IR, respectively. The proximal operator and Moreau
The derivative at point it exists, is denoted as f'(a).
2
Preliminaries
2.1 Online Learning
Online learning is mathematical framework designed to address optimization problems where objective functions change over time. In this context, an online learner sequentially makes decisions by based on historical loss and receives a new loss (b,) after making the decision. The performance of an online learning algorithm is evaluated using the concept of regret Ry, which quantifies the discrepancy between the algorithm's performance and that of an optimal static parameter setting:
T
T
RT = 1000 min DEX
(( Σ
where X' denotes the feasible set. An online learning strategy converges to the optimal static parameter setting if Rt = o(T',, indicating the average performance gap diminishes as the number of iterations T' approaches infinity. In the case of convex loss functions, different regularization functions can be employed to achieve various optimal regret bounds, depending on the assumptions about the curve of
the loss function (Zinkevich] (0033] Hazan et al.) 2007 Hazan and Seshadhri] [2007 [2009). Adaptive regularization methods, which select the regu Iagulaaization term dynamically. have also been proposed
and widely adopted various domains (Duchi al. 2010 201
Van Erven and Koolen 2016).
2.2 Passive-Aggressiv Method
The Aasreve-gggressive (PA) method is a popular online algorithm utilized for regression problems involving streaming data (Crammer al.) (2066). In online regression problem, we receive an instance E RV and predict the target value w.x, using the incrementally learned vector w. where the ground truth yı. PA predicts the next weight vector by solving the following optimization problem:
W++1 arg min 1 1| w.ll3
subject to
(=(w; (xt, v1)) 0,
(1)
WERY

---

where l is the e-insensitive hinge loss function defined as follows: w x - y/ E,
0 le (w; (x, = { TT x-
otherwise.
Intuitively, PA performs an aggressive update when the discrepancy between the predicted value and the ground truth exceeds the threshold E, and passively maintains the previous weight when the discrepancy is within the threshold E. A smaller threshold may prioritize real-time tracking accuracy could result in overfitting and compromise long-term performance. Therefore, the selection of the threshold significantly influences the performance. Additionally, relying solely on tracking accuracy without considering side information may limit the method's potential performance.
Proposed Method
In this section, present novel framework that incorporates the side information into PA for evaluating and selecting weight vector W(+1 and threshold E. This framework adaptively selects select by balancing real-time tracking accuracy and side performance, achieving performance comparable to the optimal parameter setting, supported by theoretical regret guarantees. Additionally, propose efficient method based on the successive convex approximation technique, which significantly reduces time complexity and accelerates computation.
3.1 PAS Framework
In this section, we present novel Passive-Aggressive with Side information (PAS) framework that considers the trade-off between real-time tracking accuracy and side performance. PAS builds upon two variations of PA, each providing closed-form solutions for given value of e, without imposing any constraints as follows:
We We + sign [y:- -w. x.] TXXr
W x, - Vel S E, otherwise,
Wc-1(E) =
(2)
where
( (/w]x. - - - W/Tx ye /) 20))
(PA)
(3)
(PA-II),
and PA-II refers to a robust PA method with aggressiveness constant C. For the regression problem with constraints, the final weight determined by performing projection onto the feasible set W:
W W (E)
arg min| w wEW
(E)
Although Crammer et al. (2006) does not include a projection operation, we demonstrate in Appendix D that PA with lazy projection still achieves comparable bound to Crammer (2006).
Suppose that at each round t, we have a lower semi-continuous convex function ht (w) that quantifies the performance associated with the side information. To leverage this information and enhance the performance of the weight selection, we integrate (,(w) into the projection step of the PA method and propose the PAS framework for selecting the next weight vector:
(:+1(s) arg min WEW
h4 (u((W) + 2A ||w ( PrOx (We+1 (E))
(5)
where prox Ah, denotes the proximal operator. In PAS, À serves as the trade-off parameter that quantifies the preference between tracking accuracy and side performance. When he(w) is set as constant, the PAS model essentially simplifies to the original PA method with lazy projection, as shown in Equation 44. By leveraging the proximal operator, we can explicitly integrate side performance into the weight selection process by modifying h, (w).
From another perspective, ||w Wr+ (e) can be viewed as a regularization term that passively aligns with the trend of the ground truth. In contrast, h (w) serves as the primary loss measurement, acting as the main driver for aggressively updating the weight vector. understand how the weight vector W (E) is selected, we discuss the following two scenarios:

---

he ()) side information
Update 1
parameter
proxan (w,))
W (et)
Man. (H))(()))
PA weight
Wt+1 (Et)
(e
weight
loss
Figure 1: Adaptive learning scheme of APAS.
[w!x: - yel I s, we have (c+1 = arg min (he(w) 2x w wellB). This implies that aim to passively maintain the same weight setting the previous round while aggressively updating the weight to improve side performance for small real-time tracking errors.
If ww.x yel
E. we have (++
arg niw (h: + 2 lw we
1 w sign We - w x T(X; + const). This implies that we aim to passively maintain the same weight setting the previous round while aggressively updating the weight to improve real-time tracking accuracy and side performance for large real-time tracking errors.
This framework ensures that while the selected weight passively follows the general trend of the data through the f2-norm, actively seeks to improve performance based on the side information, thus achieving balance between stability and adaptability. Consequently, Wz+1 (x) corresponds the point that defines the infimum of the trade-off between side performance h, and real-time tracking accuracy. The infimum is essentially the Moreau Envelope (Parikh et 2014), which define as the loss function with respect E:
fi(e) = inf weW
hw(w) + 2A ||w W ( = MAs, (We+1(E))-
(6)
Here, MAR, represents the Moreau Envelope of Ah, with respect to Aw (e). In this way, we establish connection between the determined weight vector w (E) and loss function fe(e) with
3.2 Adaptive PAS
The parameter e a crucial component in PAS, as it determines the weight selection W++1(e) and the performance evaluation fi(E). While the trade-off parameter has intuitive interpretation, the process of setting & is less straightforward. A smaller threshold may prioritize real-time tracking accuracy but could lead to overfitting, affecting long-term accuracy and compromising side performance. Conversely, larger might stabilize performance but result in underfitting. Hence, our objective is develop adaptive algorithm that can dynamically choose the value of based the designed loss function fe(e). To facilitate the dynamic selection of e, we introduce the following assumptions:
Assumption 1. The feasible domain D of the parameter is bounded with D =[v,, Assumption 2. The subderivatives of ft(E) is bounded, such that suPeED, [0f((e) < G.
[v, and 0.
Our proposed adaptive parameter updating scheme for w and Et+1 is as follows: At each round we receive information up to time and use select the next weight vector w++ (sx) with e.. Subsequently, we update E based on the loss f(()). The overall procedure is illustrated in Figure Under Assumptions
T andd] the updating rule for 51+1 is formulated follows:
Et+1 1lp [st Thrr (st)]
(7)

---

where [p]e]] min (max ( D). 7/
LVD and G. 1TD [ww]x vall Here, 0r(e) is Gvvt'
modified derivative of fe()), which is defined as follows:
[f((E) (e) (0.x
if Ser otherwise.
(8)
Since (1) is a continuous piecewise function with respect to E, being affine on E < S and constant otherwise, and Mar, (E)) is a strongly convex function, their composition f((e) becomes piccewise-convex function. Thus, f((E) is differentiable and strongly convex for < St. and constant otherwise. The derivative of fe(E) for & < E can be calculated using the chain rule:
(e(()) aMas, (Wi+1(E)) aMM., (Wi1(EE) (W(+1(E) (e)
de
Òe
The derivative of the Moreau Envelope MAN, with respect to (()1(E) can be calculated as follows:
OMAi, (We+l(E)) (w)+
(w--i(e) proxxs, (We+ (e)))
(10)
To summarize, the overall updating scheme for E and weight vector W141 is outlined in Algorithm
I This adaptive mechanism enables the framework to adjust dynamically to changing environments,
eliminating the need for manually set static threshold. Intuitively, the update process for works as
follows: If the real-time tracking error is lower than & (i.e., Sa < St), then according to Equation (8) the derivative (ex) 2 Based on the update rule in Equation (7). this suggests that & reduced to
avoid underestimating the tracking accuracy. Conversely, when the real-time tracking error exceeds
Er. the update mechanism adjusts E, to strike a balance between minimizing side loss and maintaining tracking accuracy.
Algorithm 1 Adaptive Passive- Uussive-AAgressivv Framework with Side Information (APAS)
1: Input: trade-off parameter A.
2: Initialize E E 'D and w1 W.
3: for f == 1......, do
4: Calculate W++1 (Et) according to Equation 2
5: Update (E+) prox (Wr+1 (Ex));
6: Update E++1 according to Equation 7
7: end for
8: Output: (T41(eT).
3.3 Efficient Algorithm
Algorithm T requuirs the calculation of the proximal operator at each iteration (see Line which can be computationally expensive. While this problem can be addressed directly using the Interior Point Method (IPM) with an off-the-shelf solver (Nemirovski) 2004), it generally incurs high-order time complexity of O(N3.5), making it inefficient for large-scale problems.
To improve efficiency, we propose an algorithm that utilizes the Successive Convex Approximation (SCA) framework accelerate computation (Scutari et al. 2013). SCA reduces time complexity by iteratively optimizing more manageable surrogate function in place of the original objective
function until convergence is reached (Sun et al., 2016 Scutari and Sun 2018). We denote the objective function of Problem (5) as Ue (w(w) h (w)
21 w W(+1(E) (E) 3 To apply SCA, the
surrogate function, denoted as ūt (w wh), should be strongly convex and satisfy the condition that Vū,("" w*) Vu, (w"),, ensuring the gradients match at w
We employ the first-order Taylor expansion to approximate h4 (w),, defining the surrogate function Te (w w as follows:
(Witz(6)) - Vhe(w()) const.
ūg (w] w
21 w w
5

---

By simplifying the formulation, we iteratively optimize the following surrogate problem instead:
minimize
ww--qa q"11
subject to w E W,
(11)
wER
where = w - such as being a probability simplex or a hyperplane, the optimization problem in Equation (IT) admits
Xh (w)). When the feasible set W exhibits special geometric properties,
closed-form solution, provided in Appendix C
(Pllomar and Fonollosa 2005 Duchi al. 2008
Algorithm 2 Efficient Algorithm for
Input: (x+1(E), X, and Vhe.
2: Initialize == 1, w W and (-*).
3: repeat:
4: Solve (1I with q" - (e)1(e) A A (w*) and the optimal point as w
5: Compute w =w to (WAt) w");
6: k k 11;
7:
until convergence
8:
Output: (++1(e) = wk+1
The overall procedure for efficiently calculating 5 is encapsulated in Algorithm Empirically, this method converges very quickly, reaching the optimal point within only a few iterations. Additionally, it does not require calculating the objective value of he(w), making it more flexible for incorporating
side information. By setting .*+1 = 7* (1 - pry*) with (0, 1) and 70 < 1/p, Algorithm 2 guarantees convergence to the optimal point of Problem (5). This convergence behavior is analyzed
in Proposition]] [ with the proof provided in Appendix
B
Proposition 1. With 7 (0, 1]. 7hh
and Σx 2 +oo, Algorithm 2 converges in a finite
number of iterations to optimal solution of (5) every limit point of the sequence {w" k== (at least one such point exists) is an optimal solution of (5)
3.4 Regret Analysis
The loss function ft(E) in the APAS framework is piecewise convex, leading to a scenario where it generally non-convex and non-smooth. In general convex online learning settings, optimal regret bounds are well-established, typically O(VT) for T iterations. However, achieving these optimal regret bounds in non non-convex online learning scenarios poses significant challenges due to the inherent difficulties optimizing non non-convex functions. Strategies address these challenges often involve either working with a restricted class of loss functions or focusing on computationally
feasible notion of regret (Hazan al. 2017 Gao et al., 2018). Additionally, some approaches dealing with general non-convex losses rely on access to sampling oracles, which are impractical in many real-world applications (Maillard and Munos 2010; Krichene al.) [2015] [Agawall et al.) 2019; Suggaaa and Netrapalli 2020). Despite recent advances, obtaining optimal regret bounds in non-convex settings remains an open and active area of research.
In work, demonstrate that Algorithm can achieve the optimal O(VT) regret bound. Our approach is novel in that it does not rely on restrictive assumptions or oracles. Instead, it leverages the properties of the function curve and quasi-convexity, as detailed in Proposition and Proposition in Appendix A Although fz( is non-convex and non-smooth, its behavior along the function curve enables us derive favorable regret bounds, achieved by carefully designing the learning rate n) and the updating rule for E++1. The following theorem formalizes the regret bound of our approach:
Theorem 2. Under Assumptions and Algorithm Jachivvs the following regret bound for T > 1:
T
T
D&G? VT -
RT = > f((E.) min > file) S2
$2
(12)
EED
1=1
where D, and G are constants defined in Assumptions Mandd 2
The proof of Theorem 2 is provided in Appendix A Theorem 2 ensures that Algorithm I accheves performance that comparable to the optimal parameter setting over the long term. Crucially, our approach does not depend on restrictive assumptions or external oracles. Instead, it dynamically adjusts the parameter e by responding to real-time changes, allowing for optimal performance in both stable and volatile environments.

---

4 Experiments
To demonstrate the performance of our proposed methods, we conduct experiments using stock lists from S&P 500 and NASDAQ 100 from Yahoo! Finance TM for enhanced index-tracking task. Enhanced index tracking is a passive portfolio selection strategy that aims to enhance returns by incorporating tactical tilts towards specific styles, while still maintaining a portfolio that closely mirrors an index (Dose and Cincotti 2005] Benidis et al.) 2017 2018 Xu et al. (022).
In our experiments, the instance X, represents the stock return at time 4, where Ti,. (Pr.: - PP-1a))---)) with Pt.i denoting the price of asset
time I. The target value Y/8 is the index return at time f. In the enhanced index tracking task, we sequentially select the portfolio weight w, at each iteration to mimic the trend of the index yt, where the feasible set is the probability simplex W {w E I 1 w 1, w 2 03. To achieve higher return, rather than merely tracking the index, we define the side information as the negative log return, i.e., hy (w) = log((1 + x.(w).
We measure the performance of different methods using tracking error and excess cumulative return. The tracking error is quantified by the magnitude of the daily tracking error (MDTE), computed by:
1 Tracking Error 7
Σ (wTx, - w1)²
(13)
The excess cumulative return is used to assess the performance relative to the tracking index, which represents the discrepancy between the logarithmic cumulative return of the strategy and the index:
T
T
Excess Cumulative Return
log (1+w.xx) x1)
Σ
log (1 + vc)
(14)
Benchmark: In addition to the base model PA, we compare the performance with two versions of SLAIT: SLAIT-ETE and SLAIT-DR (Benidis et al. 2017). SLAIT-ETE focuses tracking accuracy,
while SLAIT-DR aims to replicate the index while avoiding excessively large drawdowns.
4.1 Synthetic Data Experiments
We generate synthetic data by sampling N(, E). where μ E RV and Σ E NxN are the sample mean and sample covariance matrix calculated from the real market data from the S&P 500. The corresponding index value is generated by:
Vr
+ w,
where w (0, 82) represents Gaussian noise, and w' is the true weight of the index components. We generate 50 datasets to test the average performance of different methods, with each dataset containing T = 200 observations and N 100 dimensions. The training set consists of 50% of the data, while the test set contains the remaining 50%. Both SLAIT-ETE and SLAIT-DR use rolling training window of 100-day observations, rebalanced every days.
Figure 2 presents the performance comparison and ablation experiments of the proposed APAS framework against benchmarks the synthetic dataset. Specifically, Figure 2a illustrates the comparison of excess return and tracking error for APAS and the benchmarks, where the curve for APAS is generated by varying the trade-off parameter X. For small A, APAS exhibits relatively low tracking error, while for large X, APAS achieves higher returns with a slight sacrifice in accuracy. Compared the benchmarks, APAS demonstrates higher excess cumulative return for the same level of tracking error and lower tracking error for the same level of excess cumulative return.
Figure 2a also shows how varying the trade-off parameter À affects the balance between side performance (measured as excess cumulative return) and tracking error. Generally, can be selected based on the specific problem's 's considerations, such as the magnitude of side information and the desired balance between minimizing tracking error and maximizing side performance. In practice, can be determined using domain knowledge and cross-validation For example, if specific range of tracking error is desired, the bisection method can be employed during cross-validation to identify the value of À that maximizes side performance while meeting the tracking error requirement.
Figure 2b compares the performance of the fixed parameter setting with the adaptive one, where PAS refers to the non-adaptive version of APAS with fixed The closer the curve is to the top left, the
7

---

ARS grap)
Ecces Cuntubae Ruaum
4043 spop
2.03
PAS (2-22-3)
PAS iu-
0.0
fe-2
0.0
26 36-4)
PA -2-443)-4
FA Ic- 6e-4)
SLAIT-O8+
SLAIT-ETE+
806015
600033
0.8003
0392215
8:60.00
0.30033
20092/5
Trading
(a) Trade-off between tracking error and excess cumulative return of different methods.
(b) Ablation study: Comparison PAS with fixed parameters and APAS.
Figure 2: Comparison of tracking emror and excess cumulative return the synthetic dataset.
Excosa CumudiDD Nutum
Tractrn Eecr
6006
25
130
75
122
SLAIT-ETE SLAIT-OR
APAS [prpp Lexd))
(prup,
Figure 3: Tracking error and excess cumulative return over time for different methods on the synthetic dataset.
better the performance. Even without knowing the optimal parameter setting for e, the adaptive updating scheme in APAS ensures relatively good performance.
We also compare the trends of tracking error and excess cumulative return over time T in Figure 3 This figure shows that both the PA method and the proposed APAS method exhibit relatively low tracking error. Although the PA method has the minimum tracking error, achieves the lowest excess cumulative return among methods. In comparison, the APAS method maintains comparably low tracking eиror but with a significantly higher excess cumulative return.
It is widely acknowledged that heavy-tailed distributions offer more realistic model for data- generating processes financial markets compared to Gaussian distributions (Cardoso et al. 2021 2022). To further evaluate the performance of APAS in highly volatile and noisy environments, include a detailed comparison of our proposed methods under various data and noise distributions, available in Appendix
4.2 Real Market Data Experiments
We conduct simulations on well-known indices using real market data from Yahoo! Finance TM, the S&P 500 Index and the NASDAQ 100 Index. For the S&P 500 Index, we collect data from 2021-01-01 to 2023-01-01, totaling T 503 daily observations with N 453 stocks. For the NASDAQ 100 Index, we collect data from 2019-01-01 to 2021-01-01, also totaling T = 503 daily observations with N 101 stocks. For the and APAS methods, 50% of the data used for training, with weights updated adaptively each day based on the latest data. For the SLAIT-ETE and SLAIT-DR methods, the training lookback period 50% of the data, with rebalancing occurring every 10 days.

---

Figures 4 and 5 show the performance comparison on the S&P 500 and NASDAQ 100 datasets, respectively. As observed, with small À setting, APAS has a comparable tracking error PA while yielding better excess cumulative return. With large À setting, APAS exhibits a higher tracking error but achieves the best excess cumulative return among all methods. The real market comparisons across different datasets demonstrate that the proposed APAS model provides superior trade-off between tracking error and excess cumulative return compared to the benchmarks.
1.00
0.1-
1004
Tridknn Eneer
Exceess Cumruntiv
2.00
1000
16
130
150
120
150
260
350
S6P500
SLAIT-OR
APAS (pmpp Am Te-1)
(prop.. Ie-3)
Figure Tracking error and excess cumulative return over time T for different methods on S&P 500 dataset.
Troding Eror
1.00
Excees Cursestiv
1.00
1.00
-.25
SLAIT-ETE
ARAS (pmp. Am-T-11
Figure 5: Tracking error and excess cumulative return over time T for different methods on NASDAQ
100 dataset.
4.3 Speed Comparison of Acceleration Schemes
This section evaluates the computational efficiency of our proposed method (Algorithm) 2 in Section 3.3 across different problem dimensions N. The benchmarks include the widely-used convex problem solver CVXR Fu et al. (2020), Projected Gradient Descent (PGD), and Alternating Direction Method of Multipliers (ADMM, Boyd et al. 2011).
We assess the performance of the proposed method over 100 randomized trials, comparing the convergence speed and CPU time (in seconds), shown in Figure b The left panel of Figure illustrates the average convergence gap versus the number of iterations on a dataset with N = 1000 dimensions, comparing the proposed method with PGD and ADMM. The right panel displays the average CPU time for each method across different problem dimensions N. The results demonstrate that our method converges rapidly the optimal point, being nearly 100 times faster than CVXR and ADMM and 10 times faster than PGD for gigh-dimensional data.
To further assess whether time complexity is affected by including different types of side information, we conduct additional experiments using various forms of side information beyond the log return h (w)) log(1 + r. w). such as:

---

Switching cost: hw(w) = 1|w well1;
Weighted & norm: he(w) = Ei= Pilwoel:
Group Lasso: h₂(w)= = Ex= lellwe.lla where ,i...., are m disjoint groups.
We evaluate the performance of the proposed efficient method with different types of side information functions over 100 randomized trials, comparing the average CPU time (in seconds) in Table [ From [ it appears that group Lasso incurs higher CPU times, especially for larger dimensions N, due the added complexity of caleulating norms for disjoint groups. In general, while the type of side information can impact the computational time, the APAS framework maintains efficiency across different scenarios.
1.00-
24-42
2.300
88
Time
2.00
2.00
11
100
30c
500
1000
1500
2002
Number llerations
Figure 6: Average convergence speed and CPU time comparison of 100 randomized trials N-
dimensional datasets of Algorithm
log return
switching cost
weighted norm
group Lasso
N 500
0.00084 T 0.00051
0.00084 1 0.00163
0.00045 1 0.00051
0.00162 1 0.00054
N 1000
0.00119 1 0.00050
0.00084 1 0.00048
0.00084 1 0.00052
0.00252 1 0.00154
N 2000
0.00181
0.00103
0.00156 + 0.00129
0.00113 = 0.00043
0.00344 0.00138
NV 5000
0.00335 = 0.00080
0.00356 + 0.00125
0.00282 = 0.00122
0.00702 + 0.00205
Table 1: Average CPU time (in seconds) for different side information functions over 100 randomized
trials of Algorithm
5 Conclusions
In this paper, we addressed the limitations of the Passive-Agrresive (PA) algorithm in online regres- sion, particularly in determining the appropriate threshold and integrating side information for weight selection. To tackle these issues, we proposed the APAS framework, which incorporates side informa- tion into PA. Our APAS framework adaptively selects the threshold parameter, enabling it to leverage side information for improved performance while maintaining low tracking error. We demonstrated the robustness and effectiveness of APAS through an O(VT) regret bound, even with non-convex loss functions. Additionally, we developed an efficient algorithm that significantly reduced computational complexity without compromising theoretical performance guarantees. Comprehensive experiments on synthetic and real market datasets validated the effectiveness and efficiency of APAS, highlighting its practical applicability across various scenarios.
Acknowledgments and Disclosure of F Funding
We would like to thank the anonymous reviewers for their helpful comments. This work was supported by the Hong Kong GRF 16206123 23 research grant and the Hong Kong RGC Postdoctoral Fellowship Scheme of Project No. PDFS2425-6505.
10

---

References
Agarwal, N., Gonen, A., and Hazan, E. (2019). Learning in non-convex games with an optimization oracle. In Conference on Learning Theory, pages 18-29. PMLR.
Anava, O., Hazan, E., Mannor, S., and Shamir, O. (2013). Online learning for time series prediction. In Conference on Learning Theory, pages 172-184. PMLR.
Anava, O., Hazan, E., and Zeevi, A. (2015). Online time series prediction with missing data. In International Conference on Machine Learning, pages 2191-2199. PMLR.
Benidis, K., Feng, Y., and Palomar, D. P. (2017). Sparse portfolios for high- -igee-iinniional financial index tracking. IEEE Transactions on Signal Processing, 66(1):155-170.
Benidis, K., Feng, Y., Palomar, D. et al. (2018). Optimization methods for financial index tracking:
From theory practice. Foundations and Trends Optimization, 3(3):111-279
Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J., et al. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning, 3112
Cardoso, J. V. d. M., Ying, J., and Palomar, D. P. (2021). Graphical models in heavy-tailed markets. In Advances in Neural Information Processing Systems, volume 34, pages 19989-20001.
Cardoso, J. V. d. M., Ying, J., and Palomar, D. P. (2022). Learning bipartite graphs: Heavy tails and multiple components. In Advances in Neural Information Processing Systems, volume 35, pages 14044-14057,
Crammer, K., Dekel, O., Keshet, J., Shaley-Shwartz, S., and Singer, Y. (2006). Online passive- aggressive algorithms. Journal of Machine Learning Research, 7(19):551-585
Dose, C. and Cincotti, S. (2005). Clustering of financial time series with application to index and enhanced index tracking portfolio. Physica Statistical Mechanics and its Applications, 355(1):145-151.
Duchi, J., Hazan, E., and Singer, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7).
Duchi, J., Shalev-Shwart S., Singer, Y., and Chandra, T. (2008), Efficient projections onto the b-aball for learning in high dimensions. In International Conference on Machine Learning, pages 272-279.
Duchi. J. C., Shalev-Shwaree S., Singer, Y., and Tewari, A. (2010). Composite objective mirror descent. In Conference on Learning Theory, volume 10, pages 14 26.
Fu, A., Narasimhan, B., and Boyd, S. (2020). CVXR: An R package for disciplined convex optimization. Journal of Statistical Software, 94(14):1-34.
Gao, X., Li, X., and Zhang, S. (2018), Online learning with non-convex losses and non-stationary
regret. In International Conference on Artificial Intelligence and Statistics, pages 235-243. PMLR.
Hazan, E. (2022). Introduction to online convex optimization. MIT Press.
Hazan, E., Agarwal, A., and Kale, S. (2007). Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169-192.
Hazan, E., Lee, H., Singh, K., Zhang, C., and Zhang, Y. (2018). Spectral filtering for general linear dynamical systems. Advances Neural Information Processing Systems, 31.
Hazan, E. and Seshadhri, C. (2007). Adaptive algorithms for online decision problems. In Electronic Colloquium on Computational Complexity, volume 14.
Hazan, E. and Seshadhri, C. (2009). Efficient learning algorithms for changing environments. In International Conference Machine Learning, pages 393-400.

---

Hazan, E., Singh. K., and Zhang, C. (2017), Efficient regret minimization in non non-convex games. In International Conference Machine Learning, pages 1433-1441. PMLR.
Herbster, M. (2001). Learning additive models online with fast evaluating kemelss. In Computational Learning Theory: 14th Anmual Conference Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001 Amsterdam, The Netherlands, July 16-19, 2001 Proceedings 14, pages 444-460. Springer.
Krichene, W., Balandat, M., Tomlin, C.,, and Bayen, (2015). The hedge algorithm on a continuum. In International Conference on Machine Learning, pages 824-832. PMLR.
Lale, S., Azizzadenesheli, K., Hassibi, B., and Anandkumar, A. (2020). Logarithmic regret bound in partially observable linear dynamical systems. Advances in Neural Information Processing Systems, 33:20876-20885
Li, B. and Hoi, S. C. (2012). On-line portfolio selection with moving average reversion. In International Conference on Machine Learning, pages 563-570.
Li, B., Zhao, P., Hoi, S. C., and Gopalkrishnan, V. (2012). PAMR: Passive aggressive reversion strategy for portfolio selection. Machine Learning, 87:221-258.
Ma, J. Saul, L. K., Savage. S., and Voelker, G. M. (2009), Identifying suspicious urls: an application of large-scale online learning. In International Conference on Machine Learning, pages 681-688.
Maillard, O.-A. and Munos, R. (2010). Online learning in adversarial lipschitz environments. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 305-320. Springer.
Nemirovski, A. (2004). Interior point polynomial time methods in convex programming. Lecture notes, 42(16):3215-3224,
Orabona, F. (2019). A modern introduction to online learning. arXiv preprint arXiv:
Palomar, D. P. and Fonollosa, J. R. (2005). Practical algorithms for a family of waterfilling solutions. IEEE Transactions on Signal Processing, 53(2)68866655
Parikh, N., Boyd, S., et al. (2014), Proximal algorithms. Foundations and trends@ in Optimization, 1(3):127-33.
Scutari, G.. Facchinei, Song, P., Palomar, D. P., and Pang. J.-S. (2013). Decomposition by partial linearization: Parallel optimization of multi-agent systems. IEEE Transactions on Signal Processing, 62(3):641-656.
Scutari, G. and Sun, Y. (2018). Parallel and distributed successive convex approximation methods for big-data optimization. Lecture Notes in Mathematics, C.I.MEE, Springer Verlag series.
Shalev-Shwartz, S. and Ben-David, S. (2014). Understanding machine learning: from theory to algorithms. Cambridge University Press, USA.
Shalev-Shwartz, S. et al. (2012), Online learning and online convex optimization. Foundations and Trends@ Machine Learning, 107-1494
Suggala, A. S. and Netrapalli, P. (2020). Online non-convex learning: Following the perturbed leader optimal. In Algorithmic Learning Theory, pages 845-861. PMLR.
Sun, Y., Babu, P., and Palomar, D. (2016). sniorization-mininizatoooo algorithms in signal processing, communications, and machine learning. IEEE Transactions Signal Processing, 65(3):794-816.
Tsiamis, A. and Pappas, J. (2022). Online learning of the kalman filter with logarithmic regret. IEEE Transactions on Automatic Control, 6875)27774
Van Erven, and Koolen, W. M. (2016). Metagrad: Multiple learning rates in online learning. Advances in Neural Information Processing Systems, 29.
12

---

Xu, F., Ma, J., and Lu, H. (2022). Group sparse enhanced indexation model with adaptive beta value. Quantitative Finance, 121.0)
Zhang, Z., Cutkosky, A., and Paschalidis, Y. (2024). Unconstrained dynamic regret via sparse coding. Advances in Neural Information Processing Systems, 36.
Zhao, P. and Hoi, S. C. (2013). Cost-sensitive online active learning with application malicious url detection. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 919-927.
Zinkevich, M. (2003). Online convex programming and generalized infinitesimal gradient ascent. In International Conference on Machine Learning, pages 928-936.
13

---

Appendix
In the following sections, we present the theoretical proofs for Theorem 2 and Proposition 1 Addi- tionally, provide closed-form solutions for Algorithm 2 under special cases not explicitly stated in the main manuscript, along with a detailed specification of the regret bound analysis for the Passive- Aggressive (PA) method with lazy projection. Furthermore, we include additional experiments to assess the robustness of the proposed APAS framework under various conditions.
A Proof of Theorem 2
The proof of Theorem relies the first order bound of fo(E), shown in the following proposition. Proposition 3. Under Assumption and fe(e) is quasi-convex on D = [v, D). With the definition of (e(E) in Equation ( and Se = Dp [ vell, for all t [T] and all E D, we have
fe(v) fe(w)= s (v) ū).
(15)
where ū = min u, Ce).
The proof of Proposition 3 detailed in Appendix to Proposition 3 we have:
A.l L E arg min Ei= f(()). According
fe((t) - f(((s) s (E) - 2),
where 2; min (5r, J. Since Ex+1 11 [E+ (++] and employing the Pythagorean theorem,
we have:
(Er+1 - 2x) (1lp [e+ - n=ār(E+)] - 2x)² s (e+ (1:)((E)) - 2z)²
By properly reformulating the inequality, we have:
(e(E))(E -2) S Φe(z() (x) G.
2
where dz()))
5. 201221 and (1t(
S.t 26
Summing from to T, we have:
2n
2n
T
Rr
Σ
(fc - fc
G2
Σ
(r(2)) ()((z)) +
2
1=1
G T
(z)) w/T (2T) + Σ (di(ze) the (2+-)))))))
n
2
Thus, we only need to bound di (21) - 2/4 1/2-1(21-1)
Proposition 4. Set T)t
LVD with &e = 1l [[ Vell. Under Assumptions 7 and 2 for
Gvvi
ex arg mDn Eim fi(s), and mnin(Cr, e+}, we have:
D 1
1
01(+1) - w (z+ 1) <
(16)
2
1/t
3 20-22 and (i((
572m -284412
where (x(2))
21
2tje
The proof for Proposition 4 is detailed in Appendix
A.2
Based on Proposition 4
we have
D
G²
T
D&G
RT
Mt
<
2
-
vT
WTT
2
1=1
14

---

A.1 Proof of Proposition 3
Proof. First show that f(()) is quasi-convex on D. The loss function fe(E) is the Moreau Envelop of WE+1(E), which is given by:
f((e) MAd. (We+1(e)) = inf weW
(u(w) +
w w. w
2X
Here, MAk, (W++1 (5)) is strongly convex and smooth with respect to we+1 Furthermore, W (s)
piecewise continuous affine function of shown in Equation 22) It is constant if [w/ X y/l and an affine function of e otherwise. Since f() is composite function of the strongly convex function Mas, (W+)(EE) and the piecewise continuous affine function W++1 (E), we have:
f((e) strongly convex function
E E [v, Se)
const
E (Se. D],
where C:
1Ip [|w]x, x yell Thus, is straightforward to verify that ft(e) is quasi-convex.
To verify the inequality (15). we analyze different cases. First, we consider the simplest case where which implies that [w]x; V/i and fe(=) is constant D [v, D]. Since (r()) 2 0 according to (8) and û = v. straightforward to verify that:
fe(w) fu s (v( ū).
Then, we consider the case where Çe = D, which implies that ww] x; yel 2 and f((s) is strongly convex on D [v, D]. Here, u. and consider the following cases:
1. For v < Se. we have ğe (v), and thus, by convexity:
f((v) f((u) - (())(v u) (c(v)(v ū).
2. For = G:: 0_ f(() 2 0, then
and by convexity:
[((1) (u) v a- ( u) (v) ū)
If (-(b)( < <0, then (e(v) 0. and we have:
S((v) - (w) - 8 S - u) S (v)(vv 7).
f((E)
f((E)
a.f(3)
(a) f-((())) < 0.
0-f((())
Figure 7: Illustration for curves of f((s) with <G. < D.
Next, consider the case where Se D, meaning that ww yel. Figure illustrates the curve of fe(. The curve of the loss function f((s) could be divided into two categories: when fe(G) < O, we obtain a convex function, as shown in Figure 7a when fc() 2 0, we get quasi-convex function, shown in Figure 7b To verify the inequalities 15). consider the following cases:
F
1. For Su < Sr, we have (o(2) f((v):
15

---

(a) If S < St, then ū = minfu, 5.} = u. We can directly verify inequality 15 directly by convexity:
f((w) S f(()((v - u) = 5c(v)(r - u).
(b) If 4 Suu u < D, then ū = min(u, (t) = G. By convexity, we have:
[&(1) f(()) f((v) S((G)) S f((v)(o (t) (x(v)(
2. For S e D, have (((e) max {0, (.(())
(a) If S &e and 0_ ((())) > then (v( = fcl(e).. Thus, by convexity:
fe(v)-f((u) = fe()) - 8 f( s S- (((s)(((-- = (v))
I a < Ge and fc(() - O, then (v) 0. Since fi(E) is strongly convex on
[V, Sel. we have fe(u) > ft(G). Thus, we have:
fc(v) fe(u) f((G)) f((u) (e(u)(v u) (.( ū). (b) If S u S D, is straightforward to verify that f((v) fi(u) = and ğe (v)(v (t) 2
0. Then we have:
f((v) fa(u) g.())(v () ( ü).
Thus, we prove inequality [5
A.2 Proof of Proposition
Proof. Let 01(21) -5-25 and v1(2)) 5. 221+11 where ex E arg min Σt= f((E) and 2m
2m.
= min(Se, Let Gr = DI [[wTxx xt - wel. and consider the following four situations for GVD.
GVvi
=f 2 G--1 and E* 2 G::
01(2)) -1--1(2-1) ( (1-1(61-11
<3 - 2315:
221G1-1
21Jt
2//--1
2
Çe-1 Se
+
2
71
T/-11
1h-
Th.
2
GVVEL
(VI-I- vI)
+
2
11t
T--1
VD
2
2
T
ef 2 G-1 and e* < G::
(c(z)) ( 0r(5") (2-1((1-11
Et -0,5*
2, -2E
21)r
21/-11
20,E*
2E,E"
[Since 8* 2 G-11
2m
21/t-11
D2
1
1
<
2
1/t
Me--1
16

---

if < G--1 and Ex 2 Se:
(((2)) 1/ 1 (b((e)) 16")
67
-2815t
-244
21
21/--1
2015t
Et
22461-1
[Since St-1
217
2171-1
D
1
1
2
7/t
97-11
Ef < (c-1 and Ex < G::
Φc(2r) - - 1/1-1122-111 = 0e(E") V2-1(==)
E, -2tE" E, - 2E
21)
2T/--
D2
1/1
Me-
To summarize, have
D
1
dr(()) - (1-1((1-1)
2
Tht
B Proof of Proposition T
Proof. Since (Scutari et al., 2013, Assumptions A1-A4) hold and (5) a convex problem, the proof for Proposition (1) tollows directly from (Scutari et al. 2013 Theorem 3).
C Efficient Euclidean Projection Methods
C.1 Projection onto the Probability Simplex
Proposition 5 (Projection onto Simplex (Palomar and Fonollosa 2005)). When W = {w E R 1w = 1, w Z 0}, problem 11 has closed-form solution given by:
un = [q. + +k=] mn+ i 1,,..., N,
(17)
where k = di are the sorted elements of q arranged such that o 2 g
with max { |i
1
N N: [ +
E1-E g > 0). and
C.2 Projection onto Norm Ball
Proposition 6 (Projection onto & Norm Ball (Duchi et al. 2008 ). When W- {w E R
||/] <
c) for some constant 0. problem [T] has closed-form solution given by:
w sign(g.) [| - -)+ i= =
(18)
where is chosen such that E [19.1 -] The value of T can be efficiently found by sorting 1g/1 and using a bisection search.
D Regret Analysis of PA with Lazy Projection
Lemma 7. Let (x1,V1),.... (xr. yr) be arbitrary sequence of examples, where x, E R. and Yt R for all t. Let & for /w, Vel and & in Equation 3 otherwise. Let
17

---

W S R. be the feasible set of the weight vector and u be an arbitrary vector in W. Define & = (we; (x), and e (u (x,, 9c)). The following bound holds for any R
Σ & (2l, E. 11,12 207)
||
(19)
Proof. The proof is mainly based on (Crammer et al. facilitate the analysis of the regret bound, we rewrite the recursive updating rule of W++1 PA
2006 Lemma 6) with minor modification. To
W W. + sign [yt w/ x EX
where 0 for w gel I and & т in Equation (3) otherwise. By projecting the feasible set W, we have the weight generated by PA with lazy projection as the following:
Wr+1 1w (ww(++)) arg min ||w w2+1ll2.
weW
Without loss of generality, we set W = 0 and define
A |w, u
We+1 ul/2
Summing from T, we have
P
4
u11
|/211 u112)
t=1
|[1
||W+11
u1/
|W
u
[1
since |Ill (w1) - u113 S [ - u u
|
Ssince W 0
Let Á, ||:
11
W
ull.. we have
A W. -ul2 || - u1/ A..
Using the recursive updating rule Wi+1 in PA, we rewrite Å as
Å ||w: ul/ 2 || + sign [y+ w. xx] εip, u//
||ign [/:- w/ x:] f1x, 1/ - 2(w, u) sign [yt w/ xx] Eex:
- <l xxxxx 112 - 2 sign [v:- -w. w..x]] & (w,xx: - -uxx;)
- - 2 sign y1 w|xx/ xx] & (w.x, - y1 + St- _'xz))
<? 1x1l2 - sign
[ye w| [x] &e (w]xx - ve) + 2 sign [yv- w/ X2 &e (u xt - y1)
- 112 + 26. w/ x1 vel + 2 sign [ve- - w.xi] & (u (u'x,- - -y1)
- < x 112 + (4, + (E, +E)
E. (26, & x 2(²)
Therefore, we have
T
Σ & (2l, - 111101111 28;) A
S >
A A.S
Σ
1=1
1=1
1=1
E Robust Analysis on Performance of APAS on Heavy-tailed Data
To demonstrate the performance of APAS in the presence of high volatility and noisy data, we conducted simulations following the same procedure in our synthetic data experiments outlined in Section 4.1
18

---

In Section 4.1
we considered Gaussian noise w (0, 62) and data r, M E). However, heavy-tailed distributions are generally considered more realistic models of data-genent data-generating processes in financial markets than Gaussian distributions (Cardoso et al. 2021, 2022). To evaluate the performance of APAS with highly volatile and noisy data, we generate heavy-tailed noise and data r, based on the Student's t-distribution, using the same mean and variance settings. The degree of freedom for the Student's t-distribution set to 3, representing significant heavy tails.
side information
Table 2 shows the tracking error of APAS with different combinations noise and data distributions. Specifically, the column "N noise + t data" means the noise w is generated by Gaussian distribution and the side information data r, is generated by Student's t-distribution. general. the difference in tracking enror is small, indicating the robust performance of APAS in highly volatile data scenarios.
N noise + . data
N noise f data
noise N data
t noise + f data
À 10-2
0.000157
0.000159
0.000164
0.000174
À = 5 x 10-2
0.000198
0,000206
0.000198
0.000204
10
0.000261
0.000271
0.000259
0.000261
À x 10
0.000354
0.000369
0.000353
0.000346
Table 2: Tracking error of APAS under different combinations noise and data distributions.
Table compares the excess cumulative return under different combinations of noise and data distri- butions. For heavy-tailed noise (i.e., !-distribution noise), there mild performance degradation. Interestingly. for heavy-tailed data, there is a modest improvement, illustrating the robustness of APAS. This mainly due to the increased chances of outliers in positive side performance for heavy-tailed data. These results show that APAS is robust to heavy-tailed data with adaptivity in tilting the weight towards positive side information.
A' noise .V data
N noise data ( noise
. data
( noise data
À = 1 10
0.000157
0.000159
0.0001 64
0.000174
10
0.000198
0.000206
0.000198
0.000204
A = 1 x 10
0.000261
0.000271
0.000259
0.000261
A 2 10
0.000354
0.000369
0.000353
0.000346
Table 3: Excess cumulative return of APAS under different combinations of noise and data distribu- tions.
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims in the abstract and introduction accurately reflect our paper's contribution and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the assumptions and scope for this paper in Section 3
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
20

---

The assumptions and a complete proof have been provided in Section 3 and Appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The code, data, and instructions to reproduce the experiments are available in the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
21

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes],
The code, data, and instructions to reproduce the experiments are available in the supplemental material.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https://nig)) cc/
pub /ttpc///ges////ceeeceeeccc Cww.edeee//ooeeuummmm ss wnssonnoooo Peeioonolllie ollyy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips. cc/ wtwppp/ppppccccccccccccccccccclp i c/ des CodeSubmi ss i onPol icy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental setting and details have been specified in Section 4
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
The details for the error bars have been specified in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
22

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experiments are conducted on a PC equipped with 13th Gen Intel(R) Core(TM) 17-13700 CPU and 16GB of memory.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httt:p/s//berrrrss....////bl///p
Answer: [Yes]
Justification: Ethics.
The research conducted in this paper conforms fully with the NeurIPS Code of
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The societal impacts have been discussed in the Abstract and Introduction.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
23

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The licenses for existing assets are mentioned in Section
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use package should be provided. For popular datasets, baapeettspppersssee paperswws thoode. com datasstt has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
24

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer:[NA) [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "hObAe4XpOG", "reviewer": "Reviewer_JuTC", "summary": "This paper focuses on the online regression problems for handling large-scale streaming data. Passive-Aggressive (PA) method is a well established method for online regression but existing work struggles with determining optimal thresholds and adapting to complex scenarios with side information. To solve this issue, this paper proposes a novel adaptive framework that allows finer adjustments to the weight vector in PA using side information. Theoretical and empirical studies are shown the validate the effectiveness of this novel adaptive framework.", "questions": "1. Since $\\lambda$ is the trade-off parameter that quantifies the preference between tracking accuracy and side performance and it is one of the inputs of Algorithms 1 and 2, choice of $\\lambda$ is very important. How should we choose $\\lambda$ in a principled way?\n2. What are $D, G$ in Assumptions 1 and 2? Are they constants or parameters? If they are parameters, do they appear in upper bound in Theorem 2?\n3. Again in Theorem 2, the upper bound only shows the dependence on $T$, which is too rough. A full upper bound is highly suggested, at least listing all important parameters.\n4. In Proposition 1, \"... converges in a finite number of iterations\" is too rough. How large is the number of iterations?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. Online regression is an important problem in machine learning because it doesn't rely on strong assumptions and its models demonstrate robustness with regret guarantees in challenging scenarios in practice.\n2. Regret bound is shown to prove that the novel adaptive framework is able to converge to the optimal setting at the order of $O(T)$. Assumptions 1 and 2 are mild.\n3. An efficient algorithm is carefully designed in Section 3.3 to make proposed method actually work in practice.\n4. Both synthetic and real-world experiments are conducted to show the effectiveness of proposed framework.", "weaknesses": "Clarity remains the biggest weakness of this paper. See my questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your insightful feedback and the time you took to review our paper. We appreciate your recognition of the sound theoretical framework and the empirical validation of our method. Below, we address your comments and questions in detail.\n\n> 1. Since $\\lambda$ is the trade-off parameter that quantifies the preference between tracking accuracy and side performance and it is one of the inputs of Algorithms 1 and 2, choice of $\\lambda$ is very important. How should we choose  in a principled way?\n\n**Reply:** Thank you for your valuable feedback. The trade-off parameter $\\lambda$ is indeed crucial for balancing tracking accuracy and side performance, as illustrated in Figure 2a. In principle, $\\lambda$ can be chosen based on theoretical considerations of the problem at hand, such as the expected scale of side information and the desired trade-off between error minimization and performance related to side information. Specifically, $\\lambda$ can be chosen based on domain knowledge and through cross-validation. For example, if we have a desired range of tracking error, we can use the bisection method during cross-validation to find the $\\lambda$ that achieves the required tracking error with the best side performance. We will include a detailed discussion on the choice of $\\lambda$ in the revised paper.\n\n> 2. What are $D, G$ in Assumptions 1 and 2? Are they constants or parameters? If they are parameters, do they appear in upper bound in Theorem 2?\n\n**Reply:** $D$ and $G$ in Assumptions 1 and 2 are constants that depend on the problem setting, such as the data distribution and feature space characteristics. Specifically, $D$ represents the upper bound of the threshold parameter $\\varepsilon$, and $G$ represents the upper bound of $|\\partial f_t(\\varepsilon)|$ for all $t$ and $\\varepsilon$. These constants are crucial for bounding the regret in Theorem 2, as detailed in Line 400 of Appendix A.\n\n> 3. Again in Theorem 2, the upper bound only shows the dependence on $T$, which is too rough. A full upper bound is highly suggested, at least listing all important parameters.\n\n**Reply:** Thank you for your suggestions. The detailed upper bound for the regret in Theorem 2 can be found in line 400 of Appendix A, which is illustrated below:\n$$\nR_T \n    \\leq \\frac{D^2}{\\eta_T} + \\frac{G^2}{2}\\sum_{t=1}^{T} \\eta_t \n    \\leq 2\\sqrt{\\frac{D^3G}{\\nu}}\\sqrt{T} = O(\\sqrt{T}).\n$$\nIn the revision, we will include this detailed upper bound in the main body of the paper.\n\n> 4. In Proposition 1, \"... converges in a finite number of iterations\" is too rough. How large is the number of iterations?\n\n**Reply:** The statement of finite number of iterations for describing convergence is widely used in optimization literature (Facchinei and Pang, 2003; Scutari et al., 2013). This general description is meant to indicate that an optimization algorithm will reach convergence after a certain number of steps.\n\nThe empirical performance of our proposed algorithm's convergence speed is illustrated in Figure 6 of Section 4.3. The left panel shows that our proposed efficient algorithm achieves an approximate gap of $1 \\times 10^{-7}$ relative to the optimal value within just 4 or 5 iterations. The convergence speed of our proposed algorithm is closely related to the problem dimension. The right panel of Figure 6 illustrates the average CPU time across different problem dimensions, showing that the computational time increases a bit with the problem dimensions. \n\nWe will include a more detailed discussion on the number of iterations required for convergence in the revised paper to provide clearer insights into the performance of our algorithm. \n\nFacchinei, F. and Pang, J.-S. Finite-dimensional variational inequalities and complementarity problems. Springer, 2003.\n\nScutari, G., Facchinei, F., Song, P., Palomar, D. P., and Pang, J.-S. Decomposition by partial linearization: Parallel optimization of multi-agent systems. IEEE Transactions on Signal Processing, 62(3):641–656, 2013.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dsEE8olkQ5", "reviewer": "Reviewer_sZCN", "summary": "The paper presents a novel Adaptive Passive-Aggressive online regression framework with Side Information (APAS) framework that addresses the challenges faced by the traditional Passive-Aggressive (PA) method, such as selecting optimal thresholds and adapting to complex scenarios with additional metrics. The APAS framework integrates side information to enhance weight selection and evaluation, adaptively choosing the threshold parameter to ensure convergence to the optimal setting. The paper also introduces an efficient implementation using the Successive Convex Approximation (SCA) technique, significantly reducing computational complexity. Numerical experiments demonstrate the model’s superior performance in achieving low tracking error and high returns compared to traditional PA methods.", "questions": "1. Could you provide more insights into the choice of the trade-off lambda and its impact on the performance of the APAS?\n2. How does the APAS framework perform in scenarios with highly volatile or noisy side information? Will there be any performance degradation?\n3. Besides financial index tracking, is there any other domain where the integration of side information is also beneficial?", "limitations": "The authors have adequately addressed the limitations of their work, particularly in the context of the assumptions and scope of the theoretical analysis.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The integration of side information into the PA framework and the adaptive threshold selection address important limitations of existing methods.\n2. Both the theoretical analysis and experimental validation demonstrate the effectiveness and robustness of APAS.\n3. The paper is well-written and structured.\n4. APAS may have potential applications in different domains, such as financial index tracking.", "weaknesses": "1. Some mathematical derivations and theoretical explanations could be complemented with some high-level, more intuitive explanation to help understand. \n2. The discussion of the implications of the results and the comparison with related work could be expanded to provide a clearer understanding of the contributions and their significance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and insightful feedback on our paper. We appreciate your positive comments and the constructive suggestions you provided. Below, we address your comments and questions in detail.\n\n### Response to Weaknesses:\n\n> 1. Some mathematical derivations and theoretical explanations could be complemented with some high-level, more intuitive explanation to help understand.\n\n**Reply:** Thank you for your insightful suggestions. To enhance comprehension, we will include more explanations in the revised paper. For example, we will highlight our motivation for designing the weight selection and evaluation to balance tracking accuracy and side performance. Additionally, we will elucidate the practical meaning of the regret bound, demonstrating the convergence performance relative to the oracle for the optimal trade-off.\n\n> 2. The discussion of the implications of the results and the comparison with related work could be expanded to provide a clearer understanding of the contributions and their significance.\n\n**Reply:** We will expand the discussion on how our results compare with existing methods, highlighting the unique advantages and limitations of APAS. For example, compared to the traditional PA method, APAS achieves a superior trade-off between tracking error and side performance. Additionally, we will discuss the broader implications of our results and their potential applications.\n\n### Response to Questions:\n\n> 1. Could you provide more insights into the choice of the trade-off lambda and its impact on the performance of the APAS?\n\n**Reply:**  The trade-off parameter $\\lambda$ quantifies the preference between tracking accuracy and side performance, which is crucial for balancing this trade-off, as illustrated in Figure 2a. In principle, $\\lambda$ can be chosen based on the expected scale of side information and the desired balance between error minimization and side performance through cross-validation. For example, if we have a desired range of tracking error, we can use the bisection method during cross-validation to find the $\\lambda$ that achieves the required tracking error with the best side performance. In the revised paper, we will provide more detailed guidance on choosing $\\lambda$.\n\n> 2. How does the APAS framework perform in scenarios with highly volatile or noisy side information? Will there be any performance degradation?\n\n**Reply:** Thank you for your insightful comment. To illustrate the performance of APAS in high volatility and noisy data, we conducted simulations following the same steps as in our synthetic data experiments in Section 4.1.\n\nPreviously, we considered Gaussian noise $\\omega\\sim\\mathcal{N}(0, \\delta^2)$ and Gaussian-distributed side information data $\\mathbf{r}_t\\sim\\mathcal{N}(\\boldsymbol{\\mu},\\boldsymbol{\\Sigma})$. To evaluate the performance of APAS with highly volatile and noisy data, we generate heavy-tailed noise $\\omega$ and data $\\mathbf{r}_t$ based on the Student's t-distribution, using the same mean and variance settings. The degree of freedom for the Student's t-distribution is set to 3, representing significant heavy tails.\n\nThe following table shows **the tracking error** of APAS with different combinations of noise and data distributions. Specifically, the column \"Gaussian noise + t-distribution data\" means the noise $\\omega$ is generated by Gaussian distribution and the side information data $\\mathbf{r}_t$ is generated by Student's t-distribution. In general, the difference in tracking error is small, indicating the robust performance of APAS in highly volatile data scenarios.\n\n||Gaussian noise + Gaussian data|Gaussian noise + t-distribution data|t-distribution noise + Gaussian data|t-distribution noise + t-distribution data|\n|-|:-:|:-:|:-:|:-:|\n|$\\lambda=1\\times10^{-2}$|0.000157|0.000159|0.000164|0.000174|\n|$\\lambda=5\\times10^{-2}$|0.000198|0.000206|0.000198|0.000204|\n|$\\lambda=1\\times10^{-1}$|0.000261|0.000271|0.000259|0.000261|\n|$\\lambda=2\\times10^{-1}$|0.000354|0.000369|0.000353|0.000346|\n\nThe following table compares the **excess cumulative return** under different combinations of noise and data distributions. For heavy-tailed noise (i.e., t-distribution noise), there is a mild performance degradation. Interestingly, for heavy-tailed data, there is a modest improvement, illustrating the robustness of APAS. This is mainly due to the increased chances of outliers in positive side performance for heavy-tailed data. These results show that APAS is robust to heavy-tailed data with adaptivity in tilting the weight towards positive side information.\n\n||Gaussian noise + Gaussian data|Gaussian noise + t-distribution data|t-distribution noise + Gaussian data|t-distribution noise + t-distribution data|\n|-|:-:|:-:|:-:|:-:|\n|$\\lambda=1\\times10^{-2}$|0.0240|0.0272|0.0240|0.0238|\n|$\\lambda=5\\times10^{-2}$|0.0416|0.0458|0.0382|0.0407|\n|$\\lambda=1\\times10^{-1}$|0.0537|0.0613|0.0487|0.0525|\n|$\\lambda=2\\times10^{-1}$|0.0619|0.0754|0.0560|0.0585|\n\nWe will include these experiments and analyses in the revised paper to demonstrate how APAS handles scenarios with high volatility data.\n\n> 3. Besides financial index tracking, is there any other domain where the integration of side information is also beneficial?\n\n**Reply:** The integration of side information can be beneficial in various domains. For instance, consider a broader setting where side information functions are used to manage total switching costs when updating the weight vector. In this scenario, we can set the side information as $h_t(\\mathbf{w}) =||\\mathbf{w}-\\mathbf{w}_t||_1$, which represents the cost associated with changes in the weight vector. Other potential applications include recommendation systems, healthcare, and supply chain optimization, where contextual data can be applied to improve relevant performance. We will include a discussion of potential applications in the revised paper, illustrating the broader applicability of the APAS framework.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WsWywsn8ya", "reviewer": "Reviewer_77Tr", "summary": "This paper proposes a novel adaptive version of the passive-aggressive (PA) method for online linear regression such that it incorporates additional side information within its optimization objective while adaptively updating the threshold above which the weight parameter in the regressor is updated. This method allows the incorporation of additional side information in the optimization objective while performing online regression without degrading the tracking error. The paper also proposes an efficient version of this algorithm based on successive convex approximation (Scutari et al 2013). Additionally, regret bounds are also provided for non-convex loss functions. The work is supported by real and simulated experiments that track a stock index using market data while also enhancing monetary returns.", "questions": "Are the experiments corresponding to Fig 2, 3 and 4 conducted using the efficient version of the algorithm (i.e. Algorithm 2)?", "limitations": "The paper would benefit from an explicit section on limitations, discussing the assumptions and avenues for improvement. Discussion on potential negative societal impact may be necessary as well (e.g. design of side information functions that have societal implications depending on the downstream application).", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper explores an interesting modification of the passive-aggressive (PA) framework where it is possible to incorporate additional side information within its objective while maintaining the original tracking accuracy. The problem formulation and the solution is intuitive. The experimental results suggest that the proposed method strikes a reasonable tradeoff between tracking accuracy and optimizing for an additional goal of enhancing monetary returns from stocks. In general, the original PA method provides better tracking accuracy, but the modified version in the paper provides comparable but slightly worse accuracy while significantly enhancing the monetary returns as compared to all the baselines.", "weaknesses": "It would be interesting to have some experiments with different kinds of additional side information incorporated into the objective and to evaluate whether the time complexity is affected by it. \n\nAlso, it would be interesting to track the adaptively selected \\epsilon parameter and its relationship with tracking error. \n\nThe above experiments may provide us some more insights into the novel PA method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and constructive review of our paper. We are pleased that you found our novel adaptive version of the passive-aggressive (PA) method for online linear regression to be an interesting and significant contribution, particularly in its ability to incorporate additional side information without degrading tracking error. Below, we address your comments and questions in detail.\n\n### Response to Weaknesses:\n\n> It would be interesting to have some experiments with different kinds of additional side information incorporated into the objective and to evaluate whether the time complexity is affected by it.\n\n**Reply:** Thank you for your insightful suggestion. To evaluate whether the time complexity is affected by the inclusion of different types of side information, we conduct additional experiments utilizing various forms of side information beyond the log return $h_t(\\mathbf{w}) = -\\log(1+\\mathbf{r}_t^{\\mathsf{T}}\\mathbf{w})$, such as:\n\n+ **switching cost:** $h_t(\\mathbf{w}) = ||\\mathbf{w} - \\mathbf{w}_t||_1$\n+ **weighted $\\ell_1$ norm**: $h_t(\\mathbf{w}) = \\sum_{i=1}^N \\rho_i |w_i|$\n+ **group Lasso:** $h_t(\\mathbf{w}) = \\sum_{i=1}^{m}\\rho_{i}||w_{|\\mathcal{G}_i}||_2$, where $\\mathcal{G}_i, \\dots, \\mathcal{G}_m$ are $m$ disjoint groups\n\nWe evaluate the performance of the proposed efficient method with different kinds of side information functions over $100$ randomized trials, comparing the average CPU time (in seconds) in the following table:\n\n|          | log return            | switching cost        | weighted $\\ell_1$ norm | group Lasso           |\n| -------- | --------------------- | --------------------- | ---------------------- | --------------------- |\n| $N=500$  | $0.00084$ | $0.00084$ | $0.00045 $   | $0.00162$ |\n| $N=1000$ | $0.00119$ | $0.00084$ | $0.00084$   | $0.00252$ |\n| $N=2000$ | $0.00181$ | $0.00156$ | $0.00113$   | $0.00344$ |\n| $N=5000$ | $0.00335$ | $0.00356$ | $0.00282$  | $0.00702$ |\n\nFrom the above table, we can see the group Lasso incurs higher CPU times, especially for larger dimensions. This increase is due to the complexity of calculating the norm for disjoint groups, which is computationally more intensive. In general, while the type of side information can impact the computational time, the APAS framework maintains efficiency across different scenarios.\n\nWe will include these results and analysis in the revised paper to demonstrate the versatility and efficiency of our APAS framework.\n\n> Also, it would be interesting to track the adaptively selected $\\varepsilon$ parameter and its relationship with tracking error.\n\n**Reply:** In Figure 2b, we have included a comparison between the adaptively selected $\\varepsilon$ by APAS and a fixed $\\varepsilon$ used in PAS (which is essentially APAS with fixed $\\varepsilon$ setting). For PAS with a fixed $\\varepsilon$ setting, both the smallest $\\varepsilon$ and the largest $\\varepsilon$ fail to achieve the best tracking error, likely due to overemphasis or underestimation of real-time tracking error, thus compromising long-term tracking accuracy. This indicates the critical problem in finding the optimal parameter setting to achieve the best trade-off performance. Conversely, under the same excess cumulative return, the adaptively selected $\\varepsilon$ in APAS achieves nearly the best tracking accuracy in most cases. This indicates that APAS effectively balances tracking accuracy and side performance, achieving an optimal trade-off. We will provide a more detailed analysis of the relationship between the adaptively selected $\\varepsilon$ and the tracking error in the revised paper. \n\n### Response to Questions:\n\n> Are the experiments corresponding to Fig 2, 3 and 4 conducted using the efficient version of the algorithm (i.e. Algorithm 2)?\n\n**Reply:** Yes, the experiments corresponding to Figures 2, 3, and 4 are conducted using the efficient version of the algorithm (i.e., Algorithm 2). We will clarify this in the revised manuscript to ensure that this is explicitly stated.\n\n### Response to Limitations:\n\n> The paper would benefit from an explicit section on limitations, discussing the assumptions and avenues for improvement. Discussion on potential negative societal impact may be necessary as well (e.g. design of side information functions that have societal implications depending on the downstream application).\n\n**Reply:** Thank you for your insightful comment. In the revised manuscript, we will add a dedicated section on limitations. We will highlight scenarios where the performance of APAS may be suboptimal, such as in environments with extremely high volatility and skewed data, or when side information is unreliable. Additionally, we will discuss avenues for improvement, including potential enhancements to adaptive selection and robustness to different types of side information.\n\nMoreover, we will include a discussion on the potential negative societal implications of our work. For example, in financial applications, the use of certain side information might inadvertently favor specific market behaviors.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yZHwCUYYge", "reviewer": "Reviewer_WzCc", "summary": "The paper introduces a new method called passive-aggressive (PA) online linear regression with side-information regularization to solve the problem of stock prediction and allocation. The paper introduces PA-online regression as a variant to traditional online linear regression in two ways: 1. the parameter updates only happen when the prediction error exceeds an adaptive threshold - traditional online regression performs the update in every round - and 2. the parameters are projected back to side information - traditional online regression projection is towards an all-zero vector to minimize long-term regrets. The paper then applies the algorithm in a stock prediction problem, where the objective is to mimic an stock index without knowing the portfolio allocation ahead of time and the side information is the return of every stock symbol.\n\nIt is unclear to me how the proposed algorithm maps to the real problem or the exact guarantees the authors claimed, due to the authors use of unconventional notations and unclear description of the noise-generation assumptions.", "questions": "I have troubles understanding the problem setup or the motivations of the threshold-update techniques. I neither understand the definition of the objective function in the regret guarantees. I feel the paper has a point, but I am confused by the flow of the presentation.\n\nEdit: The author responses alluded to some unique properties about passive aggressive algorithm (mostly computational) that need to be discussed before the introduction of the algorithm. Alternative solutions should also be explored. I raised my score by 1 and lowered my confidence as a reflection of the authors' detailed answers.", "limitations": "No. The paper did not discuss the motivations of the proposed algorithm, let alone its limitations.", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper develops upon a rich body of literature on online regression algorithms. The authors utilized existing techniques in optimization literature, such as online proximal-gradient descent and successive convex acceleration (which is similar to batch gradient descent with line search). The introduced algorithm is validated in simulated and semi-real-world stock prediction and index tracking problems.", "weaknesses": "The algorithm is not very well motivated. For example, I am not sure why the authors elected to use PA-online regression with an adaptive threshold instead of regular online regression. The introduction of side-information regularization is abrupt and does not serve the purpose to minimize online regret that is commonly expected of online learning algorithms. The claim of regret guarantee is presented without defining an objective function.\n\nThe paper uses inconvenient notations for the general audience. For example, in the regression problems, the authors used cap{r} as the covariate variable and lower{r} as the outcome variable. They should use cap{x} and lower{y} instead.\n\nThe authors did not explain the noise-generating model, leading to confusions in the general understanding of the problem setup. On Line 207, the authors suggest r_{t,i} as the observed stock return and r_t^b as the index return at time t. In this case, I would assume that the error is generated from not knowing the weight parameter w. But, on Line 222, the authors then suggested that the true index return contains a Gaussian noise even if the actual weight of the index components is known. This confuses me.\n\nLastly, all of the explanations should happen at the beginning of the paper, instead of the experiment section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed feedback on our paper. We appreciate your careful review and the constructive comments you provided. Below, we address your comments and questions in detail.\n\n### Response to Weaknesses:\n\n> The algorithm is not very well motivated. For example, I am not sure why the authors elected to use PA-online regression with an adaptive threshold instead of regular online regression. \n\n**Reply:** Thank you for your comment. We would like to clarify that the PA method, as introduced by Crammer et al. (2006), is one of the most popular approaches for online regression due to its simplicity and efficiency. One of the key features of PA is its ability to provide a closed-form solution for the weight update in unconstrained problems, as shown in Equation (2).\n\nHowever, traditional PA methods face challenges in determining the optimal threshold parameter $\\varepsilon$ and adapting to scenarios where additional side information is available. The threshold $\\varepsilon$ is crucial since it determines when the weight vector is updated. Additionally, relying solely on tracking accuracy without considering side information may limit the method's potential performance. Our proposed adaptive framework enhances PA by integrating side information and adaptively updating the threshold to address the issues.\n\n> ... The introduction of side-information regularization is abrupt and does not serve the purpose to minimize online regret that is commonly expected of online learning algorithms. The claim of regret guarantee is presented without defining an objective function.\n\n**Reply:** We acknowledge that our primary goal for introducing side information is not solely to minimize the tracking error of online regression. Instead, we aim to enhance other potential performance aspects of the model. For example, in regression models, introducing sparsity might increase the error, but it can improve the model's robustness and performance in other areas. The purposes of introducing side information are twofold:\n1. **Potential Performance Enhancement:** By leveraging side information, we can enhance various aspects of model performance, such as robustness and adaptability. This is particularly important in practical applications where different performance metrics need to be balanced.\n2. **Assisting in the Selection of $\\varepsilon$:** Side information can facilitate adaptively selecting the optimal threshold parameter $\\varepsilon$. This adaptive selection process is crucial for achieving a balance between tracking accuracy and other performance metrics, thereby improving the overall effectiveness of the algorithm.\n\nOur objective is to achieve the optimal trade-off between tracking accuracy and side performance. The objective loss function for the regret bound in Theorem 2 is\n$$\nf_t(\\varepsilon) =\\underset{\\mathbf{w}\\in\\mathcal{W}}{\\inf}\\left[h_t(\\mathbf{w})+\\frac{1}{2\\lambda}||{\\mathbf{w}-\\widehat{\\mathbf{w}}_{t+1}(\\varepsilon)}||_2^2 \\right],\n$$\nwhich is explicitly defined in Equation (6). The regret bound in Theorem 2 shows that our designed adaptive method for selecting $\\varepsilon$ converges to the optimal setting in hindsight, thereby achieving the optimal trade-off. We also verify this numerically in Figure 2 of Section 4.1. We will highlight our motivation for introducing side information and the objective loss function in the revised paper.\n\n> The paper uses inconvenient notations for the general audience. For example, in the regression problems, the authors used cap{r} as the covariate variable and lower{r} as the outcome variable. They should use cap{x} and lower{y} instead.\n\n**Reply:** Thank you for your valuable feedback. We will improve the organization of the paper by moving the details of the synthetic data generation model, including noise generation and other relevant aspects, to the Preliminary section.\n\n> The authors did not explain the noise-generating model, leading to confusions in the general understanding of the problem setup... I would assume that the error is generated from not knowing the weight parameter w. But, on Line 222, the authors then suggested that the true index return contains a Gaussian noise even if the actual weight of the index components is known. This confuses me.\n\n**Reply:** It's common in regression modeling to assume the oracle of the regression problem and then generate synthetic observations and labels with a certain level of noise (Sen and Srivastava, 2012; Wang et al., 2018). Different levels of noise can be applied to assess model performance, with Gaussian noise being the most commonly used to represent uncertainty and randomness in data. To address the concerns raised, we will provide a more detailed explanation of the noise-generating model in the revised paper.\n\nSen, A. and Srivastava, M. Regression analysis: theory, methods, and applications. Springer Science & Business Media, 2012.\n\nWang, S., Gittens, A., and Mahoney, M. W. Sketched ridge regression: Optimization perspective, statistical perspective, and model averaging. Journal of Machine Learning Research, 18(218):1–50, 2018.\n\n> Lastly, all of the explanations should happen at the beginning of the paper, instead of the experiment section.\n\n**Reply:** We will provide more details of the synthetic data generation model, including noise generation and other relevant aspects, in the Preliminary section. \n\n> I have troubles understanding the problem setup or the motivations of the threshold-update techniques. I neither understand the definition of the objective function in the regret guarantees. I feel the paper has a point, but I am confused by the flow of the presentation.\n\n**Reply:** We appreciate your feedback. We will highlight the problem setup and motivations in the revised paper based on previous discussions. We hope we can address your concerns and enhance the overall clarity and impact of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces an adaptive Passive-Aggressive (PA) framework for online regression, leveraging side information to improve threshold selection and ensure low tracking error. The proposed framework integrates side information into the weight adjustment process and adaptively updates the threshold parameter to optimize performance. 

The approach is grounded in solid theoretical analysis and is validated through both synthetic and real-world experiments (particularly in financial index tracking). Reviewers appreciate the method's potential for improving online regression tasks, particularly its adaptability and integration of side information.

Several reviewers highlight concerns regarding the clarity of the paper, specifically in its theoretical analysis and motivation for the approach. Additionally, the use of unconventional notations and the lack of a thorough discussion on the method’s limitations are noted as weaknesses. The authors are encouraged to address these concerns in the revision to enhance clarity and provide a more comprehensive evaluation.
Decision: Accept (poster)