Non-Convex Bilevel Optimization with Time-Varying Objective Functions
Authors: Sen Lin
Daouda Sow
Kaiyi Ji
Yingbin Liang
Ness Shroff
Venue: NeurIPS 2023 poster (2023)
Keywords: Bilevel Optimization
Time-Varying Functions
Single-Loop
Sublinear Bilevel Local Regret
TL;DR: We propose an efficient and practical single-loop algorithm for nonconvex bilevel optimization under time-varying objective functions with novel theoretical analysis

Abstract: Bilevel optimization has become a powerful tool in a wide variety of machine learning problems. However, the current nonconvex bilevel optimization considers an offline dataset and static functions, which may not work well in emerging online applications with streaming data and time-varying functions. In this work, we study online bilevel optimization (OBO) where the functions can be time-varying and the agent continuously updates the decisions with online streaming data. To deal with the function variations and the unavailability of the true hypergradients in OBO, we propose a single-loop online bilevel optimizer with window averaging (SOBOW), which updates the outer-level decision based on a window average of the most recent hypergradient estimations stored in the memory. Compared to existing algorithms, SOBOW is computationally efficient and does not need to know previous functions. To handle the unique technical difficulties rooted in single-loop update and function variations for OBO, we develop a novel analytical technique that disentangles the complex couplings between decision variables, and carefully controls the hypergradient estimation error. We show that SOBOW can achieve a sublinear bilevel local regret under mild conditions. Extensive experiments across multiple domains corroborate the effectiveness of SOBOW.

Non-Convex Bilevel Optimization with Time- Sone-Varying Objective Functions
Sen Lin" Department of CS University of Houston sl ini50@central... uh. edu
Daouda Sow Department of ECE The Ohio State University
530os5..0seee edu
Kaiyi Ji Department of CSE University at Buffalo kaiyiji@buffalo. edu
Yingbin Liang Department of ECE The Ohio State University 1 1iang8898osu.c edu
Ness Shroff Department ECE & CSE The Ohio State University shroff. 110osuu. edu
Abstract
Bilevel optimization has become powerful tool in wide variety of machine learning problems. However, the current nonconvex bilevel optimization considers offline dataset and static functions, which may not work well in emerging online applications with streaming data and tine-vryying functions. In this work, we study online bilevel optimization (OBO) where the functions can be time-varying and the agent continuously updates the decisions with online streaming data. To deal with the function variations and the unavailability of the true hypergradients in OBO, we propose single-loop online bilevel optimizer with window averaging (SOBOW), which updates the outer-level decision based on window average of the most recent hypergradient estimations stored in the memory. Compared existing algorithms, SOBOW is computationally efficient and does need to know previous functions. To handle the unique technical difficulties rooted single-loop update and function variations for OBO, we develop novel analytical technique that disentangles the complex couplings between decision variables. and carefully controls the hypergradient estimation error. We show that SOBOW can achieve a sublinear bilevel local regret under mild conditions. Extensive experiments across multiple domains corroborate the effectiveness of SOBOW.
Introduction
Bilevel optimization has attracted significant recent attention, which in general studies the following problem:
min f(x,2(())) s.t. (²(x) arg min g( v)- xER4]
(1)
veRds
Here both the outer-level function f and the inner-level function g are continuously differentiable. and the outer optimization problem is solved subject to the optimality of the inner problem. Due to its capability of capturing hierarchical structures many machine learning problems, this nested optimization framework has been exploited in a wide variety of applications, e.g., meta-learning and neural architecture
31. hyperparameter optimization
reinforcement learning 62 57
search 38 g).
However, numerous machine learning problems with hierarchical structures are online in nature, e.g.. online meta-learning [1 and online hyperparameter optimization [63] where the current bilevel
TThe work was done when Sen Lin was in The Ohio State University
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

optimization framework cannot be directly applied due to the following reasons: (1) (streaming data) The nature of online streaming data requires decision making on-the-fly with low regret, whereas the offline framework emphasizes more on the quality of the final solution; (2) (time- varying functions) The objective functions in online applications can be time-varying because of non-stationary environments and changing tasks, in contrast to static functions considered in Equation (T) (3) (limited information) The online learning is nontrivial when the decision maker only has limited information, e.g., regarding the inner-level function, which can be even more challenging with time- vvrring functions. For example, in wireless network control [37] the controller has to operate under limited knowledge about the time-varying wireless channels (see Appendix).
To reap the success of bilevel optimization in online applications, there is an urgent need to develop a new online bilevel optimization (OBO) framework. Generally speaking, OBO considers the scenario where the data comes an online manner and the agent continuously updates her outer-level decision based on the estimation of the optimal inner-level decision. Both outer-level and inner-level objective functions can be time-varying to capture the data distribution shifts in many online scenarios. Note that OBO is significantly different from single-level online optimization [22), due to the unavailability of the true outer-level objective function composed by f and y"
The study of OBO was recently initiated in [59], but much of this new framework still remains under-explored and not well understood. In particular, [59] combines offline bilevel optimization with online optimization and proposes an online alternating time-averaged gradient method. Such an approach suffers from several limitations: 1) Multi-step update required for inner-level decision variable ye at each time i, which can be problematic when only limited information of the inner-level function g is available. 2) The hypergradient estimation at each time requires the knowledge of previous objective functions in window, and also evaluates current models on each previous function; such a design can be inefficient and infeasible in online scenarios. In this work, we seek to address these limitations and develop a new OBO algorithm that can work efficiently without the knowledge of previous objective functions.
Table Comparison of OBO algorithms. 'HV' product refers to the Hessian inverse-vector product in hypergradient estimation. OAGD estimates the hypergradient by 1 K-1 1/ fi
W
which requires the evaluation of fr=; current model (zz, 114
Algorichm
Singlc-loop update
Study estimation error HV product
Do not require previous function info
OAGi
SOBOW (this paper)
The main contributions can be summarized as follows.
(Efficient algorithm design) We propose a new single-loop online bilevel optimizer with window averaging (SOBOW), which works in a fully online manner with limited information about the objective functions. In contrast the OAGD algorithm (59]. SOBOW has the following major differences (as summarized in Table I: (1) (single-loop update) Compared to the multi-step updates of the inner-level decision Yt at each round in OAGD, we only require a one-step update of yr, which is more practical for online applications where only limited information about the inner-level function St is available. (2) (estimation error of Hessian inverse-vector product) Estimating the hypergradient requires the outer-level Hessian inverse-vecte product. [59] assumes that the exact Hessian inverse- vector product can be obtained, which can introduce high computational cost. In contrast, we consider more practical scenario where there could be an estimation error in the Hessian-inverse vector product calculation in solving the linear system. (3) (window averaged hypergradient descent) While window averaged hypergradient estimation is considered in both OAGD and SOBOW, SOBOW is more realistic and efficient than OAGD. Specifically, OAGD requires the knowledge of the most recent objective functions within a window and evaluates the current model on each previous function at every round, whereas SOBOW only stores the historical hypergradient estimation in the memory without any additional knowledge or evaluations about previous functions.
(Novel regret analysis) Based on the previous studies in single-level online non-convex optimization 23 22, we introduce a new bilevel local regret as the performance measure of OBO algorithms. We show that the proposed SOBOW algorithm can achieve a sublinear bilevel local regret under mild conditions. Compared to offline bilevel optimization and OAGD, new technical challenges need to be addressed here: (1) unlike the multi-step update of inner-level variable y/ in OAGD, the single-step update in SOBOW will lead to inaccurate estimation of the optimal inver-level

---

decision 3/" (zt) and consequently a large estimation enror for the hypergradient; this problem can be addressed in offline bilevel optimization by controlling the gap 1137 (z+) 4 (1+++1) )l? which depends only on ||x - x l? for static inner-level functions. But this technique cannot be applied here due to the time-varying 9t: (2) the function variations in OBO can blow up the impact of the hypergradient estimation error if not handled appropriately, whereas offline bilevel optimization does not have this issue due to the static functions therein. Towards this end, we appropriately control the estimation error of the Hessian inverse- vector product at each round, and disentangle the complex couplings between the decision variables through three-level analysis. This enables the control of the hypergradient estimation error, by using a decaying coefficient to diminish the impact of the large inner-level estimation error and leveraging the historical information to smooth the update of the outer-level decision.
(Extensive experimental evaluations) OBO has the potential to be used in various online applications, by capturing the hierarchical structures therein in an online manner. In this work, the experimental results clearly validate the effectiveness of SOBOW in online hyperparameter optimization and online hyper-representation learning.
2 Related Work
Online optimization Online optimization has been extensively studied for strongly convex and convex
functions in terms of both static regret, e.g., [68 21 47 and dynamic regret, e.g., 55] 48 64 66].
Recently, there has been increasing interest in studying online optimization for non-convex functions, e.g..
15), where minimizing the standard definitions of regret is computationally
intractable. Specifically, (23] introduced notion of local regret in the spirit of the optimality measure in non-convex optimization, and developed an algorithm that averages the gradients of the most recent loss functions evaluated in the current model. [2] proposed dynamic local regret to handle the distribution shift and also a computationally efficient SGD update for achieving sublinear regret. [24] and (25] studied the zeroth-orde online non-convex optimization where the agent only has access to the actual loss incurred at each round.
Offline bilevel optimization Bilevel optimization was first introduced in the seminal work [ Following this work, a number of algorithms have been developed to solve the bilevel optimization problem. Initially, the bilevel problem was reformulated into a single-level constrained problem based
on the optimality conditions of the inner-level problem [20 55 43 49], which typically involves many constraints and is difficult to implement in machine learning problems. Recently, gradient- based bilevel optimization algorithms have attracted much attention due to their simplicity and efficiency. These can be roughly classified into two categories, the approximate implicit diffcrentiation (AID) based approach
42 32 and the iterative differentiation (ITD) based approach 177. Bilevel optimization has also been studied very recently for the cases with
[00 52 16
14
17
45 12 53
33 [8] and multiple inner minima [35] 40, 39 [56]. Notably, novel value-function based method was first proposed in 33 to deal with the non-convexity of the inner-level functions. Some recent studies, e.g., [36 9 26) have also explored single-level algorithms for offline bilevel optimization with time-invariant objective functions, whereas the time- varying functions in online bilevel optimization make the hypergradient estimation error control more challenging for single-loop updates.
stochastic objective functions <
Online bilevel optimization The investigation of OBO is still in the very early stage, and to the best of our knowledge, [59 is the only work so far that has studied OBO.
3 Online Bilevel Optimization
Following the same spirit as the online optimization in (22). the decisions are made iteratively in OBO without knowing their outcomes at the time of decision-making Let 7' denote the total number of rounds in OBO. Define x, E X C Rd and fa X' x d as the decision variable and the online function for the outer level problem, respectively. Define yt R and gi X' x Rd2 as the decision variable and the online objective function for the inner level problem, respectively. Given the initial values of (1), the general procedure of OBO is described in Algorithm
Let y (x) = arg min (x, y) for any x. The OBO framework in Algorithm 1 can be interpreted from two different perspectives: (1) (single-player) The player makes the decision on I, without
3

---

Algorithm 1 General procedure of OBO
1: Initialize decisions I1 and y/1
2: for = 1.... T do
3: Get information about functions fa and ge
4: Update decision ye+11 based on 24 and gr
5: Update decision 1 based U 1 and
6:
end for
knowing the optimal inner-level decision Vi (ar). Note, yt serves as an estimation of y? (a:) from the player's perspective based on her knowledge of function gr: (2) (two-player) OBO can also be viewed as leader (x2) and follower (ya) game, where each player considers an online optimization problem and the leader seeks to play against the optimal decision y (x) of the follower at each round under limited knowledge of gr-
is worthwhile noting that OBO is quite different from the single-level online optimization. First, the outer-level objective function with respect to (w.I.)) Zt, i.e., (I MI (x1)), is not available to update It, whereas, in standard single-level online optimization, the true loss is revealed immediately after making decisions. Besides, composite function of f((1,, y) and yf (z), fc yf (z)) is non-convex in general w.r.t. the outer-level decision variable æ. Hence, standard regret definitions in online convex optimization [22 are not directly applicable here.
Motivated by the dynamic local regret defined in online non-convex optimization 22) consider the following bilevel local regret:
BLR Ex=
| (f (=+))l*
1=1
where
W Σ K-1
Fin vi (xx))
of fi ((m
and W E n/, E (), and fe(..) 0 for t S O. In contrast, the static regret in [59] evaluates the objective at time slot using variable updates at different time slot j. which does not properly characterize the online learning performance of the model update for time-varying functions
(see Appendix for more discussion). Intuitively, the regret in Equation (2) is defined as a sliding average of the hypergradients w.r.t. the decision variables at the corresponding instant for all rounds in
OBO. This indeed approximately computes the exponential average of the outer-level function values fe Vr (ax)) at the corresponding decision variables over sliding window 22. Larger weights will be assigned to more recent updates. The objective here is to design efficient OBO algorithms with sublinear bilevel regret BL (T) in T, which implies that the outer-level decision is becoming better and closer to the local optima for the outer-level optimization problem at each round. This gradient-nen more based regret shares the same spirit as the first-order optimality criterion 14 32), which is widely used in offline bilevel optimization to characterize the convergence to the local optima.
Algorithm Design
It is well known that online gradient descent (OGD) 54 has achieved great successes in single- level online optimization. On the other hand, gradient- based methods (e.g., [16] 14 42 29 have become extremely popular for solving offline bilevel optimization due to their high efficiency. Thus, we also study the online gradient descent based algorithm to solve the OBO problem. As mentioned earlier, the unique challenges of OBO should be carefully handled in the algorithm design, including 1) the inaccessibility of the objective function and accurate hypergradients compared to single-level online optimization and 2) the come-varying functions and limited information compared to offline bilevel optimization. To this end, our algorithm includes two major designs, i.c., efficient hypergradient estimation with limited information and window averaged outer-level decision update.
Hypergradient estimation In OBO, the exact hypergradient V Ve yi (xx)) w.r.t. Ty can be represented as
V. vi (rx)) = Vale vi (z.)) V. Vaga wi (zr))o
(3)
where of solves the linear system Viyn Vi (x)))x= Vyfi vi (ax)). The optimal inner-level decision yf (zx) is generally unavailable in OBO. To estimate the hypergradient V fe vi (xx)).

---

the AlD-based approach [10 [4 32 for offline bilevel optimization can be leveraged here, which will involve the following steps: (1) given 2t. run N steps of gradient descent w.r.t the inner-level objective function It. to find good approximation vi" close to yi (at); (2) given vy" obtain og
by solving Vi (Ze, vi yyu (xf((xx,1()) with Q: steps of conjugate gradient. The estimated hypergradient is constructed as
fi(z, =V -V VaV Jo
(4)
Nevertheless, the N steps gradient descent for estimating y (I²) require multiple inquiries about the inner-level function Jt, which can be inefficient and infeasible for online applications. For the algorithm being used in more practical scenarios with limited information about Jt. we consider the extreme case where N i.e.,
(5) where a is the inner-level step size. This would lead an inaccurate estimation of yr (zz), which can pose critical challenges for making satisfying outer-level decisions in OBO due to the unreliable hypergradient estimation, especially when the objective functions are amee-aaying.
Vc+1 y = y+ - V agge (e). Wt).
Window averaged decision update
deal with the non-convex and time-varying functions,
inspired by smoe-h gradient descent in online non-conver optimization [23 2, [9], we
consider a time-smoothed hypergradient descent for updating the outer-level decision variable 2;:
F1+1 1Ix(x; FVF v1+1))
(6)
where IIx the projection onto the set X, B is the outer-level step size and
V FL. 8441)
Σ ny 30 W
1
(7)
Here ( Ut+ is the hypergradient estimation at the round /. - i, as in Equation (4 Intuitively, the update of the current ze smoothed by the historical hypergradient estimations
w.r.t. the decision variables at that time, which is particularly important here for OBO due to the following reasons: (1) To compute the averaged Ft.,, (Ze. V2++1) at each round we only store the hypergradient estimation for previous rounds in the memory, i.c., store V (I 3/+1) at each round i, and estimate the current hypergradient f (Zt, 3/+11 using the available information at current round Compared to OAGD in [59], there no need access to the previous outer-level and inner-level objective functions and evaluate the current decisions on those functions, which is clearly more efficient and practical for online applications. (2) Leveraging the historical information in the window to update the current decision is helpful to deal with the inaccurate hypergradient estimation for the current round, especially under mild function variations. This indeed shares the same rationale with using past tasks to facilitate forward knowledge transfer in online meta-learning [I]] and continual learning [1], for better decision making in the current task and improving the overall performance in non-stationary environments.
Building upon these two major components, we can have our main OBO algorithm, Single-loop Online Bilevel Optimizer with Window averaging (SOBOW), as summarized in Algorithm 2 At the round t, we first estimate 3t-1 as in Equation ( given x; and ye. which will be next leveraged to solve the linear system and construct the hypergradient estimation as in Equation ( Based on the historical hypergradient estimations stored in the memory for previous rounds, we next update zt based on Equation (
5 Theoretical Analysis
In this section, we provide the theoretical analysis of the regret bound for SOBOW.
5.1 Technical Assumptions
Let = v). Before the regret analysis, we first make the following assumptions.
Assumption 5.1. The inner-level function ge ge( y) is Mo py-strongly convex w.r.t. y, and the composite objective function fe(2, y7 (z)) is non-convex w.r.t x.
Assumption 5.2. The following conditions hold for objective functions fe(z) and (x), VI. E [1, (1) The function fz(2) is Lop-hips continuous; (2) f((z)) and (ge(z) are L -ipShhhcii continuous; (3) The high-order derivatives V. V (z) and V (2) are Li-Lipschitz continuous.
5

---

Algorithm 2 Single-loop Online Bilevel Optimizer with Window averaging (SOBOW)
1: Initialize decisions IT, 1/. 00
2: for ( 1,... 7 do
3: Get information about functions ft and
4: Update Vt+1 based on Equation (5)
5: Solve the linear system (2 yc+1)u Vzfe M141) using Qe steps of conjugate
gradient starting from fixed point o with stepsize À to obtain of
6: Construct the hypergradient fa Mo+1) based on Equation
with y/ = 9t-1
7: Store V (a Mt+1) in the memory
8: Update Tt+1 based on Equation (6)
9:
end for
Note that both Assumption 5.1 and Assumption 5.2 are standard and widely used in the literature of bilevel optimization, e.g., [52]
59
27
Assumption 5.3. For any E [1, T7, the function fi y (z)) is bounded, i.e., (z, 37 (x)) | s M with M > 0. Besides, the closed convex set X' is bounded, i.e., || - x'| S D with D > 0. for any and x in X.
Assumption 5.3 on the boundedness of the objection functions is also standard in the literature
of non-convex optimization, e.g.. [23 2 50, [9]. Moreover, to guarantee the boundedness of the hypergradient estimation error, previous studies (c.g.. [14, 28 I7) in offline bilevel optimization usually assume that the gradient norm V (=)ll is bounded from above for all z. In this work, we make a weaker assumption on the feasibility of V y,fi(z, (zx yf (x:). which generally holds since ył (x) is usually assumed to be bounded in bilevel optimization:
Assumption 5.4. There exists least one X' such that || (f S where p is some constant.
5.2 Theoretical Results
Technical challenges in analysis: To analyze the regret performance of SOBOW, several key and unique technical challenges need to be addressed, compared to offline bilevel optimization and OAGD in [59 (1) unlike the multi-step update of inner-level variable ye in OAGD, the single-step stepl update in SOBOW will lead to an inaccurate estimation of y (az) and consequently large estimation error for the hypergradient fz V (xx));: this problem can be addressed offline bilevel optimization by controlling the gap |1 (zx) Vi+1 (x++1) 12, which depends only on ||xr Fz+ 1| for static inner-level functions, but this technique cannot be applied here due to the time-varying gri (2) the function variations in OBO can blow up the impact of the hypergradient estimation error if not handled appropriately, whereas offline bilevel optimization does not have this issuc due to the static functions therein; (3) among the estimation errors about Vt, z/ and x; in online learning.
three-level analysis is required to understand the involved couplings
Towards this end, the very first step is to understand the estimation error of the opti- mal solution oy to the linear system Vzge(re, yi (x:))u (Vzga(re (Ie, of
(a y7 (xx)). Here or (xx)). We have the following lemma about ||o 1l2 where of obtained by solving (ig B4+ ) V (I 1e+1) using Qe steps of conjugate gradient.
log 2.2
Lemma 5.5. Suppose Assumptions
5.7 5.4 hold. A S J.. a +. and Q++1 Qu 2
2log(1 X
We can have that
|| of calluc41 vi (x:))1² +
where 02 > 0 is some constant and the error of decays with I, i.e., e2t1 S (1-app//2)e
Lemma 5.5 characterizes the estimation error |/ of in a neat way, by constructing an upper bound with the estimation error of the inner-level optimal decision y/ (2x), i.c., || - yz (3x)) 12 and a decaying error term eg. The way of controlling || o 1|2 here is particularly important, which not only clarifies the coupling between V and y: but also helps to control the hypergradient estimation

---

error. Note that solving the linear system with larger Qr does not require more information about the inner-level function, and the introduced computation cost can be negligible, because the conjugate gradient only involves Hessian-vector product which can be efficiently computed.
Next we seek to bound the hypergradient estimation error V fe Vi (a:)) - fe f (2,, 30+1)) I|2 at the
round f. Intuitively, the hypergradient estimation error depends on both || - 2 (I2))l and ||e/
2i Building upon Lemma 5.5, this dependence can be shifted to the joint error of ll - yi (x+) and Ct which contains iteratively decreasing components after careful manipulations. Specifically, let
G1 = + C2 + 1o0, DI. DTAr))² and G2 = 2G1 (1 + a/t (1 offg). We have the following
2
Ling
theorem to characterize the hypergradient estimation error.
Theorem 5.6. Suppose that Assumptions 5. / 5.4 hold, X < t a E and Qi - Qi-1 2
Jog(1- - -22) 2log(1 - ) For E [2, we can bound the hypergradient estimation error as follows:
22i
1-2
[V (xx)) M(((), $LL.
{
Σ
(1-22)
[1
| - -xt-1l?
1=0
G2 Σ (1
) 11 (
vi ( + (1- apfs
(1-))1)) )
2 81
2
1=0
where 61 = Gi - v (x1 [211)]12 e
As shown in Theorem 5.6 the upper bound of the hypergradient estimation error includes three terms: (1) The first term decays with c, which captures the iteratively decreasing component in the joint error of [lv++1 V/ (z:) 112 and c: (2) The second term characterizes the dependence on the variation of the outer-level decision between adjacent rounds in the history; (3) The third term characterizes the dependence on the variation of the optimal inner-level decision between adjacent rounds.
To control the hypergradient estimation error as in Theorem 5.6 the key idea decouple the source of the estimation error |b++1 yd (z=))l at the current round into three different components, i.c., llve 1 (z ||2 for the previous round, the variation of the out-level decision, and the variation of the optimal inner-level decision. Since the inner-level estimation error is large due to the single-step update, we diminish its impact through a decaying coefficient, which inevitably enlarges the impact of the other two components. The variation of the optimal inner-level decision is due to nature of the OBO problem, which cannot be controlled. One has to impose some regularity constraints on this variation to achieve sublinear regret, in the same spirit to the regularities on functional variations widely used in the dynamic regret literature (e.g.. [5] (6)). Therefore, the key point now becomes the control of the variation of the out-level decision -zz1-jj Zz-5 112 which can be achieved through the window averaged update of x, in Equation (6. Intuitively, by leveraging the historical information, the window averaged hypergradient in Equation (7) smooths the outer-level decision update, which serves as a better update direction compared to the deviated single-round estimation A fe 11).). Before presenting the main result, we first introduce the following definitions to characterize the variations of the objective function fe( vt vt (-) in OBO, respectively:
vt)) (-)) and the optimal inner-level decision
T f((x, H = sup (ivi sup 3f (x))
Ví.T Σ suppfeti(
Σ 1=2
Intuitively, Vi,7 measures the overall fluctuations between the adjacent objective functions in all rounds under the same outer-level decision variable, and H2 can be regarded as the inner-level path length to capture the variation of the optimal inner-level decisions as in [59] Note that Vi,r is weaker regularity for the functional variation compared to absolute values used in single-level online optimization for dynamic regret S 66). When the functions are static, these variations terms are simply O. We are interested in the case where both Vi, and H2, are oT) as in the literature of dynamic regret.
Based on Theorem 5.6 we can have the following theorem to characterize the regret of SOBOW.
Theorem 5.7. Suppose that Assumptions 5.7 5.4 hold.
Let X < +.2 a +. Q++1
Qs >
Tog(1 2ug)
Blog(1 (1-App)) 1) E (1 042,1), and 8 < min AL," 24L|Gon
where I,g is the

---

smoothness parameter of the function ft(:; 97 (-)).
Then we can have
T
Vi.T
BLR. (T) S aW B
Ha.T
The value of f. can be found in the proof in Appendix. Note that the hypergradient estimation at the current round depends on all previous outer-level decisions as shown in Theorem [.6] While these decisions may not be good at the early stage in OBO, choosing 1 E (1 _ 1) would diminish their impact on the local regret. When the variations VT,T and H2,r are both (T)), a sublinear bilevel local regret can be achieved for appropriately selected window, e.g., W o(T) when 1j =1 h(T). where hT) - 0 as T + oc. Note that the value does not change substantially since W(1 - converges to 1. Particularly, when 7 -
- W = w(T). In this case, we can have the smallest
regret O ( V 3 + H2.r) that only depends on the function variations in OBO.
Experiments
In this section, we conduct experiments in multiple domains to corroborate the utility of the OBO framework and the effectiveness of SOBOW.
1.5
xx10**
X10*
BAGD 50 DED
5080 30
CAG2 50
1.0
0.75
Deghet
0G0
Regret
5003W 4
0.50
5003 9
Sannew M-11
Sonoi M-2
5085/N 0.08
500ONN Vw11
0.5
Roundss
1.0
1.5
Rounds
x10
0.0
0.5
Roundds
1.0
15
x10
0.00
2.5
Rmunds
1.3
K16
(a) static setup
(b) dynamic setup
(c) impact of 17
(d) impact of N
Figure 1: Evaluation for online HR. As shown in subfigures (a) and (b), SOBOW performs similarly to OAGD and significantly outperforms OGD in both static and dynamic setups. Subfigure (c) shows the performance of SOBOW under different values of the averaging parameter 1 for online HR. Better performance is achieved as + 1. Subfigure (d) shows the performance of SOBOW under different values of inner steps N when the data stream contains two data points (one in X and one in x! The performance saturates N = 2.
Specifically, we compare our algorithm SOBOW with the following baseline methods: (1) OAGD [59]. which is the only method for OBO in the literature; (2) OGD, a natural method which updates the outer-level decision by using the current hypergradient estimation only without any window averaging. Intuitively, OGD is not only a special case of OAGD when the information of previous functions is not available, but also a direct application of offline bilevel optimization, e.g., AID-based as SOBOW and OAGD with window size K,
method 32 We also denote SOBOW-K/OAGD. respectively. And we evaluate the regret using the definition in Equation ( We also compare the performance using the regret in [59 in Appendix where similar results can be observed.
Online Hy ixpeerrepressnntaiion Learning Representation learning 13 1 seeks to extract good representations of the data. The learnt representation mapping can be used in downstream tasks to facilitate the learning of task specific model parameters. This formulation is typically encountered in a multi-task setup, where A captures the common representation extracted for multiple tasks and defines the task-specific model parameters. When the data/task arrives in online manner, the hyper-representation needs to be continuously adapted to incorporate the new knowledge.
Following 17 we study online hyper-reprresentation learning (Online HR) with linear models. Specifically, at each round t, the agent applics the hyper-representation A, E Rexd and the linear model prediction we E IRd, and then receives small minibatches (X(,Y;)) and (X,, Y!9). Based on A, and (X2, Y?"), the agent updates her linear model prediction W/++ an estimation of w" (A,) arg minwerd ge( [A,, w) = | A,w - -:91 7 ||0||2 122 Based on the estimation W++11 and (X/, Y;"). the agent further updates her decision A4+1 about the hyper-representation to minimize the loss fA, w, (A)) |xx Aw; (A) - 112 In experiments,
consider synthetic data generated as in [77] and explore two distinct settings: (i) a static setup where the underlying model generating the minibatches is fixed; and (ii) staged dynamic setup where the model changes after some steps.
As shown in Figure I(a) and Figure [(b) SOBOW achieves comparable regret with OAGD both static and dynamic setups, without the need of knowing previous functions. In terms of the running
8

---

Table 2: Left:: Comparison for static online HO. We report accuracy and loss separate test split after 12000 steps. Right: Comparison for dynamic online HO. We report accuracy on a separate test split at the end of stream with corruption level 20% and 30%. Each level lasts for 4000 steps.
Method
Accuracy (%)
Test Loss
Time (8)
4
65.87
1.287
899
Method
End 20% stream
End 30% stream
Time
OAGD-4
65.96
1.285
2304
SOBOW44
58.39
59.70
T19
SOBOW-50
66.32
1.28
1188
OAGD-4
62.61
59.26
3072
OAGI-50
66.44
1.273
20161
time for 5000 steps with K = 50, SOBOW takes 1l seconds, OAGD takes 228 seconds and OGD takes 7 seconds. Therefore, SOBOW is much more computationally efficient compared to OAGD, because SOBOW does not need to re-evaluate the previous functions on the current model at each round. On the other hand, SOBOW performs substantially better than OGD (i.e.. OAGD when previous functions are not available) with similar running time. These results not only demonstrate the usefulness of SOBOW when the previous functions are not available, but also corroborate the benefit of window-averen averaged outer-level decision update by leveraging the historical hypergradient estimations in OBO. Figure [[c] shows the performance of SOBOW under different values of the averaging parameter 77. The performance is better as 1 + 1, which is also consistent with our theoretical results. Figure I(d) indicates that a small number of updates for the inner-level variable is indeed enough for online HR.
Online Hyperparameter Optimization The goal of hyperparameter optimization (HO) [3 is to search for the best values of hyperparameters A, which seeks to minimize the validation loss of the learnt model parameters w and is usually done offline. However, in online applications where the data distribution can dynamically change, e.g., the unusual traffic patterns in online traffic time series prediction problem (3). keeping the hyperparameters static could lead to sub-optimal performance. Therefore, the hyperparameters should be continuously updated together with the model parameters in an online manner.
Specifically, at each online round t, the agent applies the hyperparameters X and the model wy, and then receives a small dataset Dr- = {Dir, Dial] composed of a training subset Dj and a validation subset Draal Based on X and DiF, the agent first updates her model prediction u1++1 as an estimation of w (Ax) == arg min, C, (X,, w:), where L (X, w) == [िo EcEDt L(w; () + 52(A, w). L(w, () a cost function computed on data point Ç with prediction model w, and (ww, X) is a regularizer. Based on the model prediction W[+1 and DIr the agent updates the hyperparameters A4+1 to minimize the validation loss L)al (A, w (A)) = | ΣςED!" L (wi E)
We consider an online classification setting on the 20 Newsgroup dataset, where the classifier is modeled by an affine transformation and we use the cross-entropy loss the losscost function. For (AA, w). we use one fz-regularization parameter for each row of the transformation matrix in w, so that we have one regularization parameter for each data feature (i.e., |^] given by the dimension of the data). We remove all news headers in the 20 Newsgroup dataset and pre- pre-process the dataset so as to have data feature vectors of dimension d 99238. In our implementations, we approximate the hypergradient using implicit differentiation with the fixed point method [17]. We consider two different setups: (i) a static setup where the agent receives a stream of clean data batches (D:):: (ii) a dynamic setting in which the agent receives a stream of corrupted batches {Dr Jt. where the corruption level changes after some time steps. For both setups the batchsize is fixed to 16. For the dynamic setting we consider four different corruption levels 15%, 10%, 20%, 30%} and also optimize the learning rate as an additional hyperparameter.
We evaluate the testing accuracy for SOBOW and OAGD in Table for both static (Left) and dynamic (Right) setups. It can seen that compared to OAGD. SOBOW achieves similar accuracy but with a much shorter running time. When the window size increases in Table performance of both SOBOW and OAGD increases and the computational advantage of SOBOW becomes more significant. In particular, SOBOW runs around 20 times faster than OAGD when the window size is 50.
7 Conclusions and Discussion
In this work, we study non-convex bilevel optimization where the functions can be time-varying and the agent continuously updates the decisions with online streaming data. We proposed single-loop

---

online bilevel optimizer with window averaging (SOBOW) to handle the function variations and the unavailability of the true hypergradients in OBO. Compared to existing algorithms. SOBOW is computationally efficient and does not require previous function information. We next developed a novel analytical technique to tackle the unique challenges in OBO and showed that SOBOW can achieve sublinear bilevel local regret. Extensive experiments, justified the effectiveness of SOBOW. We also discuss the potential applications of the OBO framework in online meta-learning and online adversarial training (see Appendix).
Limitation and future directions
The study of online bilevel optimization is still in very early stage, and much of this new framework still remains under-explored and not well understood. We started with the second-order approach for hypergradient estimation, which is less scalable. One future direction is to leverage the recently developed first order approaches for hypergradient estimation. Another limitation is that we assume that the inner-level objective function is strongly convex. In the future, we will investigate the convex and even non-convex case.
Acknowledgments
This work has been supported in part by NSF grants NSF AT Institute (AI-EDGE) CNS-2112471, CNS-2106933, CNS-2106932, CNS-2312836, CNS-1955536 CNS-1901057, ECCS-111866 DMS- 2134145, and 231 1274, by Army Research Office under Grant W91 INF-211-114 and was spon- sored by the Army Research Laboratory and was accomplished under Cooperative Agreement Number W91 1NF-23---222 The views and conclusions contained in this document are those of the authors and should not be interpreted representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Govermment. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
References
[1] Naman Agarwal, Alon Gonen, and Elad Hazan. Learning in non-convex games with an optimization oracle. In Conference on Learning Theory, pages 18-29. PMLR, 2019.
[2] Sergul Aydore, Tianhao Zhu, and Dean P Foster. Dynamic local regret for non-convex online forecasting. Advances in neural information processing systems, 32, 2019.
[3] Fan Bao, Guoqiang Wu, Chongxuan Li, Jun Zhu, and Bo Zhang. Stability and generalization of bilevel programming in hyperparameter optimization. Advances in Neural Information Processing Systems, 1144529-4544 2021.
[4] Luca Bertinetto, Joao F Henriques, Philip Torr, and Andrea Vedaldi. Meta-leariigg with differentiable closed-form solvers. In International Conference on Learning Representations, 2018.
[5] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Opera- tions research, 63(5):1227-1222 1244, 2015.
[6] Jerome Bracken and James McGill. Mathematical programs with optimization problems in the constraints. Operations Research, 21(1):37-44, 1973.
[7] Tianyi Chen, Yuejiao Sun, and Wotao Yin. A single- sineee-e stochastic bilevel optimization method. arXiv preprint arXiv:2102.04677 046771 2021.
[8] Jiequan Cui, Pengguang Chen, Ruiyu Li, Shu Liu, Xiaoyong Shen, and Jiaya Jia. Fast and practical neural architecture search. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 6509-6518, 2019.
[9] Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances in Neural Information Processing Systems, 35:26698-2677 2022.
[10] Justin Domke. Generic methods for optimization- modeling. In Artificial Intelligence and Statistics, pages 318-326. PMLR, 2012.
[11] Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning.
In International Conference on Machine Learning, pages 1920-1930. PMLR, 2019.
10

---

[12] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- hyperparameter optimization. In International Conference on Machine Learning, pages 1 165--1173. PMIR, 2017.
[13] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning, In International Conference on Machine Learning, pages 1568-1577. PMIR, 2018.
[14] Saced Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint 1.Xiv:8802.0222 2018.
[15] Udaya Ghai, Zhou Lu, and Elad Hazan. Non-convex online learning via algorithmic equivalence. arXiv preprini arXiv: 15235 2022.
[16] Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application to bi-level optimization. arXiv preprini 1607.05460 2016.
[17] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. In International Conference Machine Learning, pages 3748-3758. PMLR, 2020.
[18] Zhishuai Guo and Tianbao Yang. Randomized stochastic seriance-reduced methods for stochas- tie bilevel optimization. arXiv preprint arXiv:2 002662.....2..... 2021.
[19] Nadav Hallak, Panayotis Mertikopoulos, and Volkan Cevher. Regret minimization in stochastic non-convex learning via mooximal-gradien approach. In International Conference on Machine Learning, pages 4008-4015 4017. PMLR, 2021.
[20] Pierre Hansen, Brigitte Jaumard, and Gilles Savard. New branch-and-bound rules for linear bilevel programming. SIAM Journal on scientific and Statistical Computing, 13(5): 194-1177,, 1992.
[21] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169-192, 2007.
[22] Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 203-4): 2016.
[23] Elad Hazan, Karan Singh, and Cyril Zhang. Efficient regret minimization in non-convex games.
In International Conference on Machine Learning, pages 1433-1441. PMLR, 2017.
[24] Amélie Héliou, Matthieu Martin, Panayotis Mertikopoulos, and Thibaud Rahier. Online non-
convex optimization with imperfect feedback. Advances in Neural Information Processing Systems, 33:17224-17222 17235, 2020.
[25] Amélie Héliou, Matthicu Martin, Panayotis Mertikopoulos, and Thibaud Rahier. Zeroth-order non-convex learning via hierarchical dual averaging. In International Conference on Machine Learning, pages 4192 4202. PMLR, 2021.
[26] Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor- critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
[27] Xiaoyin Hu, Nachuan Xiao, Xin Liu, and Kim-Chuan Toh. An improved unconstrained approach for bilevel optimization. arXiv preprint arXiv:2208.00733: 2022.
(28) Kaiyi Ji, Jason D Lee, Yingbin Liang, and H Vincent Poor. Convergence of meta-learning with task-specific adaptation over partial parameters. Advances in Neural Information Processing Systems, 33:1 1490-41155000 2020.
[29] Kaiyi and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization. arXiv preprint 1rXiv:2102.03926 2021.
[30] Kaiyi Ji, Mingrui Liu, Yingbin Liang, and Lci Ying. Will bilevel optimizers benefit from loops. arXiv preprint 2rXiv:2205.14222 2022.
[31] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Provably faster algorithms for bilevel optimization and applications meta-learning. 2020.
[32] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882-4892. PMI.R, 2021.
11

---

[33] Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To To Wai, Zhaoran Wang, and Zhuoran Yang. near-optimal algorithm for stochastic bilevel optimization via
Advances
in Neural Information Processing Systems, 34:30211-30283, 2021.
[34] Antoine Lesage-Landee Joshua A Taylor, and Iman Shames. Second online nonconvex optimization. IEEE Transactions on Automatic Control, 66(10):4866448) 4876, 2020.
[35] Junyi Li, Bin Gu, and Heng Huang. Improved bilevel model: Fast and optimal algorithm with theoretical guarantee. arXiv preprint arXiv:2009.0066
2020.
[36] Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7426-7434, 2022.
[37] Xiaojun Lin, Ness B Shroff, and Rayadurgam Srikant. A tutorial on cross-layer optimization in wireless networks. IEEE Journal Selected areas in Communications, 24(8):1452-15) 1463, 2006.
[38] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint 1806, 090500000000....0...000 2018
[39] Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A lalue-function-basse interior-point method for non-convex bi-level optimization. In International Conference on Machine Learning, pages 6882-6892. PMLR, 2021.
[40] Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. In International Conference Machine Learning, pages 6305-6315 6315. PMLR, 2020.
[41] David Lopez-Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. Advances in neural information processing systems, 30, 2017.
[42] Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In Infernational Conference Artificial Intelligence and Statistics, pages 1540-1552. PMLR, 2020.
[43] Yibing Lv, Tiesong Hu, Guangmin Wang, and Zhongping Wan. A penalty function method based on kuhn-tucker condition for solving linear bilevel programming. Applied mathematics and computation, (88(1):808-
2007.
[44] Matthew MacKay, Paul Vicol, Jon Lorraine, David Duvenaud, and Roger Grosse. Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. arXiv preprint arXiv: / 030888 2019.
[45] Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter opti- mization through reversible learning. In International conference on machine learning, pages 2113-2122. PMLR, 2015.
[46] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 1xXiv:170600608) 2017.
[47] H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. arXiv preprini aoXiv: (200, 2010.
[48] Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro. Online optimiza- tion in dynamic environments: Improved regret rates for strongly convex problems. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 7195-7201. IEEE, 2016.
[49] Gregory M Moore. Bilevel programming algorithms for machine learning model selection. Rensselaer Polytechnic Institute, 2010.
[50] Parvin Nazari and Esmaile Khorram. Dynamic regret analysis for online meta-learning. arXiv preprint arXiv:2109..433
2021.
[51] SangWoo Park, Julie Mulvaney-Kent Ming Jin, and Javad Lavaei. Diminishing regret for online nonconvex optimization. In 2021 American Control Conference (ACC), pages 978-985.
IEEE, 2021.
[52] Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International conference machine learning, pages 737-746. PMLR, 2016.
12

---

[53] Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back- propagation for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1723-1732. PMLR, 2019.
[54] Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2012.
[55] Chenggen Shi, Jie Lu, and Guangquan Zhang. An extended kuhn-tucker approach for linear bilevel programming. Applied Mathematics and Computation, 162(1):51-63, 2005.
[56] Daouda Sow, Kaiyi Ji, Ziwei Guan, and Yingbin Liang. constrained optimization approach to bilevel optimization with multiple inner minima. arXiv preprint arXiv:2203. /23, 2022.
[57] Bradly Stadie, Lunjun Zhang, and Jimmy Ba. Learning intrinsic rewards as a bi-level optimiza- tion problem. In Conference on Uncertainty in Artificial Intelligence, pages 1 1-120.. PMLR, 2020.
[58] Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In Algorithmic Learning Theory, pages 845-861. PMLR, 2020.
[59] Davoud Ataee Tarzanagh and Laura Balzano. Online bilevel optimization: Regret analysis of online alternating gradient methods. arXiv preprint arXiv:2207. 02829, 2022.
[60] Eric Wong, Leslie Rice, and Zico Kolter. Fast better than free: Revisiting adversarial training. arXiv preprint arXiv:2001.0333
2020.
[61] Tianbao Yang. Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In International Conference on Machine Learning, pages 449-457. PMLR, 2016.
[62] Zhuoran Yang. Zuyue Fu, Kaiqing Zhang, and Zhaoran Wang. Convergent reinforcement learning with function approximation: A bilevel optimization perspective. 2018.
[63] Hongyuan Zhan, Gabriel Gomes, Xiaoye S Li, Kamesh Madduri, and Kesheng Wu. Efficient online hyperparameter optimization for kernel ridge regression with applications traffic time series prediction. arXiv preprint arXiv: /811: 1.00200, 2018.
[64] Lijun Zhang, Tianbao Yang, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou. Improved dynamic regret for non-degenerate functions. Advances in Neural Information Processing Systems, 30, 2017.
[65] Yihua Zhang, Guanhua Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. In International Conference Machine Learning, pages 26693-267 12. PMLR, 2022.
[66] Peng Zhao and Lijun Zhang. Improved analysis for dynamic regret of strongly convex and smooth functions. In Learning for Dynamics and Control, pages 48-59, PMLR, 2021.
[67] Zhenxun Zhuang, Yunlong Wang. Kezi Yu, and Songtao Lu. No-regret non-convex online meta-learning. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3942-3946. IEEE, 2020.
[68] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-936, 2003.
13

---

Appendix
A Discussion about practical applications of OBO
(I) In the traffic flow prediction problem 663] since the data collected by the traffic sensors arrive at the controller continuously and frequently the hyperparameters need to be optimized (in the outer level) quickly in an online manner in order to guarantee the performance of the prediction model (in the inner level). Keeping the hyperparameters static for the prediction model may result in sub-optimal performance, because the distribution of the traffic flow can change gradually. Further, the controller may not have global information of the traffic flows, because it is exorbitantly expensive to deploy sensors to cover all traffic flows.
(2) In the wireless network control problem 37 the controller allocates resources, e.g.. wireless channel bandwidth, the users, where each user can have its own utility function depending on the wireless channel conditions given the allocated resources. Since wireless channels are usually time-varying, the controller has to continuously update the resource allocation quickly maximize the network performance. The rate allocation decisions (deciding what packet rate a user transmits at any given time) and scheduling decisions (which users transmit) are done a fast time-scale (in the inner level), while determining the utility functions of the users could be done at a slower time scale (in the outer level). Further these decisions need to be made in a distributed fashion, so under local knowledge of the channel conditions and interference levels.
In these applications, the current offline bilevel optimization framework cannot be directly applied because of the streaming data, the time-varying functions and possibly the limited information about the system. In contrast, online bilevel optimization has great potential for these online applications. Moreover, the decision making in these online applications also needs to be fast and efficient without the need of knowing all previous functions. Thus, the regret captures the performance of the learning model over the sequential process rather than just the performance of a final output model in the offline setting. How to design such algorithms with a sublinear regret guarantee is very important for making online bilevel optimization more practical in real applications.
B Applications of OBO in meta-learning and adversarial training
Online meta-learning online meta-learning, learning tasks arrive one at a time, and the agent aims to learn good meta-model 0 based on the past tasks in sequential manner, which can be quickly adapted to a good task-specific model ø for the current task. Specifically, each task has a training dataset D'rr and a testing dataset Di and given meta- model 0, the optimal task model is defined as
i (0) E arg min (0, Lo,,, D(") + A110 - 2
In the OBO framework of online meta-learning, the meta-model 0, is the outer-level decision variable round L, and the task model de is the inner-level decision variable. At round t, the task model d is first obtained based on ge (0,, Φ) as an estimation of Φ7 (0e); and then given e.+1, the meta-model will be further updated w.r.t.
f, = C, D( + Al10
Φc+1 1/3.
65 is usually formulated as a min-max optimization problem. The defender learns robust model to minimize the worst-case training loss against an attacker, where the attacker aims to maximize the loss by perturbing the training data. A static setting is often considered with full access to the target dataset at all times. Nevertheless, many real-world applications involve streaming data that arrive an online manner, e.g., the financial markets real-time sensor networks. A continuously robust model update is more desirable in these applications against potential attacks on the streaming data.
Online adversarial training Adversarial training 46
This online adversarial training problem can also be addressed by the OBO framework. Here the model parameters 0 the outer-level decision variable and the adversarial perturbations 8 to the data point (r. 3) is the inner-level decision variable. At each time i, the defender updates the estimate 8e41 of the worst adversarial perturbations, given her knowledge about the inner-level objection function gr (0,, 6t) -L(0,, + 6, vr) subject to the perturbation constraint. Based
14

---

on 6141, the defender updates the model 0141 robustly w.r.. the outer-level objective function fr 0.+1) [(,, 24 + 8 Bt).
C Experimental details
We use a grid of values between 10-5 and 10 to set the stepsizes and did not find the algorithm par- ticularly sensitive to them for the experiments considered. For example, achieve best performance by setting both the inner and outer stepsizes to 10- for the online hyper-representation learning experiments and small values around that scale yield the same performance. For the dynamic OHŌ experiments, only the outer step size set manually to 0.01. The inner step size is optimized along with the other regularization hyperparameters.
OAGD needs to store the previous objective functions, which requires all the previous data points to compute the function values and additional resources to store the knowledge of the function structures. In contrast, our method only stores the previous hypergradient estimates averaged over previous data points. For example, when data points used to evaluate the function at each round, the memory requirement for OAGD is O(nK). compared to O(K) for our method. Here, K is the window size. Therefore, the memory cost of our method can be lower, especially when the number of data points is large.
D Comparison between the regret definitions
For clear comparison, we restate the definitions of bilevel local regret in our work and OAGD here:
Our definition:
T
K
BLR
V ft (2
In OAGD:
K-1 Σ
BLR Σ
( (x))
The key difference that we evaluate the past loss fi- using the variable updates rt- and yū (2;-;) exactly same time ě-1. i, while in OAGD the past loss fi- is evaluated using the most recent updates H, and yi (v.). As shown in (2), the static regret in OAGD can cause problems for time-varying loss functions. Intuitively, evaluating the objective at time slot using variable updates at different time slot j can be misleading, because it does not properly characterize the online learning performance of the model update time slot especially when the objective functions vary lot.
In Figure 2 we compare our algorithm and OAGD using the regret notion proposed OAGD, The results show that our algorithm still achieves similar regret performance compared to OAGD, but with much shorter runtime.
E
Additional Results
Using path-length regularization to capture the variation of optimal decision variables is very common in the literature of dynamic online learning, e.g., [68 48
66) Note that because this variation of optimal decision variables is not controllable, we do not use this term in the design of the algorithm. Rather, the variation system lead to a tighter bound on the regret. However, we mention here that it is also possible to explicitly analyze the regret in terms of the function variations directly.
only used in the theoretical analysis understand which factors the
Theorem F. Suppose that Assumptions 5.1 5.4 hold. Let V, Σi= sup Ige+1 (x, ge (zr, v) and V 1=1 suplft+1 (I, 3) f((2. v)]. Under the same conditions X, a, Qu. and / with
Theorem 5.7 we can have BLR (7) < 0
T
+
V4
+
11
TV
3W
The main proof idea is follows:
15

---

3 x x106
SOBOW-20
OAGD-20
Regret
0
2
Rounds T
x10
Figure 2: Comparison between our SOBOW and OAGD using the regret notion proposed in 59 on the dynamic online HR problem.
(1) For the term H2,r, based on the strong convexity of gt, we can show that [1 2i (x)]12
2. sup 19++ (v, v) gr (z, w)l:
Bg
(2) For the term Vi,T, we can show that ft+1 f (i+1 Se(a,, ut (x)) I (ollv(+2(x))
of [=)]] + sup[fr11 y) - fr(z, such that Et=1 [Fin (Fe, Vt (xt)) - Fa,( vi (I++1)))
2T in Lemma H.3 can be upper bounded by Loy
My V /TT sup (9 v) ge v)
E suplfet1 v),;
go (2, v) and Vj Ei -- suplfe+1 (x, (I, y) fe(æ, y) to capture the function variations, we can have the overall re-
(3) Based on the above, if denote V/ Ei sup Ige+ (2++1(1,W) (2,
V2 V, + TV, In this case, a sublinear regret will be achieved if both V,
gret as
JW
and V are o(T') for suitably selected W. As mentioned in our previous response, the condition on the variation of vī (x) is weaker compared to the condition the variation of ge in order to achieve a small regret. For example, suppose = w(T') and the function variation of fa very small, to achieve regret of O(T3/1), V1. = OT33/4) is sufficient, while we need stricter condition on the function variation gr, i.e., Vg = (2T1/2)
Proof of Lemma 5.5
To prove Lemma 5.5 we first have the following lemma about rf:
Lemma F.1. Suppose that Assumption 5.2 Assumption
5.3 and Assumption 5.4 hold. We can have
the following upper bound on ||=:]]:
|| < PMg + DLÎ + DLifg & M..
Proof. Based on Lemma 2.2 in [4]] it can be shown that yr (I) is Ls Lipschitz continuous in æ. i.c.,
Pg
Tn
Ilvt (a:) - 27 (x')ll
<
||
x'
(8)
f4g
16

---

for any 2 and x'. According to Assumption 5.4 follows that
let & E d' such that (f (+)) S.p. Then it
vV vi v7
- V -
1 V yyfe vf
())) Vn
I1 Li
sp+ +
||22- =1
||02
Mg
pP + DL2 + DLiMg
1g
Therefore,
| =I| V ge vi (, (x,)))
vyf( ut (ca))
PMg + DL3 + DLing
P3
Based on Lemma 1 in 30, we can have that
11 of
1- (1 -Apg)) 2 (1+ (Qz14) L2Mo 1107 - Metill
$ Qc(1 - -Apgg) L2AM, +
Hg
11
+ (1 - (1 )(1))
11:1
-e+ill + (1 - )pun) 1110 - -ill
Mg
1 Q:
L2dM2 + 1 L2 +
L1
11 - y/+ + (1 - Aug)) -
Apg 1 Qe log
A-
Hg
143
L2AMa
L2M, + L1
+
11 - Me+1ll + (1 ----py)) )2a) - 2
)pg) log I-A
Mg
- C llut Ve+1ll + (1 2 11000
wfll
where CQ = (1->p1)) log 1-Apy
LaMM,
+ L, By using the Young's inequality and Lemma F.I it
follows that
1
1/u2 1111 <
1 1
Cllli M+41l 1| 1 + (1 + )11g)(1 - 220 10 - v121
Xpg
1
+
C Clll
V++1ll 11 + (1 20, + 2M
Ap
c2
yo+1
+
1 where = (1+
C2. and &t = (1 + A1ag)(1 22 + +M,.)
Xyt
G Proof of Theorem 5.6
Based on Equation
3 and Equation
it follows that
| folee (x:)) - f( ((+111
V (x))) - V. (1 Vafe(ea V V 241)
17

---

V Vaf( H 3041)0; V.V (F
+ V. V Wil
<3 V... VaJ.(=:. || V 31+1) r
+ V2 90th 11, Vi (zt) V u9 (zz V
(0)
3 /31 - v/
|1 3 || - 11 31 yo+1 yi (2:) (1))11
3L3(pmg + DLA + DLIMA)) |1 (xx) + 31 v
31.+ +
11 3.3 + DL3 + DLIID))) || 2x + 3L9
@
3L + +c2)+
14g
-317 (1+c2+ L3(pp +DL3 (LINb){)
|1 - vf (a:)
2
where (a) is true because of Assumption Lemma 5.5
5.2
(b) is true because of Lemma F. and (c) holds due to
Next, based on Assumption 5.1 and Assumption 5.2 for any and a <
1 Li we can have
|b(41 v (xx))1
<(1 0114))1 vi (2x))12
=(1 ap2))ll1 vi (2t + vi (x - 32 (x1)
(0)
<1 (1 + A) (/11g) 1lv, vi (1) 1| + (1 + x (1 - (lp - 1/ (1x))]²
1
<(1 A) 0p4 11 2 (x 2(1
X (1
- 3 (x1-1))1
21 + ) oxp1 (2)-1) - (xx))l
(6)
<1 + A1 -04tg) 1l Vo 1 2(1 + 1 )1 -agg))llliiiioe 3ā (xt
21,
1 10 0 r.l1?
12 (1
where (a) based on the Young's inequality and (b) is due to Equation {
For a/* follows that
0g4
+ A)(1 (0(1))pp))) -(1
)1 orpt)
2
a² 12
=1 atly
2
011gg
<
L +DL +DZ and 8, = G1 |1 - y1 (x:))1 + eZ. Based on Lemma 5.5
Let G1 = 1 02
we can have that
6, - -7 (x:))1 +
<G + A)(1 anp 1l vi (2- 2G, 1/ a,,))lui 2ī (f.-1)))
GL
(1 + )1 - 110)))
+
SG1 (1
0f19 11y. 3f v ( G2llvi (FL-1) vi (11-1)11
18

---

11-1 21112 + (1-
ap4
1/
2
LiG₂
8--1 + (2111i-((30-1) - V1 (21-1))1
1 =z11
<
aPg
1-1
G2
Σ
2-2
1
0441 /
| (10-1-)(00-1-)) (
1=0
G2
t-2
af4y
| 21-5|l²
(10)
jm0
where G2 2G (1+ app
(1 (rplo) and 61 (1 C2
Lion, +DL3+DLI+ luz (21))1
Lipg
c.
By substituting Equation
back into Equation
we can obtain that
[V (x)))
v fe 1++1)ll
S31,
044 - (1-2)
t-
81 + 22
Σ
t-2
(1 )
0/4 '
100-1-)( -
1=0
G2 1-2
0411g /
| 22-511? J
H Proof of Theorem 5.7
Based on Lemma 2.2 14, we can have the following lemma to characterize the smoothness the function fc(æ,, vt (x)) w.r.t x for any [1,
Lemma H.1. Suppose that Assumption 5.1 and Assumption 5.2 hold. Then for any t [1,7], the function fe(1, ui (I)) is L--moothh, ie., for any x and x',
[ vi (1)) - V Seld', . (x')) < L x'1l. where the constant Ly is given by
Lj L1 2T + 18
L + 2L L.2
I Lo L2
+
+
1gg
For any E [] we first define
Feg Ve (z)+1))
1
Σ
I Vi (1
W
0
Based on Assumption
5.2 we can show the smoothness Fen Vi (x)) w.r.t. T..
Lemma H.2. Suppose Assumption
5.2
holds.
Then the following holds for function
(T Vi (I)+1));
L1 | - rell?.
(1 ve (x++1)) Fin (Z ve (Iz)) < ( (21)), xz) +
2
Proof. For any and I', we can know that
Fi, (x (x++1)) -
K-1
Σ
1/
(1
Σ
" Se (i
W
K
Σ
W
19

---

(a)
R-1
( (f I441 xz) + 4
Σ
"/
x - xell?
W
2
1=
K
Li r++1 - xell
VV - Vi 2141 -
Vi
+
W
2
I++1 - x1) + Li -1 - xell
( vi (z,)),
where (a) holds because of the smoothness of function fe vi (2)) w.r.t
Next, based on Lemma H.2 we can have that
0f - (e, V/ (are)
< (V Vi (rx)) Fe+1 - xz) + L,g
|| 22+11
S 3(V (2t, Ve (x:)) Fr.. (1t,) + [B2L | Ft,,, M++1)11
2
S
FL, V1 (xx)))1 3(VF,, ve (zx)), Fr.,, B6+1) - F. Vi (xx)))
L1
+
|V (I,, 11+1)11
2
B
BL,,)
2
B
+
L1
[V. vi (x:)) - (
2
such that
3
T
122
L1
v (x)))) < Σ
Pan (xx)) - Fe,n (x441, (x++1))]
(a)
8 +
T
LL 2
IV (xx))
(
(11)
(I) We first have the following lemma to bound the term (a) from above:
Lemma H.3. The following inequality holds:
2MT
Σ (ar 27 (xx)) (x (x++1)) <
VL,T.
Proof. First, is clear that
Fe, (x))) - (
(
1
Σ
W
W
==0
K-1
Σ
(
(a.1)
20

---

K-1
Σ
(12)
(a.2)
For the term (a. we can obtain that
R-1
W (0t.::/::............-----------
W [i K- + (x+ckk)
f (1 - "rr
1 /1 fe- (Zee (1++
K
+ W
(
M(1 + k
M K-
(1) 1
W
W
2M
(13)
W
where the inequality holds because of Assumption 5.3
For the term (a.2), we can have that
K-
W
ssup(ft11 (#) (x)
(14)
W
By substituting Equation
13 and Equation
(14) back to Equation
12 Lemma H. can be proved:
(at vi (x+)) - 8
0/ (2+11))
2M
K-1
Σ 1=0
n¹ suppst+1 v Sc (0.
W
W
1=1
2MT
+ Vi.T-
W
(2) Next, for the term (b) which captures the window-averaged hypergradient estimation error, it follows that
(7 Fe. ((+1)11
ग ( - (1
21

---

- -
(1- -t -
W 2 Vi -
W
V Se-
(Te (
Vi (1t -
2
K
K-1
Σ
Σ
(15)
i=0
which boils down characterize the hypergradient estimation error [e vē (xx)) fe 1t+1)ll on the outer level objective function at each round.
By leveraging Theorem 5.6 it is clear that
V (F. - FF.,((2,.
K-1
(0--))) -
W
3T? K-
17 7'
W
3L4
Σ
T K-1
Σ
17'
044
t-1-i
81
W
1=2 i=0
(h.1)
t-j-2
+ GG2
Σ
(1-
0ffla
|1
(
2
j=0
(b.2)
2z
1-2-i
[
1110--1-1-------1
2
(16)
2
==0
(b.3)
Let g. For the first term (b.1), it can be seen that for 1
ally
17
1-1-i
ΣΣ (1
-
111-00
17
1=2
T
1-714
<61
17
1-744
1=2
61 (1 - 714g n11 - 17" -1)
1) + 7/4
17
6in(1 - -7Mgg)
(17)
n) + 711gg
22

---

For the second term (b.2), we have
K-1
Σ
(1- [|
(1
|=0
1-2
Σ
11
"1l |1: - (f--(0-1--)
1=0
t-3
+
(11 - 74 744 (101 (
t-1-K
+
Σ
K - 1
- K x>1
j=0
=1lvi-1( v/ (ste - 1))2 [(1 7p4g) ( 2) v
+ 1(1 - )2 - 17(1 7Hp) + 10 ( - 8 2 (22-3))
+...
+ [11 - ()n) ) -2 + (1 - -414)) x -3 + + k - -1 ( - vi (x)+1-x)11
--
+
Σ
{[L - 7144g ,+ + 7711 - 7Hg D+K-2 + 1/ K- 11 74y)'1
-=
1l - (2 k x)) Vi+t 1 (2 x-z ,)1|
-11bi (1)-1) Vē (31-1))12+ + - (-)))))²
J2g nllyi 2 - Vi- (xt
(1 ys
12110/ 11yii=(00- (3)-3) 20) +...
1
1-7
1- jk
k x Vi+2- (x(+1-K)))
+
1
1-744 jk
1-1-
+
71
K5 -
Σ
(1- - x
1
1-
1=0
(xr 1
- V7 (x+- 1)] + - - vi (
1 14
+ .... +
K --211
|1 k - -)) -
t-1-K
+
7
K K-1+ wi
K -
such that
T
K-1
Σ
- --14)) ( - (
1=2 1=0
/=0
T
n
( - vi (12 + allvi ( - vi (
11
+ 7gg
23

---

+...
-
x-
1-1-K
Σ
k
1+/ -
V k
k-
Vi+1 1 k (
j=0
T
Σ
v7 sup - (x)]1
(1 ()) 7M4))
1=2
H2.r
(18)
(1 (1] - 7Ma)
where H2, = >i= sup (1)(-1(z)) 11 (2)
Besides, we know that
| 1 - xell2 =3² (2)1
(
- 1.)) 2, (1 ( 1|]
Following the same analysis for the second term (b.2), the following result can be obtained that for the third term (b.3):
K-1
1=2
1=0
j=0
T
n 111 -
-
11 1
7P
1=2
+
+ K
Σ
K K-1+3
-
1=0
n
-
11 1 7P
(
+ " 2
+
( (
1-1
+
Σ
"1 K-1+
1=0
+
2
1 1 --
VF ( - (F-110111.0)11
1 - 1 1M
1- t=2
2,8211
1 T-1 1 1-7
7- 1+ 714
24

---

2
T
1 - (1e-
(1 (1 - 1 + (Pg)
2
T (V
+ (1 (1 - + 7Pa)
(19)
2=
Therefore, by substituting Equation have that
Equation
18
and Equation
[9
into Equation
66
we can
V (e (x:)) - (Fe
3L3
T K-1
(1 - -1p))
W
1=2 1=0
1-i-2 Σ
+ G2
7/42) |10| 118i-1 (1 - (
1=0
22
1-2-i
+
Σ
(1 - ()1gg)
+ -
1=0
3T4
81n(11 - 7p19)
+ G2
71
H2,r
W
(1 (1(11 7Wl
(1 - (1 1+ 7/4
2L7G₂
2,8211
(Z,, (z))
(1 11-1)(11-
1 + 7pg)
Gz
2
T
+
(V + (())))))()))) (21,
m (1- (1-1))11 - 1 7p1
which gives that
12T.
1 p2 11 1+ -1
V
31,2m
3T T
61 (111) + H2H +
V F. (x,, (Z
W(1 - 17) (1) - + (1kgg)
(1 v/ (x1))
(11. v2)11
1
Here
because
PgW(1- 7)(n }+rreg)
3
m I. W(1 n)(n - - 0epyg 2)
8² =
Ls
24L
m W(1 - -1) - - 22
24I4G211
12r,,880aa
31.71
Let G3 =
and G4 = W(I-n]ln-+tHu) is clear that
13 (2((1-) 1479g)
T
V Fi, v7 (xx)) - Fen (x.e.
G
G. 42 T
18 (1 7mg) + G2H2,r + G3 mg
V (z:)))
G3
25

---

+
G3 (Vi1 - (21
Based on Equation
we can have
T
PL
2
T
PR (enn Vi (xx)) - Fe. (f
t=1
3 L$L$
2
Σ
F.
T
(12 (2+ (x(+))) + (0
G1 [51(1 (1gg + G2H
$
(Lt, Vi (1x4)
Gs
G4
G2
Σ
T
2 ( - 821)118211
G3
G3
such that
(F (1.))
T
FF (Tr, (xx)) B
BL,
G. 41 Gs
(5+B2L))
A
(1 + ++BL))
G4 (1 7Ug) + +22l2,T
+
1/2 - L-BL-- C1 1L1Ga8 Gs
2 + 32L
B
K
2MT W
V1T
( + ,b,)
G.GzHar
G1
L -
G.
G. 32
+ (BBL,)
1/ - BLg
G4 1L7G,8
e 32
G2
Go
#
(g + (L1)
G.
(1 - ()p1 + Gg
(x1))
E ( (01. }2)
Ga
+
- -BLL
C4 G22
( + BBL,))
G3
T
Vi,
=0
H2,T
3W
B
Here -3L
G.
41, G28
8
+ L,)
> 0 because
Go
2
2
1
BL,
G4 4L7G28
(B
(2+B)))
BPL,)
2
G3
2
(1)
G₁ g2
BL,
2
Gs 12
(1
2,3Ls
(c)
20,
where (a) and (c) are because 9Lg < 1. and (b) is because fLg
C4 G,
03
1
26


Reviews:
[{"review_id": "tNJ3Ha4EaC", "reviewer": "Reviewer_Ue3m", "summary": "This work studies the online bilevel optimization problem with nonstationary and time-varying objective functions. This line of research can cover applications with online nature like online meta-learning, online hyperparameter tuning, wireless networks. Compared to widely studied offline bilevel problem, the studied one has challenges like limited information, hypergradient computation, changing objectives. The authors propose a single-loop online bilevel optimizers called SOBOW based on online nonconvex optimization and window averaging, and further show it can attain a sublinear regret. Some experiments are provided to justify the effectiveness of the proposed method. ", "questions": "See weaknesses.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. Bilevel optimization has been studied intensively mainly in the offline setting where all objective functions are fixed and known. It has been much less explored in the online and nonstationary setting. This work seems to provide a simple and good solution.\n\n2. The authors have done a good job in discussing the underlying challenges and the drawbacks of existing method in [54]. How to design a good online bilevel optimizer with limited queries, efficient hypergradient computation, guaranteed regret turns out to be nontrivial. \n\n3. Technically, this work needs to cope with 1) the intersection among three variables $x,y,v$ in online manner,  2) time-smoothed gradient updates, 3) biased gradient estimation, which may be straightforward. ", "weaknesses": "1. The hypergradient estimation contains second-order derivatives. Will them cost a lot in practical online settings? Is it possible to design fully first-order method without matrix-vector computations? There are some recent progress towards the Hessian-free bilevel optimization. \n\n2. The authors do not compare the rate of their method with OAGD. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough reviews and constructive comments. We provide our responses to your comments below. \n\nQ1: Is it possible to design fully first-order methods without matrix-vector computations?\n\nA1: Many thanks for the insightful comments and suggestions. Our current algorithm involves matrix-vector computations to deal with second-order derivatives, which is fairly efficient in our experiments. As the reviewer suggested, the computational cost of the algorithm can be further reduced via fully first-order methods or Hessian-free design. We describe these ideas as follows. \n\nTo the best of our knowledge, the recent first-order approaches mainly follow two strategies: (1) replace the second-order term in the hypergradient estimation with zeroth-order estimations; (2) reformulate the bilevel problem to a single-level constrained optimization problem and use first-order methods to solve the reformulated problem. \n\nFor the first strategy, applying it to our approach is straightforward by replacing the second-order term in online hypergradient via their zeroth-order estimations. For the second strategy, we need to reformulate the bilevel problem at each round to a constrained optimization problem, and then develop an online algorithm for solving such a reformulated nonconvex constrained problem. The primal-dual methods can be leveraged to solve such a constrained problem. Particularly, a recently developed single-loop algorithm for nonconvex constrained problems in (S. Lu et al., 2022) can be leveraged to develop a single-loop online algorithm and analyze its regret performance.\n\n- S. Lu et al.. A single-loop gradient descent and perturbed ascent algorithm for nonconvex functional constrained optimization. ICML, 2022.\n\nQ2: The authors do not compare the rate of their method with OAGD.\n\nA2: Thanks for the question. We have the following response to this question:\n\n(1) Since our work uses a different regret definition from that in OAGD, it would not be fair for a direct comparison between the regret bounds. \n\n(2) Instead, as seen in Figure 1, we compare the performance of our algorithm and OAGD using our definition of regret. And we have also conducted experiments to compare the performance between our algorithm and OAGD using the regret defined in OAGD (Figure 2 in Appendix). In both cases, we can see that our algorithm achieves comparable regret performance with OAGD, but with a much shorter runtime. \n \n"}, {"review_id": "yTdYD5wO5A", "reviewer": "Reviewer_98z6", "summary": "This paper proposed a new method for solving online bilevel problem that only required one-step $y$ update and leveraged the historical information to smooth the update. Extensive experiments are provided to validate their theories.", "questions": "Could the bounded function value in Assumption 5.3 be relaxed to merely on the feasible set? In this way, it can be derived from the bounded feasible set and Lipschitz continuity assumptions. Otherwise, bounded function value on the whole space is relatively restricted. Also, does the objective in the experiment part satisfy this assumption?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tThis work is the second one considering the online bilevel optimization problem and this problem can motivate many applications. \n2.\tThe algorithm does not require multiple inner updates and the evaluation of the current models on previous functions, so that it is more applicable to online setting.", "weaknesses": "1. One of the challenges unique to online bilevel optimization, as compared to its offline counterpart in this paper, lies in controlling the hypergradient estimation error, which is dependent on $ ||y_t^*(x_t)-y_{t+1}^*(x_{t+1})||^2$. Unlike in the offline case, it cannot be simply bounded by $|| x_{t+1} -x_t ||$ due to the time-variant nature of $g_t$. It is impossible to control this term without making variation assumption on the lower-level objective, so it is intriguing to see how to regulate this term by bounded variational assumption of $g_t$. However, Theorem 5.7 seems to circumvent this challenge by directly converting the hypergradient estimation error term to $V_T$ and $H_T$ — terms over which we cannot directly control. Is it possible to characterize these two terms explicitly by the variation of $g_t$? This would offer more insights into the effect on the overall online bilevel optimization.\n\n2. The state-of-the-art work on offline bilevel optimization also adopts the three-level optimization and treats $v$ as a solution to a quadratic problem and thus can eliminate the conjugate gradient loop. As one of the contributions of this work is to reduce the multiple-step lower-level updates to one-step, it is also intriguing to see whether the conjugate gradient loop can be reduced since it is also time-consuming.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough reviews and constructive comments. We provide our response to your comments below. If our response resolves your concern, we would greatly appreciate it if you could consider increasing your score. \n\nQ1: Is it possible to characterize these two terms explicitly by the variation of $g_t$? This would offer more insights into the effect on the overall online bilevel optimization.\n\nA1: Thank you for this insightful comment. We have the following response to this question:\n\n(1) Indeed as suggested by the reviewer, it is possible to explicitly analyze the regret in terms of the variation of $g_t$. For example, in terms of $H_T$, based on the strong convexity of the function $g_t$, we can further bound $||y_t^*(x_t)-y_{t+1}^*(x_t)||^2$ from above based on the function variation $\\sup_y |g_t(x_t, y)-g_{t+1}(x_t, y)|$; in terms of $V_T$, based on the Lipschitz continuity of function $f$, we can upper bound $f_{t+1}(x, y_{t+1}^*) - f_t(x, y_t^*(x))$ based on $||y_t^*(x)-y_{t+1}^*(x)||^2$ and the function variation of $f$, i.e., $\\sup_y [f_{t+1}(x, y)-f_t(x,y)]$, where the first term can be further bounded above by the function variation of $g$. We will discuss this and have a more detailed investigation in the revision.\n\n(2) In online bilevel optimization, the variation of $y_t^*(x)$ is more important since it directly affects the outer-level objective functions. Further, for strongly convex inner-level functions $g_t$, when the variation of $g_t$ is small, i.e., $|g_t(x, y)-g_{t+1}(x, y)|$ is small, the gap between $y_t^*(x)$ and $y_{t+1}^*(x)$ will not be large; when the function value $g_t$ changes significantly, as long as the variation of $y_t^*(x)$ is small, our algorithm can still guarantee a small regret. In this sense, the condition on the variation of $y_t^*(x)$ is weaker compared to the condition on the variation of $g_t$ in order to achieve a small regret.\n\n(3) Using path-length regularization to capture the variation of optimal decision variables is very common in the literature of dynamic online learning, e.g.,\n\n- M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. ICML, 2003.\n- A. Jadbabaie et al.. Online optimization: competing with dynamic comparators. AISTATS, 2015.\n- A. Mokhtari et al.. Online optimization in dynamic environments: improved regret rates for strongly convex problems. CDC, 2016\n- T. Yang et al.. Tracking slowly moving clairvoyant: optimal dynamic regret of online learning with true and noisy gradient. ICML, 2016.\n- L. Zhang et al.. Improved dynamic regret for non-degenerate functions. NeurIPS, 2017.\n- P. Zhao et al.. Dynamic regret of convex and smooth function. NeurIPS, 2020.\n\nNote that because this variation of optimal decision variables is not controllable, we do not use this term in the design of the algorithm. Rather, the variation term is only used in the theoretical analysis to understand which factors in the system lead to a tighter bound on the regret. \n\nQ2: It is also intriguing to see whether the conjugate gradient loop can be reduced since it is also time-consuming.\n\nA2: We are not very sure about the question the reviewer asked. \n\n(1) If the reviewer refers to directly using the closed form solution of $v^*$, this solution involves the calculation of Hessian inverse which is computationally expensive. \n\n(2) If the reviewer refers to using only one step of conjugate gradient to estimate $v^*$, this is doable for offline bilevel optimization with time-invariant objective functions, where slow changes of the variables can still make progress to solve the optimization problem. However, in online bilevel optimization, since the estimation error of $v_t^*$, i.e., $||v_t^Q-v_t^*||$,  depends on the estimation error of $v^*_{t-1}$ in the last round and the variation of $v_t^*$, i.e., $||v_{t-1}^*-v_t^*||$, we need to make sure that  $||v_{t-1}^*-v_t^*||$ will decay with $t$ in order to achieve a sublinear regret with one-step conjugate gradient. In the offline case, $||v_{t-1}^*-v_t^*||$ only depends on $||x_{t-1}-x_t||$ which can decay gradually; however, in the online case, $||v_{t-1}^*-v_t^*||$ also depends on the function variations, such that additional conditions may be needed for achieving a sublinear regret. To summarize, reducing the number of conjugate gradient steps is an interesting open problem, which is beyond the scope of this paper, but one that we plan to investigate for future work.\n\nQ3: Could the bounded function value in Assumption 5.3 be relaxed to merely on the feasible set? Also, does the objective in the experiment part satisfy this assumption?\n\nA3: (1) Yes, Assumption 5.3 can be relaxed that the function value on $(x, y^*(x))$, i.e., $f_t(x, y^*(x))$, is bounded, which holds given the bounded feasible set, Lipschitz continuity and also the bounded set of $y_t^*(x)$. Here $y^*(x)$ is generally assumed to be bounded in bilevel optimization such that the lower-level problem can be solved to a certain accuracy. (2) Yes, the objective in the experiments satisfies this assumption. For example, in the online hyper-representation learning problem, since both the value of data samples and the feasible set of the decision variables are bounded, the function values are bounded.\n\nWe thank the reviewer again for your insightful comments. Again, if our response resolves your concern, we will appreciate it very much if you could consider increasing the score. We will also be very happy to answer any further questions you may have.\n\n\n\n"}, {"review_id": "VTgop9k7RQ", "reviewer": "Reviewer_M56B", "summary": "The authors consider bilevel optimization in the online setting. In this setting, we have access at iteration $t$ to the outer function $f_t$ which is assumed to be differentiable and possibly nonconvex. We also have access to the inner function $g_t$ which is assumed to be twice differentiable and strongly-convex with respect to the inner variable $y$. They propose SOBOW, an algorithm that implement approximate implicit differentiation in a single loop fashion. In SOBOW, at iteration $t$, the inner variable is updated by a gradient step and the solution of the linear system involved in the expression of the hypergradient is approximated by Conjugate Gradient steps. Then, the obtained approximate hypergradient is stored and the outer variable $x$ is updated following the opposite direction given by an average of the $K-1$ last approximate hypergradient computed. The outer variable is then projected on the constrains set $\\mathcal{X}$. \nThe authors show that SOBOW achieves a sublinear local regret.\nSOBOW is numerically compared with OGD and OAGD on an online hyper-representation learning task using a simulated dataset, and on an online hyperparameter optimization problem using the 20newsgroups dataset.", "questions": "NA", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is clearly written\n* The authors study online bilevel optimization which has been very little studied in the literature.\n* The proposed method is theoretically grounded\n* The method improves upon previous work by avoiding the evaluation of the previous functions at the current iterates.\n* Numerical validation is provided on several tasks.", "weaknesses": "* The idea of single-loop updates was already exploited in offline context [1, 2, 3]. The authors should mention it.\n\n* Since the authors consider a projection onto $\\mathcal{X}$, this set has to be assumed closed.\n\n* Under a closedness assumption of $\\mathcal{X}$ and $\\mathcal{X}$ being assumed to be bounded, the boundedness of $\\nabla f$ is automatic making assumption 5.4 unecessary. \n\n* In terms of notations, the notation $\\nabla f_t(x, y^*(x))$ is confusing because it can be thought as the gradient of the function $f_t$ evaluated at the point $(x, y^*(x))$ or as the gradient of the function $x\\mapsto f_t(x,y^*(x))$. Maybe it should be clearer to give a name to the function $x\\mapsto f_t(x,y^*(x))$.\n\n[1] M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic.  arXiv:2007.05170, 2021\n\n[2] M. Dagréou, P. Ablin, S. Vaiter, and T. Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. NeurIPS, 2022.\n\n[3] J. Li, B. Gu, and H. Huang. A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse. AAAI, 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough reviews and constructive comments. We provide our response to your comments below. \n\nQ1: The idea of single-loop updates was already exploited in offline context [1, 2, 3]. The authors should mention it.\n\nA1: Thank you for bringing up these studies. We will add them in the related work in the revision.\n\nQ2: Since the authors consider a projection onto $\\mathcal{X}$, this set has to be assumed closed.\n\nA2: Thank you for pointing out this missing statement. We will change the statement to “the closed convex set $\\mathcal{X}$” in Assumption 5.3.\n\nQ3: Under a closedness assumption of $\\mathcal{X}$ and $\\mathcal{X}$ being assumed to be bounded, the boundedness of $\\nabla f$ is automatic making assumption 5.4 unnecessary.\n\nA3: Many thanks for the good suggestion. We will change this assumption to a statement.\n\nQ4: In terms of notations, the notation $\\nabla f_t(x, y^*(x))$ is confusing because it can be thought as the gradient of the function $f_t$ evaluated at the point $(x, y^*(x))$ or as the gradient of the function $x \\rightarrow f_t(x, y^*(x))$. Maybe it should be clearer to give a name to the function $x\\rightarrow f_t(x, y^*(x))$.\n\nA4: Thank you for the constructive suggestion. We will define $\\Phi_t(x): x\\rightarrow f_t(x, y_t^*(x))$ in the revision. \n"}, {"review_id": "6VrAmkcIcL", "reviewer": "Reviewer_ouS8", "summary": "This paper studies bilevel optimization in an online setting where the objective in both the levels are allowed to vary with time, and the goal is to develop an algorithm with sublinear regret. This paper proposes a practical single-loop algorithm that updates the lower-level variable only once for each upper-level variable update. The lower-level variable is updated via vanilla SGD, while the hypergradient for the upper-level update is computed via some specified number of steps of Conjugate Gradient, and averaged over a window of specified size. This design significantly improves the computational and memory overhead relative to the existing baseline which requires access to all the past objectives and gradient oracles in the window; the proposed scheme just needs to maintain the hypergradients in the window. Based a novel notion of bilevel regret, the paper shows that the proposed algorithm is able to achieve sublinear regret under some standard assumptions for appropriately set algorithmic parameters and window sizes. The empirical evaluation on two online bilevel applications show that the proposed scheme can match the performance of the existing baseline while being significantly more efficient both in terms of time and memory requirement -- the computational advantage of the proposed scheme is enhanced when considering larger window sizes.", "questions": "- Given existing single-loop static algorithms such as TTSA [A] and STABLE [B], how is the proposed algorithm positioned against these? One of the challenges with single-loop schemes is that the upper-level updates need to be very slow (that is, have a small upper-level learning rate relative to the lower-level learning rate) if we are just using a single SGD step lower-level update. This is because, otherwise, it is hard to guarantee that $y_{t+1}$ converges to $y^*(x_t)$ since the $x_{t-1} \\to x_t$ update can significantly move the lower-level target from $y^*(x_{t-1}) \\to y^*(x_t)$, which a single SGD step is unable to catch up with. That is why, the more expensive but sophisticated lower-level update is proposed in STABLE, to allow for faster upper-level updates. Does this issue manifest in the proposed SOBOW, resulting in a need for a smaller upper-level learning rate (and thus slower convergence), or is there something in the nature of the online bilevel setup that mitigates this issue?\n- Given that $\\{Q_t, t \\in [T]\\}$ would be an increasing sequence, what is the motivation to not just solve the least-squares problem to sufficient optimality at each step and remove the error term in Lemma 5.5, and simplify the analysis?\n\n>[A] Hong, Mingyi, et al. \"A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic.\" SIAM Journal on Optimization 33.1 (2023): 147-180.\n\n>[B] Chen, Tianyi, et al. \"A single-timescale method for stochastic bilevel optimization.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022.", "limitations": "The authors do explicitly discuss some limitations, and I do not anticipate any potential negative societal impact of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Practical online solution.**\nIn the online bilevel setting, it seems more practical to have a single-loop algorithm since the objectives/gradients for each of the level will probably be made available to the learner in a sequential alternate manner. However, single loop bilevel algorithms are usually harder to analyse. So it is a significant contribution to have a single loop algorithm that has sublinear regret.\n\n**Intuitive presentation of theoretical analyses.**\nThe authors have presented the theoretical analyses in a very intuitive and clear manner. After specifying the necessary assumptions, the authors discuss the necessary steps to complete the analyses, and gradually build up to each of the results. This presentation is very easy to follow for a reader, and I really appreciate the work done for such a presentation. After the main theorem, the author clearly discuss the conditions under which we might achieve the desired sublinear regret.\n\n**Strong empirical performance against baseline.**\nThe experimental results show clearly show that the proposed SOBOW matches the regret of the OAGD baseline, but is able to do so with significantly lower computational and memory overhead, and without access to the past objectives. The computational gains are very significant, with up to almost $20\\times$ speedup. This is an impressive result, making the solution even more practically useful.", "weaknesses": "**Hyperparameters in the definition of regret.**\nOne of the weaknesses of this paper is that the proposed novel notion of bilevel regret itself (equation (2)) seems to depend on the window size $K$ and the decay rate $\\eta$ (and it is not quite clear what the subscript $w$ in $BLR_w(T)$ denotes). Given that the subsequent analysis shows that these quantities need to be set appropriately for the desired convergence rate, it is odd that the notion of regret itself depends on it. The algorithm can use such hyperparameters, but the term quantifying the regret should not depend on them. Is this standard in dynamic local regret analysis? One would expect that the bilevel local regret would be defined as some term such as $\\sum_{t=1}^T || \\nabla_x f_t(x_t, y_t^*(x_t)) ||^2$ or something similar, where we are computing the per-time-step (local) suboptimality, and we would want this quantity to grow sublinearly with $T$ (with appropriate assumptions regarding the relationship between $f_t, g_t$ and $f_{t+1}, g_{t+1}$). It seems as if such a definition of bilevel regret (equation (2)) was considered because it seems to match the form of the upper-level update that is used in the proposed algorithm.\n\n**No dependence on lower-level suboptimality in the regret.**\nAnother issue with the considered notion of bilevel regret is that it is not clear why it is meaningful for the regret to depend on $(x_t, y_t^*(x_t))$ instead of just $(x_t, y_t)$ or $(x_t, y_{t+1})$. Alternately, it is not clear why the sub-optimality in the lower-level decision variable (that is, having $y_{t+1}$ instead of $y_t^*(x_t)$) does not contribute to the regret in any way. Analyses of static bilevel optimization usually establish convergence of $ || \\nabla_x f(x_t, y_t^*(x_t)) ||^2$ **as well as** that of $|| y_{t+1} - y_t^*(x_t) ||^2$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough reviews and constructive comments. We provide our response to your comments below. If our response resolves your concern, we would greatly appreciate it if you could consider increasing your score. \n\nQ1: Hyperparameters in the definition of regret. Is it standard in dynamic regret analysis?\n\nA1: Many thanks for the insightful comments. The window-smoothed regret definition is widely adopted in online nonconvex optimization for dynamic local regret analysis (e.g., E. Hazan et al., 2017; S. Aydore et al., 2019; N. Hallak et al., 2021; D. Tarzanagh and L. Balzano, 2022; Y. Huang et al., 2023; Z. Guan et al., 2023), and our definition follows exactly the same way as in S. Aydore et al., 2019 and D. Tarzanagh and L. Balzano, 2022, which also have both window size and $\\eta$ in their definitions. The underlying ideas about designing such a local regret are as follows:\n\n(1) It has been shown in the literature of online learning (e.g, E. Hazan et al., 2017) that this time-smoothing is indeed necessary for the definition of the local regret in the non-convex setup. Specifically, for any online algorithm, there exists an adversarial sequence of loss functions,  which can force the local regret to be $\\Omega(\\frac{T}{K^2})$. Therefore, a sublinear regret cannot be achieved for $\\sum_{t=1}^T ||\\nabla_x f_t(x_t, y_t^*(x_t))||^2$ suggested by the reviewer (which corresponds to the case $K=1$). In practice, the average performance of a system is also a typical and intuitive notion that is commonly used to evaluate real-world applications. For example, under changing environments, such an average performance metric during a period is naturally adopted in time series forecasting problems (S. Aydore et al., 2019). In terms of the decaying rate $\\eta$, it is reasonable to assign larger weights to the most recent functions, in the same way with, e.g., S. Aydore et al., 2019 and D. Tarzanagh and L. Balzano, 2022. Here the subscript $w$ in $BLR_w(T)$ just refers to the window-averaged local regret.\n\n(2) A small time-smoothed gradient in expectation implies that the outer-level decision is becoming better and closer to the local optima for the outer-level optimization problem at each round.\n\n- E. Hazan et al.. Efficient regret minimization in non-convex games. ICML, 2017.\n- S. Aydore et al.. Dynamic local regret for non-convex online forecasting. NeurIPS, 2019.\n- N. Hallak et al.. Regret minimization in stochastic non-convex learning via a proximal-gradient approach. ICML, 2021.\n- D. Tarzanagh and L. Balzano. Online bilevel optimization: regret analysis of online alternating gradient methods. 2022.\n- Y. Huang et al.. Online min-max problems with non-convexity and non-stationary. TMLR, 2023.\n- Z. Guan et al.. Online nonconvex optimization with limited instantaneous oracle feedback. COLT, 2023.\n\nQ2: No dependence on lower-level suboptimality in the regret.\n\nA2: Thank you for your constructive comments. We have the following response to this question:\n\n(1) Indeed, we have also thought about the reviewer’s suggestion for the regret definition at the beginning of this study. However, it turns out that the physical meaning of $f_t(x_t, y_t)$ or $f_t(x_t, y_{t+1})$ is not clear in bilevel optimization, whereas $f_t(x_t, y_t^*(x_t))$ is the true objective function in the outer level. And a small value of $f_t(x_t, y_t)$ or $f_t(x_t, y_{t+1})$ does not imply a small value of $f_t(x_t, y_t^*(x_t))$; namely, the bilevel problem requires to make $f_t(x_t, y)$ as small as possible particularly by $y_t^*(x_t)$ that minimizes the inner problem, not by any other values $y_t$ or $y_{t+1}$. Thus, minimizing the regret in terms of $f_t(x_t, y_t)$ or $f_t(x_t, y_{t+1})$ does not necessarily imply that $y_t$ or $y_{t+1}$ are near optimal with respect to inner loop problem, which then may not be desirable decision variables in the bilevel optimization problem at each step.\n\n(2) In fact, the sub-optimality in the lower-level decision variable has contributed to the regret through the update of $x_t$ in Equation (6), which highly depends on the quality of $y_{t+1}$. Intuitively, when $y_{t+1}$ is a more accurate estimate of $y_t^*(x_t)$, the hypergradient estimation is more accurate and the outer-level $x_{t+1}$ will be a better decision, leading to a smaller regret. \n\nQ3: Does SOBOW need for a smaller upper-level learning rate? \n\nA3: We do need a smaller learning rate for the upper-level problem. As shown in Theorem 5.7, the upper-level learning rate $\\beta$ is in the order of $o(\\alpha^2)$, where $\\alpha$ is the lower-level learning rate.\n\nQ4: What is the motivation to not just solve the least-squares problem to sufficient optimality at each step and remove the error term in Lemma 5.5, and simplify the analysis?\n\nA4: In practice, solving the problem for $v_t^*$ to sufficient optimality can introduce high computational cost at each step, which can significantly slow down the learning process. In contrast, the computational cost can be substantially reduced without requiring high estimation accuracy of $v_t^*$ at each step in our work. Further, note that in (K. Ji et al., 2022) it is shown that the value of $Q_t$ for solving the problem for $v_t^*$ indeed has a relatively weak impact on the overall performance. For example, in (K. Ji et al., 2022), the cases between $Q=1$ and $Q=20$ have very similar performance and also similar running time. This implies that the computational cost introduced by the increasing $Q_t$ is actually negligible. Therefore, in this work we consider the sub-optimality of $v_t$ and take the estimation error for $v_t^*$ into consideration. \n\n- K. Ji, et al.. Will bilevel optimizers benefit from loops? NeurIPS, 2022.\n\nWe thank the reviewer again for your insightful comments. Again, if our response resolves your concern, we will appreciate it very much if you could consider increasing the score. We will also be very happy to answer any further questions you may have.\n\n\n\n"}]

Author rebuttal:

Meta-review: This paper studies online bilevel optimization, which is an important topic yet still less developed. The paper proposes a single-loop algorithm for solving this problem and provides analysis for the regret. The method improves existing method from several aspects. It is a nice contribution to the field.
Decision: Accept (poster)