Accelerating ERM for data-driven algorithm design using output-sensitive techniques
Authors: Maria Florina Balcan
Christopher Seiler
Dravyansh Sharma
Venue: NeurIPS 2024 poster (2024)
Keywords: Learning Theory
Data-driven Algorithm Design
Primary area: learning_theory

Abstract: Data-driven algorithm design is a promising, learning-based approach for beyond worst-case analysis of algorithms with tunable parameters. An important open problem is the design of computationally efficient data-driven algorithms for combinatorial algorithm families with multiple parameters. As one fixes the problem instance and varies the parameters, the “dual” loss function typically has a piecewise-decomposable structure, i.e. is well-behaved except at certain sharp transition boundaries. Motivated by prior empirical work, we initiate the study of techniques to develop efficient ERM learning algorithms for data-driven algorithm design by enumerating the pieces of the sum dual loss functions for a collection of problem instances. The running time of our approach scales with the actual number of pieces that appear as opposed to worst case upper bounds on the number of pieces. Our approach involves two novel ingredients – an output-sensitive algorithm for enumerating polytopes induced by a set of hyperplanes using tools from computational geometry, and an execution graph which compactly represents all the states the algorithm could attain for all possible parameter values. We illustrate our techniques by giving algorithms for pricing problems, linkage-based clustering and dynamic-programming based sequence alignment.

Accelerating ERM for data-driven algorithm design using output-sensitive techniques
Maria-Florina Balcan"
Christopher Seiler'
Dravyansh Sharma
Abstract
Data-driven algorithm design is promising, learning-based approach for be- yond worst-case analysis of algorithms with tunable parameters. An important open problem is the design of computationally efficient data-driven algorithms for combinatorial algorithm families with multiple parameters. As one fixes the problem instance and varies the parameters, the "dual" loss function typically has structure, i.e. is well-behaved except at certain sharp
a piecewise-deconposaee transition boundaries. Motivated by prior empirical work, we initiate the study of techniques to develop efficient ERM learning algorithms for data-driven algorithm design by enumerating the pieces of the sum dual loss functions for collection of problem instances. The running time of our approach scales with the actual number of pieces that appear opposed to worst case upper bounds the number of pieces. Our approach involves two novel ingredients an output-sensitive algo- rithm for enumerating polytopes induced by a of hyperplanes using tools from computational geometry, and an execution graph which compactly represents all the states the algorithm could attain for all possible parameter values. We illustrate our techniques by giving algorithms for pricing problems, linkae-bbssed clustering and caammii--pgrrammnng based sequence alignment.
Introduction
The data-driven algorithm design paradigm captures widely occuring scenario of solving multiple related problem instances and allows the design and analysis of algorithms that use machine learning learn how to solve the instances which come from the same domain [GR16] Bal20]. Typically there are large (often infinite) parameterized algorithm families to choose from, and data-driven algorithm design approaches provide techniques select algorithm parameters that provably perform well for instances from the same domain. Data-driven algorithms have been proposed and analyzed for variety of combinatorial problems. including clustering, computational biology and mechanism design [BD220] BDD + 21 [PS20). But most of the prior work has focused on sample efficiency of learning good algorithms i.e. the number of problem instances needed to learn algorithm parameters that perform well on typical problem from the domain. A major open question for this line of research is to design computationally efficient learning algorithms [GR20 BDS21
The parameterized family may occur naturally in well-known algorithms used in practice, or one could potentially design new families interpolating known heuristics. For the problem of aligning pairs of genomic sequences, one typically obtains the best alignment using a dynamic program with some costs or weights assigned edits of different kinds, such as insertions, substitutions, or reduplications [Wat89]. These costs are the natural parameters for the alignment algorithm. The quality of the alignment can strongly depend on the parameters, and the best parameters vary depending on the application (e.g. aligning DNAs or RNAs), the pair of species being compared, or
" "Carnegie Mellon University, ninamf@cs. cmu. edu.
Work done by Christopher Seiler while he was CMU.
1 Cooresponding author: dravyêttic. edu. Work done by Dravyansh Sharma while he was at CMU.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Problem
Dim.
Ts (prior work)
T's (ours)
Term (m instances)
Linkage-based
d= 2
On log n)
[DL200]
O
mI'ss Omm" Ry)
clustering
any d
(n log n
BD220
Ó(R²n2)
mIs Omm? R3,
DP-based sequ- ence alignment
d = 2
( + RT be
GBN94
O(RTpr)
mT's + QmT Rx.
any d
( or BDD
21
O(ReL+)ToN))
mI'ss + Óm Rtz
Two-part tariff pricing
t=1
O(K*)
BPS20
O(R+K) K) Ö(R²K)
RRy + mK log mk)
any L' KOL'))
BPS20
mIss + O0mK
Table 1: Summary of running times of the proposed algorithms. TERM denotes the running time for computing the pieces in the sum dual class function in terms of Ts. the time for enumerating the pieces on single problem instance (Theorem 2.3). Ry (resp. R) denotes the number of pieces in the sum dual class function for given m problem instances (resp. dual class function for a single problem instance). n is the size of the clustering instance. 8 is the length of sequences to be aligned, L is the maximum number of subproblems in the sequence alignment DP update, R is the maximum number of pieces in the dual class function over all subproblems, TDP is the time to solve the DP on single instance. K is the number of units of the item sold and é is the menu length. The Ô notation suppresses logarithmic terms and multiplicative terms that only depend on d or L.
the purpose of the alignment. Similarly, item prices are natural parameters in automated mechanism design [BVI BPS20]. On the other hand, for linkage-based clustering, one usually chooses from a set of different available heuristics, such as single or complete linkage. Using an interpolation of these heuristics to design a parameterized family and tune the parameter, one can often obtain significant improvements in the quality of clustering (BNVWT7 BDL20).
A common property satisfied by a large number of interesting parameterized algorithm families is as function of the real-valued parameters for any fixed problem instance-callae the "dual class function" " [BS21]] is a piecewise structured function, i.e. the parameter space can be partitioned into "pieces" via sharp transition boundaries such that the loss function is well-behaved (e.g. constant or linear) within each piece [Bal20]. Prior work on data-driven algorithm design has largely focused on the sample complexity of the empirical risk minimization (ERM) algorithm which finds the loss- mossmminimizing value of the parameter over a collection of problem instances drawn from some fixed unknown distribution. The ERM on collection of problem instances can be implemented by enumerating the pieces of the sum dual class loss function. We will design algorithms for computationally efficient enumeration of these pieces, when the transition boundaries are linear, and our techniques can be used to learn good domain-specific values of these parameters given access to multiple problem instances from the problem domain. More precisely, we use techniques from computational geometry to obtain "output-sensstive" algorithms (formalized in Appendix (C) that scale with the output-size Rs (i.e. number of pieces in the partition) of the piece enumeration problem for the sum dual class function occurring problem instances, the number of pieces much smaller than worst case bounds on BDL20 GS96 and our results imply significant gains in running time whenever Ry is small.
that the loss I
collection of problem instances. Often, on commonly
Our contributions. We design novel approaches that use tools from computational geometry and lead to output-sensitiv algorithms for learning good parameters by implementing the ERM (Empirical Risk Minimization) for several distinct data-driven design problems. The resulting learning algorithms scale polynomially with the number of sum dual class function pieces Ry in the worst case (See Table I] and are efficient for small constant d.
1. We present novel output-sensitive sensitive algorithm for enumerating the cells induced by a collection of hyperplanes. Our approach applies to any problem where the loss is piecewise linear, with convex polytopic piece boundaries. We achieve output-polynomial time by removing redundant constraints in any polytope using Clarkson's 's algorithm (from computational geometry) (Cla94) and performing an implicit search over the graph of neighboring polytopes (formally Definition 2 Our results are useful in obtaining output-sensitive running times for several distinct data-driven algorithm design problems. Theorem 2.3 bounds the running time of the implementation of the
'or utitity, basically function that measures the performance of any algorithm in the family on any problem instance.
2

---

ERM for piecewise- structured duals with linear boundaries (Definition 1 that scales with Ry provided we can enumerate the pieces of the dual class function for single problem instance. It is therefore sufficient to enumerate the pieces of dual function for single instance, for which Theorem saroorem.22iss useful.
2. We show how to learn multidimensional parameterized families of hierarchical clustering algo- rithms) Our approach for enumerating the pieces of the dual class function on a single instance extends the execution tree based approach introduced for the much simpler in [BDL20] to multiple dimensions. The key idea is to track the convex polytopic subdivisions of the parameter space corresponding of the execution tree and apply our output-sensitive cell-enumeration algorithm at each node. For dynamic programming (DP) based sequence alignment, our approach for enumerating pieces of the dual class function extends the execution tree to an execution directed acyclic graph (DAG). For a small fixed d, our algorithm is efficient for small constant L, the maximum number of subproblems needed to compute any single DP update. Prior work [GBN94] only provides an algorithm for computing the full partition for d = 2, and the naive approach of comparing all pairs of alignments takes exponential time.
family
single merge step in the linkage procedure via nodes
Our main contribution is to show that when the number of pieces (Rg in Table L is small we can improve over computational efficiency of prior work. Our techniques involves a novel application of Clarkson's 's algorithm (used to remove redundant inequalities from system of linear equations) to derive output-sensitive enumeration, and execution graphs which capture problem-specific structure.
Motivation from prior empirical work. For the clustering problem. we give theoretical bounds on the output-size R depending on the specific parametric family considered (e.g. Lemmas [.] I.2. These bounds imply strict improvement even for worst-case R. but can be much faster for typical R. Indeed, prior empirical work indicates
much smaller than the worst case bounds in practice [BDL20], where even for d = 1 there is dramatic speed up of over 10 times by being output-sensitive. For the sequence alignment problem, again the upper bounds on R depend on the nature of cost functions involved. For example. Theorem 2.2 of [GBN94] gives upper bound on R for the 2-parameter problem with substitutions and deletions. For the TPT pricing problem we prove new theoretical bounds on R (Theorem G.3) that show worst-case improvements (cubic to quadratic) in the running time over prior work. In practice, R is usually much smaller than the worst case bounds, making our results even stronger. In prior experimental work computational biology data (sequence alignment with = 2, sequence length ~ 100), [GS96] observe that of a possible more than 200 alignments, only R = 120 appear as possible optimal sequence alignments (over IR2) for pair of immunoglobin sequences (a speed-up of over 58 orders of magnitude).
Preliminaries. We follow the notation of [al20]. For given algorithmic problem (say clustering, or sequence alignment), let II denote the set of problem instances of interest. We also fix a (potentially infinite) family of algorithms A, parameterized by set P C Rdd. Here d is the number of real parameters, and will also be the 'fixed' parameter in the FPT (Fixed Parameter Tractability) sense (Appendix(C). Let A, denote the algorithm in the family A parameterized by p E P. The performance of any algorithm on any problem instance is given by utility (or loss) function u : IT x P - [0, H), i.c. u(x. p) measures the performance on problem instance x E 11 of algorithm Ap E A. The utility of a fixed algorithm A, from the family is given by U, 11 + [0. H]. with up(x) = u(x, We are interested in the structure of the dual class of functions u, P + [0, HI. with u. (g = up(x), which measure the performance of all algorithms of the family for a fixed problem instance x E II. We will use II-)) to denote the 0-1 valued indicator function. For many parameterized algorithms, the dual class functions are piecewise structured in the following sense [BDD*21].
Definition 1 (Piecewise structured with linear boundaries). A function class H C RP that maps domain P C TRd to R is (F, -ipeeecees decomposable for a class F. C R² of piece functions if the following holds: for every h H. there are linear threshold functions 91.-.. 9t P + {0, 1], Le. ge(x)) = [[aa x + bi) and piece function fo E F for each bit vector b E {0, 13' such that for all y E h(y) (b) where by (g1 (v) ..... (e())) {0, 13.
*One should carefully distinguish the parameterized clustering algorithm from the ERM-based learning algorithu which learns a parameter from this family given problem instances. Our algorithmic approaches focus on implementing the ERM efficiently.
3

---

We will refer to connected subsets of the parameter space where the dual class function is fixed piece function fo as the (dual) pieces or regions, when the dual class function is clear from the context. Past work [BVV18] defines similar definition for mechanism classes called (d, t)-delineable classes which are a special case of Definition]] [ where the piece function class F consists of linear functions, and focus on sample complexity of learning, i.e. the number of problem instances from the problem distribution that are sufficient learn near-optimal parameters with high confidence over the draw of the sample. Our technigues apply for larger class, where F is a class of convex functions. Past work [BSV18 BDL20 BDD provides sample complexity guarantees for problems that satisfy Definition D on the other hand we will focus developing fast algorithmss. We develop techniques that yield efficient algorithms for computing these pieces in the multiparameter setting, i.e. constant d > The running times of our algorithms are polynomial in the output size (i.e, number of pieces). For E zt, we will use []] to denote the set of positive integers (1...., .}.
2 Output-sensitive cell enumeration and data-driven algorithm design
Suppose H is a collection of t hyperplanes in Rd. We consider the problem of enumerating the d-faces (henceforth cells) of the convex polyhedral regions induced by the hyperplanes. The enumerated cells [6] of facet-inducing hyperplanes. We will present an approach for enumerating these cells OFPT time (Output-sensitive Fixed Parameter Tractable) Definition 3). which involves two key ingredients: (a) locality-sensitivtty, and (b) output-sensitivtty By locality sensitivity, we mean that our algorithm exploits cooblem-specifee local structure in the neighborhood of each cell to work with smaller candidate set of hyperplanes which can potentially constitute the cell facets. This is abstracted out as a sub-routine COMPUTELOCALLY RELEVANT SEAANTSEEARRRRRS which we will instantiate and analyse for each individual problem. In this section we will focus more on the output sensitivnn aspect.
will be represented as sign-pateer&
To provide an output-sensitive guarantee for this enumeration problem, we compute only the non-redundant hyperplanes which provide the boundary of each cell e in the partition induced by the hyperplanes. We denote the closed polytope bounding cell by Pe. A crucial ingredient for ensuring good outuut-sensitive runtime of our algorithm is Clarkson's 'ss algorithm for computing non-redundant constraints in a system of linear inequalities [Cla94]. A constraint is redundant in a system if removing it does not change the set of solutions. The key idea is to maintain a set I of non-redundant constraints detected so far, and solve LPs that detect the redundancy of remaining constraint (not in Z) when added to I. If the constraint is redundant relative to I, it must also be redundant in the full system, otherwise we can add (potentially different) non-redundant constraint to (see Appendix for details). The following runtime guarantee is known for the algorithm.
Theorem 2.1 (Clarkson's 's algorithm). Given a list L of k half-space constraints in d dimensions, Clarkson's 's algorithm outputs the set S L of non-redundant constraints in L in time O(k-LP |4| 1)), where LP(u, c) is the time for solving an LP with v variables and c constraints.
Algorithm T uses AUGMENTEDCLARKSE
which modifies Clarkson's 's algorithm with some ad- ditional bookkeeping (details in Appendix D to facilitate a search for neighboring regions in our algorithm, while retaining the same asymptotic runtime complexity. Effectively, our algorithm be seen as a breadth- -hrast search over an implicit underlying graph (Definition P). where the neighbors (and some auxiliary useful information) are computed dynamically by AUGMENTEDCLARKSSS
Definition 2 (Cell adjacency graph). Define the cell adjacency graph for a set H of hyperplanes in Rd, written Gh = (VH, EH), as:
There is a veriex e E Vn for each cell in the partition Č Th. induced by the hyperplanes; For u, d' E VVH, add the edge (u.o'} to Eh if the corresponding polytopes intersect, i.e. P.n.P This generalizes to a subdivision ( (Definition 6 of polytope in TR.d.
This allows to state the following guarantee about the runtime of Algorithm T In the notation of Table I
we have R = Vval and |E = O(
Theorem 2.2. Let be a set of hyperplanes in Rdd. Suppose that |EH| = E and VH = V in the cell adjacency graph GH (VH1 En) of H; then the domain P is bounded by Pl < hyperplanes,
'For simplicity we will denote these by vectors of the form {0, 1, -13* where non-zero co- co-ordinates corre- spond to signs of facet-inducing hyperplanes. Hash tables would be practical data structure for implementation.

---

Algorithm 1: I:
1: Input: Set H = (a; x by heje of hyperplanes in R convex polytopic domain P C Rd
given by set of hyperplanes P, procedure
H!) with x E Rd.
Output: Partition cells Ć } clt) {0, -13 with |o iff X b, is
bounding hyperplane for cell j. and (e)) = sign(a: b,) for interior point Xj. sign(-) E {=1}.
2: 4 arbitrary point in 12 (assumed general position w.r.t H)
3: Cell c(!) with sign(c.") sign(a; X1 11-10 by)
4: q + empty queue; q.enqueue ((c()) x1])
5: - (j:++ + (
6: while q.non) do
7:
[c.x] x (.ddqquuee
8: Continue to next iteration if E C
9:
C Ccf
10:
H + COOUOUULLLCCLLLLLLLLASSSRRRRROOT
H);
/* subset of
hyperplanes in H that can be facets for cell containing x */
11:
H' - ((-ssgn(c));; -igg(())),, a; x b, E H}UP
12:
neighbor)) f AUGMENTEDDLAAKSSNXX. Hc);;
/* Algorithn 2 */
Cu
14:
q.eqqeee
(c', x')) for each [c'x') E neighbors
15:
return C
Algorithm computes the set VH in time Ô + VT + l1ss Enev, LP(d, Mcl + +1), where LP s) denotes the time to solve an LP in variables and constraints, Le denotes the number of facets for cell E VH. TeLRS denotes the running time of COMPUTELOCALLY REEEALLYREEVVANSSPPPR.. TORS and tlus denotes an upper bound on the number of locally relevant hyperplanes in Line 10
We illustrate the significance of output-sensitivity and Docality-sensiiiivg in our results with examples.
The worst-case size of VH is ((t)) and standard (output-insee insenstive) enumeration algorithms for computing VH (e.g. (EG86 Xu20j) take O(t)) time even when the output size may be much smaller. For example, if H is collection of parallel planes in R3, the running time of these approaches is O(t²). Even a naive implementation of COMPUTELOCALLY RELEAALTEEREEEEEEEEEEEEEEEE ATORS which always outputs the complete set H gives better runtime of O(t²). ). By employing
Example 1.
straightforward algorithm which binary searches the closest hyperplanes to x (in a pre-processed
we have tLRS O()) and TELRS = Ô()), and Algorithm attains a running time of Ôtt) Analogously, if H a collection of hyperplanes R with S distinct unit normal vectors, then to O (th+1),, and locality-sensitivie can be used to further improve it to Ö(tt).
H) ) as RAA.UTLLLLLAALLLLLLLAAAAAAAASSS
improves the runtime from O (
ERM in the statistical learning setting. We now use Algorithm to compute the sample mimimum (aka ERM, Empirical Risk Minimization) for the (F, piecewise-strruetuee dual losses with linear boundaries (Definition I over a problem sample S E T provided piece functions in J. can be efficiently optimized over polytope (typically the piece functions are constant or linear functions in our examples). Formally, we define search-ERM, for a given parameterized algorithm family A with parameter space P and the dual class utility function being (F, -ipeeeeee decomposable (Definition MT as follows: given set of m problem instances S E II compute the pieces, i.e. partition of the parameter space into connected subsets such that the utility function is a fixed piece function in F over each subset for each of the problem instances. The following result gives recipe for efficiently solving search-ERM problem provided we can efficiently compute the dual function pieces in individual problem instances, and the the number of pieces in the sum dual class function over the sample not too large. The key idea is to apply Algorithm for each problem instance, and once again for the search-ERo problem. In the notation of Table we have Ry \Vsl.
5

---

the number of vertices in the cell adjacency graph corresponding to the polytopic pieces in the sum utility function _i=1 U,
|Es = ((s,)) when d and O for general d.
Theorem 2.3. Let Ö₁ denote the cells partitioning the polytopic parameter space P C. Rd corre- sponding to pieces of the dual class utility function u; on a single problem instance z4 E II, from a collection (I1,...,IIm. of m problem instances. Let (Vs, Es) be the cell adjacency graph corresponding to the polytopic pieces in the sum utility function -i=1 Ug Then there is an algorithm for computing Vs given the cells C₁ in time O(d++ m)) [Es) mttas. Eneve LP(d, Lel del+11 1)), where Le denotes the number facets for cell c E Vg, and t is the number of locally relevant hyperplanes in single instance.
An important consequence of the above result is an efficient output-sensitive algorithm for data-driven algorithm design when the dual class utility function is (F, -f.eceeeeeesse decomposable. In the following sections, we will instantiate the above results for various data-driven parameter selection problems where the dual class functions are
with linear boundaries (Definition] I] Prior work [BSV 18 BDL20 BDD 21] has shown polynomial bounds the sample complexity of learning near-optimal parameters via the ERM algorithm for these problems in the statistical learning setting, i.e. the problem instances are drawn from fixed unknown distribution. In other words, ERM over polynomially large sample size m is sufficient for learning good parameters. In particular, we will design and analyze running time for opeeef-- algorithms for computing locally relevant hyperplanes. Given Theorem 2.3) it will be sufficient to give an algorithm for computing the pieces of the dual class function for a single problem instance.
Remark 1. Our results in this section directly imply efficient algorithms for pricing problems in mechanism design which are known to be (F, (F.t)-decompl deecomooppeele where F is the class of linear functions (summarized in Table see Appendix Foor details).
3 Linkage-based clustering
Clustering data into groups of similar points is fundamental tool in data analysis and unsupervised machine learning. A variety of clustering algorithms have been introduced and studied but it is not clear which algorithms will work best specific tasks. Also the quality of clustering is heavily dependent on the distance metric used to compare data points. Interpolating multiple metrics and clustering heuristics can result in significantly better clustering (BDL,20).
Problem setup. Let X' be the data domain. A clustering instance from the domain consists of point set S = {- Fn S X' and an (unknown) target clustering C (Ci...., C.). where the sets Ci...., Cs partition S into & clusters. Linkage-based clustering algorithms output a hicrarchical clustering of the input data, represented by cluster tree. We measure the agreement of a cluster tree T with the target clustering in terms of the Hamming distance between and the closest pruning of T that partitions it into le clusters (i.e., k disjoint subtrees that contain all the leaves of T). More formally, the loss ((T, C)- minp!.....PP Ps min 1 Σ IC Po where the first minimum is over all prunings Pi,.... permutations of the k cluster indices.
; P& of the cluster tree into k subtrees, and the second minimum is over all
merge function D defines the distance between a pair of clusters C2, C, S X in terms of the pairwise point distances given by a metric d. Cluster pairs with smallest values of the merge function are merged first. For example, single linkage uses the merge function (C,, C d) = min d(a, b) and complete linkage uses Dempi (Ci, Cj; d) = Ceb d(a, b). Instead of using extreme points to measure the distance between pairs of clusters, one may also use more cen- tral points, e.g. we define median linkage as Dmea Cj; d) med andian(( an( b) E C., C2}), where mndian(.) is the usual statistical median of an ordered set S C 1 Appendix H provides synthetic clustering instances where one of single, complete or median linkage leads to significantly better clustering than the other two, illustrating the need to learn an interpolated procedure. Single,
(S)) is the smallest element of S such that S has at most half its elements less than me) and most half its elements more than median(S). For comparison, the more well- known average linkage is (wp(C., Cý; d) = mean((d(a, b) I a E C., E C₁}). We may also use geometric medians of clusters. For example, we can define mediod linkage as Dgomes(C,, C,;d) di d(argmingec; Eaeec d(a, a²), argmingec, Evec, d(b,6')).

---

median and complete linkage are 2-point-based (Definition 4 Appendix M. i.e. the merge function D(A, B; d) only depends on the distance d(a, b) for two points (a,b) A B.
Parameterized algorithm families. Let A = (Di...., D denote a finite family of merge func- tions (measure distances between clusters) and 5 = (d1,.... dm) } be finite collection of distance metrics (measure distances between points). We define parameterized family of linkage-based clustering algorithms that allows us to learn both the merge function and the distance metric. It is given by the interpolated merge function D (A, 6) = LDE (i,, B; dj), where [0,] [m]. Ci.j 2 0}. In order ensure linear boundary functions for the dual class function, our interpolated merge function (A, B; takes all pairs of distance metrics and linkage procedures. Due to invariance under constant multiplicative factors, we can set Σ, 0z.j = 1 and obtain set of parameters which allows to be parameterized by d = Im- 1 values Define the parameter space P = d = P E (R220) E. 5 $1}; for any p E P we get (P E IRd+1 as a (p) = Pj for E [d].
a= {
az = 1 - -ieea Pi. We focus on learning the optimal p E P for a single instance ()) With slight abuse of notation we will sometimes use D2, B; to denote the interpolated merge function D (A, B: 6) As special case we have the family DA B; do) that interpolates merge functions (from set A) for different linkage procedures but the same distance metric dg. Another interesting family only interpolates the distance metrics, i.c. use a distance metric dp(a, b) = Ed,es 0 d, (a, b) and use a fixed linkage procedure. We denote this by D2, B;
(P)
We will extend the execution tree approach introduced by (BDL200 which computes the pieces (intervals) of Singlepparmmete and how is extended to the multi-parameter setting, deferred to Appendix I.]] Informally, for a single parameter, the execution tree is defined as the partition tree where each node represents an interval where the first t merges are identical, and edges correspond to the subset relationship between intervals obtained by refinement from a single merge. The execution, i.e. the sequence of merges, unique along any path of this tree. The same properties, i.e. refinement of the partition with each merge and correspondence to the algorithm's execution, continue to hold in the multidimensional case, but with convex polytopes instead of intervals (see Definition 5 Computing the children of any node of the execution tree corresponds to computing the subdivision of convex polytope into polytopic cells where the next merge step is fixed. The children of any node of the execution tree can be computed using Algorithm | We compute the cells by following the neighbors, keeping track of the cluster pairs merged for the computed cells to avoid recomputation. For any single cell, we find the bounding polytope along with cluster pairs corresponding to neighboring cells by computing the tight constraints in a system of linear inequalities. Theorem 2.2 gives the runtime complexity of the proposed algorithm for computing the children of any node of the execution tree. It only A
linkage-based clustering. A formal treatment of the execution tree,
remains to specify
For a given x = p we find the next merge candidate in time O(dn² )) by computing the merge function D2 (A, B:8) for all pairs of candidate (unmerged) clusters A, B. If (A*, B²)) minimizes the merge function, the locally relevant hyperplanes are given by D (A",
",","";11 B²; 5) I D (A', B'; 5) for (A'BB) * (A", B²) i.e. fLRS S n². Using Theorem 2.2] we give the following bound for the overall runtime of the algorithm (soft-O notation suppresses logarithmic terms and multiplicative constants in d, proof in Appendix 1.2p.
Theorem 3.1. Let S be clustering instance with |S| n, and let R3 IP:l and R Rn- Let H, = [[(21, HI=I((Q,, 22) E p? 21 i Q2 # 03 denote the total number of adjacencies between any two P,
pieces P, and H = Hn, Then, the leaves of the execution tree on S can be computed time (EL,, + R,TM)) (n - i 1)²), where TM is the time to compute the merge function.
In the case of single, median, and complete linkage, we may assume TM = =(d) by carefully maintaining a hashtable containing distances between every pair of clusters. Each merge requires
overhead at most Onn)), n, n t being the number of unmerged clusters at the node at depth t, which is absorbed by the cost of solving the LP corresponding to the cell of the merge. We have the following corollary which states that our algorithm is output-lineal for d = 2.
Corollary 3.2. For d = 2 the leaves of the execution tree of any clustering instance S with |S| n can be computed in time an"")
Above results yield bounds on T'. the enumeration time for dual function of the pieces in a single problem instance Theorem (00oremm.33frr further implies bounds on the runtime of ERM [T.
In contrast, the parametric family in (BDL20) has + m parameters but it does not satisty Definition| 1
7

---

4 Dynamic Programming based sequence alignment
Sequence alignment is a fundamental combinatorial problem with applications computational biology. For example, to compare two DNA, RNA or amino acid sequences the standard approach to align two sequences to detect similar regions and compute the optimal alignment [NW70, Wat89 CBOO]. However, the optimal alignment depends on the relative costs or weights used for specific substitutions, insertions/deletions, or gaps (consecutive deletions) in the sequences. Given a set of weights, the optimal alignment computation is typically a simple dynamic program. Our goal is to learn the weights, such that the alignment produced by the dynamic program has application-specffie desirable properties.
Problem setup. Given a pair of sequences $1, $2 over some alphabet Σ of lengths m = |s and n = |s2], and a 'space' character - & E, a space-extension of a sequence over Σ is a sequence over Σ U {-} such that removing all occurrences of in gives s. A global alignment (or simply alignment) of $1; 82 is a pair of sequences 4,, l2 such that |t = |/2). (1, 12 are space- extensions of 81,82 respectively, and for no 1 S i S [t, we have h = (2 -. Let s(i] denote the i-th character of sequence and s|: i] denote the first i characters of sequence 8. For 1 < i S [4,/. if [i] = t2 we call it a match. If [ + t2[i], and one of [ or [2[i] is the character
we call it space, else it is a mismatch. A sequence of characters (in i or (2) is called gap. Matches, mismatches, gaps and spaces are commonly used features of an alignment, i.e. functions that map sequences and their alignments (81, 82; (2,42) to Zoo (for example, the number of spaces). A common measure of cost of an alignment is some linear combination of features. For example if there are d features given by (x(.), k [d], the cost may be given by c(s1, 82, f1. f22 p)
Ei=1 Pk14 82, &1, t2) where p = (pi...., Pa) are the parameters that govern the relative weight of the features [KKO6]. Let T(s, s' p) = argmin,, .22 c(s, s', ,t,,,tt P) and ((s,s',p) = min c(s, s', 11, 12, p) denote the optimal alignment and its cost respectively.
A general DP update rule. For a fixed p. suppose the sequence alignment problem can be solved, i.c. we can find the alignment with the smallest cost, using dynamic program A, with linear parameter dependence (described below). Our main application will be to the family of dynamic programs Ap which compute the optimal alignment 7 7(81, 82, P) given any pair of sequences ($1,82) 82) E Σm x Σ" = II for any & E Rd but we will proceed to provide more general abstraction. See Section D.T for example DPs using well-known features in computational biology. expressed using the abstraction below. For any problem (81,82) E II, the dynamic program A, (p E P C Rd, the P [ Ps = (2),82)} of l subproblems (typically, r (811,22 S IT =2 = {(1 (: ('), 82) 5'): 1
set of parameters) solves set T (81, 82) = = [P:
m...... E (O...., ]] S IT) in some fixed order Pi...., Pk (#1. 82). Crucially, the subproblems sequence Pi,..., Px do not depend on A In particular, a problem P, can be efficiently solved given optimal alignments and their costs (T)(P), C(())) for problems P. for each i E -1. Some initial problems in the sequence Pi...., Ps of subproblems are base case subproblems where the optimal alignment and its cost can be directly computed without referring to a previous subproblem. To solve a (non base case) subproblem P,. consider V alternative cases q II + [V], i.. P, belongs to exactly one of the V cases (e.g. if Pj = [s1 ['"] s2(:5"]). we could have two cases corresponding to $1 [2] = s2[3"] and s s1 * s2l)'). Typically, V will be small constant. For any case v ((3)) E [V] that Pj may belong to, the cost of the optimal alignment of P, is given by a minimum over L., terms of the form cp.1 Pj) =
p. We, + oe, (p, P3), where I E [Lr]. We.1 E RRd 0p P.) = Cp(p) E (p)( C,-1 is the cost of some previously solved subproblem P.- (s1[=t]).x[[:>]))
(s1 s2 (i.e. I depends on v, L,j but not on p). and (p P3) is the cost of alignment (p, P,) (T) which extends the optimal alignment for subproblem P. by a p-independent transformation T T.)(.). That is, the DP update for computing the cost of the optimal alignment takes the form
DP(p. min(f Wa(P))) + Co(P)) PD)..
and the optimal alignment is given by (p, = (p, Py), where /' argming(p "g(P))++ + a P,)). The DP specification is completed by including base cases (C(s, - p. Wa.s' 6') E B(si, }2)} (or (T(s, s',p) = Ts.s' (s, s') E B(si, }2)} for the
we have (811 = leny. and we first solve the base case subproblems (which have fixed optimal aligmment for all p) followed by problems (s1 [:'), s2 in non-decreasing order of i j' for any value of
"For the sequence alignment DP in Appendix 1.1.1
8

---

optimal alignment DP) corresponding to a set of base case subproblems ((s1,52) S II .e. Let maX Lg denote the maximum number of subproblems needed compute a single DP update in any of the cases. T. is often small, typically 2 or 3 (see examples in Section I.I. Our main result is to provide an algorithm for computing the polytopic pieces of the dual class functions efficiently for small constants d and T..
As indicated above, we consider the family of dynamic programs Ap which compute the optimal alignment 82;
82; p) given any pair of sequences (81, 82) ETH x Σ" = III for any p IRd. For any alignment (41, 42), the algorithm has a fixed real-valued utility (different from the cost function above) which captures the quality of the alignment, i.e. the utility function u((s). $2), p) only depends on the alignment 7 (s1. 92. p). The dual class function is piecewise constant with convex polytopic pieces (Lemma [.5 in Appendix p.3). For any fixed problem ($1, 52). the space of parameters p can be parti- tioned into R convex polytopic regions where the optimal alignment is fixed. The optimal parameter can then be found by simply comparing the costs of the alignments in each of these pieces. For the rest of this section we consider the algorithmic problem of computing these R pieces efficiently.
For the clustering algorithm family, as we have seen in Section 3 we get refinement of the parameter space with each new step (merge) performed by the algorithm. This does not hold for the sequence alignment problem. Instead we obtain the following DAG, from which the desired pieces can be obtained by looking at nodes with no out-edges (call these terminal nodes). Intuitively. the DAG built by iteratively adding nodes corresponding to subproblems PI...., P's and adding edges directed towards P, from all subproblems that appear in the DP update for it. That is, for base case subproblems, we have singleton nodes with no incoming edges. Using the recurrence relation ( we note that the optimal alignment for the pair of sequences (s1 [s) s2 jl) can be obtained from the where r' q(s1[te], [:d]],s s21::]) (:j]). The DAG for (s1 [: s2(: is therefore simply obtained by using the DAGs G , for the subproblems and adding directed edges from the terminal nodes of G to new nodes up,i, corresponding to each A more compact representation of the execution graph would have only single node tijj for each subproblem [s][: $2 (:))) (the node stores the corresponding partition P)i][) and edges directed towards Uz,j from nodes of subproblems used to solve $2(::)) Note that the graph depends on the problem instance (81, 82) as the relevant DP cases = q(<i [:i]] sp]: depend on the sequences 81, 82. A naive way to encode the execution graph would be an exponentially large tree corresponding to the recursion tree of the recurrence relation (
optimal alignments for subproblems {(s [: &er .I]. S2 (er,)))))rrr..>.....
piece p of the partition Piili]] of given by the set of pieces of Uss (s11)).111)) (s).s=(())
Execution DAG. Formally we define a compact execution graph Ge = (Ve, Ee) as follows. For the base cases, we have nodes labeled by (s, s') B(s), s2) storing the base case solutions (Wa,s': T over the unpartitioned parameter space p RR For i > O, we have a node v.j labeled by [s1[:d]. s2[: [:]) and the corresponding partition Pi of the parameter space, with incoming edges from nodes of the relevant subproblems {<1 ēo' .]. s2l:
where e' = [s1][:]]. s2l::]).
This graph is DAG since every directed edge is from some node Uz,y to node "y with i' j" >> i+j
in typical sequence alignment dynamic programs (Appendixp.Il p.Ip. Algorithm 5 (Appendix (.2) gives
procedure to compute the partition of the parameter space for any given problem instance ($1, 52) us-
ing the compact execution DAG. We give intuitive overviews of the three main routines in Algorithm D
computes overlay PP of the input polytopic subdivisions (P, | E S.} and uses Clarkson's 's algorithm for intersecting polytopes with output-sensitiv efficiency. We show that the overlay can be computed by solving at most R' linear programs (Algorithm 6 Lemma I.1] COMPUTESUBDI DIVSSONDD applies Algorithm [ in each piece of the overlay we need find the polytopic subdivision induced by O(L") hyperplanes (the set of hyperplanes depends on the piece). This works because all relevant subproblems have the same solution within any piece of the overlay. merges pieces where the optimal alignment is identical using a simple search over the resulting subdivision.
COMPUTEOVERLAYE
Finally RESOLVEDEGENER
For our implementation of the subroutines, we have the following guarantee for Algorithm
Theorem 4.1. Let Ri, denote the number of pieces in P(i][),, and R maxi<m.ján Rs.j- Ife time complexity for computing the optimal alignment is ((TP)), then Algorithm 5ean be used to compute the pieces for the dual class function for any problem instance ($1, in time Odd.L 4d
1 p21++ 'T
For the special case of d = 2, we show that (Theorem I.6. Appendix J.3 the pieces may be computed in O (RTbb) time using the ray search technique of MMg778

---

Acknowledgments
We thank Dan DeBlasio for useful discussions on the computational biology literature. We also thank Avrim Blum and Mikhail Khodak for helpful feedback. This material is based work supported by the National Science Foundation under grants CCF-1910321, IIS- 1901403, and SES-1919453, the Defense Advanced Research Projects Agency under cooperative agreement HR001 12020003; a Simons Investigator Award; an AWS Machine Learning Research Award; an Amazon Research Award; Bloomberg Research Grant; Microsoft Research Faculty Fellowship.
References
[AF96] David Avis and Komei Fukuda. Reverse search for enumeration. Discrete applied mathematics, 65(1-3):21-44 1996.
[Bal20] Maria-Florina Balcan. Data-Driven Algorithm Design. In Tim Roughgarden, editor, Beyond Worst Case Analysis of Algorithms. Cambridge University Press, 2020.
[BB24] Maria-Florina Balcan and Hedyeh Beyhaghi. Learning revenue maximizing menus of lotteries and two-part tariffs. Transactions on Machine Learning Research (TMLR), 2024.
[BBSZ23] Maria-Florina Balcan, Avrim Blum, Dravyansh Sharma, and Hongyang Zhang, An analysis robustness of non-lipschitz networks. Journal of Machine Learning Research (JMLR), 24(98):1 2023.
[BDD+21] Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient learn high-performing algorithms? Generalization guarantees for data-driven algorithm design. In Symposium on Theory of Computing (STOC), pages 919-932, 2021.
[BDL20] Maria-Florina Balcan, Travis Dick, and Manuel Lang. Learning to link. In International Conference on Learning Representations (ICLR), 2020.
[BDS20] Maria-Florina Balcan, Travis Dick, and Dravyansh Sharma. Learning piecewise Lip- schitz functions in changing environments. In International Conference on Artificial Intelligence and Statistics, pages 3567-3577. PMLR, 2020.
[BDS21] Avrim Blum, Chen Dan, and Saeed Seddighin. Learning complexity of simulated an- nealing. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1540-1548. PMLR. 2021.
[BDSV18] Maria-Floo Frorina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning branch. In International Conference on Machine Learning (ICML), pages 344-353. PMLR, 2018.
[BDV18] Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 603-614. IEEE, 2018.
[BFM97] David Bremner, Komei Fukuda, and Ambros Marzetta. Primal-dual methods for vertex and facet enumeration (preliminary version). In Symposium on Computational Geometry (SoCG), pages 49-56, 1997.
[BWW22] Peter Bartlett, Piotr Indyk, and Tal Wagner. Generalization bounds for data-driven numerical linear algebra. In Conference on Learning Theory (COLT), pages 2013-2040. PMLR, 2022.
[BKST22] Maria-Florina Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar. Provably tuning the FlasticNet across instances. Advances in Neural Information Processing Systems, 35:27769-27782. 2022.
10

---

[BNWW17] Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning- theoretic foundations of algorithm configuration for combinatorial partitioning problems. In Conference on Learning Theory (COLTT) pages 213-274. PMLR, 2017.
[BPS20] Maria-Florina Balean, Siddharth Prasad, and Tuomas Sandholm. Efficient algorithms for learning revenue- revenue-maxinin maximizing two-par -oo-part tariffs, In International Joint Conferences on Artificial Intelligence (IJCAI), pages 332-338, 2020.
[BS21] Maria-Florina Balcan and Dravyansh Sharma. Data driven semi-supervised learning. Advances in Neural Information Processing Systems, 34, 2021.
[SV16] Maria-Floring Balcan, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of automated mechanism design. Advances in Neural Information Processing Systems, 29,
2016.
[BSV18] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. A general theory of sample complexity for multi-item profit maximization. Economics and Computation (EC), pages 173-174, 2018.
[Buc43] Robert Creighton Buck. Partition of space. The American Mathematical Monthly, 50(9):541-544, 1943.
[CAK17] Vincent Cohen-Addad and Varun Kanade. Online optimization of smoothed piecewise constant functions. In Artificial Intelligence and Statistics, pages 412-420. PMLR, 2017.
[CB00] Peter Clote and Rolf Backofen. Computational Molecular Biology: An Introduction. John Wiley Chichester; New York, 2000.
[CE92] Bernard Chazelle and Herbert Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. Journal of the ACM (JACM), 39(1):1-54, 1992.
[Cha96] Timothy M Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry, 16(4):361-368 1996.
[Cha18] Timothy M Chan. Improved deterministic algorithms for linear programming low dimensions. ACM Transactions on Algorithums (TALG), 1433)1-10,, 2018.
[Cla94] Kenneth L Clarkson. More output-sensitive geometric algorithms. In Symposium on Foundations of Computer Science (FOCS), pages 695-702. IEEE, 1994.
[DF12] Rodney G Downey and Michael Ralph Fellows. Parameterized complexity. Springer Science & Business Media, 2012.
[EG86]
Herbert Edelsbrunner and Leonidas J Guibas. Topologically sweeping arrangement. In Symposium on Theory of Computing (STOC), pages 389-403, 1986.
[Fer02]
Henning Fernau. On parameterized enumeration. In International Computing and Combinatorics Conference, pages 564-573. Springer, 2002.
[FGS+ + 19] Henning Fernau, Petr Golovach, Marie-France Sagot, et al. Algorithmic enumera- tion: Output-sensitive, input-sensitive, parameterized, approximative (Dagstuhl Seminar 18421). In Dagstuhl Reports, volume 8. Schloss matik, 2019.
fuer Infor-
[GBN94] Dan Gusfield, Krishnan Balasubramanian, and Dalit Naor. Parametric optimization of sequence alignment. Algorithmica, 12(4):3123326, 1994.
[GR16] Rishi Gupta and Tim Roughgarden. PAC approach to application-specffi algorithm selection. In Innovations 1 Theoretical Computer Science Conference (ITCS), 2016.
[GR20) Rishi Gupta and Tim Roughgarden. Data-driven algorithm design. Communications of the ACM, 63(6),87-94, 2020.

---

[GS96] Dan Gusfield and Paul Stelling, Parametric and inverse-pait parametric sequence alignment with XPARAL. Methods in Enzymology, 266:481-499 1494, 1996.
[KK06] John Kececioglu and Eagu Kim. Simple and fast inverse alignment. In Annual Interna- tional Conference on Research in Computational Molecular Biology, pages 441-455. Springer, 2006.
[KKW10] John Kececioglu, Eagu Kim, and Travis Wheeler, Aligning protein sequences with predicted secondary structure. Journal of Computational Biology, 17(3):511-580, 2010.
[1] Krishnan Kumaran, Dimitri Papageorgiou, Martin Takac, Laurens Lueg, and Nicolas Sahinidis. Active metric learning for supervised classification. Computers & Chemical Engineering, 10713,, 2021.
[Lew41] W Arthur Lewis. The two-part tariff. Economica, 8(31):249-22) 270, 1941.
[Meg78] Nimrod Megiddo. Combinatorial optimization with rational objective functions. In Symposium on Theory of Computing (STOC), pages 1-12, 1978.
[MR15] Jamie Morgenstern and Tim Roughgarden. On the pseudo dimension of nearly optimal auctions. Advances in Neural Information Processing Systems, 28, 2015.
[Nak04] Shin-ichi Nakano. Efficient generation of triconnected plane triangulations. Computa- tional Geometry, (7(2):109-122) 2004.
[NW70] Saul B Needleman and Christian D Wunsch. A general method applicable the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3):443-453 1970.
[Oi71] Walter Y Oi. A Disneyland dilemma: Two-part tariffs for a Mickey Mouse monopoly. The Quarterly Journal of Economics, 85(1):77-96, 1971.
[RC18] Miroslav Rada and Michal Cerny. A new algorithm for enumeration of cells of hyper- plane arrangements and a comparison with Avis and Fukuda's 's reverse search. SIAM Journal on Discrete Mathematics, 32( (2(1):4554433 2018.
[SC11] Shiliang Sun and Qiaona Chen. Hierarchical distance metric learning for large mar- gin nearest neighbor classification. International Journal of Pattern Recognition and Artificial Intelligence (IJPRAI), 25:1073-1087, 11 2011.
[Sei91] Raimund Seidel. lmall-dimensione linear programming and convex hulls made easy. Discrete & Computational Geometry, 6:423-434, 1991.
[SJ23] Dravyansh Sharma and Maxwell Jones. Efficiently learning the graph for semi- supervised learning. The Conference on Uncertainty in Artificial Intelligence (UAI), 2023.
[SIc99] Nora Sleumer. Output-sensitive cell enumeration in hyperplane arrangements, Nordic Journal of Computing. 6(2):137-147, 1999.
[Syr17] Vasilis Syrgkanis. sample complexity measure with applications to learning optimal auctions. Advances in Neural Information Processing Systems, 30. 2017.
[Wat89] Michael S Waterman. Mathematical methods for DNA sequences. Boca Raton, FL (USA); CRC Press Inc., 1989.
[WS09] Kilian Q Weinberger and Lawrence K Saul. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research (JMLR), 10(2), 2009.
[Xu20] Haifeng Xu. On the tractability of public persuasion with no externalities. In Symposium on Discrete Algorithms (SODA), pages 2708-2727. SIAM, 2020.
12

---

A Additional insights and challenges
We first present an algorithm for enumerating the cells induced by a finite collection of hyperplanes in Rd in output-sensitive time. Our approach is based on output-sensitive algorithm for determining the non-redundant constraints a linear system due to Clarkson [Cla94]. At any point, we compute the locally relevant hyperplanes that constitute the candidate hyperplanes which could bound the cell (or piece) containing that point, using a croblem-specifit sub-routine, and apply Clarkson's 's algorithm over these to determine the facet- facet-inducing hyperplanes for the cell as well as collection of points in neighboring cells. This allows us to compute all the induced cells by traversing an implicit cell adjacency graph (Definition 2 in breadth-first order. Our approach gives recipe for computing the pieces of piecewise structured dual class functions with linear boundaries, which can be used to find the best parameters over a single problem instance. We further show how to compute the pieces of the sum dual class function for collection of problem instances in output-sensitive time, by applying our approach to the collection of facet-inducing hyperplanes from each problem instance. Our approach is useful for several mechanism design problems which are known to be piecewise structured [BSV18), and we instantiate our results for two-part tariff pricing and item pricing with anonymous prices. For the single menu two-part tariff case (d = 2), we use additional structure of the dual class function to give further improvement in the running time.
For linkage-based clustering, we extend the execution tree based approach of [DL220 for single- parameter families d > 1. The key idea is that linkage-baset clustering algorithms involve sequence of steps (called merges), and the algorithmic decision at any step can only refine the partition of the parameter space corresponding to a fixed sequence of steps so far. Thus, the pieces can be viewed as leaves of a tree whose nodes at depth i correspond to a partition of the parameter space such that the first steps of the algorithm are identical in each piece of the partition. While in the single parameter family the pieces are intervals, we approach the significantly harder challenge of efficiently computing convex polytopic subdivisions (formally Definition 6). We essentially compute the execution tree top-down for any given problem instance, and use our hyperplane cell enumeration to compute the children nodes for any node of the tree.
We further extend the execution tree approach to a problem where all the algorithmic states corre- sponding to different parameter values cannot be concisely represented via a tree. For dynamic- programming based sequence alignment, we define a compact representation of the execution graph and use primitives from computational geometry, in particular for overlaying two convex subdivisions in output-polynomial time. A key challenge in this problem is that the execution graph is no longer a tree but DAG, and we need to design an efficient representation for this DAG. We cannot directly apply Clarkson's 's algorithm since the number of possible alignments of two strings (and therefore the number of candidate hyperplanes) is exponential in the size of the strings. Instead, we carefully combine the polytopes of subproblems in accordance with the dynamic program update for solving the sequence alignment (for a fixed value of parameters). and the number of candidate hyperplanes is output-sensitive inside regions where all the relevant subproblems have fixed optimal alignments.
B Additional related work
Data-driven algorithm design. The framework for data-driven design was introduced by [GR16] and surveyed in [Bal20). It allows the design of algorithms with powerful formal guarantees when used repeatedly on inputs consisting of related problem instances, as opposed to designing and analyzing for worst-case instances. Data-driven algorithms have been proposed and analyzed for a wide variety of combinatorial problems, including clustering [BDL220, computational biology [BDD+21], mechanism design [BSV18], mixed integer lincar programming [BDSV18), cuni-supervieed learning [B22 SI23), linear regression [BKST22), low-rank approximation (BIW22 and adversarially robust learning [BBSZ23. Typically these are Na-hard problems with a variety of known heuristics. Data-driven design provides techniques to select the heuristic (from a collection parameterized family) which is best suited for data coming from some domain. Tools for data-driven design have also been studied in the online learning setting where problems arrive in an online sequence [CAK17 BDVI8, BDS20]. In this work, we focus on the statistical learning setting where the "related" problems are drawn from fixed but unknown distribution.
Linkage-bused clustering BNVWI7] introduce several single parameter families to interpolate well-known linkage procedures for linkage-based clustering, and study the sample complexity of
13

---

consider families with multiple parameters, and also consider the interpolation of different distance metrics. However the proposed execution-tre tree based algorithm for computing the constant-pent penftant-eerformace regions in the parameter space only applies to single-paran parameter families, and therefore the results can be used to interpolate linkage procedures or distance metries, but not both. Our work removes this limitation and provides algorithms for general nulti-parameter families.
learning the parameter. [BDL20]
Other approaches to learning a distance metric to improve the quality of clustering algorithms have been explored. For instance, [WS09] and (KPT+21] consider versions of global distance metric learning, a technique to learn a linear transformation of the input space before applying a known distance metric. [SCI1] also consider a hierarchical distance metric learning, which allows the learned distance function to depend on already-merged clusters. For such distance learning paradigms, the underlying objective function often continuous, admitting gradient descent techniques. However, in our setting. the objective function is neither convex nor continuous in p; instead, it is piecewise constant for convex pieces. As a result, instead of relying on numerical techniques for finding the optimum p. our multidimensional approach enumerates all the pieces for which the objective function constant. Furthermore, this technique determines the exact optimum p rather than an approximation; one consequence of doing so is that our analysis can be extended to apply generalization guarantees from BDL20 when learning the optimal over a family of instances.
Sequence alignment. For the problem of aligning pairs of genomic sequences, one typically obtains the best alignment using a dynamic program with some costs or weights assigned edits of different kinds, such as insertions, substitutions, or reduplications [Wat89]. Prior work has considered learning these weights by examining the cost of alignment for the possible weight settings. [BDD+21 considers the problem for how many training examples (say pairs of DNA sequences with known ancestral or evolutionary relationship) are needed to learn the best weights for good generalization on unseen examples. More closely related to our work is the line of work which proposes algorithms which compute the partition of the space of weights which result in different optimal alignments [GBN94 GS96). In this work, we propose new algorithm which computes this partition more efficiently.
Pricing problems. Data-driven algorithms have been proposed and studied for automated mech- anism design [RI5 BSV18 BDVI8]. Prior work on designing multi-dimenniooal mechanisms has focused mainly on the generalization guarantees, and include studying classes of structured mechanisms for revenue maximization [MRS BSVI6 1yr17 BSVI8). Computationally efficient algorithms have been proposed for the two-part tariff pricing problem [BPS20]. Our algorithms have output-sensitive complexity and are more efficient than [BPS20 even for worst-case outputs. Also, our techniques are more general and apply to mechanism design besides two-part tariff pricing. [B24 consider discretization-bent work in problems beyond mechanism design, for example, data-driven clustering [BNVWI7).
techniques which are not output-sensitive and known to not
On cell enumeration of hyperplane arrangements. A finite set of t hyperplanes in E. induces a collection of faces in dimensions S d, commonly referred to as an arrangement. A well-known inductive argument implies that the number of d-faces, or cells, in an arrangement of hyperplanes in Rd is at most O(t)). Several algorithms, ranging from topological sweep based (EG86) to incremental construction based [Xu20], can enumerate all the cells (typically represented by collections of facet- inducing hyperplanes) in optimal worst-case time O(Ld). The first output-sensitive algorithm proposed for this problem was the reverse search based approach of (AF96), which runs in OldR (dd ()) time, where R denotes the output-size (number of cells in the output) and LP(d, is the time for solving a linear program in d variables and constraints. This was further improved by a factor of t via more refined reverse-seard [Slc99], and by additive terms via different incremental construction based approach by [RCI8]. We propose a novel approach for cell enumeration based on Clarkson's algorithm [Cla94] for removing redundant constraints from linear systems of inequalities, which asymptotically matches the worst case output-sensitive running times of these algorithms while improving over their runtime in the presence of additional structure possessed by the typical piecewise structured (Definition T loss functions encountered in data-driven algorithm design.
14

---

C
Output-sensitive Parameterized Complexity
Output-sensitive algorithms have running time that depends the size of the output for any input problem instance. Output-sensitive analysis is frequently employed in computational geometry, for example Chan's algorithm [Cha96] computes the convex hull of a set of 2-dimensional points in time (n log R),, where R is the size of the (output) convex hull. Output-sensitive algorithms are useful if the output size is variable, and 'typical' output instances are much smaller than worst case instances. Parameterized complexity extends classical complexity theory by taking into account not only the total input length n. but also other aspects of the problem encoded in a parameter And The motivation is to confine the super-pol poper--olynomiall runtime needed for solving many natural problems strictly to the parameter. Formally, parameterized decision problem (or language) is subset L _ E" x N, where E is a fixed alphabet, i.c. an input (ar, k) to parameterized problem consists of two parts, where the second part is the parameter. A parameterized problem L. is fixed-put pard-marreeter tractable there exists an algorithm which on given input (x., k) E Σ" x N. decides whether (æ, k) E I. in f(k) poly([x))) time, where f is an arbitrary computable function in [DF12] FPT is the class of all parameterized problems which are
tractable. In contrast, the class XP (aka slicewise-polynome consists of problems for which there is an algorithm with running time |a|| (ek) It is known that FPT Ç XP. We consider an extension of the above search problems and incorporate output-sensitiviyy in the following definition.
Definition 3 (Output-polynomil Fixed Parameter Tractable). A parameterized search problem P E. x N - Σn is said be oulput-polynomall fixed-parameter tractable if there exists an algorithm which on given input (x, k) Σ' x N, computes the output P(x. k) E Σ" in time [(k) poly((<), Rt,, where R = [P(r, k)] is the output size and f is an arbitrary computable fomputaabe.functionn in k.
As discussed above, output-sensitvin and fixed- parameerreeter tractability both offer more fine-grained complexity analysis than traditional (input) polynomial time complexity. Both techniques have been employed in efficient algorithmic enumeration [Fer02] [ak04] and have gathered recent interest 19]. In this work, we consider the optimization problem of selecting tunable parameters over a continuous domain C Rd with the fixed-parameter = d, the number of tunable parameters. We will design OFPT enumeration algorithms which, roughly speaking, output finite "search space" which can be used to easily find the best parameter for the problem instance.
D Augmented Clarkson's algorithm
We describe here the details of the Augmented Clarkson's algorithm, which modifies the algorithm of Clarkson [Cla94] with additional bookkeeping needed for tracking the partition cells in Algorithm [ The underlying problem solved by Clarkson's 's algorithm may be stated as follows.
Problem Setup. Given a linear system of inequalities Ax S b, inequality A,r S b, is said to be redundant in the system if the set of solutions is unchanged when the inequality is removed from the system. Given system (A E ma b R find an equivalent system with no redundant inequalities.
Note that to test if a single inequality Air S by is redundant, it is sufficient to solve the following LP variables and m constraints.
maximize subject to
A₁x
A₁æ S bj, Vj E [m] (i)
A +1
Using this directly to solve the redundancy removal problem gives an algorithm with running time m LP(d, m), where LP m) denotes the time to solve an LP in d variables and m constraints. This can be improved using Clarkson's 's algorithm if the number of non-redundant constraints is much less than the total number of constraints m (Theorem (.1).
We assume that an interior point z E IRd satisfying Ax < b is given. At a high level, one maintains the set of non-redundant constraints I discovered so far i.c. A,z < by is not redundant for each
N.B The term "parameter" is overloaded. It is used to refer to the real-valued parameters in the algorithm family, well as the parameter to the optimization problem the algorithm family.
15

---

Algorithm 2: AUGMENTEDCLAKKSON. H ()
Input: A E Ruxd b E R", e RR sign-pattern E {0, 1, -1
Output: list of non-redundant hyperplanes [ [m], points in neighboring cells Z C R.
0. < [m].
while J * ( do
Select & E J
Detect if Agæ & by is redundant in A & DIURK by solving LP (2)
x² optimal solution of the above LP
if' redundant then
J (k)
j.** + RayShoot(A,, b, 2,);
/* Computes j such that A, by is
pacet-induciig hyperplane hit by ray from z along x² */
J J [5}
of + -g. a ViE [m] {/)
- TU + Zu ( [[c]=")]
return 1,2
i E I. When testing a new index the algorithm solves an LP of the form and either detects that AA. I by is redundant, or finds index E [m] such that A5æ I by is redundandd.n. The latter involves the use of procedure RayShoot (A, 2, 2)) which finds the non-rece non-redundant hyperplane hit by ray originating from in the direction
E (Rd) in the system A, b. The size of the LP from which the complexity follows.
needed for this test is LP
[1| []]
To implement the RayShoot procedure, the hyperplanes A,æ I by and output the one closest to (defining the cell facet in that direction). We also output interior point from the adjacent cell during this computation, which saves time relative to [Sle99] where the interior point is computed for each cell (our Clarkson based approach also circumvents their need for the Raindrop procedure [BFM97]). Finally we state the running time guarantee of Algorithm which follows from the original result of Clarkson (Cla94).
can simply find the intersections of the ray x with
Algorithm 3: RayShoot
Input: A E Rmxd b RT E RR E Rd A (x - 2) = 0 for some then
L 2 2 2 (e, ......" for sufficiently small e; /* Ensure general position. */
t b-A.2.
/* intersection of z + t(x - 2) with A&r = b, */
Ac((Z-2)
j argmin, (4 14 > 03. l' max(ming (4: 44 0}.0}
4+te (x 2)
return j,z
Theorem D.1 (Augmented Clarkson's algorithm). Given a list L of half-space constraints in d dimensions, Algorithm 2 outputs the set C [T]] of non-redundant constraints in L,, well as auxiliary neighbor information, time O(k: L. [T] + 1)), where LPP e) is the time for solving an L.P with variables and e constraints.
E Additional details and proofs from Section 2
Algorithm I maintaains set of visited or explored cells in C, and their bound- ing hyperplanes (corresponding cell facets) in Č. It also maintains queue of cells, such that each cell in the queue has been discovered in Line 12 as neighbor of some visited cell in C, but is yet to be explored itself. The algorithm detects if cell has been visited before by using its sign pattern on the hyperplanes in H. This can be done in O(dlog t) time, since |C| = O(t') using well-known combinatorial fact (e.g. [Buc43)). For new cell e, we run AUGMENTEDCLARKSS bounding hyperplanes I. as well sign patterns for neighbors in time O LP [T.| 1)) by Theorem 2.T The computed neighbors are added to the queue in Line [4] A cell gets added the queue at this step up to [c] times, but is not explored if already visited. Thus we up V iterations
Proof of Theorem 2.2
to compute its
16

---

of AUGMENTEDCLARKSON and up to 1 + ΣcEV, [cc = 2E + 1 queue insertions/removals. Using efficient union-find struucurssss the set union and membership queries (for and Õ) can be done in Ó(1) time per iteration of the loop. So total time over the V cell explorations and no more than 2. + 1 iterations of the while loop is (dE) + O Eeevy (d,d, (d. Lel + 1)) + O(VTELSS) C
Proof of Theorem 2.3 We will apply Algorithm ann compute the locally relevant hyperplanes by simply taking union of the facet-inducing hyperplanes any point x, across the problem instances.
Let G (V()) E(d) denote the cell adjacency graph for the cells in C. We apply Algorithm 1
implicitly over H = U.H where H is the collection of facet-inducing hyperplanes in C. To H) we simply search the computed partition cell O₂ for the cell containing x in each problem instance z4 in time O 16 = O(m Esl), obtain the set of corresponding facet-inducing hyperplanes H and output Hx U in time O(mLLRs). The former step only needs to be computed once, as the partition cells for subsequent points can be tracked in ((m) time. Theorem 2.2 now gives running time of Deevs (Pdd, + 1)).
implement
OddEEs + m| + mVs
mttRR
F Profit maximization in pricing problems
Prior work [MR15 BSV18 on data-driven mechanism design has shown that the profit function of the prices (parameters) is (F, (F, ()-decomposable with JF the set of linear functions on IR for a large number of mechanism classes (named (d, ()-delineable mechanisms in (BVV We will instantiate our approach for multi-item pricing problems which are (F. f).t) deccomppsslll and analyse the rumning times. In contrast, recent work [BB24] employs cata-independent discretization for computationally efficient data-driven algorithm design for mechanism design problems even in the worst-case. This discretization based approach is not output-sensitive and is known to not work well for other applications like data-driven clustering.
F1 Two-part tariff' pricing
In the two-part tariff problem [Lw41] Oi71], the seller with multiple identical items charges a fixed price, well price per item purchased. For example, cab meters often charge base cost for any trip and an additional cost per mile traveled. Subscription or membership programs often require an upfront joining fee plus a membership fee per renewal period, or per service usage. Often there is a menu or tier of prices, i.e. a company may design multiple subscription levels (say basic, silver, gold, platinum), each more expensive than the previous but providing a cheaper per-unit price. Given access to market data (i.e. profits for different pricing schemes for typical buyers) we would like to learn how to set the base and per-item prices maximize the profit. We define these settings formally as follows.
Two-part tariffs. The seller has K identical units of an item. Suppose the buyers have valuation functions v; : {l...., K} + R~0 where i E {I.... m) denotes the buyer, and the value is assumed to be zero if no items
bought. Buyer i will purchase g quantities of the item that maximizes their utility uz(g)= = (g)) (pr + P2q), buying zero units if the utility is negative for each > 0. The revenue, which
want to maximize the seller, is zero if no item is bought, and p1 + P2q if q 0 items are bought. The algorithmic parameter we want to select is the price
(pi, P2). and the problem instances are specified by the valuations v;- We also consider a generalization of the above scheme: instead of just a single two-part tariff (TPT), suppose the seller provides a menu of TPTs (p) pb..... (pÉ. pL) of length& f. Buyer i selects a tariff (pl.p), pb) from the menu as well as the item quantity q to maximize their utility uf (g) = vz(g) (vf + vág)). This problem has 28 parameters, ... .p......f..... .f))),, and the single two-part tariff setting corresponds to f=1- 1. p (p) pb. rol.pp.....p
The dual class functions in this case are known be piecewise linear with linear boundaries (BSVI8). restated as Lemma G.2 in Appendix G). We will now implement Algorithm [ for this problem by specifying how to compute the locally relevant hyperplanes. For any price vector x p, say the buyers buy quantities (gI.... Im) E (O.....
.......K" K}" according to tariffs (J1...., Jmm) E _ For fixed price vector this can be done in time OmKK)) by computing argmax,,, in (q) for each buyer
17

---

at that price for each two-part tariff in the menu. Then for each buyer we have [(e - 1) potential alternative quantities and tariffs given by hyperplanes u." (q:) 2 uz! q'') + q: & js. for a total of JsRS- mk (e 1) locally relevant hyperplanes. Thus TEIRS = O(mKe) for the above approach, and Theorem 2.2 implies the following runtime bound.
in which given valuation function v(.) for a single problem instance, computes all the pieces of the dual class function u.(-) in time Ō (20)++2K) where the menu length is l, and there are K units of the good.
Theorem F.1 There exists an implementation of
Algorithm 7
Theorem together with Theorem 2.3 implies implementation of the search-ERM problem over
e+2 K))), where Ry; denotes the number of pieces in the total dual class function U( (-)= Σ, un. (+) (formally, Corollary G.I in Appendix G In contrast, prior work for this problem has only obtained an XP runtime of (mK))(0)
m buyers (with valuation functions (-(-) for E [m]] in time O O (2f)
BPS20] For the special case 1, we also provide an algorithm (Algorithm 4 in Appendix G that uses additional structure of the polytopes and employs a computational geometry
algorithm due to CE99 to compute the pieces in optimal O(m log(mK) + Rs:) time, improving over the previously best known runtime of (m K3) due to [BPS20) even for worst-case Ry; The worst-case improvement follows from a bound of Ry: = ( K') on the number of pieces, which establish in Theorem G.3 We further show that running time for l = 1 is asymptotically optimal under the algebraic decision-tree model of computation, by linear time reduction from the element uniqueness problem (Theorem G.
F.2 Item-Pricing with anonymous prices
We will consider market with single seller, interested in designing a mechanism to sell m distinct items to buyers. We represent a bundle of items by quantity vector q E 2 such that the number of units of the ith item in the bundle denoted by q is given by its ith component gli]. In particular, the bundle consisting of a single copy of item is denoted by the standard basis vector e; where edii] i j}. where I{-} is the 0-1 valued indicator function. Each buyer j E [nz] has valuation function By : T + R>0 over bundles of items. We denote an allocation as Q = (qI...., 9n) where qj is the bundle of items that buyer j receives under allocation Q. Under anonymous prices, the seller sets a price p; per item i. There is some fixed but arbitrary ordering on the buyers such that the first buyer in the ordering arrives first and buys the bundle of items that maximizes their utility, then the next buyer in the ordering arrives, and so on. For a given buyer j and bundle pair buyer j will prefer bundle qı over bundle 92 so long as uz(g1)
un(g)= = 2y (4) - Eigli Pt. Therefore, for a fixed set of buyer values and for each buyer j. their q1. E {0,
uy (g2) where
preference ordering over the bundles is completely determined by the (2th) hyperplanes. The dual class functions are known to be piecewise linear with linear boundaries 2
[BVI88]
To implement Algorithm| T for this problem we specify how to compute the locally relevant hy- perplanes. For any price vector fixed price vector this can be done in time (n2"))) by computing argmax,,51, uy(9) for each buyer at that price vector, where Lj denotes the remaining items after allocations to buyers ......j - at that price. Then for each buyer we have at most 2 1 potential alternative bundles given by hyperplanes (g) 2 (, g' * qs. for a total of fLuS I n(2 1) locally relevant hyperplanes.
(PI..... ..m)) say the buyers buy bundles (g1..... 9n). For
Thus TELeS 0n22m) for the above approach, and Theorem 2.2 implies the following runtime bound.
Theorem F.2. There exists an implementation of Algorithm [ which given valuation functions vx(-), (()-)or i E [n), computes all the R pieces of the dual class function in time ((R((2m))) (2m)""n,, where there are m items and n buyers.
in
Proof. In the terminology of Theorem 2.2 we have d m, E < R2, = R, TARS O(n2m), *LRS = T2(2 - 1). By [Cha18), we have LeEV, LP,d, [c]|+ + 1) < O(Ed)) < ORR2m m Thus, Theorem 2.2 implies a runtime bound on Algorithm of Ö V fLRS Eeev, LP (d, [T 1)) Ō R n).
18

---

We will next use this tighter result to bound the number of points of intersection of non-collinear non-axial bounding lines, let's call them crossing points, across all instances (UI,.... pm)). Consider a pair of instances given by buyer valuation functions Us. U/ We will establish that the number of Our approach yields an efficient algorithm when the number of items m and the number of dual class function pieces R are small. Prior work on item- with anonymous prices has only focussed on sample complexity of the data-driven design problem [BSV18].
G Additional details and proofs from Section
Proof of Theorem F7 the terminology of Theorem 2.2 we have = 26, E S R., = R TELRS = O(KE), fLRS- I Ke. By [Cha18] we have Σeevn LP(d, [Ta| + + S =(Ed4/2+1) S
O ((R((2))(+)) Thus, Theorem 2.2 implies runtime bound on Algorithm of Ö(dE + VTRRS LLSS. EeEvy LP(d, [cl + 1)) = O (2)((2))+
Corollary G.1. There exists an implementation of in Algorithm which given valuation functions v.(:) for E [m], computes all the Ry pieces of the total dual class function U U......... (-) E, Uy (-) in time (2))(22))+2 where the menu length is l, there are K units of the good and m is the number of buyers.
Proof. We first compute the pieces for each of the problem instances (single buyers) and then the pieces in the sum dual class function using Theorem 2.3 By Theorem F.I the former takes time Ö(mRR(22) (2E))+2 and the latter can be implemented in time O(Im + 2 mKeE.ev LP(d, Te| 1)) ((R3 (2 which dominates the overall running time. n
G.1 Piecewise structure of the dual class function
The following lemma restates the result from BSV18 in terms of Definition Note that up in the following denotes the revenue function (or seller's utility) and should not be confused with the buyer utility function W4.
Lemma G.2. Let U be the set of functions {up : v(.) - vî +5 4 5 argmax,,, v(g)
p² (1.9), pم = (pt. (b) that map valuations v(.) to R. The dual class Ut is (F, (FF((K))) (ieee)) decomposable, where = {fo u + IR C E 2 consists of linear functions fe up + p c.
We also bound the number of pieces R. in the worst-case for 8 = 1. The following bound implics that our algorithm is better than prior best algorithm which achieves an O(m² (m) runtime bound, even for worst case outputs.
Theorem G.3. Let menu length = 1. The number of pieces Ry in the total dual class function U (V 3 (-) E (-) is at most Omm²
Proof. By Lemma G.2 the dual class (F, K2) ppiecewie decomposable, where F is the class of linear functions. That is, the two-dimense two-dimensional parameter space (P1,P2) can be partitioned into polygons by at most X2 straight lines such that any dual class function Uy, is a linear function inside any polygon.
We first tighten the above result to show that the dual class in fact (F, 2K + pieeeeee decom- posable. that is the number of bounding lines for the pieces is O(K). This seems counterintuitive since for any buyer i, we have @(K2) lines (g(g) 2 (g(')) for q < q' E {0...., K}. If q > (4(g) = =4'('') are axis axis-parallel lines with intercepts (((44)-)(4) Since for any pair q, o' the buyer 9'-9
has a fixed (but opposite) preference on either side of the axis-parallel line, we have at most K distinct horizontal 'slabs' corresponding to buyer's 's preference of quantities, i.c. regions between lines p2 = a and p2 b for some a, b >>> O. Thus we have at most K non-redundant lines. Together with another K lines (0) = u,(g") and the axes, we have 2K + 2 bounding lines in all as claimed.
crossing points are at most 4K for the pair instances. Let I, and l, be bounding lines for the pieces of Uh: and May respectively. If they are both axis-paralle,, then they cannot result in crossing point. For pairs of bounding lines 1 and I, such that I, is axis-parallel and 1 is not, we can have most K crossing points in all. This is because any fixed 4 can intersect at most one such ly since buyer j's
19

---

preferred quantity 9, is fixed along any horizontal line, unless zj changes across 4 in which case the crossing points for the consecutive 1 coincide. Thus, there is at most one such crossing point for each of at most K axis-parallel 1 l's. By symmetry, there are at most K crossing points between 1;, 1j where 1 is axis parallel and not. Finally, if neither 4, 1 axis parallel, we claim there can be no more than 2 crossing points. Indeed, if we arrange these points in the order of increasing P2- then the preferred quantity of at least one of the buyers i or j strictly decreases between consecutive crossing points. Thus, across all instances, there are at most 2m K crossing points.
Finally, observe that the cell adjacency graph Gy for the pieces of the total dual class function U (v......"..))))) (-) is planar in this case. The vertices of this graph correspond to crossing points, or intersections of bounding lines with the axes. The latter is clearly ((mK) since there are O(K) bounding lines in any problem instance. Using the above bound on crossing points, the number of vertices in GU is (m²²)) Since Gu is simple, connected, planar graph, the number of faces is no more than twice the number of vertices and therefore the number of pieces Ry is also O(m² K). O
G.2 Optimal algorithm for Single TPT pricing
Consider the setting with menu wenu-length l = 1. The key insight is to characterize the polytopic structure of the pieces of the dual class function for a single buyer. We do this in Lemma G.4
Lemma G.4. Consider a single buyer with valuation function v(-). The buyer buys zero units of the item except for a set Pu C RR2, where Pu is a convex polygon with at most K + 2 sides. Moreover, 2r can be subdivided into K' S K polygons g each a triangle or a trapezoid with bases parallel to the pr P1-axis, such that for each i E [K"] the buyer buys the same quantity g0) of the item for all (8)
prices in Qv
Proof. We proceed by an induction on K, the number of items. For K = 1, it is straightforward to verify that @. is the triangle pi 2 0, 2 0, P1 + P2 S v(1).
Let K > 1. If we consider the restriction of the valuation function ui()) to K - 1 items, we have a convex polygon e satisfying the induction hypothesis. To account for the K-th item we only need to consider the region p1 2 0. P2 2 0.p2 I v(K)-e(() for < < K, and p1 + P2K S v(K). If this
K-9
(K') with q (kk)) = K, the region where the buyer would buy K units of the item is a trapezoid with bases parallel to the P axii... We
region is empty, e. = e'.. and we are done. Otherwise, denoted by do
claim that Pe = (g) L P2 S x( w())
(K') and satisfies the properties in the lemma.
U gu
K-4
We have (K'-) 1)= argmin, v(K)-v(s) such that the buyer's preference changes from q' = -('K-1) K-9
v(K)-v(a)) To prove e is convex, we use the inductive to g(k()) K units across the line p2 a K K-
hypothesis on g and observe that P1 = v(K) - P2K coincides with p = v(g') - p29' for P2 = u(k)-u(d'), Also the only side of du that is not present in e, lies along the line p1 p2K v(K). K-q'
thus @u has most K +-2 sides. The subdivison property is also readily verified given the construction (K') of On from d. and @o
Based on this structure, we propose Algorithm 4 which runs in in O(mK log(mK) + R&)) time.
Theorem G.S. There is algorithm (Algorithm 4 that, given valuation functions v.(-) for i E [m]] computes all the pieces of the total dual class function U ((i....em)) (.) for K units of the good from the m samples in Omm log(mK) + R2) time.
Proof. Note that if 0 < < q' and (x(g) > (g()),, then for any P1 2 0, 2 O we have that (,(g) v, (g)g) (p1 + P29) 0;(g') (P1 + P2g), or the buyer will never prefer quantity q' of the item over the entire tariff domain. Thus, we will assume the valuations v;(4) are monotonic in q (we can simply ignore valuations at the larger value for any violation). Algorithm exxplois the structure in Lemma G.4 and computes the O(K) line segments bounding the dual class pieces for a single buyer in O(K) time. Across m buyers, we have O(mK) line segments (computed in ((mk) time). The topological plane-sweep based algorithm of [C192] now computes all the intersection points in O(mK (log mK) + Ry:) time. Here we have used that the number of polytopic vertices is O(R)) using standard result for planar graphs.
20

---

Algorithm 4: CompuueFiccAAlicctioRReejoo
Input: 1/ (,), valuation functions
1. For i = 1... 172 do
Q - 0 (stack), q' 1, h v1)))
3. For q 2... do
3.1 h' f (v:(4) - vi (z(d)))((a (a
3.2
if0 < h' <
h H²'
Push (q, h²) onto Q
o' 4-g 9
3.3
else if 0 < h'
while N' 2 h do
Pop (q': R) from Q
(q,, h1) t- Top(Q)
h' + (vi(g) (11)))((q qi)
h hth4 h1
d' 4q
Push (q, ht) onto Q
4. For (q. h) do
Obtain ()) for g0) using lines = h and =(()) P29.
Compute intersection of segments in Pe: for [m]] using (CE92).
6. Use the intersection points to compute boundaries of all polygons (pieces) formed by the intersections.
We further show that this bound is essentially optimal. A runtime lower bound of QmmK + Rs) follows simply due to the amount of time needed for reading the complete input and producing the complete output. We prove a stronger lower bound which matches the above upper bound by reduction the element uniqueness problem (given list of numbers, there any duplicates?) for which an 2in log n) lower bound known in the algebraic decision-tree model of computation.
Theorem G.6. Given list of n numbers L = (II,..., In) N", there a linear time reduction to a m-buyer, K-item TPT pricing given by v.(,), E [m]] with mK = (n), such that the pieces of the total dual class function U ((.......))) (+) can be used to solve the element uniqueness problem for f. in (n)) time.
Proof. Let mK = n be any factorization of n into two factors. We construct a m-buyer, K + 1 item single TPT pricing scheme follows. Define yj Tj + max F& for each æÿ in the list L. For every buyer E [m²). we set (1) = max; 2 + and (g + 1) = > Mj+(i-1) for each [K] Buyer i's pieces include the segments p2 = (u: + 1) +
q E
(i-((- for E [K] (Lemma G.4). Thus, across all buyers E [m]] we have mK = n segments along the mnj. We say duplicate present if there are fewer than mK segments parallel to the P1 axis in the pieces of the total dual class function, otherwise we say 'No' (i.e. all elements are distinct). This completes the linear-time reduction.
lines P2 = 2, for
H Comparing the quality of single, complete and median linkage procedures on different data distributions
We will construct clutering instances where each of two-point based linkage procedures, i.c. single, complete and median linkage, dominates the other two procedures. Let T TS cmpl and Ti denote the cluster tree on clustering instance S using Degt, Dempl and Dmed as the merge function (defined in Section 3) respectively for some distance metric d which will be evident from context. We have the following theorem.
Theorem H.l. For any n 2 10, for i E (1,2,3), there exist clustering instances with |Sa] = n and larget clusterings C₁ such that the hamming loss of the optimal pruning of the cluster trees constructed using single, complete and median linkage procedures (using the same distance metric d) satisfy
21

---

(i) E(T C1) = (22) E(T cmpt C1) = =[(1) and E(T med: C1) (((),
(ūi) ((Te cmpt C2) = 21 ((T C2) = (1(1) and E(T med: C2) 12(1),
(iii) E(T C2) ( { C2) (1)) and E(T C2) S2(1).
Proof. In the following constructions we will have S, C 2R and the distance metric d will be the Euclidean metric. Also we will have number of target clusters k = 2.
Construction of St, Ct. For Sj, we will specify the points using their polar coordinates. We place
a single point x at the origin (0, 6) and n-1 points each along the unit circle at locations 3/1 8
(1,0),32 1/2 = (1, 7 - e), y/3 = (1, 2 = (1, 3mt and Us = (1, 7x
T c), ys = (1, ya = (1, 5
I - c), = (1, 3z 2
4 - c), where = 0.001. Also set C1 = {(=), \ {x}).
In each linkage procedure, the first 9 merges will join coincident points at locations Vj. [8]. let Ø3 denote the corresponding sets of merged points. The next four merges will be 2j. == {ūj, ] for j E (1,3,577} for each procedure since ((Uj,85+) = v2 - 2 cos( ] - c) < minf /2 2 cos( _ + e), 1), again common across all procedures. Now single linkage will continue to merge clusters on the unit circle since /2 - cos( ] + c) < 1, however both complete and median linkage will join each of zj. [1,3, 5, 7 to the singleton cluster {x} since the median (and therefore also the maximum distance between points in Ej, = # j is at least v2 > Therefore a 2-pruning m of T yields C1 i.e ( C1) = 0, while a 2-pruning of Temp or The would yield {zy St 2 for some j (1, 5, 7). corresponding to hamming loss of + (22) Ω(1).
Construction of S2, C2. For S2, we will specify the points using their Cartesian coordinates. We place single points 21, 22 at (0, 0) and (3.2, 0.5) and n-2 points each at y1 = (1.1, 1.8) and y/ = (1.8, 0.5). = We set C2 = {{(x), y) E S2 y 1), v( S2 y 1)}- The distances between pairs of points may be ordered as
d(x2, 1/2) = 1.4 < d(y), 12) R 1.5 < ((11,2)) R 1.9 d(ai, v1) R 2.1 < d(x2, ) R 2.5
< x2)
All linkage procedures will merge the coincident points at y1 and y/ (respectively) for the first 4 merges. Denote the corresponding clusters by ÿ1 and ÿ2 respectively. The next merge will be 22 == {#2, } in all cases. Now single linkage will join 22 with V1. Further, since 10, n- 2 4 and therefore the median distance between 22 and ÿn is also d(y1.32) However, since d(x1, (() < d(22. )1), the complete linkage procedure will merge {21, 22). Finally, the two remaining clusters are merged in each of the two procedures. Clearly, 2-pruning of T yields C2 or ((TS: cmpt+ C2) = O. However, E(TSS) C2) = ((TSS m C2) = 1 - 0 = Q(1).
Construction of S3, C3. We specify the points in S3 using their Cartesian coordinates. We place n-1 points each at æ1 = (0. 0). = (0, 2c). 12
n-1 points each at of = (0, c), 22 = =0, 1 + c). x-
points each 1/1 (1 0.9cc, c), 1/2 (1+c, 1 1.9c), and one point 21 (0, 2) with c = 0.3. With some abuse of notation we will use the coordinate variables defined above to also denote the collection
of points at their respective locations. We set C3- ({(,,)) v) E S2 x S 0}, ((x,)) E S2 x > 0}}.
After merging the coincident points, all procedures will merge clusters क == {#1, +1) and ã == {#2, ( 21 }- Let's now consider the single linkage merge function. We have ( Z2; d) = and all other cluster pairs are further apart. The next merge is therefore ă := [2), Also, Degi (ū, 31:d) = 1 + 0.9c < min D ( 1/2 d), Degl (M,, y/5 d)} leading to the merge {ū, M. and finally y2 is merged in. A 2-pruning therefore has loss E(TTSA C2) = (11). On the other hand, sgl Dmea (m d) 1 + > (mea(M1, 1/23 d) v(1 0z + 0. and D M1;d) d) ((1 0. 2 (Dmea(y1, y2; d), Dieea S2; d)). As result, median linkage would first
A ko ---urrunnn for a tree 1 is a partition of the points contained in ""'s root into ko clusters such that each cluster is an internal node T".
22

---

381
9/2
DF
V1
M6
98
32
yi
97
St.
S2.
Ss. Ca
Figure I: Construction of clustering instances showing the need for interpolating linkage heuristics. We give concrete instances and target clusterings where each of two-point based linkage procedures, iee single, complete and median linkage, dominates the other two.
merge (2), followed by (āi, .2). and 2-pruning yields Cs. Complete linkage also merges {yi 323 first. But Dempl (T1, T2; d) > (m1 82); d). Thus, E(Zempi C3) 12(1).
I Additional details and proofs from Section 3
Definition (2-point-basee) merge function [DL20)]. merge function is 2-point-based if for any pair of clusters A, B S X and any metric d, there exists set of points (a.b) E A x B such that D(A, B;d) = d(a, b). Furthermore, the selection of a and b only depend on the relative ordering of the distances between points in A and B. More formally, for any metrics d and d' such that d(a, b) S. daa', if and only d' d' S d' d'l,,' ,b), then ( B;d) = d(a, b) implies D(A, B; d²) d' ba)
For instance, single, median and complete linkage are 2-point-based, since the merge function D(A, B; d) only depends on the distance d(a, b) for some E A. E B. We have the following observation about our parameterized algorithm families D (A, B; 8) when A consists of 2-point- based merge functions which essentially establishes piecewise structure with linear boundaries (in the sense of Definition T.
Lemma L11 Suppose S E is a clustering instance, A is set 2- point-based merge functions with | I, and 8 is set of distance metrics with |6| = m. Consider the family of clustering algorithmms with the parameterized merge function (A, B; 8). The corresponding dual class function us(() is piecewise constant with ((S))mm) linear boundaries.
Proof. Let (aij- bij, aly- By Misssisasssmm S.S be sequences Im points each; for each such a, let Ja P > R denote the function
ga(p)
Σ EE
adg()) bij) d, dz bgy)
and let g (gul (aij. bij, d' My lssssssssss SS be the collection of all such linear functions; notice that [G] = O(S 41m Fix p.p' I' e P with g(p) and g(p') having the same sign patterns for all such g. For each A, B, A', B' C S, Dj E. and d, 8, have D, B; dy) (a b) and DA B': = (a' b') for some a, b, a' E (since D; is 2-point-basedd Thus we can write (;
Lieimlad eo (as(p)dj(ain) bij) for some agj bij E S; similarly, (A ;) Eie Lds 0 (p)d, Byy) for some d'y, E.S. As result, (A, B,5) S (A',', B'; and only
Σ (p)( (dz(arg byy) dz(dlys 1())) 5 kE(0,
which is exactly when ga (p) < for some sequence a. Since (p) and ga (p())) have the same sign pattern, we have (A 8; < (A', B'; if and only if D2 (A. B; 8) DD (A', So p
23

---

Figure 2: The first three levels of an example execution tree of a clustering instance on four points, with a two-parameter algorithm (P A 2). Successive partitions Po. Pı, P2 are shown at merge levels 0, 1, and 2, respectively, and the nested shapes show cluster merges.
and p' induce the same sequence of merges, meaning the algorithm's output is constant each piece induced by g. as desired.
From Lemmal I.1 we obtain a bound on the number of hyperplanes needed to divide P into output- constant pieces. Let H be set of hyperplanes which splits P into output-constant pieces; then, a naive approach to finding a dual-minimizing requiring ([ runtime. However, by constructing regions merge-by merge-by-merge and successively refining the parameter space, we can obtain a better runtime bound which is output-sensitive in the total number of pieces.
P is to enumerate all pieces generated by H,
Proof of Lemma ??. This simple corollary of Lemma 1= d +++ 1.
I.I for m 1. this case, we have
Lemma L.2. Consider the family of clustering algorithms with the parameterized merge function (),AA, B) Let TS denote the cluster tree computed using the parameterized merge function RRy that map a clustering instance R. The dual class Ut (F, pieceeesss decomposable, where F= [fe 1 R R]} consists of constant functions fo Upp
(A, d:)
sample S. Let U be the set of functions {up S E(T) is
The key observation for the proof comes from BDL20 where it is observed that two parameterized distance metries dp,; dpp behave identically (yield the same cluster tree) given dataset S if the relative distance for all pairs of two points (a, b), (a', (T) E 52 x S2, da(a, b) da 1). has the same sign for P1 P2. This corresponds to partition of the parameter space with |S] hyperplanes, with all distance metrics behaving identically each piece of the partition. More formally, we have
Proof of Lemma 1.2 Let be any clustering instance. Fix points a, b, a', 6 S. Define the linear function da.b.' & (p) E, pi(d,(a, (a, b) d, fa',, (,)). If dp denotes the interpolated distance metric, we have that da(a, b) < da ( b') and only ga.b,a'.v (p) S 0. Therefore we have a, b',
S} of SS hyperplanes such that any piece of the sign-pattern partition of the parameter space by the hyperplanes, the interpolated distance metric behaves identically, i.e. for any P. p' in the same piece d, S d, 8') iff de (a. b) S (a' The resulting clustering is therefore identical in these pieces. This means that for any connected
set = {ga.haa N (p)

---

component R of I \ H, there exists real value en such that up($1, )2) = en for all p E R By definition of the dual, ea (up) up(81,82) 82) cR- For each hyperplane h E H, let g(h) E g denote the corresponding halfspace. Order these &o = |S]* functions arbitrarily 91...... given connected component R of IR H, let ba E {0, 1 be the corresponding sign pattern. Define the function f(bu) fog and for b not corresponding any R. f(b) fo- Thus, for each p R
................................ 9k- 9 For
" 00 (up)
Σ BE (E.11))
[(p)(up)= = b (b))
Corollary L3. For any clustering instance S E II, the dual class function us(:) for the family in Lemmal 1.2 is piecewise constant with O ((S) pieces.
Lemma L.4. Let S E IT be a clustering instance, A be a set of merge functions, and 5 be a set of distance metries. Then, the corresponding dual class function ug(:) is piecewise constant with (11655)) linear boundaries of pieces.
Proof. For each subset of points A, B, A', B' C S, let JABB,A' P + IR denote the function
AA.B.A',B (p) = D2(A, - -
and let G be the collection of all such functions for distinct subsets A, B, A', B'. Observe that G is class of linear functions with [g] S (2181)² 16 16|s| Suppose that for p. p' P. gp) and g(p') have the same sign for all g G: then, the ordering over all cluster pairs A, B of D, B;5) the same as that of D (A, 8). At each stage of the algorithm, the cluster pair A, B S S minimizing Dp(A, B; 5)) is the same as that which minimizes D2 (A, B: 8). so the sequences of merges produced by and p' are the same. Thus the algorithm's 's output is constant on the region induced by 9A.B.A'.B' meaning (-(() (-) is piecewise constant on the regions induced by G, which have linear boundaries. 0
L. Execution Tree
Formally we define execution tree (Figure 2 as follows.
Definition 5 (Execution tree). Let S be clustering instance with |S| n, and @ + P (0, 1]s. The execution tree on S with respect to 'P is a depth-n rooted tree T, whose nodes are defined recursively as follows: r (I), P)) is the root, where [] denotes the empty sequence; then, for any node v = ([u), u2..... Uz], Q) E T with t < R 1, the children of are defined as
children(u) (v) = (ILL u2,..... ................................ Ue, (
{
A. C is the (1 1)st merge by Ap for exactly the p E QA.B C,P with 0 + QA. S Q
(), QA.B)
For an execution tree T with T and each with 0 S i n. we let P; denote the set of Q such that there exists depth-i node E T and sequence merges M with v = (M, Intuitively, the execution tree represents all possible execution paths (i.e. sequences for the merges) for the algorithm we vary the algorithm parameter p E P. Furthermore, each P,
family when run on the instance is subdivision of the parameter space into pieces where each piece has the first i merges constant. We establish the exccution tree captures all possible sequences of merges by some algorithm Ap in the parameterized family via its nodes, and each node corresponds to convex polytope if the parameter space P a convex polytope (Lemmata 1.5 and [.6).
Our cell enumeration algorithm for computing all the pieces of the dual class function now simply computes the execution tree, using Algorithm compute the children nodes for any given node, starting with the root.
Lemma L.S. Let S be clustering instance and T be its execution tree with respect to P. Then, if sequence of merges M [wi, W2,.... Ue] is attained by for some p E P, then there exists some E T at depth 1 with v (M, Q) and with Q C P being the exact set of values of p for which Ap may attain M. Conversely, for every node e = (M, 2) E T, M a valid sequence of merges attainable by Ap for some p P.
25

---

Proof. We proceed by induction on t. For t = O, the only possible sequence of merges is the empty sequence, which is obtained for all p E P. Furthermore, the only node in T depth is the root (0, P), and the set P is exactly where an empty sequence of merges occurs.
Now, suppose the claim holds for some 2 0. We show both directions in the induction step.
For the forward direction, let MM+1 = [ui. u2,..... Ue, 1c+1]. and suppose Mr+1 is attained by Ap for some E P. This means that M, [u1, u2....... Ue] is attained by Ap as well; by the induction hypothesis, there exists some node v2 = (M,, 2.) E T' at depth t, where p E 2 and 2, is exactly the set of values for which A may attain Mr. Now, u4+1 is possible next merge by Ap for some E Qi; by definition of the execution tree, this means iy has some child U1+1 = (M1+1, Qx+1) ) in T such that Q++1 is the set of values where u4+1 is the next merge in Q. Moreover, Q++ is exactly the set of values p E P for which Ap can attain the merge sequence M++1- In other words for any p' E ' \ Q1+1, Ap cannot attain the merge sequence Mr+1 Otherwise, either some p' E P \ Q attains M meaning Ag attains Mr (contradicting the induction hypothesis), or Ap attains Me+1 for some p' E E2+11 \ 2c, contradicting the definition of 2++1.
For the backward direction, let vt+1 = (Me+1, 2441) E T at depth + 1. Since 1 is not the root, Vt+1 must be the child of some node vt, which has depth t. By the induction hypothesis, 2t = (Me, Qt), where M₁ = [U1, Ug...., ue] is attained by A, for some p E P. Thus by definition of the execution tree, MM+1 has the form [u1, u2,,... . Uy, (A, B)], for some merging of cluster pairs (A, B) which is realizable for p E Qs. Thus M is a valid sequence of merges attainable by Ap for some p E P.
Lemma L.. Let S be a clustering instance and T be its execution tree with respect to P. Suppose P a convex polytope; then, for each v (M, Q) E T, Q a convex polytope.
Proof. We proceed by induction on the tree depth t. For f = 0. the only node is (0, P), and P convex polytope. Now, consider node T at depth t + 1; by definition of the execution tree, e = (Ma, 2,) is the child of some node u E T, where the depth of u is t. Inductively, we know that w = (Ma,, 2w.) for some convex polytope 2.. We also know Mi.. has the form M.. = [u,, ..., ue]. and thus Q. is defined to be the set of points p E Qw where the merge sequence M, = [u,, uy..... Uys (A, B)] is attainable for some fixed B, B C S. Notice that the definition of being attainable by the algorithm Ap is that D,(A, (A, B; is minimized over all choices of next cluster pairs A', B' to merge. That is, Qu is the set of points
Q. f Qw D; S Dp(A', 8'; for all available cluster pairs A', B' after Mw)
Since (A, 5) an affine function of p. the constraint (A, B;8) S (A', B¹; a half- space. In other words, 2, is the intersection of convex polytope 2.. with finitely many half space constraints, meaning 2, is itself a convex polytope.
It follows from Lemma L6 that P. forms convex subdivision of P, where each Pi+1 is refinement of P;; Figure 2 (in the appendix) shows an example exccution tree corresponding to a partition of a 2-dimensional parameter space. From Lemma [.5] the sequence of the first merges stays constant on each region P E P,. Our algorithm computes a representation of the execution tree of an instance S with respect P; to do so, it suffices to provide a procedure to list the children of node in the execution tree. Then, a simple breadth- first search from the root will enumerate all the leaves in the execution tree.
Now, our goal is to subdivide P into regions in which the (j + 1)st merge is constant. Each region corresponds to cluster pair being merged at step j + 1. Since we know these regions are always convex polytopes (Lemma I.6). we can provide an efficient algorithm for enumcrating these regions.
Our algorithm provides an output-sensitive guarantee by ignoring the cluster pairs which are never merged. Supposing there are n, unmerged clusters, we start with some point x / and determine which piece W it is in. Then, we search for more non-empty pieces contained in P by listing the "neighbors" of W. The neighbors of W are pieces inside P that are adjacent to W: to this end, we will more formally define a graph Gp associated with P where each vertex is a piece and two vertices have an edge when the pieces are adjacent in space. Then we show that we can enumerate neighbors of a vertex efficiently and establish that Gp is connected. It follows that listing the pieces is simply a matter of running a graph search algorithm from one vertex of Gr, thus only incurring a cost for each non-empty piece rather than enumerating through all n pairs of pieces.
26

---

Proof of Corollary 3.2 The key observation is that on any iteration i, the number of adjacencies H, O(R)). This is because for any region P E P, P is polygon divided into convex subpolygons, and the graph Gp has vertices which are faces and edges which cross between faces. Since the subdivision of P can be embedded the plane, so can the graph Gr. Thus Gp planar, meaning
H, (R))) Plugging into Theorem 3.1 noting that (n + 1)2 S n H, S H, and RG S R, we obtain the desired runtime bound of O (Z (R RTM)) = ORTTMn))
1.2 Auxiliary lemmas and proofs of runtime bounds for our algorithm
Lemma 1.7. Fix an offine function f: R - IR via f(x) = xa + b, for a, b IR and a + 0 For a subset S S IR, if f(S) is convex and closed, then S is also convex and closed.
Proof. First note that f is injective, since a + 0%_ To show convexity of S, take arbitrary x, y E S and x E [0, 1]; show that Ax + (1 A)y S. Consider f(Ar
A)y):
f(Ax + (1 {)y) = (Az + (1 x)y)a
= A(xa + b) + (1 \) + b)
By definition, ya + b, xa + be f(S), so it follows that f(Ax + (1 - A)y) E f(S) by convexity of f(S). So there exists some
S with f(z) f(x + (1 \)y), but since is injective, Az + (1 A)y = 2 S. Thus S is convex.
To show closedness of S, we show R \ is open. Let Nxx, r) denote the open ball of radius r around x, in either oie-dimensional or d-dimensional space. Let x E R \ S; we know fa) & S(S) since injective. Since gd f(S) open, there exists some r >> 0 with N(f(x), S R2d f(S). Then, take Talla > O; for every E (xr,e), we have
If(x) f() 12 = || + b ya - bll2 < | vlllalla r
and so f(v) N(f(2),r) S Rd ((S),, meaning y since injective. Thus N(x, e) RAS. meaning S is closed as desired.
This allows us to prove the following key lemma. We describe proof sketch first. For arbitrary (i,j), (i' ?) E Vp. we show that there exists a path from (i,j) to (i', J') in Gp. We pick arbitrary points Qij. Qr.y' we do this because by definition, Vp only has elements correspond- ing to non-empty cluster pairs. Then, we draw a straight line segment in from w to x. When we do so, may pass through other sets the way; each time we pass into
region, traverse an edge in Gr, so the sequence of regions we pass through on this line determines a G G--path from w to
Lemma L8. The vertices Vş of the region adjacency graph Gp form a connected component; all other connected components of Gp are isolated vertices.
Proof. It suffices to show that for arbitrary vertices (i1, (12. E Vp, there exists a path from (11.31 (i2.12) in Gp. For ease of notation, detine Q1 Qi..j. and Q2 Q
Fix arbitrary points u E Q1 and w E Q2- If = w then we're done, since the edge from (11, to (12. f2) exists, suppose + Consider the line segment L defined as
L (uu + (1 A)w X [0,
Since Q1, Q2 C P, we have u, P. Furthermore, by convexity of P. it follows that L C P.
Define the sets Ra.j as
RA,j = Qi,
Since each Qi,j and T. are convex and closed, is each Rigj- Furthermore, since U., Qij P. must have ULs Rij L. Finally, define the sets Si.j as
St. = (t E [0. 1] tu + (1 t)w E Rag} } S [0,
27

---

Note that St is convex and closed; the affine map f St. - Ri, given by f(x) zu+ + æ(u w) + w has Ri, as an image. Furthermore, must be convex and closed. Furthermore, U., S.. = [0. 1].
- =))
o 0%, by Lemma I.7 the preimage Si,j
The only convex, closed subsets of [0, 1] are closed intervals. We sort the intervals in increasing order based on their lower endpoint, giving us intervals 11 .2...... It. We also assume all intervals are non-empty (we throw out empty intervals). Let (p) denote the corresponding cluster pair associated with interval Lpi that is, if the interval 1p is formed from the set Si.. then o = (i,j).
Define 0g, by to be the lower and upper endpoints, respectively, of I5. We want to show that for all 1 I i _ 8- 1, the edge (t))), (i + 1)} E Ep; this would show that ((1) is connected to a (() in the Vp. But (1) (i1.j1) and (E) (i2, so this suffices for our claim.
Now consider intervals I, - las, bi] and l++1 = [a:+1, otherwise, some smaller interval would fit in the range [bz, (h,,a--]: and it would be placed before I in the interval ordering.
must be the case that by a++1
Since by 474+1 by definition, ub; (1 (1-b,,) w E R (o In particular, ub, + (1 (1-1111) b,) E Qo(a) n QQ(+44); by definition of Ep, this means {a(i), ai 1)} E Ep, as desired.
L
Theorem 3.1. Let S be clustering instance with |S|= n. and let R, [Psl and R = Rn- Let H, = {{(2,, 22) E ? 21 n222 + 6)| denote the total number of adjacencies between any two pieces of P, and H Hn. Then, the leaves of the execution tree on S can be computed in time Ó ( (H, + RTTM) (n it 1)2), where Ta is the time to compute the merge function.
Proof. Let T be the execution tree with respect to S, and let T, denote the vertices T at depth t. From Theorem 2.2 for each node (M, Q) E T with depth in time On?) [Pdd, E.) + Vo n K), where V. is the number children of v, and
can compute the children of
{
(Q1 O2) P2 Q Q2 + and
Fy =
= (Mi, U2 = (M2, 22)
for some children 11, U2 of
Now, observe
Σ E, < H2t1 VET++1
since H4+1 counts all adjacent pieces 21, 22 in Pt+1: each pair is counted at most once by some Eg. Similarly, we have EvET. V, R4+1. since R&+1 counts the total size of Pt+1- Note that n++1 = (n-t), since merges have been executed by time t+ so n n-i+1. Seidel's algorithm is a randomized algorithm that may be used for efficiently solving linear programs in low dimensions, the expected running time for solving an LP in d variables and m constraints is O E.,) (also holds with high probability, e.g. Corollary 2.1 of (Sei91)). There are also deterministic algorithms with the same (in fact slightly better) worst-case runtime bounds [Chal8]. Therefore, we can set LP E.)) = (d! E.). So that the total cost of computing PP; is
Σ d! En - it 1)2 + VoK(n-i+ 1)² VE
Σ
(d) 11, R2K) (n (n- iin))² 1)²
as desired.
J Further details and proofs from Section
We provide further details for Algorithm 5 in Appendix J.2 and other proofs from Section 4 are located in Appendix J.3
J.1 Example dynamic programs for sequence alignment
We exhibit how two well-known sequence alignment formulations can be solved using dynamic programs which fit our model in Section 4 In Section J.I.T we show a DP with two free parameters (d = 2), and in Section]] J.1.2 we show another DP which has three free parameters (d = 3).
28

---

J.1.1 Mismatches and spaces
Suppose we only have two features, mismatches and spaces. The alignment that minimizes the cost e may be obtained using a dynamic program in O(m)) time. The dynamic program is given by the following recurrence relation for the cost function which holds for any i,j > 0, and for any
p = (2),
C(sil:i - s21: 1)
if s s2 s2
C(s1|:t),
min C(s s 1),
p2 - p),
if s # $2]5].
/2 C 1),
The base cases are C(o, é, p) 0, [)) Here & denotes the empty sequence. One can write down a similar recurrence for computing the optimal alignment T($1, $2 P).
C(si[:i], o, = ip for i,j E [m]] x [n]]
We can solve the non base-cass subproblems [: (:(:))) in any non-decreasing order of i+j.. Note that the number of cases V = 2, and the maximum number of subproblems needed to compute single DP update I, = 3 (L,1 = 1, L2 3). For a non base-case problem (i.e. i,j > 0) the cases are given by [[s1[:]] (]. 82[:
[:]] = 1 if $1 [ = s2li]. and [:4] (:(s]) = 2 otherwise. The DP update in each
case is a minimum of terms of the form cp [=]] [2]:)))))[:])))) = - wo,t + cp [s][: (2):: For example if ((s) i], s2 [:]] = 2. we have W2,1 = (1, and 1 (s1 s2|: j]) equals
C(s1l:i-1 1], 82[:3- 11, p). i.e. the solution of previously solved subproblem (si[:í-1) 821: - 1]),
the index of this subproblem depends on I, and index of (s1[:i], s2(:5]) but not on p itself.
J.1.2 Mismatches, spaces and gaps
Suppose we have three features, mismatches, spaces and gaps. Typically gaps (consecutive spaces) are penalized in addition to spaces in this model, i.e. the cost of sequence of three consecutive gaps in an alignment (...
b. ...... a' p q r b' 8'...) would be 3p2 + P3 where P2. P3 are costs for spaces and gaps respectively [KKWIO], The alignment that minimizes the cost may again be obtained using dynamic program (mn) time. We will need a slight extension of our DP model from Section to capture this. We have three subproblems corresponding to any problem in IT,, (as opposed exactly one subproblem, which was sufficient for the example in I.I.I). We have set of subproblems x($1,82) 82) with (T(1, 82) | S , for which our model is applicable. For each (s) [=i]] s2(:))) we can compute the three costs (for any fixed p)
(=(s)[=4) is the cost of optimal alignment that ends with substitution of 81 [i] with s2[i].
[[](s]]:)), s2|=0] p) is the cost of optimal alignment that ends with insertion of x2(j). . [2 p) is the cost of optimal alignment that ends with deletion of [i].
The cost of the overall optimal alignment is simply C(si(: s2 s) = min (C. s2(: il. p). Ciss][ti), s2[:j], p), [a(si[:i],ss) s2[:]] p)).
The dynamic program is given by the following recurrence relation for the cost function which holds for any i 0, and for any p (p1, (2..),)))). Ps).
P1 + C.(sf:i s/]j 1).p), Pi + C(s[iii sg/:j 1).p), Pi -+ 1).p))
(2 min
P2 + +
s2.:1)1) = min
P2 + -
P2 P 11
P2 + --
Ca(s1[:i), 82/1),) p) min
02 + - + C
29

---

Algorithm 5: COMPUTECOMPACTEXXECTOONND
Input: Execution DAG Ge (Ve, Ee). problem instance (31, $2)
Po <- P
2: 01..... Un <- topological ordering of vertices Ve
3: for i = I to do
4: Let S; be the set of nodes with incoming edges to 2;
5:
For vs E St, let P. denote the partition corresponding to v,
6:
P. < COMPUTEOYERLAYDR(2. & S.))
7:
for each E P. do
8:
D' + COMPUTESL $2))
9:
P. + P. P. & RESOVVIDEGGNRRACESDDPPP)
10:
11:
return Partition Pn.
By having three subproblems for each (s1[: sy[:)] and ordering the non base-case problems again in non-decreasing order of i j. the DP updates again fit our model (T).
J.2 Details of the Execution-DAG based algorithm
We start with some well-known terminology from computational geometry.
Definition 6. A (convex) subdivision S of P C Rd is a finite set of disjoint d-dimensional (convex) sets (called cells) whose union is P. The overlay S of subdivisions S S nonempty sets of the form Aietn) 8 with s, E S,. With slight abuse of terminology, we will refer to closures of cells also as cells.
Sn is defined as all
The COMPUTROVERLLAY procedure takes a set of partitions, which are convex polytopic subdivisions of gd, and computes their overlay. We will represent a convex polytopic subdivision list of cells, each represented as a list of bounding hyperplanes. Now to compute the overlay of subdivisions Pi..... Pr. with lists of cells Ci...., Cr, respectively, we define |Ci|
|Cz.] sets of hyperplanes S; is the ji-th cell of Pt and H(c) denotes the hyperplanes bounding cell e. We compute the cells of the overlay by applying Clarkson's 's algorithm (Cla94] to
H = (Uie(z) H( where (!)
each H H........ We have the following guarantee about the running time of Algorithm 6
Algorithm 6: COMPUTEOVERLAYDE
Input: Convex polytopic subdivisions Pı...., Pr. of RRd represented as lists C₁ of hyperplanes for çach cell in the subdivision
H(c)) ()) hyperplanes bounding ji-th cell of Pt for ( E [4], E Ci
for each j1, .......3 :.......J. jL [Cal...., C2 do
H + (UleRz) H())))
H H + CLARKSON H (.......)) C. +- non-empty lists of hyperplanes in H H for ji Ci return Partition represented by
Lemma J.1. Let Rig denote the number of pieces in P(il[i], and it = maxigm.jsn P(ili]. There is an implementation of the COMPUTEOVERLAYY routine Algorithm Jwhich computes the overlay of T. convex polytopic subdivisions in time ((IRR++1.T. (d, Re + +1), which (R2.1.R2 using algorithms for solving low-dimensional LPs [Chal8j.
Proof. Consider Algorithm 6 We apply the Clarkson's 's algorithm at most R2 times, once correspond- ing to each L-tuple of cells from the subdivisions. Each iteration corresponding to cell in the output overlay (corresponding to C) has set of most Lî hyperplanes and yields at most R. non-redundant hyperplanes. By Theorem 2.1 each iteration takes time O LP(dd, R. 1)), where LP(d, R. is bounded by O(d.R.) for the algorithm of [Chal8]. Note that E. R. corresponds to
30

---

Algorithm 7: COMPUTESUDDVISSIODD
Input: Convex Polytope problem instance (2)
the DP case (((11, {2)) for the problem instance Po < an arbitrary point in P
(f). (2) <- optimal alignment of 82) for parameter Po. using subproblem
(g S2 for some lo E [L.]]
mark < 0, polys= new hashtable, poly-queue +- new queue
poly_queue (qquue.enuuuee(()
while po emp ty(( do
f ee-pool-quee dequueee
Continue to next iteration if E mark
mark +- mark {
L C
for all subproblems (s][:d,,,), s2(:ju.,, for E [L,]. # do Add the half-space inequality b" p= corresponding to
Cr,(p, h/
S cn.1 (e, (81, to L; /* Label the constraint (b,c) with
It CLARKSON(L)
www.quueueueeeee (neuueennuueu((")
for each 1' such that the constraint labeled by it is in polys(4 < [C[ e
return polys
the total number of edges in the cell adjacency graph of which is bounded by R Further note that Rg S R_ for each C and |C] S R² to get runtime bound of O(LR4+1, LP(d, R 1)). c
We now consider an implementation for the COMPUTESUBDDIVSSONDDE subroutine. The algorithm computes the hyperplanes across which the subproblem used for computing the optimal alignment changes in the recurrence relation ( by adapting Algorithm We restate the algorithm in the context of sequence alignment as Algorithm
Lemma J.2. Let Ri.j denote the number of pieces in P(([[), and R maxigm.js R..-- There is an implementation of COMPUTESUUDIVVSSONND most (T + I.2d Rt") (d, 1? + R))) )) for each outer loop of Algorithm If the algorithm of [Cha18) is used to solve the LP, this is at most Odd.1 2d+2 1(2L).
routine in Algorithm wiit running time at
Proof. Consider Algorithm 7 For any piece in the overlay, all the required subproblems have fixed optimal alignment, and O(L² + Rt4) hyperplanes corresponding pieces in the subdivision is at most 2dd since have most L hyperplanes intersecting the piece, so we need O(L2d-2 + L R²) time to list all the pieces Cp. The time needed to run Clarkson's algorithm is upper bounded by OlErEC, (I.2 Re)) LP(d, R. 1)) O(Eec,, (1.2 R²-). LP(d, L R² O(L 2 + R2d -L + R.)). Using [Chal8] to solve the LP, this most R 1,24+4)
find the subdivision of the piece by adapting Algorithm [ [using
subproblems and piece boundaries). The number of
Lemma J.3. Let Ri, denote the number of pieces in P(][) and R = maxicmiin R.g-- There is an implementation of DESOLVEDEGENERACIIN most O( i r I,dd) for each outer loop of Algorithm
routine in Algorithm with running time at
Proof. The RESOLVEDEGGENERAIISSD is computed by simple BFS over the cell adjacency graph G. (Vc. E.) (i.e. the graph with polytopic cells as nodes and edges between polytopes sharing facets). We need to find (maximal) components of subgraph the cell adjacency graph where each node in the same component has the same optimal alignment. This is achieved by simple BFS O(VV + [Ea)) time. Indeed, by labeling each polytope with the corresponding optimal alignment,
compute the components of the subgraph of G. with edges restricted
31

---

to nodes joining the same optimal alignment. Note that the resulting polytopic subdivision after the merge still a convex subdivision using arguments in Lemma [.5 but applied to appropriate
sequence alignment subproblem. As noted in the proof of Lemma J.2 we have [V I I, 2 R
since the number of cells within each piece p is at most _ and there are at most ft4 pieces in the overlay. Since Exl= < |Vl22 we have an implementation of RESOLVVEDRGENERRCCISSS O((L2d ( ).
in time
Finally we can put all the above together to give a proof of Theorem 4.1
Proof Theorem 4.7 The proof follows by combining Lemmal J.1, Lemma and Lemma I.3 Note that the execution DAG, we have |V&l S |Eel = OT Further, we invoke COMPUTHOVER- LAYDP and RESOLVED SIONDP across the |Ve] outer loops.
VVel times across all iterations and COMPUTESUBDIVIL
J.3 Additional Proofs
The following results closely follow and extend the corresponding results from BDD Specifi- cally, we generalize to the case of two sequences of unequal length, and provide sharper bounds on the number of distinct alignments and boundary functions in the piecewise decomposition (even in the special case of equal lengths). We first have bound on the total number of distinet alignments.
Lemma J.4. For a fixed pair of sequences 81, 82 E Em Σ", with m S n, there are at most m(m + n1 distinct alignments.
Proof. For any alignment (2), by definition, we have |t,l = |t>| and for all i E [[ if [i] = -, then [2]i] * and vice versa. This implies that & has exactly n m more gaps than 12. To prove the upper bound, we count the number of alignments (21, where l2 has exactly gaps for i E [m]. There are ("+") choices for placing the gap in t2. Given a fixed l2 with i gaps, there are a (+-++) choices for placing the gap in 41 Thus, there are at most (n+i))
(P+))- = M(m-fMae-m I (m + n)" possibilities since i S m. Summing over all i, we have at most m(m + 12 alignments of 82,
This implies that the dual class functions are piecewise-sttructueed in the following sense.
Lemma J.S. Let li be the set of functions {up ($1, + u(s1, s2, I E Rd) that map sequence pairs $1, 82 E TR x E to R. by computing the optimal alignment cost C(s1, 82, p) for a set of features ([:())) The dual class l is (F, G, m²(m + "n)a"))pieccwii" decomposable, where F = Uf + R ||c I Rb consists of constant functions Se Up + c and G = {yw : u - {0,
W. E [Rd} consists of halfspace indicator functions Iw Upp + [w < 0).
Proof. Fix a pair of sequences $1 and 82. Let 7 be the set of optimal alignments we range over all parameter vectors E Rdd By Lemma J.4 we have |T| I m(m + n)m For any aligmment (11,22 (2) E r, the algorithm A, will return (21,2) if and only if
d
Σ 82 82, 82,
Σ S2,th,
for all (2) E E ((t, t2)). Therefore, there is set H of at most (77) S <m?(m + n hyperplanes such that across all parameter vectors in single connected component of [Rd H. the output of the algorithm Ap on ($1, 82) is fixed. This means that for any connected component R of Rd \ H, there exists a real value en such that up $2) = CR for all p E Rd. By definition of the dual, "r (up) = up(81, = en- For each hyperplane E H, let g E 9 denote the corresponding halfspace. Order these k ((7)) functions arbitrarily as ... .k. For given connected component It of IRd \ H, let bR E {0, 1 be the corresponding sign pattern. Define the function (ba) = for and for b not corresponding to any R, f(b) = fo- Thus, for each p E Rd.
" .89 (up)
Σ (0.01
1(g((up) b.vi
32

---

For the special case of d 2, we have an algorithm which runs in time (RTTpe) where the number of pieces in [[m][n] which improves on the prior result O + Dr for two- wwo-parameter sequence alignment problems. The algorithm employs the ray search technique of [Meg78] (also employed by [GBN94] but for more general sequence alignment problems) and enjoys the following runtime guarantee.
Theorem J.6. For the global sequence alignment problem with 2. for any problem instance ($1, $2), there is an algorithum to compute the pieces for the dual class function in O p( time, where De the time complexity of computing the optimal alignment for a fixed parameter p R?, and R is the number of pieces of (((1.02)
Proof. We note that for any alignment (t1, t2), the boundary functions for the piece where (t1, 12) is an optimal alignment are straight lines through the origin of the form
(51, $2 t,, P2l2 $2, t2) > (111(51, $2 12) + (212(51, $2, t
for some alignment (t', t22) different from (f1,ty). The intersection of these halfplanes is either the empty set or the region between two straight lines through the origin. The output subdivision therefore only consists of the axes and straight lines through the origin in the positive orthant.
We will present algorithm using the ray search technique of Meg78j. The algorithm computes the optimal alignment (f1, t2), (t1, (22 at points p (0, 1) and = (1, 0). If the alignments are identical, conclude that (61, t2) the optimal alignment everywhere. Otherwise,
find the optimal alignment (t", (2) for the intersection of line L joining (0, and = (1, with the line L' given by
$2 t1,t2) (212 82, s2,t1,t2) > p1li(51, $2 (2,t) + (212 $2 t 122
If (t", (2) = (t1, or (t' 12) = (t), we have exactly 2 optimal alignments and the piece boundaries are given by L' and the axes. Otherwise we repeat the above process for alignment pairs (t" th), (ti, 12) and (2), (ti, 12). Notice we need to compute at most R + 1 dynamic programs to compute all the pieces, giving the desired time bound.
33

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No] ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We clear state the claims and make sure they accurately reflect our contribu-
tions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
34

---

Justification:
We clearly state that our results lead to faster algorithms when the output-siz is small, and worst-case improved runtimes are left for future work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Complete proofs and details are in the Appendix and appropriately referenced from the main body.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
Guidelines:
35

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https c/iips.cc/public//uu
Codeeuumiiii wwabbbmmsssiinii ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
36

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
37

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttps://eeurips.. http://wwwrp...pppl//l//cccccaaa
Answer: [Yes]
Justification:
We follow the Ethics Guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We view our work as theoretical, with techniques leading to faster machine learning algorithms.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
38

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does existing
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
39

---

Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
40


Reviews:
[{"review_id": "O9hqPvdbWo", "reviewer": "Reviewer_gq34", "summary": "The paper explores computational aspects of implementing ERM in data-driven algorithm design. \n\nThe paper contributes an efficient algorithm to ennumerate cells induced by a collection of hyperplanes. The paper then shows how to utilize this as a subprocedure to solve ERM problems for algorithm design, focusing on linkage-based clustering, sequence alignment, and two-part tariff pricing.", "questions": "See questions above.", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "One of the main interesting things I find about this paper is that the runtime of the ERM implementations is instance dependent, and specifically depends on the number of sum dual class loss function pieces. The paper comments that their runtime bounds imply improvements over prior work in the worst-case R but also can be faster for \"typical\" R.\n\nThe paper is well-written and easy to follow. The paper discusses relevant background and related work.", "weaknesses": "To what extent is the approach generalizable to other data-driven algorithm design problems? Is there a generic principle or a general characterization of the problems for which this approach can be utilized?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and useful comments.\n\n``Generalizability to other data-driven algorithm design problems:`` Our approach is applicable to a fairly large number of problems, for example the various mechanism design problems in [1] are (d,t)-delineable which is a special case of Definition 1 (We include a couple examples in Appendix F). Our current approach is useful whenever the loss as a function of the algorithmic parameter on a fixed problem instance can be shown to have a piecewise structure with linear transition boundaries. The execution tree/DAG technique enables output-sensitive runtime complexity when the piecewise structure can be viewed as a refinement of pieces induced in successive algorithmic steps (e.g. see Figure 2), each refinement involving linear decision boundaries in the parameter space, and we expect this to be useful beyond the linkage clustering and sequence alignment problems considered. There is also potential for extending our work beyond linear transition boundaries e.g. to algebraic boundaries which would be relevant for several problems of interest in data-driven algorithm design.\n\n\n\n[1] Balcan, Maria-Florina, Tuomas Sandholm, and Ellen Vitercik. \"A general theory of sample complexity for multi-item profit maximization.\" In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 173-174. 2018.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4EquHKAZfg", "reviewer": "Reviewer_swPv", "summary": "In data-driven algorithm design, we are given a collection of problem instances sampled from an unknown distribution, and a family of algorithms for solving the problem, typically parameterized by a real-valued multivariate parameter. The goal is to find a setting of parameters such that the performance of the algorithm they parameterize is close to optimal among the family of algorithms, in expectation over the distribution of instances. Most prior work is firstly focused on the generalization aspect, i.e., on showing that a small number of samples suffices (in the sample complexity sense) for finding approximately optimal parameters for the distribution (these are the ERM parameters for the given sample of instance), and thus the family of algorithms is \"learnable\". It then (sometimes) proceeds to develop an efficient algorithm for finding those ERM parameters, based on the structure used to prove the generalization bound.\n\nThis paper focuses more systematically on the ERM efficiency aspect. To this end, it starts with a common theme in many prior works on data-driven algorithms, that had been abstracted out and formulated in a generalized form in Balcan et al. (STOC 2021): for any fixed problem instance, the function that maps a setting of parameters to utility (of invoking their associated algorithm on that instance) admits a simple piecewise structure. Say, there is a small number of \"simple\" boundary functions (say, linear thresholds) that induce a partition of the parameter space R^d such that the utility function restricted to each piece is \"simple\" (say, constant). This is helpful in bounding the VC dimension of the utility functions and thus proving generalization bounds, and also potentially for navigating the parameter space efficiently to find the ERM parameters.\n\nThe novelty in this paper is an attempt to give a more systematic recipe for the second part (navigating the piecewise structure for efficient ERM), with two main advantages -- (1) creating a unified framework that takes care of some parts of the ERM procedure in a general way, thus restricting the portion that needs to be figured out per each problem individually, and (2) obtaining algorithms whose running time depends on the actual number of pieces in the given instances (\"output-sensitive\") rather than worst-case number of pieces. The per-problem part to figure out is a subroutine that, given a problem instance and parameter setting p, returns a list of candidate boundary functions for the piece that contains p, and this subroutine depends on the specific problem in question. The unified part of the framework uses this subroutine to search through the pieces in an \"output-sensitive\" running time.\n\n__Post-rebuttal__: I appreciate the authors' elaborations on the technical content, and the conceptual aspect of the paper. I have raised my score to support acceptance.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The strength of this paper is that the matter of efficient ERM in data-driven algorithms indeed merits its own systematic study rather than being left as an afterthought of the generalization bounds.", "weaknesses": "The main weakness is that the end result isn't very strong: the framework is restricted to linear boundary functions and (more disconcertingly) to a constant number of parameters, and for the most part does not yield improved running times in the worst case, but a different notion of efficiency (output sensitivity). It tends more to systematically organizing ideas that have appeared in the literature in one form or another and less to introducing new algorithmic insights or techniques. I also feel that the presentation and writing could be too opaque for a wide readership like that of NeurIPS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We respectfully disagree with the reviewer that the main result is not strong. Since its inception (around 2016), the field of theoretical guarantees of data driven algorithm design has been focused on sample complexity results. The *major* direction that has been left open in this field is to also consider the computational efficiency of data-driven algorithms. Our paper is the first to consider this question at some level of generality. We note that one cannot hope for the same level of generality as for the sample complexity of data driven algorithm design since algorithmic consideration have always been much more problem specific even in the classic (non-data driven) scenarios, that is in classic learning theory: even in classic learning theory we have general sample complexity results for ERM, yet the computational complexity of ERM algorithms depend heavily on the class (and even for basic classes we still have major open questions). \n\nOur work contains many subtle aspects, for example:\n- We make a novel connection with computational geometry to give beyond worst-case improvements on runtime efficiency. It is a priori not clear  which tool to use to advance the state-of-the-art here.\n- The execution tree approach for linkage clustering needs several technical lemmas for establishing soundness of the approach (e.g. lemmas I.5 to I.8 in Appendix I).\n- The execution DAG approach used in sequence alignment is a completely novel contribution of this paper, and is critical to achieve the desired output-sensitive runtime guarantee.\n\n``Applications of our framework (linear boundaries, constant parameters):`` We show several distinct applications in our work where the linear boundary and constant parameter size is relevant for the data-driven algorithm design problem: linkage clustering - both metric learning and distance function learning; sequence alignment; two-part tariff pricing (App F); item-pricing with anonymous prices (App F). The linear boundary setting appears more frequently than one might initially expect, see e.g. [1] for several applications. Moreover, by a simple linearization argument, our approach yields ERM implementations for polynomial boundaries with small degrees e.g.  e.g. Thm 3.1, Lem 4.1 in [2] or Lemma 2 in [3]. Finally, we remark that we initiate a detailed study of computationally efficient implementation of ERM for data-driven algorithm design and tackle the natural first case where we already show significant improvement over previous runtimes (Table 1) provided output size is small.\n\n``the most part does not yield improved running times in the worst case, but a different notion of efficiency (output sensitivity)`` \nOutput-sensitivity is a relevant notion for data-driven algorithm design. We summarize motivation from prior empirical work in lines 91-104, which indicates usefulness of output-sensitivity from a practical perspective. Note that the whole point of data-driven algorithm design is to provide beyond worst-case improvements in algorithm design [4], so it is not unusual to expect a beyond worst-case measure of efficiency (output-sensitivity and fixed parameter tractability).\n\n``It tends more to systematically organizing ideas that have appeared in the literature in one form or another and less to introducing new algorithmic insights or techniques``\nWe remark that using a computational geometry based technique in the context of learning theory is in itself remarkable and has hardly ever appeared in prior literature. Moreover, a direct application of Clarkson's algorithm itself is not always sufficient. Our “execution DAG” technique proposed for the sequence alignment problem is a novel algorithmic idea not from any previous literature, and is crucial for tracking the partition of the parameter space for each DP sub-problem. In this case the number of alternative alignments (and therefore the number of relevant hyperplanes $t_{LRS}$) for any fixed optimal alignment is exponential, so a direct application of Clarkson’s algorithm would still be exponential runtime.\n\n*References*\n\n[1] Balcan, Maria-Florina, Tuomas Sandholm, and Ellen Vitercik. \"A general theory of sample complexity for multi-item profit maximization.\" In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 173-174. 2018.\n\n[2] Balcan, Maria-Florina, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. \"Structural analysis of branch-and-cut and the learnability of gomory mixed integer cuts.\" Advances in Neural Information Processing Systems 35 (2022): 33890-33903.\n\n[3] Balcan, Maria-Florina, Travis Dick, and Manuel Lang. \"Learning to Link.\" In International Conference on Learning Representations 2020.\n\n[4] Maria-Florina Balcan. Data-Driven Algorithm Design. In Tim Roughgarden, editor, Beyond Worst Case Analysis of Algorithms. Cambridge University Press, 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BXcc4BUZxQ", "reviewer": "Reviewer_YVeC", "summary": "This paper addresses the problem of learning optimal parameters for data-driven algorithm design. A characteristic of the problem is that the dual loss function, which measures the performance of an algorithm as a function of parameters, is discontinuous. Nevertheless, the dual loss is typically piecewise structured (constant, linear, etc.) with linear boundaries. Thus, roughly speaking, the problem of finding optimal parameters reduces to exploring polytopic cells partitioned by boundary hyperplanes. \n\nThe main contribution is a cell enumeration algorithm that runs in output-polynomial time. The algorithm can be seen as a breadth-first search on a cell adjacency graph, where the enumeration of neighbors is done in an output-sensitive manner based on Clarkson's algorithm. The resulting output-sensitive complexity can be significantly better than the worst-case, as demonstrated in Example 1.\n\nThe authors then instantiate the ERM method based on the cell enumeration for linkage-based clustering and DP-based sequence alignment. The applications involve designing execution graphs, which originate from the execution tree of [BDL20]. Combining appropriate problem-specific execution graphs with the cell enumeration leads to the improved time complexity of ERM in several data-driven algorithm design problems, as in Table 1.", "questions": "1. I would like to know more intuition about how AugmentedClarkson differs from the original Clarkson and why it is important. \n2. While the paper focuses on linear boundaries, some studies on data-driven algorithm design consider parameter spaces partitioned by polynomials:\n\nhttps://proceedings.neurips.cc/paper_files/paper/2022/hash/db2cbf43a349bc866111e791b58c7bf4-Abstract-Conference.html\n\nhttps://proceedings.mlr.press/v178/bartlett22a.html\n\nhttps://proceedings.mlr.press/v206/sakaue23a.html\n\nIs there a possibility of applying similar enumeration ideas to such situations?", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The paper addresses the important problem of optimizing algorithm parameters in data-driven algorithm design. \n2. The theoretical results given in Table 1 appear strong compared with previous ones. \n3. The output-sensitive cell enumeration might be of independent interest in the context of computational geometry.", "weaknesses": "1. The paper would have been more appealing if implementations of the proposed methods and experimental results were provided.\n2. The paper is somewhat dense and it is not easy to follow the technical details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and insightful comments. Re experiments, we note that prior empirical work already suggests usefulness of output-sensitive guarantees on typical instances, which we elaborate below.\n\n``Experiments:``\nOur work is motivated from prior empirical research (lines 91-104) which indicate that the output cell size on typical problems is empirically much smaller than the worst-case cell size. The missing component is the development of algorithms with theoretical runtime guarantees which are output-sensitive, as previously proposed algorithms scale with the worst-case cell size. We expect implementation of our (LP-based) algorithm to be relatively straightforward, and would like to remark that there are no reasonable baselines known as previous algorithms were intractable.\n\n``Beyond linear boundaries:``\nWe agree that algebraic boundaries would be the next direction to look at based on our work. One simple way to apply our algorithms to the polynomial boundary case is to use linearization by projecting into a higher dimension corresponding to the monomials (this would work if the polynomials have a small constant degree e.g. Thm 3.1, Lem 4.1 in [1] or Lemma 2 in [2]). A more direct extension which tries to compute cells induced by polynomial boundaries in an output-sensitive way is an interesting direction for future work.\n\n``AugmentedClarkson:``\nClarkson’s Algorithm computes the set of non-redundant hyperplanes in a linear system in an output-sensitive time complexity. Intuitively, our augmentation additionally keeps track of the neighboring cells corresponding to the non-redundant hyperplanes to facilitate the breadth-first search over the cell adjacency graph. This is important as directly applying Clarkson’s and searching for the nearest cell (in a fixed direction) across each bounding hyperplane can add to the runtime complexity.\n\n*References*\n\n[1] Balcan, Maria-Florina, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. \"Structural analysis of branch-and-cut and the learnability of gomory mixed integer cuts.\" Advances in Neural Information Processing Systems 35 (2022): 33890-33903.\n\n[2] Balcan, Maria-Florina, Travis Dick, and Manuel Lang. \"Learning to Link.\" In International Conference on Learning Representations 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Our work is a first major step in making the growing field of data-driven algorithm design a practically feasible endeavor by addressing the frequently noted open question of computational complexity [1, 2]. Our proposed algorithms provide concrete and significant improvements in the running time of ERM from $n^{O(d)}$ (formally XP time) to $f(d).poly(n)$ effectively establish fixed parameter tractability (for parameter $d$, input size $n$, see Table 1) assuming output is polynomially large. Our work is well-motivated by prior empirical work on clustering and sequence alignment (lines 91-104) which show that typical output size is dramatically smaller than worst-case bounds, implying that our methods lead to dramatic speed-up over prior work on typical instances.

We have shown four different applications of our results (linear transition boundaries, constant number of parameters) in three different domains (data science, computational biology, computational economics), which is rare for algorithmic results that use the specific structure of the problem. We further expect more direct and indirect applications of our results [3, 4]. Technically, our work involves several novel ideas:
- Use of computational geometry in learning theory does not have precedent in the literature as far as we are aware. We identify and adapt the relevant techniques to address the crucial problem of implementing ERM in data-driven algorithm design.
- We develop novel techniques (execution tree and DAG) which are critical in addition to comp. geo. tools, e.g. directly using Clarkson’s algorithm would still lead to exponential time in $n$ but our techniques circumvent this.
- We present our results in a modular framework, reducing the ERM problem to a simpler problem that can be solved in a problem-specific way, making it easier to apply our results for future applications. 


*References*

[1] Rishi Gupta and Tim Roughgarden. Data-driven algorithm design. Communications of the ACM, 63(6):87–94, 2020.

[2] Avrim Blum, Chen Dan, and Saeed Seddighin. Learning complexity of simulated annealing. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1540–1548. PMLR, 2021.

[3] Balcan, Maria-Florina, Tuomas Sandholm, and Ellen Vitercik. "A general theory of sample complexity for multi-item profit maximization." In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 173-174. 2018.

[4] Balcan, Maria-Florina, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. "Structural analysis of branch-and-cut and the learnability of gomory mixed integer cuts." Advances in Neural Information Processing Systems 35 (2022): 33890-33903.

Meta-review: During the discussion, the reviewers unanimously acknowledged the conceptual contribution of the paper in pioneering a systematic study of the computational complexity of ERMs. The rebuttal helped clarify some initial concerns, further strengthening the case for acceptance. I recommend acceptance.
Decision: Accept (poster)