On the Convergence Theory for Hessian-Free Bilevel Algorithms
Authors: Daouda Sow
Kaiyi Ji
Yingbin Liang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Convergence Rate
Computational Complexity
Jacobian Matrix
Stochastic Algorithm
Bilevel Optimization

Abstract: Bilevel optimization has arisen as a powerful tool in modern machine learning. However, due to the nested structure of bilevel optimization, even gradient-based methods require second-order derivative approximations via Jacobian- or/and Hessian-vector computations, which can be costly and unscalable in practice. Recently, Hessian-free bilevel schemes have been proposed to resolve this issue, where the general idea is to use zeroth- or first-order methods to approximate the full hypergradient of the bilevel problem. However, we empirically observe that such approximation can lead to large variance and unstable training, but estimating only the response Jacobian matrix as a partial component of the hypergradient turns out to be extremely effective. To this end, we propose a new Hessian-free method, which adopts the zeroth-order-like method to approximate the response Jacobian matrix via taking difference between two optimization paths. Theoretically, we provide the convergence rate analysis for the proposed algorithms, where our key challenge is to characterize the approximation and smoothness properties of the trajectory-dependent estimator, which can be of independent interest. This is the first known convergence rate result for this type of Hessian-free bilevel algorithms. Experimentally, we demonstrate that the proposed algorithms outperform baseline bilevel optimizers on various bilevel problems. Particularly, in our experiment on few-shot meta-learning with ResNet-12 network over the miniImageNet dataset, we show that our algorithm outperforms baseline meta-learning algorithms, while other baseline bilevel optimizers do not solve such meta-learning problems within a comparable time frame.

