Efficient Method for Bi-level Optimization with Non-smooth Lower-Level Problem
Authors: Wanli Shi
Bin Gu
Venue: Submitted to ICLR 2023 (2023)
Keywords: bilevel optimization
nonsmooth

Abstract: Bi-level optimization plays a key role in a lot of machine learning applications. Existing state-of-the-art bi-level optimization methods are limited to smooth or some specific non-smooth lower-level problems. Therefore, achieving an efficient algorithm for the bi-level problems with a generalized non-smooth lower-level objective is still an open problem. To address this problem, in this paper, we propose a new bi-level optimization algorithm based on smoothing and penalty techniques. Using the theory of generalized directional derivative, we derive new conditions for the bilevel optimization problem with nonsmooth, perhaps non-Lipschitz lower-level problem, and prove our method can converge to the points satisfying these conditions. We also compare our method with existing state-of-the-art bi-level optimization methods and demonstrate that our method is superior to the others in terms of accuracy and efficiency.

Under review as a conference paper at ICLR 2023
EFFICIENT METHOD FOR BI-LEVEL OPTIMIZATION WITH NON-SMOOTH LOWER-LEVEL PROBLEM
Anonymous authors Paper under double-bling review
ABSTRACT
Bi-level optimization plays key role in a lot of machine learning applications. Existing ofate-of-the-art bi-level optimization methods are limited smooth or some specific non-smooth lower-level problems. Therefore, achieving an efficient algorithm for the bi-level problems with generalized non-smooth lower-level objective is still an open problem. To address this problem, in this paper, we propose a new bi-level optimization algorithm based on smoothing and penalty techniques. Using the theory of generalized directional derivative, we derive new conditions for the bilevel optimization problem with nonsmooth, perhaps non- Lipschitz lower-leve! problem, and prove our method can converge to the points satisfying these conditions. We also compare our method with existing state-of- the-art bi-level optimization methods and demonstrate that our method superior to the others in terms of accuracy and efficiency.
INTRODUCTION
Bi-level optimization (BO) Bard 2013
Colson et al. 2007) plays a central role in various machine
learning applications including nyper-parameter optimization (Pedregosa] 2016 Bergstra et al. 2011
Bertsekas 1976), meta-leaming (Feurer et al. 2015 Franceschi et al. 2018 Rajeswaran et al. 2019).
reinforcement learning (Hong al. 2020; Konda & Tsitsiklis 2000). involves a competition
between two parties or two objectives, and if one party makes its choice first it will affect the optimal choice for the other party. Several approaches, such Bayesian optimization (Klein al. (017). random search (Bergstra & Bengio 2012). evolution strategy (Sinha et al. 201 gradient-based methods (Pedregosa 2016; Maclaurin et al. 20155 Swersky et al. [014], have bee proposed to solve BO problems, among which gradient-based methods have become the mainstream for large-scale BO problems.
The key idea of the gradient-based method is to approximate the gradient of upper-level variables, called hypergradient. For example, the implicit differentiation methods (Pedregosa) 2016 Rajeswaran et al. 2019) the first derivative of the lower-level problem to be 0 to derive the hypergradient. The explicit differentiation methods calculate the gradient of the update rules of the lower-level based on chain rule (Maclaurin et al., 2015 Domke 2012 Franceschi et al. 2017 Swersky et al., 2014) to approximate the hypergradient. |Mehra & Hamm (2019) reformulate the bilevel problem as a single-Ievel constrained problem by replacing the lower level problem with its first-order necessary conditions, and then solve the new problem by using the penalty method. Obviously, all these methods need the lower-level problem to be smooth.
2008), variable selection (Fan applications, such as image restoration (Chen et al.; Nikolova et al. [[2200]|Huag al.) [2008] Zhang al. 2010)) and signal processing (Bruckstein et al. al.] 2009), the objective may have complicated non non-smooth, perhaps non-Lipschitz term (Bian & Chen 2017). Traditional methods cannot be directly used to solve the bilevel problem with such a lower-level problem. To solve the BO problems with some specific nonsmooth lower-level problems, researchers have proposed several algorithms based on the above-mentioned methods. Specifically, [Brtrrndd et al. (220)) searched the regularization parameters for LASSO-type problems by approximating the hypergradient from the soft thresholding function (Donoho 1995 Bredies & Lorenz] 2008 Beck & Teboulle, 2009). Frecon et al. (2018) proposed a primal-dus FMD-based method, called FBBGLasso, to search the group structures of group-LASSS problems. Okuno et al. (202T) used the smoothing method and constrained optimization method to search the regularization
However, in many real-world

---

Under review as a conference paper at ICLR 2023
Table Representative gradient-based bi-level optimization methods.
Method
Reference
Problem
Method type
FMD
Franceschi et al.
(017 7)
Smooth
Bi-level
RMD
Franceschi el al. (2017)
Smooth
Bi-level
Approx
Pedregosa
(0016)
Smooth
Bi-level
Penalty
Mehra & Hamm
22099
Smooth
Single-level
FBBGL
Frecon al. (2018)
Group LASSO
Bi-level
SparseHO
Bertrand et al.
(0220)
LASSO-type
Bi-level
SMNBP
Okuno et al.
(021)
p-norm
Single-level
SPNBO
Ours
Generalized
Single-level
parameter of q-norm (0 q 1) and provided the convergence analysis of their method. We summarize several representative methods in Table Obviously, all these methods and their theoretic analysis only focus on some specific problem and can not be used solve the bilevel problem with generalized nonsmoothed lower-level problem. Therefore, how to solve the BO problem with a generalized non-smooth lower-level objective and obtain its convergence analysis are still open problems.
To address this problem, in this paper, we propose new algorithm, called SPNBO, based on smoothing (Nesterov] 2005) 2005)) Chen et al. 2013) and penalty (Wright & Nocedal 1999) techniques. Specifically, we use the smoothing technique approximate the original non-Lipschhiz lower-level problem and generate sequence of smoothed bi-level problems. Then, single-level constrained problem is obtained by replacing the smoothed lower-level objective with its first-order necessary condition. For each given smoothing parameter, propose stochastic constraint optimization method to solve the single-level constrained problem to avoid calculating the Hessian matrix of the lower-level problem. Theoretically, using the theory of generalized directional derivative, derive new conditions for the bilevel optimization problem with nonsmooth, perhaps non-Lipschitz lower-level problem, and prove our method can converge the points satisfying these conditions. We also compare our method with several satee-o-the-aas bi-level optimization methods, and the experimental results demonstrate that our method superior to the others in terms of accuracy and efficiency.
Contributions, We summarize the main contributions of this paper as follows:
1. We propose new method solve the non-Lipschitz bilevel optimization problem based on the penalty method and smoothing method. By using the stochastic constraint method, our method can avoid calculating the Hessian matrix of the lower-level problem, which makes our method a lower time complexity.
2. Based on the Clarke generalized directional derivative, we propose new conditions for the bilevel problem with generalized non- smoothed lower-level problem. We prove that our method can converge to the proposed conditions.
2 PRELIMINARIES
2.1
FORMULATION OF NON-SMOOTH BI-LEVEL OPTIMIZATION PROBLEM
In this paper, we consider the following non-smooth bi-level optimization problem:
min f(w", A) s.t. w" E arrg min g(w, X) + exp(\i))((h(w))
(I)
w
where A = A2,, ... A_ IT E R. A : D2,,... )Td and w E Rd. f Rdd x R + R and g Rd x R. + IR are twice continuously differentiable on w and X. sf.)) R + R is twice continuously differentiable. h(-)) gd + R is continuous, not necessarily convex, not differentiable, or even not Lipschitz at some points. Assume h(w) := (hr(DT w), h2 (b] w). hn (D) w)), where D, dx and h, Rd + R (i 1,2, we have an index set Ino = {i E 21, n) : h, is not Lipschitz continuous at D w and i Izn by is twice continuously differentiable.
is continuous. For fixed point w. assume
2

---

Under review as a conference paper at ICLR 2023
2.2 EXAMPLES OF NON-SMOOTH NON-LIPSCHITZ
PROBLEMS
The non-smooth non-Lipschitz optimization problems widely exist in image restoration (Chen et al. Nikolova et al. 2008), variable selection (Fan & Li |001] Huang et al. 2008 Zhang et 2010) and signal processing (Bruckstein al. 2009). Here, we give two examples es as follows.
1. Ip n-norm Chen et 2013): : min g X) + exp(A1)
Ei w.l". where p E (0,
2. OSCAR penalty
(Bondell Reich 2008): min (ww, X) exp(\)]lu|))
exp(A) Ei<s max, wg, ). where G, denotes the group index.
Note that Okuno et al. (2021) only considered the bilevel problem with the lower-level problem given in Example 1. Their theoretical analysis is not suitable for the problem in Example even more complicated formulation.
3 PROPOSED METHOD
In this section, we give brief review of the smoothing method and then propose stochastic gradient algorithm based on the penalty method and single-level reduction method to solve the bilevel problem.
3.1 SMOOTHING TECHNIQUE
Here, we give the definition of smoothing function (Nesterov 2005 Chen al. 2013 Bian & Chen
2017) which is widely used in nonsmooth non-Lipschitz problems.
Definition 1. Let v/ Bd + T. be a continuous nonsmooth, non-Lipschitz function. We call ;b Rd x [0, +o] + R smoothing function of vb if ((((;,)) p) is twice continuously differentiable for any fixed >> 0 and 1i (b (1) (w)) holds for any w E IRd.
Here, we give two examples of smoothing functions. The smoothing function of 2/1 (w) = Eie |aay u/ (w, p) Ei=(wu 1221/2 and the smoothing function of (2((w) Eiej max wi, wy} is (2( Eies
(w, + w2)² n (w:
w,)² n1²)
According to Definition] I the non-smooth lower level problem in problem (I could be approximated by using a sequence the following parameterized smoothing functions,
w arg min (ww, Ā) exp(\i)(((((w,,) x²))
(2)
1 (Tr (DI w. ",,),,)), ), haahhaaa w. n²),
where
the smoothing hn (D. ))
parameter
and h(w, μ²)
For each given smoothing parameter 1**t > O. we can replace the smoothed lower-level objective with its first-order necessary condition and derive the following single-level problem:
min f(w, A) s.1. clw. >: x1 O, w.
(3)
where c(w, A: p²) ((())==((w())) V whh(w (w. pM)).
Vug(w, 2) + exp(A1) V wo (h(w, and Vwi(h(Ww,
3.2 STOCHASTIC CONSTRAINT GRADIENT METHOD
In this subsection, we discuss method to solve the subproblem 3 Obviously, we can use the gradient method to solve its corresponding penalty function to solve the single-level constrained problem. However, calculating the gradient of the penalty functions needs to calculate the Hessian matrix. If the dimension of w, calculating the Hessian matrix is very coneeconsuming To solve this problem, introduce stochastic layer into the constraint such that only need to calculate the
3

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Smoothing and Penalty Method for Non-Lipschitz Bi-level Optimization (SPNBO)
Input: K, p', 1,,,,"",00 .8,. (0,
Output: w and A
I: for k 1=11....
1, K do
2: Find (w** s++1, p
, = min paxd L(w", X pp, 3 )²) using the SCG method.
3: 1 6npth.
4: .h+1 8eEk-
5: end for
gradient of the sampled element of the constraint. Specifically, we reformulate the subproblem (3) as the following minimax problem
min max L(w, A. P. f(w, A) + Σ p (w, A; w. PEA4
7 llp12.
where > =
1&0 S S 11. c(ww, ,²) denote the
i-th elements of c(w, P²). The last term is used to ensure L is strongly-concave on Such
reformulation widely used many methods (Cotter al. 2016 Narasimhan al. 2020 Shi et 2022) to solve the constrained problem.
In each iteration, we sample an element w, of w according to distribution and calculate the corresponding value of e; and its gradient w.r.t un Then, we can obtain the stochastic gradient of L w.r.t up follows,
V Cww, de Pc. - (t) = fw:, A,) - 2Bc (wi, Ari Ar Vi Ars
(5)
Using the same method, we can obtain the stochastic gradient VxL(w, Pt, Pt, ;::: Then,
Algorithm 2 Stochastic constraint gradient (SCG)
Input: 7, o. T/. 0141,1 4,+1, Output: w and X.
I: Initialize m1.1, m1.2, M133 1r,1 m22, ma.3, ?h1
2: while Not satisfy the conditions [00 do
uPe+1 = we 7A, m4,1-
4: wi+1 wi m1((++11111 wt).
5: Å4+1 A: -27,,22m..2
6:
A+11 A, 4 1/ (1 A²)-
7:
p++1 PA (p. + A.,
8:
P&+1 p. + T/. (p p.).
Sample constraint according to distribution p.
10:
Calculate the stochastic gradient V t C(w,, de, Pe, pe: and VxC(w,, De, Ee))
Randomly sample constraint.
12:
Calculate the stochastic gradient C(wwm, Ae, pe.
13:
Update m4,1, m4,2, m4,3-
Update fH,, 1,,,2 fug3 clip [e. 6].
15:
Calculate Ar, As,2, At,3-
16:
end while
randomly sample another element Wj, we can calculate the value of ej and obtain the stochastic gradient of w.r.t. as follows
vpL(w, A., Pt, p ; =ee >1 Ap3),
(6)
where ej denotes a vector where its j-th element is and other elements are 0. Since p is related to the value of constraints, sampling constraint according to p helps us find the most violating conditions.
To achieve better performance, the momentum-bars based variance reduction method and adaptive method are also used. Specifically, calculate the momentum-based gradient estimation w.r.t w. X
4

---

Under review as a conference paper at ICLR 2023
and p as follows,
m4,1 Vol(wr, d. Pr, :(. + a++1,1)
M1-1,1 -
1, Et)
2 - VxC(wr, de. Pc, u² ;&) + (1 - 1141,1)
M4 - VxC(w,- 1, Ex)
m1,3 = vpL(ur, Pe. Pc: ph: {d + (1 - ac-1,2) 1,3 - pp - Pc- Et)
and A1.3 for updating X and p. Then, we calculate the adaptive matrix matrices A,,,, As.2 respectively. Here, we present the calculation of adaptive matrix Ar.1 as an example. Specifically, we calculate a second momentum-basee based estimation 1 = www,, A Pt. , [t)² + -11-))m:1.. Pr,
Then, we clip each element of 1 into the range of [p,b] and obtain the adaptive matrix Ar
diag elippime,, b) Note that we can use other method to calculate the adaptive matrices,
such AdaGrad-Nor -orm WWrd et al. 2020), AMSGrad (Reddi et al. 2019). Adam (Liu et al. Then, we can obtain the update rules as follows,
2020).
7 m4 Å = X - m4,
W++1 = We + 11 (1 w.),
(7)
A-1 = d + ne n - de),
(8)
p++1 Pa (P: + a A
Pe+1 = + n: (P p.),
(9)
where 7 >> 0, 0, 1/2 > 0 and (a denotes the projection onto Ad.
Once the following conditions are satisfied,
VwL(w, A. P, n*) ) < E [Vx[(w, A. )12 S E
| A: "; S Se.
(10)
where V.rC and V denote the full gradients w.r.t w and A, we enlarge the penalty parameter B, and decrease the smooth parameter μtt
The whole algorithm is presented in Algorithm I and 2 Note that instead of checking the conditions in each iteration of SCD, we check the conditions after several iterations to save time.
4 THEORETICAL ANALYSIS
In this section, we discuss the convergence performance our proposed method (Detailed proofs are given in our appendix). Here, we give several assumptions which are widely used in convergence analysis.
Assumption 1.
We have E,V, "pC(zu41,Pet1
P::1, = V P ) [|ll V C( Pi+1.
) 1. p C(z-1111111
PP41 1 ))]
VeL(z Pi+1 4 [al
V2 and
E1lV [ll/Vp/ )² (p P.+1, 1)2 V2.
Assumption 2. The function L(w, X, X. , is r-strongly concave on p for any give μ²²t > O.
Assumption 3. The function L(w, >. A. 1²t) has Li-Liscchtzz gradient on (w, x) for any give
4* > O.
Assumption 4. The smoothing funccionn i(w,p") is twice continuously differentiable on w for any 1 >
Assumption 5. f is Lipschitz continuous and g is twice Lipschitz continuous w.r.f. w and X.
We prove our Algorithm 2 can converge to the points satisfying conditions 10 Here, we give the definitions of c-stationary of the constrained problem 3 and minimax problem and then show the relations between these definitions as follows.
Definition 2. (e-stationary point of the constrained optimization problem.) (wo X a²) is said to be the e-stationary point of the sub-problem (3) the the following conditions hold, [ w f(w" x ;=;)))) )
EE V Vwoi(".
e I[Vx(("* x²) + Σi= a; V (w x w < eg and
DI (W x ) S Gg where a denotes the lagrangian multipliers.
Remark 1. Let ag 2, (w0" >1: The conditions in Defintion is equivalent to the tolerance conditions 10
5

---

Under review as a conference paper at ICLR 2023
Definition 3. (e-stationary point of the mini-max problem.) (w* X" pp) is said be the stationary point of the mini-max problem if it satisfies the conditions V C S é², VV e² and || 2 < e
Proposition 1. If Assumptions 2 and hold, , X.pp) is the e-stationary point of the problem 4
then (w" X+ the e-stationary point of the constrained problem 3
According to Shi al. (2022). the minimax problem is equivalent to the following minimization problem:
max L(w, X. f(w, X. (w. x, 11}.
min
H (w, A) wx
(11)
PEAm
where p'(w. (w, X)
arg maxp L(ur, X. p). Here, we give stationary point the minimization problem aa its relationship with Definition 3 follows,
Definition 4. We call u² e-stationary point of differentiable function H(w), if IV X²) S E and ( ,>) S.
Proposition Under Assumptions 3 Bndd 2 i'r', .') is the e-stationary point of H(w, X), then (w', ,') is the e-stationary point of mill maXpesd C(w, X, n²)) be obtained. Cons- versely, if (w', ...p') is the e-stationary point of min maxpess [(w. X.P. ph) then point (w", X') is stationary point of Hww, A).
Remark According to Proposition Iiriiionnann Zand Proposition 2 we have that once we find the e-stationary point in terms of Definition 4 then we get the e-stationary point in terms of Desinition 2 Therefore, we can obtain the points satisfying the tolerance conditions (T0).
Before, give the convergence reuslt of our method, present the lemma useful in our analysis. We have
Lemma 1. Under assumptions, let ww: A}. we have
[[V((2) me, 112 $21 p.ll3 V Pt, Pc,
mr,=11
(12)
Then, we can define the following metric
122 Mr = 72 72112411 - 2z + 22 (z))))(((2))
+ + V - -m.,213-
(13)
We have
8²
M&
2 77 11 - -A7, - 2:113 [z) - m,,= | + [VV m. VH(z))
If M 0. we have [ + O. Thus, can bound M₁ to find the stationary point of problem
Then, we give the convergence theorem in the following theorem.
2
Theorem 1. Assume Assumptions hold, if act1111 cini c ci
Th 0 <
<7
3e3
V3rop
15 1 }, we have
and < o S ming
2 12L + 12517x26
12f' 69,
?cfV? o2 1/3/3 4p T Σ M. ( Om + 2/2/3
7 1
In(m + T)
(14)
Te
PT
Remark 3. Theorem demonstrate that with suitable setting, our method converge to the points satisfying the conditions (10) at the rate of (TT-333) ) if omitting log.
Then, we discuss the convergence performance of our whole algorithm. Define a new function
[D, w) h,, w)
i I E
(DD w)
(15)
which is Lipschitz continuous at DJ. w. 1,2, n. Then, we have h (w) :
(MF DF 18 w) w) .1a DJ w)). which has the same value h(w)) but opposite property.

---

Under review as a conference paper at ICLR 2023
For convenience, define (w) sp(h (w)) and ((w) ((h(w))). Besides, define vector set as follows,
D. V (o: 0, E Im]
(16)
which means that v is perpendicular to all column vectors in D; i E Zw According to Bian & Chen (017)). the necessary condition of the non-Lipschitz lower level problem is
Vug(ww X) ( (w";))
(17)
o(w tv) ((w) denotes the Clarke generalized
for all v E Vwo, where 6 (w*:)) lim sup
t
directional derivative of ((((ww) at wt. Replacing the lower-level problem with above condition, we can obtain the following single-level problem,
min s(w, X) 8.l. c(w, A) Vug(w, X) + exp(Ai) (d) (wr; v) 2 0 W,
(18)
for all v E Vwn. For this new problem, we have the following theorem.
Theorem 2. (f X²) satisfy the following conditions, then they are the stationary points of the problem
Vwl(w" x²) 02 (a) V ww )0); + exp(Ai) U1 0,,))) 2 0,
(19)
Vxs(w" )²) 03 Ug- - (o3 ( V )000 + + (w0") 2 0,
(20)
Veg(w" x²) + exp(Xi)o (wweu) 20,
(21)
E" (Vwg(w" x²) U1 +
v1)) = 0.
(22)
<" 2 0,
(23)
for all vi E Vw-, U/ E Rd Uy E R", where Us v1 (w:; In addition. (v1, U2 v3) is direction
[ug. 0 5y = [ug. .... 03 1 and
800 [w: U1 U2) limsup
$10
vector used in calculating the Clarke directional derivative.
Then, we show with decreasing the smoothing parameter and tolerance parameters, our method can converge to stationary point defined in Theorem 2 in the following theorem.
Theorem 3. Suppose { are positive and convergent (lima Ek = 0) sequences, {u²} is positive and convergent (lims-+oo μ** 0) sequence. Then any limit point of the sequence points
generated by SPNBO satisfies the conditions (79 23
Then, we show the relations between the conditions 19 23 and the original nonsmooth bilevel problem
Theorem 4. Assume the lower level problem in problem 7 is strongly convex. we have (w", X*) and 5* 2 0 satisfying the conditions (79--23) then (w", X*) is the stationary point of the original nonsmooth bilevel problem.
EXPERIMENTS
In this section, we conduct experiments to demonstrate the superiority of our method in terms of accuracy and efficiency.
5.1 EXPERIMENTAL SETUP
We summarize the baseline methods used in our experiments as follows.
1. Penalty. The method proposed in Mehra & Hamm 2019). It formulates the bi-level optimization problem as a one-level optimization problem, and then use penalty method to solve the new problem.
7

---

Under review as a conference paper at ICLR 2023
SPNBO
24
SPNIO
1.00
SPNI0
SENIO
SWNIP
24
SMNIP
SMNNRI
SMNID
Peniity
Peralty
TEST N380
2.3
Apprix
Appriox
2.50
Appeox
Approos
0.0
RMn
RMD
RMM
KMD
14
1.5
12
1.50
206
250
125
1200
120
Time (6)
Time
Fime
Timme (6)
(a) Cifar10
MNIST Figure 1: Test MSE against training time of all the methods in data re- re-weight.
(b) FaSSIonMNIST
(d) SVHN
2. Approx. The method proposed in Pedregosa (2016). solves an additional linear problem to find the hypergradient to update the typer-parameterr
3. RMD. The reverse method proposed in Franceschi et al. (017)) ). An additional loop is used to approximate the hypergradient.
4. SMNBP. The method proposed in Okuno et al. (2021) It uses the smoothing method to produce sequence of smoothing lower-level functions and replaces them with the necessary condition. Then the penalty method is used to solve each single level problem.
We implement SMNBP, Penalty, Approx, RMD, and our method in Python. Since original Penalty, Approx and RMD are used for the smoothing problems, we use the smoothing function to approximate the lower-level problem. We fix the smoothing parameter at μ = 0.0001 in these methods. In SMNBP, for each given smoothing parameter, we solve the constrained problem using the Penalty method. For all these method, we use ADAM to update w and X and choose the initial step size from {0.1, 0.01, 0.001}. For our method, we set = 0.9 and other parameters are set according to Theorem I We choose the penalty parameter from {0.1, 1, 10, 100} for our method, SMNBP, and Penalty. We fix the inner iteration number T in Penalty, Approx, and RMD at 10 according to Mchra & Hamm 2019). We summarize the datasets used in our experiments Table 2 and we divide all the datasets into three parts, i.e., 40% for training, 40% for validation and 20% for testing. All the experiments are carried out 10 times on a PC with four 1080 Ti GPUs.
5.2 APPLICATIONS
Data re-weight: In this experiment, we evaluate the performance all the methods the application named data re-weight. In many wallwwrld applica- tions, the training set and testing set may have differ- ent distributions. To reduce the discrepancy between the two distributions, each data point will be given an additional importance weight, which is called data weight. In this application, we search the weight A; of each training data and the OSCAR regularization parameters Ā and Å. This problem can be formulated
Table 2: Datasets used in the experiments.
Datasets
Features
Samples Classes
SVHN
32 x 32 x 3
73257
10)
Cifar10
84 84 x
50000
10
MNIST
28 x
x
60000
10
FashionMNIST
28 x 28 x
60000
10
Nost Σ 1=1
min X
aa "n,""" y:)
(24)
Noat
No.
exp(Ai)
s.t. w' E arg min
l(x w. yı) + exp(A)] + exp(x) Σ max Wg., wg }. Ej exp(>,)
where Ner and Neat denote the sizes of training set and validation set respectively. {x;, y:) denotes the data instance, 9; denotes the group index. In this experiments, set the group number equal to 10, and we use the mean squared loss l (x. w y:)²
Training data poisoning: In this experiment, evaluate the performance of all the methods in training data poisoning. Assume have pure training data ( with several poisoned points
8

---

Under review as a conference paper at ICLR 2023
Table 3: The test mse of all the methods data reweight. (Lower is better.)
Datasets
SPNBO
SMNBP
Penalty
Approx
RMD
10
2.146 + 0.006
2.147 + 0.012
2.147 0.011
2.171 0.004
2.203 0.0T2
MNIST
1.338 1 0.004
1.339 0.006
1.340
0.007
1.345 0.010
1.412 0.076
FaSHIonMNIST
1.091 1: 0.011
1.096 + 0.020
1.100 1: 0.001
1.1044000000
1.097 0.013
SVHN
2.138 1: 0.004
2.176 + 0.002
2.184 4 0.006
2.142 1 0.004
2.165 1 0.002
Voloktiion Lena
Val Loss
Valldaron
Validadion
SPNIBO
SPNBO
SINBO
SPNBO
Perulty
Panaly
Paseiy
Perally
Approx
Appmox
Timee (4)
Fire (1)
Time [4]
Time
(a) 10 Figure 2: Validation loss versus training time of all the methods in training data poisoning.
(b) MNSST
(c) MNIST
(d) SVHN
Noos assigned arbitrary labels. In this task, we search the poisoned data which can hurt the performance of the model trained from the clean data. This problem can be formulated as
Nou!
1 N
max
Noat Σ e(O(ar; w²) y:) s.t.
w" arg min
Σ ((((x;)) y:) + [ EIED
where = Ntr + Poor and D denote the dataset containing all the clean training data and poisoned Resnet18 model. Besides, we add p-norm (0 < p < 1)
data. In this experiment, regularization term in the lower-level problem to ensure that we can get a sparse model. In this experiment, we p 0.5. After solving the bilevel problem, retrain the model the clean data and poisoned data and then test the model.
Table 4: Test accuracy (%) of all the methods in training data poisoning (lower better).
Data
Approx
RMD
Penalty
SMNBP
SPNBO
SVHN
50.79 + 0.39
50.67 + 0.27
50.67 + 0.27
50.62 + 0.29
48.85 + 0.57
Cifarl0
82.91 0.18
83.25 + 0.11
82.29 + 0.11
82.57 + 0.11
82.22
0.28
FashionMNIST
96.09 + 0.07
95.89
+ 0.31
95.87
+ 0.19
96.01
+ 0.22
95.80 + 0.20
MNIST
80.27 + 0.25
77.63 + 0.08
77.43 + 0.54
77.50 + 0.30
77.22 + 0.08
5.3 RESULTS AND DISCUSSION
All the results presented in Tables 4 and Figure 1 our method has the similar results to other methods. From Figure and Figure 2 we can find that our method is faster than other methods in most cases. This is because Approx and RMD need solve the lower-level objective first and then need an additional loop to approximate the hypergradient which makes these methods have higher time complexity. Penalty and SMNBP need to use all the constraints in each updating step which is also time-consuming when we use complex models (e.g., DNNs), Penalty and SMNBP suffer from high time complexity. However, our method uses the stochastic gradient method which makes it scalable to complicated models and does not need any intermediate steps to approximate the hypergradient. From all these results, we can conclude that our SPNBO is superior to other methods in terms of accuracy and efficiency.
From Table and Table 4 can find that
6 CONCLUSION
In this paper, we proposed a new method, SPNBO, to solve the generalized non-smooth non-Lipschitz bi-level optimization problems by using the smoothing method and the penalty method. We also give the convergence analysis of our proposed method. The experimental results demonstrate the superiority of our method in terms of training time and accuracy.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Jonathan F Bard. Practical bilevel optimization: algorithms and applications, volume 30. Springer Science & Business Media, 2013.
Amir Beck and Mare Teboulle. A fast iterative Shrinkage-thresholding algorithm for linear inverse problems. SIAM journal imaging sciences, (11::183-202, 2009.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. The Journal of Machine Learning Research, 13(1):281-305, 2012.
James S Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper-parameter optimization. In Advances in neural information processing systems, pp. 2546-2554, 2011.
Quentin Bertrand, Quentin Klopfenstein, Mathieu Blondel, Samuel Vaiter, Alexandre Gramfort, and Joseph Salmon. Implicit differentiation of lasso-type models for hyperparameter optimization. In International Conference Machine Learning, pp. 810-821. PMLR, 2020.
Dimitri Bertsekas. On penalty and multiplier methods for constrained minimization. SIAM Journal on Control and Optinization, 14(2):216 -235, 1976.
Wei Bian and Xiaojun Chen. Optimality and complexity for constrained optimization problems with nonconvex regularization. Mathematics of Operations Research, 42644:1063-1084, 2017.
Howard D Bondell and Brian Reich. Simultaneous regression shrinkage, variable selection, and
supervised clustering of predictors with oscar. Biometrics, 64(1):115-123, 2008.
Kristian Bredies and Dirk A Lorenz. Linear convergence of iterative soft-thresholding. Journal of Fourier Analysis and Applications, 14(5-6):813-877, 2008.
Alfred M Bruckstein, David L Donoho, and Michael Elad. From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM review, 51(1):34-81, 2009.
Chen, M Ng, and Zhang. Nonconvex Ip regularization and box constrained model for image restoration. IEEE Trans. Image Process, 21.
Xiaojun Chen, Lingfeng Niu, and Yaxiang Yuan. Optimality conditions and smoothing trust region newton method for nonlipschitz optimization. SIAM Journal on Optimization, 23(3):152--1552 2013.
Benoît Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of operations research, 153(1):235-25) 22665--5,,2222 2007.
Andrew Cotter, Maya Gupta, and Jan Pfeifer. A light touch for heavily constrained sgd. In Conference on Learning Theory, pp. 729-771. PMLR, 2016.
Justin Domke. Generic methods for optimization-basel modeling. In Artificial Intelligence and Statistics, pp. 318-326, 2012.
David L Donoho. De-noising by soft-thresholding. IEEE transactions on information theory, 41))): 613-627, 1995.
Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association. 96(456): 1348-11300 2001.
Matthias Feurer, Jost Tobias Springenberg, and Frank Hutter. Initializing bayesian hyperparameter optimization via meta-learning In Twenty-Ninth AAAI Conference Artificial Intelligence, 2015.
Luca Franceschi, Michele Donini, Paolo Frasconi. and Massimiliano Pontil. Forward and reverse 2017.
gradient-based hyperparameter optimization. arXiv preprint
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, pp. 1568-1577 PMLR, 2018.
10

---

Under review as a conference paper at ICLR 2023
Jordan Frecon, Saverio Salzo, and Massimiliano Pontil. Bilevel learning of the group lasso structure. Advances in Neural Information Processing Systems, 31:8301-833 2018.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:0007.05170, 2020.
Jian Huang, Joel Horowitz, Shuangge Ma, al. Asymptotic properties of bridge estimators in sparse high-dimensional regression models. Annals of Statistics, 36(2):587-613, 2008.
A. Klein, S. Falkner, N. Mansur, and F, Hutter. Robo: A flexible and robust bayesian optimization framework in python. In NIPS 2017 Bayesian Optimization Workshop. December 2017.
Vijay Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in neural information processing systems, pp. 1008-1014. Citeseer, 2000.
Mingrui Liu, Wei Zhang, Francesco Orabona, and Tianbao Yang. Adam A stochastic method with
adaptive variance reduction. arXiv preprint arXiv:2011.11985 2020.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. maddent-bbsed hyperparameter optimization through reversible learning. In International Conference on Machine Learning, pp. 13-2222, 2015.
Akshay Mehra and Jihun Hamm. Penalty method for inversion-free deep bilevel optimization. arXiv preprint arXiv:19/1.034 /.0432, 2019.
Harikrishna Narasimhan, Andrew Cotter, Yichen Zhou, Serena Wang, and Wenshuo Guo. Ap- proximate beavily-constrained learning with lagrange multiplier models. Advances in Neural Information Processing Systems, 33:8693-8703, 2020.
Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical programming, 103(1): 127-152, 2005.
Mila Nikolova, Michael K Ng. Shuqin Zhang, and Wai-Ki Ching. Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization. SIAM journal on Imaging Sciences, (1):2-25, 2008.
Takayuki Okuno, Akiko Takeda, Akihiro Kawana, and Motokazu Watanabe. On Ip-hyperparammter learning via bilevel nonsmooth optimization. Mach. Learn. Res., 22:245:1 2021.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. arXiv preprint arXiv:1602.02355, 2016.
Aravind Rajeswaran, Chelsea Finn, Sham Kakade, and Sergey Levine. Meta-learning with implicit gradients. arXiv preprint arXiv: 1999.04630) 2019.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv:1904.0092: 2019.
Wanli Shi, Hongchang Gao, and Bin Gu. Gradient-free method for heavily constrained nonconvex optimization. In International Conference on Machine Learning, pp. 19935-19955. PMLR, 2022.
Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. Exolutionary algorithm for bilevel optimization using approximations of the lower level optimal solution mapping. European Journal of Operational Research, 257(2)3395-411 2017.
Kevin Swersky, Jasper Snoek, and Ryan Prescott Adams. Freeze-thaw bayesian optimization. arXiv preprint arxiv:/400 3006.886, 2014.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. The Jourmal of Machine Learning Research, 21(1):9047-9076, 2020.
Stephen Wright and Jorge Nocedal. Numerical optimization. Springer Science, 35(67-68):7, 1999.
Cun-Hui Zhang et al. Nearly unbiased variable selection under minimax concave penalty. The Annals of statistics, 38(2):894 942, 2010.
11


Reviews:
[{"review_id": "rpjjXL1bswb", "reviewer": "Reviewer_KAnF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors provide the first provably convergent algorithm for bilevel optimization with non-smooth non-Lipschitz lower-level function to their knowledge, via smoothing and penalty techniques. The proposed algorithm is empirically more accurate and efficient than existing state of the arts.", "summary_of_the_review": "Since the novelty is insignificant and there are many points to clarify, I recommend borderline rejection. ", "strength_and_weaknesses": "Pros: The authors provide the first provably convergent algorithm for bilevel optimization with non-smooth non-Lipschitz lower-level function to their knowledge. The contributions look clear. \n\nConcerns: Lack of novelty and clarity as shown in \"Clarity, Quality, Novelty And Reproducibility\". ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cw4OGvnlUY", "reviewer": "Reviewer_xEMd", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces an algorithm to solve bilevel optimization problems with non-smooth inner problems. \nAuthors propose to smooth the non-smooth term in the inner problem, and to iteratively decrease the smoothing parameter. \nIn addition, a stochastic approach is proposed to avoid compute full hypergradient.", "summary_of_the_review": "I have concerns about how practical this algorithm is: there are so many hyperhyperparamters, I do not if it will be useful.\nIn addition I am not sure of how strong is the theoretical contribution.", "strength_and_weaknesses": "My main concerns are the following:\n\n- Could you clarify the contribution, is it the smoothing? Or the stochasticity in the algorithm?\n\n- \"Instead of calculating the hypergradients which normally involves the calculation of Hessian matrices or the training of lower-level problem\"\nCan authors give a reference for the fact that single-level problem requires creating the Hessian  I am very surprised by this \"Hessian\", since the Hessian is usually never computed, the linear system can be solved without creating and storing the Hessian, but using matrix vector product.\n\n- Could you comment on the cost in time per iteration of the proposed algorithm?\nMaybe by adding the cost of each step in the algorithm?\n\n- Once the problem is smoothed why not directly applying implicit differentiation? As in [1] or [2]?\n\n- It seems that the algorithm introduces a lot of new hyperparameters controlling the convergence of the algorithm.\nHow robust/sensitive to these hyperparameters is the algorithm? In particular, the resolution can be very sensitive to the sequence $(\\eta_t)$\n\nMinor:\n- It would be friendlier to indicate the number of hyperparameters tuned for each problem.\n\n\n[1] Bengio, Y. (2000). Gradient-based optimization of hyperparameters. Neural computation\n\n[2] Pedregosa, F. (2016). Hyperparameter optimization with approximate gradient. In International conference on machine learning", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BPB4z1IRaV", "reviewer": "Reviewer_rqtu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new nonsmooth bi-level optimization algorithm based on smoothing and penalty techniques. New convergence conditions are derived for problems which may even have non-Lipschitz lower-level problem. Some numerical experiments are provided to demonstrate the effectiveness of the proposed method. ", "summary_of_the_review": "The paper seems to have some interesting algorithm/analysis developments. However, it is very hard to follow the mathematical proofs in the paper. The algorithm also seems overly complicated with many hyperparameters. For these reasons, I feel the paper is slightly below the bar. ", "strength_and_weaknesses": "Strength:\n1. Some new analysis has been provided in this paper to provide some interesting convergence guarantees.\n\n2. The numerical result looks promising.\n\n\n\nWeakness:\n1. The proposed algorithm looks quite overly complicated with a lot of hyperparameters. \n\n2. The proof is also quite complicated and hard to follow. I was not able to verify the correctness of the proof. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "A1hNqMGB0X", "reviewer": "Reviewer_6kJf", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers a specific nonsmooth bilevel problem with a structured nonsmooth regularization term, such as the $\\ell_p$ norm and the OSCAR penalty, in the lower-level problem. The authors first recursively smooth the nonsmooth regularization term with a smoothing parameter $\\mu^k$ that is set to decrease to $0$ as iteration goes. Each corresponding smoothed bilevel problem is solved by first transforming it into an equivalent single-level problem with a constraint that enforces the optimality of the smoothed lower-level problem. This single-level problem is further transformed into a regularized minimax problem via the penalty technique, which is then solved by the (partially stochastic) gradient (descent-ascent) method. The authors finally show that the sequence of approximate solutions (for each $\\mu^k$) converges to a point satisfying a necessary optimality condition.", "summary_of_the_review": "This paper proposed an iterative method that finds a solution of a bilevel problem with some structured nonsmooth regularization term in the lower-level problem, which has not been studied elsewhere. Although it has some merits, the paper is missing some details, such as how $\\beta$ is updated in accordance to $\\epsilon$, which makes it hard to verify the correctness of the analysis.", "strength_and_weaknesses": "**Strength**\n- This can handle some structured nonsmooth regularization term in the lower-level problem, which has not been studied elsewhere.\n\n**Weaknesses**\n- The title and abstract somewhat imply that the proposed method can handle general nonsmooth lower-level problem, but it is yet quite restrictive (in terms of applications), so this might seem to be an oversell.\n- The SCG assumes that (10) is satisfied for any choice of $\\epsilon_k$, which does not seem to be correct. In specific, Theorem 1 shows that SCG can decrease the $||\\nabla H(z_t)||$ as much as possible. Let $\\hat{\\epsilon}$ be its tolerance after certain number of iterations. Then, this translates to $\\epsilon$-stationarity of the constrained problem (3) in Definition 2, where $\\epsilon_3^2$ in Definition 2 is chosen to be $\\sqrt{\\frac{2d\\hat{\\epsilon}^2 + 2d^2\\tau^2}{\\beta^2}}$. Since this value cannot be decreased arbitrary small for finite $\\tau$ and $\\beta$, it looks possible that SCG might not meet the condition (10) for any $\\epsilon_k$. So, how we choose and update $\\epsilon_k$, $\\beta$, $\\tau$ seems important, but this does not seem to be carefully discussed in the paper. \n- Algorithm 1 should have a line for updating $\\beta$. Overall, the algorithm is not well written down.\n- Assumption 2 is already satisfied, so this seems redundant. Technically, Assumption 3 on $\\mathcal{L}$ is not satisfied.\n\n**Minor**\n- page 1: been\n- page 3: OSCAR penalty not defined properly; the dimension of $w$ \"is large\";\n- page 4: SCG samples the constraint, rather than an element $w_i$; distribution $p_{t+1}$\n- page 5: $\\beta^k$? How about $\\tau$ as iteration goes?\n- page 6: Lemma 1: $||\\nabla H(z_t)||$; Theorem 1: $A_{t+1,1}$, rather than $a_{t+1,1}$? $m$ without index?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject