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.
Paper
Similar papers
Peer review
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.
Strengths
**Practical online solution.** In 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. **Intuitive presentation of theoretical analyses.** The 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. **Strong empirical performance against baseline.** The 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.** One 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. **No dependence on lower-level suboptimality in the regret.** Another 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$.
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? - 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? >[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. >[B] Chen, Tianyi, et al. "A single-timescale method for stochastic bilevel optimization." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
4 excellent
Contribution
3 good
Limitations
The authors do explicitly discuss some limitations, and I do not anticipate any potential negative societal impact of this work.
Dear Reviewer ouS8: can you read the authors' response, and see if your comments are addressed?
Dear Reviewer ouS8, We would like to bring to your attention that your individual ratings on Soundness (3 good), Presentation (4 excellent) and Contribution (3 good) are not consistent with your final rating 3 of our paper. Your review seems to also suggest that you highly favor this paper, as reflected by your comments such as “So it is a significant contribution to have a single loop algorithm that has sublinear regret”; “The computational gains are very significant”; “This is an impressive result, making the solution even more practically useful”, etc. Your comments on the weakness part seem to have only clarification questions, which we believe we have provided convincing answers in our response. Could you please reconsider your final rating of the paper to make it aligned with your review and our response to your concerns. Of course, if you have any further questions, we would be very happy to address them. Thank you very much for your time and efforts!
Main concerns addressed
I thank the authors for their detailed response to my comments and questions. My main concerns have been addressed as it seems that the choice of the regret is standard in literature. I will update my score to support this paper.
Many thanks for raising the score! We genuinely appreciate your constructive comments and time.
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}$. The authors show that SOBOW achieves a sublinear local regret. SOBOW 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.
Strengths
* The paper is clearly written * The authors study online bilevel optimization which has been very little studied in the literature. * The proposed method is theoretically grounded * The method improves upon previous work by avoiding the evaluation of the previous functions at the current iterates. * 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. * Since the authors consider a projection onto $\mathcal{X}$, this set has to be assumed closed. * 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. * 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))$. [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 [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. [3] J. Li, B. Gu, and H. Huang. A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse. AAAI, 2022
Questions
NA
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
NA
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.
Strengths
1. This work is the second one considering the online bilevel optimization problem and this problem can motivate many applications. 2. The 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. 2. 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.
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?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
3 good
Contribution
2 fair
Limitations
Yes
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.
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. 2. 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. 3. 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. 2. The authors do not compare the rate of their method with OAGD.
Questions
See weaknesses.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
4 excellent
Limitations
Yes
Thank you for the response. It clarifies my questions. I remain the score.
Thank you for your clarification; it has addressed some of my questions. I think that controlling the term $\\|y_t^*\left(x_t\right)-y_{t+1}^*\left(x_t\right)\\|^2$ by bounded variational assumption of $g_t(x,y)$ remains crucial to online bilevel optimization. As you also concur with its potential solution, it might be better to incorporate a more detailed discussion and a rigorous theory on this topic in the current version. Regarding Q2, I'm referencing the fully single-loop techniques [1]-[3] in offline bilevel optimization, where $v$ is treated as another optimization variable, akin to $y$. Given your strategy to reduce the number of loops for optimizing $y$, could a similar approach be applied to $v$? [1] A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse. AAAI 2022. [2] A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. NeurIPS 2022. [3] Amortized Implicit Differentiation for Stochastic Bilevel Optimization. ICLR 2022.
Response to the further comment
Q1: It might be better to incorporate a more detailed discussion and a rigorous theory on this topic in the current version. A1: Thank you for the advice. We have developed the following theorem by using the function variations: **Theorem. Suppose that Assumptions 5.1-5.4 hold. Let $V_g=\sum_{t=1}^T \sup |g_{t+1}(x, y)-g_{t}(x, y)|$ and $V_f=\sum_{t=1}^T \sup [f_{t+1}(x, y)-f_t(x, y)]$. Under the same conditions on $\lambda$, $\alpha$, $Q_t$, $\eta$ and $\beta$ with Theorem 5.7, we can have $BLR_w(T)\leq O\left(\frac{T}{\beta W} + \frac{V_f}{\beta} + V_g + \frac{\sqrt{T V_g}}{\beta} \right)$.** A more detailed analysis is as follows: (1) For $H_{2,T}$, based on the strong convexity of $g_t$, we can show that $||y_{t+1}^*(x)-y_{t}^*(x)||^2 \leq \frac{2}{\mu_g} \sup |g_{t+1}(x, y)-g_{t}(x, y)|$; (2) For $V_{1,T}$, we can show that $f_{t+1}(x, y^*_{t+1}(x))-f_t(x,y_t^*(x))\leq L_0 ||y^*_{t+1}(x)-y_t^*(x)||+\sup [f_{t+1}(x, y)-f_t(x, y)]$, such that Line 667 (Lemma G.3) in Appendix can be upper bounded by $\frac{2MT}{W}+L_0\sqrt{\frac{2T}{\mu_g}}\sqrt{\sum_{t=1}^T \sup |g_{t+1}(x, y)-g_{t}(x, y)|}+ \sum_{t=1}^T \sup [f_{t+1}(x, y)-f_t(x, y)]$; (3) Based on these, if we denote $V_g=\sum_{t=1}^T \sup |g_{t+1}(x, y)-g_{t}(x, y)|$ and $V_f=\sum_{t=1}^T \sup [f_{t+1}(x, y)-f_t(x, y)]$ to capture the function variations, we can have the overall regret as $O\left(\frac{T}{\beta W} + \frac{V_f}{\beta} + V_g + \frac{\sqrt{T V_g}}{\beta} \right)$. In this case, a sublinear regret will be achieved if both $V_g$ and $V_f$ are $o(T)$ for suitably selected $W$. As mentioned in our previous response, 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. For example, suppose $W= \omega(T)$ and the function variation of $f_t$ is very small, to achieve a regret of $O(T^{3/4})$, $H_{2,T}=O(T^{3/4})$ is sufficient, while we need a stricter condition on the variation of $g_t$, i.e., $V_g=O(T^{1/2})$. We will add the theorem and more detailed discussions on this in the final version per the reviewer’s suggestion. Once again, we do not use the terms $H_{2,T}$ and $V_{1,T}$ in 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. Q2: Given your strategy to reduce the number of loops for optimizing $y$, could a similar approach be applied to $v$? A2: This does not appear to be the case because the objective functions in the offline setting such as in [1]-[3] are **time-invariant**, while the objective functions in the online setting (such as ours) are **time-varying**. Hence, in the offline setting, it is easier to control the error even with only one step conjugate gradient estimate of $v^*$ because of the offline time-invariant setup. In contrast, because of the time-varying nature of the objective function in the online setting, controlling the error with only one step conjugate gradient becomes extremely difficult. More details are provided below to explain this difficulty. (1) In the current work, we seek to reduce the number of steps for updating $y_t$ so that our algorithm can also work under limited knowledge of the function $g_t$. But this can result in a large estimation error for the hypergradient at each step. To control this error, we carefully control the estimation errors of $y_t^*$ and $v_t^*$ together, such that the summation of $||y_t^*(x_t)-y_{t+1}||^2$ and $||v_t^*-v_t^Q||^2$ will decay in order to achieve a sublinear regret under function variations. We achieve this by increasing the estimation accuracy for $v_t$ (note that this does not require more information about the function $g_t$), which compensates the large estimation error of $y_t^*$ due to a single step update. (2) When further reducing the number of update steps for $v_t$, we still need to jointly control the estimation error of $y_t^*$ and $v_t^*$. But the strategy we take above doesn’t work anymore since the estimation error of $v_t^*$ is also large. Besides, the warm start strategy used in offline bilevel optimization will not work due to the time-varying functions in online bilevel optimization. In particular, the estimation error of $v_t^*$ depends on both the update of $x_t$, $y_t^*$ and the function variations including both outer-level function $f_t$ and inner-level function $g_t$. This will largely complicate the analysis and make achieving a sublinear regret highly nontrivial. Investigating this problem is very interesting but is worth to be considered as an independent future work. Finally, if our response resolves your concerns to a satisfactory level, we kindly ask the reviewer to reconsider raising the score of your evaluation. Certainly, we are more than happy to address any further questions that you may have during the discussion period. We thank the reviewer again for the helpful comments and suggestions for our work.
Dear Reviewer ouS8, Since the author-reviewer discussion period has started for one week, and will end very soon. Could you please check our response at your earliest convenience? This way, if you have further questions, we will still have time to respond before the discussion period ends. We thank the reviewer very much in advance for your time and efforts.
Thank you so much for all the valuable comments and raising the score!
Decision
Accept (poster)