On the Convergence Theory for Hessian-Free Bilevel Algorithms
Daouda A. Sow Department of ECE
Kaiyi Department of CSE University at Buffalo kaiyi fibiffff@bufaall... edu
Yingbin Liang Department of ECE The Ohio State University liang. 8898osu. edu
The Ohio State University sow. 53@osu......mmm edu
Abstract
Bilevel optimization has arisen powerful tool in modern machine learning. However, due to the nested structure of bilevel optimization, even gradient-bas based methods require second-order derivative approximations via Jacobian- or/and Hessian-vector computations, which can be costly and unscalable practice. Recently, Hessian-free bilevel schemes have been proposed to resolve this issue, where the general idea is to use zeroth- or first-order methods to approximate the full hypergradient of the bilevel problem. However, empirically observe that such approximation can lead to large variance and unstable training, but estimating partial component of the hypergradient turns
only the response Jacobian matrix out to be extremely effective. To this end, we propose a new Hessian free method, which adopts the peroth-order-Hi method approximate the response Jacobian matrix via taking difference between two optimization paths. Theoretically, we provide the convergence rate analysis for the proposed algorithms, where our key challenge is to characterize the approximation and smoothness properties of the vajectory-dependent estimator, which first known convergence rate result for this type of Hessian-free bilevel algorithms. Experimentallyy we demonstrate that the proposed algorithms outperform bascline bilevel optimizers on various bilevel problems. Particularly, in our experiment on few-shot meta-learning with ResNet- network over the minilmageNet dataset, we show that our algorithm outperforms baseline meta-learning algorithms, while other baseline bilevel optimizers do solve such meta-learning problems within comparable time frame.
be of independent interest. This is the
Introduction
Bilevel optimization has recently arisen as powerful tool to capture various modern machine learning
problems, including meta-learning 12 49 24 36), hyperparamater optimization [12, [1], neural
architecture search [35] (58, signal processing [10, etc. Bilevel optimization generally takes the
following mathematical form:
min ((x) = ZERY
s.t.
y y²(x)
arg min g(x, y),
(1)
yERd
where the outer objective f R x Rd + R is continuously differentiable function and the inner objective g IR d R is twice differentiable.
Gradient-based methods have served as popular tool for solving bilevel optimization problems. Two types of approaches have been widely used: the iterative differentiation (TTD) method 11 51 and the approximate iterative differentiation (AID) method 77] 47 42). Due to the bilevel structure of the problem, even such gradient-bass based methods typically involve second-order matrix computations,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

500
Partial estimation Full estimation
35
Partial estimation
30
Full estimation
Ovter loss
23
20
200
25
10
100
100
20
30
40
50
10
20
30
40
50
60
70
Steps
Stops
Figure 1: Hyper-representation (HR) with linear (left)/-llayer net (right) embedding model.
because the gradient of (xx) ) in eq. ( (which is called hypergradient) involves the optimal solution of
the inner function. Although the ITD and AID methods often adopt Jacobian- or/and Hessian- -eector implementations, the computation can still be very costly in practice for nigh-dimensional problems with neural networks.
To overcome the computational challenge of current gradient-based methods, variety of Hessian-fiee free bilevel algorithms have been proposed. For example, popular approaches such FOMAMI. 9 35
ignores the calculations of any second-order derivatives. However, such a trick has no guaranteed performance and may suffer from inferior test performance [ 8. In addition, when the outer-level function fzz y) depends only on variable, c.g., in some hyperparameter optimization applica- tions [1). it can be shown from eq. (2) that the hypergradient (2) vanishes if we eliminate all second-order directives. More recently, several zeroth-order methods [88] have been proposed
to approximate the full hypergradient (T(x). In particular, ES-MAML [54] and HOZOG [[8] use zeroth-order methods to approximate the full hypergraident based on the objective function evaluations.
However, as demonstrated in Figure (also see our further experiments in Section 4 we empirically observe that such full hypergradient estimation can encounter large variance and inferior perfor- mance, whereas a new reroth-order-like method PZOBO with partial hypergradient estimation (as we propose below) performs significantly better.
Encouraged by such an interesting observation, we propose a simple but effective Hessian-free method named PZOBO, which stands for partial zeroth-order- bilevel optimizer. PZOBO uses seroth-order-lik approach approximate only the response Jacobian By (x) ähr (which is the major computational bottleneck of hypergradient) based on the difference between two gradient- based optimization paths. The remaining terms hypergradient can simply be calculated by their analytical forms. In this way. PZOBO avoids the large variance of the zeroth-order method for estimating the entire hypergradient, but still enjoys its Hessian-free advantage. We further show that PZOBO admits an easy extension to the large-scale stochastic setting by simply taking small-batch gradients without introducing any complex sub-procedure such as the Neumann Series (NS) type of construction in 23 Experimentally, PZOBO and its stochastic version PZOBO-S achieve superior performance compared to the current baseline bilevel optimizers, and such an improvement is robust across various bilevel problems. In particular, the few-shot meta-nca problem over ResNet- 12 network, PZOBO outperforms the state-of-the--as optimization based meta learners (not necessarily bilevel optimizers), while other bilevel optimizers do not scale to solve such meta-learning problems within a comparable time frame.
Furthermore, our zeroth-order-like response Jacobian estimator in PZOBO takes the difference between two optimization-base trajectories, whereas the vanilla zeroth-order method uses function value difference at two close points for approximation. Such difference complicates the (a) Conventional zeroth-order analysis often requires
analysis of PZOBO from three perspectives. some Lipshitzness properties (c.g.. smoothness) of the objective function. whereas they may not hold for the optimization-bann based output of our response Jacobian estimator. (b) It is unclear the trajectory-based Hypergradient estimator has bounded error at each iteration, which is critical in the convergence analysis for bilevel optimization 14 23 22 (c) Such characterizations are more challenging for stochastic settings because the randomness along the trajectory needs to be considered.
Theoretically, we provide the convergence rate guarantee for both PZOBO and PZOBO-S. To best of our knowledge, this is the first known non-asymptotic performance guarantee for Hessian-free bilevel algorithms via zeroth-order-like approximation. Technically, contrast to the conventional analysis of the zeroth-order estimation on the smoothed blackbox function values, we develop

---

tools to characterize the bias, variance, smoothness and boundedness of the proposed response Jacobian estimator via a recursive analysis over the gradient-based optimization path, which can be of independent interest for zeroth-order estimation based bilevel optimization.
1.1 Related Work
Bilevel optimization. Bilevel optimization has been studied for decades since [5]. variety of bilevel
optimization algorithms were then developed, including constraint- based approaches [21] 52 45)
approximate implicit differentiation (AID) approaches 7 47 16 42 and iterative differentiation
(ITD) approaches 7 44 9 [T
49 39 These methods often suffer from expensive computations
of second-order information (e.g., Hessian vector products). Hessian- free algorithms were recently proposed based on interior-poin pointt method 37 and zeroth-order approximation [18] 54).
[3 proposed
an initialization auxiliary method to deal with nonconvex inner problem. However, these methods
may suffer from either costly procedure in regularization parameter tuning 37
38 or large
estimation variance [8 54] in supervised learning. This paper proposes a simpler and more efficient Hessian free approach via exploiting the benign structure of the hypergradient and zeroth-order-lin like response Jacobian estimation. Recently, the convergence rate has been established for gradient- brased (Hessian involved) bilevel algorithms analysis for the proposed zeroth-order-like bilevel approach.
17
28
49 25]. This paper provides new convergence
Stochastic bilevel optimization. 11
28 22 proposed stochastic gradient descent (SGD) type bilevel optimization algorithms by employing Neumann Series for flessian-invers-veer approximation. 20 (7 then leveraged momentum-based variance reduction to further reduce the computational complexity of existing SGD-type bilevel optimizers from ((c to O(c-1.5). However, these methods often do not scale well in large models due to the Hessian or Hessian inverse computations. In this paper, we propose a stochastic Hessian-fire method, which eliminates the computation of all eccond-order information.
Recent works [29] 30 6
19
Bilevel optimization applications. Bilevel optimization has been employed in various applications
such as few-shot meta-learning [53 12
59
24 27), hyperparameter optimization [11] 43 51]
neural architecture search [35] [8] etc. For example. [43] models the response function itself as a neural network (where each layer involves affine transformation of typerparameters) using the Self-Tuning Networks (STNs). An improved and more stable version of STNs was further proposed in 3]. which focused on accurately approximating the response Jacobian rather than the response function itself. This paper demonstrates the superior performance of the proposed Hessian free bilevel optimizer with guaranteed performance in meta-leaming and hyperparameter optimization.
Zeroth-order methods and applications. Zeroth-order optimization methods have been studied for long time. For example, [66 proposed an effective zeroth-order gradient estimator via Gaussian smoothing. which was further extended to the stochastic setting by [13] Such a technique has exhibited great effectiveness in various applications including meta-reinforcement lcarning [54), hyperparameter optimization [18), adversarial machine learning [26] 40), minimax optimization [41 (6), etc. This paper proposes novel Jacobian estimator for accelerating bilevel optimization based on an idea similar to zeroth-order estimation via the difference between two optimization paths.
2 Proposed Algorithms
2.1 Hypergradients
The key step in popular gradient-base based bilevel optimizers is the estimation of the hypergradient (i.e., the gradient of the objective with respect to the outer variable r), which takes the following form:
(Φ) V. (2, (x)) + [x))) TV Vg (a:)
where the Jacobian matrix (z) (y)(a) E dddp, Following [42]. it can be seen that (x(x) contains two components: the direct gradient v y (x)) and the indirect gradient Jx) Vyf((z, y² (z)). The direct component can be efficiently computed using the existing au- tomatic differentiation techniques. The indirect component, however, is computationally much
Vigg (z, y (x)) V. V,V ng (s, y (z)) (if Vigg (x, y" (x)) is invertible). which contains the Hessian inverse and the second-order mixed derivative. Some approaches mitigate the issue by designing Jacobian-vector and Hessian-vector
more complex, because (x(x) takes the form of (x))
3

---

Algorithm Partial
Bilevel Optimizer (PZOBO)
1: Input: lower- and upper-level stepsizes a, initializations æo I2 and yo R inner and outer iterations numbers K and N, and number of Gaussian vectors Q.
2: for 0, 2, .. K do
3: Set VL = y0, yk.
j = 1,.,, Q
4: for -- 1, 2,
do
5: Update y V2 a Vo
end
7: for -= Q do
8: Generate ux., = (0, 1) R.
9:
for = 2,.,... N do
10:
Update Vk.j = Vkg
aV a Vol + park vk.s)
11:
end for
Compute 0, th.s ot
12:
1
13:
end for
14: Compute (Tx) Vaf(oa, + 3 Egm (8,, Vof(ru, (i
was
15:
Update 2k+1 = I6 - (z4(
16:
end for
to replace second-order computations. But the computation is still costly for high-dimensional bilevel problems such those with neural network variables. We next introduce the zeroth-order approach which is at the core for designing efficient Hessian-free bilevel optimizers.
products 47
2.2 Zeroth-Order Approximation
Zeroth-order approximation is powerful technique to estimate the gradient of function based on function values, when it is not feasible (such in black-box problems) or computationally costly to evaluate the gradient. The idea of the zeroth-orde method in [46] is to approximate the gradient of
general black-box function h R" + IR using the following oracle based only on the function values
<)(z;u) h(x + pu) h(x)
where u E R" is a Gaussian random vector and f > O is the smoothing parameter. Such an oracle can be shown to be unbiased estimator of the gradient of the smoothed function E,, [h(r jm)).
2.3 Proposed Bilevel Optimizers
Our key idea to exploit the analytical structure of the hypergradient in eq. (2) where the derivatives Vef y" (x)) and V (z, y" (x)) can be computed efficiently and accurately, and hence use the zero-order estimator similar to eq. (3) to estimate only the Jacobian [x),,, which the major term posing computational difficulty. In this way, estimation of the hypergradient can be much more accurate and reliable. In particular, our Jacobian estimator contains two ingredients: (i) for a given æ, apply algorithm solve the inner optimization problem and use the output y" (z); for example, the output y (z) of gradient descent steps of the inner problem can serve as an estimate for y" (z). Then IN (x) By (=)
approximation of
Bx serves as an estimate of J. (x)); and (ii) construct the
zeroth-order-lie Jacobian estimator IN (I;2)= E Rdxx for JN(x) as
IN (x; y.Vl (r + pu) y (x)
(4)
where E IRP Gaussian vector with independent and identically distributed (i.i..)) entries. Then for any vector E Rd, the Jacobian-vector product can be efficiently computed using only vector-vector dot product IN u) c = (6(z; u), v) u, where 6(æ; u) (2+nu)-
gd.
PZOBO: partial zeroth-order based bilevel optimizer. For the bilevel problem in eq. 1 we design an optimizer (see Algorithm [
using the Jacobian estimator in eq. 4 which we call as the PZOBO algorithm. Clearly, the zeroth-order estimator is used only for estimating partial hypergradient. At each step & of the algorithm, PZOBO runs an step full GD to approximate y (æx). PZOBO then

---

samples Q Gaussian vectors {uE, C. Q). and for each sample Wk,j runs an N-step full GD approximate y (zg p(lk,)), and then computes the Jacobian estimator IN(2;: uk.)) as in eq. (4). Then the sample average over the Q estimators is used for constructing the following hypergradient estimator for updating the outer variable x.
(1x))) V Vzf(z 3K
Q Σj= (ax: U V (Z 3k
V V yk Q Ej= (ō(rk: uk V y (Tks Uk uk.j-
(S)
In our experiments (see Section 4). we choose small constant-level Q = (1) (e.g., Q = in most applications with neural nets) due much better performance. Our convergence guarantee holds for this case, as shown later.
Computationally, in contrast to the existing AID and ITD bilevel optimizers 47 12 17 that contains the complex Hessian- and/or Jacobian-vector product computations, PZOBO has only gradient com- putations and becomes Hessian-frree, and hence is much more efficient as shown in our experiments.
PZOBO-S: stochastic PZOBO. In machine learning applications, the loss functions f. in eq. often take finite-sum forms over given data Dn,m = -Ei, Sg 1.... n. 1, ... m) as below.
f(x, v) = E.= Et). g(x,)) = i/ E G(z.v:
(6)
where the sample sizes n and m are typically very large. For such large-scale scenario, we design stochastic PZOBO bilevel optimizer (see Algorithm Qn Appendix A), which we call as PZOBO-S.
Differently from Algorithm [ which applies GD updates to find y (Izz), PZOBO-S uses N stochas- tic gradient descent (SGD) steps to find {Y: I.,..... Y } to the inner problem, each with the outer variable set be r& + jolkk.j- Note that all SGD runs follow the same batch sampling path
SN, - }. The Jacobian estimator IN (zgg ux.j) can then be computed as in eq. At the outer level, PZOBO-S samples new batch DD independently from the inner batches {So, .... SN-13 } to evaluate the stochastic gradients V, F(r,, Y2 DD) and F( Y (D)). The hypergradient
(Tx()) is then estimated as
(Φ((z)= V, YE E9 (8(0); P(r., ;E wn.j-
3 Main Theoretical Results
3.1 Technical Assumptions
In this paper, we consider the following types of objective functions.
Assumption 1. The inner function g(z, v) is My -trsonnggly convex with respect to y and the outer function (x. y) is possibly nonconvex w.r.. For the finite-sum case, the same assumption holds for functions Gar,
(r., y. () and V:
The above assumption on f.g g has also been adopted in 14 28 57 In fact, many bilevel machine learning problems satisfy this assumption. For example, few-shot meta-learning, the task task-specific parameters are likely the weights of the last classification layer so that the resulting bilevel problem has strongly-conve inner problem [48] 37).
Assumption 2. Let w = (I. The gradient Vg(w) is Li-Lipschitz continuous, i.e., for any W1, W2, VV((w) - Vg(w2)ll S Lg [|w - wall; further, the derivatives Vig(w) and V, V yg(w)) are and T -ippschttz continuous, i.e, (Vz)) - (ig((z2)l & pl[wy w2l and |V (w1) V. V.g (g((w)) w2) || 1 T|| - w2ll The same assumptions hold for G(w;; Ç) in the finite-umm case.
Assumption 3. Ler w = (I, y). The objective f(w) and its gradient V f(()) are M- and Lipischht continuous, i.e., for any W1, W2, [f(w) f(w2) < M ||l - w/|| [f(w1) vf(wz)) <
w2|l, Lr||w] -alll which hold for F(w; {) in the sumite-sum case.
Assumption For the fimite-sum case, the gradient VG(w;; () has bounded variance condition, iee, Eç V[ Vg(w) 122 < o² for some constant 0.
5

---

3.2 Convergence Analysis for PZOBO
Differently from the standard zeroth-order analysis for blackbox function, here we develop new techniques to analyze the
Jacobian estimator that depends on the entire inner optimization trajectory, which unique bilevel optimization. We first establish the following important proposition which characterizes the Lipshitzness property of the approximate Jacobian matrix IN (z)
(x) dz
Proposition 1. Suppose that Assumptions and 2 hold. Let La = Po max L Lg Then, the Jacobian IN(x) x)) is Lisschitz continuous with constant L.: [[Tx( IN (x2))l La - x22 Vri, 32 E TR.
x with (
We next show that the variance of hypergradient estimation can be bounded. The characterization of the estimation bias can be found in Lemma in the appendix.
Proposition 2. Suppose that Assumptions 7 can be upper-bounded
and hold. The hypergradient estimation variance
E (D(()) V o (a- (
- pdp Q
P Q
+
where [-]-] is conditioned on By and taken over the Gaussian vectors {uk. ::= 1,,,,.,.Q1)
Proposition 2 upper bounds the hypergradient estimation variance, which mainly arises due the estimation variance of the Jacobian matrix Js by the proposed estimator JN. via three types of variances: (a) the approximation variance between JN and J. via inner-loop gradient descent, which decreases exponentially w.r.t. the number of inner iterations due to the strong convexity of the inner objective; (b) the variance between our estimator and the Jacobian Jj of the smoothed output E.y (Ix + yeu), which decreases sublinearly w.r.. the batch size Q, and (c) the variance between the Jacobian IN and T,r. which can be controlled by the smoothness parameter μ..
By using the smoothness property in Proposition I and the upper bound in Proposition we provide the following characterization of the convergence rate for PZOBO.
Theorem 1 (Convergence of PZOBO). Suppose that Assumptions inner- and outer-loop stepsizes respectively as a S 1, and 3 0 WR Further, set = (1) and
and hold. Choose the
J 0 VKVpp Then, the iterates T&k for 0,..., K of P%0BO satisfy
( S 5 VK + (1-a)H))
Theorem I shows that the convergence rate of PZOBO is sublinear with respect to the number K of outer iterations due to nonconvexity of the outer objective, and linear (i.e., exponentially decay) with respect to the number N of inner iterations due to the strong convexity.
Theorem I also indicates the following features that ensures the efficiency of the algorithms. (i) The batch size Q of the Jacobian estimator can be chosen as constant (in particular Q as in our experiments) so that the computation of the ES estimator is efficient. (ii) The number of inner iterations can be chosen to be small due to its exponential convergence, and hence the algorithm can run efficiently. (iii) PZOBO requires only gradient computations converge, and eliminates Hessian- and Jacobian- vector products required by the existing AID and ITT based bilevel optimizers ([47 12 17. Thus, PZOBO is more efficient particularly for high-dimensional problems.
3.3
Convergence Analysis for PZOBO-S
In this section, we apply the stochastic algorithm PZOBO-S to the finite-sum objective in eq. (6 and analyze its convergence rate. The following proposition establishes upper bound the estimation error of Jacobian J. by IN Ox Proposition 3. Suppose that Assumptions
N where Y is the output of N inner SGD updates.
Z and hold. Choose the inner-loop stepsize as Ltpp'' where max L,, Lg). Then, we have:
JN Jzl SNN + c,
L 1
AL+H,, P110a,,)
(L+t,) (L-Pp

---

(a) Outer loss, d 128
(d) Outer loss
500
P2380
H020G
30
PZ0B0
225
300
AID-PP
Door
ITD-A
g20
AID-CG
200
35
AID-FF
100
5-
0
0.3
0.3
0.4
0.5
10
15
20
Running
Running
(b) Outer loss, d 256
(c) Hypergradient norm
P2080
800
H020G
H0206
AID-CG
600
ARD-P
AID-FP
ITD
200
Running time
(c) PZOBO-N: N inner steps
(f) PZOBO-N: N inner steps
175
25
150
P2OBG-5
125
PZO8G-10
100
Cuter
15
P2OBO-20
P2080-10
10
P208O-30
5-
0-
6.05
0.10
0.35
0.20
0.25
2
Running time
Running
Figure 2: First column: HR with linear embedding model. Second column: HR with two-layer net.
where A, 1, and C2 < are constants (see Appendix for their precise forms).
We next show that the variance hypergradient estimation bounded.
Proposition 4. Suppose that Assumptions 7 2 and Set the inner-loop stepsize where L L Lgg. Then, we have:
2
L+
E ()))) (xxx)) S ((1 (1)- +
ap)
1
12d22
pddpt Q
Dj
where S and D, are the sizes of the inner and outer mini- miii-batches, respectively.
Based on Propositions T. and 4 we characterize the convergence rate for PZOBO-S.
Theorem 2 (Convergence of PZOBO-S). Suppose that Assumptions 7 and Ahold. Set the inner-
and outer-loop stepsizes respectively
Ltp, 2_ and B O VR where L max Lg
Further, set Q = O(1,, D, = 01), and μ O 1 of PZOBO-S satisfy:
Then, the iterates It, = O,... K - -
Kdp
kiz B [ < 0o ( (1- +1))
Comparing to the convergence bound in Theorem | for the deterministic algorithm PZOBO, Theo- remb 2 for the stochastic algorithm PZOBO-S captures one more sublinearly decreasing error term due to the sampling of inner batches to estimate the objectives. Note that the sampling of outer batches has been included into the sublinear decay term w.r.t. the number K of outer-loop iterations.
4 Experiments
We validate our algorithms in four bilevel problems: shallow hyper-representtaion (HR) with linear/2-layer net embedding model synthetic data, deep HR with LeNet network (32 MNIST
7

---

2.0
0.8
Accurar
0.7
PZOBO $
Outer loss
1.5
PZOBO S
0.6
AID-FP
AID-FP
0.5
AID-CG
1.0
AID-CG
StocBIO
stocBlO
0.5
50
100
150
200
250
300
350
400
50
100
150
200
250
300
350
400
Running time
Running time
(a) Accuracy outer data
(b) Outer loss value
Figure 3: Deep HR on the MNIST dataset.
dataset, few-shot meta-learning with ResNet-12 on minilmageNet dataset, and hyperparameter optimization (HO) the 20 Newsgroup dataset. We run all models using single NVIDIA Tesla P100 GPU. All running time are in seconds.
4.1 Shallow Represeeppresnttaioon on Synthetic Data
The repeesteprrsnnntttoon (HR) problem [2 17
searches for regression (or classification) model following two-phased optimization process. The inner-level identifies the optimal linear regressor parameters w, and the outer level solves for the optimal embedding model (i.e., representation) parameters A. Mathematically. the problem can be modeled by the following bilevel optimization:
min f(A) XERM
[TT(Xi;)w'' 1111 w² arggin weRd
[T(X2; A)w Y2 12 + 10/l
(8)
2m1
2nz
where X2 E 1 and X1 Rm are matrices of synthesized training and validation data, and Y2 22 Y1 E I are the corresponding response vectors. In the case of shallow HR, the embedding function T(-; is either linear transformation or two-layer network. We generate data matrices X1 X2 and labels Y,, Y1 following the same process in T7
We compare PZOBO algorithm with the baseline bilevel optimizers AID-FP, AID-CG, ITD-R, and HOZOG (see Appendix [.. for details about the baseline algorithms and hyperparameters used). Figure show the performance comparison among the algorithms under linear and two-layer embedding models. It can be observed that for both cases, our proposed method PZOBO converges faster than all the other approaches, and the advantage of PZOBO becomes more significant in Figure (d), which under higher-dimensione model of two-layer net. In particular, PZOBO outperforms the existing ES-based algorithm HOZOG. This is because HOZOG uses the ES technique to approximate the entire hypergradient, which likely incurs large estimation eтror. In contrast, our PZOBO exploits the structure of the hypergradient and only estimate the response Jacobian so that the estimation of hypergradient is more accurate. Such an advantage is more evident under two-layer model, where HOZOG does not converge as shown in Figure (d). This can be explained by the flat hypergradient norm as shown in Figure which indicates that the hypergradient estimator in HOZOG fails to provide a good descent direction for the outer optimizer. Figure (c) and (f) further show that the convergence of PZOBO does not change substantially with the number N of inner GD steps, and hence tuning of in practice is not costly.
4.2 Deep Repreeeeerrsnntttionn on MNIST Dataset
In order to demonstrate the advantage of proposed algorithms in neural net models, perform deep reprrrrepreenntation to classify MNIST images by learning an entire LeNet network. The problem formulation is described in Appendix
Figure B compares compares the classification accuracy on the outer dataset Dout between our PZOBO-S and other stochastic baseline bilevel optimizers including two AlD-based stochastic algorithms AID-FP and AID-CG, and a recently proposed new stochastic bilevel optimizer stocBiO which has been demonstrated to exhibit superior performance. Note that ITD and HOZOG are not included in the comparison, because there have not been stochastic algorithms proposed based on these approaches in the literature yet. Our algorithm PZOBO-S converges with the fastest rate and attains the best

---

1.0
Algorithm
67%
69%
0.8
PZOBO
2.0
2.8
Accuracy
0.7
MetaOptNet
20+
20+
0.6
ProtNet
3.5
4.4
PZOBO-S-5
ANIL
6.3
MAML
9.7
PZOBO-S-20
0.0
2.5
5.0
7.5
10.0
12.5
15.0 17.5
Running time
Figure 4: Left plot: Deep HR on the MNIST dataset with different inner steps number N. PZOBO- S-N means PZOBO-S with N inner steps. Right table: Time to reach X% accuracy for few-shot learning experiments with ResNet-12.
accuracy with the lowest variance among all algorithms. Note that PZOBO-S is the only bilevel method that is able attain the same accuracy of 0.98+ obtained by the state-of-the-art training of all parameters with one one-phased optimization on the MNIST dataset using the same backbone network. All other bilevel methods fail to recover such a level of performance, but instead saturate around an accuracy of 0.93. Further, the plot Figure indicates that the convergence of PZOBO-S does not change substantially with the number N of inner SGD steps. This demonstrates the robustness of our method when applied to complex function geometries such as deep nets.
4.3 Few-Shot Meta-Learning over MinilmageNet
We study the few-shot image recognition problem, where classification tasks Tú, i =1, 1,... m are sampled over distribution Py. In particular, consider the following commonly adopted meta- learning setting (e.g., [8], where all tasks share common embedding features parameterized by ø, and each task has its task-specific parameter wo; for 1, ..., m. More specifically, we e to be the parameters of the convolutional part of a deep CNN model (e.g.. ResNet-12 network) and includes the parameters of the last classification layer. All model parameters (é, w) trained following a bilevel procedure. In the inner-loop, the base learner of each task T: fixes & and minimizes its loss function over training set S, to obtain adapted parameters w At the outer stage, the meta-learner computes the test loss for each task Ti using the parameters (ø, w²) over a test set D, and optimizes the parameters & of the common embedding function by minimizing the meta-objective fmeta over all classification tasks. The detailed problem formulation is given in Appendix E.4
65
65
accuracy
accurasy
55
55
PZOBO
ProtoNet
45
MetaOptNet
PZOBO
ANIL
ANIL
MAML
MAML
35
5000
10000
15000
20000
25000
500
1000
1500
2000
2500
3000
Running time
Running time
(a) Test accuracy (ResNet-12)
(b) Test accuracy (CNN4)
Figure 5: 5way-5shot few-shot classification on the minilmageNet dataset on single GPU. Left plot: Test accuracy (ResNet-12), Right plot: Test accuracy (CNN4)
We conduct few-shot meta- learning on the minilmageNet dataset (55] using two different backbone networks for feature extraction: ResNet-12 12 and CNN4 [55]. The dataset and hyperparameter details
can found in Appendix [E.4] We compare our algorithm PZOBO with four baseline methods for few-shot meta-learning MAMI [9, ANIL 48 MetaOptNet [3 and ProtoNet (53] Other bilevel optimizers are not included into comparison because they do not solve the problem within comparable time frame. Zeroth-order ES-MAML [54] is not included because it exhibits large

---

variance and cannot reach desired accuracy. Also note that since ProtoNet and MetaOptNet are usually presented in the ResNet setting, and are not relevant in smaller scale networks, we include them into comparison only for our ResNet-12 12 experiment. We run their efficient Pytorch Lightning implementations available at the learn2learn repository
Figure a) and (b) show that our algorithm PZOBO converges faster than the other baseline meta- learning methods. Also, Comparing Figure 5 a) and (b), the advantage of our method over the baselines MAML and ANIL becomes more significant as the size of the network increases. Further, the table Figure 4 shows that MetaOptNet did not reach 69% accuracy after 20 hours of training with ResNet- 12 network. In comparison, our PZOBO is able to attain 69% in less than three hours, which is about 1.5 times less than the time taken for ProtoNet reach the same performance level. Both PZOBO and ProtoNet saturate around 70% accuracy after 10 hours of training.
4.4 Hyperparameter Optimization
Hyperparameter optimization (HO) is the problem of finding the the best hyperparamters (either representational or regularization parameters) that yield the optimal value of some criterion of model quality (usually validation loss unseen data). HO be posed bilevel optimization problem in which the inner problem corresponds to finding the model parameters by minimizing training loss (usually regularized) for the given hyperparameters and then the outer problem minimizes over the hyperparameters. Due to space limitations, we provide more complete description of the problem and settings in Appendix F
c.80
6./5
Valrdalion acturetyy
0.30
0.75
Valdddeen
0.65
P208O
HOZOG
HOZOG
0.00
AID-CG
AID-CG
0.55
AID-FP
0.65
AID-FP
REVERSE
REVERSE
0.2
0.4
0.5
0.8
10
12
0.25
0.50
0.75
1.50
1.25
1.50
1.75
2:30
2.5
Running time
Running time
Figure 6: Classification results on Newsgroup dataset. Left: number of inner GD step Right: number of inner GD steps N 10.
can be seen from Figure 6 our method PZOBO slightly outperforms HOZOG and converges faster than the other AID and ITD based approaches. We note that the similar performance for PZOBO and HOZOG can be explained by the fact that in HO, the hypergradient expession in eq. (5) contains only the second term (the first term is zero), which is very close the approximation HOZOG method. However, as we have seen in the HR experiments in Figure 2 PZOBO achieves much better performance than HOZOG. Thus, compared HOZOG, our PZOBO much more stable and achieves superior performance across many bilevel problems.
5
Conclusion
In this paper, we propose novel Hessian-free approach for bilevel optimization based on a zeroth- order-like Jacobian estimator. Compared to the existing such types of Hessian-free algorithms, approach explores the analytical structure the hypergradient, and hence leads to much more efficient and accurate hypergradient estimation. Thus, algorithm outperforms existing baselines in various experiments, particularly in nigh-dimensional problems. We also provide the convergence guarantee and characterize the convergence rate for proposed algorithms. We anticipate that approach and analysis will be useful for bilevel optimization and various machine learning applications.
Acknowledgements
The work of D. Sow and Y. Liang was supported in part by the U.S. National Science Foundation under the grant CCF-1900145 and CNS-2112471.
10

---

References
[1] A. Antoniou, H. Edwards, and A. Storkey. How to train your maml. arXiv:1810.005522, 2018.
arXiv preprint
[2] M. Amold. Mahajan, Datta, and Bunner. leam2leam, 2019. attps://githur: com/
Learrables/Leam2leamn
[3] J. Bae and R. B. Grosse. Delta-stn: Efficient bilevel optimization for neural networks using structured response jacobians. CoRR, abs/2010. 135114 2020.
[4] L. Bertinetto, J. F. Henriques, P. Torr, and A. Vedaldi. Meta-learning with differentiable closed-form solvers. In International Conference on Learning Representations (ICLR), 2018.
[5] Bracken and J. McGill. Mathematical programs with optimization problems in the constraints. Operations Research, 21(1):37-44, 1973.
[6] Chen, Sun, and W. Yin. single-timescale stochastic bilevel optimization method. arXiv preprint arXiv:2102.04671 2021.
[7] J. Domke. Generic methods for optimization-baser modeling. International Conference Artificial Intelligence and Statistics (AISTATS), page 318-326, 2012.
[8] A. Fallah, A. Mokhtari, and A. Ozdaglar. On the convergence theory of gradient-based model- agnostic meta-learning algorithms. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1082-1092. PMLR, 2020.
[9] C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proc. International Conference on Machine Learning (ICML), pages 1126-1135. 2017.
[10] R. Flamary, A. Rakotomamonjy, and G. Gasso. Learning constrained task similarities in graphregularized multi-task learning. Regularization, Optimization, Kernels, and Support Vector Machines, page 103, 2014.
[11] L. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and reverse gradient-bast based hyperparameter optimization. In International Conference on Machine Learning (ICML), pages 1165-1173, 2017.
[12] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. International Conference on Machine Learning (ICML), pages 1568-1577, 2018
[13] S. Ghadimi and G. Lan. Stochastic first-and grothh-odde methods for nonconvex stochastic programming. SIAM Journal Optimization, 23(4):2341-2366 2013.
[14] S. Ghadimi and M. Wang. Approximation methods for bilevel programming, arXiv preprint 2018.
[15] T. Giovannelli, G. Kent, and L. N. Vicente. Bilevel stochastic methods for optimization and machine learning: Bilevel stochastic descent and darts. arXiv preprint arX1v:2110.00644, 2021.
[16] S. Gould, B. Fernando, A. Cherian, P. Anderson, R. S. Cruz, and E. Guo. On differentiating parameterized argmin and argmax problems with application bi-level optimization. arXiv preprint arXiv:
2016.
[17] R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient computation. International Conference on Machine Learning (ICML)), 2020.
[18] B. Gu, G. Liu, Y. Zhang, X. Geng, and H. Huang. Optimizing large-scale hyperparameters via automated learning algorithm. CoRR, 2021.
[19] Guo, Xu, W. Yin, Jin, and Yang. On stochastic moving-average estimators for non-convex optimization. arXiv preprint arXiv:2104.14840, 2021.

---

[20] Z. Guo and T. Yang. Randomized stochastic variance-reduced methods for stochastic bilevel optimization. arXiv preprint arXiv:2105.02266: 2021.
[21] Hansen, B. Jaumard, and G. Savard. New branch-and-boumdt rules for linear bilevel program- ming. SIAM Journal Scientific and Statistical Computing, 13(5): (555)1194-121,, 1992.
[22] 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 preprint arXiv:2007.05170, 2020.
[23] K. Ji. Bilevel optimization for machine learning: Algorithm design and convergence analysis.
arXiv preprint arXiv:2 108.003300 2021.
[24] K. Ji, J. D. Lee, Y. Liang, and H. V. Poor. Convergence of meta-lcarning with task-specific adaptation over partial parameter. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[25] K. Ji and Y. Liang. Lower bounds and accelerated algorithms for bilevel optimization. arXiv preprint arXiv:2102.0340 002.0392. 2021.
[26] K. Ji, Z. Wang. Y. Zhou, and Y. Liang. Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. In International Conference Machine Learning (ICML), pages 3100-3109, 2019.
[27] K. Ji, J. Yang, and Y. Liang. Multi-step model-agnostic meta-learning: Convergence and improved algorithms. arXiv preprint arXiv:2002.07836 2020.
[28] K. Ji, J. Yang, and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design. International Conference on Machine Learning (ICML)), 2021.
(29] P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A momentum-assisted single-timescale stochastic approximation algorithm for bilevel optimization. arXiv e-prints, pages 21X2 2021.
[30] Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A near-optimal algorithm for stochastic bilevel optimization via Gouble-momentie arXiv preprint arXiv:2102.07367, 2021.
[31] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR), 2014.
[32] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 86(11):2278-2324 1998.
[33] K. Lee, Maji, Ravichandran, and S. Soatto. Meta-learning with differentiable convex optimization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10657-10665, 2019.
[34] R. Liao, Y. Xiong, E. Fetaya, L. Zhang, X. Yoon, KiJung Pitkow, R. Urtasun, and R. Zemel. Reviving and improving recurrent back-propagation. International Conference Machine Learning (ICML)), 2018.
[35] H. Liu, K. Simonyan, and Y. Yang. Darts: Differentiable architecture search. arXiv preprint /806 09055. 2018.
[36] R. Liu, J. Gao. J. Zhang, D. Meng, and Z. Lin. Investigating bi-level optimization for learning and vision from unified perspective: A survey and beyond. arXiv preprint 1511, 2021.
[37] R. Liu, X. Liu, X. Yuan, S. Zeng, and J. Zhang. A value-function--asee interior-point method for non-convex bi-level optimization. International Conference on Machine Learning (ICML), 2021.
[38] R. Liu, Liu, S. Zeng, and J. Zhang. Towards gradient-based bilevel optimization with non- convex followers and beyond. Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
12

---

[39] R. Liu, P. Mu, X. Yuan, S. Zeng, and J. Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. In International Conference on Machine Learning (ICML), 2020.
[40] S. Liu, B. Kailkhura, P.-Y. Chen, P. Ting, S. Chang, and L. Amini. Zeroth-order stochastic variance reduction for nonconvex optimization. In Advances in Neural Information Processing Systems (NeurlPS), pages 3731-3741, 2018.
[41] S. Liu, S. Lu, X. Chen, Y. Feng, K. Xu, A. Al-Dujaili, M. Hong, and U.-M. O' O'Reilly. Min- max optimization without gradients: Convergence and applications to black-box evasion and poisoning attacks. In International Conference on Machine Learning (ICML), pages 6282-6293, 2020.
[42] J. Lorraine, P. Vicol, and D. Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. International Conference on Artificial Intelligence and Staristics (AISTATS), page 1540-1552, 2020.
[43] M. Mackay, P. Vicol, J. Lorraine, D. Duvenaud, and R. Grosse. Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. In International Conference Learning Representations (ICLR), 2018.
[44] D. Maclaurin, D. Duvenaud, and R. Adams. Gradient- fraddeet-bbsedd hyperparameter optimization through reversible learning. In International Conference on Machine Learning (ICML), pages 2113-2122, 2015.
[45] G. M. Moore. Bilevel programming algorithms for machine learning model selection. Rensselaer Polytechnic Institute, 2010.
[46] Y. Nesterov and V. Spokoiny. Random gradient-free minimization of convex functions. Founda- tions of Computational Mathematics, pages 527-566, 2017.
[47] F. Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning (ICML), pages 737-746, 2016
[48] A. Raghu, M. Raghu, S. Bengio, and O. Vinyals. Rapid learning or feature reuse? towards un- derstanding the effectiveness of MAML. International Conference on Learning Representations (ICLR), 2019.
[49] A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine. Meta-learning with implicit gradients. In Advances in Neural Information Processing Systems (NeurIPS), pages 113-124, 2019.
[50] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma. Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 3(115):211-222 2015.
[51] A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots. Truncated tack-propagation for bilevel optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1723-1732, 2019.
[52] C. Shi, J. Lu, and G. Zhang. An extended kuhn tucker approach for linear bilevel programming. Applied Mathematics and Computation, 162(():51-63, 2005.
[53] J. Snell, K. Swersky, and R. Zemel. Prototypical networks for few-shot learning. In Advances in Neural Information Processing Systems (NIPS), 2017.
[54] X. Song, W. Gao, Y. Yang, K. Choromanski, A. Pacchiano, and Y. Tang. Es-maml: Simple hessian-free meta learning. In International Conference on Learning Representations (ICLR), 2019.
[55] O. Vinyals, C. Blundell, T. Lillicrap, and D. Wierstra. Matching networks for one shot learning. In Advances in Neural Information Processing Systems (NIPS), 2016.
[56] T. Xu, Z. Wang. Y. Liang, and H. V. Poor. Gradient free minimax optimization: Variance reduction and faster convergence. arXiv preprint arXiv:2006.09332 2020.
13

---

[57] J. Yang, K. Ji, and Y. Liang. Provably faster algorithms for bilevel optimization, arXiv preprint S14V::2000.04662, 2021.
[58] M. Zhang, S. Su, S. Pan. X. Chang, E. Abbasnejad, and R. Haffari. idarts: Differentiable architecture search with stochastic implicit gradients. arXiv preprint arXiv:2106. 2021.
[59] D. Zügger and S. Günnemann. Adversarial attacks graph neural networks via meta learning. In International Conference on Learning Representations (ICLR), 2019.
14


Reviews:
[{"review_id": "QsmR1Sg2iPZ", "reviewer": "Reviewer_2qAw", "summary": "This work focuses on the Hessian-free bilevel optimization, which is a timely topic in machine learning, and has been widely used in many important applications such as neural architecture search, hyperparameter optimization, reinforcement learning, etc. In particular, the authors study the convergence performance and efficiency of Hessian-free bilevel algorithms via zeroth-order estimation, which have shown promise in many deep learning applications such as ES-MAML in meta-reinforcement learning, HOZOG in hyperparameter optimization. The authors first address an important variance and convergence issue of existing zeroth-order method, and propose to estimate only the response Jacobian of the hypergradient using direct forward propagation without any backpropagation. They further provide a convergence rate analysis for the resulting Hessian-free PZOBO method with partial hypergradient estimation and its stochastic version PZOBO-S. Extensive experiments support the convergence theories and justify the effectiveness of the designs in various applications. ", "questions": "This method uses the gradient descent for both the inner and outer updates. It would be good to know if the accelerated gradient methods such as Nesterov’s momentum can be used to further improve the convergence and complexity performance.  \n\nThe algorithm allows multiple random smoothing vectors, i.e., Q>1, which may be useful for reducing the estimation variance. I see that all experiments adopts the choice Q=1. Can the authors provide an explanation on why this choice is good? Furthermore, an experiment  on comparison of different Q should be provided.\n\nPlease add the units to x-axis of Figure 2(a), 2(b), and 2(c). For (a) and (b), the running time scales with 5, 10, 15, 20, but (c) scales with 0.5, 1, 1.5, 2. Please make the consistence accordingly.\n", "limitations": "authors adequately addressed the limitations and potential negative societal impact of their work\n\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work is generally written and motivated well. The finding that partial zeroth-order hypergradient estimation can improve the variance and convergence is a good contribution to Hessian-free bilevel optimization, in particular for the supervised scenarios. The proposed zeroth-order-like response Jacobian estimator enables a simple implementation in practice, in particular admitting a very easy extension to the stochastic case. This is kind of important because for conventional AID or ITD types of methods, more involved procedures such as Taylor expansion types of stochastic estimation are needed for hypergradient computations. \n\nThe analysis developed in this paper seems to be the first convergence rate analysis for zeroth-order bilevel optimization. Although the high-level idea comes from the zeroth-order optimization, there are indeed some differences under this bilevel structure. For example, from my reading, the smoothness property of the N-step output of the lower-level gradient-based algorithm established in Proposition 1 needs to conduct a recursive analysis on the entire gradient path, and the error characterization of stochastic Jacobian estimator needs to take the randomness of points in the path into consideration. Such analysis seems nontrivial to me. \n\nExperiments seem to be comprehensive, on different applications such as representation learning, meta-learning, hyperparameter optimization. The proposed method indeed outperforms other bilevel optimizers quite a lot, in particular when the network size is large as in the meta-learning experiments.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "AesyxwUUbdy", "reviewer": "Reviewer_eYhq", "summary": "The paper presents an algorithm and its stochastic extension to finite sums for solving smooth bilevel optimization problems which avoid computing the hessian associated to the lower level problem by instead using zeroth order oracles. Rather than approximate the entire gradient of the entire loss function in the upper level problem using zeroth order methods, the proposed algorithms only approximate the gradient of the solution mapping for the lower level problem with zeroth order methods, reducing variance and improving the method. Convergence guarantees are proven and four numerical experiments are performed that suggest the method is competitive with some contemporary methods.", "questions": "It's not clear what is the dimension of the hyperparameter vector in the various experiments; is p=1 in 4.1, for example? Even after searching the appendix I couldn't find it written what is the dimension of the hyperparameter vector for the applications.\n\nOn line 265 a bilevel optimization problem for an application is given - is the lower level problem really strongly convex and smooth here? \n\nOn line 131 you use that g is twice differentiable but you have only assumed it's C1?", "limitations": "One limitation is that there are many assumptions to apply the results. The assumptions are clearly stated which help alleviate this issue but the authors should address the limitations imposed by the assumptions in the numerical experiments because not made clear that the assumptions needed to apply the theorems are met. I think you should be explicit when/if the assumptions are being broken and whether or not the theorems that were proved actually apply to these practical examples. In the appendix it's sometimes mentioned when the lower level problem is strongly convex but I think for the neural network examples it could be nonsmooth and this should be mentioned as a limitation.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I found the paper to be well written and of high quality. The main idea, to use zeroth approximations of the Jacobian of the solution mapping for the lower level problem with respect to the hyperparameters appears to be original and significant, to the best of my knowledge. Some parts of the paper could be clearer, as touched on in the questions and limitations sections, but otherwise the main ideas are well-communicated. Regarding the experiments, they are limited to comparing to baselines and I think it's a weakness not to compare against other first-order optimization methods like AmIGO [Arbel, Mairal 2022] or single loops algorithms like SABA [Dagréou et al 2022].\n\n\"Amortized Implicit Differentiation for Stochastic Bilevel Optimization\" - Michael Arbel, Julien Mairal, 2022\n\n\"A framework for bilevel optimization that enables stochastic and global variance reduction algorithms\" - Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, Thomas Moreau, 2022", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7Y3r5Kis9a9", "reviewer": "Reviewer_vjNx", "summary": "This paper introduces a Hessian-free bi-level optimizer called partial zeroth-order-like bilevel optimizer (PZOBO). The method uses a zeroth-order-like Jacobian estimator, which provides accurate hypergradient estimates and a computationally effective way of solving bi-level optimization problems. The paper presents a thorough theoretical analysis and experimental validation on various bi-level problems. ", "questions": "+ Covariances should be added to the curves to better illustrate the performance variation. For example, Figures 3(a) and 3(b) shows the covariances but other figures do not. \n\n+ In related work, an analysis of the limitations of previous solvers and a discuss of how the proposed method can address those limitations can be helpful to evaluate the novelty and impact of the proposed method.\n\n+ The text refers to Figure 4(a), (b) and (c), but Figure 4 does not have subfigure labels.\n\n+ The consistency of figure formatting can be improved. For example, the shadows at the bottom of some figures such as Figures 2(d) and Figures 2(f).\n", "limitations": "This work does not have negative society impacts. A further discussion of the limitations of the proposed bi-level optimizer will be helpful. For example, the paper assumes the inner-level function to be strongly convex. How the proposed approach can be extended to address problems without this assumption?", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ The paper addresses the important bi-level optimization problem by providing an efficient and accurate solution.\n\n+ The paper shows the convergence guarantee of the proposed approach. \n\n+ Experimental results and comparisons with various baseline bi-level optimizers are provided over various bi-level problems. The proposed method generally outperforms baseline methods, especially in high-dimensional problems. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7Qahqjqx9ih", "reviewer": "Reviewer_mkCb", "summary": "## Further Update\n\nNot all my concerns are fairly treated and addressed in the discussion period (as the authors have promised). I lower the overall rating from 6 to 5 and the presentation rating from 3 to 2. This is my final decision.\n\n## Update\n\nI changed my rating from 4 to 6 due to the fair rebuttal from the authors.\n\n---\n\nThis paper proposes a zeroth-order based solver for bi-level optimization problem. In order to avoid the heavy computation of Hessian matrix and its inversion, the paper proposes to directly approximate the Jacobian matrix (implicit gradient) through function value difference and develops a Hessian-free bi-level algorithm. For the proposed method, the authors provide convergence analysis for the proposed zeroth-order algorithm and reach a non-asymptotic performance guarantee.", "questions": "Please see the comments in the weaknesses above.", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact.", "rating": 5, "confidence": 5, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Theoretical: The theoretical contributions are the main strength of this paper. To analyze the zeroth-order approximation, the authors must take into consideration the bias, variance, smoothness, and boundedness of the proposed optimizer, and this procedure is even more difficult when the commonly adopted Lipschitz-smooth assumption does not apply. The authors make very detailed discussion on different application scenarios of the proposed method and obtain meaningful result. This is difficult and remarkable.\n\n2.  Various experiments were conducted on different deep learning tasks to show the effectiveness of the proposed methods. The results generally look good and do outperform baselines.\n\nWeaknesses:\n\n1. Novelty: My main concern lies in the novelty of the paper. As is all known, that zeroth-order is a common technique even in the context of bi-level optimization. For example, DARTS [34] also used the zeroth-order method to solve the Jacobian-involved term without calculating Hessian matrix. I wonder what is the difference between this paper and DARTS in terms of theory as well as performance. In general, zeroth-order approach is not a novel ingredients in bi-level optimization and this greatly constrains the novelty of the proposed method.\n\n2. Experiments: I strongly suggest the authors to add some experiments on neural architecture search (NAS) for bi-level tasks. As I mentioned above, DARTS [34] used very similar approaches and I am curious which one performs better.\n\n3. Multiple trials: The authors do not report any results on the variance of any of the experiments. It is significance to report the variance to show the stability of each algorithm as well as the significance of the improvement.\n\n4. Minor issues: In all the plots/figures, the authors are suggested to use similar font sizes in ticks, axis labels, and legends. It is difficult to read the labels of all the figures in this paper. \n\nIn general, I believe the theoretical part of the paper is excellent, but the method proposed lacks major innovation and significance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept