Relax and penalize: a new bilevel approach to mixed-binary hyperparameter optimization
Authors: Sara Venturini
Marianna De Santis
Jordan Patracone
Martin Schmidt
Francesco Rinaldi
Saverio Salzo
Venue: Accepted by TMLR ()

Abstract: In recent years, bilevel approaches have become very popular to efficiently estimate high-dimensional hyperparameters of machine learning models. However, to date, binary parameters are handled by continuous relaxation and rounding strategies, which could lead to inconsistent solutions. In this context, we tackle the challenging optimization of mixed-binary hyperparameters by resorting to an equivalent continuous bilevel reformulation based on an appropriate penalty term. We propose an algorithmic framework that, under suitable assumptions, is guaranteed to provide mixed-binary solutions. Moreover, the generality of the method allows to safely use existing continuous bilevel solvers within the proposed framework. We evaluate the performance of our approach for two specific machine learning problems, i.e., the estimation of the group-sparsity structure in regression problems and the data distillation problem. The reported results show that our method is competitive with state-of-the-art approaches based on relaxation and rounding.

Published in Transactions on Machine Learning Research (02/2025)
Relax and penalize: a new bilevel approach to mixed-binary hyperparameter optimization
Sara Venturini MIT Senseable City Lab Massachusetls Institute of Technology
sventuri@mitt.cm edu
Marianna De Santis
mariannuu.desmmiishhuuinni
Department of Information Engineering University of Florence
Jordan Patracone
Inria, Laboratoire Hubert Curien Université Jean Monnet Saint-Ettenne
Martin Schmidt
martin.cciiiddtuniitiieee
Deportment of Mathematics
Trier Universily
Francesco Rinaldi'
rinaldi Smath.
Department of Mathematics University of Padovo
Saverio Salzo*
salzo@diag uniromal.
DIAG, Sapienza University of Rome and Italian Instätute of Technology
Reviewed on OpenReview: https: openreview. net/ forum? id= A1R1
Abstract
In recent years, bilevel approaches have become very popular to efficiently estimate high- dimensional hyperparameters machine learning models. However, to date, binary parameters are handled by continuous relazation and rounding strategios, which could lead to inconsistent solutions. In this context, we tackle the challenging optimization of mixed-binary hyperparameters by resorting to equivalent continuous bilevel reformulation based on appropriate penalty term. We propose algorithmic framework that, under suitable assumptions, is guaranteed to provide mixed-binary solutions. Morcover, the generality of the method allows to safely use existing continuous bilevel solvers within the proposed framework. We evaluate the performance our approach for two specific machine learning problems, i.c., the estimation of the group-sparsity structure in regression problems and the data distillation problem. The reported results show that our method is competitive with state-of-the-art approaches based on relaxation and rounding.
1 Introduction
Nowadays, machine learning systems tend to incorporate an increasing number of hyperparameters with the purpose of improving the overall performance of learning tasks and achieving a higher flexibility. Then,
"These authors contributed equally to this work. Université Jean Monnet. Stienn,, CNRS, Institut d'Optique Graduate School, Inria, Laboratoire Hubert Curien UMR 5516, F-42023, SAINT- ETIENNE, France.

---

Published in Transactions on Machine Learning Research (02/2025)
optimizing such high-dimensional hyperparameters becomes a crucial step for devising efficient and fully parameter-free machine learning systems. In recent years, bilevel approaches to hyperraaameeeer optimization have become very popular as an effective way to estimate high-dimensional hyperparameters (Arbel & Mairal
2022
Bac & Grosse 2020
Bennett et al. 2006 Franceschi et al. 2018 Grazzi et al. 2020 Maclaurin et al.,
Pedregosa 2016). On the other hand, in many circumstances, binary hyperparameters are included in the model to allow the pruning of the irrelevant variables or the discovery of sparsity structures. Interesting examples are given by the pruning of large-scale deep learning models (Zhang et al.] 2022), the identification of the group-sparsity structures in regression problems (Frecon et al. 2018: Wang et al.) 2020), and learning the discrete structure of a graph neural net networks (Franceschi et al. 2019). For these cases, the usual optimization approach is that of relazing the respective parameterln over the unit interval [o, IJ, solve the continuous oplimization problem, and then rounding the solution so to get a binary output. This is essentially a heuristic, which overcomes the challenge of dealing with integer variables, but does not offer any theoretical guarantees. The aim of the present work to provide a more principled way of approaching mixed-binary hyperparameter optimization.
2015;
Related works. In the context of machine learning, bilevel optimization problems with binary variables arise in number of situations. In Frecon et al. (2018) the estimation of group-sparsity structures in multi-task regression is addressed by mixed-binary bilevel optimization model, which is handled by a continuous relaxation and approximation of the problem. The output of the optimization procedure is a vector of continuous variables, which are then rounded to the closest binary values, so to provide the final grouping of the features. In Section 5] we tackle this same problem and show the advantage of our approach. In the work Zhang et al. (0022) 1, new model pruning, based on bilevel optimization, is proposed, where the upper level variable is a binary mask. The related iterative algorithm performs gradient descent step on the continuous relaxation of the problem followed by projection step onto discrete set, which is indeed a tard-thresholding operation. No convergence guarantees are provided. In Borsos et al. (2024), the authors present a general framework for coresct construction by formulating coreset selection as a cardinnllit-conssttanned bilevel optimization problem, solved using a tailored algorithm that combines greedy forward ion and first-order methods. The proposed approach is model-agnostic and applicable to any wwice-differentiale model, including neural networks. A drawback is that the coreset weights must be determined for each selection step, which involves an iterative process. To streamline this, binary weights (i.e., unweighted coreset) are also used and a mixed-binary bilevel optimization problem is defined, thus eliminating the weight optimization step. The authors only report a theoretical analysis of the algorithm for the continuous-weights case. In another recent paper Zhou et al. (2024) some deep learning techniques are developed to tackle a bilevel problem with a binary tender, i.e., a problem where the upper and lower levels are connected through binary variables. neural network trained to approximate the optimal value of the lower-level problem as a function of the binary tender. This enables a single-level reformulation of the bilevel program using a mixed-integer representation of the value function. Additionally, comparative analysis is conducted between two neural network architectures- general neural networks and novel input-supermocular neural networks-te to assess their representational capacities. To handle high-dimensional bilevel programs, an enhanced sampling method is introduced to generate higher-quality samples, along with an iterative process to refine solutions.
Beyond the machine learning litcrature, there are a number of works related to mixed-integer bilevel programming; see, e-g., Section 5.3 of the recent survey Kleinert al. (2021b). An important drawback one needs to take into account when applying those methods to hyperparameter optimization problems are however limited scalability. Common approaches like, e.g., the outer-approximationn ct al. (2021a), or the algorithm proposed in Mitsos (2010), which requires the global solution of a significant number of mixed-integer nonlinear programs have indeed a prohibitive cost when the dimensionality grows. Furthermore, it should be noted that they aim to achieve global optimality an overly ambitious goal in the context of machine learning applications.
method in Kleinert
Contributions and outline. In this paper, we analyze more carefully the mixed-binary setting and propose relax and penalize method, which producos mixed-binary output and relics on improved mathematical grounds. More precisely, we present in Section 2 general mixed continuous-binary bilevel problem and show in Section 3 that it is equivalent, in terms of global minima and minimizers, to a fully continuous and penalized
2

---

