Learning Configurations for Data-Driven Multi-Objective Optimization
Authors: Zhiyang Chen
Hailong Yao
Xia Yin
Venue: ICML 2025 poster (2025)
Keywords: Data-driven algorithm design
Algorithm configuration
Sample complexity
Primary area: theory->learning_theory
TL;DR: We provide learning-theoretic foundations of algorithm configuration for multi-objective optimization algorithms.

Abstract: Multi-objective optimization problems arise widely in various fields. In practice, multi-objective optimization is generally solved by heuristics with tunable parameters that are highly application-specific. Tuning parameters based on real-world instances (a.k.a. algorithm configuration) are generally empirical without theoretical guarantees. In this work, we establish the theoretical foundation of data-driven multi-objective optimization through the lens of machine learning theory. We provide generalization guarantees on selecting parameters for multi-objective optimization algorithms based on sampled problem instances. Moreover, if the performance metric of the algorithm is the Pareto volume, we can PAC-learn the approximately optimal configuration in polynomial time. We apply our framework to various algorithms, including approximation algorithms, local search, and linear programming. Experiments on multiple problems verify our theoretical findings.

Learning Configurations for Data-Driven Multi-Objective Optimization
Zhiyang Chen
Hailong Yao 23 Xia Yin
Abstract
exact set of Pareto-optimal solutions is generally intractable for most multi-objective optimization problems, since the optimal Pareto set may contain an exponential number of solutions. In practice, heuristic algorithms are often applied to tackle multi-objective optimization. For example, approx- imation algorithms (Ravi & Goemans, 1996; Chen & Young, 2020) are designed to simultaneously approximate multiple objectives. Another widely used heuristic the weighted method, e.g., turning two-objective optimization prob- lem max (ci (zz), c2(2r) into single-objective one by opti- mizing convex combination of objectives,
Multi-objective optimization problems arise widely in various fields. In practice, multi- objective optimization is generally solved by heuristies with tunable parameters that are highly application-specific. Tuning parameters based on real-world instances (a.k.a. algorithm configura- tion) are generally empirical without theoretical guarantees. this work, we establish the theo- retical foundation of data-driven multi-objective optimization through the lens of machine Iearn- ing theory. We provide generalization guarantees on selecting parameters for multi-objective opti- mization algorithms based on sampled problem instances. Moreover, if the performance metric of the algorithm is the Pareto volume, we can PAC-learn the approximately optimal configura- tion in polynomial time. We apply our framework to various algorithms, including approximation algorithms, local search, and linear programming. Experiments on multiple problems verify our theo- retical findings.
max (1 - p) c1(x) + c2(()),
where 0 P 1.
However, both approximation algorithms and the weighted sum method contain tunable parameters. An approximation algorithm (Ravi & Goemans, 1996; Chen & Young, 2020) may contain parameters to balance the approximation ratio of different objectives. The weighted sum method also re- quires setting the weight The user may select parameter configuration to optimize the algorithmic performance, or even select multiple configurations to form a solution port- folio to provide more decision options. The selection of pa- rameters significantly impacts the algorithmic performance. There is usually no universal best configuration, and the user needs to tune the parameters based on ieplication-speciffe problem instances carefully. Many algorithm configuration methods (Schede et al., 2022) are proposed to automatically select parameters with good performances. Researchers even apply neural networks (Li al., 2021) predict good parameters for multi-objective optimization.
1. Introduction
Multi-objective optimization problems arise widely in var- ious fields, including operations research (Herzel et al., 2021), machine learning (Sener & Koltun, 2018), and de- sign automation (Chen & Young, 2020). A multi-objective optimization problem may involve multiple contradictory objectives that require simultaneous optimization. There- fore, a best-of-all- all-world solution that is optimal for every objective may not exist. Algorithm designers instead seek trade-off between multiple objectives.
Although multi-objective optimization algorithms are widely used in practice, the theoretical foundation of pa- rameter selection is limited. In this work, we study the prob- lem of algorithm configuration for multi-objective optimiza- tion through the lens of machine learning theory. Recently, there has been growing interest in the sample complex- ity of learning algorithm parameters for given applica- tion domain, a.k.a., data-driven algorithm design (Balcan, 2020). Concretely, there is probabilistic distribution over instances of multi-objective optimization problem. Given a training set sampled from this distribution, the learning algorithm selects one or multiple parameters that optimize the algorithmic performance from a parameterized family
A notion of optimality for multi-objective optimization is the so-called Pareto optimality. However, computing the
'Tsinghua University, China University of Science and Tech- nology Beijing, China Key Laboratory of Advanced Materials and Devices for Post-Moore Chips, Ministry of Education of China. Correspondence to: Hailong Yao <hailongyao @ ustb.edu..co edu.en">
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning Configurations for Data-Driven Multi-Objective Optimization
using empirical risk minimization. We aim to provide gen- eralization guarantees (a.k.a., sample complexity bounds) that bound the number of required samples to guarantee the performance difference to be small enough between training samples and the real distribution.
Table 1. An overview of sample complexity results for parame- terized multi-objective optimization, where & is the number of parameters and e the generalization error.
Problem
Worst-case
Smoothed
Shallow-light trees
Ō(k-e-3)
N/A
1.1. Main results
Bi-criterion MSTs
N/A
We summarize the contributions of this work as follows.
Local search
Ö(k- 2)
Simulated anncaling
O(k.T.E-3)
Ö(k Ō(k.E-
The first theoretical framework for data-driven multi- objective optimization. We establish a general framework for data-driven multi-objective optimization algorithms. Pre- vious work (Gupta & Roughgarden, 2017; Balcan et al., 2018a; 2021a; Sakaue & Oki, 2022) data-driven algo- rithm design shows that many parameterized algorithms, especially combinatorial algorithms, exhibit a piecewise structural property. The same structure also arises in multi- objective optimization algorithms. We present a general theorem that bounds the sample complexity of parameter- ized multi-objectivv optimization algorithms with respect to the complexity of the piecewise structure.
General linear programs
Ölk Olk-n.e-
Markov decision processes
Ó 0(K-151.E- 15)
o(k
light trees indeed improves the Pareto volume metric of multi-objective optimization. We also compute the number of pieces in the piecewise structure two algorithms, local search for VLSII circuit partitioning and resource-gathering Markov decision process. We find that, in practice, the intrinsic complexity of the performance metric function is indeed small, thus leading to small generalization bounds. This shows that the smoothed analysis setting is reasonable.
1.2. Organization
We also discuss how to efficiently learn the parameter from training samples (a.k.a,, empirical risk minimization): If the performance metric function is the Pareto
The rest of this paper is organized as follows: Section 2 introduces basic notations and the problem formulation of this work. Section 3 presents the general framework of sample complexity analysis for data-driven multi-objective optimization algorithms. In Sections 4, 5, and 6, we apply our framework to approximation algorithms, local search, and linear programs, respectively. Section 7 provides em- pirical verifications of our results. Finally, we conclude this paper and discuss directions for future work in Section 8.
we can (1 2) -approximatell PAC-learn the optimal pa- rameter in polynomial time by exploiting the submodular property of the Pareto volume. We further show that the approximation ratio is tight assuming P + NP.
Sample complexity bounds of learning configurations for various algorithms. We apply our general framework to various objeti-objective optimization algorithms, including approximation algorithms (shallow-light Steiner trees and bi-criterion minimum spanning trees), local search (vanilla local search and simulated annealing), and linear program- ming (general LPs and Markov decision processes).
A comparison with related work is discussed in Appendix A. Preliminaries are introduced in Appendix B. Technical proofs are given in Appendix C. Appendix D discusses some extensions of our framework. Appendix E supplements the detailed experimental settings.
For local search and linear programs, we find that a technical challenge is that the complexities of the piecewise structures may be exponentially large in the worst case, leading to poly- nomial sample complexity with respect to the problem size. We can overcome this barrier by conducting a beyond-wood -oost-- case analysis. The main idea is to use smoothed analysis. If the problem instance distribution contains small noise, we can reduce the number of pieces in performance metric functions to polynomial size, thus leading to logarithmic sample complexity bounds.
2. Notations and Problem Formulation
Notations. We use ((f()) [(m) poly log n to sup- press logarithmic factors. We also use [ra] to denote the set
n and II(-) to denote the indicator function. Preliminary notations for multi-objective optimization is omitted to Appendix B.
Problem formulation. Given a multi-objective optimiza- tion problem II, we use I to denote the set of possible problem instances that the algorithm takes input. We assume there is an unknown, domain-specific probabilistic distribution D over I.
Table 1 gives an overview of our sample complexity results. As an extension, we also discuss the application of machine learning models in predicting parameters in Appendix D.
Empirical verifications of theoretical bounds. We verify our theoretical findings with experimental results. We show that the empirical risk minimization algorithm on shallow-
We have an algorithm A to solve problem II parameterized by p E P. Suppose the problem II has d optimization objectives, we use A P x I - IR to denote the objective
2

---

Learning Configurations for Data-Driven Multi-Objective Optimization
vector of algorithm A's output on particular instance E I with parameter p E P.
We omit basic tools of statistical learning theory for proving sample complexity bounds to Appendix B.2.
The aim of algorithm configuration is to select k param- eters P = (PI...., Pk) E pk for A with good per- formance in expectation over the distribution D. Sup- pose the outputs of algorithm A are using parameters Pl..... Pl on an instance I. We use 1( ph I + 10, H]] to denote performance met- ric for A(pi, r).......... A(ps, I), where H is constant' that upper bounds the performance metric. For example, the performance metric can be the Pareto volume Vol (see Defi- nition 1. We aim to maximize the expected performance of A. i.e,, pa (Ez~p|u(P) ()))-
3. General Framework for Sample Complexity
3.1. Uniform convergence
In our main results, we consider the simple case that the problem has only objectives, and hence the algorithm gen- erally has only one real parameter. We discuss the extension to more than 2 objectives in Section D.
We study the setting where the performance of the algo- rithm has piecewise-constant structure with respect to the parameters. This structure widely appears in many op- timization algorithms, including greedy heuristics (Gupta & Roughgarden, 2017), branch-and-bound (Balcan et al., 2018a) 8a). dynamic programming (Balcan et al., 2021a), A* search (Sakaue & Oki, 2022), etc. Formally, the piecewise- constant structure is defined as follows.
We provide generalization guarantees (a.k.a., sample com- plexity bounds) for learning the parameters P. Given m training data [1, I..... : Im I that are independently sampled from D, a generalization guarantee bounds the difference between the average performance on training data and the expected performance on 'D. We use the idea of uniform convergence from statistical learning theory. Uniform con- vergence provides generalization guarantees for any choice of parameters P E pk, Therefore, it is independent of the learning algorithm.
algorithm). For any problem instance I, we can partition the parameter space P C R into t intervals, such that in each interval, the output of the algorithm A(., I) is a constant function.
Definition 3.1 (Piecewise-constee
Theorem 3.2. Given m ii.dd training samples II,..., Im from the instance distribution D, with probability at least 5, for any set of l parameters P (pr..... .k) E ph: we have
Definition 2.1 (Uniform convergence). The parameter- ized algorithm A has generalization error (m,,),, if for any distribution DD over X, with probability at least
(L (E EELDDL((,
1 8 over m i.i.d. samples Im ~ D, we have > I(P. - Er-D[[(P,, [)] S E, for any P pk The least number of samples m(e,5) that ensures such guarantee is called the sample complexity of I) distribution D.
O (v (A:log t log 4)
Equivalently, this generalization guarantee can be presented using the language of sample complexity: For any 0 and 0 < 8 < 1, m = Ω { (k log t log 8 8-1) samples are sufficient to ensure that with probability 1 - 8, the gen- eralization error is at most e. This theorem can be proved by classic pseudo-dimensie
We are also interested in providing guarantees for the complete learning procedure. Given m training data Im we use empirical risk minimization algorithm m im u(P, 1.). By uniform conver- gence bounds, the learned P is probably approximately correct (PAC) for the optimal parameter.
to solve maxpeps 1 E
techniques.
However, as we will show in the following sections, the number of pieces I can be exponential with respect the problem size. This gives polynomial bound the sample complexity (or generalization gap). To overcome this barrier, we apply smoothed analysis. In practice, worst-case bounds are generally loose. These bounds are seldom tight since random noises appear in real-world instances. Smoothed analysis assumes the instance distribution is not arbitrary, but distribution of smoothed instances.
Definition 2.2 (PAC-learning). A learning algorithm (a, B, PAACCleessssss the (approximate) optimal parameter, if given m i.i.d. samples from D, with probability at least 1 - 5, the learning algorithm finds k parameters P such that
(T-D(u(P,T)) a max EL~D(M(P", B, PPE
for some <aa < and 8 > 0.
Concretely, to sample instance I, we first sample smoothed instance / from some distribution D. A smoothed instance is an instance with a small random perturbation, i.e., a probabilistic distribution. Then, we obtain instance I by sampling the random perturbation from İ. We set a smoothness parameter k to evaluate the randomness of the
TTii assumption is standard in previous work of data-driven algorithm design (Gupta & Roughgarden, 2017). and is indeed reasonable. Although the performance metric may depend on the problem size, we can always normalize the metric and consider the relative performance, given fixed problem instance distribution.
3

---

Learning Configurations for Data-Driven Multi-Objective Optimization
perturbation. (As goes from I to +00, our analysis inter- polates between average-case and worst-case analysis.) In this setting, the number of pieces t is a random variable with respect to I. We can also obtain generalization guarantees by upper bounds on Ft, for any smoothed instance 7. Since t is a random variable, we can no longer use pseudo- dimension. Instead, we consider a smoothed version of Rademacher complexity and apply Massart's lemma.
On the negative side, we show that (1 1 >approximation is the best bound we can achieve assuming P * NP by making a reduction from maximum k-set-cover.
Theorem 3.7. The empirical risk minimization problem (1)
cannot be (1 _ + -pppprxxxmmt in poly (m, t) time for any E > 0, unless P NP.
ē
4. Applications to Approximation Algorithms
Theorem 3.3. Given m. ii.dd instances !1s...? I.m where I I and I; 'D from smoothed instance distribu- tion D for each i E [m]] with probability at least 1 - 5, for any set of l parameters P- = (pI.....Pk) E Pt.
We first apply our framework to approximation algorithms. We consider two approximation heuristics that are of practi- cal values in VLSII design and network optimization.
Em u(P.I.) - EILB E [u
we have
4.1. Shallow-light Steiner trees
(k: log B [ + logm m + log })
Given a weighted and undirected graph G = (V, E) with a set of terminals S S V and a root r E S, a Steiner free of G is a sub-tree that inter-connects S with root r. For any sub-graph G' S G, let (u, v) denote the shortest path distance between and v on G', and w('') denote the total edge weight of G".
m
3.2. Empirical risk minimization for Pareto volume
We also study the problem of empirical risk minimization to learn the optimal parameters. If the performance metric function is the Pareto volume Vol (see Appendix B.1), i.e., ((P, (olpp, I), ..... A(pk: I))), we can approxi- mately PAC-learn k parameters P E pp by exploiting the submodular property of the Pareto volume.
In the shallow-light Steiner tree (SLT) problem (Chen & Young, 2020), the objective is to construct a Steiner tree that simultaneously minimizes the total weight and the path length from the root r to each terminal in S. We say Steiner tree T' is a-shallow, if (r, 8) S a-da(r; 8) for each E S. and is 3-light, if (T) I B w(T)), where T is Steiner tree with the minimum total weight (a.k.a., the minimum Steiner tree). Our goal is to find (a, 3)-LLTs minimizing both a and B. An SLT is an interpolation between the minimum Steiner tree and the shortest path tree.
Definition 3.4. A set function 22 + R is submodular, if for any Ti C T3 S S. and any x E 55 T2, we have J(T) U (x)) - ((T) 2 (T2 U (x)) (T22)
Lemma 3.5. Let S = (u.,.... 3n} be a set of objective vectors. The function Vol 2 + [0, H), which maps a subset T C S to the Pareto volume of T, is monotone and submodular.
A direct application of SLTs is the construction of timing- driven routing trees for VL.SI design. In VL.SI design, we consider rectilinear routing on 2D plane, i.e., SLTs in metric space (R2 (l.) (In fact, our results can be extended to the general case (IR (lx)) for any d,p 2 1.)
Therefore, we can use the folklore (1 - ) -pproximation algorithm for submodular maximization to perform empir- ical risk minimization. Let I,,... Im denote the training samples from instance distribution D. Empirical risk mini- mization finds & parameters P= (P.....,PP)) to maximize the empirical Pareto volume, i.e.,
Chen & Young (2020) propose a practical heuristic, namely SALT, for constructing rectilinear SLTs. For a parameter p 2 0, it obtains (1 + p, [log p -1)-ST.. However, this bound is generally loose in practice. It is important to tune the value of to obtain tighter Pareto curve. We study the problem of tuning the parameter p of SALT.
1 m Vol(( IJ), ........ A(p,, PEP m71
max
Theorem 3.6. Given m. i.idd. samples from the instance distribution D, and suppose for any instance I, we have an oracle to compute each piece of A(. There exists learn- ing algorithm that finds k parameters P = (p .......,pkk) pk) that (1 2, -PA--leassssss the optimal parameter using m ( 2z (R: log + (og8-1)) samples in poly(m, t) time.
The SALT algorithm is described as follows: The algo- rithm begins by calling a heuristic (Chu & Wong, 2008) to obtain an approximate Steiner minimum tree To. It then performs a depth-firs search on To. During the search pro- cess, the distance dist(e) from the root to each point on To is maintained. Whenever a node v is accessed such that dist(u) > (1+ p) ||r vlli (which induces shallow- ness larger than 1 + p). we call v a breakpoint and update dist(v) = ||| - 2/[1- After the search, a shortest path tree is reconstructed for all breakpoints by calling heuristic by
1
Note that similar result also holds in the smoothed analysis setting by taking an expectation. In practice, the oracle can be implemented by, e.g., performing a binary search on the parameter space. See Appendix E. for details.
4

---

Learning Configurations for Data-Driven Multi-Ohjeetive Optimization
Córdova & Lee (1994). The algorithm finally post-optimizes the tree by performing some safe refinements.
Let A(p, be the output of SALT on an instance I with the parameter p, we have the following lemma.
looe W2 -
((2)
Lemma 4.1. For any SLT instance I, we can partition [0, +00) into at most n² intervals, such that in each interval, A(. I) constant.
W;
This lemma can be proved by counting the values of p that affect the breakpoints. This gives a sample complexity bound by Theorem 3.2.
Figure 1. An illustration of Goemans-Ravi algorithm.
Corollary 4.2. Let uu.,1) denote any performance metric function for SLT instance The sample complexity of u for SALT is
Let A(p, I) denote the output of Goemans-Ran on an in- stance I with W2 equal to p. we have the following lemma.
Lemma 4.3. For any instance I, A(., I) is a piecewise- constant function with most O(IVI2) pieces.
4.2. Bi-criterion minimum spanning trees
Corollary 4.4. Let u(. I) denote any performance met- ric function for bicriterion MST instance I. The sample complexity of u for Goemans-Ran is Ô (2)
Given an undirected graph G = (V. E)) with each edge e E E associated with two positive weights w (e) and wy (e), we consider the problem of bi-criterion minimum spanning trees, i.e., constructing spanning trees T such that the total weights (W) (T) = -Eeer W1 (c), Eeer w2(e)) are both minimized, Ravi & Goemans (1996) consider the budget- constraied version of this problem, and propose (1, appproopooiintoonnn algorithm. Concretely, given a bud- get constraint W2. the algorithm considers the following problem,
5. Applications to Local Search
5.1. Vanilla local search
In this section, we consider multi-objective optimization using local search algorithms. Local search, as well as its variant, simulated annealing, is widely used in various combinatorial optimization problems. If the problem has multiple objectives, the most natural and popular method is to optimize a weighted sum of the objectives. Such ex- amples include Sechen & Sangiovanni- Vincentelli (1986), Chen et al. (2008), Yu et al. (2022), etc.
min (I( Ie: E
Σ W2(e) Ie S W2,
s.t
eEE
Te E {0, 1}. Vee
We define the following general model for local search: Let S denote the states of the search algorithm. (Note that [S] can be very large, e.g., exponential in the problem size.) Each state S E S has a set of neighbors N(S) S S {S}. We use n to denote the maximum number of neighbors for all states S. Each state S is also associated with two costs (S)) (2)) Without loss of generality, we assume e (S), (S) [0, We use a weighted sum method to find state $ such that c($) (1 p) ci($) p c2(S) is minimized.
{el x.
= == E E} forms a spanning tree.
Let Wf be the optimal weight of this problem. The Ravi- Goemans algorithm finds a spanning tree with total weights (W1, W2) such that W S Wi and W2 < 2W, in almost- linear time. Note that RavinGoemans cannot find a solution T' that exactly satisfies the constraint W2(T') < W2. To balance Wi(T) and WT(T), we need to carefully tune the value of W2. In the following, consider the problem of learning parameters W2 for Ravi-Goemans.
We consider the standard local search algorithm by Johnson et al. (1988). Initially, the local search algorithm starts from an arbitrary but fixed state So E S. For each iteration E [T). the algorithm enumerates the neighbors of the current state S, and finds S' NS) with the minimal c(S'). If c(S') I c(S), let S - S'. Otherwise, the algorithm stops. Notice that a local search algorithm may converge after an exponential number of iterations. Thus, we define T, an upper bound of the iteration number. If the algorithm does not converge, we directly output the state S after iteration T, which a technique generally applied in practice.
The algorithm can be described as follows: Prune all edges with uz(e)= > W2. Let
L(z)= min sparning tree
Σ (wr(e)) + (wy))) z)æe - W2 = EEE
denote the Lagrangian function of the problem. The al- gorithm solves the Lagrangian relaxation max (z)). Let 2" denote the optimal solution. The algorithm finds the spanning tree T with the least EesT wz(e) such that Eeer (e) 2 W2. See Figure for an illustration.
5

---

Learning Configurations for Data-Driven Multi-Objective Optimization
Let D be a distribution of problem instances, A(p, I) denote the output of the local search algorithm using parameter p on instance 1, and u( I) denote the performance metric. We have the following lemma.
for any L E [T] is the temperature of the algorithm). 4. Let t + t + 1. If T, goto Step 2.
Note that we assume the algorithm does not access any state twice. We make this assumption to provide enough probabilistic independence to make the smoothed analysis possible. This assumption is not very strong since the prob- lem state is usually nigh-dimensional in practice, and the algorithm seldom repetitively accesses a state.
Lemma 5.1. For any instance I, we can partition [0, 1] into at most (n + 1) intervals, such that A(-: T) is constant in each interval. Moreover, there exists an instance such that the number of pieces is at least n (TT))
By Theorem 3.2, this gives a sample complexity bound of Ô ( (c2) ). We cannot further improve this bound using Theorem 3.2 since Lemma 5.1 also gives an asymptotically tight lower bound.
Since simulated annealing is a randomized algorithm, we also make the following assumption for simplicity of analy- sis. We assume the randomness of the algorithm is prede- termined as part of the input. Concretely, in Step 2 of the algorithm, for each pair of state S and iteration L, we assume the sample S' sample (S, t) E (N) is fixed as we vary the value of p. In Step 3, the algorithm accepts the new state by checking whether prob(!) S min (exp(A) (A/ /T,,, 1) where prob(t) is uniformly sampled over [0, 1] for t = .. before executing the algorithm. Now, an instance / is in the form of sample( ).roo(((.)..pro((.))). where inst denotes the local search problem instance, and sample, prob denote the randomness of the algorithm. Then, the distribution is joint distribution over problem instances and algorithmic randomness. This formulation is reasonable, since in prac- tice, for an instance I in the training set, we cannot obtain the expected performance of the algorithm on I, but rather observe the performance of the algorithm on I for some random seed. Thus, we can regard the random seed coming from the instance distribution.
However, we overcome this barrier using smoothed analysis. The philosophy of smoothed analysis is that the instances in practice always contain some randomness so that the worst case almost never exists.
We say a real random variable is k-bounded, if its probability density function is upper bounded by K. For example, a uniform distribution over an interval of length 1/x is K- bounded. We call an instance k-smoothed, if the costs ci (S) and e2 (S) are sampled individually and independently from k-bounded distributions on [0, 1] for each S E S. Therefore, a n-smoothed instance is an instance distribution such that the costs are perturbed with a small random noise.
Using smoothed analysis, we can reduce the number of pieces to polynomial size, leading complexity. The key proof technique is that, due to the random noise, the discontinuities produced in each iteration are (poly( (T, n)- x)-bbuudedd Thus, if the length of a piece is small, in the next iteration, it will not produce new pieces in expectation as much as in the worst case. By an induction on the iteration number, we show a polynomial upper bound on the expected number of pieces.
Ô (#) sample
Let D be a joint distribution over instances and algorithmic randomness, A(p, I) denote the output of the algorithm using parameter on I, and u(P. I)) denote the performance metric. Using a similar analysis to Lemma 5.1, the worst-
case sample complexity is also Ô ( (AT), and we can reduce the bound by smoothed analysis.
Theorem 5.2. Let DD be a distribution over k-smoothed local search instances. The sample complexity of u on D is
Theorem 5.3. The sample complexity of for k-smoothed simulated annealing is Ô k
6. Applications to Linear Programming
5.2. Simulated annealing
6.1. General LP
Simulated annealing (SA) is a variant of the local search method, which has gained great success in many practical problems. We extend our sample complexity results for multi-objective local search to simulated annealing.
Another application of our framework is multi-objective linear programs. Consider the following problem,
max T I,, S.t. Ar S b, 2
We consider the following simulated annealing algorithm:
where x R", A g Fr E R", and c (1- p) + p C2 R is the convex combination of two objectives C₁ and C2 Let A(p, 7) denote the output on instance / with parameter Let ui ((P. 1) denote a metric function on multi- objective LP instance I with E P = (PI....,Pi) We study the sample complexity of tuning P to optimize the metric E, [u(:,) T)).
1. Initialize the state S < Sy for some arbitrary but fixed So and / <- 1. Mark So as visited.
2. Randomly sample a state S' E N(S), and compute
A = =(S)- ((S).
3. If S' is not visited, mark S' as visited and with proba- bility min(exx(A/Ti)) 1), set S t S' (where T, >
6

---

Learning Configurations for Data-Driven Multi-Objective Optimization
Corollary 6.3. The sample complexity for smoothed mulli- objective linear programs is Ô k
6.2. Special LP: Markov decision processes
Projection
The smoothed shadow path bound for general linear pro- grams requires Gaussian noises on all coefficient entries. We can relax the smoothed analysis model if the linear program has a special structure.
Shadow path
Figure 2. An illustration of shadow path (blue) and its projection to the (cT2,e x) plane.
In the following, we study multi-objective Markov deci- sion processes (MDPs), which can be formulated as a spe- cial kind of linear programming. MDP the fundamental model for reinforcement learning and stochastic optimiza- tion. An MDP consists of the following components: A set of states S, a set of actions A, a transition probability map P[S(+1 Ar]. reward function R : S X A + [-1, 1]. and a discount factor E (0, 1). We aim to find a policy π : - A to maximize the expected accumulated reward using オ. For the case of multi-objective MDPs, a natural approach is to optimize the weighted sum of multiple reward functions, e.g., Goldie & Mirhoseini (2020) and Yang et al. (2023).
The sample complexity of u(:; I) for multi-objective LPs is Ö km This is obvious since the number of pieces for A(. 1) upper bounded by the number of vertices of the polyhedron Q= {zl Az b}. which is ((r").
We can also use smoothed analysis to improve the worst- case sample complexity bound. Let Q[c] denote the face of Q maximizing cTz: x. We aim to bound the smoothed number of faces Q[c] as p varies from zero to one. This is the same as the shadow path of Q, which is proposed in previous work studying the smoothed complexity of the Simplex method for LPs. We can hence apply off-the-shelf results of shadow paths to obtain sample complexity bounds.
It is well-known that MDPs can be solved by linear pro- gramming (Bertsekas & Tsitsiklis, 1996):
Definition 6.1 (Shadow path). Let Q S R be a polyhe- dron. Given two vectors c1, C2 E IR,, there exists a unique
min Σ d(s) V(s), (s)))
sequence of faces Q(c1, = (Va, C1, 01...., ., Gt, 21) of Q, and sequence 0 = Po P1 <... < pt < M+1
SES
s.t. (s)) 2 R(s, +7 Σ Pllls,,)V(s))
such that (1) for S i S I, 6, @ p:) + p:02]: ; (2) for 0 O i < 1 and p (pi, Pi+), U. Q[(1 p)c1 pc2]: (3) for 1 < i < 1 - 1, 0 = e, 0 e441- ((11, 02) is called the shadow path of Q with respect to e1, 02 (see Figure 2).
S'E
ASE S
Here, V is the value of Bellman's equation, and d can be in- terpreted as a distribution over S such that E.es d(s) = 1. Then, the objective is equal to the total expected accumu- lated reward if the initial state is sampled from this dis- tribution. Since the optimal policy is independent of the initial state, we can set d as an arbitrary positive vector. For simplicity of analysis, we set d(s) 1/|S], i.e., uniform distribution over S.
Under random perturbations, we have dim e; = for 1 1 i S almost surely. Therefore, without loss of generality, the shadow path is indeed "path" where {1;} are vertices and {e:} are edges.
To illustrate the optimization objectives, we can project the shadow path to the plane by mapping each point x E Q(c1.02) 02) to (ef af).. This results in concave curve and we use seope(e;) to denote the slope of e after projection.
To define a multi-objective MDP, we assume the reward function R(s, a) = (1 (1-10 p) - Rí (8, a) + p. R2 a) for 0 < p S 1. We aim learn a set of ls values of p maximize the performance metric u. In the worst case, upper bound for the sample complexity of u(,, I) is ((k(S)=-)) since there are at most ||||S| choices of the policy. Thus, we can partition [o, 1] into at most ||||S| intervals such that the optimal policy is constant for p in each interval.
Spielman & Teng (2004) study the shadow path size of the smoothed LP model, maxc (A + A)z < b4 + b, where the rows of (A, b) are normalized with l2 norms at most 1, and each entry of Á, 6 is independent Gaussian noise? with zero mean and 1 1/x² variance.
Theorem 6.2 (Spielman & Teng (2004)). The expected size of any shadow path for Q = {o| (A Å)x < b+bb0 b} is upper bounded by poly (n, r, k).
Now, we consider the smoothed analysis setting. We assume that the rewards Ri a) and (2 a) for each pair (s, a) are sampled independently from x-bounded distributions over [-1, 1]. Such instances are called k-smoothed.
"The Gaussian distribution (0, -2) is x -bondeed. Sadly, current results of smoothed analysis for linear programs only hold for particular distributions, such as Gaussian or Laplacian noises.
Theorem 6.4. The sample complexity for K- k-smoothed multi- objective MDPs Ô ((5 (.)).
7

---

Learning Configurations for Data-Driven Multi-Ohjective Optimization
To apply the shadow path method, we instead consider the dual problem of the MDP:
Local
MDP
Number of giocess
Number pieces
Number of gieces
10.015
Generaliznl waaiinn enter
Ger. Error
Gencraitzstoo
15
0.010
ΣΣ R(s,a) ( ((),a); REA
10
Number of pieces
00.003
max
14
-10
80
1.00
0.0
10
20
30
0.0000
Probtem
Prob size
Σ (() = d(B) +7 ΣΣ dEE
P(slo',alu(s'..
s.t.
Figure 3. The number of discontinuities in the piecewise structure (red) and the generalization error (blue) for local search (left) and MDPs (right).
aEd
p(s,a) 2 0, V& S,
Lemma 6.5. The expected size of the shadow path of the K-smoothed dual MDP problem is upper bounded by 0 |)k)
Table 2. The Pareto volume of learned parameters for SALT. Our empirical risk minimization algorithm achieves larger Pareto vol- umes, compared with the vanilla geometric series setting in SALT.
ERM (ours)
Vanilla SALT
FRM (ours)
Vanilla SALT
Theorem 6.4 is direct corollary of Lemma 6.5. The main proof technique is observe that for each U; the shadow path, there exists some (s, such that p(s a) = 0 for and (u(s, a) > O for 01+1- We show that the contribution of such (s, a) to slope(e:+1) is ((|S)/((111000000000000110111011 7)) bouundd,, thus leading to a polynomial bound in expectation.
0.1157
0.0159
7
0.1618
0.1233
0,1338
0.0206
0,1625
0.1399
0,1487
0.0374
9
0.1632
0.1511
0,1529
0.0557
0.1636
0.1573
0.1559
0,0782
11
0.16338
0.1610
0.1607
0.1030
0.1639
0.1626
Remark 6.6. Although we prove polynomial bound for the shadow path size of MDPs in the smoothed setting, we are unable to prove super-pol polynomial lower bound in the worst case. Note that the classic policy iteration method is known to solve MDPs in polynomial time (Ye, 201 I). It is possible that the shadow path size is also polynomial in the worst case. We left such analysis as future work.
The results are illustrated in Figure 3. The problem size denotes the number of nodes (for circuit partitioning) and the number of rows and columns of the grid environment (for MDP). Although in the worst case, the number of pieces may be exponential in the problem size, the empirical re- sults show that the number of pieces grows mildly. This indicates that the worst-case behavior does not appear in practice and our smoothed analysis matches experiments. As a consequence, the generalization error is also small.
7. Experiments
In this section, we perform empirical verifications of our the- oretical results. Due to the page limit, we omit the detailed experimental settings to Appendix E.
7.2. Optimizing Pareto volume
Then, we experimentally show that the empirical risk mini- mization algorithm in Section 3.2 can optimize the Pareto volume of learned parameters. We conduct experiments on shallow-light Steiner tree benchmarks from real-world VLSI designs.
7.1. Generalization bounds
First, we verify the effectiveness of smoothed analysis in our sample complexity analysis. We evaluate the generaliza- tion bound on local search and Markov decision processes. For local search, we consider the VLSI cireuit partitioning problem (Hu al., 2022). For MDP, we consider resource- gathering problem in previous work on multi-objective rein- forcement learning (Barrett & Narayanan, 2008).
The original implementation of SALT uses a simple heuris- tic that selects the values of p from geometric series. We compare our method with this baseline. Let & denote the number of learned parameters. The result is listed in Ta- ble 2. The empirical risk minimization algorithm obtains larger Pareto volume for the shallowness- especially when l is small. This indicates the strength of an empirical risk minimization algorithm in tuning a multi- objective optimization algorithm.
curve,
We tune the parameter p of the weighted sum method, and compute the maximum number of pieces in the piecewise structure of the solution found by the algorithm. We report the maximum number of pieces over problem instances of particular size. We also report the generalization error. Since the performance metric may depend on the specific application, we simply compute the maximum gap of two objectives averaged on training and evaluation instances. Note that the generalization error depends on the range of the objective. We normalize the objective by the maximum value among data sets to make the error between (0, 1).
8. Conclusion
This work studies the sample complexity of data-driven algorithm configuration for multi-objective optimization al- gorithms. We present sample complexity bounds for several applications, in which the algorithmic behavior exhibits a piecewise-constant structure.
8

---

Learning Configurations for Data-Driven Multi-Objective Optimization
Our work suggests several directions for future research. First, discussed in Section D.2, can extend the smoothed analysis to the case of more than 2 objectives? We conjecture that smoothed sample complexity of O(kd= is possible for d objectives. Second, can we extend the sam- ple complexity bound for MDPs to environments beyond tabular cases, e.g., MDPs with continuous features? Finally, can we prove sample complexity bounds for branch-and- bound solvers of integer linear programs? The analysis will be much harder since the algorithm solves a relaxed linear program on each search tree node.
learn high-performing algorithms? Generalization guar- antees for data-driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 919-932, 2021a.
Balcan, M.-F. Sandholm, T., and Vitercik, E. Generaliza- tion in portfolio-based algorithm selection. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 12225-1221 -12322, 2021b.
Balcan, M.-F., Prasad, S., Sandholm, T., and Vitereik, Structural analysis of branch-and-cut and the learnability of Gomory mixed integer cuts. In Advances in Neural Information Processing Systems, volume 35, pp. 33890- 33903, 2022.
Acknowledgements
This work was supported by the Key Program of National Natural Science Foundation of China (No. 62034005).
Barrett, L. and Narayanan, S. Learning all optimal policies with multiple criteria. In Proceedings of the 25th Inter- national Conference on Machine Learning, pp. 41-47, 2008
Impact Statement
This paper presents theoretical studies on data-driven al- gorithm configuration of multiplc-objective optimization. There are no potential societal consequences of our work that must be specifically highlighted here.
Bartlett, P., Indyk, P., and Wagner, T. Generalization bounds for data-driven numerical linear algebra. In Proceedings of Thirty Fifth Conference Learning Theory, volume 178, pp. 2013-2040, 2022.
References
Balcan, M.-F. Data-driven algorithm design. arXiv preprint arXiv 2017,07 2020.
Bertsekas, D. P. and Tsitsiklis, Neuro-Dynamic Program- ming. Athena Scientific, 1996.
Balcan, M. F. and Sharma, D. Learning accurate and in- terpretable decision trees. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024.
Blot, A., Hoos, H. H., Jourdan, L.,, Marisci,,aamioon., M.-É., and Trautmann, H. MO-ParamlLSS: A multi-objective au- tomatic algorithm configuration framework. In Learning and Intelligent Optimization, pp. 32 32-47, 2016.
Balcan, M.-F., Dick, T.. Sandholm, T., and Vitercik, E.
Learning to branch. In Proceedings of the 35th Interna- tional Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 344-353.
Blot, A., Marmion, M.-E., Jourdan, L., and Hoos, H. H. Automatic configuration of multi-objective local search algorithms for permutation problems. Evolutionary Com- putation, 27(1)1147-171, 2019.
PMLR, 2018a.
Balcan, M.-F., Dick, T., and Vitercik, E. Dispersion for data-driven algorithm design, online learning, and pri- vate optimization. In IEEE 59th Annual Symposium on Foundations of Computer Science, pp. 603-614, 201 8b.
Chen, G. and Young, E, F. Y. SALT: Provably good routing topology by a novel Steiner shallow- light tree algorithm. IEEE Transactions on Computer-Aided Design of Inte- grated Circuits and Systems, 39(6): 2020.
Balcan, M.-F., Dick, T., and Pegden, W. Semi-bandi opti-
mization in the dispersed setting. In Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence, volume 124, pp. 909-918, 2020a.
Chen, T.-C., Yuh, P.-H., Chang, Y.-.,, Huang, F.J.,, and Liu, T.-Y. MP-Trees: A packing- macking-based macro placement algorithm for modern mixed-size designs. IEEE Transac- tions on Computer Design of Integrated Circuits and Systems, 27(9): 162111 2008
Balcan, M.-F,, Sandholm, T., and Vitercik, E. Refined bounds for algorithm configuration: The knife-edge of dual class approximability. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. 580-590, 2020b.
Cheng, H., Khalife, S., Fiedorowicz, B., and Basu, A. Sam- ple complexity of algorithm selection using neural net- works and its applications to branch-and-cut. In The eight Annual Conference on Neural Information Processing Systems, 2024.
Balcan, M.-F,, DeBlasio, D., Dick, T., Kingsford, C., Sand- holm, T., and Vitercik, How much data is sufficient to

---

Learning Configurations for Data-Driven Multi-Objective Optimization
Chu, C. and Wong, Y.-.. FLUTE: Fast lookup table based rectilinear Steiner minimal tree algorithm for VL.II de- sign. IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, 27(1):70-88) 83, 2008.
Rakhlin, A., Sridharan, K., and Tewari, A. Online lear- ing: Stochastic, constrained, and smoothed adversaries. In Advances in Neural Information Processing Systems, volume 24, 2011.
Córdova, and Lee, Y.-H. A heuristic algorithm for the rectilinear Steiner arborescence problem. 1994.
Ravi, R. and Goemans, M. X. The constrained minimum spanning tree problem (Extended abstract). In Proceed- ings of the 5th Scandinavian Workshop on Algorithm Theory, pp. 66-75, 1996.
Feige, U. A threshold of In n for approximating set cover. Journal of the ACM, 45(4):634 652, 1998.
Röglin, H. and Teng, S.-H. Smoothed analysis of multiob- jective optimization. In 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 681-690, 2009.
Goldie, A. and Mirhoseini, A. Placement optimization with deep reinforcement learning. In Proceedings of the 2020 International Symposium Physical Design, pp. 3-7, 2020.
Sakaue, S. and Oki, T. Sample complexity of learning heuristic functions for greedy-best- and A search. Proceedings of the 36th International Conference on Neural Information Processing Systems, 2022.
Gupta, R. and Roughgarden, application-speeific algorithm selection. SIAM Journal Computing, 46(3):992-100 1017, 2017.
PAC approach to
Schede, E., Brandt, J., Tornede, A., Wever, M., Bengs, V., Hullermeier, E., and Tierney, K. A survey of methods for automated algorithm configuration. Journal of Artificial Intelligence Research,
Herzel, A., Ruzika, S., and Thielen, C. Approximation methods for multiobjective optimization problems: A survey. INFORMS Journal on Computing, 33(4):1284 1284- 1299, 2021.
2022.
Sechen, C. and Sangiovanni- Vincentelli, A. TimberWolf3. 2: A new standard cell placement and global routing pack- age. In Proceedings of the 23rd Annual Design Automa- tion Conference, pp. 432-439, 1986.
Hu, K.-S., Lin, I.JJ,, Huang, Y.-H., Chi, H.-Y., Wu, Y.H.,, and Shen, C.-F. C. ICCAD 2022 CAD contest problem B: 3D placement with D2D vertical connections. In Pro- ceedings of the IEEE/ACM International Conference on Computer-Aided Design, 2022.
Sener, O. and Koltun, V. Multi-task learning as multi- objective optimization. In Advances in Neural Informa- tion Processing Systems, pp. 525-536, 2018.
Johnson, D. S., Papadimitriou, C. H., and Yannakakis, M. How easy is local search? Journal of Computer and System Sciences, 37(1):79-100, 1988.
Spielman, D. A. and Teng, S.-H. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3):885-463, 2004.
Khodak, M., Chow, E., Balcan, M. F., and Talwalkar, A. Learning to relax: Setting solver parameters across sequence of linear system instances. In The Twelfth Inter- national Conference on Learning Representations, 2024.
Wang, J., Zheng, Y., Zhang, Z., Peng, H., and Wang, H. A novel multi-state reinforcement learning-basse based multi- objective evolutionary algorithm. Information Sciences, 688: 121397. 2025.
Kim, M.-C. and Hu, J. Incremental timing-driven place- ment and benchmark suite. Available at htts::/www.iccad- mmntest.ogg22115prrobi httt:///ssppeeeeeeeeee.t.t..ttta c/default 2015.
Wolsey, L. A. and Nemhauser, G. L. Integer and Combina- torial Optimization. Wiley-Interscience, 1999.
Li, W., Qu, Y., Chen, G., Ma. Y., and Yu, B. TreeNet: Deep point cloud embedding for routing tree construction. In Asia and South Pacific Design Automation Conference, pp. 164-169, 2021.
Xue, K., Xu, J., Yuan, L., Li. M., Qian, C., Zhang, Z.. and Yu, Y. Multi-agent dynamic algorithm configuration In Proceedings of the 36th International Conference on Neural Information Processing Systems, 2022.
Lin, Y., Dhar, S., Li, W., Ren, H., Khailany, B., and Pan, D. Z. DREAMPlace: Deep learning toolkit-enabled GPU acceleration for modern VLSSI placement. In Proceedings of the 56th Annual Design Automation Conference, pp. 1-6, 2019.
Yang, L.,, Sun, G., and Ding, H. Towards timing- routing: An efficient learning based geometric approach. In International Conference Computer Aided Design, pp. 1-9, 2023.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- tions of Machine Learning. The MIT Press, 2nd edition, 2018.
Ye, Y. The simplex and -olicy-iteration methods are strongly polynomial for the Markov decision problem with fixed
10

---

Learning Configurations for Data-Driven Multi-Objective Optimization
discount rate. Mathematics of Operations Research, 36: 593-603, 2011.
Yu, H.-C., Lin, Y.-H., Chen, Z., Li, B., Huang, X., Schlicht- mann, U., Ho, T.-Y., and Yao, H. Contamination-awall synthesis for programmable microfluidic devices. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 41(11):5016-500 2022.
Yu, X., Xu, P., Wang. F., and Wang. X. Reinforcement learning-based differential evolution algorithm for con- strained multi-objective optimization problems. Engineer- ing Applications of Artificial Intelligence, 131:107817, 2024.
Zhang, T., Georgiopoulos, M., and Anagnostopoulos, G. C. SPRINT multi-objective model racing. In Proceedings of the 2015 Annual Conference Genetic and Evolutionary Computation, pp. 1383-1390, 2015.
Zhang, X., Lin, X., Xue, B., Chen, Y., and Zhang, Q. Hy- pervolume maximization: A geometric view of Pareto set learning. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
Zhao, Y., Wang, L., Yang, K., Zhang, T., Guo, T., and Tian, Y. Multi-objective optimization by learning space partition. In International Conference Learning Rep- resentations, 2022.

---

Learning Configurations for Data-Driven Multi-Objective Optimization
A. Related Work
In the following, we briefly survey related work to ours, and discuss comparisons with them.
Data-driven algorithm design. Gupta & Roughgarden (2017) initially establish the framework of data-driven algorithm design, where both statistical learning and online learning settings are considered. For statistical learning, this framework has been applied to learning branch policies for branch-and-
(Balcan et al., 2018a). learning cuts for branch-and- cut (Balcan et al., 2022; Cheng et al., 2024), parameter tuning for string alignment and mechanism design (Balcan et al., 2021a), learning embeddings for A search (Sakaue & Oki, 2022), data-driven numerical linear algebra (Bartlett et al., 2022), tuning decision tree models (Balcan & Sharma, 2024), to name a few. For online learning, this framework has been applied to tuning greedy heuristics (Gupta& & Roughgarden, 2017; Balcan et al., 2018b), tuning clustering algorithms (Balcan et al., 2020a), tuning linear system solvers (Khodak et al., 2024), etc. Our work focuses on statistical learning of multi-ohjective optimization algorithms.
Our main technical tool is smoothed analysis, which reduces the intrinsic complexity of the parameterized multi-objective optimization algorithm family. Note that smoothed analysis is also applied in online learning of data-driven algorithm design (Gupta& & Roughgarden, 2017; Balcan et al., 2018b) (i.e., the dispersion property in Balcan et al. (2018b)). In fact, their regret bounds can be turned into statistical ones by applying ppline-to-batel results. However, we emphasize that our method is different from dispersion. Dispersion is proposed to overcome the impossibility of no-regret online learning for worst-case instances. For a family of parameterized algorithms with discontinuities in the piecewise structure, the dispersion property says that these K discontinuities do not concentrate tightly in the smoothed analysis setting, and thus no-regret online learning is possible by making a discretization-baas method. However, the dispersion property does not present tools for bounding the number of discontinuities K. Our work shows that the number of discontinuities in the piecewise structure can be greatly reduced (i.e., from exponential to polynomial) using smoothed analysis. Therefore, our technique is orthogonal to dispersion.
Balcan et al. (2020b) also propose a method to reduce the intrinsic complexity of the piecewise structures. They use a surrogate function with a simpler structure to approximate the original performance metric function. This approach yields a data-dependent numerical bound for the generalization error. In contrast, our work considers asymptotic bounds without accessing the concrete training data.
Finally, we remark that smoothed analysis is also applied to interpolate between distributional and adversarial settings of classic learning problems, such as online prediction (e.g., Rakhlin et al. (2011)). Our technique is different from classic learning problems since our analysis focuses on the combinatorial structure of multi-objective optimization algorithm configuration.
Algorithm configuration for multi-objective optimization. Algorithm configuration is concerned with the problem of searching parameter configurations of parameterized algorithm. Several work (Zhang al., 2015; Blot et al., 2016; 2019; Xue et al., 2022; Yu et al., 2024; Wang et al., 2025) have been devoted to algorithm configuration with multiple objectives. We refer readers to a comprehensive survey of algorithm configuration (Schede et al., 2022). These work are generally empirical, and the theoretical foundation of multi-objective algorithm configuration is lacking.
Machine learning for multi-ohjective optimization. Previous work also explores the integration of machine learning techniques into multi-objective optimization. Zhao et al. (2022) combine learning models with Monte-Carlo tree search to improve multi-objective black-box optimization algorithms. Zhang et al. (2023) consider modeling the Pareto set using neural networks. These work are different from ours since we focus tuning the parameter of multi-objective optimization algorithms.
Smoothed analysis of algorithms. Smoothed analysis is proposed by Spielman & Teng (2004) to explain the efficiency of the Simplex method for linear programs in practice. They show that, with a small Gaussian noise on the linear programming instance, the expected time complexity of Simplex is polynomial, breaking the exponential lower bound in worst-case analysis. Smoothed analysis has then been applied go beyond worst-case analysis of many algorithms.
A related work to ours is due to Röglin & Teng (2009), which shows that a multi-objective binary integer program has only a polynomial number of Pareto-optimal solutions under smoothed analysis. However, their work is different from ours: (1) They consider the optimal Pareto solution set of the problem, while we focus on the behavior of algorithms (which may not produce optimal solutions); (2) Their analysis focuses on binary integer programs, while our framework can be applied to other problems.
12

---

Learning Configurations for Data-Driven Multi-Ohjective Optimization
B. Preliminaries
In this section, we introduce preliminaries on multi-objective optimization and statistical learning theory, which serve as fundamental tools for our analysis. We refer readers to, e.g., Mohri al. (2018) for more details learning theory.
B.1. Preliminaries on multi-objective optimization
For a maximization problem' with objectives, we use an objective vector o IR4. to denote the d objectives solution. An objective vector is said to be dominated by another o' os S of for any S d. We use = o' denote domination.
Definition B.1 (Pareto volume). For set of solutions S = ...... ,..), the Pareto volume Vol(S) is the (hyler-)volume of the set that contains points dominated by at least one point in S, i.e.,
Vol(S) / 1(3d' E S, o
JOER
B.2. Preliminaries on learning theory
Definition B.2 (VC- and pscudo-dimension), Let H. denote set of functions from some domain to A finite set S= ( Jm C X is shartered by H. if there exist witnesses Tm such that, for each of the 2 subsets T C S, there exists h E H such that h(x;,) > Ta if and only if x; E T. The pseudo-dimension Pdim(H)) is the cardinality of the largest subset of X shattered by H. Specially, if h E H. are binary functions (h X + {-1,1] 1)), the pseudo-dimension is also called the VC-dimension VC).
By definition, we have the following fact. Fact B.3. Let H be function class from some domain X. to R. and H' = [h' | (z,r) sgn(h(x) r), E H. X, r E RJ. Then, we have VCdim(H) = Pdim"HH).
Lemma B.4 (Sauer). Let H be a function class from some domain X. (1,-1) with VCdim(H) d. For any {x) "0I...,,T'' X. have
[(h(z)).....
h(zm. h(zm))
HHI
m Σ
0(m)).
0
Definition B.5 (Rademacher complexity). Let H. denote set of functions from some domain X to [0, H]. The empirical Rademacher complexity H for a finite set S = (.1,..., Tmm
C
m
Rs(H) (-1.-11)
Σ
o.Maa))
sup NEW m
where each o; is independently and uniformly sampled from {-1,1}. The Rademacher complexity of H is RD(H)
Es-DD (P)) where each E S is independently sampled from some distribution DD
Lemma B.6 (Massart), For a function class H from to [0, H), and S (.1,..., 3m X, we have
2 log |A|
R+) < H
where A = Theorem B.7 (Uniform convergence). Given m ii.dd samples S = (II...., Im from a distribution D, for any E (0, 1),
h E H. is the set of all possible values of h E H on S.
with probability at least 5, for any H. we have
8 1
Σ 1=1
Mxx)) - E. B.DDDEDhhhh [b])]]]]])])))))(()))) S 00()) complexity(H)) + VV log 1og
where complexity(H) the Rademacher complexity (H),), the empirical Rademacher complexity Rs (H), or a pseudo-
dimension-bused term H Pdim(N)
Forr minimization problems, transform it into maximization problem by selecting baseline with objectives (oi,...,0i) oi)) and consider the Pareto volume of (oj .1..... 2g o.) for objectives (O1...., Od).
13

---

Learning Configurations for Data-Driven Multi-Ohjeetive Optimization
C. Omitted Proofs
C.1. Proofs in Section 3.1
Proof of Theorem 3.2. Let u = [u(P,)]P E ptj. By Theorem B.7, it suffices to bound the pscudo-dimension Pdim(Uf) = Okllog)).
Suppose Pdim((4) m. Let S {h,,... [m] be m instances that be shattered by U and ri.-.. vm E R be the witnesses. For every S' S S, there exists Ps E pk such that 4; E S* if and only if u(P. > Let M (Ps S S} and [M = 2
By Definition 3.1, the parameter space P can be partitioned into t. intervals such that in each interval, A(: 7) is constant. Combining the intervals for m instances, we can partition P into m t intervals such that the function is constant on all m instances. Since P pk, the vector (w( (P, Ii),..., u P, Im)) can take at most (md) values. Therefore, we have 2 M < (mt)*. Solving for m yields m logtt..)
Proof of Theorem 3.3. For simplicity, we use E to denote E Given instances [im) = {.1..... I J. let RImm) (U) = E. pup 1 Ei I,) be the empirical Rademacher complexity of fu(P..)) P P*} Let
R(U)- = 1 (mmj~mm [R (2) be the Rademacher complexity. Our goal is to bound the Rademacher complexity of Ut
Notice that
R(U)
E (im)
[R] (2) S sup [(m]] [(m) ml
[1mg (24)
Don
[m]] [m]
For any m smoothed instances II,..., we define the smoothed empirical Rademacher complexity as Rim (U)
Bi [mm) [Ri (2)). Combining the t intervals for each instances, and considering the choice of k parameters, we have m 1i takes at most (mt)* values. By Massart's lemma, we have
log((
R [m] (4) 5 0(1)
E
[(m] [pm]
k(logt + log m)
k(log E B [4] log m)
= 0(
0(1)
Tpp
where the last inequality is due to Jensen's inequality. This yields the desired result by Theorem B.7.
C.2. Proofs in Section 3.2
Proof of Lemma 3.5. It is obvious that Vol is monotone. We only prove the submodularity, For any Ti C T3 S S, and Mg E S T2, we have
(Vol(T) U {uot) - Vol(Ti)) -Vol- (wo}) Vol(T2))
(I((Ve' E Ti,u 1 u') A (u = un)) - 1((('' E T2, A u') A (u = un do))
T[(Vu' TT,u (Eu E TT Tú - v/) (u S uo))
2 0,
which satisfies Definition 3.4.
Proof of Theorem 3.6. Since A(p, I) is piecewise-constan it suffices to consider selecting, p from at most t m pieces. Note that the average of Vol is also monotone and submodular. We can use the greedy algorithm to approximately maximize the empirical Pareto volume.
Fact C.1 (Wolsey & Nemhauser (1999)). The greedy algorithm that selects l elements to maximize a monotone and submodular function yields (1 -pppproximattion the optimal solution.
14

---

Learning Configurations for Data-Driven Multi-Objective Optimization
Let pa denote the optimal set of parameters that maximize Eι~D[u(P, D),, P* denote the optimal solution problem (1),
and P denote the solution found by the greedy algorithm in Fact C.I. We have, with probability at least 1 - 6,
m
(v -
ET>Dlu(P,
((P, -
logt dog
1
Σ (Pp .4)-
m
-0 (v (Vm (k log 8 8-1)
1
m
1 )) m Σ u(P', .Ii) -i)-0
m
(V (klott + log log8-1)
0
1 - ) E EI~DlU(P" []] 2 e ))
. -0 (V (k:logt log 8-1)
which is the desired result by plugging in m. The first and the last inequality comes from Theorem 3.2, the second inequality comes from Fact C.I, and the third inequality is due the optimality of pa
Proof of Theorem 3.7. Proof by reduction from maximum k-set-cover. The max k-cover problem is defined as follows: Given universe U = {ar,...., (.,), J. subsets Si,..., St U. and an integer k. We aim to select k sets from Si,..., St. such that the union of the i sets has maximum cardinality.
Theorem C.2 (Theorem 5.3 of Feige (1998)). For any & > max k-cover cannot be approximated in polynomial time within a ratio of (1 1 + :), unless P NP.
Given a max k-cover instance, we construct an instance of problem (I), Each element in the universe corresponds to a training sample I,. The algorithm A(.,I, contains pieces, and we let the partition of pieces be the same for each sample Fy- piece j of 7,, if ag E Sy. we let A(,, [4) = (1, 1) (i.e., with Pareto volume 1). Otherwise, we let A(, 7,) = (0, 0) (i.e., with Pareto volume 0). Therefore, selecting i subsets from Si...., St is equivalent to selecting & pieces to maximize the Pareto volume. Since the reduction preserves the approximation ratio, our result follows from Theorem C.2.
C.3. Proofs in Section
Proof of Lemma 4.1. As the value of p varies from 0 +00, the output of SALT changes as some point becomes or no dist(e)
longer a breakpoint. Such discontinuities happen as p = |r-ujl and the distance from the root to on the tree dist(v) is in the form of ||r o' || + dr v) for some v' E S, where (r'"', fo',, v) is the distance between o' and v on the initial Steiner minimum tree. Therefore, dist(v) can take at most n 1 values. Combining the breakpoints for each v E S, the number of discontinuities is at most n(n - 1) + 1 n².
Fix the point v. The value of ||r ull2 is a constant,
Proof of Lemma 4.3. is easy to notice that the behavior of the algorithm is fixed if x is fixed (see Figure 1). Therefore, it suffices to consider the number of pieces of L(z) (the red segments in Figure 1).
The following property is crucial to our analysis.
Lemma C.3 (Lemma 3.2 of Ravi & Goemans (1996)). Suppose T and T' are two spanning trees corresponding to two adjacent segments of L(z). Then, T and T' differ by only a single edge swap (i.e., there exist e E and e' E T such that T = (T - e) Ue').
Let Ti..... ,,. Tn edge swap between T; and T:+1 in Lemma C.3 for i E [n - 1]. We claim that each pair of edges (e, e') F.2 only appears at most once in {(e,, </ E [n 1]}.
denote the spanning tree that minimizes L(z) as varies from 0 to +o. We use (ea, e E E to denote the
Proof by contradiction. Suppose there exist * j such that (e,,ef) ef) = e/)). We consider the intersection point of Wi + W2 2 for T;, T:+1 and TJ,T The line W1(T) + W2(T.) intersects W1 (T<+1) + W2(T++1) 2 at W, (W.):) (a())) ( (2(.44)
[wi(e:)-w1(e (e() Similarly, Wi (T;) + W2(T)) z also intersects WT (T,+1) W2(T)+a) 2
15

---

Learning Configurations for Data-Driven Multi-Ohjeetive Optimization
G (5))
M
22
(2)
C (S)
C2(5)
P
Figure 4. The discontinuity point of local search for two states S and S"
ww + (
Both points have the same 2 coordinate. However, it is impossible that Tú. T4+1, T3 T3,+11 all lie on the
+ux (é,ب]
minimum segments of I(z). This is a contradiction.
C.4. Proof of Lemma 5.1
Proof. (Upper bound.) Proof by induction. We claim that after iteration i, the algorithmic behavior is piecewise-constant with at most (n + 1)' pieces.
Initially, 0, and there only one interval [o. 1]. Suppose our claim holds for iteration t, and consider the next iteration ++1 1. Fix an interval (a, bj from the total of (n 1)' sub-intervals after iteration t. If p E [a, b), after l iterations, the algorithm finds fixed state S, and explores the neighborhood (SS). Consider the weighted sum of costs for states in (S)). The cost c(S") = (1 p)- ci (S") p- c2(S") for each S' E {S} U (S)) is a linear function with respect to p. In iteration + 1, the algorithm finds the state S' with the least cost c(S') (If c(S) is the minimum, the algorithm terminates, and no more sub-intervals are created.) Note that the minimum of n + lines is a piecewise-linear function with at most n + pieces. Therefore, the interval (a, b] is divided into at most n + 1 sub-intervals such that in each sub-interval the algorithmic behavior is fixed in iteration + 1. Combining the sub-intervals for each interval [a, b] yields a total of at most (n + 1)- (n + 1)¹ (n + 1)*+1 sub-intervals for iteration t + 1, which the desired result.
(Lower bound.) We construct the instance follows. The states and the neighborhood relations form rooted tree. The root is the initial state Sg. and the tree is full (n 1)-ary tree with depth T. Each non-leaf node has -1 children.
The cost of the root is c1 (So) = (S,) = 1, and corresponds to the whole interval [0, 1]. We recursively set the costs of each node. Suppose a node corresponding to state S and interval [a, bj is not a leaf, and (5) = C2, c2()) = C2. We let the n 1 children , 1 of p correspond to states Si,.... Sn-1, respectively.
Let A- b-o and y >> 0 be a real number be determined later. We set o2 C2 (n i)- - for any E |n 1]. Then, 2 (n- 1)2) We can let y 11-a-2 . (Sm-r) ci (S I-a (n- 1)1
we set e1 (S1) = C T-
*(a+A) Ci (S2) ci (S1) ((a+2A)
small enough such that ei (S..1) > and (2,) > O. It is easy to verify that the solution of (1 - p) -2 (S.) + p2 (s,) = p1-p) c (S(+1) + p 02 11) is p = a + iA. Since C > (Si) > ... > 1S and (2i) < (2( <...< c2()) < C2. we have P1. ..... 1n-1 correspond to intervals (a,a + A], [a A, + 2 [b A, b). respectively.
Therefore, the tree has total of (n- 1)" leaves, and each leaf corresponds to interval of length 1/(n 1)a This gives the (n- 1)T 2 T/2 ((T) lower bound.
C.5. Proof of Theorem 5.2
To prove Theorem 5.2, we first prove few lemmas. We fix smoothed instance I and 1 ~ ī. Let E(ai denote the event that A(a, I)- A(p, I) for any p E a). That is to say, if E(xr) happens, we only need to consider p E [ax 1]. The value of a is to be determined later.
Lemma C.4. For any < 0.5, we have P[(Ea 2 1 2(n + 1)2Tka.
Proof. Let (a( denote the event that the behavior of the local search algorithm is fixed for E [0, a] in the t-th iteration. We first bound the probability (a)]
Fix E (T) and consider the iteration Let S, denote the state after iteration (i E [t)). By the principle of deferred
16

---

Learning Configurations for Data-Driven Multi-Ohjeetive Optimization
decisions, we assume the costs c(S") for any S' E Spas are fixed, where Spest = (N)) the algorithm has already accessed. Notice that any state S' E Spas satisfies c(S") 2 c(St-1). Let Sneu (S' s' N (S, S' & )par). In iteration t, the algorithm chooses the state S' E Snext with the minimal cost c(S") and updates the state. Therefore, the behavior of the algorithm changes as passes discontinuity point satisfying c(S) = c(S"), i.e.
contains the states
(1 p) (0))c(())) (S) + p. c2( = (1- p) .1(S") + c22(S))
(2)
for some S, S' E [St} U Suar. S o S" If p E [0, 1], the discontinuity point is p = x و where A = (c((s) - c1 (5")
and A = (S) - (2() (see Figure 4). p E [0, ai), we have 0 S X S 2 X2 S 2a. Since a 2x-bounded (due to the absolute value), we have (a)) 2 1 1 2(n + 1)²a using an union bound over choices of S, 8".
Finally, we consider the variance of t. A union bound over t = 1..... I gives P[E(a)) 2 1 2(n + T)²
Lemma C.5. For k-smoothed instance i and ~ j, we can partition (a; 1] into #int intervals, such that in each interval, 1) fixed. We have E, [#int] O Tx
Proof. We bound the expectation of the interval number by induction. Let #int, denote the number of intervals in [ar, 1] after iteration i. Similarly to Lemma C.4, we fix t [T] and consider the iteration t. We follow the notations Se, Spast Spext as in the proof of Lemma C.4.
Before iteration I, there are #inty-1 intervals. Each interval Q S [ax, 1] is divided into at most (n + 1)² sub-intervals if the X
value of p satisfying (2) lies in Q. As shown in the proof of Lemma C.4, the value of the discontinuity point p = + (Figure 4), where X and X2 are random variables with support on [o. 1] and probability density at most 2x. By the principle of deferred decisions, we fix the value of Å1- We claim that the probability density of the discontinuity point p is at most OkRa-2) 22, due to the following claim.
Claim C.6. If a real random variable X has density at most K, and Y = =2 2') satisfies Y 2 a >> 0 almost surely. Then, Y has density at most O(22|a~7) -x).
Proof. Let px (x) and py (v) denote the probability density function of X and Y. We have X = g(V) = z/YY which is the desired result.
Therefore, py (v) = Px (g()) 19 1g'(w)) S k
=1 |s o²
Suppose the length of interval Q is I. In expectation, Q produces at most 0Inn2xa=2 new sub-intervals. Combining all intervals Q, the total number of new intervals after iteration in expectation is at most O (n² (n²ka=²) 2).
Therefore, we have E[#int]] E[#int + (n² na =2)-). which means E[+int] O TT a²
Now we are ready prove Theorem 5.2. The general idea is to show that with high probability, the event E(a) happens for all m instances. The total number of possible values for Σ I,) is upper bounded by (m #int)* which gives an Ö( / f//m bound for the smoothed Rademacher complexity.
Proof of Theorem 5.2. Given m k-smoothed instances T,.... i. we aim to bound the smoothed Rademacher complexity Rimm (U), where U denotes the function class (u(lpt...., px], -) S pi 1}.
By Lemma C.4 and a union bound over m instances, we have with probability at least 2mm( + T)2T
m
m u((pr ... .o.n....,.pp..110 T1) Σ u((a Cu(aa..., o), I.), 0A MI, ....... Pk a
Then, suffices to consider p E [a. 1]. We use Eim) to denote the event that (3) happens. To make the probability that &mm) happens high enough, we set a = mi Therefore, we have P[{mm]] 2 1 4. We also have E[#Hint] = O(n which is exponentially smaller than the worst-case ((T) bound. This gives a nigh-probabbllit logarithmic generalization error bound.
17

---

Learning Configurations for Data-Driven Multi-Ohjective Optimization
Let #int denote the total number of intervals for p [0, 1]. By Massart's lemma, have
k llog(m (.
Ri
(1))
m
k lm #int)
k log(mm 0.)
Emm] p(em))
s 0(1)
E
Eiml [m]) +
m
m
Recall that in the worst-case, #int(o.1] S (n + 1)². Since P/E[mi]] >
7 we have
A: klog(m #int)
kT (og(m))
Rí R/mm (1) 5 0(1)
E
Eiml
T
m
m
A: klog(mm #int)
h: Alog(mm)
$ 0(1)
E
m
Tm
A: log(mm E[
le klog(mn)
S 0(1)
m
T'
00 (
k = (1
(log T + log + log + log
l)g m)
m
The second inequality is due to
[E[X- 1(8mmi)] p([mm)
E[X] < (1+0 (++0#))
(7) E[X]
B [m:]
<
1/T
for any random variable X. The third inequality is due to Jensen's 's inequality for concave functions.
C.6. Proof of Theorem 5.3
Proof. The proof is similar to Theorem 5.2. Fix a smoothed instance and I ~ İ. Let E(a) denote the event that A(a, I)= = A(p, I) for any E a). Let #int, denote the number of intervals after iteration i. Initially, #into 1. We study the recursion on #int..
For any E [T], let denote the state after iteration / and S' be the sampled neighbor. If S has not been visited, behavior of the algorithm changes as P passes a discontinuity satisfying
exp (1-0)- (1-p))aa() + p c2() (1- p) ci') P c2(8") prob(t).
Tt
Let A ( d2 =2(()) c2(S). Solving for p yields
log prob(t) + d1
p \ A2
Lemma C.7. P)(E(a)] 2 4Tkg.
Proof. Note that since 0 < (c(( (2( < for any S, we have
t log prob(t) = - p) ci ()) + oz - (1-))))) -
e
E [-1,1]
as long as E [0, 1].
Since A\1 Ael < 2, we have p > a as long as | log prob(t) + A1l > 2a. Since X1 k-bounded, we have P([7: log prob(t) + A S 20] I 4an. A union bound over = 1,..., T proves Lemma C.7.
18

---

Learning Configurations for Data-Driven Multi-Objective Optimization
Lemma C.8. We can partition (a, 1] into #int intervals, such that A(: I) is constant in each interval. We have By 0 (35).
By[intt)
Proof. Let #int; denote the number of intervals in [ax 1] after iteration L. By Claim C.6, the probability density of p on [a, 1] at most O(xa 2). Thus, the expected number of new intervals for iteration at most O(xa 3), i... B[#int,] = El#int,,1l (()a=2). Solving the recurrence shows that E B[#int] (TTra
Therefore, following the proof of Theorem 5.2, we can bound the smoothed Rademacher complexity by Õ( k/mm similarly and obtain the desired result.
C.7. Proof of Lemma 6.5
Proof. To prove this lemma, we first introduce few notations. We use Q to denote the polyhedron of the dual MDP. Let QRR; R2) = (vo, e1, 01,...; et, ut) denote the shadow path of Q. Moreover, we use Q {ur / E P, pls,, a) = 0) to denote the polyhedron P. but fixing u(s, a) O. We also use (B,, R2) (vo ei vi denote the shadow path of pa...
The following claim can be easily verified.
Claim C.9. The optimal solution to the dual MDP is 1e (s, = Ei20 *P(S 8, A, = a). where P(S =, A, a] denotes the probability of St = and A, = a at time t with the initial state So following P[So - s] =((s) and the policy being the optimal policy n²
By Claim C.9, for each state s, the optimal solution 2 u²(ssa) a) = 0 if a + (s), since the optimal policy x" S + A is deterministic. (Note that in the smoothed analysis setting, the optimal policy unique with probability 1.) Given a solution μ., we use (nactive(u) = {(ss a) p(s. a) 0} to denote the set of actions that not used by the corresponding policy x² arg max, (u(s,a).
Suppose the optimal solution moves from v; Us+1 through e; increases. There must exist some action (s, a) such that (s, a) E inactive(r;) and a) & inactive(<:+1) by Claim C.9. Thus, we have
1-1 ΣΣΣ
IQ(R), R2)1
I((s,a) E inactivo(u;) (s, a) & inactive(u;+4))
(4)
1=0 aESa
Interchange the order of summations and fix pair of (s, We bound the expectation of E E inactive(ss) A (s, a) & inactive(E:+))]
Since U4-1, e4, 24, 6,+1, U are on the shadow path Q(R,, R2) (assuming 1 1 < D), we have slope(e,) > slope(er+1).
(s, a) E inactive(1;). then, v, pe.a, i.e., i also on the shadow path Q* R2). Suppose us U2 for some j. Note that Qs,a Q. have slope(e,,)) Z slope(e,) and slope(e(+1) 2 slope(e))1) Thus, have
[[(s, a) E inactive(e:) A ()) & inactive( & Ule E psa A slope(e,,)) " > slope(e411 2 slope(e)f1))
5.a
Plugging this bound into (4) yields
lan
(Q(R,, S ΣΣ
2+
Σ
I[slo)e(e;41) E slope
(5)
sESaEA
1=1
where e depends on j. Note that Pea fixes (ls,a) = O. Therefore, the interval (slope(e, slope(e,.)) does not depend on the value of Rí (s, a) and R2(s, a). By the principle of deferred decisions, we fix the reward on actions other than (s, a) and consider the randomness of R, (s, a) and R2(s, a). Note that
(Re, vx) - (R2, v+11) (Ri, vz) (Ri, vi41)
slope(er+1)
19

---

Learning Configurations for Data-Driven Multi-Objective Optimization
where (R E.,a R(s a))(s, a) is the inner product. Let μ and y' denote the solution of U, and 1/41, respectively, Recall that pu(s, a) 0 and p'(s, a) 0. We can hence represent slope(e++1) as
pl a) R2 a) + deterministic term
n² nl(8,a) a) (s( a) deterministic term
Note that we set d()) 1/|5] for any & E S. By Claim C.9, we have μ'(s, a) Z 1/|S]. Since Ra(s, a) is k-bounded. and the absolute value of the denominator is upper bounded by (L1((1-1) 7)), we claim that the probability density of slope(e;+1) 1) is upper bounded by O S/
Therefore, taking the expectation of (5) yields
(slope(e,))) (loppp(e)]]) |5|K
EIQ(R1 R₂)1 S 0(1)
ΣΣ
2+
Σ
#ES NES
|||
ΣΣ S 01)
O(1) +
(slope(e) slope(e(...))
1-7
#ES aEA aEA
By symmetry, we can break the shadow path into two parts. The slopes of the segments in the first part lie in [- 0), and the ones in the second part lie in (-o0, -1). The expected sizes of the two parts are asymptotically equivalent since we can swap R1 and R2 without loss of generality. Therefore, we assume slope(e,")) s.") ) slope(e) 3.0
(e S 1. We thus have
|
EIQ(Ri, R2) So
(1-7
1-7
which is the desired bound.
D. Extensions of our Framework
D.1. Feature-based parameter predictor
natural extension of algorithm configuration is to train machine learning model to predict the algorithm parameter based on the features of the instance. Balcan al. (2021b) present generalization bounds for selecting parameters from a portfolio of finite algorithm configurations. Cheng al. (2024) study the sample complexity of predicting parameters using neural networks. In the following, we extend our framework for multi-objective optimization to the setting of predicting k parameters using any PAC-learnable (i.e., with finite pseudo-dimension) machine learning models.
Let DD be a distribution of (maybe smoothed) instances, A(p, I) be the output of the algorithm with parameter on instance I, and u(,,I) be the performance metric for set P = (pi..... p of parameter values of p. Instead of directly learning P. we learn a predictor (0) f): θ x I + pk to predict P. For example, if and xz the feature vector of instance 1, we may choose a linear model pred: (0, 1) + 0'z, predict the parameter p. We study the sample complexity of learning A @ for performance metric (ppred(., I), I). We assume the prediction model has finite pseudo-dimension that sample complexity bounds are possible: Let pred (0, I) (pred, (0, I)....,,redd, (0, /)) be the predicted parameters. We assume Pdim ((pred,(e, (6, | (}) I d for any i [R:].
with at most or in expectation t pieces (in worst- or smoothed-case). The sample complexity of u(pred(,, I), is Ō loglog
Theorem D.1. Suppose A(-; T) is piecewise-consseeee
Proof. Fix an instance I. With a little abuse notations, we use I to denote either an instance or a sample from a smoothed instance. By definition, we can partition the parameter space P into t intervals, such that the algorithmic behavior fixed on in each interval. Let Po < P
Pt denote the terminals of these intervals. Let sgn(pred) (0, 1) Pÿ) denote the sign of pred, (8, I) Pj for some 1 < i k, i < t. As we vary the prediction model parameter 6, uppred I), I) is fixed if
i = (sgn(pred, (0, I) P))) isjKt k
fixed due to the piecewise-com peecewiss-constant constant structure of A. Since the pseudo-dimension of pred, is at most d, by Fact B.3, the VC-dimension of (sgn(pred, (0, I) - p3) 0 e Q} is also at most d. Therefore, by Sauer's 's lemma, the number of values of most (rkd).
20

---

Learning Configurations for Data-Driven Multi-Objective Optimization
Now, we vary the fixed instance I. Given m instances, the number of values of
(sgu(pred, (0, 4t) - -P))) isistmm
is most ((ml)kdd) Here, Pj denotes the union of all interval terminals for instances. Using Massart's lemma, we obtain that the Rademacher complexity is at most O (v V (ol(o)))) m
). This proves the desired result.
D.2. Extension to more than two objectives
Previous results focus on learning configurations for multi-objective optimization problems with two objectives. Now, we consider the case of three or more objectives. We show that we can prove similar worst-case sample complexity bounds. For example, we have the following result for local search.
Theorem D.2. Suppose D is distribution over local search instances with d objectives Ci..... Ca. We use local search to optimize the weighted sum objective Σi= Pi Gi with Σi= Pi = Let A(p, T) denote the result instance with parameter p (PL. (PL....,,al) Pd). The sample complexity of ul. I) is O kdT
Proof. Fix an instance I. Since each state has at most neighbors, there are at most n² trajectories of the state in T local search iterations.
Fix trajectory Su, , Sr, where S, denote the state after iteration i. We show that the set of parameters p lie in the union of T n half-spaces. For each / = =,,.... T, the algorithm selects S, E N(S,-1) in iteration Ł if and only if for any S' E [S \ {St}, we have
Σ Pr GS')
Σ pi pa-0 (St); 1=1
which is half-space with respect to p. Altogether, there are T n half-spaces. Combining the half-spaces for n. different trajectories yields total number of TnT+1
Now, we vary the instance I. Given m instances 4,...,, Am. there are at most mfn'*+1 half-spaces partitioning the simplex A = {pl Σ P: = 1} such that in each region, A(p, I;) is fixed for any i E [m]) Note that half-spaces in Rd partition the space into at most Ott)) sub-regions. Therefore, we can partition A into at most O(mI'nn "nnnf*++++> regions such that u(P, I.) is fixed for any i E [m]. Similar to the proof of Theorem 3.2, this yields a pseudo-dimension bound Plim = OkdTT log n), thus leading to Ô kdl")
sample complexity.
Similar results also hold for simulated annealing and linear programs. However, the smoothed analysis technique cannot be directly extended to 3 or more objectives. The reason is that in the 2-objective case, we can directly bound the probability that a discontinuity point lies in length-/ interval by (ppoy(xx) I). However, this approach does not work for a multi- dimensional space. Even if a set of half-spaces are close to each other, the (hyper-)volume of the union of half-spaces can be large. We left the smoothed analysis of multi-dimensionall parameter spaces to future work.
E. Details of Experiments
In this section, we present the implementation details of our experiments in Section 7.
Local search. We consider the VLSI circuit partitioning problem for 3D chips (Hu et al., 2022). Given a circuit netlist (represented by hypergraph), we aim to partition the netlist into two parts. The first and second parts correspond to the top and bottom dies, respectively. If net (i.c., a hyperedge the hypergraph) crosses both dies, a cross-die terminal is required to connect both dies. We need to minimize the number of terminals (corresponding to the routability and the cost of the chip). as well as the total wirelength after circuit placement (corresponding to the performance of the chip).
A direct method for circuit partitioning is local search. We initialize an arbitrary partition, and improve the solution by locally moving a cell (i.e., a node in the hypergraph) from the current die to the other. We optimize a weighted sum of both objectives, where the number of terminals can be directly computed and the total wirelength is evaluated by running a VLSI placer. Notice that VLSI placers (e.g., Lin al. (2019)) are randomized algorithms, and the outcomes of the
21

---

multiple kinds Learning Configurations for Data-Driven Multi-Objective Optimization
wirelength naturally contain random perturbations. This shows that the smoothed analysis setting is indeed reasonable. In experiments, we fix the random seed of the placer make the placement result deterministic.
We evaluate the generalization guarantee for local search on ICCAD-22 benchmark (Hu et al., 2022). Since the benchmark consists of only several testcases, we randomly sample subgraphs of the original circuit to obtain instances with various sizes.
Markov decision processes. We consider a resource- gattrriig Markov decision process in previous work on multi-objective reinforcement learning (Barrett & Narayanan, 2008). The environment is a grid graph with a home base. The agent starts from the home base, gathers resources in the environment, and takes them back to the home. There of resources, RI, R2, etc. If the agent reaches grid node with resource Ri, it picks up one unit of Ri. The agent can simultaneously carry at most one unit for each kind of resource. When the agent reaches the home base, it gets one reward for each kind of resource it carries. Some grid nodes have enemies. If the agent passes node with enemies, with a particular probability, it receives a penalty, loses the resources it carries, and is reset to the home base. The objective to maximize the reward and minimize the penalty.
We set the discount factor 7 = 0.9, and find the optimal policy by optimizing weighted sum of the reward and the penalty, We randomly synthesize the environment with different sizes test the generalization ability. We synthesize 100 instances for each problem size (since finding all pieces is time-consuming), with 50 being the training set, and the rest being the test set.
For both local search and MDP, we compute the number of pieces in the seecewise-constan structure. To compute this number, starting from = 0, we use binary search to find the next value of p such that the algorithm outcome varies until
p=
Shallow-light trees. The open-source code of SALT (Chen & Young, 2020) and the ICCAD-15 benchmark (Kim & Hu, 2015) for timing-driven driven VLSI placement are used. The ICCAD-15 benchmark consists of 9.9 x 10th shallow-light tree instances, in which about 4.8 x 10s instances are large-degree instances, i.e., with more than 32 nodes. The experiments are conducted on large-degree instances, since the tradeoff between shallowness and lightness is not significant for small-degree nets. We randomly select 80% nets as the training set and the rest as the test set. We learn a set of parameter values p to optimize the Pareto volume of shallowness and lightness.
Let a and 3 denote the shallowness and lightness of a solution. Since the shallow light tree a minimization problem, we define the Pareto volume the area of domination for (OFLUTE o; BCL 3), where OFLUTE and AcL are baselines for single-objective Steiner trees in the original paper (Chen & Young, 2020).
22


Reviews:
[{"review_id": "acGB352THi", "reviewer": "Reviewer_mqRb", "summary": "This paper proves generalization guarantees for the problem of selecting a weighting parameter in multiobjective optimization. Then, it proves the PAC-learnability of parameters which maximize the Pareto volume in polynomial time. It adapts these results to several classes of optimization problems.\n\n## Update after author response\nRegarding the authors' last comment, I agree there is no such contradiction within the paper's claimed contributions. My main point was that appreciating its essential, novel contributions requires much discernment between the proposed and previously existing work, as well as between the preface material (which is framed pretty generally) and the more limited scope which is ultimately delivered on. Overall I don't have the confidence to push for acceptance, but would not oppose it.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thanks for your review! We are delighted that you consider our work thorough and comprehensive. We address your concerns as follows:\n\n> Q: How novel are the theoretical results of Section 3.1? Are they very general beyond the setting of multiobjective discrete optimization?\n\nWe admit that the results in Section 3.1 are not technically novel. As discussed in the paper, the piecewise-constant structure has appeared in previous work, e.g., Gupta & Roughgarden (2017), Balcan et al. (2018a, 2021a). The difference is that we need to learn multiple parameters in multiobjective optimization (MOO), while in previous work, only one parameter is required (and this is where our analysis is related to MOO).\n\nHowever, we want to emphasize that we introduce the results in Section 3.1 only because it is the basis of subsequent analysis. The main technical novelty of our work is the subsequent bounds on the number of pieces in this structure (especially Sections 5 & 6). We use smoothed analysis to reduce the worst-case exponential bounds to polynomial sizes for local search and linear programs, which are highly non-trivial compared with previous work.\n\nFor example, Balcan et al. (2018a) study the generalization bound of selecting branching parameters for integer programming (IP). They prove the number of pieces for the branching parameter is $O(2^{n(n-1)/2}n^n)$, and this gives an $O(n^2)$ pseudo-dimension / Rademacher complexity bound for IPs with $n$ variables. This bound is very loose (e.g., it requires over $10^6$ samples to obtain a non-vacuous generalization bound). However, in our work, although the number of pieces can be exponential in the worst-case, it can be reduced to polynomial under a slight random noise for local search and linear programs (and this matches empirical results). Thus, **logarithmic** Rademacher complexity bounds are achieved. We believe this phenomenon is very interesting since similar results have not appeared in other data-driven algorithmic settings, and this is the key contribution of our work.\n\n> Q: Is the algorithm for Pareto volume optimization novel, or just the guarantees?\n\nWe agree that submodular maximization is a classic algorithm and is applied to many machine learning tasks, such as feature selection [1]. However, to the best of our knowledge, this is the first work that applies submodular optimization to parameter selection of MOO problems.\n\nAnother thing that we want to point out is that ERM is seldom discussed in previous work of data-driven algorithm design. The only work is [2] and its method is not very practical. Thus, although proving the submodularity of Pareto volume is not technically fancy, we believe it is interesting to present our ERM method in the paper, considering its application in practice (Section 7.2).\n\n[1] Bilmes. Submodularity In Machine Learning and Artificial Intelligence. arXiv 2202.00132.  \n[2] Balcan et al. Accelerating ERM for data-driven algorithm design using output-sensitive techniques. NeurIPS-2024.\n\n> Q: I wish the paper were more friendly to beginners in statistical learning theory, because despite being greatly interested in data-driven optimization, the paper left me questioning how interesting I should find this intersectional topic.\n\nThanks for your valuable advice! Since we want to make our presentation of main results rigorous and comprehensive, we spend much space on discussing settings of our results, and only discuss the intuition of using statistical learning theory to study MOO in Section 1. We will modify it to include more intuitive discussions (if accepted). We clarify as follows to make our contributions clear:\n\nBriefly speaking, statistical learning theory answers the question of why machine learning models can generalize to unseen data in training. A tight generalization bound is important since it implies the number of data samples such that the learned model does not overfit training data and has strong generalization abilities.\n\nThe same question also arises in algorithm configuration. In practice, we just tune the parameter of MOO algorithms on sampled instances, and select a configuration that performs good on these instances. But why does this parameter generalize?\n\nOur work answers this question by showing that the size of the piecewise-constant structure is small. Thus, the learned parameters for MOO can generalize since the intrinsic complexities of these MOO algorithms are limited. From the practical view, our logarithmic generalization bound indicates that the number of instances required for training is only **logarithmic** as the problem size grows. From the theoretical view, our results are interesting, since it is somewhat surprising that classic learning theory, (together with smoothed analysis) is also able to shed light on algorithm configuration with **discrete** algorithmic structures.\n\nWe hope that the above responses make the positioning of our paper more clear with our contributions clarified.", "claims_and_evidence": "The evidence comes mainly in the proofs. I'm not qualified to validate the correctness of the proofs, but I believe all the evidence is sound to the best of my understanding.", "methods_and_evaluation_criteria": "The paper seems to propose a method for the ERM optimization of the weighting parameter, based on well-known submodular optimization, but I cannot tell how novel is the method itself. Otherwise the paper proposes no new methods, but focuses on provable theoretical results.", "theoretical_claims": "All the proofs are relegated to the appendix; I have read through their organization but did not check the details. I don't detect any major faults.", "experimental_designs_or_analyses": "The experimental context of the paper is quite sparse, consisting of a figure which corroborates the generalization bounds, and a table which reports accuracy of the proposed ERM. I don't see any issues with the results.", "relation_to_broader_scientific_literature": "The paper is at the intersection of statistical learning theory and data-driven optimization.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "I think the paper does a rather thorough job of what it sets out to do: proving error bounds around the problem of learning an optimal objective weight in multi-objective optimization. It also does a good job of relating how those abstract results can be applied to optimization problems of specific forms. For readers interested in these specific questions, I believe this paper provides comprehensive answers. \n\nMy only concern is how significant the results really are, to those who would be interested. From what I can gather, almost none of the analysis before Section 3.2 seems to depend on the fact that were are studying multi-objective optimization. It seems to mostly follow from the piecewise-constant property, which should be satisfied by any number of parameter selection problems for discrete algorithms, not just multiobjective optimization. I'm not positioned to tell how novel is this material. \n\nThe ERM method for Pareto volume maximization by submodular optimization is pretty interesting, but again I cannot tell how novel is the idea itself, or if the novelty lies in the theoretical guarantee.", "other_comments_or_suggestions": "The paper is tightly structured to present all the results in a very organized way, which makes it easy to navigate around. On the other hand, much back and forth navigation was necessary for me, since the paper wastes very little space to motivate the intuitive significance of each result. I won't presume to suggest this is a flawed organization, but I feel it puts much onus on the reader to find their own reasons to be interested in the results. I wish the paper were more friendly to beginners in statistical learning theory, because despite being greatly interested in data-driven optimization, the paper left me questioning how interesting I should find this intersectional topic.", "questions_for_authors": "- Is the algorithm for Pareto volume optimization novel, or just the guarantees?\n- How novel are the theoretical results of Section 3.1? Are they very general beyond the setting of multiobjective discrete optimization?\n- If so, why do they not already exist in the literature?", "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": "", "extra_scores": {}}, {"review_id": "K0XXuH7ogF", "reviewer": "Reviewer_N1Jh", "summary": "This paper develops a theoretical framework for learning algorithm configurations in the context of multi-objective optimization. The framework is then applied to several settings, including approximation algorithms, local search, general linear programming, and Markov decision processes.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thanks for your review! We are delighted that you consider our work sound and rigorous. We address your concerns as follows:\n\n> Q: Does the proposed theoretical framework for data-driven multiobjective optimization offer any practical insights?\n\nThis is a very good question. In this work, we use statistical learning theory to study the generalization ability of multi-objective optimization (MOO) algorithms. Briefly speaking, statistical learning theory answers the question of why machine learning models are able to generalize to unseen data in training. A tight generalization bound is important since it implies the number of data samples such that the learned model does not overfit training data and has strong generalization abilities.\n\nThe same question also arises in algorithm configuration. In MOO, we just tune the parameter of MOO algorithms on sampled problem instances, and select a configuration that performs good on these instances in practice. But why does this parameter generalize? Our work answers this question by showing that the size of the piecewise-constant structure is small. Thus, the learned parameters for MOO can generalize since the intrinsic complexities of these MOO algorithms are limited. From the practical view, our logarithmic generalization bound (w.r.t. problem sizes) indicates that the number of problem instances required for training is only **logarithmic** as the problem size grows.\n\nMoreover, our empirical risk minimization method for Pareto volume in Section 3.2 is actually practical. As we show in experiments of Section 7.2, the ERM method indeed improves the Pareto volume (although the $1-1/e$ approximation ratio may be loose in practice).\n\n> Q: The smoothed analysis is restricted to the two-objective case.\n\nThis is indeed a limitation of our analysis. Still, we emphasize that the smoothed analysis for two objectives in our paper is already non-trivial compared with previous work. For example, Balcan et al. (2018a) studies the generalization bound of selecting branching parameters for branch-and-bound solvers. They prove that the number of pieces for the branching parameter is $O(2^{n(n-1)/2}n^n)$, and this gives an $O(n^2)$ pseudo-dimension / Rademacher complexity bound for integer programs with $n$ variables. This bound is very loose (e.g., it requires over $10^6$ samples to obtain a non-vacuous generalization bound). However, in our work, although the number of pieces can be exponential in the worst-case, it can be reduced to polynomial under a slight random noise for local search and linear programs (and this matches empirical results). Thus, logarithmic Rademacher complexity bounds (w.r.t. problem sizes) are achieved. We believe this phenomenon is very interesting since similar results have not appeared in other data-driven algorithmic settings.\n\nMoreover, the case of two objectives has already covered many applications of MOO in practice, e.g., the reference Yang et al. (2023) in our paper. Thus, our analysis is compatible with practice.\n\n> Q: It would be good to validate all the algorithms discussed in Sections 4, 5, and 6 in the experiments section.\n\nThanks for your advice! Since the primary area of our paper is learning theory, we put much attention to theoretical results in our work. We will include more experimental results in the appendix (if accepted).\n\nWe hope that the above responses make the positioning of our paper more clear with our contributions clarified.", "claims_and_evidence": "The claims are generally supported by detailed proofs and experimental evidence.", "methods_and_evaluation_criteria": "The proposed method is appropriate for addressing the problem.", "theoretical_claims": "I didn't check the correctness of proofs for theoretical claims.", "experimental_designs_or_analyses": "The experimental design is sound overall.", "relation_to_broader_scientific_literature": "It is related to data-driven algorithm design and multi-objective optimization, which are discussed in the paper.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "**Strengths:**\n\n- The paper establishes a rigorous theoretical foundation for Data-Driven Multi-Objective Optimization.  \n- It successfully utilizes advanced techniques to derive sample complexity bounds.  \n- it provides sample complexity bounds for learning configurations across various algorithms.  \n\n**Weaknesses:**  \n\n- The smoothed analysis is restricted to the two-objective case.  \n- It would be good to validate all the algorithms discussed in Sections 4, 5, and 6 in the experiments section.", "other_comments_or_suggestions": "See Weaknesses.", "questions_for_authors": "Does the proposed theoretical framework for data-driven multiobjective optimization offer any practical insights?", "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": "", "extra_scores": {}}, {"review_id": "ocPpXra23A", "reviewer": "Reviewer_84tm", "summary": "This paper establishes the theoretical foundation of data-driven multi-objective optimization. Authors discuss the piecewise structure of combinatorial optimization algorithms and prove a theorem which bounds the sample complexity of parameterized multi-objective combinatorial optimization algorithms. Authors then analyse the application of the proposed theorem on several algorithms and experimental results validate the effectiveness of the propsoed method on  multi-objective combinatorial optimization problems.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thanks for your review! We answer your question as follows:\n\n> Q: Since the title is multi-objective optimization (instead of combinatorial multi-objective optimization) while the discussions in the paper seem mostly focus on combinatorial optimization, can the proposed method be applied to continuous multi-objective black box optimization algorithms (i.e., MOEA/D or NSGA-III) which may not have piecewise-constant structures?\n\nThis is a very good question!\n\nFirst, in Section 6.1 we focus on generalization results for general linear programs. Linear programming is not usually considered as a combinatorial optimization problem (and this is why we say multi-objective optimization (MOO) instead of combinatorial MOO in the title).\n\nSecond, generalization bounds for the configuration of black-box optimization algorithms are indeed an interesting direction for future research. Sadly, due to the black-box nature of these problems (which means the landscape of the performance metric function is unknown), the behavior of these algorithms may go arbitrarily ill without reasonable assumptions. We do not have substantial mathematical tools to tackle them. In future work, we will explore whether some mild assumptions can yield meaningful generalization guarantees.\n\n> Q: How is the time efficiency of the proposed method, i.e., comparing to the vanilla geometric series in SALT?\n\nThe time overhead is rather mild compared with vanilla parameter settings. For the ICCAD-15 benchmark, the number of pieces is usually only between 2 to 5 for most instances. Since we use binary search to find the pieces of each instance, the ERM method is very efficient. It costs about 23 minutes for the complete ERM and evaluation process, while the vanilla method has already required about 19 minutes to run all instances (for the extreme case of $k=12$).\n\n> Q: In Appendix A authors present the review of related works. However, for algorithm configuration and machine learning for multi-objective optimization, some related works are not included, especially black-box optimization works.\n\nThanks for pointing out the missing references! We will include them in the paper (if accepted). Still, just to clarify, we remark that the generalization bound results in our work are based on **uniform convergence**, which is independent of the learning algorithm. Thus, these results hold for **any algorithm configurators** that are used.\n\n> Q: Although the authors provide comprehensive proofs for the proposed method, the performance comparison in the experiment only includes the application on SALT with two-objective problems, while more algorithms and problems with more objectives are not rigorously evaluated.\n\nWe clarify that the contributions of our sample complexity results include two parts: Section 3.1 focuses on the uniform convergence generalization bounds, which is independent of the ERM algorithm. It holds for any algorithm configurators and any performance metric functions. Section 3.2 focuses on the special case that the performance metric is the Pareto volume. In this case, we present an efficient ERM method to select the parameters.\n\nExperiments in Section 7.1 are conducted to verify the results in Section 3.1 (local search and MDP), while Section 7.2 focuses on the ERM method (SALT). Section 7.1 is also very important, since they are conducted to verify the effectiveness of smoothed analysis for local search and linear programs. The results in Section 7.1 show that the number of pieces in the piecewise structure grows moderately as we increase the problem size. This shows that the smoothed analysis setting is reasonable and is compatible with practice (which is a key contribution of our work). In Section 7.2, we evaluate the ERM method on the SALT algorithm since the Pareto curves are generally applied to evaluate the shallow-light Steiner tree algorithms as in Chen & Young (2020).\n\nWe hope that the above responses make the positioning of our paper clearer with our contributions clarified.", "claims_and_evidence": "The authors demonstrate the effectiveness of the proposed method on configuring parameters for different approximation algorithms, local search methods and linear programing methods on multi-objective combinatorial optimization problems in the experiments.", "methods_and_evaluation_criteria": "The authors present the detailed proof of the proposed theorems and methods in the paper and appendix, experimental results also validate the effectiveness of the proposed method, which makes sense.", "theoretical_claims": "The authors provide the detailed proof of the proposed theorems, lemmas and claims in the Appendix one by one.", "experimental_designs_or_analyses": "The authors discuss the changing of the number of pieces and generalization errors of local search and MDP methods along the problem size. The superior performance of the proposed method configured SALT over vanilla SALT is demonstrated. However, the performance of the local search and LP methods configured by the proposed method is not evluated.", "relation_to_broader_scientific_literature": "1) Algorithm Configuration: The proposed theorems and method are used to configure tunable paremeters of algorithms.\n\n2) Multi-objective optimization: The proposed method is applied to solve multi-objective optimization problems.", "essential_references_not_discussed": "In Appendix A authors present the review of related works. However, for algorithm configuration and machine learning for multi-objective optimziation, some related works are not included, especially black-box optimization works. For instance, MADAC[1] published in NeurIPS 2022 uses multi-agent Reinforcement Learning for algorithm configuration on multi-objective optimziation algorithm, similar works include RLMODE[2], MRL-MOEA[3] and so on. I recommend referring to an ArXiv survey[4] which provides more machine learning based algorithm configuration works for multi-objective optimziation.\n\n[1] Xue, Ke, et al. \"Multi-agent dynamic algorithm configuration.\" Advances in Neural Information Processing Systems 35 (2022): 20147-20161.\n\n[2] Yu, Xiaobing, et al. \"Reinforcement learning-based differential evolution algorithm for constrained multi-objective optimization problems.\" Engineering Applications of Artificial Intelligence 131 (2024): 107817.\n\n[3] Wang, Jing, et al. \"A novel multi-state reinforcement learning-based multi-objective evolutionary algorithm.\" Information Sciences 688 (2025): 121397.\n\n[4] Ma, Zeyuan, et al. \"Toward Automated Algorithm Design: A Survey and Practical Guide to Meta-Black-Box-Optimization.\" arXiv preprint arXiv:2411.00625 (2024).", "other_strengths_and_weaknesses": "Weakness: Although the authors provide comprehensive proofs for the proposed method, the performance comparison in the experiment only includes the application on SALT with two-objective problems, while more algorithms and problems with more objectives are not rigorously evaluated.", "other_comments_or_suggestions": "None.", "questions_for_authors": "1) Since the title is multi-objective optimization (instead of combinatorial multi-objective optimization) while the discussions in the paper seem mostly focus on combinatorial optimization, can the proposed method be applied to continuous multi-objective black box optimization algorithms (i.e., MOEA/D or NSGA-III) which may not have piecewise-constant structures?\n\n2) How is the time efficiency of the proposed method, i.e., comparing to the vanilla geometric series in SALT?", "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": "", "extra_scores": {}}, {"review_id": "ea6kIaHMqo", "reviewer": "Reviewer_HLDU", "summary": "This paper provides a generalization framework for data-driven multi-objective optimization through sample complexity analysis. The smoothed analysis offers logarithmic bounds, making the framework feasible for real-world problems. If the performance metric is Pareto volume, this paper further shows that an approximately optimal configuration can be PAC-learned. The proposed framework is then applied to various problems including local search, linear programming, MDP, etc. Numerical results also support the smoothed analysis assumption.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thanks for your review! We are delighted that you considered our work clearly organized and logical. We answer your question as follows:\n\n> Q: The proof assumes the piecewise-constant structure holds for all instances, but this paper does not discuss how to verify it. This property is crucial to bound the algorithm's complexity.\n\nWe want to clarify that the piecewise-constant structure (Definition 3.1) is not an **assumption**, but a **condition** of our framework in Section 3.1. The algorithms we analyze in Sections 4, 5, and 6 all satisfy this condition as in our proofs.\n\n> Q: Theorem 3.6 assumes an oracle to compute each piece of $\\mathcal{A}$. A more detailed discussion of the oracle in the practical implementation would be better provided to enhance clarity. How this could be relaxed or approximated in real-world applications.\n\nThanks for your suggestion! In Appendix E (line 1119 of page 21), we discuss how to compute the number of pieces in this structure experimentally (i.e., the oracle in Theorem 3.6). Starting from zero (if the parameter lies in $[0,1]$), we use binary search to find the breaking point of the current piece, and iteratively do this for each piece we found. We will add a remark after Theorem 3.6 to enhance clarity (if accepted).\n\n> Q: For Appendix D, the extension seems to lack discussion on feature selection, model choice (linear, neural nets).\n\nLet us clarify our result in Appendix D.1: Theorem D.1 is a general result. It holds for **any features** $\\theta$ and **any prediction model** with a finite pseudo-dimension $d$. For example, if the model is the linear regression with $F$ features, then $d=F$. If the model is a ReLU neural network with $W$ weights and $L$ layers, then $d=O(WL\\log W)$ [1].\n\n[1] Bartlett et al. Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 2019.\n\nWe hope that the above responses make the positioning of our paper clearer with our contributions clarified.", "claims_and_evidence": "Most claims are supported by clear evidence.\n\nTheorem 3.6 assumes an oracle to compute each piece of $\\mathcal{A}(\\cdot, I)$. A more detailed discussion of the oracle in the practical implementation would be better provided to enhance clarity. How this could be relaxed or approximated in real-world applications.", "methods_and_evaluation_criteria": "The benchmarks including Shallow-light Trees, Local Search, and synthetic MDPs are common domains for multi-objective optimization. The Pareto volume is a standard metric for multi-objective optimization. Both the benchmark datasets and performance metrics make sense for the proposed method. However, the restriction to only two objectives limits the applicability to higher-dimensional situations. It would be better to provide some empirical demonstration, not just the discussion in Appendix D.", "theoretical_claims": "The proof assumes the piecewise-constant structure holds for all instances, but this paper does not discuss how to verify it. This property is crucial to bound the algorithm's complexity.", "experimental_designs_or_analyses": "Figure 3 shows the number of discontinuities/number of pieces and generalization error as functions of problem size, demonstrating the smoothed complexity bound.", "relation_to_broader_scientific_literature": "This paper connects multi-objective optimization and data-driven design by introducing piecewise-constant structure and smoothed analysis.", "essential_references_not_discussed": "As far as I know, all the essential related works are cited and discussed. It would be better to provide more details on the piecewise constant structure.", "other_strengths_and_weaknesses": "This paper is clearly organized, with a logical progression from theoretical framework to applications and numerical results.", "other_comments_or_suggestions": "I do not have any other comments.", "questions_for_authors": "All my concerns are presented above.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers all like the line of research and find the results interesting. The submission nicely combines multi-objective optimization with the framework of data-driven algorithms. The main point of the discussion was if the methods are novel enough to meet the bar for ICML. While the general framework for bounding the sample complexity is by now standard, the main novelty is in Sections 5 and 6 and consists in applying smoothed analysis to the problem in question. This is a nice twist but also in these sections the methods seem quite related to previous work on smoothed analysis. Overall, the submission contains interesting results even though the technical novelty is somewhat debatable.
Decision: Accept (poster)