Learning No-Regret Sparse Generalized Linear Models with Varying Observation(s)
Authors: Diyang Li
Charles Ling
zhiqiang xu
Huan Xiong
Bin Gu
Venue: ICLR 2024 spotlight (2024)
Keywords: Generalized Linear Models
Learning with Varying Data
Differential Equations
Primary area: general machine learning (i.e., none of the above)

Abstract: Generalized Linear Models (GLMs) encompass a wide array of regression and classification models, where prediction is a function of a linear combination of the input variables. Often in real-world scenarios, a number of observations would be added into or removed from the existing training dataset, necessitating the development of learning systems that can efficiently train optimal models with varying observations in an online (sequential) manner instead of retraining from scratch. Despite the significance of data-varying scenarios, most existing approaches to sparse GLMs concentrate on offline batch updates, leaving online solutions largely underexplored. In this work, we present the first algorithm without compromising accuracy for GLMs regularized by sparsity-enforcing penalties trained on varying observations. Our methodology is capable of handling the addition and deletion of observations simultaneously, while adaptively updating data-dependent regularization parameters to ensure the best statistical performance. Specifically, we recast sparse GLMs as a bilevel optimization objective upon varying observations and characterize it as an explicit gradient flow in the underlying space for the inner and outer subproblems we are optimizing over, respectively. We further derive a set of rules to ensure a proper transition at regions of non-smoothness, and establish the guarantees of theoretical consistency and finite convergence. Encouraging results are exhibited on real-world benchmarks.

Published as a conference paper at ICLR 2024
LEARNING NO-REGRET SPARSE GENERALIZED LINEAR MODELS WITH VARYING OBSERVATION(S)
Diyang Li', Charles X. Ling", Zhiqiang Xu², Huan Xiong' & Bin Gu
'Corell University
Westernn University
Moohaeed bin Zayed University of Artificial Intelligence
diyang cornell. edu, charles. charles. .iingeuww.ca izhiqiang xu, huan. xiong, bin. gu (mmbuaii ac
ABSTRACT
Generalized Linear Models (GLMs) encompass a wide array of regression and classification models, where prediction a function of a linear combination of the input variables. Often in real-world scenarios, number of observations would be added into or removed from the existing training dataset, necessitating the devel- opment of learning systems that can efficiently train optimal models with varying observations an online (sequential) manner instead of retraining from scratch. Despite the significance of data-varying scenarios, most existing approaches to sparse GL.Ms concentrate on offline batch updates, leaving online solutions largely underexplored. In this work, present the first algorithm without compromising accuracy for GLMs regularized by sparsity-enforcing penalties trained on varying observations. Our methodology is capable of handling the addition and deletion of observations simultaneously, while adaptively updating data-dependent regulariza- tion parameters to ensure the best statistical performance. Specifically, recast sparse GLMs as a bilevel optimization objective upon varying observations and characterize it as explicit gradient flow in the underlying space for the inner and outer subproblems we are optimizing over, respectively. We further derive set of rules ensure proper transition at regions of non-smothhness, and establish the guarantees of theoretical consistency and finite convergence. Encouraging results are exhibited on real-worke benchmarks.
INTRODUCTION
Sparse GLMSs
Generalized Linear Models (GLMs) (Nelder & Wedderbum, 1972
McCullagh &
Nelder 2019 Massias et al.) (020) constitute a comprehensive extension of ordinary least squares,
profoundly impacting the communities of machine learning (Kumar et al. 2015 Emaai et al. 2020
Kulkarni al. 2021), data mining (Zhang al.) (016) and computer vision (Kim al. 2014). These models have been extensively utilized as statistical estimators for diverse regression and classification tasks, wherein the output is postulated adhere to an exponential family distribution whose mean is linear combination of the input variables. Renowned instances of GLMs consist of logistic regression (Wright 1995), Poisson regression (Frome) 1983). Gamma regression (Prentice 1974). and proportional odds model (Bennett) 1983). In the realm of high- digh-siinnsional learning, sparsity- inducing regularizations have emerged as powerful tools with substantial theoretical underpinnings (Tibshirani) 1996. Bach et al. 2011 2012), facilitating the concurrent execution of feature selection and model prediction. By substantially diminishing the quantity of active predictors (variables) involved, sparsity-inducing penalization yiclds interpretable models and expedite computational efficiency during the prediction phase.
Nowadays, vast majority of existing algorithms designed for sparse GLMs have predominantly been trained offline in batch-mode (Fercoq & Richtárik 2015 Karimireddy et al. 2019), which necessitates the availability of all training observations at the onset
GLMs with Varying Observations
"Corresponding author.

---

Published as a conference paper at ICLR 2024
of the learning process. However, such a prerequisite may not always be realistic or applicable, particularly in real-time scenarios or large-scale problems. Indeed, in numerous real-world machine learning applications, e.g., edge or cloud computing (Pathak et al., 2018). dynamic pricing (Levina et al. 2009), and fraud detection (Dhieb et al., 2020), the observations (samples) of input can dynamically change, thereby rendering it computationally impractical to train over the entire dataset multiple times. Contrastingly, the paradigm of data-varying (also referred to as incremental and decremental) algorithms has proven its efficiency and computational feasibility across various contexts (Burkov 2020). These methods enable models to incrementally update their knowledge without necessitating complete re-training with each data alteration (also referred to as one online round), such as the addition or removal of observation(s) from the training set. Consequently, algorithms for varying data have garnered increasing attention from both academic and industrial research communities in recent years (Hoi et al. 2021 Zhou 2022).
State-of-the-art The literature on data-varying algorithms has grown significantly, aiming to achieve comparable accuracy to batch re-training without incurring regret (i.e., the regret is zero, or no-regret). However, these works are specifically tailored certain learning models and are not readily extensible to other loss functions and regularizers in sparse GLM The contributions to this domain encompass online k-NN (Rodriguez et al., 2002), logistic regression (Tsai et al. 2014), (group) Lasso (Garrigues & Ghaoui (Chen & Hero 2012, Li & Gu 2022 Hofleitner et al.) 2013), and a plethora of Support Vector Machines (SVMs) (Laskov et al., 2006 Gu et al. 2014 2015) 2018: Kashei| (02T). It is pertinent to highlight that nearly all of the aforementioned algorithms are exclusively capable of adjusting the model weights (i.e., learnable parameters) and lack the ability to dynamically update predefined hyperparameters like regularization, during successive online rounds.
Technical Challenges In this paper, we aim to present a sophisticated no-regret learning framework for varying observations accompanied by pertinent algorithm, which not only yields identical solutions to batch retraining algorithms but also facilitate model selection by dynamically selecting data-dependent regularization parameter(s) at each round, ensuring the optimal statistical performance of the estimator. From data perspective, the proposed methodology accommodates simultancous addition and deletion of observations while efficiently processing multiple data points in a single execution (i.e., chunk updating). as opposed to many single-point algorithms (e.g., Garrigues & Ghaoui (2008); Gu et al.) (2018); ; Yang et al.. (2000). However, the devising of innovative and high-quality data-varying algorithms remains an arduous task. Firstly, these algorithms often stem from standard learning approach (Tsai et al. 2014),, which may result in exceedingly intricate procedures that are challenging to manage. Secondly, the design of data-varying learning algorithms may diverge considerably depending on the concrete loss functions or regularizers (Hoi et al. 202T]. J. rendering the establishment of a universally applicable framework technically demanding. As result, the creation of an efficient algorithm for sparse GL.Ms with varying observations continues to be a highly sought-after yet formidable task for researchers (Burkov 2020 Luo & Song 2020).
Proposed Method To work around these bottlenecks, we commence by reparameterizing the data- varying learning task, which entails transforming one single online round into a bilevel optimization framework. Within this refined construct, we characterize its dynamics as an explicit gradient flow in the underlying space we are optimizing over. Consequently, the inner problem is proficiently modeled and tackled through the utilization of a system of Partial Differential Equations (PDE), whereas the outer problem capitalizes on an Ordinary Differential Equations (ODE) system for its effective numerical resolution. Recognizing the inherent sparsity property, we leverage set control methodologies that circumvent non-differentiable regions and establish threshold conditions for the active set inclusion. Such an approach facilitates the training of a data-varying SpArse GLMs in an Online manner, namely SAGO algorithm. Our comprehensive empirical evaluations substantiate the superior efficiency and accuracy of S&GO in comparison to prevalent batch re- re-training techniques.
Our Contributions The main contributions brought by this paper are delineated as follows.
We present a sophisticated framework and propose a cutting-edge algorithm for a more general form of sparse GLMs, which offers valuable insights into the dynamics of data- varying paradigm. Under mild assumptions, our analysis demonstrates that SAGO converges to the stationarity point on new set and attains convergence within finite number of steps.
In Appendix C.1 we discuss why existing methods cannot be readily extended to GLMSs and delincate the connections hetween our study and conventional online learning with hounded regret.
2

---

Published as a conference paper at ICLR 2024
(i)
(ii)
(ii)
X
X
X
X
X
Figure 1: Depiction of the alterations in the training set during online rounds. A single black arrow signifies one learning round, while red and blue arrows indicate the (incoming) operations con- ducted on data. The status (i), (ii) represent various model conditions (i.e., trained on different dataset).
Figure 2: Distinct blue di- rectional lines represent varied paths from (i) to (ii). The solutions of 2 at [s, (resp. [s, I) is associated with the sta- tus (i) (resp. (ii)) ) in Fig.
Contrasting with existing frameworks for data-varying sparse GLMs, SAGO enables the incorporation and removal of multiple observations in single execution without sacrificing accuracy, while concurrently updating the regularization parameter(s) in each round.
We clucidate how SAGO paves the way to no-regret online training for multiple well-known GLMs, including Poisson (Frome 1983) and gamma regression (Prentice 1974). To the best of our knowledge, this constitutes the first exact data-varying algorithm for these models.
PRELIMINARIES
Basic Notation For any integer d E N, we denote by [d] the set f1.... d}. The vector of size
with all entries equal to 0 (resp. 1) is denoted by O,, (resp. 1,). The design matrix X E Raxm is composed of observations x E R." stored row-wise; the vector the response vector for regression (resp. binary classification). For a model weights vector 3 and subset A C [m), AA and X are 3 and X restricted to features in A. Subscripts (e.g., 3,) denote vector entries or matrix columns. The standard Euclidean norm for vectors reads || ||: the E -nomm is symbolized by/l ||1. We provide comprehensive compilation of all notations in Appendix
Ih" (resp. {-1,1]") signifies
2.1 FORMALIZED SETTING
Considering each online round, the data is structured (partitioned)
X {(x1, ..... (xno= }no X {[xxo++1 +no+1) (xno Bnotn]]
X [(x,, v1 Vi E [mo n. 1, no n nn]),
where X indicates the set of observations to be retained (i.e., unchanged single online round), X- (resp. X*) represents the set of observations be eliminated (resp. incorporated). Figure illustrates the schematic diagram of the data-varying setup. Let us assume that we presently possess no + n. labelled instances X (X X-} and an optimal machine learning model trained using XO, which the parameter is denoted by 3 E Rm (already known). In certain practical contexts, it may be desirable to incorporate new samples X into X while concurrently discarding selected samples X- from X This implies the requirement for an optimal learning model that trained on X {X" U X+), and the learnable parameter of this optimal model on the new (changed) dataset signified as 300 E Ihm which is currently unknown. essence, the resultant sample size should be ni + (n. n.) following this online update. Methodologies in conventional paradigm would only involve re-training a new model on (X U Xt). However, our proposed approach SAGO seeks to compute (00i) directly, meaning bypasses the need for re-training from the ground up, and instead leverages the information encapsulated within initial (0)
3

---

Published as a conference paper at ICLR 2024
2.2 OFFLINE SPARSE GLMS
To commence, we introduce the class of optimization problems under consideration.
Definition 1 (Sparse GLMs). We call sparse generalized linear models the following problem
(u. +
Σ Σ Pa (183),AA))
min BER
k=1jES
where each (()) represents piecewise (or elementwise) twice-differentiable convex loss and d is
the number of regularizers. We have S (S,,S,...., Sy. where Sk C. [m| denotes the subset of coefficients being penalized (8 for Shrink). P., (10g],)*) is scalar penalty function (regularizer), with n representing potential parameter(s) for penalty family and A IR being non-negative hyperparameter.
We define X = .... Ad]" controlling the trade-off between data fidelity and regularization in (1) To achieve model selection, we typically employ K-fold cross-validation. In its simplest form, cross-
validation involves the use of a second, independent set of data {&, ūe V (commonly referred to as
validation set (Shao [993)). which serves evaluate model performance and select appropriate regularization parameters. Additionally, we impose several mild conditions on P. [1351, Ax.)
Assumption Let P,(p,E) E) be a shorthand notation for Pr (185),2a) We assume Pr E) satisfies the following regularity conditions: (i) symmetric about 0 in p. (i) (0) -00, VE 2 O, and & is separable as a multiplier from (p E). (iii) monotone increasing in & 2 0 for any fixed p. (iv) non non-decreasing in p 2 for any fixed E. (v) the first two derivatives w.Et. p exist and are finite.
Most commonly used penalties satisfy the aforementioned Assumption I including but not limited A E (0. 2] (Frank & Friedman 1993). log penalty P, (18), = > In(1) + (8] 19 > 0 (Armagan et al. 2013), along with the non-convex SCAD
to the power family P, ( [[, Ax))
regularizer (Fan & Li 2001 and MC+ penalty (Zanng 2010), etc.
2.3 FROM OFFLINE TO ONLINE
Given a GLM as described in ①. we present a framework for learning it with varying observations. Definition 2 (Parameterizer). The parameterizers put), v (s) E RM must satisfy the following conditions: (i) The inverse of parameterizers, denoted as μ or or- exists and should be continuous. (ï) The first-order derivative of μ (t) (resp. v (s)) w.r.t. t (resp. s) smooth in the closed interval [t. tl (resp. [s. $ 1)), where t μ (0), f= = reparameterized objective retains its original (onttcoon....ty.
(0) and 3 v (1). (iii The
The parameterizer in Definition _ can be employed to recast the original dara-ng learning, which could be implemented in two manners, i.e., function-wise or observation-wiss Mathe- matically, let denote either 1a (t) v (s), the corresponding reparameterization could take the Es (v. (3 x;) or Es Ye.
form of
3 xx)). For simplicity, denote (²)
Σ (((0))))) (v., f (3Tx:)) x:)). (3) Σ ((((o.))xx)) (v., xx) and similarly, (B). Then we introduce the following class of function-wie reparameterized optimization problem
N
min Loat Σ
l Vc. f (3 xx)))
stt. B arg min RE
e (t) (2())
Σ Σ P. (13),,b)) km1jES
[< 8
The (2) characterizes a bilevel optimization problem, in which the inner-level problem addresses the changes of varying data, while the outer-level problem exploits validation set to determine the regularization parameter(s) each online round. Here, s and t serve as variables within the reparameterization (i.e,, parameterizer incorporating). At the onset of each round, we initialize
OOrr choice of terminology may be considered abuse of language since for some choice of E, 's, e.g., an Huber loss, there is no underlying statistical GL.
4

---

Published as a conference paper at ICLR 2024
and t as & and f. respectively. To deduce optimal solution subsequent to round of online data changes, we could progressively increase and t, while concurrently computing (tracking) the dynamics on B in association with (s, t), until they attain the upper bound of = and f. =
Remark A naive example is y (t) def I, V (8) def 1 8. Then (s. 1) transitions from (0,0) to (1,1).
Intuitively, μ parameterizes increment and parameterizes decrement.
Theorem (Equivalence Guarantee (informal)). Let be a batch algorithm that trains on X and
outputs model f & H. ie., A (X): X - H. The symbol <- signifies online updating as per (2)
Suppose we desire to incorporate X and remove from the existing model. Then VT E H.
P R{(A(X {A(XXXU))
Adding x
Deleting
x
E =
Online
Online
Formal statements and proofs are in Appendix B.1 The underlying intuition of Theorem is that the output of SAGO for (2) is indeed equivalent to the solution that would be obtained if trained from scratch using {Xx UX*], and the regret of solution produced by our SAGO algorithm [s, 6). is provably zero after each online round (a.k.a,, no-regret). This equivalence establishes a bridge that links two disparate model statuses (c.f. Figure By applying the aforementioned procedure, we empowered to train in an online manner when the set of observations is not fixed, further affirming that the first-order optimal solution can be achieved, akin to the capabilities of batch algorithms.
ELABORATED SAGO
In this section, we introduce an innovative approach, employing the PDE and ODE systems, referred to as the PDE-ODE, procedure, trace the trajectory of (s, f (2) or (3, Loal) for short, until we reach the terminal points [3, {l and Amax. Set S. = UP St. For a parameter vector S.
0} to represent the set of penalized parameters that are E S. B, * 0} demarcates the set of penalized parameters with non-zero values. In light of the fact that typically only a fraction of the coefficients are non-zero in the optimal solution, prevalent strategy to speed up solver efficiency is to narrow down the optimization problem's magnitude by excluding features that not contribute to the solution 3. We define the active set A = Sz U.S indexes the current active predictors having either unpenalized or non-zero penalized coefficients, with cardinality ||81o.-
R" we use Sz - [
zero and correspondingly. (2) (3)
Assumption 2. We presuppose that the first- frrst-order optimal solutions of ( and (2 can be accom- plished (via batch algorithms), and the active set A is non-empty for Vt E L. D. Vs E le, 8), AA E A. Theorem (Continuity Guarantee). Assume that there exists positive constant M such that the inequalities V3,3 < M1, 8 3 M1mm 8/3 2 M1m Σ-1 1 3 M1 holds universally for all 3, where C. will be defined in (3). Then provided fixed active set A, the solution 3 demonstrates continuity w.r.l. the variables of the inner problem and the variable(s) of the outer problem, respectively.
3.1 INNER PROBLEM SOLVING
We define = (ye: (S)xx.A)). Theorem aids in tracking the flow to inner-level soluions.
Theorem 3 (Inner-level Dynamics). Suppose | is the solution the inner problem of 2 for given and t, and the collection A is fixed, the dynamics of gradient flow on Ba(s, f) comply with
du(l))
V (3) + (8.2)
08A(s,1)
=0
dt
0t
du(s)
FA + 2 (3.A)
aBa(s,t) Is
ds
+ Vaa (2(0))((0())))))0))))) (3)
(B.2)
Σ
V2A Σ Pn (18)).2e)
==1
JESE,A
3(s -==
1)
303
The 3 represents first-order homogeneous PDE system. By employing our proposed procedure, the resolution of the inner problem transforms into standard form initial-value problem (IVP) (Fatunla
5

---

Published as a conference paper at ICLR 2024
2014) in the context of numerical PDE. The solving to enables tracking of the entire spectrum of solutions for | (s, ((s,t) E [s. s] x |4. J. As our primary interest lies in the specific solutions when s = and f, we can select an integral path [{ss t) = connecting [s, f] and [s, 8). and then perform a line integral along Ω (c.f. Figure 2 to attain ((s, Ł). During the integration, careful management of the set of non-zero coefficients according to the thresholding conditions enables the application of our algorithm within the nower-dimensions subspace spanned solely by active coefficients. We emphasize that 3 is piecewise smooth as a function of and i, i.c., there exists t = tu < t1 < t2 < .... < tkmaz = t and & = $o < $1 < 82 <
Skmax = 3, such that the <
solution 3 (s, t) can be precisely represented via
<[ ds V2,
du(t) Vaa Vea (a() (ds. (ds.de) 1)
(sx-11 - ((8,A)"
(4)
dt
where Vs E [sk-1, 8k], 11 E [[,-1,4]] [x].
The 8n and la essentially represent event points and will be formally introduced in Section 3.3
3.2 OUTER PROBLEM SOLVING
In each round of online phase, Theorem facilitates the approximation to for the outer problem. Theorem (Outer-level Dynamics), Assume that the set fixed. Under varying values the outer problem, the dynamics of grudient flow on Ba(A) in the outer Loot can be expressed as
db dA
(18))
VoA (1( + (2))
Pa (8/
VAA Σ Pa JESN.A
2e)) (S)
JES
In analogy with the inner problem, 33 exhibits piecewise smoothness as a function of A. Consequently.
it is possible to numerically solve the IVP for the first-order ODE system (5). The Picard-
theorem (Siegmund et al. 2016) unequivocally establishes the uniqueness of solutions facilitating
the calculation of Coot (A) A E AJ. given that V V a direct function of / (A), represented
N
d$
VeCeat
Vol, (v.. (3)x))
(6)
dx
where d.//d could be computed via To identify the optimal regularization parameter(s), one can evaluate the condition V V _ O. practical scenarios, an alternate approach examine the as a loose condition (relaxation) to approximately select
hyper-gradient, accepting Coatll the regularization parameter(s), where e E R2 an user-defined parameter.
Theorem 5 (Approximation Error). Assume that the outer-level loss function exhibits k-strong quasi-convexity over the optimal solutions set of the inner-level problem, the difference between the optimal parameter X* and its estimated counterpart X is upper-bounded by 1|. X+1 2ck
3.3 EVENT POINTS
For illustrative purposes, we consider the case of & penalty and let S = [m]. While we focus on a specific case for clarity, the analysis presented in Section B.3 is generalizable to any regularization term satisfying Assumption (c.. Appendix C.2). The thresholding conditions for an E, regularized problem, as put forth by Rosset & Zhu (007), are reproduced follows.
Lemma 1. (c.f. (Rosset& & Zhu 2007 ) For any loss function ((X,)) that differentiable w.r.t. B, any stationary point 3 of the optimization problem
min L(y, ((X,))). s.L. || < D
3
ensures the following properties: (a) 3, + =
AL ag.
max,
aL 0g,
(b) sign (8,) (B.)=
sign
aL 03,
We refer here the uniqueness of the solution
IVP
whereas non-uniqueness for is permissible.

---

Published as a conference paper at ICLR 2024
and suppose the current active Denote a = max;
aL 88,
Trajectory
Integration
set is [A1, k2).
Lemma suggests that a =
aL
03k,
BL
8L In the inner-level (resp. outer-level), 73.
we start at = 8, == (resp. initial )) to compute the trajectory via the PDE-ODE procedure. It can be inferred that the trajectory remains smooth until the occurrence of one of the two possible events: E1: Another variable
E1
index K; (i + 1, 2) joins the active set as
aL
a; E2:
ape;
Figure 3: Demonstration of different cate- gories of events. E1: 3x, enters the trajec- tory, with its new sign being determined as per Lemma (b): E2: 3k, leaves the path, leading to the removal of ką from A and the invalidation Lemma (a).
Any of the Bk, becomes 0 (c.f. Figure 3 The solution 3 related to 8, I and À can be computed swiftly before any alterations occur in A. We term the points where an event occurs as event points, and the smooth trajectory (path) between two event points as a segment. Theorem offerrs insights into the behaviour of path segmentation. At an event point, we reset A according to the index violator(s) and proceed to the subsequent segment.
Theorem (Segmentation End). For (3, A) that satisfies the KKT system of
suppose the active
set is PU {g). but is just eliminated from the active set. Let Cr = max;
OE
i E P. If the Jacobian
01%
8% (e + e*) (P.g)
00 Σ Pa
(18)). (P.9)
Σ
0 Σ
Pv ( .ve)
J
JEDE
JES
(7)
Eo Σ P. JES
(3...2a)) Av {P.g}
0
full rank, then 8 or X cannot be the end point of path segment. Here gg extracts only ai. the entries atl with index i E SP {g) B.1 (P,9} extracts 03,03,' with index i, E EPU {g}-
85,
Remark 2 (Discontinuities). Our extensive empirical studies suggest that when utilizing non-convex penalties, outer-level path discontinuities may arise when predictors enter the model at non-zero magnitude or vice versa. This phenomenon is attributable to the jumping between local minima, wherein we can employ a warm-start strategy to compute the initial value of the ensuing segment.
4 DISCUSSIONS
4.1 SAGO IMPLEMENTATION
The comprehensive SAGO algorithm computes the PDE-ODE procedure a segment-by-segmeet basis, which is delineated in Algorithm [ serves as a promising fitting strategy for online scenarios. At junctures where the events E1 and E2 occur, we halt and update the system, subsequently resuming the trajectory until the traversal of Qi and A is complete.
Remark 3 (Extension on Non-linear Pattern). While we presuppose a linear model in 7.. this assumption is far less restrictive than it appears. Indeed, the model can be linear in basis expansions of the original predictors. thereby enabling Algorithm to encompass kernel methods (Shawe- Taylor
et al. 2004), wavelets (nttoiiaiis al. 1997), boosting techniques (Schapire) 2003) and more.
4.2 COMPLEXITY & CONVERGENCE
Any PDE/ODE solver recurrently evaluates the (partial) derivative in 3 and 5 requiring approxi- mately O ((no + n_ + n2,) |Al) flops to compute the requisite linear systems. When updating V or its inverse, one can use the low-rank updating or Woodbury formulae (Ben-Israel & Greville 2003), with the computational cost capped at O (LA(2). The identification of active and inactive penalized predictor by thresholding demands O ((A)) flops. The detailed computational complexity of the entire SAGO Algorithm is contingent upon the explicit form of the loss, the number of smooth segments (events), and the chosen method (solver) for executing the PDE-ODE procedure. This procedure chiefly leverages numerical library for first-order PDE and ODE, which has undergone extensive investigation within the applied mathematics community (Rhee et al. 2014).
7

---

Published as a conference paper at ICLR 2024
Table 1: Datasets description. The BC denotes Binary Classi- fication and R for Regression.
Average sunning Timkets
120
Coldhyal
Warmtyb
Duiieet
Samples
Din. Task
ColdByO
reclltcanl
MiniBoeNE
384807
180064
WarmByd
SAGO
biggs
98050
BC
mumenulbus
96320
20planes
Size Dalaset
Size of Dataset
ACSlocine
Buszisecialmmlii
583250
Figure 4: Comparative analysis of algorithmic efficiency. The subfig- ures on the left and right are GLMs (i) and (ii), respectively.
ChilbeNewssPoplaaaee
The efficiency of Algorithm T lies in the fact that SACO can trace the opti- mal solutions w.r.t. the variables and parameter(s). Throughout this proce- dure, the solver adaptively selects step sizes to capture all events, thereby elim- inating the need for repeated iterations within each round. This stands in con- trast conventional methods that ne- cessitate numerous loops over all sam-
Algorithm SAGO Algorithm
Require:
Initial solution 8(0), online rounds T, training sets X X X in each round, tolerance c for X, max_itee 1: for r 1,... , do
2: Initialize A 4- --S UZ according to 3(r-1),
3: t.5.6 (
4: while 3, tttsto do
5:
Solve the PDE system if any E A has 8x then
b> Inner-level problem
6:
7:
Exclude from A. E2 occurred
ples or coordinates until ultimate con-
8:
else if (k E Sz) meets thresholding conditions then >> E1 occurred
vergence. The convergence of SAGO ensured by forthcoming Theorem 10:
9:
Add & into A.
end if
Update / and l.,A by the modified A.
and Theorem g and more related dis-
cussions are given in Appendix C.2
12:
end while
13:
iters +0
Theorem 7 (Successive Adjustments).
14:
while Voatlll >
and iters < mmarritee do
On the solving interval, if an index j' is incorporated into the set A, j' will not be removed from A in the immediate next adjustment cycle; if an index j" is expelled from the set A, j" will not be reintroduced into A in the immediate next round of adjustment.
15:
Solve the ODE system (5)
Outer-level prohlem
16:
if any & E A has 8 then
17:
Exclude from A.
E2 occurred.
else 3 S2) meets thresholding conditions then
19:
Add & into A. >> E1 occurred.
20:
end if
21:
Compute VxCeat via 66
Theorem 8 (Finite Convergence).
22:
Update 8(4 and & by the modified A, and warm- start if necessary.
Given the pre-established s, t, and A, the SAGO can fit the problem delin- eated in (2) within a finite number of steps upon Assumption
iters < iters +1
24:
end while
25:
A(T) +- arg min V.
26:
end for
Ensure: {B(T)), (1())
EMPIRICAL STUDY
Sparse GLMs
For evaluation, here we employ two specific GLMs: (i) Sparse Poisson Re-
gression FFome 1983) given by ming
1 n E. log exp(3 x.) (yt-expl exp33 x))] - A ||
A2 2| and (ii) Logistic Group Lasso Meier et al, 2008) (for classification) expressed as ming 1
Σ y4 log (ha(x:)) (1 ys) log (1 - (x(),)) + A > ddy [| wherein (x(xx) (1 e xx))= is hypothesis function. There has total of G groups, d, is the
n
number features in g-th group.
Dataset We employ real-world datasets from OpenML /Vanschoren et al. 2014) and UCI repository (Asuncion & Newman 2007) for our simulations. Table summarizes the dataset information. We randomly partition the datasets into training, validation, and testing sets, with 70%, 15%, and 15% of the total samples, respectively.
Baselines Given the lack exact no-regret algorithms for these models prior to SAGO, we compare against the following baselines: (ii dori (resp. Wa WarmGrid employs cold-start (resp. warm-
8

---

Published as a conference paper at ICLR 2024
Table 2: Numerical results for validation loss with standard deviation. The best results are shown in bold. We employ GLM (i) and GLM (ii) for Regression and Binary Classification tasks, respectively.
creditcard
MiniBooNE
Biggs
mumerai23.6
ACSIncome
Buzinncciltneii
house_168t
Coldgeid
0.017
0:432
0,071
0.012
256.2
12:58
27.91
coldryn
0.0R3 0,009
0.383 0.017
0.027
0.711 0.014
256.0 +
12.58 0.02
53981
27.43
coldayo
0.000 0.016
0::22 0.025
0.006
0.712 0.022
0.50
13.05 0.33
3,008
20.48
SAR2
0.692
0.004
0.380 + 0.000
0.038
0.001
0.001 0.002
265.9 +: 0.09
12.54 + 0.08
9.761 = 0.14
20.25 0.07
Round #2
coldG:1d
0.201
0.077
1.288.11 0.04)
0,632 0.043
0.745
0.043
258.6 0.08
13:11 0.04
3,680 1: 0.41
27.14
1.0.77
ColdFy6:
0.008
0.006
0.250) 002
0.000
0.003
0,756 0.086
256.
0:35
12:68
0.00
5.84 2:
21/62
Co1c2y0
0,708
1.0.00000000 0.014
0,321 1: 0,007
(1651
=: 01,811
0.789 0,008
257.5
1: 0.188
12.70 2: 0.85
3.727 2: 0.74
21.77 1: 1.0.75
$200
0.694
0.008
0.287
1: 0.021
0.638
1: 0.006
0.737 0.006
263.7
0.48
12.53 1: 0.04
3.680 1: 0.24
26.39 0.14
Round 8t
We Recririd
0.715
+-044
0,300 + 6.014
0.632 0.023
0.712 0.087
256.5 0.88
12.56 + 0.49
A.021 + 0.85
27.05 0.1.1
0,705
+ 0.096
0.260 + 0.096
0.646 = 0.026
0.673 + 0.011
265.5 + 0.87
18:06 + 11.66
$.08 + 0.45
26.97 + 0.54
Narnayo SAGO
0:708
0.055
0:307 1: 0.007
0.651 :: 0.000
0.688 0.065
255 1: 0.08
12:94 :: 0.63
3.925 2: 0.76
21:25 1 0.25
0.893 + 0.006
0.260
: 0.005
0.640 0.014
0.008 0.003
255.5 +: 0.12
12.52 +: 0.05
3.079 :: 0.39
20.63 0.04
Inner SAGO 0:.1
Inner SACO (4- 0.30
29.15
Probebbiligg
2000
Rumino
0.00
140 7T. 150 15
6iz Batch Size of Updated Data
212
2035
2200
event points evant points
Event Points
Figure 5: Normalized updating time per data sample (total up- dating time divided by batch size) for the inner-level problem. probbee...
Figure 6: Histograms of event points. The left (or right) panel corresponds to the inner (or outer) problem.
Figure 7: Running time as a function of event point numbers.
start) batch retraining for online updating and utilizes grid search to determine the optimal X. (ii) ColdHyBi (resp. WarmHyBi) applies cold-start (resp. warm-start) batch retraining for online updating and leverages hypergradient-basee bilevel framework (Feng & Simon| 2018) to find X (iii) ColdByO (resp. WarmByO) adopts cold-start (rexp. warm-start) batch retraining for online updating and employs Bayesian optimization (Snock et al. (012) to identify the optimal A. For the grid search, we rely on Scikit-learn (Pedregosa et al. (011). and for Bayesian optimization, we use the Hyperopt library (Bergstra et al. 2015). For batch re-training, we leverage the popular FISTA optimiser (Beck & Teboulle| 2009) integrated with gradient-base bradeent-based adaptive restarting scheme (O O'donoghue& & [andes] 2015).
Setup To rigorously assess the validity of our conclusions and the practical efficacy of our SAGO algorithm, we simulate an online environment with varying observations as detailed in Section 2.1 We use 70% of the training set to train an initial model, in which we assign half of the observations with randomly assigned erroneous labels. In each round, the model is updated by progressively eliminating these incorrectl-labeeled training data and simultaneously introducing the remaining 30% of unutilized clean data. All experiments are conducted over 50 trials and more details are listed in Appendix
SAGatte 1e-1]
Orocie Ostinal
64215
4420
Online Rounds
Figure 8: Dynamics of A.
Results & Analysis At first we perform a single round update (maintaining a constant n4, + n2.) on datasets of varying scales contrast the runtime of diverse algorithms. The results depicted in Figure underscore the computational advantage of proposed SAGO. We present our numerical results in Table suggesting that the accuracy of our algorithm parallels that of existing methodologies. Moreover, we fix the dataset size no and vary the number of dynamically updated samples per round, as illustrated in Figure 5 The running time observed to scale linearly with the growth of n4 + n... which means our method is scalable with the increasing number of varying observations. Figure 6 displays the histograms of event points, revealing a near-absence event points in the inner-level problem, while most of them are present in the outer-layer problem. Subsequently, we forcibly alter the optimality conditions during a certain round, causing a change in the number of event points. Figure [ illustrates that the influence of event point count overall runtime is almost negligible. Lastly, Figure | validates SACO's 's capability to approximate optimal regularization parameter when the samples varying in each online round.

---

Published as a conference paper at ICLR 2024
REFERENCES
Muhammad Amin, Muhammad Amanullah, and Muhammad Aslam. Empirical evaluation of the inverse gaussian regression residuals for the assessment of influential points. Journal of Chemo- metrics, 30(7):394 404, 2016.
Anestis Antoniadis et al. Wavelets in statistics: review. Journal of the Italian Statistical Society, 6 (2):97-130, 1997.
Artin Armagan, David B Dunson, and Jaeyong Lee. Generalized double pareto shrinkage. Statistica Sinica, 23(1):119, 2013.
Arthur Asuncion and David Newman. Uci machine learning repository, 2007.
Francis Bach, Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski, et al. Convex optimization with sparsity- norms. Optimization for Machine Learning. 5:19 53, 2011.
Francis Bach, Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski, et al. Optimization with sparsity-inducinn penalties. Foundations and Trends@ in Machine Learning. 4(1):1-106, 2012.
Amir Beck and Mare Teboulle. fast iterative shrinkage- shrinkage-threshoolee thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-22)))) 202,, 2009.
Adi Ben-Isracl and Thomas NE Greville. Generalized inverses: theory and applications, volume 15.
Springer Science & Business Media, 2003.
Steve Bennett. Analysis of survival data by the proportional odds model. Statistics in medicine, 2(2): 273-277, 1983.
James Bergstra, Brent Komer, Chris Eliasmith, Dan Yamins, and David D Cox. Hyperopt: a python library for model selection and hyperparameter optimization. Computational Science & Discovery, 8(1 8(1):014008, 2015.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette- Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. 2021 IEEE Symposium on Security and Privacy (SP), pp. 141-159. IEEE, 2021.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Andriy Burkov. Machine learning engineering, volume 1. True Positive Incorporated Montreal, QC, Canada, 2020.
Yilun Chen and Alfred O Hero. Recursive i-1,infty group lasso. IEEE transactions on signal processing, 60(8):3978-3987, 2012.
Shui Nee Chow, John Mallet-Paret, and James A Yorke. Finding zeroes maps: homotopy methods that are constructive with probability one. Mathematics of Computation, 32(14)):877-89, 1978.
Marina Danilova, Pavel Dvurechensky, Alexander Gasnikov, Eduard Gorbunov, Sergey Guminov, Dmitry Kamzolov, and Inmokentiy Shibaev. Recent theoretical advances in non-convex optimiza- tion. In High Digensinmms Optimization and Probability: With a View Towards Data Science, pp. 79-163. Springer, 2022.
Najmeddine Dhieb, Hakim Ghazzai. Hichem Besbes, and Yehia Massoud. A secure ai-driven architecture for automated insurance systems: Fraud detection and risk mcasurement. IEEE Access, 8:58546-58558 2020.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Melikasadat Emami. Mojtaba Aahrace-Ardakan Parthe Pandit, Sundeep Rangan, and Alyson Fletcher. Generalization error generalized linear models in high dimensions. In International Conference Machine Learning, pp. 2892-2901. PMLR, 2020.
10

---

Published as a conference paper at ICLR 2024
Jianqing Fan and Runze Li. Variable selection via nonconeave penalized likelihood and its oracle properties. Journal of the American statistical Association, 96(456): (3455))):338133333 1360,, 2001.
Jianqing Fan, Wenyan Gong, Chris Junchi Li, and Qiang Sun. Statistical sparse online regression: A diffusion approximation perspective. International Conference on Artificial Intelligence and Stalistics, pp. 1017-1026. PMLR, 2018.
Simeon Ola Fatunla. Numerical methods for initial value problems in ordinary differential equations. Academic Press, 2014.
Jean Feng and Noah Simon. Gradient-based regularization parameter selection for problems with nonsmooth penalty functions, Journal of Computational and Graphical Statistics, 27(2))426-435, 2018.
Olivier Fercoq and Peter Richtárik. Accelerated, parallel, and proximal coordinate descent. SIAM Journal on Optimization, 25(4):1977-2023, 2015.
Gerald B Folland. Remainder estimates in taylor's theorem. The American Mathematical Monthly, 97(3):233225 235, 1990.
LLdiko E Frank and Jerome Friedman. A statistical view of some chemometrics regression tools. Technometrics, 35(2):109-133 1993.
Edward L Frome. The analysis of rates using poisson regression models. Biometrics, pp. 665-674, 1983.
Benoît Frénay and Michel Verleysen. Classification in the presence of label noise: A survey. Neural Networks and Learning Systems, IEEE Transactions on, 25:845 869,, 05 2014. doi: 2000/
Pierre Garrigues and Laurent Ghaoui. An homotopy algorithm for the lasso with online observations. Advances in neural information processing systems, 21, 2008
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint (rXiv:1802.02246 2018.
Aritra Ghosh, Himanshu Kumar, and Sastry. Robust loss functions under label noise for deep neural networks. 12 2017.
Göknur Giner and Gordon K Smyth. statmod: probability calculations for the inverse gaussian distribution. arXiv preprint 16X3::66030660 2016.
Bin Gu, Victor S Sheng, Keng Yeow Tay, Walter Romano, and Shuo Li. Incremental support vector learning for ordinal regression. IEEE Transactions on Neural networks and learning systems, 26 (7):1403-1416, 2014.
Bin Gu, Victor S Sheng, Zhijie Wang, Derek Ho, Said Osman, Shuo Li. Incremental learning for y-support vector regression. Neural networks, 67:140-150, 2015.
Bin Gu, Xiao-Tong Yuan, Songcan Chen, and Heng Huang. New incremental learning algorithm for semi-supervised support vector machine. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 1475-1484, 2018
Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi- Malvai-iallajjrrdi, and Chris Waites. Adaptive machine unlearning. Advances in Neural Information Processing Systems, 34:16319- 16330, 2021.
Aude Hofleitner, Tarek Rabbani, Laurent El Ghaoui, and Alexandre Bayen. Online homotopy algorithm for a generalization of the lasso. IEEE Transactions on Automatic Control, 58(12): 3175-3179,2011
Steven CH Hoi, Doyen Sahoo, Jing Lu, and Peilin Zhao. Online learning: comprehensive survey. Neurocomputing, 459:249-289 2021.
11

---

Published as a conference paper at ICLR 2024
Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru, and Bo Li. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. pp. 19-35, 05 2018.
doi: 10.1109/SP2201800000
Sai Praneeth Karimireddy, Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi. Efficient greedy coordinate descent for composite problems. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 2887-2896. PMLR, 2019.
Rasha Kashef. A boosted classifier trained by incremental learning and decremental unlearning approach, Expert Systems with Applications, 167:1 14154, 2021.
Hyunwoo Kim, Nagesh Adluru, Maxwell D Collins, Moo K Chung, Barbara B Bendlin, Sterling C Johnson, Richard J Davidson, and Vikas Singh. Multivariate general linear models (mglm) on riemannian manifolds with applications to statistical analysis of diffusion weighted images. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2705-2712, 2014.
Steven George Krantz and Harold R Parks. The implicit function theorem: history, theory, and applications. Springer Science Business Media, 2002.
Tejas Kulkarni, Joonas Jälkö, Antti Koskela, Samuel Kaski, and Antti Honkela. Differentially private bayesian inference for generalized linear models. In International Conference on Machine Learning, pp. 5838-5849, PMLR, 2021.
Arun Kumar, Jeffrey Naughton, and Jignesh M Patel. Learning generalized linear models over nor- malized data. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 1969-1984 2015.
Pavel Laskov, Christian Gehl, Stefan Krüger, Klaus- Müller, Kristin P Bennett, and Emilio Heerado-Hernádde.. Incremental support vector learning: Analysis, implementation and applica- tions. Journal of machine learning research, 7(9), 2006.
Hoai An Le Thi, Hoai Minh Le, Van Vinh Nguyen, and Tao Pham Dinh. A de programming approach for feature selection in support vector machines learning. Advances in Data Analysis and Classification, 2:259-278, 2008
Tatsiana Levina, Yuri Levin, Jeff McGill, and Mikhail Nediak. Dynamic pricing with online learning and strategic consumers: an application aggregating algorithm. Operations research, 57(2): 327-341, 2009.
Diyang Li and Bin Gu. Chunk dynamic updating for group lasso with odes. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 7408-7416, 2022.
Jongmin Lim, Byungchai Lee, and Ikjin Lee. Second-order reliability method- baaedd inverse reliability analysis using hessian update for accurate and efficient reliability- based design optimization. International Journal for Numerical Methods in Engineering. 100(10):773-79. 2014.
Lan Luo and Peter X-K Song. Renewable estimation and incremental inference in generalized linear models with streaming data sets. Journal of the Royal Statistical Society Series B: Staristical Methodology, 82(1):69-99) 2020.
Mathurin Massias, Samuel Vaiter, Alexandre Gramfort, and Joseph Salmon. Dual extrapolation for sparse generalized linear models. The Journal of Machine Learning Research, 21 9595099556., 2020.
Peter McCullagh and John A Nelder. Generalized linear models. Routledge, 2019.
Lukas Meier, Sara Van De Geer, and Peter Bühlmann. The group lasso for logistic regression. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70(1):3377,, 2008
John Milnor and David W Weaver. Topology from the differentiable viewpoint, volume 21. Princeton university press, 1997.
12

---

Published as a conference paper at ICLR 2024
Martina Mittlböck and Harald Heinzl. Measures of explained variation in gamma regression models. and Computation, 31(1):61-73, 2002.
Communications
Jorge J Moré and David J Thuente. Line search algorithms with guaranteed sufficient decrease. ACM Trunsactions on Mathematical Software (TOMS), 20(3)228--37,, 1994.
Dániel Nagy, Lambert Plavecz, and Ferenc Hegedús. The art of solving a large number of non-stiff, low-dimensional ordinary differential equation systems on gpus and cpus. Communications in Nonlinear Science and Numerical Simulation, 112: 106521, 2022.
John Ashworth Nelder and Robert WM Wedderburn. Generalized linear models. Journal of the Royal Statistical Society: Series A (General), 135(3):370-385) -844,,3-8444 1972.
Brendan O' d'donoghue and Emmanuel Candes. Adaptive restart for accelerated gradient schemes. Foundations of computational mathematics, 15(3):715-72,, 2015.
Kumarjit Pathak, Jitin Kapila, Nikit Gawande, al. Incremental learning framework using cloud computing. arXiv preprini 1805: 2018.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
Ross Prentice, log gamma model and its maximum likelihood estimation. Biometrika, 61(3): 539-544, 1974.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
Hyun-Ko Ku Rhee, Rutherford Aris, and Neal Amundson, First-order partial differential equations, Vol. 1, volume 1. Courier Corporation, 2014.
Clemente Rodríguez, F Boto, Soraluze, and Alicia Pérez. An incremental and hierarchical k-nn classifier for handwritten characters. In 2002 International Conference on Pattern Recognition, volume 3, pp. 98 101, IEEE, 2002.
Saharon Rosset and Ji Zhu. Piecewise linear regularized solution paths. The Annals of Statistics, pp. 1012-1030, 2007.
Robert E Schapire. The boosting approach to machine learning: An overview. Nonlinear estimation and classification, pp. 149-171, 2003.
Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2012.
Jun Shao. Linear model selection by cross-validation Journal of the American statistical Association, 88(422):486-494, 1993.
John Shawe- Taylor, Nello Cristianini, et al. Kernel methods for pattern analysis. university press, 2004.
Cambridge
Stefan Siegmund, Christine Nowak, and Josef Diblik. A generalized picard-lindelöf theorem. Electronic Journal of Qualitative Theory of Differential Equations, 2016(28): 2016.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58 (8(11)2677-28, 1996.
Cheng-Hao Tsai, Chieh- Yen Lin, and Chih-Jen Lin. Incremental and decremental training for linear classification. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 343-352, 2014.
13

---

Published as a conference paper at ICLR 2024
Joaquin Vanschoren, Jan N Van Rijn, Bernd Bischl, and Luis Torgo. Openml: networked science in machine learning. ACM SIGKDD Explorations Newsletter, 15(2):49 60, 2014.
Jean-Philippe Vial. Strong convexity of sets and functions. Journal of Mathematical Economics, (1-2):187-205, 1982.
Xue Wang, Mike Mingcheng Wei, and Tao Yao. Online learning and decision-making under generalized linear model with high-dimensional data. arXiv preprint arXiv: 1812.029,, 2018.
Raymond E Wright. Logistic regression. 1995.
Lin Xiao. Dual averaging method for regularized stochastic learning and online optimization. Advances in Neural Information Processing Systems, 22, 2009.
Haiqin Yang, Zenglin Xu, Irwin King, and Michael R Lyu. Online learning for group lasso. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pp. 1191-1198,
2010.
Shuoguang Yang, Yuhao Yan, Xiuneng Zhu, and Qiang Sun. Online linearized lasso. In International Conference on Artificial Intelligence and Statistics, pp. 7594-7610. PMLR, 2023.
Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty. The Annals of statistics, 38(2):894 942, 2010.
XianXing Zhang, Yitong Zhou, Yiming Ma, Bee-Chung Chen, Liang Zhang, and Deepak Agarwal. Glmix: Generalized linear mixed models for large-scale response prediction. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp- 363-372. 2016.
Zhi-Hi Hua Zhou. open-environmeent machine learning. National Science Review, 98) 123, 2022.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pp. 928-936, 2003.
14

---

Published as a conference paper at ICLR 2024
Supplemental Material
Table of Contents
Glossary
16
Omitted Proofs
17
Proof Theorem
B.2
Proof of Theorem
18
B3
Proof of Theorem
21
B44 4
Proof of Theorem
23
B.5
Proof of Theorem
24
B.6
Proof of Theorem
25
7
Proof of Theorem
26
Proof Theorem
27
B.9
Derivation
27
C
Further Discussions
28
More Prior Work
28
More on Algorithm
29
Algorithmic Drawbacks
30
Open Problems
31
D Sensitivity Analysis
31
E
Experiment Details
32
E.1
Code
33
F
Additional Results
33
F1
Additional Histograms
33
F22
On the Inner-level Solving Interval
................................
33
F3
Performance Under Varying Levels of Sparsity
33
F4
On Other Forms of GLMS
34
F5
On the Non-linear Patlern
36
15

---

Published as a conference paper at ICLR 2024
A GLOSSARY
Term/Symbol
Explanation
SAGO
Algorithm for training a dara-va SpArse GLMs in an Online manner.
A
A corresponding batch algorithm.
d
The total number of regularizer(s) Predefined searching space of X.
A
A
The regularization parameter of the k-th regularizer, or the k-th component of X.
3
The learnable parameters model weights vector.
B
The j-th component of vector 3.
B
The optimal solution of B.
89
The parameter(s) of g-th group in group Lasso.
Sk
The subset of coefficients being penalized of the k-th regularizer.
X ,-,
The (sub)dataset include observation(s) to be kept, removed and incorporated in each round, respectively.
T1o Th, 71+
The number of observation(s) in X X=, X respectively.
m
The size of feature space number of features in observation.
A pair of i-th observation and its label.
30
The optimal solution before each online round (i.e., initial value of (3))
300
The optimal solution after each online round.
8
Loss function.
Lval
Validation loss.
(x,, W.)m
Validation set with N observations.
Calculated lower bound for and s.
8
Calculated upper bound for and
((t), P (s)
The defined parameterizers.
77
The potential parameter(s) for a penalty family.
T
Number of rounds.
T
Index for iterating over rounds.
iters
Number of current iterations when running SAGO.
max iter
Maximum allowed number of iterations.
A
Active set.
M
A positive constant in Theorem
elementwise
Twice-differentiable limited certain elements / coordinates (in A).
twice-
differentiable
reparameterization
The process of reparameterize using parameterizers.
knot
The point in regularizer that is not well-defined.
16

---

Published as a conference paper at ICLR 2024
(Continued)
Term/Symbol
Explanation
(x(x)
The subdifferential of For proper function R IR U foo). its subdiffer- ential at x E IR" is 0f(x) { E I Vy E R", f(v) 2 f(x) + u u - x)}.
sign(-)
The sign function, defined as x + x/ | with the convention 0/0 = 0.
exp(-)
The exponential function with base. Applied vectors, sign, exp(-) act element-wise.
if j E Sk.
(jES.)
The indicator function, defined as (JeS,) =
0
if j & St.
describe k-strong quasi-convexity.
(sk, (k)
The k-th event point.
(.--)
Inner product.
V3,3
Calculate second-order derivative.
0
Calculate second-order partial derivative.
Ω
An integral path [28 1) = 0.
Sa
Curvilinear integral over Q.
Sk,A
Intersection of the set Sş and A.
P(}
Probability of events.
Tolerance for hyperparameter X.
X
Optimal hyperparameter À in the space.
Some predefined constant in Lemma
Maximum absolute value of directional derivative in Lemmal
0(-)
The Big-O notation of complexity.
hs(-)
Hypothesis function.
B OMITTED PROOFS
B.1 PROOF OF THEOREM 1
present the formal statement of Theorem T as Theorem 9 and subsequently provide proof.
Theorem 9 (Equivalence Guarantee). Let A be a batch algorithm that trains the dataset X X and outputs a model f E H. i.e.. A (X) : X - H. Now, assume that there a requirement to incorporate observations in X* and simultaneously exclude certain existing observations X from the trained model using algorithm A. Then VT C H. we have
P SAGO A(X ET = ET.
where U represents standard set operations. The operator SAGO executes an online update based on the reformulation given by (2). Within the arguments of SAGO [-), the first term is the output of A (.), the second term corresponds to the observations to be added. and the third term signifies the observations to be removed.
17

---

Published as a conference paper at ICLR 2024
Proof. We begin by considering the case where t = 1 and According to Definition observe that p(t) = and v(s) = 1. This leads to the following representation of (2)
2
min Leal Σ ls V.. f(3 x1) xEA
(9)
d + Σ P. (1851 Ax)
s.t. B arg min
BERm
k=1jeSe
Equation is associated with the model state (i) depicted in Figure wherein (s, t) in (9 is
obtained by minimizing the loss of observations in X and X_. Assuming that (9) is properly solved
by a batch algorithm A, the solution indeed A U in (8). We now consider varying and to and 7, implying that (u(() = and v(s) = 0. This results in
N
min Loot = XEA
Σ 1=1
4
Üi-1
(3Tx.)
(10)
s.t. E arg min
E 0+
Σ Σ k=1jES.
P. (13,),
BER"
Equation 10 corresponds to the model status (ii), as illustrated in Figure 1 which is equivalent
the model trained by minimizing the loss of observations in X and X,, Assuming that (TO) is
correctly solved by a batch algorithm A, the solution is denoted as A (X* U X in (8). Since we employ our SAGO [-] to transition from (10), the equivalence of our SAGO and batch retraining methodology is thereby established.
B.2 PROOF OF THEOREM 2
Before presenting our proof of Theorem 2 it is essential to establish the existence of the path of solutions {å (s, (ss, [s, $)
for the inner problem, and { (A) LA E A} for the outer
[t. 8
problem as critical prerequisite.
Lemma 2. The solution paths 3 w.r.f. for AY E À for the outer problem.
2 exist for (ss t) E [s, for the inner problem, and
Proof. Our proof inspired by ideas in probability-one homotopy methods (Chow al. 1978). We make use of the 1-/ manifold classification theorem in differential topology (Milnor & Weaver 1997). which states that a 1-dimensional smooth manifold must be homeomorphic either to a line segment to circle. Therefore, need to show two things: (i) first, the path is (close to) 1-D manifold (it does not self-intersect); (ii) second, this manifold cannot be a circle.
The first is local property, and the implicit function theorem (Krantz & Parks, 2002) is used to prove it. To prove that the manifold solutions cannot be a circle, we make sure that the path starts at (s. f) in single direction. When this holds, it cannot be circle, since circle will imply two directions to choose from at each point. To see this, suppose that the manifold of solutions is a circle, and let be the circle. Let be unit tangent vector
point p on C, which gives well-defined direction Since the manifold of solutions is path, it intersects the circle at two points and p2. Let p1 be the starting point of the path, i.c., P1 (s, t). Without loss generality, the counterclockwise direction from be the unit tangent vector to C at P2. Since C is circle, 01 and d22 are opposite directions. However, since the manifold of solutions is a path, it cannot change direction suddenly, so it must continue the same direction as vi as it leaves Pt. But this is contradiction since v1 and U2 are opposite directions, so the manifold of solutions cannot be circle.
can assume that p2 is in Then, let ej be the unit tangent vector to C at Pt, and let 02
The proof for the existence of solution paths in the outer problem is analogous that of the inner problem; therefore, we omit it here.
L
We proceed to prove Theorem 2 first demonstrating the solution continuity of the outer problem, followed by proof of the continuous path w.r.f. the inner problem. For the sake of simplicity and
18

---

Published as a conference paper at ICLR 2024
uniformity, we designate the Hessian matrix V3 (A) H2(3). Similarly, the notation (3) to represent C-1 (.). We also introduce the shorthand H and H, to denote the second partial derivatives w.r. 8 and I, respectively, of B3, that is 0 (s. 1) and 3 (s,t).
Proof. Let (()) denote the solution corresponding to the hyperparameter value of the outer problem, and let 3(A + ΔA) represent the solution associated with the hyperparameter value X AX. Our aim is demonstrate that (()) 3(A AA) 0 AA + 0. By employing the fundamental
theorem of calculus, can write
JA M d3(x')
( AA) -
dx dX
(1I)
1
A+A d3(x)
AddX'
AA
dX
Taking the norm of both sides yields
-
B(A) -
1
A+AA
d3((x)
dx
(12)
dx
Utilizing Taylor's theorem, we arrive at
(A+ - - v AA+ 2 (AA) T Hx
(13)
where 3' is point on the line segment between B(A) and B(A AA). Rearranging terms, get
(A+ (A)+ (A) - - AN
1 M ||N||
(14)
2
We need to demonstrate that the right-hand side of 12 goes to zero as AA + 0. To achieve this, we shall use the assumption that H HB( = MI for some positive constant M and for every 3. Let
d5(X') be vector. Firstly, we can bound
d3(x) dX'
Σ
(3.
(3:] A1
JESS
d
<
2
(3,
Ps (105).
JESt
(15)
Vd
V Σ
Pm (13g/.20))
$
Amax
H H())
JES
Vd
V Σ JES,
Ps (18.)..2) \/
m
VM
where Xmax (H (3)) is the maximum eigenvalue of the Hessian matrix H (3)) at B. By employing the Cauchy-Schwarz Schwarz inequality, we can also derive the following inequality
d3(x)
1
||
dX
=
M
(I"
IMIPPN)
1M
ax
(16)
VX
1
1vllaxx ax
VAA
'We employ the shorthand notation 9 (or E,) in place of BA (or li.a) whenever the context allows for such simplification.
19

---

Published as a conference paper at ICLR 2024
Substituting this inequality into 12
and then using
(14) and 15
we get
A+AA
dB(2)
| ((++
-
A(A)
-
dx
IAN
dN
IvPax $
A+AA
dx
(AATAA MP(AAJON))
3
(17)
ax
A
M
A
| 1
= M AAJE.
Since M is positive constant, it is evident that the right-hand side of this inequality goes zero AA -> 0. Consequently, have established that | (A + ΔA) - 8 0 AA - which
implies that is continuous w.r.f. the variables of the outer problem.
For the inner problem, revisit the system of PDE (3) follows.
dp(t).
A&s,tt 0
V (3) (1)+) (B.A))
di
Ø1
du(s)
(B) 2 (3.))
s t)
ds
Os
(18)
2 (B.A) Σ k=1
V 32 Σp,
Pn (1..). 21) jES
+ 4 ((0))
Our objective to demonstrate that the solution 3(s, t) is continuous w.E.. both and t. To this end, let B1(8, I) and (2(s,,, () represent two solutions to the system in (18. Define the difference (B(s,t) t) = 31 (s, - (2 t). Our goal is to show that A5 can be made arbitrarily small by selecting s and sufficiently close, which implies the continuity of B(s,t), To accomplish this, consider the equation for As t), derived by subtracting the two equations (8)
du(l1) (Bet(8) - du(l2) dt
Vget(3) + + (BI. 031(81,41
7 (Bc.2) 082(82, 12)
dt
Ot
Ot 081(01,11) - E (B2,2) 0,3202, (2)
dv(si) (B)) du(s2) vzt + E (Br.))
ds
ds
Øs
Os
(19)
By rearranging terms and employing the Taylor's 's Theorem with remainder estimates (Folland 1990). obtain
(8(5,,11)+
82 81
82 - 81 to t1
(2,,3(011,))
82 - 81
+0 (11622-11,4 - 81, - (01--8811161)11 -())l())
to t
(2 tr
AB(s1,t1) + (..44,(s1,))
82 - $1
to t
+ 2 _ (1 (1-7).
82 - 81 t/ h
oV., (((,tt
Vv., AB....(s..)
(32 - 31) +
(t2 - t1) dy,
Øs
Øt
(1-7)s
Im (1- M)
(20)
where we utilize the fact that, according to 18 the functions ab(a.))
and aā(s.()
are continuous w.E.f
de
2t
and I,, respectively. Observe that the integrand in the final term of 20 be bounded using the
20

---

Published as a conference paper at ICLR 2024
Bruchy-Schwarz inequality and triangle inequality, follows
(s2 - -1) + Vv..
82 - 81 t2 1
(12 t1)
Os
ŌL
==
(1 116
OV,, (,)
OV., (3,,))
82 - 81
(s2 - -1) +
(12-41) (1)
t2 1
Os
Ōt
am (1-2))
(1
VV., AB(
1V s,t (
82 81 t2 t
882 81
Itz t1l
as
Ot
y= 1)-1)81
1=yt (1-
(21)
Substituting this bound into 20 leads to
A, A2( (2)l
(82 -11)
AB(51,
Vo. V
(12 41
/ (1-?)
(82- 62-51 $1
(B(st)
0V oV,, ((s,,)
(s2 s1) +
(t2 t1) d7
1/ 1
Os
Ot
s=ye2+(1-)1e
( )1 + (
(82 112-81) $1 1/2 1
82 $1
||
(IV., 4i)l + V2M / (82 -1) (12- t11²²
t2
A
)
3
V (st, 3
bi|| || (33-2) 91)
+M ((s2 01)² + (12 (12-11) -1)))
(22)
where we employ the assumption that H. 3 M1 and H; = M1m for every B. Without loss of generality, we assume that (8(1),4) 0, ie., B1 (81,4) (1). Then, we find
AB(52, t2) $ 3
$1 1/ 11 ((:g -
+ MM ((02 $1)² + (to - -1))) (23)
Let e > given. Since 0n(s.))
and 08(s.)) St are continuous w.rl. s and 4, there exists
such
ds
that for all s, with distance V(02 21)2+ (t2 t22 < 6, we have V V,, +1)
< + Now,
let A = min ( 3M J- Then, for any 82, to with V(s2 s1)² - (t2 t22² < A, it can be inferred
that the following inequalities
A3 (52, b2)
V,, 331,
||
||
(82 1 81
t2 +M ((02 (182-117² (t2 - 11)²)
81)²
2
(24)
E
(22 51 ) + M-
2
t/ - t
<e
holds. This result demonstrates that (s, t) is continuous function of s and t. Therefore, A(s, t) is also continuous function of and as it can be obtained by adding ( to B (s, t), which concludes the proof.
B.3 PROOF OF THEOREM 3
We commence by establishing Lemma 3 and thereafter, we present complete proof of Theorem
21

---

Published as a conference paper at ICLR 2024
Lemma 3 (Necessary Optimality Condition). Given (s,t), if B is a local minimum of the inner problem of (2). then 3 fulfills the stationarity condition of the inner problem, expressed as
PP, (18/). .h
((t) V,, (g,
Σ
wy w)]()E = =0, Vj E [m],
0|3]]
(25)
where the coefficient wj meets
(-1)
if 33 <0
W E
[1,1]
if 3
(26)
if 8 0
Proof. Two potential cases are contemplated. (i) When the penalty function P. (1551, As) is convex,
this naturally corresponds to the first-order optimality condition for unconstrained convex minimiza- tion (Boyd et al. 2004). (ii) Alternatively, when P. [10,) )x.) is non-convex, the optimality condition is examined on a coordinate-wise basis. For j E U A3 + 0), this is self-evident. When 3 = 0, the implication of 3, being local minimum is that the two directional derivatives are non-negative
Danilova et al. 2022). We denote the inner-level objective of the parameterized problem by
(B). Let Cy represent steering vector. Then, we obtain
θ ( + +e,) 0(3) (00000
OP, (133) AR)
de,0 (33
lim
+
Σ
> 0
e40
6
k=
+ (8 + se,) - 0(3) -, (0()) + +1) (v)))
d
OP, (13,) An) 20,
d-e, ((3)
lim <10
Σ
E
0 |8gl
(27)
which is equivalent to
25 with wy E [[-1,1] 1].
In light of Lemma
we now proceed to delineate the proof of Theorem
Proof. To infer the inner-level dynamics, we treat/ 3 as a bivariate function of 8 and t. Initially, we compute the partial derivative w.r.f. which adheres to the subsequent equation
du((t)
V pa E2 (3(s,1) + m(1)3 E (B(s. dt
0BA(s,t) t) + (s) & (B(s,1)
3BA(s,) t)
Øt (84(s,t) 0.
V2 22 ())
(s,
BA Σ Pn (18)
Ot
Ot
JESu.A
(28)
Likewise, the partial derivative w.E.. is established as follows
((t)V Ea ()(s,t) 1))(s,() as + du(s)
du(s) EA (B(s. + +u(s) E (3(s,t)
a.3((, 1)
+
ds
Os
0BA(s,t) IN
0BA(s,t)
V V2 1 ())
Σ
BA
Σ Py (133)/22) .2x)
0.
Os
1=1
JESt.
(29)
*Considering the path illustrated in Figure distinct directions can be identified.
we can observe that at any given point on ?, maximum of
22

---

Published as a conference paper at ICLR 2024
In situations where the expression does not engender ambiguity, employ & as shorthand for B(s, t). By reordering the terms in (28) and 229, acquire
du(()) (3) + Vi
0Bu(s,
+
V2 RA JESu.
Σ P.j
(13)
dt
Ot
k=1
common term, denotes as E(3.2)
(s(s) V (A +
ViA (20))++((( +
Σ Pn (135).21)
00A(s, t)
ds
BA
Os
1=1
JESE,
(30)
Incorporating the initial conditions of the system, we arrive at
du(t)
034(s, t)
0
dt
dv(s)
08,(s,t) 0
vDx + + (B.2)
(31)
ds
Os
(sst)) t)
l=git=t = 3o.
wherein the E (B.>) has been pre-defined in (30).
Remark 4. Furthermore, the E (3.2) is verified to be positive semi-defing The verification of the positive semidefiniteness w.r.t. E (B,x) is drawn from the second-order necessary optimality condition when constrained to coordinates within the set A.
B.4 PROOF OF THEOREM 4
Lemma 4 (c.f. Lemma 2.1 in Ghadimi & Wang 2018)). Assuming for any X E A, the U22G (A, wx) invertible. We consider
min f(A) = F XEA
s.t. w> = arg min min G(A,w) w)
(32)
and the hyper- grpperggralient w.r.t X takes the form
Vxf = OFF - OwiG (A, &.G O.F (N,w)).
(33)
Herein, F and G represent the outer and inner problems, respectively, and X, w are the corresponding outer and inner variables.
Employing Lemma 4 will demonstrate the proof for Theorem
Proof. Grounded in the PDE associated with the inner problem solving, we obtain the following condition
0 E V (0))+ V (5)
Σ
P. (133 (B3). k= JEE
Σ
(34)
where d signifies the subdifferential (i.e., set of subgradients). Subsequently, by differentiating both sides, apply the chain rule, and invoke the implicit function theorem we derive
d3 (3)
d3
OE 2 F4
dx
V2
(3)
dd
V
Σ
Py ((3)) An)
:2x)
+
+V2
BA
Σ
P
((²)
Ae
dt
1=1
JESu.A
JES
(35)
23

---

Published as a conference paper at ICLR 2024
A9A dA
Upon extracting the factor w.r.f.
we deduce
)
dBA
d
(13)) = 21c) )
V
(200))
+
AA
33)
dx
V
Σ
k=1
JE
1=1
JESK.A
(36)
By reorganizing the above expression, we arrive at
)[
dBA
d
VBA (2(0)+
+ Σ 2 Po (13)
Po
-DA Σ Py (12))
dA
jESu.A
jESu,
(37)
Moreover, Lemma Supplies the derivative as given in (38)
N
d3 dA
Vxhrall =0x
Es @i.1 f (BTx:)
xx
V 8 i=1
&
Vi.1 (BT&:))
2=1
(38)
B li [ s xx)=
db
dx
B.5 PROOF OF THEOREM 5
Lemma 5 (Implication of k-strong
(c.f. (Vial 1982)) By definition, a differentiable
function Loot is strongly quasi-convex if the following inequality holds
Enat (X*) 3 Luas (Aa) + L (2a)" (X* - Aa) + K マタ - Xz112
(39)
for some k > 0 and all A A.
Subsequently, we provide our proof of Theorem 5
Proof.
Utilizing the property articulated in Lemma 5 and invoking the triangle inequality, we ascertain
that
N
Lval
Σ
4 Wos f (STA*)x:)
N
4 f f (BTA)x))
Σ
N
sh (b.. (BTW)x)) -x)
- 11
+
-X1?
+
N
N
E f f (B(A)x))
+ + || 1 - x=1 2 +
Evae, (ii. (BTA)x))) =2
-112- - 2/1 cos 2b
i=1
N
Σ V g2 (w.,1 f (3T()):)) FARCNs/ (((A)))))=A&((())
N
>
Σ
(BT
11 A1 ~1
+
- -1 xll
i=1
(40)
where
ΣN V
1 (AT()) x;) -
3/ arg cos
(41)
N ΣN' Voli J ff (BT(A)))))
v2B(A)
-11-- All
Following the reorganization, we deduce
N
K | 2-
- - All-
<
Σ
V shs (Dr. (B(A)x:)) )
(42)
2
24

---

Published as a conference paper at ICLR 2024
For the case where À X", the proof is self-evident. We now consider the scenario wherein À X², thereby arriving at
Σ Val (ūs, ( (BT()2;)) VasrA
a| X1I
(43)
2
This in turn leads us our ultimate conclusion, expressed as
V Voli ( (3 (BT()x:)) vASCA)) 22ex
| 1 X1 & 2x
(44)
B.6 PROOF OF THEOREM 6
Proof. We can complete this proof by contradiction. Suppose that À lies at the end point of one segment of solution path, and the corresponding Jacobian J is full rank. Let A = 3 - 3 and AA = X' X, where the elements in 3 considered indexed by the activity set. Since 3 satisfies the KKT system of (2), we have
d Σ
V Vet (B) u(t) (3)+
Σ agP, (13)). k=1jES
(45)
0x Σ la Ün.1 (BTA)x:)) =0
From the above assumption, we know that X is not on the solution path. This implies that there exists some 3r such that satisfies the KKT system, where 3r is different from B. Then we have
4e (B') ((1) (8))
+ Σ Σ
PgP (13) X/) =0
k= k=1jES
(46)
0 Σ l ir. (BT()) 0.
Subtracting the two sets of KKT conditions, we obtain
V (8)))) ( (()) + u()VV
(ee(3²) (()
(47)
+ V (((8))((3)) Σ Σ
OgP, (10) .x)) 0ztn (18) (22)
Ax)
0.
jEj.
Note that 3 and 3' have different active sets, which means that some of the gradient(s) above may not
exist. Let Cr
øt Øउ.
for i E P. Then we have
OE V (1(3) (8)) + v()VV, ((())-((3)) + v(8)V (1(8)- - -E(3)
Σ ai (3)) -ign(())) + Σ Σ OpP, (105) .Xo) - Ogpn (185).211 .222
(48)
iEP
k=ljes.
0
Σ
l (int (BT())x:) ls (J..f (BTA)x
Without loss of generality, we set t, 8= 3 to simplify notations. Now we can convert the above system as
p
J.
= 0,
(49)
A
25

---

Published as a conference paper at ICLR 2024
where J is the Jacobian matrix defined in the theorem statement. Since J is full rank by assumption, have 3 and A 0. This contradicts the assumption that 8 and X are different from 3 and X, respectively. Therefore, the end point cannot have a full rank Jacobian matrix. Hence the theorem is proved.
Geometric Intuition. There also exists geometric understanding towards Theorem 6 Consider perturbation (AB, ΔA) w.r.f. the variables / and The perturbed optimality condition, linearized around (3, A), can be written as
d
d (P.g) + _ 0 P.
0 (C-
Pr
(3/ (1x A
(3)
AA = 0, AB)
k=1
jESk
k=1
JESk
Σ k=1
83 P,
(133) A1x .2x)
3 = =0, a= max
Ol
i I.E.
03,
JES
(50)
matrix J is full rank, then the only solution to the linearized optimality condition is the trivial
solution Appp
Ax = O, which implies that no nontrivial perturbations in the variables 3 and À can
satisfy the optimality conditions near (8, A). Suppose (AB,AM) span the null space of J. Since the Jacobian J non-degenerate, there must be a unique direction (A,, AA) in the null space of J. Taking small step along this direction will not violate the KKT conditions given the active set, and thus, the path continues in that direction. Therefore, (3, A) cannot be the end point of one segment of KKT path in this case.
B.7 PROOF OF THEOREM 7
Proof. We commence by examining the case where an index j' is appended the set A at the point (t,s) s) within the interval [t. [s, 3). Let B(t, s) represent the vector of solutions at (t, s), and ((..s) denote the subvector pertinent the active set A(t, s). By derivation, the PDE system illustrating the trajectory of 3 is given by
8)) DL
du(t).
dt V (B) du(s) VB (A
Z (aAcc.))))
(51)
aBt(t,s) s)
Os
ds
where Z Z(3 (BA(L.0)2) is defined as per
(3. Hence, for any small ot > 0 and âs > 0, there exists a 6,9
such that
i A + 5, -A(14880455))
(52)
On integrating
52) over the interval [t, t öt) and [s, ds), we derive
du(t') Vale ve
83 1.0t
85
E (BACe...))))))
dt du(s')
ds'dt'.
(53)
V ((r,))))))))
ds
Upon synthesizing (5) and 53 it becomes evident that the change in By nonzero. Thus, obtain
(t, + and By + öt, 8s) +
(54)
which signifies that j' is included in A (t, s) and would remain active for small öt 0 and 5s > O. This further implies that j' will not be excluded from in the immediate next time of segmentation.
Utilizing a comparable line of reasoning, we assume the existence of a point (f', s') ) in the interval L. x [s, ø] such that j" expelled from at (t', 8"). Given that j" is inactive, the corresponding
26

---

Published as a conference paper at ICLR 2024
entry of () becomes zero. Additionally, the coefficient w associated with By at (t', (t',") must be less than 1. Otherwise, j" would be active in the segment. Analogously to the prior case, we integrate 52 over the interval [t', t' + 5t"] and [s', 8' + 6s'] as
du(t") dt Vax E AA(M a (8)
88" = fra
E (BAl(MM.))))))
ds" ds"dt". (55)
du(s")
Vaa (B)
ds
By combining [51 and 533 it can be observed that the change in 8yr zero. Thus, we derive
By 5') = 0 and Br + 50' 58') 0.
(56)
As j" is excluded from A at s") and remains inactive for small 8t' and òs' > 0, it can be deduced that j" will not be incorporated into A during the immediate next time of segmentation. C
B.8 PROOF OF THEOREM g
22008). it can be deduced that 3, o too and d j t... We define a compact set T x S, where T [. and S = [s. 8). As L and increase within s1) E T x S, the active set A may alter. Employing Theorem 2 and Definition readily verified that there exist gma g_aa such that gmax
Proof. Analogous to the analysis conducted in Le Thi et al.
[ it can be f > and s g 8 > 0, where tm and gmax denote the maximal and s fulfilling Lemma 3 given the initial partition A. Consequently, the first segment constitutes a nontrivial interval (iee, not merely a single point). In a similar vein, one can deduce the existence of sequence of nontrivial interval(s) within T x S. Based the active set definition, each subinterval must correspond to unique pair of partitions A and A. Invoking Theorem 7 we ascertain that the sequence of segments is finite, as the combinatorial numbers of A and A are finite.
We now examine the outer problem. Analogously, as À varies, the path of 3 is also piecewise smooth, with each segment associated with a specific active set AA Given that the number of potential combinations of the active set A is finite, a finite number of piecewise segments exist for the path w.r.f. A. Hence, we have demonstrated that both the inner and outer problems can be solved in finite number of steps, thus completing the proof.
B.9 DERIVATION OF (4
To integrate along the Ω, we need to combine the first two equations in the PDE system as follows
du(t).
(BA(s,t) Ven (2) ((3.)) 0š1(s,t)
du(s)
( (B,(s,t)
+ ds
dt
Os
=2 (3.2) -0.
Os +
(B,(s.t)
01 + di Vo)
dult).
dv(s)
(
(57)
ds
Given the integration path ((s, t) = O, we calculate a vector line integral to obtain
(B2(s.t)
3 (sk (0-1114-11)
do
+
de
8 Os
Øt
12
du(t)
Voa C (3)dt 1 ((3,))-1. du(s)
9 (sx 1, 11
((3,2)
ds Vol E (3)ds
dl
- (sa- (52-1,22111
/ (3.))En
_(B,A)-1
ddu(t)
Ba et (3) + du(s)
ds V (33)ds))
(di dl.
f(
((au(s) Vex du(() VBa V ( [ss, dt
=3 -8k-111
I(0,
ds
dt
(58)
which yields the final result
4 for each respective segment.
27

---

Published as a conference paper at ICLR 2024
C FURTHER DISCUSSIONS
C.I. MORE ON PRIOR WORK
C.I.1 LIMITATIONS OF OTATE-OF-THE-ART
In this subsection, we present an analysis highlighting why prior art cannot be trivially extended to sparse GLMs defined in objective (I). This discussion not only illuminates the connection between our theorem and pre-existing work, but also delves into the limitations of specific data-varying algorithms.
Incremental learning with k-Nearest Neighbors (k-NN) is derived from the inherent nature of the algorithm (Rodríguez et al. 2002). As instance-based learning algorithm, k-NN retains the entire training dataset instead of parametric modeling. It can incorporate new observation(s) into the existing training set without necessitating retraining process. This characteristic due the absence of internal parameters or states, i.e., only the data itself matters. Analogously, removing observations involves merely deleting the corresponding data. The process for online logistic regression presented by Tsai al. (2014) transforms the original objective into its dual problem, and outlines the boundaries to estimate solutions after one online round. Using this solution, they apply warm-start training to compute the definitive new solution. However, their primal and dual initial values in (12) are not adaptable to models exceeding simple & and lz loss, as their dual form would invite added complexity. Therefore, we cannot derive similar bound as presented in their Equations (17) to (19).
Adopting the procedure of online Lasso (Garrigues & Ghaoui 2008), employing different losses would not yield closed-form solution for 01 and w2 like their Equations (4) and (5), which are crucial for deriving the analytical updating rules using homotopy reformulation. Analogous constraints also apparent in the methodologies of the generalized Lasso (Chen & Hero 2012) (i.e., their Equations (35)-(40) (Hofleitner et al.) (013) (i.e., their Lemma and Lemma 2). The research concerning online group Lasso (Li & Gu (022) utilizes the finite difference and Taylor expansion. Nevertheless, in their Equations (5) and (6), other loss functions (e.g.. inverse Gaussian deviance) cannot independently separate Aw" and AØ as per their derivation. Furthermore, the high-order residual of their regularization term converges to constant and therefore, cannot be extended to broader situations as explored in our study.
Moreover, numerous studies on online (or incremental and decremental) SVMs (Laskov et al. 2006 Gu et al. 2014 2015 2018: Kashef 202T] are conducted in the dual space as opposed to the original loss. During on online adjustments, they typically maintain the KKT conditions of the various classes of support vectors, encompassing both relaxed adiabatic incremental adjustments and strict restoration adjustments. It is evident that the style of these works differs significantly from general sparse GLMs and thus cannot offer technical insight for the development of more generic online GLMss
Within the context of adjusting the hyperparameter(s) in online scenarios, (Garrigues & Ghaoui 2008 Yang et al. (202)) attempt to derive many rules for updating the regularization strength in each round. Nevertheless, these methods remain largely heuristic in nature, demonstrating deficiency in identifying the locally or globally optimal À throughout the full breadth of the parameter space.
C.1.2 RELATIONSHIP WITH (CONVENTIONAL) ONLINE LEARNING
The term "no-regret" is used to describe online algorithms that have a property where, as the number of rounds decisions grows, the average regret per round converges zero (Zinkevich) 2003).
Concerning the regret bound of SAGO framework, based on definition Regret -ーー F (.-)
mingeRm ΣT= (5) (T is the round index and F denotes the whole objective i and our Theorem (i.e., Equivalence Guarantee), we could simply find that the theoretical regret value is fixed at
ΣF_ 0.
Pursuing alternate vein, drawing upon the framework established by (Zinkevich 2003 Xiao
2009; Duchi et al. 2011
Wang et al. (0188) in conventional online learning, numerous contemporary Luo & Song 2020 Yang al.] (2023) have ventured into facilitating online learning for sparse GLMS with regret bound. In other words, their algorithm fails to establish an
studies (Fan et al. 2018
equivalence guarantee similar to that of our Theorem
28

---

Published as a conference paper at ICLR 2024
A salient distinction between these works and ours is the access constraint placed training data in their algorithms. Specifically, these algorithmss are limited to accessing only the "current new" training data. Once a subset of the data has been utilized in particular round, it becomes inaccessible in subsequent training rounds, due to the stipulated setting which forbids the retention of historical training data. In essence, they cannot store data in an offline manner. While several algorithms are permitted to retain summaries of past observations such as historical average gradients (Shalev- Shwartz et al. 2012 Hoi et al. 202T), theoretically, they still fall short of emulating the effectiveness of batch retraining. Nevertheless, these methods intrinsically offer approximate solutions. Their convergence to the stationarity point of a new or modified dataset remains non non-deterministic. This underscores that the models derived from these methodologies are not congruent to those trained ab initio as in our SAGO approach. Additionally, they frequently exhibit an insufficiency in adaptively adjusting regularization hyperparameters.
C.1.3 RELATIONSIIPP WITH MACHINE UNLEARNING
Recently, concerns related to privacy in machine learning have gained pronounced emphasis. In this realm, machine unlearning (or data deletion) algorithms (Bourtoule al. 202T Gupta al.] 2021)) exhibit certain parallels with our configuration as detailed in Section 1. Such algorithms endeavor to expunge the influence of specific data points from trained models, aiming for a more computationally efficient alternative than a complete model retraining. Fundamentally, these algorithms prioritize an approximative online removal strategy, utilizing the theoretical framework of differential privacy. This stands in contrast to our approach, which concurrently addresses both the addition and removal of samples. Nevertheless, our methodology holds potential to inspire future endeavors in that research.
C.2 MORE ON ALGORITHM T
Solving Interval The length of the solving interval (path) for the inner problem has a bearing on different varieties of (()), m(s). Remarkably, significantly shorter interval results in a substantial reduction in the total query times (computing time) of PDE solver. We will verify this property empirically in Appendix F22 However, we underscore that an exceedingly short solving interval could potentially instigate numerical instability. Moreover, an overly complex form of parameterization would considerably augment the challenges in theoretical analysis.
Line Search for Event Points To more efficiently identify the location (existence) of the subsequent event, a line search strategy that integrates binary splits with interpolation could also be employed. Starting at an event point, we utilize interpolation to estimate the solution 3 ($k+11 (x+1) ) for the end of next segment, assuming there are no nearby event points. If the interpolation proves unsuccessful, we either resort on bisection (Moré & Thuente 1994) between the known maximal point (after an event occurrence) and minimal point (where no event has occurred), or use step size three times the last one if we do not know any maximal point. Within the line search, if any probed point has already been computed, we directly use the cached solution.
Generalized Thresholding Conditions In Section 3.3 we have discussed the application of the & regularization term's 's thresholding condition. Indeed, this a classic conclusion, but it might struggle with expressions of other more complex regularizers. Here, point out how to establish thresholding condition for all regularizers that meet our Assumption [ For more general cases, you may find our previous Lemma 3 useful, as it is not based on any specific regularizer and provides set of subgradient conditions for 3,. In practice we only need to calculate (or just estimate) the value
of wy according to Equation (25). and based
(-1)
if 3 0
Wj
3, 0 [1,1]
(59)
(1} if 83 > 0
determine the occurrence of event E1 and E2. It is worth noting that if the computing architecture allows, each wj can be calculated in a parallel and vectorized manner.
the loss on the training when computing the gradient flow for the inner problem, and use the loss on the validation set for the outer problem.
Remark 5. When computing the Wj via (25), should
29

---

Published as a conference paper at ICLR 2024
analyzed the algorithmic complexity of the SAGO. In the context of computational overhead, it is imperative to elucidate the following points
Regarding Computational Burdens In Section 4.2
and 6 give the explicit expression of gradient when solving PDEs & ODEs, which substantiates the symmetry of some (sub)matrices and leads the fundamental acceleration induced by Numpy & SciPy libraries. While the principal burden of solving lies in matrix inversion, how to utilize the symmetrical characteristic to accelerate inversion has been extensively well-investigated in community (Lim al., (014). Additionally, more libraries oriented towards parallel computation are emerging, such as the pbdR package in R.
Our Equ.
Assuming that the partition A known, even the fastest (rate) second-order Newton's method needs to solve the similar linear system multiple times until final convergence. The efficiency of SAGO lies the fact that no iterations are needed the overwhelming majority values of and it adaptively chooses step sizes to capture all pertinent events across the intervals.
The current state-of-the-art in numerical libraries for ODEs and PDEs offers commendable computational efficiency. Furthermore, there exists a relentless endeavor within the research community unearth even more expeditious solution techniques, exemplified by works such as Nagy et al. (2022).
GLMs without the Sparsity Given A represent the complete set of features within the dataset, our proposed SAGO approach can be seamlessly adapted for dense parameter estimation within generalized linear models. Interestingly, the imposition of sparsity often eases the process of theorem derivations, influencing steps within Algorithm without imposed sparsity in Algorithm
We elaborate S&GO in the context of GLMs
Algorithm 2
SAGO Algorithm (Dense Estimating)
Require: Initial solution 3(0), online rounds T, training sets x*xx*, X in each round, tolerance
for A, mar mar_iterr iter.
1: Initialize A < [m].
2: for 7= 1. _
3: 8 s
4: while 8 S 5, 1 < do
5: Solve the PDE system
Inner-level problem
6: Update 3(7) and L.
7:
end while
8:
iters +0
9:
while | > and ilers < moaziler do
10: Solve the ODE system (5). D Outer-level problem
Compute VxLval via (6).
12: Update 8(7) and li,A, and warm-start if necessary.
ilers ilers +
14: end while
(T) + arg min VxCval
16: end for
Ensure: (g(r)), (10)
C.3 ALGORITHMIC DRAWBACKS
In this subsection, we articulate the inherent limitations associated with the proposed SAGO algorithm. Currently, these primary drawbacks manifest in two specific areas.
Memory Challenge. The foremost consideration is the storage challenge in the context of online applications. Our framework necessitates the storage of every observation present in both X and X* With the substantial accumulation of historical data or the influx of new data, the required memory space escalates significantly. That is to say, if the quantity of samples consistently increases in each
30

---

Published as a conference paper at ICLR 2024
round without any corresponding reduction (f.e., data deletion), the storage requirements of our algorithm will progressively grow until it surpasses the maximum available capacity. Contrastingly, certain existing online frameworks (Duchi et al. 2011 Yang al. (023) offer adaptability to online environments involving infinite rounds since they solely store the information extracted from the historical data.
However, within the perspective of information theory, the necessity to guarantee the first-order optimality condition remains theoretical inevitability for nearly all exact online algorithms, with some SVMs being the exception.
Dimensionality Challenge. Another important aspect note is the challenge posed by high- dimensional data. In scenarios where |A] > n, the running complexity becomes predominantly governed by |A] rather than the size n. Consequently, in cases of exceptionally high-dimensional data, where the order of magnitude of |A| exceeds that of n (or no + (n, n=)), the algorithm's performance advantage is likely decline, or possibly underperform when compared to established batch algorithms.
To further improve the scalability of SAGO, we primarily need reduce the computational burden associated with Hessian inversion. An intuitive approach might involve leveraging low-rank approxi- mations or related methodologies. Another conceivable strategy could entail keeping the Hessian component of (3) and (5) fixed for many queries, modifying only the gradient part, and updating the Hessian intermittently. However, the clear disadvantage would be that the equivalence guarantee would no longer hold. We have not yet explored this avenue but believe it is worth pursuing.
C.4 OPEN PROBLEMS
Despite the progress accomplished through this study, there remain multitude of open-ended questions that can act as promising trajectories for future research. We give examples here.
In relation to Remark we noted the possibility of path discontinuities arising in the context of non-convex penalties. Formally, let e, denote a steering vector. Then there exists X dis such that
lim @ (Adie + Ee,) * lim 3 (A + s70
=10
This phenomenon leads to an interesting question: how can we calculate the value of / during discontinuities without the reliance on warm-start training? If we can establish equivalent updating rules, we can further improve efficiency for non-convex (p, E).
Computing the gradient deep learning architectures can prove to be highly computationally intensive. This leads us to the question of how we could effectively extend the proposed methodology SAGO to accommodate more intricate structures such as neural networks or other machine learning tasks like clustering algorithms? Additionally, exploring how SAGO could be adapted to the context of black- box models presents a significant challenge.
D SENSITIVITY ANALYSIS
In this section, we turn our focus towards the stability analysis of the inner-level problem, acknowl- edging that the outer layer problem follows a comparable tract. To carry out a sensitivity analysis on the solution 3(s, t) of the PDE system, we first introduce small perturbations to the independent variables s and Let ös and öt represent these perturbations, and 83(s, t) is the corresponding perturbation in the dependent variable A(s, t). Nonetheless, without specific functional forms, a general sensitivity analysis may be quite abstract. We can now consider the Taylor expansion of the perturbed system around the point (s, t), and we have
B(s + 8s, t 5t) (s, + a3((s
8s
Øt 5t O(os"
as
(60)
= (s,,) t) + (3((st)) t) + 06852,0
31

---

Published as a conference paper at ICLR 2024
By substituting this expansion into the original PDE system as per B of the system concerning the introduced perturbations. This results in
effectuate the linearization
du(() (10) V2 [ + v dt
(8,(s,1) Öt
0.
(61)
Using the base solution
dp(t).
0B2(s, 01
Ve (
(62)
di
the first term inside the square brackets in 61 vanishes leaving us with
du(t) di C3)00 v
03A(s.t) 0.
Vī(3, A)03
(63)
01
We can follow a similar process for the second equation. Upon linearizing, we obtain two linearized PDEs for the perturbation (s, t) as follows
du(t) dt
0BA(s,t) t) 0
V (3)68 V
Øt
(64)
dv(s)
0 t)
V2 (3)58 (
8s 0.
ds
Investigating the eigenvalues of the Hessian matrices V (3). V (3) and V3,5 helps
us inspect the stability of the solution 3(s, l). In practical settings, it becomes imperative to utilize numerical methods for finding the eigenvalues and affirming the system's 's stability given the intricacies in analytically solving this eigenvalue problem for particular functional forms and parameter values. solution exhibiting all positive eigenvalues can be deemed stable concerning the perturbations ós and 8t, while the presence of any negative eigenvalue imply potential instability in the solution.
Table 3: The smallest matrix eigenvalue across 50 trials, with the loss function imposed on each dataset identical to that mentioned in Section 5
Dataset
crediteard
MiniBooNE
higgs
numerai28.6
2dplanes
452.7
2.3
466.1
2925.7
1484.1
57.9
8.0
945.6
2821.5
1534.9
38.8
1.7
307.5
1708.5
1526.6
P
383.4
5.0
1828.4
1071.5
1517.9
Dataset
ACSIncome
Burzinsocialmedia
fried
OnlineNewsPoqularity
house_ |6H
1313,9
0,0422
2785.6
0.360
5891.0
854.8
0.0230
3160.8
0.323
5032.7
V P
827.3
0.677
2982.7
0..69
5343.1
P
662.0
0.0826
3025.4
0.397
5240.7
BA
Referring to the large amount of positive outcomes in Table 3 we can ascertain that the PDE system exhibits stability simulations. This implies that small perturbations in the solution will decay over time and will not give rise to unbounded behavior. This inference is instrumental in understanding the robustness and reliability of the inner-level PDE system, along with its solutions various online data-varying applications.
E EXPERIMENT DETAILS
In this section, we provide missing details of the experimental settings used in Section
32

---

Published as a conference paper at ICLR 2024
Data Preprocessing For datasets regarding both Poisson and Gamma regressions, take each component in label 3/4 as its absolute value to ensure it's greater than 0. For X (i.e. deleted observations), generate noises by turning normal samples into poisoning ones by flipping their labels (Frénay & Verleysen 2014 Ghosh et al. 2017) for classification tasks. For regression tasks, noises generated following distribution analogous the original training data, consistent with the methodology delineated in Jagielski et al. (2018).
Infrastructure All experiments presented this study were conducted on a workstation running the Ubuntu 18.04 operating system, equipped with Intel 2.30GHz CPUx200 and 400.0GB of RAM. should be noted that we abstained from employing data-parte aata-parallel training methodologies during performance speed comparisons.
Baseline Details We implement our SAGO algorithm in Python 3.7, wherein the numeri- cal solvers exploit the Runge-Kutta method of order 4 or 5. We implement the batch train- ing methods in Python, using the NumPy and SciPy libraries. The parameterizers are set to (t)= y (s) = s², respectively. We approximately control each group to have the number of 10. d) features. The convergence tolerance for batch training is le-7 and the tolerance for hyperparameter in the outer-level problem is le-4. For logistic loss, we adopted the line search algorithm presented in Beck & Teboulle (2009) estimate the Lipschitz bound, with an initial guess given by the Frobenius norm of the data matrix. We didn't 't compare with the baselines for simple fz-regularized cases, since their problem structure less complex than ours. Meanwhile, they cannot be extended to other GLMs like SAGO did here.
Results Details The Figure 5 Figure Figure 7 Figure g are plotted using Logistic group Lasso on the higgs dataset, while the Figure 4 (left) is plotted using sparse Poisson regression the ACSIncome dataset and the Figure 4 (right) is plotted using group Lasso on the credit card dataset. In Figure 7 manually alter the optimality conditions shown in our Lemma to trigger the events E1 or E2, so as to test with the varying number of event points.
E. CODE
To ensure the replicability, Python codes corresponding to the pivotal components of the proposed algorithms are incorporated within the supplementary materials.
F ADDITIONAL RESULTS
F.1 ADDITIONAL HISTOGRAMS
The histogram of the number of event points when solving the GL.M on more datasets are provided in Figure [ and Figure IO] It should be emphasized that the total number of event points is intricately linked to the length of the solution interval. Consequently, our primary focus is on their distributional characteristics rather than their absolute count.
F.2 ON THE INNER-LEVEL SOLVING INTERVAL
In order to investigate the total query times when solving the inner-level of SAGO, we adopt the different 2 (-) and mark their running times as shown in Figure When the interval length gets shorter, the total number of queries also gets smaller, resulting in a decreased total training time, The results of this experiment align with those delineated Appendix C.2
F.3 PERFORMANCE UNDER VARYING LEVELS OF SPARSITY
To investigate the performance of SACO with different scenarios of A, simulate the settings in Section while varying the size of feature spaces. The results of accuracy performance as well as the running time reported in Table and Figure 12 respectively.
As the dimensionality (i.e., the number of features) of observations increases, the efficiency benefit of our SAGO algorithm, as quantified by the performance gain (or time gap) among various methods,
33

---

Published as a conference paper at ICLR 2024
1.0 0.963
10
1.0
0334
2.891
0.814
Probability
Probability
Probability
Probability
0.6-
0.6-
0.6
0.6
0.4
02-
0.2
02-
0.2
0.228
2
0
0.0
2
0.22
2.
0.0
0
2
# event points (ACSincome)
# paints (Buzzinsaci almemia)
# event points (fried)
event points
(house_166) 16H)
Figure Histograms number of event points in inner-level problem when training the GLM (i)
(i.e., Sparse Poisson Regression). The name of the each dataset enclosed in parentheses.
Probabliity
Probability
0.638
Probability
Probability
0.519
0.49
0.301
0.287
0.221
0.206
0.072
0.029
2
0
3
event points (ACSIncome)
# event points (Buzzinsocialmeddia)
event points (fried)
# event points thouse_16H)
Figure 10: Histograms of the number of event points in outer-level problem when training the GLM (i) (i.e., Sparse Poisson Regression). The name of the each dataset enclosed in parentheses.
Table 4: Numerical results for validation loss w.rr different levels of feature space. The best results are shown bold. simulations we use sparse Poisson regression (i) on Buzzinsoci amedia dataset and the number of observations in X and X is fixed within the trials in each column. In order to increase the quantity of features, we have employed polynomial feature transformation with degree of 2, and randomly select subset of features.
Method
m 21
m 41
m 61
m 81
m 101
ColdGrid
0.62
24.92
16.44
12.80 1 0.38
11.78
WarmGrid
42.67 + 0.39
24.76 1: 0.58
16.27 0.78
12.68 1 0.78
11.76 = 0.45
ColdHyBi
41.83 0.27
25.23 0.11
16.04 + 0.49
12.81 1 0.48
12.26 0.52
WarmHyBi
41.68
0.15
16.28 + 0.39
12.82 0.33
12.09 0.34
ColdByo
41.77
24.58
16.57 0.56
12.69 + 0.45
11.95 0.24
WarmByO
41.44
24.40 + 0.37
16.56 + 0.43
12.52 - 0.55
11.83 0.26
SAGO
40.85
24.36 0.13
16.04 + 0.07
0.19 12.52 0.19
11.63 0.27
tends to decrease. On the other hand, the increase in the number of observations does not significantly influence this efficiency and complexity. Consequently, we can conclude that the SACO algorithm exhibits superior performance in scenarios characterized by extensive sample sizes opposed to those with high dimensional spaces.
F.4 ON OTHER FORMS OF GLMS
34

---

Published as a conference paper at ICLR 2024
Am1e-2
Am2e>2
A-2 A=2.5e-2
Running time (logi5))
Running (logta))
Bunning time (lests))
Figure 11: Evaluations for running time w.r.t different S, where S J"
/ ((s)
(2(s) ds (or
cquivalently, Je VI+ (t)) dé) is the are length of Ω (-). We use Gamma regression on higgs dataset and the À is fixed (shown in sugfigure's ' title) in the inner-level problem solving.
Running Time (s)
Running Time
Rummn lime
20
Size feature set (5eed=5)
Size of feature set (seed=30)
Size of feature set (seed 5000
Figure 12: Comparisons of algorithmic efficiency. In experiments we keep the number of observations in X X* and X- well as the random seed, while alternating the size of m. Other settings are the same in the T
F.4.1 SPARSE GAMMA REGRESSION
The Gamma distribution is frequently used to model waiting times. For instance, in life testing, the waiting time until death is a random variable that is frequently modeled with gamma distribution (Mittböckk & Heinzl 2002). Similar to Poisson regression, minimize the gamma deviance (Prentice 1974) in regression as
exp (8xx))
y/
min SER
log
+ 1|
(65)
V/
exp
x;)
The numerical results obtained from applying SAGO to (65) are elucidated in Table A comparative analysis of execution times against various baseline methods can be found in Figure
160
180
Auver age Runnning Timals)
Warmayo
Warmbyc
SAGD
SAGO
80
80
60000
120000
180000
240000
300000
60000
120000
180000
240000
300000
Size of Dataset
Size of Dataset
Figure 13: Comparative analysis of algorithmic efficiency. The subfigures the left and right are sparse GLMs mentioned Appendix F.4.T and Appendix R.4.2 respectively. This figure plotted using ACSIncome dataset.
35

---

Published as a conference paper at ICLR 2024
Table Numerical results for validation loss with standard deviation. The best results are shown in bold. We conduct comparative experiments in the same environment and setting as in the main paper.
Method
ACSIncome
Buzzinsocialmedia
fried
house 16H
Round #1
ColdGrid
296.0 = 0.45
17.59 + 0.59
9.260 + 0.52
34.22 + 0.81
ColdHyBi
295.0 + 0.31
17.40 0.61
9.489 0.27
34.23 1 0.54
ColdByo
295.3 = 0.34
17.18 + 0.45
9.224 + 0.34
33.05 + 0.47
SAGO
294.4 + 0.19
16.04 + 0.09
9.007 + 0.11
32.96 + 0.21
Round #2
ColdGrid
295.6 0.15
18.55 + 0.68
8.511 + 0.45
34.23 - 0.85
ColdHyBi
294.9 = 0.30
16.98 + 0.86
8.774 = 0.27
33.66 + 0.23
ColdBy0
295.7 1 0.18
16.84 1 0.14
8.974 1 0.79
33.74 1 0.65
SAGO
293.1 + 0.21
16.79 + 0.14
8,460 + 0.12
33.66 + 0.07
Round #3
WarmGrid
295.7 + 0.73
17.55 + 0.57
9.571 + 0.37
34.92 + 0.61
WarmHyBi
295.8 = 0.69
18.86 + 0.56
9.126 + 0.40
35.96 - 0.94
WarmByo
294.5 0.52
17.51 + 0.49
8.874 = 0.38
34.98 = 0.44
SAGO
293.7 +
16.26 0.17
8.843 0.14
34.86 0.09
F.4.2 SPARSE INVERSE GAUSSIAN GLM
Inverse Gaussian GLM GGiner & Smyth, 2016) considers models for positive continuous data. Variables that take positive and continuous values often measure the amount of some physical quantity that is always present (Amin et al. (016). We minimize the inverse Gaussian deviance as
(/:- eep (BT x2))
min BERm
+ A ||
(66)
y/ exp (8 xx)
The numerical results of SAGO on (66) is displayed in Table A comparison of running times against various baselines can be found in Figure [3
Table 6: Numerical results for validation loss with standard deviation. The best results are shown in bold. We conduct comparative experiments in the same environment and setting in the main paper.
Method
ACSIncome
Buzzinsocialmedia
fried
house 16H
Round #1
ColdGrid
246.2 = 0.63
37.79 + 0.33
6.608 + 0.32
21.22 + 0.88
ColdHyBi
244.5 = 0.45
36.70 + 0.29
6.385 = 0.44
19.87 = 0.76
ColdBy0
244.9 1 0.67
37.03 1 0.88
6.208 1 0.14
19.74 0.12
SAGO
243.1 + 0.59
36.07 + 0.17
6.176 + 0.12
19.73 + 0.05
Round #2
ColdGrid
246.8 + 0.76
35.98 + 0.69
6.994 + 0.92
19.81 + 0.68
ColdHyBi
247.5 0.38
35.59 + 0.61
6.779 0.72
19.88 + 0.18
ColdByo
246.7 = U.47
35.52 + 0.53
6.860 + 0.74
19.92 + 0.67
SAGO
245.8 + 0.35
35.40 + 0.13
6.773 0.14
19.72 + 0.24
Round #3
WarmGrid
246.8 0.32
36.13 + 0.31
6.895 0.18
20.74 0.57
WarmilyBi
247.5 = 0.96
36.51 + 0.57
6.795 + 0.13
22.68 + 0.35
WarmByo
246.7 + 0.85
35.60 + 0.79
6.878 1 0.53
20.34 1 0.42 0.42
SAGO
245.8 + 0.41
35.60 + 0.11
6.693 + 0.18
20.26 + 0.39
F.5 ON THE NON-LINEAR PATTERN
As delineated Remark B our approach is adept at handling (some) non-lineat patterns. To illustrate it empirically, consider the utilization of random Fourier features.
Given any thift-invariant kernel like the Gaussian kernel, characterized by k(x, y) = k(x - y). Rahimi & Recht (007)) introduced comprehensive decomposition approach employing Fourier basis
36

---

Published as a conference paper at ICLR 2024
functions { (x:) 2 cos (w" x; + +b weee.. This allows for the identification of its associated feature mapping. In practical terms, is sampled from p(w) and b uniformly drawn from the interval [0, 2 Notably, the probability distribution p(w), when affiliated with the Gaussian kernel, corresponds to normal distribution, connection further elaborated in Rahimi Recht (2007).
In our experiment configuration, the parameter of the RBF kernel is designated as 2, and the random seed is initialized to 100. We map the native input features into feature space comprising 200 dimensions. The numerical results of SAGO is displayed in Table 7
Table 7: Non-linear accuracy results for validation loss with standard deviation. The best results are shown in bold. We conduct comparative experiments in the same environment setting as in the main paper, well as the GLMs for each specific dataset.
Method
ACSIncome
Buzzinsocialmedia
fried
house 16H
Round #1
ColdGrid
234.9 L 0.51
46.55 0.68
0.40
0.76
ColdiyBni
236.7 = 0.52
48.04 + 0.86
3.438 + 0.84
24.93 + 0.62
ColdByO
236.2 + 0.41
45.79 1 0.96
3.017 1 0.24
24.77 + 0.19
SAGO
234.8 + 0.27
44.28 + 0.14
2.728 + 0.13
24.59 + 0.17
Round #2
ColdGrid
237.0 + 0.53
46.07 +: 0.57
3.046 +: 0.72
26.21 + 0.65
ColdHyBi
236.9 +: 0.63
41.98 +: 0.38
3.175 +: 0.58
25.94 +: 0.64
ColdByo
235.7 = 0.69
41.16 + 0.59
2.892 + 0.02
26.09 = 0.89
SAGO
235.3 + 0.18
40.35 + 0.21
2.892 + 0.12
25.53 + 0.27
Round #3
WarmGrid
233.3 = 0.70
40.68 + 0.42
3.419 +: 0.69
25.32 1 0.58
Wa WarmHyRi
237.7 + 0.96
40. + 0.25
3.227 + 0.40
25.21
+ 0.63
NarmByO
235.3 0.82
38.96 + 0.70
2.567 + 0.62
26.33
0.39
SAGO
233.1 + 0.38
38.87
2.259 0.53
24.11 0.22
37


Reviews:
[{"review_id": "OGAv9TfXu2", "reviewer": "Reviewer_oT9i", "summary": "In this work, authors study GLMs with varying observations. Specifically, they develop an algorithm that can train optimal GLMs by only considering newly added (and removed) data points. This alleviates the need to train the entire model from scratch by only focusing on varied observations. They provide theoretical guarantees for their claim and conduct empirical studies to validate their theoretical contributions. Their algorithm outperforms the baselines in the numerical experiments.", "questions": "How easy is it to optimally solve the PDE-ODE procedure in both inner and outer problems? Are there existing solvers that solve them optimally with provable convergence guarantees and what are their computational/sample complexities? These can be answered for the models used in empirical study, i.e., for Sparse Poisson Regression and Logistic Group Lasso.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "I am not an expert in this specific research area, and it's important to take my opinions into consideration with that in mind.\n\nThe paper is well-written and presented. The theoretical results seem sound and the approach seems novel. As I perceive it, the introduction of the proposed bilevel optimization, coupled with the utilization of ordinary differential equations (ODEs) and partial differential equations (PDEs) to address these problems, represents a novel and inventive approach. While I have not conducted an exhaustive review of the mathematical details presented in the supplementary material, the findings in the main paper hold promise.", "weaknesses": "Please see questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "CyzSFIwBqG", "reviewer": "Reviewer_MPDs", "summary": "An online updating algorithm SAGO for generalized linear models based on solving ODE-PDE systems was proposed. It is proved that the algorithm has no regret. The merit of the SAGO is empirically tested  by comparing with ColdGrid (WarmGrid), ColdHyBi (WarmHyBi) and ColdByO (WarmByO). Improved accuracy was observed in numerical experiments.", "questions": "1. Comparing with existing methods ColdGrid, ColdHyBi, ColdByO:\n\n(a) It would be good to present the computational time SAGO and benchmark with the existing methods\n\n(b) Comparing the active sets f => do the methods agree on which ones are active?\n\n2. Minor: above Eq. (2), it should probably be $\\Sigma_{\\{i|({\\bf x_i}, y_i) \\in X^\\diamond\\}}$ in the definition of $\\ell^{\\diamond}$. Same applies to $\\ell^{-}$ and $\\ell^{+}$.\n\n3. In Algorithm 1, line 16-19: the thresholding condition is based on Lemma 1, which seems to only apply on $\\ell_1$ penalty. However, it is claimed that Algorithm 1 applies to penalties satisfying Assumption 1. There seems to be a gap and I wonder how the thresholding condition can be generalized to a wider class of penalty functions\n\n4. It's unclear how a coefficient can become active from inactive in SAGO in Algorithm 1, i.e. E1 on line 18-19. \n\n(a) The ODE in Eq. (5) describe the dynamics of coefficients in \"active\" set, so solving (5) doesn't seem to provide an update for the coefficients in inactive sets?\n\n(b) When applying the thresholding condition, should one replace the $L$ in Lemma 1 by the validation loss $\\mathcal L_{val}$? To make things concrete, probably it's better to repeat explicitly the thresholding condition in line 18-19.\n\n5. Minor: line 25 of Algorithm 1: should probably be arg zero.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ Careful theoretical development", "weaknesses": "- The proposed algorithm seems to require high computational resources, e.g. memory, making it incompetent with existing algorithms\n- Dimension of the datasets selected for empirical studies are relatively large, but are low in model dimension. It is unclear whether the proposed SAGO algorithm can handle modern datasets of interest", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "RaPKmTg6TQ", "reviewer": "Reviewer_244k", "summary": "This paper analyzes learning a generalized linear model in online scenarios. The paper proposes an algorithm and analyzes the performance, path of optimizer and regret. Specifically, this paper analyzes the action of adding and eliminating some data by an ODE, and the based on the KKT condition, it proposes the path of optimizer given by the implementation of the proposed algorithm. At the end the empirical study validates the algorithm.\n\nUpdate:\n\nThanks for the authors' comment. It makes sense to me, I raised the score to 8.", "questions": "Lemma 3, eq 27, Why is there a minus sign in the second equation? However the proof below from eq 28 is correct.\n\nIn Assumption 1, shall the last assumption be there? If the function is symmetric about zero and has the first two derivatives, then the first derivative at zero must be 0, otherwise at the point 0 there is only subgradient but no gradient. However the examples, such as $\\ell_1$ norm, or the regularizers that encourage sparsity, are all non-smooth at 0, or, if you take out the absolute value thus it is linear, then it is not symmetric about 0, but instead $f(x) = -f(-x)$ right?\n\nAlgo 1, line 5, what does “solve” mean? Solve the whole trajectory of $\\hat \\beta$?\n\nPage 4 and later, I'm a bit confused about the set definitions and the elements in sets. For example, are $S_1,...,S_d$ elements of $S$, or $S = S_1 \\cup ... \\cup S_d$, is it consistent with the definition of $S_{\\bar Z}$ which says $j\\in S$? \n\n\"Formal statements ... in Appendix B.1\", what if place the formal theorem and proof sketch in main body and the detailed proof in appendix?\n\nShould Thm 2. be called continuity or Lipschitz?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The algorithm is correct and concrete in maths, and the technique that treats the discrete actions of adding and removing data in a continuous space is normal and inspiring. It proposes a mathematical sound and practical algorithm and gives thorough analysis of the algorithm.", "weaknesses": "I do appreciate the discussion of the path of the optimizer in both inner loop and outer loop, but I'm still a little bit confused about how the notion of “no-regret” takes place, I would like to see more discussion about the final claim that can highlight the importance of the result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (spotlight)