Published in Transactions on Machine Learning Research (02/2025)
optimization problem. Next, in Section 4 propose an algorithmic framework, which consists of iteratively solving sequence of continuous and penalized problems which, under suitable assumptions, guaranteed to provide mixed-binary local solutions. The performance of the proposed approach is quantitatively assessed on the two machine-learning applications of the group structure cstimation in the group lasso problem and the data distillation task. Numerical experiments are reported in Section 5 and show how the relax and penalize method compares with state-of-the-art approaches based on relaxation and rounding. Finally, conclusions and perspectives are drawn in Section G
Notation. For every integer 2 1, [n] denotes the set (L.....,.). We denote by ||-|| the Euclidean norm
in R and by |l the infinity norm, mcaning | maxigugn pra.- If a E R2 and p > 0 we denote by (x)x) the closed ball in I" with center I and radius p. i.e. (T) = {x's E R": || - x S).. The standard (n - si-mmplee is denoted by A = {a E R Σ I2 1]. Moreover, @ is the Hadamard product, meaning the component-wise multiplication of vectors in Rd. If V: R - R continuous function and
Ω S R", we denote by argming the set of minimizers of v over and with a slight abuse of notation also the minimizer itself when is unique.
2 Problem statement
We consider mixed-binary bilevel problems of the form
F(A,O,w(A, min x,0
(Ia)
s.t.
XEA R", A Oin S (0, 13' w(),0) argmin f(A.0,w), w), we,(),0)
(1b)
(1c)
where F: 1RT x RP x Rd + R and C We note that the lower-level problem is supposed to admit a unique solution and that the hyperparameters À and I are continuous and binary variables, respectively. In the context of machine learning problems, the functions F and I often are the loss over a validation set and training set, respectively. We will provide major applications of this situation Scction
In the remainder of this paper assume that the binary set Ovin is embedded in larger contimuuus set θ and that the lower-level problem admits unique solution also for 0 E θ. Then, and more compact formulation
consider the following
min (A.0)EAXQuin
G(\,0)
of the above problem, where we set G(),0) = F(A, 0, w(, 0)) and require that the following assumption holds. Assumption 1.
(i) A C Rm is nonemply and compact.
(ii) Obin = (0, + Ø, where + C 10, 112 convex and compact and θ \ θ bin A Ø.
(iii) G: A x θ R. is continuous.
(iv) For all X E A, the map G(),)) is Lipschitz continuous with constont L >>>> O.
Assumption 1 can be met with appropriate hypotheses on the functions F and f. For instance, sufficient
condition for [ is that the functions and f are jointly continuous, that the function f(A, 0,.) ) is strongly convex with a modulus of convexity which is uniform for every (A,0), and that the set-valued mapping (X,0) > W(A, 0) closed and such that, for every (X, x (ust(w((X, 0), (ww, 0)) - 0 as (A. - (X, B) Bonnans Shapiro 2000 Proposition 4.4). Additional conditions can ensure the validity of (iv) too; see,
Bonnans & Shapiro (2000] Section 4.4).
3

---

Published in Transactions on Machine Learning Research (02/2025)
3 Restating the problem via smooth penalty function
In order to deal with the binary variables in problem 2 we relax the integrality constraints on 0 via a
classic penalty term. This leads to the continuous optimization problem
min G(A,0) + (0( (x.0)Exx0
(3)
in which we use the penalty function
(0()) Σ 0,(1 0,).
(4)
Note that the function in 4 is smooth, concave, and quadratic function with the following properties:
A4 E (0, 1j": (0)) 2 and 4A E (0,1)" (0)) 0.
This penalty has been introduced in Raghavachari 1969 to define equivalent continuous reformulations of mixed-integer linear programming problems. In Section we give the main properties of this penalty function that we use to prove the main results of this and the next section.
We start with a result establishing the equivalence of Problems 2 and (3) in terms of global minimizers. It is in line with stream of works analyzing the use concave penalty functions in the framework of nonlinear optimization problems with binary or integer variables (see, e.g., Giannessi & Niccolucci (1976); Kalantari & Rosen (1987); Lucidi & Rinaldi (2010) and references therein). For the reader's convenience we provide the proof of this result in the appendix.
Theorem 1. Suppose that Assumption 1 is satisfied. Then, there exists an È > 0 such that for all E E [0, Problems and 3 have the same global minimizers, i.e.,
1 argmin G(A, argmin G(A,0) + (()) (A.0)EAXe
(xx))
The conclusion of Theorem is remarkable since it guarantees that despite the fact that 3 is a purely contimuuus optimization problem, for sufficiently small, all of its global minimizers are mixed-binary feasible and are exactly the global minimizers of the original problem (2)
Remark 1.
(i) Set Ax:Axx R such that function of the set Obin; iee., the funclion that is zero on Obin and too otherwise. Then, il is easy see that Ge r-converge to G 6Λx@mm as E - Moreover, the family of functions (Ge)ezo is clearly equicoercive since they are all defined on the compact set A O. Therefore, it holds
and let ŌxXOa.. A be the indicator
argmin Ge argmin G + tAx0ma. argmin G 6 Axe
Axe
Ax
in the sense of set convergence. This is standard result from variational analysis (Dontchev & ZZolezz 1993) and it is always true provided that G and yp are continuous functions as well as that & and (00)= if and only if 0 Osin holds.
(ii) In view of (i) which gives asymptotic result, the statement of Theorem 1 is stronger in the sense that, for the special function
4 and for small enough, argmin Axe Ge argmin G holds.
The previous theorem provides a justification to address problem 3 instead 2 However, because the objective function (3) nonconvex, only local minimizers are computationally approachable. Thus, the idea is that of looking for local minimizers of 3 which also mixed-binary since the global minimizers of lie among them.
The next result is entirely new and addresses the issue of identifying mixed-binary local minimizers of the objective in 3 providing a sufficient condition for that purpose.
This type of convergence functions also known epiconvergence.
4

---

Published in Transactions on Machine Learning Research (02/2025)
Theorem 2. Suppose that Assumption holds. Let E |0,1/2[ and 0 <<<<< (1- 2c)/L. Morcover, let (A, 0) be local minimizer of
G(A,0) (0) Ax
If (0, Obm) == inf infe ||0 01|0 C, then 0 E Oin.
Proof. Since (0, Ohin) < there exists 0 E Obin such that |10 - 0l1oo < Let
0, (1 1)0 10 1(0 0) with & [0, 1].
particular, 10, - 0l = t1l0 01|00 te S c and 0g E θ since is convex. By Lemma 3
( (0,) 2 (1 2c) -
(5)
holds. Moreover, there exists such that for all (x'0) B, 0) n (A 0); it holds
1 (() G(X, 0¹) (0') G(A,0) -
Now, take & 1 such that < p/(c/p). Then, 0, E θ and 110 011 s vpl.0 811 < vptc < p.
Therefore, (2, BA 0) (A x )) and we obtain
1 G(Î,0) 0.) G(λ, 0) ((0) 00) S L1IO,
1
1
0|
(v((0) (())
5
2c
L|
10, - Ø1
6
1
2c
1 011
(6)
Moreover, if 0 & 10, since 0 (0, 132, have |10-0] 01 0 and hence 11: 011 > 0 for / />> 0. Thus,
6 is
strictly negative and it holds
G(A, 0.) 1 (0.) < 0(²,0) + -p(0),
which gives contradiction. Thus, necessarily 0 {0,
Remark 2.
(i) Theorem 2 essentially says that, if is small enough, within the distance of 1/2 measured with the infinity norm, there are no other local minimizers of 33 than the ones that are mized- -ineeyybnrryyyy feasible.
(ii) Note that it does not make much sense to consider local månimizers of the function G over A x O since any point in Opin is an isolated point and thus one can fond a corresponding local minimmizer for each one of them.
4 An iterative penalty method
We now present an iterative method addressing problem 22 The idea that of solving sequence of problems of the form (3), indexed with k, with decreasing parameters εk. Hence, the problem to be solved in each iteration reads
min G(A 2t ((0).
(Pk)
(A,))A
Then, thanks to Theorem [ it is clear that after finite number of iterations, the original mixed-binary optimization problem and the relaxed and penalized one (P*) become equivalent in terms global minimizers. Morcover, as we have already discussed in the previous section, practice we can only target the computation of local minimizers, but we can restrict the search the mixed-binary ones. In the following, make this strategy more precise.
5

---

Published in Transactions on Machine Learning Research (02/2025)
Algorithm 1: Penalty method
Input: Problem c0 > 0, 3 e 1
for k = 0,1, do
Let (A*,0)) be a solution (either local or global) problem P if 8h & {0, 1 then
update gh+1 = 3E else
4
return (A%,0h).
Theorem Suppose that Assumption 7 holds. Let (Ek kEN be vanishing sequence of positive numbers and, for every & E N, let (A*, 8h) be local minimizer of P Then,
lim inf dist. (0t, Ohin) 1/2 AkE 8.L. 0 Ohin-
+0000
Morcover, 0h E bin, then have that X is local minimizer of
min G(A, 0*). AEA
Proof. Suppose that lim inf dist (8" bia) < 1/2 and let such that lim inf dist (0*, Obin) < 1/2. k-++00
4-+000
Then, there exists a subsequence (f )KEN such that
E distao00% Ohin) < c
and = + O.
Thus, there exists l E N such that
- 2c L
dist (0 Obi)) < and Enk
and this, in view of Theorem 2 gives that 6th E Obin- Concerning the second part of the statement, suppose
that H E Obin, where (A Bh) is a local minimizer of P Then, H E 13, and there cxists Pa > 0 such that
- p(0))) s G(A, 0) p())
((, Bon (** oh) n O): G(* 0h)
Ek
EK
Therefore, taking 0 = 0h in the above inequality and noting that (e(()t = 0, we have
B) G(X" + p(0)) $ G(A, 0%) + (
0
which shows that A is local minimizer of G(,,0t) over A.
Remark 3.
(i) In the experiments given in Section checked that the condition considered in Theorem 3 always occurs, meaning that the distance dist (8*, Qbmn), where 6² was obtoined by solving problem (p*
vio a gradient-based basedd subroutine, remains well-below the threshold 1/2 for k sufficiently large (See Appendir D.3 for a plot of the evolution along the iterations).
iii) We note that there might indeed exist points 0 E ④ such that dist (0, Obin) 1/2. For instance, if we take the standard (p- -imsimp
θ = AP-1
E R.P.
Σo, 10,=1
1=1

---

Published in Transactions on Machine Learning Research (02/2025)
we have that
{0 dist (0, Obin) 2 n
(7)
which for p= is the full equilateral triangle with vertices (er + e2)/2, (er + es)/2 and (e2 + es) where the eq are the vectors of the camoricaal basis of RP, In general, the set in 7 is polytope of
dimension with 2p facets and (p(p 1)/2) vertices.
The method is formally given Algorithm
5 Two machine-learning applications
In this section, we present machine-learning applications: estimating the group-sparsity structure in regression problems (Subscction 5.1 and performing data distillation (Subscction 5.2p. Firstly, we present the problem setting and the bilevel formulation. Secondly, we show how the problem fits our mathematical formulation. Finally, we provide a comparison with relaxation and rounding using two different rounding strategics: the simple rounding baseline, which obtains the mixed-binary solution by rounding cach variable individually to 0 or L, and the top-k hard thresholding baseline, where the mixed-intee integer solution is obtained by performing a top-k hard thresholding operation on the continuous solution Frecon et al. 2018 Zhang et al. 2022). The codes are available on the GitHub page: httts:///gihub... com satanaaravnttuinnn/// Belax-and penalize
5.1 Group lasso structure
Here, present the application of estimating group-sparsity structures, which is useful in areas such gene expression analysis. We follow the formulation, the optimization algorithm, and the experimental setup in Frecon et al. (2018). In particular, we extend the approach by optimizing over both the hyperparamctors O and X, instead of determining À by cross-validation. We compare our relar and penalize strategy with the relazation and rounding proposed in Frecon et al. (2018), using both simple and top-k hard thresholding rounding. The datasets usod in the tests are challenging variants the synthetic datasets referenced Frecon ct al. 2018), specifically designed to create classes of differing sizes.
Problem setting and formulation. Given output vector y E N and design matrix X E NXP, the group lasso problem can be formulated as follows
1 min - [Xw -01l- A Σ 10: O w|l2, WER 2
1=1
where À > O is regularization parameter and O: is binary vector (with entries in {0,1)) indicating the features (components) of w belonging to the /th group, meaning Gi {i [P]: 0,,1 = 1}, where the vectors 0₁ are thought as columns of a P I matrix. In the case of nonoverlapping groups, it is assumed that Ei.10 0,.= for every j E [P] In the classic literature on the topic, the groups are assumndd to be known a priori (Yuan & Lin 2006 Zhao et al. 2009), but often in practice there is no clue about the structure of the groups and the problem to infer this group structure from the data. However, this amounts to estimating the binary variables f,'s, which in general poses a challenge.
In view of the discussion above, in the related literature common approach is to relax the problem allowing the 0,'s 's to vary in the continuum [o, 1J"" This approach was followed in Frecon et al. 2018 in which the following bilevel optimization problem is proposed
( PxI,)
1 E C.la(AA)))) 0)) with o min BEe T 1=1
Σ 01 00==1 1p
(A--1)P
1=1
(8)
(w ( T and w()
argmin 1 1
Σ
( (11 - 1il1? +
> 10 wellz + "1
T
t=1
2wicc be equivalently defined as rounding up to the largest components vector and the other ones.
7

---

Published in Transactions on Machine Learning Research (02/2025)
Here, (X,, B1SSSTTT defines T regression problems in which the regressors share the same group-sparste structure, Ct is a smooth cost. function acting validation error for the I-th task, and 0 are thought columns of a P x L matrix. Note that in this formulation, À is supposed to be fixed (possibly determined by a cross-validation procedure). The regularization terms r/2 with 17 < 1, are added to ensure uniqueness of the solution to the lower-level problem and to devise dual algorithmic procedure generaling a sequence (wrl)) (A, gEN with smooth updates (w.r.t. 0) such that wl (2,0) (2,0) - w(2. uniformly on as g - +oo; see Frecon et al. (2018) Section 3.2). Ultimately, the groups are estimated by solving the problem
T Σ
min G
T (A
with q large enough, and by appropriately thresholding (a posterior) the solution in order to recover binary variables 0/'s.
Proposed method. Our general relas and penalize approach, described in Section 4 allows bypass the last thresholding step and directly address the more challenging problem
A Amin Amax] with 0 < Amin
Amaxi
T Σ
min (X.0)AAxeiin
(((wl)))))) with
Oin {o (0,1) Vj E Σ [01=113
Note that in Frecon et al. (2018). X is supposed be fixed (possibly determined by a cross-validation procedure). Instead, here we are optimizing w.r.t. both the hyperparameters 0 and X, obtaining a mixed- binary problem in the end. In Section C we report the details of the extension. Now, since w(9) (2, is
smooth w.r.t. 0, the objective in (9) satisfies Assumption I [nd hence, in view of Theorem [ and Theorem we can consider the relazed and penalized version of Problem that is
min
1 T
Σ
(Crtullo (A, 0))
(2,0)
1 =
(10)
(x.))Ax0
and state that, if e is small enough, the two problems 9 and 10 share the same global minimizers. By leveraging this equivalence, we study in the next section the added benefits of the proposed Algorithm [
Remark 4. According to Frecon et al. 2018 Theorem 3.1) have that w/ (2,0) w(>, f) as q
uniformly on A x Obin: so that, similarly to Precon et al. 2018 Theovem 2.1), one can proce that Problem converges q + 400 to the problem
9
1
Σ (,((A,)))
min Ax
T
in terms of optimal values and sets of global minimizers. This provides a jjustfficatio for addressing Problem
Numerical experiments. The experimental setting is similar to that of Frecon et al. 2018 Indeed, we create synthetic datasets where each task amounts to predict an oracle regressor w² R. and an oracle group structure 0* E PxL, such that for all j [P] and E [4], 07, 1 if j belongs
group I and O otherwise. We consider P = 100 features, N = 20 observations, T = 500 tasks, and L = 10 oracle groups. For every task t [T], generate the oracle regressor wt and the data (Xe, 3r) follows. The regressor wi is generated such that its values are non-zero in one group chosen at random. In particular, we study the datasets as These values belong to the interval [-1,- U [a, 1] as 0 < a S 1 varies. We point out that in Frecon et al. (2018), w are considered binary, and the smaller a is, the more difficult the problem becomes. The design matrix X, E NxP is randomly drawn according to standard normal distribution and then normalized column-wistt The output y1 such that y, ~N((Xu 0.2Ip). Validation and test sets are generated similarly. Unlike Frecon et al. (2018), we allow groups of completely random sizes, with
8

---

Published in Transactions on Machine Learning Research (02/2025)
l" oracle
gr
0
ftop
0.0
20
0.2
feat ures
40
0.4
60
0.6
80
0.8
100
1.0
4 8 groups
10
2
6
10
2
8
4 8
10
groups
groups
groups
groups
Figure 1: Example of oracle group structure with random sizes and parameter a 0.5, and the corrisponding obtained by the relazation and rounding before the rounding procedure (ref. as r), after both simple (ref. s) and lop-1 hard thresholding rounding (ref. top), and the relax and penalize (ref. as p) methods.
Table 1: Test errors (mean standard deviation), i.e., the value of the upper level functions G, for the relaration and rounding (ref. as r), with both simple (ref. as s) and top-1 hard thresholding rounding (ref. top), and the relaz and penalize (ref. p) methods, over 3 runs of incqual and random group structures, for (0.1, 0.5).
INEQUAL
RANDOM
G(A",6")
0.04 + 0.00 0.05 + 0.00 0.06 + 0.00 0.06 + 0.00 0.07 + 0.00 0.09 + 0.00
G("","))
0.04
0.00
0.00
0.00
0.07
G(A7,0")
0.06 1: 0.02
0.05
0.00 0.06 1: 0.00 0.12
0.05 0.09 1 0.03 0.14 0.06
G(A",699))
0.04 + 0.00
0.05 + 0.00 0.06 + 0.00
0.05 = 0.06 + 0.01 0.07 + 0.01
G(2",6") 0.04 + 0.00 0.03 + 0.00 0.06 + 0.01 0.06 + 0.00 0.07 + 0.00 0.09 + 0.00
G(A,6") 0.05 0.00 0.05 0.00 0.06 0.01 0.05 0.00 0.06 + 0.01 0.07 0.01
predefined criteria. In particular, we consider two settings: the unequal one, with half groups of size 5 and half groups of size 15, and the random one, where the size of the groups are allowed to be different and are calculated as follow. We generate normally distributed random values, apply the softmax operation to obtain L percentages, and use these percentages to distribute the P features across the different groups. All the results are averaged over 5 runs. See Section for more details.
We compare several methods, which produce the following quantities: (X", obtained by pure relazation method, without any rounding, (Xr, 0*) obtained by a simple rounding of the relaxed solution, (X",gto) obtained by top-1 hard thresholding the relaxed solution, mcaning assigning each feature group, and finally (XP, "P) obtained by the proposed relax and penalize method. In Figure we first show an example of the different group structures retrieved by the various methods compared to the oracle group structure 8", for random synthetic dataset with 0.5. We can notice that using directly the relazed solution, some values are less than 0.5. As result, after simple rounding, some rows may end up as zeros, leaving Those features unassigned to any group. Then, we evaluate the methods using two performance measures, which are also evaluated at the oracle group structure 6*, The related results are reported in Table [ and Table [ Notice that 8*, 0², grop do are binary instead 0" might not be so. Overall, these preliminary experiments on group lasso problem show that the proposed method and the relazation and rounding method with top-1 hard thresholding perform essentially the same, and they both preferable to
dominant.

---

Published in Transactions on Machine Learning Research (02/2025)
Table 2: Reconstruction errois (mean + standard deviation), i.e,, Frobenius norm of the difference of the oracle regressor and the obtained regressors, for the relozation and rounding (ref. as r), with both simple (ref. as s) and top-1 hard thresholding rounding (ref. as top), and the relaz and penalize (ref. as p) methods, over 3 runs of inequal and random group structures, for a
0.3,
INEQUAL
RANDOM
0.1
0.3
0.5
0.1
0.3
0.5
[wx("", -00 - w"
4.20 + 0.21
5,24
4 0.19
4.67
= 0.15
5.34
+ 0.18
5.96
+ 0.16
6.69
+ 0.15
[ReeAA 8-) w= "I
4.73 = 0.35
5.04
0.05
5.13 = 0.22
5.50 - 0.24
6.10
0.25
6.86
0.19
[[w("".0") - w= 11
7.93
+ 1.52 5.99 + 1.17 6.63
= 0.16 11.17
# 2.51 9.17
+ 2.05
11.95
+ 2.72
IintA" "000)) w= 1|
5.10 + 0.37
5.99 0.15
5.40 + 0.16
5.93 + 0.16
6.50 + 0.41
7.18 0.25
[we(A",0" - "" 11
4.20 + 0.20
5.32
0.20 4.69
0.15
5.33
+ 0.16 5.92
0.11
6.75
0.12
[|0[ .00) - w w'
5.15 +: 0.29 6.04 0.11 5.54 1 0.18 5.94 1 0.17 6.57 0.39
7.17
0.23
the relaxed and simple rounding procedure. We believe that the effectiveness of the top-1 hard thresholding is due the the fact that we are considering nonoverlapping group structures which put strong constraints on the binary variables, since it is all about identifying one nonzero entry for each feature. Finally, it is worth noting that the group lasso problems used in the study are randomly generated synthetic problems. As such, they appear to be less challenging compared to the real-world problems addressed in the next experiment.
5.2 Data distillation
We now present the application of data distillation. Data distillation a process that synthesizes compact summaries of large datasets, enabling efficient model training and inference. Preserving essential information while reducing size allows quicker processing and improved performance in various applications. In [aachdeva & McAuley 2023), the authors give an extensive survey on data distillation and propose bilevel optimization model to handle the task (see Section 2 in Sachdeva & McAuley (2023)), which is the same model described here. We optimize the lower-level problem exactly, and the upper-level problem with a stochastic projected gradient descent. We test the relaration and rounding, with both simple and top-k hard thresholding rounding Zhang et al. 2022,, and relox and penalize strategies over two real datasets, showing the effectiveness of the last one.
Problem setting and formulation. Given a training dataset that needs to be distilled Dirain [(a)rmin .y. ( 1.m and data budget T E zt, data distillation techniques aim to synthesize high-fidelity data summary Dirain = {xttrain ) with 7 < m. Given validation set D = {(x)a) . . ) the data distillation task can be formulated as the following bilevel optimization problem
min of 10
gual (C(b)) with ((v) argmin gtrain + $|511
(11)
with validation loss goal, weighted training loss grrain = En u.l(ztrain yf train .),, regularization parameter & E RR u being a binary vector of dimension m indicating the samples in Durain and e v = T is the knapsack constraint to take into account the budget. Therefore, we wish to have i.- = for the 5 most representative samples.
syn
A simple approach to solve Problem 11 is to relax it by allowing the v,'s to vary within the interval [0, 1], projecting them to the region defined by the knapsack constraint, and then rounding them at the end. In particular, in our case we suppose x;, 2; E Rd as well as yi, Mj E Re and we consider Ç = (W, b) a linear model with weight W and bias as well as gval and l being mean squared error losses. Therefore, the aim is to solve the bilevel integer problem
min 1 n _e( ver
( + bb())= - val j=1
2n
(12)
1
with (W()),b())) = argmin
Ug W x
train + - y train 12 + W/]?
W WERexd.bER m
10

---

Published in Transactions on Machine Learning Research (02/2025)
We indicate with θ { E [0, e-v= e-v=rj. and with Obin θ m
Proposed method. Using the approach presented in Section 1 we avoid the final thresholding and directly optimize the following problem
1
min (0 e
W (o)a, + b((v) "j
2n
==1
(13)
1
with (W(e),
argmin
Ui W Wa Viriain
train
y1 train 12 [W]?
We bER" m
We solve the lower-level problem exactly, obtaining
W(v) (200)(1()00 c.(.))) (" (_)x(x)+ +x)x) sla)
b(u) 0. W(u)
(14)
m
with
m
Cx(XY)) Σ
U (v) train
Fe (x. T.,)
being the cross-covariance matrix,
Cx(X) Σ
(1
Fx. Fz.
being the covariance matrix, and
F
Golli
1%
Σi=1 U/
1=1
i=1
All the results are averaged over 5 runs. See Scction for more details. We can also write the problem as
min eval (val (c)) with VE [0,1)" eJu=T.
(15)
We solve the upper-level problem by means of a projected stochastic gradient descent method. To efficiently perform the projection over the knapsack constraint, for further details. Now, since W(v) and b(x) are smooth w.r.t. the objective in (15) satisfies Assumption
the Kiwiel algorithm (Kiwiel 2008); see Section D
and hence, in view of Theorem and Theorem 3 we can consider the relazed and penalized version of
Problem 15 ie., min e (S(w())) + ((x) with v E [0,1
e vw=
(16)
and state that, if e small enough, the two problems 15 and 16 share the same global minimizers.
Numerical experiments. We tested the proposed method on the data distillation problem by performing experiments on two real-world datasets. First, music (Bertin-Mahieux 2011), a dataset with song features from 1922 to 2011 used to predict the release year based on 90 attributes, including timbre averages and covariances. Second, blog (Buza] 2014h, dataset containing features from blog posts, focused on predicting the number of comments received in the next 24 hours using various attributes. For each dataset, we address Problem 12) by using a training set for the lower level and validation set for the upper level. We vary the distillation budget at 10 %,, 20 %, 30 % of the training set size; see Section D for more details. We run the experiments with the relazation and rounding, with both simple and top-k hard thresholding rounding, and the relax and penalize strategies, and we report the results Table First, we compare the final objective values of the upper-level problem obtained from relazation and rounding, with both rounding strategies, alongside those from relax and penalize, including the actual number of training samples selected in Duaain Next,
11

---

Published in Transactions on Machine Learning Research (02/2025)
Table 3: Experiments on the regression task across two real-world datasets: music and blog. The distillation budget is varied at 10 %, 20 %, and 30 % (pere column) of the training set size. For the relozation and rounding, with both simple (simple) and top-k hard thresholding rounding (top-k), and the relar and penalize (penalize) methods, report (mean + standard deviation over 5 runs) the values of the upper level function (before rounding in brackets) for the validation and test sets, the cardinality of the synthesized set, and the RMSE.
dataset pere
mothod
g
Dlesin
plast
RMSE
music
10 23186 simple
126.85 + 1.37 (58.57 + 0.02)
12764.20 = 28.63
128.61 + 1.37
16.04 + 0.09
top-k
65.60
0.32 (58.57 0.02)
23186.00
67.02 0.30
11.58 1. 0.03
penalize
64.87 + 0.70
23186.00 :: 0.00
65.96 + 0.08
11.49 + 0.01
20 46371
aimple
84.84
0.40 (53.37 + 0.01)
24967. 00 = 47.02
86.19 0.41
13:13 = 0.03
top-k
54.61
0.02 (53.37 + 0.01)
16371.00 + 0.00
55.82 0.03
10.57 = 0.00
penalize
54.20 + 0.02
46371.00
55.45 0.03
10.53 0.00 0.00
30 69557
simple
64.91
0.11 (50.93 0.00)
38250.20 = 23.68
66.15 0.11
11.50 1: 0.01
top-k
50.71 + 0.02 (50.93 0.00)
69557 00 + 0.00
51.91 0.02
10.19 = 0.00
penalize
50.52 + 0.01
69557.00
51.69 0.01
10.17 + 0.00
blog
10 5240
simple
2890.77 +: 240.03 (297.17 0.10)
515,00 5,52
3048.3
276.60
78.02 +: 3.47
top-k
373.36 5.20 (297.17 0.10)
5240.00 1 0.00
287.96 1. 4.36
24.00 1. 0.18
penalize
326.64 +: 23.61
5240.00 + 0.00
217.87 +: 1.74
20.87 + 0.08
20 10179
simple
2209.31
35.05 (292.37 0.01)
80 4.02
2283.30 + 11.51
67.57 0.61
top-k
306.08 + 1.76 (292.37 + 0.01)
10479. 00 + 0.00
219.44 + 1.76
20.95 + 0.08
penalize
296.77
10479.00
207.90 + 0.43
20.39 + 0.02
30 15719
simple
13972.08 + 11300.87 (327.78 + 19.11)
10447.00 + 23265.78
15134.38 + 10849.34
156.81 + 84.26
top-k
360.31 d: 27.39 (327.78 1. 29.11)
15719.00 00 1 0.00
297.70 80.29
24.23 1. 3.24
penalize
352.68 2.16
15719.00 0.00
247.87 1 1.11
22.27 + 0.05
evaluate both methods by optimizing the same upper level function on a test set using the selected Dtrain sets, reporting the objective value and the root mean square error (RMSE), common metric for assessing regression model performance. Similar to the group lasso structures discussed in Section [.] the relazation and rounding, with both simple and lop-k hard thresholding rounding methodologies, initially achieves low objective function value at the upper level, but this value increases after rounding. In contrast, the relax and penalize method successfully finds an integer solution with a low objective function value. Additionally, the penalty method selects a number of training samples close to the budget, while the relaration and rounding strategy results in a relaxed solution with only few components above 0.5. The simple rounding hence leads to fewer samples and ultimately not utilizing the full budget, while the rounding based on top-k hard thresholding naturally leads to a solution that satisfies the budget constraint. When applying the selected Dirain to a test set, the relaz and penalize method always achieves lower values for the objective function and RMSE, leading to a better overall solution with respect to relaration and rounding, both simple and top-k. In Section D.4 we report the evolution along the different steps of the quantities reported in Table 3 for one setting.
6 Conclusion
In this paper, we studied the idea of relaxing the integrality constraints and using a penalty term to handle mixed-binane bilevel optimization problems arising in hyperparameter tuning of machine learning systems. Besides a result concerning the equivalence in terms of global minimizers, sufficient conditions for identifying mixed-binary local minimizers are stated. These thcoretical results naturally lead to devise penalty method that is, under suitable assumptions, guaranteed to provide mixed-binary solutions. The reported numerical results highlight that our method is competitive with state-of-the-art approaches based on relaxation and rounding for the group lasso problem and outperfo these methods on the data distillation task.
References
Michael Arbel and Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimization. International Conference on Learning Representations (ICLR), 2022.
Juhan Bae and Roger B. Grosse. Delta-stn: Efficient bilevel optimization for neural networks using structured response jacobians. Advances in Neural Information Processing Systems, 33:21722 11-21725-21737 2020.
12

---

Published in Transactions on Machine Learning Research (02/2025)
Kristin P Bennett, Jing Hu, Xiaoyun Ji, Gautam Kunapuli, and Jong-Shi Pang. Model selection via bilevel optimization. Tn The 2006 IEEE International Joinl Conference on Neural Network Proceedings, pp- 1922 1929. LEEE, 2006.
Thierry Bertin-Mahieuxx Year Prediction MSD. UCI Machine Learning Repository, 2011. DOL: http:///tbbooog1100244/////////
J.Frédéric Bonnans and Alexander Shapiro. Perfurbation Analysis of Optimization Problems. Springer- Verlag, New York, 2000.
Zalán Borsos, Mojmír Mutný, Marco Tagliasacchi, and Andreas Krause. Data summarization via bilevel oplimization. Journal of Machine Learning Research, 25(73):1 53, 2024. URL http::/jmmr... httt:://jmll..rr/ppaprr..
v25/21-1132.
Krisztian Buza. Blogbeedback.
UCI
Machine Learning Repository, 2014.
DOL:
https://doi.org. 1 10.24432/C5883F C58S3F.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in Neural Information Processing Systems, 27, 2014.
Asen L. Dontchev and Tullio Zolezzi. Well-posed optimization problems. Springer-Veriee Berlin., 1993.
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.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinor (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1972 1982. PMLR, 09 15 Jun 2019.
Jordan Frecon, Saverio Salzo, and Massimiliano Pontil. Bilevel lcarning of the group lasso structure. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 8301-8311. Curran Associates, Inc., 2018.
Franco Giannessi and Niccolucci. Connections between nonlinear and integer programming problems. Symposia Mathematica, volume 19, pp. 161-176 Academic Press New York, 1976.
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 Proceedings of Machine Learning Research, pp. 3748 3758. PMLR, 13-18 Jul 2020.
Bahman Kalantari and J Ben Rosen. Penalty formulation for zero-one nonlinear programming, Discrele Applied Mathematics, 16(2):179-18) 182, 1987.
Krzysztof C. Kiwiel. Breakpoint searching algorithms for the continuous quadratic knapsack problem. Mathematical Programming, 112:473-499 491, 2008
Thomas Kleinert, Veronika Grimm, and Martin Schmidt. Outer approximation for global optimization of mixed-integer quadratic bilevel problems. Mathematical Programming (Series B), 2021a. doi: 10.1007/ s10107-000-0060012
Thomas Kleinert, Martine Labbé, Ivana Ljubič, and Martin Schmidt. A survey on mixed-integer programming techniques in bilevel optimization. EURO Journal on Computational Optimization, 9:100007, 2021b. ISSN 2192-4406. doi: 10.
Stefano Lucidi and Francesco Rinaldi. Exact penalty functions for nonlinear integer programming problems. Journal of oplimizalion theory and applications, 145(3):479-488 488, 2010.
13

---

Published in Transactions on Machine Learning Research (02/2025)
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-basse hyperparamcter optimization through reversible learning. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 2113 2122, Lille, France, 07-09 Jul 2015. PMLR.
Alexander Mitsos. Global solution of nonlincar mixed-integer bilevel programs. Journal of Global Optimization, 47(4):557 582, 2010. doi: 10. 00000//00980000--00
Fabian Pedregosa, Hyperparameter optimization with approximate gradient. In Maria Florina. Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 737-746, New York, New York, USA, 20-22 Jun 2016. PMLR.
Madabhushi Raghavachari. On connections between zero-one integer programming and concave programming under linear constraints. Operations Research, 17(4):680 684, 1969.
Noveen Sachdeva and Julian McAuley, Data distillation: A survey. Thansactions on Machine Learning Research, 2023. ISSN 2835-8856. URL https://openreviiet hwtp:///ww.....ooooo//o////////a Survey Certification.
Yingjie Wang, Hong Chen, Feng Zheng, Chen Xu, Tieliang Gong, and Yanhong Chen. Multi-task additive models for robust estimation and automatic structure discovery. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Newral Information Processing Systems, volume 33, pp- 11744 11755. Curran Associates, Inc., 2020.
Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68:49-67, 2006.
Yihua Zhang, Yuguang Yao, Parikshit Ram, Pu Zhao, Tianlong Chen, Mingyi Hong, Yanzhi Wang, and Sijia Liu. Advancing model pruning via bi-level optimization. In Advances in Neural Information Processing Systems, 2022.
Peng Zhao, Guilherme Rocha, and Bin Yu. The composite absolute penalties family for grouped and hierarchical variable selection. The Annals of Statistics, (6()))33668 3497, 2009.
Bo Zhou, Ruiwei Jiang, and Siqian Shen. Learning to solve bilevel programs with binary tender. In The Twelfth International Conference on Learning Representations, 2024.
A Auxiliary results
In this section, we give a number of technical results related to the penalty function &o used throughout the paper. We recall that yp: [o, 1|2 + R is defined as
(())= = Σ 0,(1 (1).
8=1
Moreover, we denote by [p] the set {l..... p} and by ||-I1 the Euclidean norm in RP. Occasionally, we will also used the norms
|10|| Σ 10.1 and ||0]]>0 max 0z)-
15:55
Lemma 1. Let wh: [0, + IR be such that
e 1]: s(1) 1(1 - 1)-
Let a e 10,1/2] Then, for every ti E
10, 1] have
f1 + t2
2 a
(12) - ((+1)) > 2n 1/2 - -11-
2 2
14

---

Published in Transactions on Machine Learning Research (02/2025)
Proof. Let 12 [0, 1]. One can easily check that
- - (tt1) = (1 - (t1 + (t)))( - t1).
Therefore,
11 + 1/
1
(12()) (tt1) it1 + 12 1/ 11
t/ t1
20 t1l-
2
2
Lemma 2. Let a E [0, 1/2] and 0, E [0, be such that the following holds:
0, + 0
1
ViE lp]: 0g +0
a
and
0j
2 0,
2
Then, -(0'))((() 2 20 10' - A||
Proof. Let 0 E [0, 1 be as in the statement and let
{i [p] 0. * 0.). Then,
8; + 8
IIEI:
2 o
and (0,)) - ((,)
2
2
and hence, by Lemma
we have
s0((") (00)= = Σ (00))) - (0.))
iE1
Σ (V((') v(00) 2 20 > 00 - 0:l
iE
iE1
0|] 2 20 - -B11. 2o 16'
where we used I|-II $ I1-I]a for the last inequality.
Remark 5. Lemma g says that if the components of the mid point (0 /22 bounded away from 1/2 and the componentuise distance from 0 to 1/2 is larger than that of 0' to 1/2, then sp(0)) =0() can be bounded from below by ||0' O||; to a multiplicative constant.
Remark 6. The conditions on 0 and 0' required by Lemma 2 are satisfied if
(0, 1/2)(0) 1/2) 2 0,
Vi [p]: 0, 0,06
10% - 1/2| S 10: - 1/2),
20 < 10 1/2).
Indeed, in such case we have
0 0
0; + -1-
1
1
2 0 0%
0,
0
2 a,
2
2
2
where the equality in (+) is due to the fact that
(0, 1/2)( 1/2) 0, 1/2 < 10, 1/2
(0,
S 0 < 1/2 or 0, 2 2
Corollary 1. Let a E [0, 1/2] and 0 E {0, 1P. Then
vo [0. 1p:: ||0 0|| s 1 2x
(000)) 20 20 10' 01-
15

---

Published in Transactions on Machine Learning Research (02/2025)
Proof. Let 0 10 and 0' [0,1]] 1P.. We will check the conditions in Lemma 2 Let i E [p]. Since
10: 1/21 = 1/2, the condition 10' - 1/2 I 00 1/2 is automatically satisfied. Now, note that
0 + 0
0
_ 1/2 10: 0.))
0:
20, -
0, + 0g
0g
1
0,
0
5
10, -.1)-
2
Therefore,
0g + 06
20
00 0,1 2 20 10, 0.1 S 1 -22
and the first condition in Lemma 2 is then equivalent to the condition 1 - 011xc S 2a. The slatement.
follows by recalling that I1-1loo S II-II.
Remark 7. It is clear from the proof of Corollary 1 that, in fact, it holds
AA' E P:: ||0' 2| S 20 20
=00)) 2 20|10' - A|.
Lemma 3. Let 0 E (0, 13, 0 E [0. 1l,, and E IR be such that 110 2 < c < 1.2 Leb
0f = (1 1)0 + 10 with LE [0.
Then,
(00) p(0)) 2 (1 2c)] 811.
Proof. Since 10,-0,1 < < 2/2 holds for all ,,..., n, we have
1
1
1
= 0
< 10, 0.1
+
0,
<
c
0
2
2
2
2
which implies
1
0,
c.
2 2
Moreover, since 0, E {0,1) 1} and |0, - 0,1 < <
21 we have
0: = = 8; 0 0 <<< 2'
0. = 1 <1 0, 0,,
and, hence, since 0f is between 0, and 0,, it holds
1
1
0
2
2
2
so that
0 + 0
1
1
2
2
2
(0)
+
0,
1)
2
0
2
+
0,
-
//
1
0:
+
0.
>
21
1
1
2
2
Therefore, by Lemma 2
(0)
(0(0)) > (1 2c) 0|| holds.
16

---

Published in Transactions on Machine Learning Research (02/2025)
B Proof of Theorem
For the sake of brevity, set
argmin (
G( and S(c) argmin G(O, + 9000).
(e (e.))xxe
E
Recall that Ohin nn 10, Let Pe 10, 1f and let 6 E 10, p)/L[. We define the open set
U = Bp(
0
where p is chosen small enough to ensure that O U x 3
Let 0 be minimizer of over the compact
set θ \ U. Then, clearly
40 EUIU: ((0) 2 (0)) > 0.
(17)
(Note that, since g U, then 0 & IP, and hence there exists i E [p] such that 0; E jo, 16 which implies that (00)= 2 0,(1 - 0.) > 0.) Thus, since
lim 6-0
p() -00,
there exists ě E 60 such that
EEE 10,6]
(p()) >
sup G inf G.
(18)
Axerin
Ax(e)))
Now, we let E J0, é] and show that S(e) C Obin- Let (X",0) S(e) and suppose, by contradiction, that (A*,0% 0*) & Opin- We can have the following two cases:
(a) Let 0" U. Then, there exists 0 Opin such that l BB) Thus, in view of Assumption and Corollary [ we have
G(X",0) - G(X,,0)) s I.100 Oll 1 12---1100 011 s 1 =p((0)) = -0((0) -0(
8
and, hence,
G(A", 0) + (0) < G(X, -
which yields a contradiction since (X",0% is a global minimizer of Problem 3
(b) Let 8 & U. Then (A*,0") E A x (e U) and hence, recalling and
18 we have
G(A", 0*) + 1 =p((0)) > inf Ax(e)U)
1 G
= (0")
inf Ax(e)U)
G
& ((()
sup
G
Axera
2 G(O, A)
(0))
for any (0 A x Obia CA θ, which gives again contradiction.
Thhis that there cxists 0* θ such that for every 0 Osins it holds ||0 0- > p. This condition met if pick
8* {0, 132 (see Assumption [i] and (taking into account that Obin e {0, 13. is finite set) choose p such that < p inface -81]
17

---

Published in Transactions on Machine Learning Research (02/2025)
Thus, in both cases we get contradiction and therefore necessarily (A*,8") A Obin. Now, if we take (x,0") E S(e), since (A*00) 00) E A x Ohi, we have
G(A", 07) + p(00) = G(
E( Obin CAxe.
Thus, for all (0 E A x θ Choosing 0** E SE)), since (X*, 0*) E A x bin have
bin: G(X, 0*) < G(B, A), meaning (A*,0*) S. Vice versa, let (A*,0*) E S.
G(X* 0) + &
(0)) = G 0)) S (0) G((;,00
=0
1 (0) = min I G( 00)
G(O, + -
(0,A))εAxB
Hence, (*) E S(e).
C Details on the group lasso application
In this section, report on the details regarding the group-sparsity structure estimation in regression problems presented in Section 5.1 Firstly, we discuss the extension of the algorithm presented in Frecon et al. 2018 to the mix-integer case. Secondly, we report the details of the performed experiments.
C.1 Extensions to (Frecon et al., 2018)
In Frecon et al. (2018). Problem 9 is considered only in the integer hyperparameter 8, while the real hyperparameter À is supposed to be fixed. Here, report the extension to the optimization in both the hyperparameters 0 and A. In particular, Frecon et al. (2018) do not solve the lower-level problem exactly, rather consider the following approximate problem, providing conditions under which it converges to the exact one as the number of inner iterations grows:
(0) = PXL
Vi= 0......... 1- ((+1 ((,)0
min (0,) with (0A))A
(0,) 2) Bl,l (0, A), (0,)) = ET= Ci(wl))
and A: RXL x x RPXL as well as B PXL x A A We denote by 0,A(u, 0, A) the partial derivatives of A with respect the variable and 02A(u,, 8, A) the partial derivatives of AA with respect the variables À and The same notation is used for the partial derivatives B. When specializing to the case of group lasso, A and B take the expression reported in Section B.1 of Frecon et al. (2018) supplementary material:
A(u,0,A)= (v) + + AoB(u,
B(u,0)=v/1 = V
with Φ being the separable Hellinger-like function defined in Definition 3.2 in Frecon et al. 2018 7 > 0
is some given step-size, f is the Fenchel conjugate of f. and A] is the transpose of the operator Ag as defined in Problem 3.1 and Problem 3.2 in Frecon et al.] (2018). Therefore, noticing that the dependence on 0 is hidden in Φx, we only need to update dzA(u, 8, A), because does not depend on f and A, 8, A) is the derivative by u. We recall that, for every u = (w)12ıg1 E PxL and = (11)2251 E PXL for every L,
v,4(u)= Vo(u)=
U1
and Vv) (o)
/X2
XX2
18

---

Published in Transactions on Machine Learning Research (02/2025)
holds. Therefore, obtain
(u, = (1+1 (
(x(2)
(12 (
and
,2A4 (u, (u)) (2 + 2x((2)
(er( (((2))
V1+ + (A)
(1+ (1er
with
(A)
MI + 70: o Bu,, 0) and of(A)= (1 + ||m M4-
V1+ 1u:13
For clarity, we re-write (A) and e/(2)
(1(A) un di, o((2) k m
with
(1 13) di 40 OB,0, B(u,0).
VI+ 1
Our aim is to compute 0zA(u, 8, A) with a E Rxt, where the partial derivative is with respect to all the hyperparameters, meaning the group of variables (0, A). Considering that
(b, E x R: 0,A(u,0,)))) B) A,, arA(u,
we have
(02A(u, 0, 0,100,)), -00,Alu, (10
(b, ObAu,, 0, (0,
(19)
= ((b,)). (8g 8, (,)
It follows that
02A(u, A) (0aA(u, u A) AQ, A),
Thanks to this result, hyperparameters to the hypergradient computation, substituting the expression of 02A(u (0, A), 0, A) ( (1+1)
Algorithm 2 in Frecon al. (2018) extended to the optimization in both
in the calculation of (66 (with i iteration index); see Algorithm 2 In particular, in our case, we have an additional component of 7(0) regarding the hyperparameter X, that we call gg0) E R. Therefore,
3(0) (0 A), (1-1) + g(++1)
L
((+1)) + g(++
holds with
(mr(A) + (a(())).(+t1))
((n((), (0t)) (1 (1+11(((11)) (A)
(w (O.A),,, ((t1))
/I+ (1)a
C.2 Experimental setup
In Section 5.1 we conduct experiments on synthetic datascts for the group lasso problem. Regarding the details of the experiments, we implement the framework of Algorithm [ by solving a sequence of outer optimization problems pk type (10) w.r.t. (X, We select e = 10a such that the penalty term does not dominate the function, making the evaluation the first point behave similarly to the unconstrained version. In order to better exploit the hyperparameter B, we perform an ablation study for the setting with inequal group sizes and 0.3. From Table 4 we notice that high leads to higher number of external
19

---

Published in Transactions on Machine Learning Research (02/2025)
Algorithm 2: Hypergradient computation (reverse mode)
Require: Group structure 0, number of inner iterations 9- Initialize (00) (0, A) = RPxL
for i to q do
(0, A) - A( (1- (0,
end for
Output: 1. u (0. X),
( (0, A), (0, =
Initialize a, (( (0, A), 0, VC(xl9) A),b, 0rB(u (0, (), A) (C(20) (0
for i q- 1 to 0 do
(+)) (B, (T ((++1)
((0) = (gA((u()) (0. a(it1) + 6(++1)
10
g(0)
+ g(+11)
end for
Output: 2. Hypergradients Vol((0 (0 ,00, (2 3(0)
18
Table 4: Ablation study hyperparameter / for the setting inequal group size and a 0.3.
outer iter
G(*"
[] 0*)
w" w[]l
0.1
4.33
0.58
0.06
1 0.00
5.86
0.17
0.3
7.00
0.00
0.05
0.00
5.71
0.14
0.5
11.33
+ 0.58
0.05
0.00
5.54 - 0.11
0.9
47.00
5.29
0.07 0.03
5.87
1.02
iterations and a longer rumning time. Across the different B, the algorithm seems to find different local minima. The best performances, in terms of test error and reconstruction errors, are reached with 8 = 0.5, which we used for all the experiments. The slopping criterion the condition dist {0, PxLL) < tol
with tol 10-2 tolerance. The lower-level problem in (8) solved using Algorithm described in Frecon et al. (2018) stochastically, setting the batch size to as in their paper. Therefore, at each iteration, we consider one W/, = 10 g = 500 inner iterations, and 0.99 m// the inner step size. For the upper-level optimization in f10), we utilize SAGA (Defazio et al. 2014 and we distribute the inner iterations for each external iteration as follows: [5000, 5000, 2500, 2500, 2500, 2500, 2500, 1000, 1000,...]. The step size is set to T/0.025 for 8 and is multiplied by the preconditioner c = 10- for X. The hyperparameters and X are projected to the unit simplex (A" and the box [10 3 1], respectively, and they are initialized to Pa(L-'Ipxa + (Opxx. 1....-.LII-pp. and 2 we run all the methods with the same parameters and the same amount of votal iterations. Here report also in Figure] the evolution of the quantity dist (85 9bm)) along the iterations for the relar and penalize method, showing that for h sufficiently large it abruptly reaches O as soon as it is below & predicted in Remark
X 10-1 and 8
For a fair comparison, in Figure I and Tables
0.5
1.0
1.5
2.0
255
-10
Figure 2: Evolution of dist (0t Obi)) for the setting with inequal group sizes and 0.3.
20

---

Published in Transactions on Machine Learning Research (02/2025)
D Details on the data distillation application
In this scction, we report the calculations regarding the data distillation issue presented in Section 5.2 Firstly, we present the calculations to solve exactly the lower-level problem. Secondly, we report the calculations of the gradient of the upper-level problem needed to perform the stochastic gradient descent. Finally, we report the details of the experiments that were performed.
D.1 Lower-level calculations
The lower-level problem that we want to solve in 13 given by
min W.b
W train + b - |
2 + W|
(20)
with aqtain E IRdd vi mma E ERR, W E Rexd atrain and ytrain for simplicity. We define these quantities
ER. In the subsequent sections, will use æ and y instead of
Di=1
Σ i= Wali
y
= x;
I.
01 y1
y.
1/
Σ U/-
It follows that
Σ
U
U = 0, Σ v. = O.
(21)
Considering the first part of the objective function in 20
obtain
m
m
us Wa, +
yi 12
U/ [
0 + W + b 2-12
2/12
Σ
0: W
0:1l
W + b 5/1
(22)
WW
U:Di, WJ + 17
i=1
1=1
1=1
u f. 0:112 + Σ
0 l + 017
Using this, Problem 20
is equivalent
min W.B
Wt, 0.11 + 2
| + b- b-
Therefore, the minimization can be performed separately the variables w and b, and Problem 20 is equivalent
min
m. W2, 8:11 s/| and b = ÿ - Wa.
W
We solve the first minimization in W by setting
m
m
2 m
U. (Wa; - J + 2sW = 2W
u + sId
m Σ
v.q.a.T
m 1=1
1=1
which is valid if and only if
m
W = m
Σ
250 + sld
1=1
21

---

Published in Transactions on Machine Learning Research (02/2025)
Finally, we obtain the formula in 14
Computationally, calculate (())2 for I2 by first solving
+ +ld)a==
in and then calculating
W(u)z= = Y)a
D.2 Upper-level calculations
We consider the upper-level problem in
[13
neglecting the constraints on un
min VER"
[w())x))) b(v) - y |2
(23)
2n
For simplicity, in the subsequent sections, we will use and y instead of xaa and yاo and we will refer to the objective function in (23) as (() with J R² + R.
To solve the problem with a stochastic gradient descent algorithm, we need to calculate the gradient of J(e):
8J(u) 00,
1
(V(u):;+bb) - x)) (
(WW(1) Ovy
ob(e)
2,
n
Ou,
1
(W())(x; - 2o) + -w)) (o)(c)
(xi Tz)
(())a))
"
Ovg
-i=1 vs
(24)
1
(W())(a; - 2o) go v)) (w(v)
(xt -io)
n
(W(v) - -x)) + Tu 5) (0) W()).)).
We will proceed to calculate following three maps
(w() Bmg
taking advantage of the expression given in
14 We consider the
Φ: R" Radd
miw - T.)(a=- - T.)",
vb R" + Rdd
Σ pi(2; - Zx) - - + sId,
U H
GL(d)
R dxd
A A
A-1
with (d) being the general linear group of degree d. Therefore, we can write
W(v) (()){(((v)) E aad
(25)
Notice that
(A)::: Rdd + Bddd
U A-A-
YU E gdxd
(26)
since
(pA +U) - (AA) (A + tU)- - - A-1
A 1 A (A++U)
(A -A+ - (U((+W))
(27)
Using
25
and
27 we can write
W (v + Iu)
W(v) slv + -w)
t
(ōlo + tu) + tu)) 6(v tt)p(((())
(28)
+ ő(v + -
= o(v + tu) p(b(1 tw)) ((v(v)) Φ(v tu) ((u) p(((v)).
22

---

Published in Transactions on Machine Learning Research (02/2025)
It follows that
[w) -
( (v)luioo))) -
(29)
-C.,(x, + -100000000000/0/oooooooooo------ + +ldd E Rudd
holds, where, in the second equality we used that
- -(0
Choosing u = Ej in we obtain
aw (u)
01p(v)
ad(w)
(X) +ldd
(30)
0oj
doy
From the definitions of σy and yo: we retrieve
ar. 0
Σ
m
1=1
m
Ui3;
Iz
Ovj Ih
V/
E= 12)2
m
2: 02
2:m
Vi
>x
U;
Oee yj
Do
Dj
Dug
Σi m
i== Us
Di=1
m
Us
Therefore,
0Φ(r)
Σ
611 [20 - _z0 T
Us
(Je 1.) x2)
Oz,
Juy
i=1
1=1
91
Em= Up
22 2
Ugūt)) &
n
im1
where used (1 in the last equation as well as
@v((v) = 65
Oug
Finally,
OW())
(C(XXY))C,(X)++111)) -8888 +8,87) (C.(X) + sid)-1,
Oug
and
0b(r)
OT.
(w(v)
X, (()) g5.
Ou,
De,
du,
Dv,
0
OW(v)
3z
X, - W(v)
Σ 14
Oug
Σ
0j
W (u)a,
dW (w)
D
U/
Ouj
As for the lower lever, computationally we calculate
ow(x), for Rd, solving the following systems Buy
(C.(X)+ 2, (C,(X) + =dda==
After solving the leper-level problem with the stochastic gradient descent method, we need to project the solution onto the simplex defined by the knapsack constraint. To do this efficiently, we utilize the Kiwiel algorithm Kiwiell 2008).
23

---

Published in Transactions on Machine Learning Research (02/2025)
Table 5: Ablation study hyperparameter for the setting pere= 20%.
mussie
blog
B
g
Fret
RMSE
g
g
RMSE
0.1
14.2
+ 0.45
58.77
0.12
60.59
0.12
11.01
+ 0.01
15.2 = 0.45
309.21 + 0.53
231.9
0.78
21.68
0.01
0.3
25.8
+ 0.45
58.16
0.15
59.63
1 0.16
10.92
+ 0.01
28.0
- 0.00
306.75
4 0.87
229.68
2.39
21.43
4 0.11
0.5
43.0
1 0.00
57.30
0.09
58.61
1 0.10
10.83
1 0.01
47.0
1 0.00
305.29
1: 0.34
225.26
2.11
21.23
1 0.10
0.7
81.2
10.70
0.01
88.8
0.84
219.09
1.81
0.9
258.0
1.87
54.23
+ 0.03
55.48
+ 0.03
10.53
2 0.00
291.3
+ 129.40
296.77
+ 25.52
207.90
+ 18.13
20.39
- 0.85
D.3 Experimental setup
In Section 5.2 we present experiments on the data distillation problem for two regression tasks involving the following world datasets:
music
(Bertin-Mahieux- 2011) is dataset that includes song features from 1922 to 2011. It consists of 463 715 training samples, with the first 231 857 used for training the lower level and the remaining 231 857 reserved for testing the weights afterward. Additionally, 51 630 validation samples were utilized for the upper level. Each sample represents a song, featuring 90 attributes (12 related to timbre average and 78 related to timbre covariance), with the year of release as the target variable (as an integer). The aim is to predict the release year of a song based on audio features.
blog (Buza 2014) is dataset containing features extracted from blog posts. It comprises 52 training and 7624 validation samples, with the first 1089 used for training the lower level and the remaining 6535 set aside for testing the weights afterward. Each sample represents a post with 280 features, and the target variable is the mumber of comments received in the next 24 hours (as an integer). The goal is to predict comments received in the next 24 hours using various features.
Regarding the details of the experiments, we implement the framework of Algorithm D by solving a sequence of K outer optimization problems P of type (16) w.r.t. v. The parameters are selected as explained in C.2 In particular, we initialize e = 10 for both datasets, such that the penalty term does not dominate the function, making the evaluation at the first point behave similarly to the unconstrained version. In order better exploit the hyperparameter 3, we perform an ablation study for the setting pere= 20%. From Table 5] we can notice that high 33 will create more thresholds until convergence, a higher leading to higher number of external iterations and longer rumning time. Across the different B, the algorithm seems to find different local minima. The best performances, in terms of test error and reconstruction errors, are reached with 3 0.9, which we used for all the experiments. The true stopping criterion is the condition {0, ( 1 < fol with tol = 10-2 tolerance. For each problem of type (16), we solve the lower-level problem exactly and the upper-level problem with stochastic gradient descent. In the lower-level problem, we set the regularization parameter to s = 102. For the upper-level problem, we use a batch of size 600 for computing time reasons, we perform 100 inner iterations for each problem (P and we set the step size to 10-3 for music and to 10-5 for blog. The hyperparameter is projected onto the simplex defined by the knapsack constraint and initialized at =I with being the size of the training set and being the budget. For a fair comparison with the relonation and rounding, with both simple and top-k hard thresholding rounding, we run the code with the same parameters and the same total number of iterations, rounding at the end. We perform the projection onto the feasible set defined by the knapsack constraints using the Kiwiel algorithm with tolerance 10-10 and 103 number of iterations.
We report in Figure the evolution of the quantity dist (v" @bin) along the iterations for the relar and penalize method, showing that for l sufficiently large it rapidly reaches as soon it is below 2 as seen in Figure 2 for the group lasso problem.
D.4 Additional results along the steps
In Figure + we report the evolution along the different iterations of the quantitics reported in Table 3 for the music dataset with distillation budget at 20% of the training set size. Since the solution can also violate integrality constraints through the iterations, the quantities [ glest and RMSE, referring to
24

---

Published in Transactions on Machine Learning Research (02/2025)
0.8
0.6
0.4
0.2
0
0.1
0.5
1.0
15
2.0
2.5
-10
Figure 3: Evolution of disto (v" Obm)) for the blog dataset and budget 20%.
the correspondent rounded value. The y-axis represents the internal iterations. Notice that, for example, the violation of the integrality raints for the relox and penalize method is not checked at each internal iteration, but only for the outer ones. We recall that all the methods under analysis evolve with the same total number of itcrations and start from the same point. Figure ! and [ shows the results regarding the relazation and rounding method, respectively using simple and lop-k hard thresholding rounding. We show the evolution of gral and grest both before and after rounding the solution (resp. in orange and teal), noticing that the objective function values increase after rounding. It can be observed that, for the relaration and rounding method with simple rounding, the quantity [ increases over the iterations but remains well below the total available budget (46371), while the top-k hard thresholding use the whole budget at each iteration by definition. For the relazation and rounding method, dist (u, Oba)) stays stable at 0.5, therefore, no integer solution found with both the rounding procedures. Figure shows the results regarding the relar and penalize method. From the plots of gal grest and RMSE, we can observe an increase after 25, 000 inner iterations, when the penalty term has higher weight in p Corresponding to this, it is apparent that the method finds an integer solution (dist (v, Obin) = 0) and that it saturates the budget ([Darain 46371).
25

---

Published in Transactions on Machine Learning Research (02/2025)
(a) gval
(b) Derain syn
(c) disto (v, {0, 1)m)
-104
0.55
600
0.5
4
before
400
0.45
2
after
200
0.4
0
0
0.35
0.5
1.5
2.5
3
(d) great
(e) RMSE
-104
-104
400
6
before
after
2
100
0
1.5
2
50
3
0.5
1.5
2.5
3
104
-104
Figure 4: Evolution of the quantities reported in Table 3 for the relazation and rounding method with simple rounding on the music dataset with distillation budget at 20% the training set size.
(a) eval
(b) Diraiu
(c) dist (u, (0, 13m)
-104
0.55
400
0.5
350
before
0.45
0.5
after
0.4
300
0.35
0.5
1.5
2.5
(d) feest
(e) RMSE
104
30
400
28
26
before
300
after
200
20
0.5
1.5
5
0.5
1.5
2.5
104
-104
Figure 5: Evolution of the quantities reported in Table 3 for the relaration and rounding method with lop-k hard thresholding rounding on the music dataset with distillation budget at 20% of the training set size.
26

---

Published in Transactions on Machine Learning Research (02/2025)
(a) eval
(b)
Dtrain syn
(c) dist (u, (0, 1)
-108
-10
Buddge
0.4
0.5
(d) grest
ee) RMSE
260
24
240
22
220
200
20
0.5
1.5
2.5
1.5
2.5
.104
1104
Figure 6: Evolution of the quantities reported in Table
3 for the relax and penalize method on the music
dataset with distillation budget at 20% the training set size.
27


Reviews:
[{"review_id": "YETYPrmxfh", "reviewer": "Reviewer_Sbp8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The analysis is done carefully. The authors are very clear about what assumptions have to hold in terms of smoothness, uniqueness of follower solutions, proximity of local solutions to binary feasibility, etc. and these assumptions are reasonable for the experimental settings they consider.\n- The method appears to work well on interesting machine learning problems.\n- Bilevel optimization (especially with some discrete variables) is fairly important and general, and there are probably broader applications of this technique.\n\nWeaknesses:\n\n- There are no substantial weaknesses to this paper that I can see.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider bilevel optimization where some of the leader variables are binary (the follower variables are continuous), under the assumption that the follower problem has a unique solution. This is a quite general problem with a lot of interesting real applications; the authors focus on machine learning problems that show bilevel structure.\n\nThe authors start by focusing on the leader’s problem only (leaving the follower’s best-response map implicit) and replacing the binary constraints with a penalty term from the literature. \n\nTheir main new result is that is that, for this penalty problem, and for small enough penalty term, all *local* minimizers that are sufficiently close (in $\\ell_\\infty$ distance) to a binary feasible point, will have to be binary feasible. (In their experiments, they actually check that the assumptions for this do hold.) They also extend old results showing that for small enough penalty term, the penalized problem’s global minimizer will be correct for the original problem.\n\nThis provides motivation for their simple but effective optimization algorithm. They gradually increase the penalty term, locally solving the penalized problem at each point. At some point, they will end up with a relaxed problem whose global minimizer is correct. In practice, this is nice but not directly relevant, because for nonconvex optimization, one can only really hope to find a local minimizer, but their new result at least guarantees that eventually, their local minimizers will be binary-feasible. Experiments are on two reasonable and well-studied (though slightly niche) machine learning tasks and show it works well compared to defensible baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "No requested changes.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1rpNth2rXt", "reviewer": "Reviewer_6nSq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* The proposed *relax and penalize* method introduces a novel approach to mixed-binary bilevel optimization. By incorporating a quadratic penalty term, the proposed penalized optimization—although formulated as a continuous relaxation—is theoretically proven to be equivalent to the original mixed-binary bilevel optimization (under certain conditions) in terms of global optimizers. Furthermore, additional analysis shows that local optimizers in the mixed-binary domain can be practically found by examining local optimizers of the penalized relaxation. This provides strong theoretical guarantees that are absent in the two-stage method used in prior work, which relaxes the bilevel objective to the continuous domain directly without a penalty term and then convert the continuous solution to a mixed-binary form.\n\n* Hyperparameter optimization with mixed-binary constraints is a problem that has practical applications, as demonstrated by the two test tasks used in the empirical section of the paper. The method proposed in the paper makes a step further in the research of suitable methods for hyperparameter tuning of machine learning systems.\n\n* The paper is overall well-written, with the proposed method and its theoretical contributions presented clearly and effectively. The remarks following the theorems are quite helpful for understanding the results themselves as well as the underlying motivations.\n\nWeaknesses:\n* My major concern about the paper is the mischaracterization of the methods in prior work and the choice of comparing against the *continuous relaxation and rounding* baseline:\n  * The paper claims that \"our method can outperform state-of-the-art approaches based on relaxation and rounding\", and in Section 5.1 the baseline is presented as the method of Frecon et al., 2018 [1]. However, the *continuous relaxation and rounding* baseline, as defined in the paper, is not an accurate characterization of the two-stage methods used in the cited related works such as Frecon et al., 2018 and Zhang et al., 2022 [2]. After solving the relaxed continuous problem in the first stage, these two baselines obtain the final mixed-binary solution based on the continuous solution in a quite different way than the *continuous relaxation and rounding* baseline in the paper.\n    * The *continuous relaxation and rounding* baseline in the paper obtains the mixed-binary solution by rounding each binary variable (hyperparameter) individually to 0 or 1.\n    * For the group lasso task, Frecon et al., 2018 obtains the mixed-binary solution by assigning each feature to its most dominant group (See Section 4.1 of Frecon et al., 2018). A continuous solution of $[0.3, 0.4, 0.2, 0.1]$ would be rounded to $[0, 1, 0, 0]$, assuming these four variables represents the grouping weights for one feature. In contrast, the *continuous relaxation and rounding* baseline would round the solution to the all-zero vector $[0, 0, 0, 0]$, not assigning this feature to any group, essentially violating the feasibility constraint of the original grouping problem that $\\sum_{l=1}^L \\theta_{j,l}=1$ for every $j \\in [P]$.\n    * Zhang et al., 2022 obtains the mixed-integer solution by doing a top-k hard thresholding operation to the continuous solution, which can be equivalently defined as getting the Euclidean projection of the continuous solution onto the feasible mixed-integer domain (i.e., the domain that is defined by both the mixed-integer constraints and the feasibility constraints). (See discussions of *Euclidean projection* and *top-k hard thresholding* in Zhang et al., 2022.) This would be a more suitable approach for the data distillation task. For example, with $5$ training samples and a budget of $3$, the continuous solution $[0.4, 0.9, 0.4, 0.1, 0.2]$ would be projected to $[1, 1, 1, 0, 0]$ with the top-k hard thresholding. The *continuous relaxation and rounding* baseline would round this to $[0, 1, 0, 0, 0]$, under-utilizing the budget.\n  * These differences between the prior work and the *continuous relaxation and rounding* baseline likely have a substantial impact on performance in the paper's test tasks. The *continuous relaxation and rounding* baseline is not suitable for these tasks as it produces excessive zero values in the rounded solution, leading to infeasibility (multiple features that are not assigned to any group) in Figure 1 and significant under-utilization of the knapsack budget in Table 3.\n  * The *continuous relaxation followed by Euclidean projection onto the feasible mixed-binary domain* method as mentioned above would align with the prior works much better, and it does not require specific knowledge of each tasks's structure. This approach would be a more reasonable baseline and would likely performe significantly better than the current baseline in the test tasks.\n\n\n[1] Jordan Frecon, Saverio Salzo, and Massimiliano Pontil. Bilevel learning of the group lasso structure. In Advances in Neural Information Processing Systems 31, pp. 8301–8311. Curran Associates, Inc., 2018.\n\n[2] Yihua Zhang, Yuguang Yao, Parikshit Ram, Pu Zhao, Tianlong Chen, Mingyi Hong, Yanzhi Wang, and Sijia Liu. Advancing model pruning via bi-level optimization. In Advances in Neural Information Processing Systems, 2022.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The optimization of machine learning systems can be formulated as a bilevel optimization, where the outer level optimizes the hyperparameters and the inner level optimizes model parameters given specific hyperparameters. For settings with binary hyperparameters, the mixed-binary nature poses a challenge to the optimization. Prior work often relaxes the binary domain dimensions to the continuous range $[0, 1]$, solves the relaxed problem, and gets to a solution in the original mixed-binary domain based on the continuous solution. However, this two-stage approach lacks theoretical guarantees for optimality in the mixed-binary domain.\n\nThis paper introduces a novel approach called *relax and penalize*, which adds a quadratic penalty term to the bilevel objective and optimizes over the relaxed continuous domain. The penalty term encourages solutions close to the mixed-binary domain. Theoretical analysis show that under certain conditions, this penalized bilevel optimization over the relaxed continuous domain is equivalent to the original mixed-binary optimization in terms of global optimizers, and its local optimizers are in the mixed-binary domain under some additional conditions.\n\nBased on the theoretical results, an iterative algorithm is proposed that applies an exponentially larger penalty weight to find local optimizers of mixed-binary bilevel optimization. The proposed method is evaluated against a two-stage approach that first solves the bilevel optimization over a relaxed continuous domain and then gets a binary solution by rounding each variable that should be binary. Empirical results show that the proposed method consistently outperforms this *continuous relaxation and rounding* approach across two machine learning tasks involving mixed-binary bilevel optimization.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* As mentioned in the weaknesses discussion, a more appropriate baseline—such as the *continuous relaxation followed by Euclidean projection onto the feasible mixed-binary domain* method—is needed to provide a reasonable empirical comparison between the proposed method and prior work on the test tasks.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TrawRWlYwf", "reviewer": "Reviewer_9wEJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "First I would like to express that this is not exactly my area of expertise, that said the paper is well written to still understand its motivation so thank you for that.\n\n### Strengths\n\n- The paper is well written and organized\n- The method proposed is theoretically grounded\n- The application show performance improvements\n\n### Weaknesses\n\n- One issue that I have is the $\\beta$ hyperparameter presented in Algorithm 1 and only referred in the appendix by giving it's value for each experiment.\n    - How were these values selected (grid search? If so what was the selection criteria, over what space)\n    - No ablation / impact study is provided in the paper (what is the impact of the $\\beta$, a high $\\beta$ wil create more thresholds until convergence, leading longer running time -- and maybe finding other local minima?) This should be reported and discussed.\n    - The $\\beta$ is fixed, this seems \"naive\" as adaptative values could be chosen (the more penalized the problem, the faster the convergence and during runtime have a $\\beta$ with higher values will have finer grains of precision)\n    - The number of problems to solve in App. C.2 is set to K=6 and in D.3 K=10. Shouldn't the sequence of problems to solve not have a limited number of steps and only be stopped given a stoppping criterion (based on the convergence/stationnarity of the objective and the constraints satisfaction)? In this case I would expect a curve representing the evolution of the objective along the different steps k and in parallel the evolution of $\\theta^k$'s violation of the binary constraint.\n\n- Table 1-2: Maybe I did not understand it correctly, but shouldn't *relax and penalize* be refered as *p* and not *r* (and switch with the rounding method name) in captions/first column. Otherwise as it represents test error / reconstruction error (to minimze) it seems that relax and penalize performs worse than the rounding method. Please either correct it or discuss more the results obtained.\n\n- The assumption for Theorem 3 that $d_\\infty (\\theta^k, \\Theta_{\\text{bin}})$, while being monitored (Remark 3) is briefly discussed but is also intriguing (not really a weak point more a curiosity). Has this condition ever been breached in the experiments in Section 5? If so, do you propose to simply project the obtained vector $\\theta^k$ -- via rounding maybe to combine with existing work. Can you minitor the evolution of this quantity during optimization and provide the results ? This would be of interest to show that the assumption is indeed verified.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a new approach for binary parameters in bilevel optimization.\nTheir approach is theoretically motivated and shows performance improvements in the case of reconstruction errors on two real datasets (data distillation problem) and in simulated regression context with group sparsity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses related to comments for:\n\n- Algorithm 1 and $\\beta$ hyperparameter\n- Table 1-2 possible issue\n- Add more discussion regarding the assumptions for theorem 3\n\n### Typos and technicalities\n\n- Misusage of `\\citet` and `\\citep` in the paper (almost everywhere), please correct it\n- Use either `\\emptyset` or `\\varnothing` but not both to be consistent (between main paper and appendices)", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Based on the back-and-forth with the reviewers and the revisions made, I am very happy to say this paper is now a quite clear accept, with contributions that are well supported.

There are a number of very minor comments that should be addressed before the camera ready:

 - Quoting from a reviewer: "In the latest version, the summaries of the empirical results in the introduction and conclusion sections have not been updated to accurately reflect the new experimental results added since the initial submission. For example, the conclusion currently suggests that the proposed method outperforms the relaxation and rounding baseline on both the group lasso problem and the data distillation task. This was the case for the old experiments in the initial submission which had a different baseline implementation, but with the latest experiments, the proposed method shows better performance only on the data distillation task. These summaries in the paper should be revised to align with the updated experimental results."
 - Minor formatting issues: 
    - Tables have inconsistent font sizes; if small font is needed in a table, please use small font for all tables.
    - There is an extra space before the period at the end of Table 3's caption
    - Some Remarks that have subpoints (i) and (ii) begin with a line break but others don't. I recommend adding the line break so that (i) and (ii) line up neatly.
    - In Table 1 and 2 and maybe elsewhere you have some instances of $\theta^{top}$ which should be styled as $\theta^{\text{top}}$ using a \text environment, otherwise the letters "top" are kerned incorrectly as if they were a product of one-character variables. This might also be the case for "music", "blog", and "perc" in Table 3, where probably \emph is more appropriate if needed.
Decision: Accept (poster)