Coreset for Rational Functions
Authors: David Denisov
Ibrahim Jubran
Dan Feldman
Venue: Submitted to ICLR 2023 (2023)
Keywords: Coreset
Auto-regression
rational functions
non-convex optimization

Abstract: We consider the problem of fitting a rational function $f:\mathbb{R}\to\mathbb{R}$ to a time-series $g:\{1,\cdots,n\}\to\mathbb{R}$. This is by minimizing the sum of distances (loss function) $\ell(f):=\sum_{i=1}^n |f(i)-g(i)|$, possibly with additional constraints and regularization terms that may depend on $f$. Our main motivation is to approximate such a time-series by a recursive sequence model $F_n=\sum_{i=1}^k \theta_i F_{n-i}$, e.g. a Fibonacci sequence, where $\theta\in \mathbb{R}^k$ are the model parameters, and $k\geq1$ is constant.
For $\varepsilon\in(0,1)$, an $\varepsilon$-coreset for this problem is a small data structure that approximates $\ell(g)$ up to $1\pm\varepsilon$ multiplicative factor, for every rational function $g$ of constant degree.
We prove that every signal has an $\varepsilon$-coreset of size $O(n^{0.001}/\varepsilon^2)$, and provide a construction algorithm that computes it in $O(n^{1.001})$ time.
Open source code is provided, as well as extensive experimental results, on both real and synthetic datasets, which compare our method to existing solvers from Scipy.

Under review as a conference paper at ICLR 2023
CORESET FOR RATIONAL FUNCTIONS
Anonymous authors
Paper under double-blind review
ABSTRACT
We consider the problem of fitting a rational function g R - R to a time-series f (1. n2 + R. This is by minimizing the sum of distances (loss function) ((g) = : E (i) - g(i)l, possibly with additional constraints and regulariza- tion terms that may depend on g. Our main motivation is to approximate such time-series by a recursive sequence model G, Σ B e.g. Fibonacei sequence, where
R are the model parameters, and 2 is constant. For (0, 1), an E-coreset for this problem is data structure that approximates {gg) up to + e multiplicative factor, for every rational function g of constant degree. We suggest coreset construction that runs in O(n' +o(1)) time and returns such a coreset that uses O(no(1)E²) memory words. We provide open source code as well as extensive experimental results, on both real and synthetic datasets, which compare our method to existing solvers from Numpy and Scipy.
BACKGROUND
The original motivation for this work was to suggest provable and efficient approximation algo- rithms for fitting input data by a stochastic model or its variants, such as Hidden-Markon Models (HMM) Basu et al. (200T); y. McCallum et al. (2000); Murphy (2002) Park et al. (2012); [assi et al. 2020 Yu et al. 2010) and reference therein, Baysian Networks Acar et al. (2007 y Murphy (2002);
Nikolova et al. 2010); Rudzicz (2010) and reference therein, auto-regression Ghosh et al. 2013)
and Decision Markov Process Shanahan & den Poel (2010). Informally, and in the context of this work, model defines time series (sequence, discrete signal, time series) F [m]] - IR where [n] == {1.- ........ nn. and the value Ftt) at time (integer) 2 is a function of only the previous (constant) k > 1 past values F(t - 1), F(t - k) in the sequence, and the model's parameter 8.
1.1 AUTO-REGRESSION
Unfortunately, most existing results seem be based heuristics with little provable approxima- tion guarantees. We thus investigate a simplified but fundamental version, called auto-regression, which has provable but not so efficient solution using polynomial system solvers, after applying the technique of generating functions. This technique is strongly related to the Fourier, Laplace and s-Transfomm, as explained below. We define an auto-regression inspired by Ghosh et al. (2013); Eshragh et al. )2019); Yuan (2009), as follows:
Definition 1. A time-series F [n] + R is an auto-regression (AR for short) of degree k, if there
exist a vector of coefficients 0 = (0,
0x.) E Be such that F(1) = F(1-1)+...++ F0gFF 01 is called the characteristic polynomial of F.
The polynomial P(x) x² 0g
Substituting &- = 2, = (1, and F(1) = F(2) = in Definition 1)+ + F(t 2), where F(1) F(2) =
I yields the Fibonacci sequence,
L.e. F(I)= [(t)=([-- 1)
From Auto-regression to Rational functions. In the corresponding "data science version" of Fibonacci's sequence, the input is the time-series G(1), G(2), ... which is based on F with addi- tional noise. A straight forward method to recover the original model is by directly minimizing of the squared error between the given noisy time-series and the fitted values, as done e.g. in Eshragh et al. (2019)) using simple linear regression. However, this has major drawback; AR time-series usually grows exponentially, like geometric sequences, and thus the loss will be dominated by the last few terms in the time-series. Moreover, small changes in the time domain have exponential

---

Under review as a conference paper at ICLR 2023
affect over time, it makes more sense to assume added noise in the frequency generative function domain. Intuitively, noise in analog signals such as audio/video signals from an analog radio/tv is added in the frequency domain, such as aliasing of channels Nyquist (1928); Karras et al. (2011) Shani & Brafman (2004), and not in the time domain, such as the volume.
To solve these issues, the fitting is done for the corresponding generation functions as follows.
Proposition 1 (generative function Yuan (209)). Consider an AR time-series F' and its character- istic polynomial P(x) of degree k. Let Q(x) =x* +²) be the polynomial whose coefficients are the coefficients of in reverse order. Then, there is polynomial R(x) of degree less than is such
R(x)) that the generative function of F is f(x) == Ei=1 F(i)x*=1== Q(ay for every x E TR.
Inspired by the motivation above, we define the following loss function for the AR recovery problem
Problem 1 (RFF). Given a time-series g [n] + R and an integer 2 1, find a rational function
f: [n] IR whose numerator and denominator are polynomials of degree at most k that minimizes
Σ f(x) g(x)]-
Note that the loss above is for fitting samples from the generative function of noisy AR as done in Section 3.1 While we will focus sum of errors (distances), we expect easy generalization to qquared-distances. robust M-estimators and any other loss function that satisfies the triangle inequal- ity, up constant factor, in other coreset constructions [eldman (2020).
1.2 CORESETS
Informally, an input signal P consists of 2-dimensional points, a set Q of models, an approximation coreset C' is data structure that approximates the loss ((P.g) for every model q E Q. up to multiplicative factor of + e, in time that depends only on [C]. Hence, ideally, C' also much smaller than the original input P.
error E (0, 1), and a loss function
Coreset for rational functions. Unfortunately, similarly to Rosman et al. 2014). the RFF problem with general imput has no coreset which is weighed subset of the input; see Claim [ This was also the case e.g., Jubran et al. (202T). Hence, we solve this problem similarly to Rosman et al. (2014), which requires us assume that our input signal's first coordinate simply a set of consecutive integers, rather than a general set of reals. Even under this assumption there is no coreset which is a weighed subset of the input, or even a small weighed set of points; see Claim [ We solve this problem by constructing "representational" coreset that allows efficient storage and evaluation but dues not immediately yield an efficient solution to the problem as more commonly |Fllmaan 20200. For more explanation the components of this coreset see Section 1.4
commonlyFelddman
Why such coreset? A trivial use of such coreset is data compression for efficient transmission and storage. While there many properties of coresets mentioned at Feldman (2020), some of them are non-immediate from our coreset; see Feldman (2020) for a general overview that was skipped due space limitations. Nonetheless, since optimization over the coreset reduces the number of parameter, we hope that in the future there would be an efficient guaranteed solution (or approxima- tion) over the coreset. Moreover, since this coreset does support efficient evaluation, we hope this coreset would yield an improvement for heuristics by utilizing this fast evaluation.
1.3 RELATED WORK
Polynomial approximations. While polynomials are usually simple and easy to handle, they do not suffice to accurately approximate non-smooth or non-Lipschitz functions; in such cases, high order polynomials are required, which leads to severe oscillations and numerical instabilities Peiris et al. 2021I. To overcome this problem. one might try to utilize piccewise polynomials polynomial splines Northrop (2016); Nürnberger (1989): Sukhorukoval (2010). However, this results in a very complex optimization problem Meinardus al. (1989); (Sukhorukova & Ugon (2017).
Rational function approximation. A more promising direction would be to utilize rational func- tions for approximating the input signals, an example for this is Runge's phenomenon Epperson (1987) that resonates with Figure 4 in the appendix. Rational function approximation is a straight forward extension for polynomial approximations Trefethen (2019), yet much more expressive
2

---

Under review as a conference paper at ICLR 2023
due to polynomial in the denominator. A motivation for this can be found in the popular book Bu- lirsch et al.] (2002). A close relation between such functions and spline approximations has been demonstrated e.g., in Petrushev & Popovj (201I). Given an imput signal consisting of n pairs of points in R22 the rational function fitting (or RFF) problem aims to recover a rational function that best fits this input, as minimize some given loss function.
Hardness of rational function approximation. To the best of our knowledge, rational function approximation has only been solved for the max deviation case (where the loss the maximum over all the pairwise distances between the input signal and the approximation function) in Peiris et al. (22TT. Various heuristics have been suggested for other instances of the problem, see Peiris et al. with references therein.
2021
1.4 NOVELTY
The suggested coreset in this paper is very different from previous coreset papers. To our knowledge, this is the first coreset for stochastic signals. Most existing coresets are motivated by problems in computational geometry or linear algebra, especially clustering, and subspace approximation. Their input is usually a set of points (and not time series), with few exceptions e.g. coresets for linear regression Dasgupta al. (2009) that can be considered as type of hyperplane approximation.
Our main challenges were also very different from existing coreset constructions. A typical coreset construction begins with what is known as a-approximation or (a,, -pprooxxiiiiiiooon for the optimal solution that can be easily constructed, c.g. using Arthur & Vassilvitskii (2007); ; Feldman & Langberg (2011); Cohen et al. (2015). From this point the main change in these papers compute the sensitivity or importance of each point using the Feldman- Feldman-Langberg framework Feldman & Langberg 2011). The coreset is then non-uniform random sample from the input set, based on the
distribution of sensitivities.
However, in this paper, the sensitivity of point is simply proportional to its distance from (a, 3) -ppappooximttion. Therefore, the main challenge in this paper is to use our solver for rational functions, which takes time polynomial in n, to compute an efficient (a,, (8) ())appprxiimtion. We cannot use the existing sample techniques as in Feldman & Langberg (2011) since it might create too many "holes" con-eccnee sub-signals) in the input signal. solution for computing bicriteria for k-line segments was suggested in Feldman et al. (2012); Jubran et al. (2021) by partitioning the input signal into consecutive equal 2k sub-signals, so that least half of them would contain only a single segment, for every k-segmentation. In our case, k rational function cannot be partitioned into, say, O(k) linear or even polynomial functions.
Instead, we computed a "weak coreset", which guarantees a desired approximation for a constrained version of the problem; terms of constraints on both its input signal and feasible rational func- tions. We then combine this weaker coreset with merge-reduce tree for maintaining an (a, 3)- approximation, which is very different from the classic merge-reduce tree that is used to construct coresets for streaming data. This tree of height most log log n is also related to the not-so- common running time and space complexity of our suggested coreset.
We hope that this coreset technique will be generalized in the future for more involved stochastic models, such as graphical models, Baysian networks, and HMMs.
2 CORESET FOR RATIONAL FUNCTION FITTING
2.1 DEFINITIONS
We assume that l: 2 is an integer, and denote by TR the union of k-dimensional real column vectors. For every integer n. 2 O, denote [n] (1, ,n). For every vector (ci,... ck) R and a real number x E R. we denote by poly(c, = Ex= C: -11 the value of the polynomial of degree less than & whose coefficients are the entries of c at E R. For simplicity, we assume log(z) := log, (z). weighted set is a pair (P,w) w) where P C R² and w P - [0, xc) is a weights function. A partition (Pi,... Po} of set P c IRa is called consecutive if for every i E [0- - 1] we have min {a (z.y) E } > max {x (a, y) E P.). A query q E (R+)² 2 is pair of k-dimensional coefficients vectors. For any integer > 1 an n-signal is set P of
3

---

R to be the function that maps every pair Under review as a conference paper at ICLR 2023
ordered set of reals, (n. of a function [n] + R. A set c R2 is an interval of an n-signal if P {aa Nal, (a + (a+1)..)............)))))))).)). (b, yb)] for some b E [n]] such that a < b. The sets {a, a + 1,................ ............................... b} and (ya, Ua+l, " -bb are the interval's first and second coordinates, respectively. Given function as {a, f(a))... (b, (b)) }. The RFF problem is defined as follows. Note that the following
pairs (1). (n, yn)} in R2. Such an n-signal corresponds
discrete signal, or to the graph
IR - R. the projection of P onto is defined
definition of the rational function is inspired by Proposition
Definition 2 (RFF). We define ratio q (c,c') E (R*)² and any E IR
(R+)* 2
R
poly x)
i/ +
x- x pol.-ooly(,))) #0
ratio(g. = ratio =
+ x. poly(c',x)
x
otherwise.
For every pair (x,y) IR2 the loss of approximating (xr, y) via rational function is defined as D(g, (z. = ly ratio(q, z)). For a finite set P R2 we define the RFF loss of fitting to P as
((P.g)
D(a.))
Σ ly 1u-raate ratio(g,
pEP
(2.0)EP
More generally, for a weighted set (P, w) we define the RFF loss of fitting q to (P, w) as
E((P, w).9) = Σ ((p)
E (2.8)EP
w((x, yy ratiolq. x)
(1)
PEP
coreset construction usually requires some rough approximation to the optimal solution as its Unfortunately, we do not know how to compute even a constant factor approximation to the RFF problem in Definition 2 in near-linear time, but only in (2kn)0(k) time; see Lemma 8 Instead, our work is mostly focused on efficiently computing an (a,33 or bicriteria approximation as Fellman & Langberg (2011) defined at Section 4.2.
input; see Section 1.4
Definition 3 ((a, approximmat)) Let P be an interval of an n-signal. Let (P,,..., P3} be (P
consecutive partition of P, and " ,9 E (RR))² The set {(P1,91) ... (Pp. of 3 pairs is an (a, approoipxiiiaioonnn of P if
Σ ((P..)) a min ((P,
gE(RR)2
= the (a, 1) 1)-approximation = ((P1,41) is called an a-approximation. For every i E [3]
we denote by P the projection of P. onto and by U. Pf the projection of P onto B. We define the set of bicriterias of P as the union of all the (a', 88) apparooxxiatss P.
A coreset for the RFF problem defined follows. Similarly Rosman al. 2014) it includes an approximation to allow a coreset construction despite the lower bound from Claim I
Definition 4 (e-coreset). Let P C IR² be an n-signal, and let > 0 be an error parameter. Let B = ((Pi, (Pp, qa)} be bicriteria approximation of (see Definition 3 and let (C, w) be a weighted set. The tuple (B, C, w) is c-coreset for P. ifr every E (IR*) we have
((P.q) - ((C,,): - E(P'' Se SEE((P.)
(x,y) E P.) is the projection of P onto B. The storage where P : (s, ratio(g;, x:) | i (x, space required for representing such coreset is in O ((C) + 3k).
2.2 ALGORITHMS OVERVIEW
For less technical intuition for the algorithms Section J.4 the appendix.
4

---

Under review as a conference paper at ICLR 2023
For simplicity, in the following we consider k to be constant. The input to Algorithm I which is the main algorithm, is an n-signal P. and input parameters e, E (0,1/10), Its output, with probability at least 1 1- ö, is an e-coreset (B, C, w) of P with size in O (2) for constant 6.
As in Definition 4 the coreset consists of an (a, 9)- approximation B : ((P)).)),... , (Ps, {3}} } of the input set P. and weighted set (C, w.. The weighted set (C, w) consists of a small sample C C P and its weights function w C - (0, oo). As in Feldman et al. 2012). for every i E [8] the probability of placing a point (ar, E P, into the sampled set C' is Dist q, p). Hence, a point (z. y) E P whose y-value is far (not approximated well) from B would be sampled with high probability, but a point that is close to B will probably not be sampled. The weight wp) of point is inverse proportional to its probability to be chosen, so that the sum of distances to any query (rational function) is the same as its expectation.
Algorithm 2 coreset construction.
The rest of the algorithms aim to compute the (a, apprrooxximtii B.
Algorithm| 1 bi-criteria free construction. We compute B via balanced 3-tree, which is similar to the classic merge-reduce tree that is usually used to compute coresets for streaming data BBavveran al. [2020). However, the merge and reduce steps are different, well as the number of children in each node. Each leaf of this tree corresponds to a 1-approximation (i.e. optimal solution) for a consecutive set of B := O ((n'/loggog(()) input points, which is com- puted via Algorithm 5 Hence, there are ((n/3) leaves. An inner node in the ith level corre- sponds to an (at, approxxmmaniio of its |3 child nodes, it has O (8*) leaves and O (3++1) in- put points of its sub-tree, for every [e]. where & = [log log(n)) 1 is the number of levels n. Here, a; 3 B, 0(1)', and thus
in the tree; follows since (ne//og log log(n)) log log(n)
(a, 3) = (c)),3t) E (O(log(n)), lo)gg())) )())
Algorithm 3: the merge-reduce step. This step is computed in each inner node of the tree. For
an inner node in the ith level, where i E {2. .2....,,), ,{], the input is a set B of size B, where each B₁ E B is an (0, (0,r,)-an raprapppoxiiitioonn of P, (i.e. P3 is projected unto B,), where ,,. Ps is an
equally-sized consecutive partition of an interval of an n-signal P, and the output is bicriteria for
P; see Algorithm and Fig. This is by computing the following for every possible subset G C [3]
of size 3 - 6k + 3: (i) Compute {{,9G)} an a-approximation, for some a 2 1, for Uje, Py. (ii)
For each j E G set Ej := E(Pj. 9a) as the loss of 9G for P,. (iii) Set G' c G to be the union of the
6k 3 indices j G with the largest value lj. (iv) Set sa == Ejecror Ezi the sum of the losses E excluding the largest [g').
The final bicriteria approximation for the inner node is the one that minimizes 8G. among every subset g C B of child nodes above. More precisely, we take its part that approximates the union of [ 2|'"| children whose approximation error is 8y, and take its union with the 2| original (input) bicriterias that correspond to the child nodes (B) g) Ug The final approximation error in the inner node is thus the minimum of SG over every G C B of size 3 6k + 3.
Algorithm 4 restricted coresets for rational functions. Computing the a-approximation in Step (i) above can be done by computing the optimal solution, with details shown in Lemma 8 However, this would take n 0(1) and not quasi-linear time as desired. To this end, Algorithm 4 constructs restricted coreset for rational functions that is restricted in the following two senses: (i) It assumes that the input signal is projected onto a bicriteria approximation, which is indeed the case in Step
(i) of the merge-reduce step above. (ii) It approximates only specific rational functions, which are bounddde over the first coordinate of the input signal; see Definition
We handle the second assumption by removing the O(k) sets where the second assumption does not hold (via the exhaustive search described above). It should be emphasized that the final coreset construction has no such restrictions or assumptions for either its input or queries.
This restricted coreset is computed on each child node, so that in Step (i) above compute the a-approximation only on the union of [CI - |C"| coresets that corresponds to the chosen [C] |C'| internal nodes. The size of the coreset, that fail with probability at most e (0, 1/10), m O (llo (Sn/6))²) and thus the running time of our approximation algorithm (Algorithm
o(1), which is in O (no())) for every constant 5 > O. Algorithm computes this restricted coreset by: (i) Partitioning the input into chunks of exponentially increasing sizes; see Fig. 5 (ii)
5

---

Under review as a conference paper at ICLR 2023
Computing sensitivity based sub-sample for each chunk. (iii) Returning the union of those coresets after appropriate re- wewigghtinng
As show in the proof, the sensitivity for the RFF inside each chunk can be reduced to the sensi- tivity of the polynomial fitting problem, which was previously tackled; see Corollary 2
2.3 ALGORITHMS
From bicriteria to sampling-baser coresets. In Feldman et al. (2012) sampling based coreset construction algorithm was suggested for the k-segments problem. This algorithm requires as input an (a, -ppapoooxnniionnn
defined above. With some modifications to this algorithm, we can effi- ciently construct a coreset for the RFF problem. The missing part is a bicriteria approximation for the RFF, which is the main focus and main contribution of this work.
Optimal solution (a = 3 = 1) in polynomial time. Using polynomial solvers, and previous work (see e.g., Marom & Feldman (2019) with references therein) it can be proven that given set P of n points on the plane, we can compute the optimal fitting rational function to the point, i.e., the
rational function that minimizes Equation at Definition 2 in (2kn)0(k) O(k) time; see Lemma 8
Efficient (1, approximation for large B. Using the polynomial time optimal solution above, we can compute an ( apprrxxximtionnnn to n-signal P. for a large 3. This is by partitioning the input into many (3) small subsets, and apply the optimal solution to each subset, which
relatively fast each set is very small, more precisely n=((k33)) see Algorithm for suggested implementation, note that there corresponds to n/8 at this paragraph.
Algorithm 1: CORESET k e, 8); see Theorem
Input : An n-signal P, an integer l 2 1, and constants e, E (0, 1/10]-
Output: tuple (B, C, w), where B is bieriteria approximation of P, and (C, w) is
weighted set.
1 =
2/ log(log(n)) ; = [n/31; = 6k 3
Set c*
2 1 to be a constant that can be determined from the proof of Theorem
kn
λ =
c² c²(4h+1p (igk+1ph
2.2 +)
k2 1og((44-113 + + + log
B (B,..., B|B) BATCH-APPROX( / see Algorithm
while X 2, do
Set { By, ,., B
to be partition of B into equally sized consecutive sets, each of size 1 E [3. 2,3.. a power of 2; i.e. B. = (Ba," Batyl for some a E [[]]] and every i [B/ Set B; = REDUCE(B AI, A) for every i E [1,.... J see Algorithm // We reduce every set in the partitions B.
/
B = =(B, (BI,..., Bb)
B' (BI.-. B // B' is (un-ordered) set.
10 B = REDUCE(B' ,Y,,).
A2= z log(n): (k² (12 + log (7))
(B. (BC.ww) = SAMPLE (B, // see Algorithm
13 return WB.C.)).
The following theorem proves the correctness of Algorithm 1 See Theorem 5 full proof.
Theorem 1. Let P be an n-signal, for n that a power 2, and put c, (0, 1/10], Let (B, w) be the output of call to CORESET P, k 8); see Algorithm 7 With probability at least 1 - 6,
(B, C, w) is an e-coresel of P; see Definition 4 Moreover, the computation time of (B, C, w) is in
201k²) n ((k)/ log log(n) log(n) (oglo(())) loo(l//))) 1og(1/8)0(k)
and the memory words required to store (B, C, w) are in (2k) log(n) (n) 001) log (l/ In particular, if and 8 are constants a running time of (a(1)) and the space is in O (1) (1))))

---

Under review as a conference paper at ICLR 2023
Q5
Qu
Qo
Q10
21
Q12
Q14
2is
115
10
P1
P3
P3
Pg
Pg
Piu
P11
Py2
Pas
P1s
Pis
P1o
(3
P())
(8)
(1)
2
(
Figure 1: Illustration for Algorithm 1 (Top) In Line 4 an input n-signal P (black ticks and
red dots) and its partition (P,, Pio) into 1o 16 sets via a call to Algorithm 5 This call also computes (1, apprroopooini B; = ((P:,Q.) for every P: (green curves), see Def-
inition 3 In Line 6 the set {Bi...., Bis} is partitioned into B Bi B₁ U B2 B4, where each such set contains 4 elements from B. (Middle) In Line 7 for every E [4] we set
B, = {P(") o!!)
(P! Bill Q! )! as the output of call to REDUCE(B)). For every
i E [3] the projection of every U Bdl p(i) onto B, is denoted in green. (Bottom) The process above repeated, with B == (B1; B2, B3, Ba). B is therefore partitioned into sets of size B 4, i.e., only such set B, and then REDUCE( B) is called, which reduces the size of B to 5.
3 EXPERIMENTAL RESULTS
We implemented our coreset construction from Algorithm [ in Python 3.7 and in this section evaluate its empirical results, both on synthetic and real-world datasets. More results are placed in the supplementary material; see Section [ Open-source code can be found in Code (2022).
Note that since it is non trivial how to accelerate the computation of the optimal solution using the coreset will focus on the quality of the compression, similarly video compression analysis.
Hardware. We used a PC with an Intel Core i7-10700, NVIDIA GeForce GTX 1660 SUPER (GPU), and 16GB of RAM.
The gap between theory and practice. In practice, we apply two minor changes to our theoretically-provbble algorithms, which have seemingly neglectable effect on their output quality, but aim to improve their running times. Those changes are: (i): Line I1 of Algorithm computes the query with the smallest cost (((S, w).r) over every r E R x R$ Instead, to reduce the com- putational time, iterate only over the queries in PAST-CENTROID-SEET (S, 64); see Algorithm 6 (ii): Line of AlgorithmB 5 computes, for every P; C R defined Algorithm 5 the query with the smallest cost rP.,r) over every r g* R Instead, to reduce the computational time, for every such Pi., iterate only over the queries in FAST-CENTROID-SETTE
64); Algorithm 6 (iii) At Line 11 of Algorithm 4 the set S was sampled from Pi an interval of an n--ignal, where each point (I, E P was sampled with probability 8'(x). We observed, in practice, that the probabil- ities assigned by s' were sufficiently close to 1/|P/| for most of the points. Hence, to reduce the computational time, we sampled the set S uniformly from P.¹
Global parameters: We used the degree k = 2 in our experiments, since seemed as sufficiently large degree to allow visually pleasing approximation as seen, for example, in Figure I
Competing methods. We consider the following compression schemes: (i): MFF-coreset (P, A) The implementation based on Algorithm I where we set B 32, 3 32, '1 32, and A 0.
7

---

Under review as a conference paper at ICLR 2023
(ii:: FRFF-corese A heuristic modification to REF-coreset above, where the call to REDUCE at Line of Algorithm[]ia replaced with a call to FAST-CENTROID SET; see Algorithm This should boost the running time by slightly compromising accuracy.
(iit): Gradient (P, A rational function q E (B+)² was fitted to the input signal via
scipy.optimize.mmmiie minimiie with the default values, where the function minimized is q(P, and the starting position is {o}* x {0}². Then, a coreset was constructed using the provable algorithm
SAMPLE-CORESET/( ([ ,)).)).
(iv): Cor (P. A rational function q E arg o paXper D(p, q') was com- puted based on Peiris ct al. (2021). Then, a coreset was constructed using the provable algorithm SAMPLE-CORESET
(v): RandomSamplle (vi): NearCorvexCoreset(.... X) The coreset construction from Tukan et al. (2020). chosen to be of size 1.5 X.
returns uniform random sample of size 1.5 À from P.
Coreset size. In all the following experiments, for fair comparison, the input parameters of all the competing methods above were tuned as to obtain an output coreset of the same desired size. Note that there can be small noise in the sizes due to repeated samples of the same element.
Repetitions. Each experiment was repeated 100 times. All the results are averaged over the tests.
Evaluation. The quality of given compression scheme (from the competing methods above) is defined as E()) = 100 1 where l' is the loss in Equation when plugging in the compression and some query q, and é is the same loss but when plugging the Full input signal and the same query q. We tested couple of different options for such query q: (i): as it is hard to compute the optimal solution q² which minimizes Equation [ we sampled a set Q of 1024 queries using Algorithm 6 and recovered the query y Q which has the smallest loss over the full data. This query aims to test the compression accuracy in a near-optimal scenario. We then presented E(q) for the q above. (ii): For every individual compression scheme, we picked the query in q E Q. which yields the largest value for (q); i.e., the least satisfied query.
3.1 SYNTHETIC DATA EXPERIMENT
In this experiment, we aim reconstruct given noisy homogeneous recurrence sequence's explicit representation, as explained in Section (specifically, see Definition I
and Proposition I..
Dataset. Following the motivation in Section D the data (n-signal) P we used in this test is simply a set of n values [F(x) x = j/n 1/2.j j E [n]} of the generating function of a noisy Fibonacci series, i.e., F(x) = E 8:+1 x²) where s; is the i'th element in the Fibonacci series with Gaussian noise with zero mean and standard deviation of 0.25.
Results. Fig. 2 presents the results, along with error bars that present the 25% and 75% percentiles.
3.2 REAL-WORLD DATA EXPERIMENT
In this experiment we consider an input signal which contains readings of some quantity (c.g., temperature or pressure) over time. We aim to fit rational function to such signal, with the goal of predicting future readings and uncovering some behavioral pattern.
Dataset. In this experiment we consider the Beijing Air Quality Dataset Chen 2019) from the public UCI Machine Learning Repository AAsuncion & Newman (2007). The dataset contains n 7344, 8760, 8760, 8784 readings, respectively for the years 2013 to 2016. Each reading contains "the temperature (degree Celsius, denoted by TEMP), pressure (hPa, denoted by PRES), and dew point temperature (degree Celsius, denoted by DEWP)". For each year and property individually, we construct an n-signal of the readings over time. Missing entries were replaced with the average property value. Fig. presents the dataset readings along with rational function fitting algorithm and Scipy's 's rational function fitting. The Italy Air Quality Dataset Vito (2016) is also tested; see Section 1.2 in the appendix.
Results. Fig. presents the results for the year 2016, along error bars that present the 25% and 75% percentiles. Graphs for other years along with results for dataset Vito 2016) are placed in Section
8

---

Under review as a conference paper at ICLR 2023
Corweents siee.. 107
Copeset's Site
Coneset's Ste
751
duriee
Qureaje
dur-sge
Cormet
0.
12.0
125
133
12.5 340
16.3
12.5
335 335 340 545
35.
16.
12.0
123
535
140
545
15.3 25.3 16.0
Coosaat's
Corseetss 522
Consect 2632.
Ourtr
Cy-tre
qui
160
Gradees
15
Gidder
Grdder
L-Coeest
CoComet
LyCo
TasdenSarph
Sendar
15.
125
215
240
145
15.0
15.5
16.1
126
1255
220
225
240
155
16.6
12.0 22.
14.0
245
15.3
Figure 2: Results of the experiment from Section 3.1 logarithmic scale, the size of the input signal, and the Y-axis presents the approximation error of each compression scheme, for given compression sizes of 382 and 2824 respectively. The upper and lower rows present Evaluations (i) and (ii) respectively. (Right): The computational time for each of the two coreset sizes. The evaluation method does not affect those times.
(Left + Middle): The X-axis presents, on
The piot by DRWP your 2015.
The sict foe PGES for yeur 2015
The plst the TEMP your 2016.
Ountpr
Ourrry Our repe
Our mate
Nerdsndenple
Aanderiarntte
TandordaTck
Commers cibe angraldees
Corsects slee percention cripiol
COMMUTT.ONN anggiaaida
DEWP yoar 2016.
p for FRES yor 2016.
poe you
-+- GunEET
QueliT
Carmeet Randendarple
toreict Randerdarata
100
50
2.55
9.30
2.22
3.30
2.38
E00
0.10
6.35
325
0.25
6:50
2.25
3.35
3.15
0.35
0.39
Figure 3: Results of the experiment from Section 3.2 sion percentage from the original data, and the -axis presents the approximation error of cach compression scheme. The top and bottom rows present Evaluations (i) and (ii) respectively.
The X-axis presents the size of
the compres-
3.3 DISCUSSION
Fig. 4 demonstrates that rational function fitting is more suitable than polynomial fitting, for a rela- tively normal dataset. It also shows that computing any of those fitting functions either on top of the full data our coreset produces similar results. Lastly, Fig. (2 and demonstrate that method and its variants achieve, almost consistently, better approximation quality in faster time, as compared to most of the competing methods; the only faster methods were the uniform sample and gradient which yielded sigmificantly worse results. For more in depth discussion see Section J which is at the appendix due space limitation.
FUTURE WORK AND CONCLUSION
This paper provides coreset construction that gets a time-series and returns small coreset that approximates its sum of (fitting) distances to any rational functions of constant degree, up to factor of 1 + c. The size of the coreset is sub-linear in n and quadratic in 1/c. Our main application is fitting to Rego-Regresnion model, whose generative functions are rational. While we focused on sum of errors (distances), we expect easy generalization to squared-distances, robust M-estimators and any other loss function that satisfies the triangle inequality, up to constant factor, as in other coreset constructions. We believe that the new suggested technique initializes a line of research that would enable sub-linear time algorithms with provable approximation for more sophisticated stochastic models such mentioned at the start of the paper in Section D

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
To the best of our knowledge, there are no ethical concerns for our work due to the following:
The work of theoretical nature that aims to develop efficient coresets for rational func- tions (and approximation is major part of the contribution).
All the datasets which we tested our methods on where from the public UCI Ma- chine Learning Repository Asuncion & Newman (2007), and more precisely Vito (2016)
and Chen (2019)
REPRODUCIBILITY STATEMENT
In all our tests we included error bars, hardware used, global parameters, dataset (citing existing data or generalization method) and the paper contains full pseudo-code for all the Algorithms. Where there were assumptions on the data they were stated explicitly.
As stated in Code (2022), the authors commit to publish the code for all of the tests (or part of them) upon acceptance of this paper or reviewer request.
10

---

Under review as a conference paper at ICLR 2023
REFERENCES
Umut A Acar, Alexander Ihler, Ramgopal Mettu, and Ozgür Sümer. Adaptive hayesian inference. In Neural Information Processing Systems (NIPS), volume 10, 2007.
Martin Anthony and Peter L Bartlett. Neural Network Learning: Theoretical Foundations, Cam-
bridge University Press, 2009.
David Arthur and Sergei Vassilvitskii. K-means++: The advantages of careful seeding. Proceed- ings of the Eighteenth Annual ACM-SIAN Symposium on Discrete Algorithms, SODA '07, pp- 1027-1035, USA, 2007. Society for Industrial and Applied Mathematics. ISBN 9780898716245.
Arthur Asuncion and David Newman. UCI machine learning repository, 2007.
George A Baker Jr. The theory and application of the padé approximant method. Technical report, Los Alamos Scientific Lab., Univ. California, N. Mex., 1964.
Sumit Basu, Tanzeem Choudhury, Brian Clarkson, Alex Pentland, et al. Learning human interactions with the influence model. In Neural Information Processing Systems (NIPS), 2001.
Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou. New frame- works for offline and streaming coreset constructions, 2020.
Roland Bulirsch, Josef Stoer, and Stoer. Introduction to numerical analysis, volume 3. Springer, 2002.
Song Chen.
Machine Learning Repository, 2019. URL httpss://rrchive-beeet ics uci http.eeemmm/aaatts////aaaae jingt mu mu iigtiiis
Beijing Multi-Site Qir-Quality Data. UCI
Code. Open source code for all the algorithms presented this paper, 2022. the authors commit to publish upon acceptance of this paper reviewer request.
Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation. Proceedings the 2015 Conference on Innovations in Theoretical Computer Science, pp. 181-190, 2015.
Michael B. Cohen, Yi Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pp. 938 942, 2019. ISBN 9781450367059. doi: 10.1145/3313276.
3316303. URL htt.tttt/////oo org 10. 1ee.11115313121 33163033 6303
Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W Mahoney, Sampling algorithms and coresets for Ep regression. SIAM Journal on Computing, 38(5):2060-20) 2078- 2009.
James F Epperson. On the runge example. The American Mathematical Monthly, 94(4):329-34 341, 1987.
Ali Eshragh, Fred Roosta, Asef Nazari, and Michael W. Mahoney. Lsar: Efficient leverage score sampling algorithm for the analysis of big time series data, 2019.
Dan Feldman. Core-sets: Updated survey. Sampling Techniques for Supervised or Unsupervised Tasks, pp. 23 44, 2020.
Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 569-578, 2011.
Dan Feldman, Cynthia Sung, and Daniela Rus. The single pixel gps: Learning big data signals from tiny coresets. In GIS: Proceedings of the ACM International Symposium Advances in Geographic Information Systems, pp. 23-32, 2012. doi: 10.1145/2424321. 2442425..
Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant- size coresets for k-means, pea and projective clustering. In Proceedings the twenty-fourth annual ACM-SIAM SIAM symposium on Discrete algorithms, pp. 1434-1453 Society for Industrial and Applied Mathematics, 2013.

---

Under review as a conference paper at ICLR 2023
Dan Feldman, Zahi Kfir, and Xuan Wu. Coresets for gaussian mixture models of any shape. CoRR, otw.iiioorrr/oooooooo abs/1906...11.. 04895
abs/1906.04895,, 2019. URL
Saurav Ghosh, Theodoros Rekatsinas, Sumiko R Mekaru, Elaine O Nsoesie, John S Brownstein, Lise Getoor, and Naren Ramakrishnan. Forecasting rare disease outbreaks with spatio-temporal topic models. In NIPS 2013 Workshop Topic Models, Lake Tahoe, NV, USA, 2013.
Sariel Har-Peled and Micha Sharir. Relative (pegssloo)-apppoxximattosss in geometry. CoRR, abs/0909.0711 2009. URL
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kem, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre
Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant, Ar- ray programming with NumPy. Nature, 58577825)3357-362 September 2020. doi: 10.1038/ 15586-020-2649-11 URL https://ao.. wwtpor//oo......
2649-2
R. A. Horn and C. R. Johnson. Matrix analysis. UK: Cambridge University Press, pp. 146-147, 1999.
Ibrahim Jubran, Ernesto Evgeniy Sanches Shayda, Ilan Newman, and Dan Feldman. Coresets for decision trees of signals. In Neural Information Processing Systems (NIPS), volume 34, pp- 10322-30364, 2021.
Tero Karras, Miia Aittala, Samuli Laine, Erik Härkönen, Janne Hellsten, Jaakko Lehtinen, and Timo Aila, Alias-free generative adversarial networks. In Neural Information Processing Systems (NIPS), volume 34, 2021.
Yi Li, Philip M. Long, and Aravind Srinivasan. Improved bounds the sample complexity of learning. J. Compul. Syst. Sci., 62(3)-516-527, May 2001. ISSN 0022-0000. 2000.1741. URL htlL:tt::/// doi www.doo.ooorroo www.oogg///..
doi: 10. 1006/Jsss...
wwtp://.......ee..eeeeee 10w.:/000.ssss.. wwt.ecsss....... 2000. 1741
Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. Training gaussian mixture models scale via coresets. The Journal of Machine Learning Research, 18(1):5885-590 2017.
Yair Marom and Dan Feldman. k-means clustering of lines for big data. CoRR, abs/1903.06904, 2019.
06904
Andrew McCallum, Dayne Freitag, and Fernando CN Pereira. Maximum entropy markov models for information extraction and segmentation. In leml, volume 17, pp. 591-598, 2000.
Günter Meinardus, Günther Nürnberger, Manfred Sommer, and Hans StrauB. Algorithms for piece- wise polynomials and splines with free knots. Mathematics of computation, 53(187):235-277, 1989.
Kevin Patrick Murphy. Dynamic bayesian networks: representation, inference and learning. Uni- versity of California, Berkeley, 2002.
Arnold Neumaier. Introduction to numerical analysis. Cambridge University Press, 2001.
Olga Nikolova, Jaroslaw Zola, and Srinivas Aluru. A parallel algorithm for exact structure learning of bayesian networks. In Neural Information Processing Systems (NIPS), 2010.
NIST/SEMATECH. e-handbook of statistical methods. htm 2021.
https: wwwpw/wwww/mmmmmmmm itl. nist. gov/
J. Nocedal and S. Wright. Numerical Optimization. Springer Series in Operations Research and
Financial Engineering. Springer New York. 2006. ISBN 9780387400655. URL httpp:///
books wwwpss..ooll..... co. bppogle.cc.../ooooksiidd.o wtlboookk//oeeoooooooellllllll
Robert B Northrop. Signals and systems analysis in biomedical engineering. CRC press, 2016.
12

---

Under review as a conference paper at ICLR 2023
Günther Nürnberger. Approximation by spline functions, volume 1. Springer, 1989.
Harry Nyquist. Certain topics in telegraph transmission theory. Transactions of the American Insti-
lute of Electrical Engineers, 47(2):617-644, 1928.
Hyunsin Park, Sungrack Yun, Sanghyuk Park, Jongmin Kim, and Chang Yoo. Phoneme classi- fication using constrained variational gaussian process dynamical system. In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger (eds.), Neural Information Processing Systems (NIPS), volume 25, 2012. URL
Peiris, N. Sharon, N. Sukhorukova, and Ugon. Generalised rational approximation and its application to improve deep learning classifiers Applied Mathematics and Computation, 389 (C), 2021. doi:
2020. 125560. URL lttttts::://ddee wtwpse/....c.....eeeeeeeeeeee
html
K. B. Petersen and M. S. Pedersen. The matrix cookbook. URL hOLp:ttt://ww http:::/wwwwww...p....ee.te
dk/pun htt/pubbb/pubb//// /2tp://pppb/32/4/ 3274- - full full.html Version 20121115.
Penco Petrov Petrushev and Vasil Atanasov Popov. Rational approximation of real functions. Num- ber 28. Cambridge University Press, 2011.
Andrea Pizzo, Alessio Zappone, and Luca Sanguinetti. Solving fractional polynomial problems by polynomial optimization theory. IEEE Signal Prucessing Letters, 25(10):1540-154, 2018.
Guy Rosman, Mikhail Volkov, Dan Feldman, John W Fisher III, and Daniela Rus. Core- sets for k-segmentation of streaming data. In 7. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (eds.), Neural Information Processing Systems (NIPS), volume 27, 2014. URL Intps:://proceddingg neurips.eeppp.... cc wwt.:eis....ppppe////...... cctppapetr/211////1e boa22eelee00333885511ddd0------2 Pape pdf
Frank Rudzicz. Learning mixed acoustic/articulltory models for disabled speech. In Neural Infor-
mation Processing Systems (NIPS), pp. 70-78, 2010.
Imad Sassi, Samir Anter, and Abdelkrim Bekkhoucha. A new improved baum- baum-welch algorithm for unsupervised learning for continuous-time hmm using spark. International Journal of Intelligent Engineering and Systems, 13(1):214-223 2020.
J Shanahan and D den Poel. Determining optimal advertisement frequency capping policy via markov decision processes maximize click through rates. In Proceedings of NIPS Workshop: Machine Learning in Online Advertising, pp. 45, 2010.
Guy Shani and Ronen Brafman. Resolving perceptual aliasing in the presence of noisy sensors. In Neural Information Processing Systems (NIPS), volume 2004.
Nadezda Sukhorukova. Uniform approximation by the highest defect continuous polynomial splines: necessary and sufficient optimality conditions and their generalisations. Journal of opti- mization theory and applications, 147(2):378-394, 2010.
Nadezda Sukhorukova and Julien Ugon. Characterisation theorem for best polynomial spline ap- proximation with free knots. Transactions of the American Mathematical Society, 369(9):6389- 6405, 2017.
Joseph Miller Thomas. Sturm's theorem for multiple roots. National Mathematics Magazine, 15(8): 391-394, 1941.
Lloyd N Trefethen. Approximation Theory and Approximation Practice, Extended Edition. SIAM, 2019.
Murad Tukan, Alaa Maalouf, and Dan Feldman. Coresets for near-convex functions, 2020.
13

---

Under review as a conference paper at ICLR 2023
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Courna- peau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nel- son, Eric Jones, Robert Kern, Eric Larson, C Carey, Ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, António H. Ribeiro, Fabian Pedregosa, Paul van Mul- bregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272 2020. doi: 10. 10.1038/s4
Saverio Vito. Air Quality. UCI Machine Learning Repository, 2016. URL https://
archive- beteebeeaaa.... ics. uci eduu /ttp://m//dataatttt//rrgr-u..la
David H. Wolpert. The Lack of Priori Distinctions Between Learning Algorithms. Neural Com-
putation, 8(7):1441-1399 10 1996. ISSN 0899-7667. doi: 00.1162/nec0.1199.877113333 URL
199.......99........
D.H. Wolpert and W.G. Macready, No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):67-82, 1997. doi: 10.1109/2355588889)
Dong Yu, Deng, and George Dahl. Roles of pre-training and fine-tuning context-dependent dbn-hmms for real-world speech recognition. In Proc. NIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2010.
Qiaochu Yuan. Topics in generating functions, pp. 22-23, 01 2009.
14

---

Under review as a conference paper at ICLR 2023
Appendix
Table of Contents
Additional motivation for RFF
16
B
Additional algorithms
16
B.1
Sample based on a bicretiria approximation algorithm
16
B.2
From larger to smaller values of 3
17
B.3
Computing an (a, apppoxxxinitoooon with Large algorithm
20
B.4
Fast practical heuristic
21
C
Algorithm 2
Coreset given (o. apappooxiiaiinnnnn
22
C.1
Bound on the dimension of the query space
22
Sensitivity of functions
23
Analysis of Algorithm
SAMPLE-COR CORESET
24
Lower bound.
25
D
Inefficient solver for the RFF problem
26
E Coreset under constraints; Analysis of Algorithm
29
E.1 Upper bound on the polynomial-titue sensitivity
29
F.2 Upper bound on the RFF sensitivity
29
E.3
Correctness of Algorithm|4] proof of Lemma
31
Combining (a, apaapooxxiiiinnnnn Analysis of Algorithm 3
34
G
Algorithm ! Streaming
37
H Fast practical heuristic; analysis of Algorithm
39
I1.1
Fitting plane to points
39
H2 SOLVER computation; see Detinition
................................
42
Analysis of Algorithm
MAST-CENTROID-SET
................................
44
Full results for real life data tests
45
Full results for the test over the dataset Chen (2019)
45
Test for the dataset [2016]
47
Additional discussion
49
J.1
Fig.44
49
1.2
Section 3.
49
J.3
Section |
49
Discussion on the theoretical resu
50
15

---

Under review as a conference paper at ICLR 2023
A ADDITIONAL MOTIVATION FOR RFF
In the following figure we demonstrate that in some cases rational functions can yield better approx- imations than polynomials, this is essentially variation of the known Runge's phenomenon Ep- person (1987). We do not use a rational function, that is commonly used to demonstrate Runge's phenomenon Epperson (1987), since upon existing solvers, and if all the points are exactly on rational function existing rational inter- polation methods can solve this case as well; for example Padé approximant mentioned in Baker (1964) or rational function fitting for max deviation as mentioned in Peiris et al. (202T).
also want demonstrate the superiority of our methods
While rational functions can give better fitting than polynomials some cases the same also holds for polynomials, where at some instances polynomials would yield a significantly better fitting, For an example where the polynomial fitting yielded better results than our methods see Figure and with discussion at Section 13..1
Figure 12
3000
3000
2500
Poly-fit
2500
Poly-fit
Gradient
Gradient
2000
Durs
2000
Ours
1500
1500
1000
1000
500
500
0
0
1000
2000 X
3000
4000
1000
2000
3000
4000
Figure 4: RFF illustration. A time-series (xx 2/5512 over {1, ... ,22] in red, which is de- noted by GT. an abbreviation of ground truth. The goal is to approximate it via: (black) a rational function computed using our algorithm FRE PREF-coreset from the Experimental Results (see Sec- tion 3. (blue) rational function computed using the Scipy. paiipy.ppe opt mi ze m nimi ze which aims to minimize the same RFF loss as in Equation [] and (green) polynomial of degree 3 computed using the numpy. polyfit function, which minimizes the sum of squared distances between the polynomial and the input. For fair comparison, all three methods have been allowed free param- eters. (Left): All 3 methods applied to the original signal. (Right): A coreset of size 10% of the input was first computed for the given signal via Algorithm| [ Then, all methods were applied on the coreset points only. The error bars are from 10 experiments.
B ADDITIONAL ALGORIHHM
B.1 SAMPLE BASED ON A BICRETIRIA APPROXIMATION AL.GORITHM
Algorithm gets as input a bicretiria approximation of the RFF problem for some given input n- signal P; see Definition 3 The algorithm utilizes this rough approximation in order to compute, in linear time, an (-coreset as Definition via sensitivity sampling. The formal statement given in Lemma T This algorithm is modified version of the algorithm presented for the k-segments problem in Feldman al. (0122).
The following lemma states the desired properties of Algorithm 2 see Lemma 6 for its proof.
Lemma 1. Let B = (PP q1) (.................... (Pa,qa) be an (a, apppprooxnnnaooon of some n-signal foror some a > O; see Definition Put e, (0, 1/10), and let
c* (a + (k2 log(a +1 log(1/6))
where c* 2 1 is a constant that can be determined from the proof. Let (B, C, w) be the output of call SAMPLE- CEW.F---OOREE/EEE X); Algorithm Then, Claims (i)-(i) hold as follows:
16

---

Under review as a conference paper at ICLR 2023
(i) (B,C,w) can be stored using O (A + 3k) memory.
(ii) With probability at least 1 - ò, we have that (B, C, w) is an e-coreset of P; see Definition
Algorithm 2: SAMPLE-CORESET (B, A); see Lemma
Input
bicirteria approximation B : {(P), (1,, (P of some resignal P; see
Definition 3 An integer À 2 1 for the sample size.
Output: tuple (B, C, w), where B is a bicriteria approximation of P, and (C, w)) is weighted set.
Σ ((P.. i=1 if iee {0, )o) then
Let w: : R² + {0} such that for every E IR² we have w(p) = 0.
return (B.
s(p) (gc, p)/c for every i E [8] and every p E P:.
Pick sample S P of points from where S multi-set and each point p E S is sampled i..dd with probability s(p); observe that there might be repetitions in S. Set r(p) as the number of repetitions of p the multi-set S, for every p P.
w(p) := r>rp)/(A ((psspp))))))))))))))))())))(( for every p S.
S" = ((,,roatio ratio(q, x)) i E [8], () P,nS) // project the labels of every set P. Ens S onto qi and take their union.
10 for every f1,....... ,8 do
11 w (a,ratio(q;; x)) == w(p) for every p SnP,
12 C C SUS"
a return (B, (B,C.u)
B.2 FROM LARGER TO SMALLER VALUES OF |
In this section, we show how, given an (a,, appp)xaappooiiiaiioon with large 3, we can recover an (a', ( "aprrxxmmttionn with 3 B but larger a' > This is achieved by computing ap- proximation to the projection of the set points approximated by the (a, aappooo-ppooinniionnn onto the (a, pppppppoxiiiiiinns This is implemented in Algorithm which utilizes Algorithm 4
To efficiently compute the previously stated bicriteria we will utilize restricted coresets. It should be emphasized that the final coreset will not contain such restriction. One of the limitation the restricted coresets will involve the following definition.
Definition (p-bounded function). For every X C R. [1, oo), and any (c,d)) E (R²)² we say that (c, d') is p-bounded over X if and only if
max f(x) X
S P.
min fxx) x
where the function f -> IR maps every x E to f(x) 1 11+a (ol-polyyye,))
Overview of Algorithm 3 The imput for the algorithm is P interval of n-signal which is projected onto some set of (a, 3 approoxxiiais This projection is represented by the set B, where each element B, E B is (0, 9) -approximation for some P,, and Pi.... P(B) is consecutive partition of P. The algorithm also receives parameter which control the size of the output, and a parameter 8 which control the trade-off between the running time and robustness. The algorithm returns B' bicriterai of P, where the size of B' smaller than | B The algorithm runs in ((P()))(()) [+((1) time. This (a, appapopooinnnooonn is computed as mentioned in Section 2.2
17

---

Under review as a conference paper at ICLR 2023
Algorithm 3: REDUCE X, A); see Lemma
Input A set B := [Bi,... B3), where each B; E B is an (0) appppooooinnnnooonn of P., i.e. P, projected unto B, and (Pi,... P3} } is an equally-sized consecutive partition of
P. some interval of n-signal; see Figure 6 and Definition 3 Integers À 2 1 and
0.
Output: A bicriteria approximation B' of P; see Definition B
8
e" 00; B' U
B,
;=1
for every B, do
Identify , ((()) 1 B,
for every B()) E B, do (5 ((()
MINI-REDUSE
see Algorithm
for every set G C (1,... .... 33 of size |G| 3 A do
So = Q.
for every E G and B( E B, do
Set wc(l) := w (6) (p) for every p S
S = Sa U()))
10
Set 9G E min ((SG, wc), q): see Definition 2 and Lemma 8 NE(RR)2
11
12
for every i G do 4 = ((P;, Set G' c C to be the union of the 6k - 3 indices i E G with the largest value C, Ties
14
broken arbitrarily.
15
if
Cieoroo (i) < then
== -EErGrror fs) // update smallest loss
16
Set (Ri,...,, to be the smallest partition of G G' such that for every E [>] we have G" n [min (R),, max(R.) 0, and for any i,j [7]. where
n
have
R n (R.). max(R;)] =
// Via simple greedy partition; see Fig
P. {(., ratro((((), (I, E P.)) for every i G// the projection Pr onto q.
18
PT U P., for every i hyl WER
// Union of all the sets Pa with index v in R.
B' = (PP). ( u (B()) e B, Gi
21
return B'
Note that the following lemma different than in Lemma This is since Algorithm would be called subroutine at most times, and as such need adjust the failure probability in this use of Lemma 3 to 8/n.
The following lemma states the desired properties of Algorithm 3 see Lemma 14 for its proof. Lemma 2. Let B (B,,... B3} such that there is (PI.... P' an equally-sizer
consecutive partition of some interval of n-signal P. PP > 2k. where each B, E B is an (0, rz) apparroxxiittion of P,, i.e. P, projected unto B;; see Figure 6 andd Definition 3 Put c, E (0. 1 1/10], and let
c*
(1 +1) (12 11)((1100,) (221ogg (4
1k
A= -2
+ x
log2
be an integer, where c² > is constant that can be determined from the proof. Let B' be the output of REDUCE(B, 6k - 3); see Algorithm 3 With probability at least ö, we have that B' is
(1 10c, (1+10,,8))apprann)) Japproximmatio of P for some 3r 2 1; Definition 3
18

---

Under review as a conference paper at ICLR 2023
R
C1
R₂
C2
R3
Figure 5: A set [3] for 3 30 of indices (black ticks), set C = f(i, 02) S
[ of 2 indices, and
partition R1 R2 R3 = [13] of the indices not in C, as described Line 17 of Algorithm
B
B2
B 2)
B
(2
B (1)
P (1)
(2)
((1)
p
((1)
(2)
3
P1
P2
P3
Figure 6: Illustration for the input to Algorithm The set 42, P3 is an equally-sized consec- utive partition of P an interval of an n-signal, where for every E (1,2,3) the set P: is projected onto a bicriteria of size which is denoted by ((()) (2)
Overview of Algorithm The input for the algorithm is the projection of an interval of an n- signal onto some rational function. This projection is represented by an (0, apprroxximaaoon see Definition B] The algorithm also receives an integer À 2 which controls the size of the output. The algorithm computes (restricted) coreset for the projected input, for which the approximation guarantees hold only for the subset the set of rational functions that are 2 2--bounded over the first. coordinate of the input interval; see Definition and Lemma] 3
Algorithm
4 computes this restricted coreset as mentioned section 2.2
X
x
X 5
X
X7 x
1
X
Figure 7: exponential partition X!.... .... X set X; = [30]: see Line of Algorithm
We note that in code substitute the precise computation of the partition in Line of Algo- rithm 4 presented in Lemma 11by by an "approximate partition", where the roots of the polynomials in Lemma I1 are approximated by numeric methods; done using the method roots from the library numpy, which to the best of our knowledge utilizes Horn & Johnson (1999).
19

---

Under review as a conference paper at ICLR 2023
Algorithm 4: MINI-REDUCE(B, A); see Lemma
Input An interval of an n-signal P which is projected unto some q E (R+)² i.e.,
((P. q) 0. This represent by == ((P, g)). which is a (0, 1>approximation of P: see Definition 3 An integer À
Output: A weighted set (S, w) i.e., S C I² and w S + R; see Section 2.1
X = far (x,y)= E i.e. X is the union over the first coordinate of every pair P. (c,d):= (R+)²
Let {X1, Xn) be partition of X into E (kk) sets, such that for every E [r] the function (() =
(c) is monotonic over [mnn min((:)) max(),)) and for every
i.j [n). where + j we have X, minn(X)). max(X;)) 0: see Lemma 11 :
for every i {1,...
7 do
Let {x!,
x,
be a consecutive partition X; into m, E O (Iog((X.))) sets such
that for every [m we have [X]] 2min()-1..m-)),, // See Figure for illustration.
for every [m,] do
Ipoly(c, x))
Let x (0, 0o) such that s(x) 2 sup
Ex'xx! [poly(e,x')] for every x E X².
and Σxex s(x) E O(k2) where the supremum is over e 22++1 such that
Ipoly x) > see Corollary 2
s(x)
Set (x) Erext s(x')
for every X/.
P/:= = (1, (at.ooai(q x)) I x // see Definition 2
Pick a sample S of A iid. points from P/D where each (z,z) P/ is sampled with probability sx().
11
12
5 SU! Set w()) == 1/(A s(x)) for every p = (I, y) E S.
13
14
return (S,w)
The following lemma states the desired properties of Algorithm 4 Lemma
13
for its proof.
Lemma 3. Let P be an interval of a n-signal which is projected unto some q E Let = {(P, }) which is a (0, 1)-pprroximttio B of P; see Definition 3
[
i.e, E(P,4)
Let X be the first
coordinate of P. i.e. X = {x (x, P). Put e, E (0, 1/10], and let
(klosm)
(klogg)
x2 22 +1) (1)))(22))) 14+ 1) + log
be an integer, where c² 1 is constant that can that can be determined from the proof. Let (S, w) be the weighted set that is returned by call to MINI-REDUCE(B, A); see Algorithm Then |S] O (kA l) and, with probability at least 8, for every d' (IR+)² that is 2 -oundde over X (see Definition we have
(e(P, - e(S,,
S (..
(2)
B.3 COMPUTING AN (a, APPROXXIIAAIIOOO WITH LARGE 3 ALGORITHM
Algorithm 5 takes as input an n-signal P and an integer 3 2 1. aims to partition P into v E + (.5) sets Pi, P2, Ps of the same size, and to compute, for every such
Overview of Algorithm
set P., the query 9: E )IR*) that minimizes the RFF loss ((P..)) 4) for this set. The algorithm outputs the sets P. in the partition of P, each equipped with its optimal query 9:-
As the time to compute the optimal query for each set the partition of depends polynomially on the size of the
need those sets be small. Unfortunately, this implies that, we must plug
20

---

Under review as a conference paper at ICLR 2023
large value of 3. To this end, this algorithm its does not suffice in order to compute the desired (a, -ppaprooinntio with small values of both a and B. However, this algorithm still utilized in Algorithm!] D as some sort of initialization.
Algorithm 5: BATCH-APPROX(PP B); see Lemma
Input : An n--iinal P where n 2 2k is a power of 2, and a positive integer B.
Output: An ordered set B that contains & E ( (BI..... BB), where every B, is an
(1, 1) )-approximation Definition [
set P; in some consecutive partition (Pi,'.. Pe of P; see
Compute an equally-size partition {PI,--- ,P where & E [L8/2], of P whose size is
Pil = 2mm for some integer m 2
For every i [eb], let qi be the optimal fitting rational function for P; for every i [b), i.. Qi E arg min ((P; q); see Lemma 8 for an implementation.
9E(Rt)²
Set B == (B1, .. Bb), where B, = {(P,, q.), for every i [v]. return B.
Lemma 4. Let P be n-signal, where is power of 2. Let [3 be positive integer. Let B (B1,- ...,....... Be), where vp [13/2], 33. be the output of a call to BATCH--APPRO((P- B); see Algo-
(P&s qr)] is an (1, 3)- approximation of P; see Definition 3 Moreover, the output of the call to EATCH-APPRON
rithm 5 Put {(Ps, q:)) == for every E [w]. Then, B' == q1),
can compute in n (2kn/3) (kk)) time.
Proof. By its construction in Algorithm 5 we have that B' is an fap))aaopoxiiiaioon of P. By
Lemma 8. for every i [v)], the computation time of every d in Line 2 of Algorithm 5 is in
(2k P. (k) Combining this with the construction of Algorithm proves the lemma.
B.4 FAST PRACTICAL HEURISTIC
Unfortunately the running time of the algorithms is still large. Therefore, we suggest heuristic on top of our coreset. We later prove that, under some assumptions, this heuristic gives constant factor approximation. For this heuristic we need the following definition.
Definition Let S be a set of 2k points on the plane. We define SOLVER(S) as an arbitrary (c,c') E (R*)² that satisfies ((S,q) 9) 0 if there is such pair, otherwise it is empry.
In Lemma 20 we prove, that if {x y (a, v) E SS 2k, then SOLVER never empty and that it can be computed in O (I=2) time. In our companion code, we sample G directly from P.
Algorithm 6: FAST-CCETROID-SST((PP. 3); see Lemma 21
Input : A finite set P C 22 of at least 24 points, where
VS C P, S| 2k {a (x, v) E S} 21, and an integer 3 2 1.
Output: A set G C (R*)*
of size G 8.
G (SC P [S| 2k).
PP]
G| 3 then // G : 2k
return U
SOLVER S)// see Definition 6.
SEG
Pick sample G' G of |G'| = 3 sets of points, where each set G' of points is sampled i.i.d. and uniformly at random from G.
return
U SOLVER(S)/ //) see Definition SEG"
21

---

Under review as a conference paper at ICLR 2023
C ALGORITHM 2 CORESET GIVEN AN (a, ( -PPPOXXPXOONI
The coreset construction that we use in Algorithm 2 is a non-uniform sample from a distribution, which is known sensitivity, that is based on the (a, 3 -approxximaio defined in Definition To apply the generic coreset construction we need two ingredients:
bound on the dimension induced by the query space ("complexity") that corresponds to our problem as formally stated and bounded in subsection C.I This bound the dimen- sion induced by the query space determines the required size of the random sample picked in Algorithm 2
(ii) A bound on the sensitivity as formally stated and bounded in the proof of Lemma 6 This bound on the sensitivity determines the required size of the random sample that is picked in Algorithm 2
C.1 BOUND ON THE DIMENSION OF THE QUERY SPACE
We first define the classic notion of VC-dimension, which used in Theorem 8.14 in Anthony & Bartlett (2009), and is usually related to the PAC-learnnn theory [i et al. (2001).
Definition (VC-dimension Lucic et al. (017)) ). Let F C {R' + {0, and let X C R.. Fix
set S = f ... ] C X and a function J E F. We call S, {az E S [(x) = 11 the induced
subset of S by f. A subset S = {o1,... Inl of X shattered by F if {S} 5 I F} = 2". The
VC-dimension of F is the size of the largest subset of X shattered by F.
Theorem 2. Let be a function from R. Rd to {0, 1}, and let
= (ha : (0. 1) R.)
Suppose that h be computed by algorithm that takes input the pair 0 E R Rd and returns ho(x) after no more than of the following operations:
the arithmetic operations +, -, and / on real numbers,
jumps conditioned on >, <, 2,2,=, and + comparisons of real numbers, and
output 0,
Then the VC-dimension of H. O(m² mt).
For the sample mentioned in the start of Section we utilize the following generalization of the previous definition of VC-dimension. This commonly referred to VC-dimension, but to differen- tiate this definition from the previous, and to be in line with the notations in Feldman et al. (2019) we abbreviate to dimension. This is the dimension induced by the query space which would be assigned in Theorem to obtain the proof of Algorithm
Definition (range space Feldman et al. (2013)). A range space is pair ranges) where L is set, called ground set and ranges is a family (set) of subsets of L.
Definition (dimension of range spaces Feldman al. (2013)).
The dimension of range space (L, ranges) is the size |S] of the largest subset S C such that
I{S n range range E ranges) = 2|
Definition (range space of functions Feldman et al. (2013); : (aa--Pled & Sharir (2009) Feldman
Fellmmnn
& Langberg (011)). Let F be finite set of functions from a set Q to [0, oc). For every Q E Q and r 2 U, let range((F,
= ( f(Q) r.. Q Let ranges( F)) (range(F, Q) E 0}.
Finally, let R = (F, ranges(((()) be the range space induced by Q and F.
In the following lemma, which is inspired by Theorem 12 in Lucic et al. 2017). we bound the VC-dimension which would be assigned in Theorem 3o obtain the proof of Algorithm
Lemma 5. Let ((P).q)),... (P3, qo) } be an (a, apprrooxxnntoo of some n-signal {(1, v)) (2, 12).... ,,. see Definition
Let P (R+)² [0, oo), be the function that
22

---

Under review as a conference paper at ICLR 2023
maps every p (x, v) P. where p Pa. and any q (R=*)² to [(x) D(a ratio(a; s:).
For every i E [n] let fi (R*)² + [0, 0o) denote the function that maps every q (R+)² to Silg) = (i. Let F ( Sn). The dimension of the range spuce Raxy,, that is induced by (R+)² and F is in O(12).
Proof. For every (g.r) (c, (R*)² R. let (rlee R - {0,1} that maps every E [n]] to (x) 1 if and only if Si(q) S and every E IR \ [n] to leceier))) (3)) 0. Let H (he O R2*+1). For every R and any I R we can compute poly(c, with O(k) arithmetic operations on real numbers and jumps conditioned on comparisons of real numbers; see, for example, Horner's scheme Neumaier (2001), which is used in numpy's ' implementation of the method polyval Harris et al. (020)). Therefore, for every E [n] and any O 2 by the definition of D, we can calculate hz(3) with O(k) arithmetic operations on real numbers and jumps conditioned on comparisons of real numbers. Hence, substituting d := n. m == 2k + 1, h := h, H : H. and E (k)) in Theorem 2 yields that the VC-dimension of H (k²)) Hence, by the construction of H and the definition of range spaces in Definition 7 we have that the dimension of the range space P. that induced by P and is in (K2)).
C.2 SENSITIVITY OF FUNCTIONS
For the self containment of the work we state previous work sensitivity of functions.
Observe that the following is stated in a more general form than required in this section. This is since would re-use the stated results in later parts for the restricted coreset, while in this section we bound the sensitivity to the projection unto a bicretiria; see Section 4 and Definition 3
Definition 8 (query space Feldman et al. (2019). Let P C IR² be a finite non empty set. Let f: P x (IR*)² > [0, oo) and loss R [0, oc) be function. The tuple (P, (RR²) .S. loss) is
called a query space. For every E (I=)² we define the overall fitiing error of P to by
(P,0) = loss (s ()pp)) -loss
Sppp,
To emphasize that the following coreset is a subset the input set, in contrast to e-coreset as in Definition we call it subset-e-coreset. In Section C.4 we prove that there is no such coreset for the RFF problem; see Definition 2
Definition 9 (subset-e-coreset Feldman al. 2019 ). Let (P, (R+)² loss) be a query space as
in Definition & For approximation error >> the pair S' = (S, u) is called subset-e-coreset
for the query space (P, (R²)² loss). if S have
+ 00, 20). and for every q E (RR) 2 we
(1 musss P.o) S Jiuss (S'. :4) S (Issss
Definition 10 (sensitivity of functions). Let C R² be finite and non empty set, and let F C
(P + [0, xo]} be possibly infinite set of functions. The sensitivity of every point E P is
f(p)
S(p = =sup
(3)
SEF Σ f(())
PEP
where sup is over every f E F such that the denominator is positive. The total sensitivity given sensitivity defined be the sum over these sensitivities, (P) ) =Eper ((p,,,()) The function
S(P.F) P + [0, oc) is sensitivity bound for S(. for every p E P we have S(p,r((D) Z
(rr (p). The total sensitivity bound is then defined to be (P) Σ Spp,
PEP
The following theorem proves that a coreset can be computed by sampling according to sensitiv- ity of functions. The size of the coreset depends on the total sensitivity and the complexity (VC- dimension) of the query space, as well as the desired error e and probability of failure.
Theorem (coreset construction Feldman et al. 2019)). Let
23

---

Under review as a conference paper at ICLR 2023
P (11,-.. ,Pp C IR² be a finite and empty set, and f: P (R+) - (0).
F= (fi...., fa), where fi(g) = f(p,, q) for every E [n]] and q E (IR*)
d' be the dimension of the range space that is induced by (R=*)² and F.
[0, 00) such that s* (p) is the sensitivity of every p P, after substituting and F {{ 10, oo) Vp P.q (RR) f2) ((p.9) in Definition 10 and 8: - oo) be the sensitivity bound of 8"
l Epers(p)
e, (0.
c > a universal constant that can be determined from the proof.
A A c(t + 1) log(t + +) log(1/6))
: [1}, i.e. function such that for every p E P we have w(p)
(S, u) be the output of call to CORESET-FRAMEWORK w, X) (Algorithm I in Feld- man et al. (2099))
Then the following holds
With probability at least 1 6, (S, w) an subset-c-coreset size |S| S X for the query space (F, (R+) ff II:); see Definition
C.3 ANALYSIS OF ALGORITHM 2 CAMPLE-CORESEE
the following lemma we prove Lemma I which proves that, given values that satisfy specific
properties, we have that Algorithm| 2 yields e-coreset; see Definition
Lemma 6. Let B = {(Pi.g) g , ... (P3, }o)} be an (a, appppooxiinti of some n-signal P. Pofor some a > see Definition
Put c, (0, 1001/10), and ler
22 (a + (k² log(a + + log(l100)) (1/))
where c' 2 1 is constant that can be determined from the proof. Let (B, C, w) be the output of call HAMPLE-CORESTEE A); see Algorithm 2
Then, Claims (i)-ti) hold as follows:
(i) (B, w, can be stored using O (A + 3k) memory.
(ii) With probability at least 1 8, we have that (B, C, w)) an e-coreset of P; see Definition 4
Proof. We have (i) by the construction of Algorithm 2 and the definitions in the theorem. Let e as computed in the call to HAMPLE-CORESETUE A); see Algorithm 2 Since is an (a, 3)- approximation of P have that # If c O, then the theorem holds by the construction of Algorithm 2 Hence, we assume this is not the case. Let P' be the projection of P unto B,
i.e., P' = {x,, ratio x)) [8), (x.y) y) E P};
Definition Let Q be the union of q
(c, d') E )I=))* such that + (cly(c', 2) * 0 for every (x,y) P. Let (c, c') Q. We have
Σ D(g.p) - Σ (w(l)) D(q,p)) - Σ D(g.))
PEP
PEC
PEP
Σ D(q.)) Σ D(g.2) (w()) D(a.p)
(4)
ED(g
PEP
pEP
PEC
D(g.p)
Σ D(g.p)
PEP
24

---

Under review as a conference paper at ICLR 2023
where the previous equality is by taking
Σ D(g. p) out of the sum. Let st::: P (0, defined
PEP
in Line of Algorithm in the call to HAMPLE-CORESETE A), ie., for every i E [$] and any
p E we have
s(p) D(g.))
(5)
Σ ((P.)))))
Let i E [3] and 8/ : P; - [0, oo) such that for every point = (z. y) E P3 we have
8 {p) D(a,)) - (o)( - [g(2a]
(6)
D(a,p)
PEP
which, due to the definition of P' as projection of P unto B, is upper bound the contribution of every point P. to the sum in Equation
Let (z. y) E Pt, so that
Díg. p) (x) fa(x))
sp)
Σ D(a,p)
PEP
(7)
1 fa(t)) - (Ia fa(t))
y (x)
D(g.P)
S a s(p),
Σ D(g.P)
((..p)
Σ D(g.p)
PEP
PEP
PEP
where the first equality is by the definition of s* from Equation 6 the second equality is by the defi- nition of D. the inequality is by the reverse triangle inequality, the third equality by the definition of D, and the last equality is by Equation and the definition of B as an (ax, apprroxxiintioo of P.
Let P [0, 0o) such that for every P we have 8(p) a s(p). By Equation 7 for every i [3]. we have that is a sensitivity bound for 87
For every p (x, P.ç E [3] and any q (R+)² let (q, D(g, ratio();:)) Let F = (f1...... fn) where fr(y) f( for every E P,, [3] and q E (R²)² Let E (13)) be the dimension of the range space Rp,F from Lemma [ when assigning P and B.
Substituting = e, = 8, A = A, the query space (P, Q, F1 II.), E e the VC-dimension induced by (R+*) and F from Lemma 5 the sensitivity bound 8, and the total sensitivity
s(p) in Theorem 3 combined with the construction of Algorithm 2 yields that with
probability least 1 5, for every q E Q, we have
Σ
D( Σ D(g,))
w(()) D(1,r))
PEP
PEP
PEC
S E.
(8)
D(g.p)
D(g.p)
PEP
PEP
Combining Equation 8 and Equation proves the theorem.
C.4 LOWER BOUND.
In this section prove that there is subset-e-coreset for the query space (P. (R*)
D. 11 -D.II-I)).. II)).
8 This justifies our Definition of coreset for RFF. The main idea in the following claim is illustrated by figure g
where P C IR2 is n-signal P and D is Definition 2 defined in Definition
Claim (Minor modification of Claim 5 in Rosman al. (2014)). For every integer 2 2 there is an nisigaal such that the following holds. For every C C TR?, where |C| < n, there is q E (I.**)
such that Σ D(g.p) [0, oc) and PEC
Σ D(g.p)
PEP
25

---

Under review as a conference paper at ICLR 2023
Proof. Let P [(1,0) (n, and C S R2, where |C| < Put (a, P. > 0 such that
Cn {(a,8) y E [R] 0; ie., there is no point in C' with v-value equal a. There such a point
since [C] n = Pl] Let (1,0.0, ... 0), (-2. 0,0, .0. and q = (c, c') E (R*)²
Since [(aa, 0), |ratio(g, a) 0 xc (observe that apoly (c, a) - a/a = 0),
and (a,0) 0) P. obtain Σ D(g.p) (((a))),)) co. On the other hand 1
PEP
only for x = a, therefore vp E C D(g.p) E 00), and since C' a finite set we obtain
Σ PEC
D(g p) E o0)
P
100
(a,0)
query
0
-100
0
5
10
15
20
25
Figure 8: Visual illustration of the main idea behind Claim 1 The n-signal P (1,0), .... (25, 0)} as in Claim for
25 (black dots). Consider a subset C' that contains all these points except single one, say, the red point (15,0) We can always find rational function (query) whose sum of distances is close to zero for P, but close to oc for C, due to due its high change the point (15, 0) that was not selected to C.
D INEFFICIENT SOLVER FOR THE RFF PROBLEM
In the following section we will prove that we can solve the REF problem from Definition in (2kn)O(k) time as previously mentioned Section 2.1
The main idea is that, given an assignment of whether each point is below or above the best fitting rational function (to the loss in Equation [ from Definitions 2 the problem can be written as frac- tional polynomial programming problem and solved in polynomial (in the input size) time; see Pizzo al. (218)). Using previous work Marom & Feldman (2019) we can bound the number of candidate assignments mentioned above to be polynomial in the input size. Hence, by constructing semi tree we can find all the satisfiable assignments time polynomial in the input size, which enables us to compute optimal solution in polynomial time.
In the following section, for every x E IR let sign(r) 1 x: > O and sign(x) = -1 otherwise. Theorem 4 (Theorem 23 in Marom & Feldman (2019). Let f1,..., , be real polynomials I. Then the number of sign sequences
< m variables, each of degree at most
44emm
(wggne))......gg((ff............ over E T that consist of the terms 1, - is at most
h:
To utilize this previous bound state the following observation.
26

---

Under review as a conference paper at ICLR 2023
Observation 1. Let P ((11,))),".. (Fn, bn)} R2, Let Q be the union of (c,d)) ) (R+)²
such that + x. poly(c', .x) + for every (z,y) E P. There are 91. In 2k IR polynomial of degree in (n) with 2k variables such thatfor every (c, E Q we have
gi(el c) = (1+x poly(c', x)) (poly(e,x) y- y poly(c', x)).
Proof. L=t (c) Q. For every (ar v) P, by reorganizing the expression have
sign (ratio ()), -) sign (1+ x)) (e, ----------- -u-----poly(c' x))) (9)
For every i E [n]] let 9i IR + R be polynomial of degree in O(n) with 2k variables that maps every (c,d) E (I+)² to
gi(e d) = (1 + x poly(c',x)) (poly(e, - y y.v p-ly---oo-((
By Equation 9 we have that 91,"" 3aa R2 + R satisfy the observation.
Using this observation and Theorem 4 we obtain the following result.
Corollary 1. Let P ((01,,91) " (In, Un)] } C R22. Let Q be the union of (c,c') E (R+) such that 1 1-x- (c'olyc',c x) # Ofror every (I, E P. The number of sign sequences sigg (ratio(q, x1)- 21)." .....,iiggi sign (ratio(y, Fn)) - vnn) over every overevery
E Q is in (2k))
Proof. By Observation 1
let 91,- I9n 1 R be real polynomials of degree in O(n) with 24: variables such that for every == (c, E Q we have
sign (ratio(q, x1) - v:) sign (gi(c) (c)c
(10)
By Claim 4. the number of sign sequences (sign(g) (a)), ... sign( Un (x)) over i E 2R that consist of the terms 1, - in (2kn) (kk) Combining this with Equation 10 proves the Corollary.
While, as stated before, the number of possible positions of every points indeed polynomial, there is the problem of computing this set in polynomial time. We will solve this by utilizing previous work on polynomial programming mentioned in Pizzo al. (2018).
Observation 2. Let P {(z1, y1),... (In, vn)} C R.. Let Q (I²))² be the union of every (c,d) E (R*)² such that + x poly(d,,) x) + O for every (z. E P. For every vector S e {0, 1)" check in (2k))o(k) the existence of q Q that satisfies S sign (ratio(q, 21) 21), ... sign (ratio(q, vn) - -,.)) i.e., satisfies the assignment by S.
Proof. By Observation I
let g1, ........ In 2 + R be real polynomials of degree in ((n) with 2/: variables such that for every = (c, E Q we have
sign (ratio(g, m1) vi) sign (gi(e) c))).
Hence, for every assignment S E {0, 13"", there q E Q such that
S = sign (ratio(g, 21) - v1),"" ... sign (ratiolg, vn) - y.u)
if and only if there is x dd such that S (g((z), ((.()))).....(xx))) and the later can be written as polynomial programming and thus solved numerically in (2kn) O(k) time: since this is equality can be written as sum of squares (SOS), see Pizzo et al. (0118.
Using this, in the following lemma, we prove that we can generate all the satisfiable options for the function to be above the points below the points in polynomial time and not exponential.
27

---

Under review as a conference paper at ICLR 2023
Lemma 7. Let P
{ y1), (Zn: yoll C RR. For every non empry C P let Q(C) c (R+)² be the union of every (c, (R*) such that ++ polyyd', x) & for any (z, y) C. All the sign sequences (iign (ratio(g, x1) v1)." sign (ratio(g, vn) overevery every E Q(P)
can be computed in (2k)) time.
Proof. By Corollary for every C C P.ICI = m 2 2k there are at most m (kk) options for the sing sequence
sign (ratio(q.)) - y) (z, v) E c) over every E Q(C).
Let C₁ C2 c P, = = 122 2 1, where we know all the satisfiable sign sequences sign (ratio(q. x)) - v) (z, E c over q E Q(C") for C E {Ci, C2}. Since [C1]: n, by
Corollary I the size of { siign (ratio(g, =)) - u) (2, v) E c) 1 E Q(C)} in (2kn) for Ce (2,,C,): Hence, the size of the candidate sets for
{( sign (ratio(q, x)) v) (x.v) E GUU)) 1 I Q(CUCa)
in (2kn)0(k) Therefore, by utilizing Corollary to validate each candidate, we can compute in (2kn) (O() the set { sigg (ratio(g, x)) y) (a.y) Ci CUS)) q Q(C (C)).
Thus, partitioning P to sets of size O(k) 2 2k, for each such C c P using Corollary to compute in (2k) the set {{ options as stated above proves the lemma.
sign (ratio(g, x)) - v) (x, EC) 1 Q(C)). and combining all the
Using this observation, and returning to the original problem, we obtain the following solver. Lemma 8. For every weighed set (8, w) that contains n arg min ((S, 4) can be computed in (2k))o(k) time; Definition 2 qE(Rk)²
[S| points pair q in
Proof. Let Q C (IR))* be the union of all the pairs (c, (I²)) such that 1 1+r 1-xx-polycc x) + for every (I,y) S. By Lemma in (2kn) ((() time, compute all the 0(k) possible sign sequences sign (ratio(d' æ1) v1), ... sign (ratio(q', zn) un)) over every g' E (R+)²
For every such sign sequences w', where w' E {-1, 13 is the sign of every point P, observe the following:
For every q: (c, d') E Q satisfying the assignment by w' we have
poly(c, -i-polllee... (i+ poly(d,x) -9) -
E((S, w),4)
Σ (=(x,))SS
w(p)w'(p)
Hence, by taking the common denominator in the right part of the equation above, there are poly- nomials fig (I&)) + R of degree in (2kn)0(1) with (R&)² as the variables and (2kn)
parameters, such that for every g Q have
f((2)
((S, w) 9(4)
Hence, utilizing Pizzo et (018). this problem can be solved in ((k)))(k) time; the solution is numerical solution that can be approximated to arbitrary precision. Hence, by taking the minimum over the ((k) candidate solutions, we can compute g as defined in the lemma in (2kn) O(A) time.
28

---

Under review as a conference paper at ICLR 2023
E CORESET UNDER CONSTRAINTS, ANALYSIS OF ALGORITHM
4
In this section we will prove that Algorithm 4 constructs restricted coreset for rational functions, which, as previously mentioned in Section 2.2 will be utilized efficiently compute an (a, 9)- approximation to given n-signal P. where at 3 E O(log(n)). It should be emphasized that the final coreset construction has no such restrictions or assumptions for either its input or queries.
For readability we split the proof into three parts:
(i Mostly citing previous work, we bound the polynomial manttiil-iittingg sensitivity.
(ii) Utilizing the previous bound we compute sensitivity for restricted case of the RFF fitting problem from Equation of Definition that formally sated and bounded in Lemma I0
(iii) We utilize the previous bound in Lemma 13 which proves the previously stated Lemma that summarises the desired properties of Algorithm 4
E.
UPPER BOUND ON THE POLYNOMIAL-RTTING SENSITIVITY
For the polynomial-fitiing sensitivity, consider the following lemma that follows from the work on sensitivity of near-convex functions by Murad Tukan Tukan et al. (2020)
Lemma 9 (Lemma 35 in Tukan et al. (0220). Let Y be a set of n points in Rd. A function (0) can be computed O d²) time such that for every x E we have
Y
JaT .
I s'x),, where the supremum is over E Rd such that laT gl > 0, and
sup
EPEY 1VT gl
gER
Σ (z) E 0 (2/2).
YEY
Using this lemma we obtain the following corollary.
Corollary 2. Let be a set of 2 reals, and k 2 1 be an integer. A function s: X + 00) can
|poly(c, x))
be computed in O (n k²) time such that for every x E X we have sup
S s((),
Σ Eyex poly v)
oER*
where the supremum is over q E IRd such that ppolycc, x) > 0, and
s(x) E (k3/2)
aeX
Proof. Let f X - R be the function that maps every x E X to (L, ... {f(x) x E X} denote the image of f. and let sf + [0, oo) as defined Lemma 9 For every E X, E RR where |pll(c, m O. we have
- Let Y
[poly(,,))
[((x) Eyex f(U)T c S S sf(())),
Σpex vp)
where the first inequality is by the definition of poly, and the second inequality by the definition of s'; see Lemma 9 Let s: X + [0, co) be the function that maps every y E X to s(y) = s' d'(()))- By Lemma 9 satisfies all the claims the corollary.
Computation time of s. For every x X we can compute f(x) in O (I22 time. Hence, the computation time of Y is in O (nk?). By Lemma 9 the computation time of s' is in O (n- Therefore, since, for every y X we defined s(y) s' (f(x)), we have that the computation time of s O (n (n.)
E.2 UPPER BOUND ON THE REF SENSITIVITY
In this section we the RFF sensitivity for the restricted case mentioned in property (ii) at the begin- ning of Section E For this we define the following.
29

---

Under review as a conference paper at ICLR 2023
Definition 11 (Lipschitz-functinn Let O, and a, R. where b. A function f la. b] + [0, oo) is r-Lipschitz if f is non-decreasing over [a, b). and for every 2 1, and any x E [a, we have f(c. x) < f(z).
In the following claim state known property of polynomial functions.
Claim 2. Let k 2 1 be integer. and a. b E R where b. Let f [a, b] oo) be positive and deccesscgg polynomial over (a, b] of degree at most k. Then f is a h--ipschitz
Using the claim above, we obtain the following corollary.
Corollary 3. Let e' E 1R. Let C R denote the extrema of the function g that maps every æ E R to g(x) = | + x poly(c', x)). Let X |a, b] C IR, |X| | >> 1 such that for every x E X we have
min EG
> max(X) min(X).
1
Then the function f X
T. that maps every X to f(x) 1 + poly(c',x) is well defined,
max [x))
and satisfies #eX
min [ 2
Proof. By the definition of X, if there is X such that G. then by substituting min Ir 7 z max(X) - min(X) we have that max(X) = min(X) and as such |X = 1, TEG
which contradicts the definition of X in the claim. Therefore, we have X G 0, that is g has no extrema over X. If there is x E X such that g(x) = 0, by the definition of we have that is an extrema of the function g. Hence, there is no x X such that g(x) 0, which yields that the function f defined in the claim is well defined.
max [f(x)) x min x
Since g has extrema over X we can prove that
[f(x) S 2 via the following
Case (i): y constant in the range X.
From the definition of the case and the definition of f it follows that f is constant in the range of X, and thus max [z)) = min [xx)]
zex
=ex
Case (ii): increases in the range of X.
Let x, y X such that y. By the assumptions (and Claim 2
1 + x (o x)1 s 2 -1 x poly(c', (c), and
[f()) 2 |s()))
where the first inequality is by Claim and the second follows from the definition of f and dividing both sides by g(z) g(y). Hence, max f(x) < 2* min [f()). zeX
aex
Case (iii): decreases in the range of X. Let x. E X such that x < y. By the assumptions (and Claim
1 + poly(c', v)1 2 2 2 + poly(d, and [ 2 2h |f())]
where the first inequality is by Claim 2 and the second follows from the definition of f and dividing both sides by g(z) g(y). Hence, max f(x) < 2* min [=))..
zeX
Using Corollary 3 we obtain the following bound for the RFF sensitivity.
Lemma 10. Let qı = (c1, ef) E (IR*) Let D C RR denote the extrema of the function g that maps
every x E R to g(z) |1 11++ x)) Let X R such that for every x E [min(X), max(X))
we have that min ir >1 2 max(x) - min(X). Let E (R+)² be 2 -b-uddde over X; see 7ED
30

---

Under review as a conference paper at ICLR 2023
Definition 5 Lets: X + oo)) be the sensitivity bound computed in Corollary aater substituting with 2k
and Y by X. For every I X we have
ratio(q1: x² ratio Q2 x)]
3 4t s(x).
ratiolgi, v) - (atio
VEX
Proof. If X by the construction of in Corollary 2 we have that the single value E X satisfies s(x) 2 1, which yields that the inequality in the lemma holds for this case. Therefore, from now on we assume that this is not the case, i.e., we assume that [X] >
Identify 42 (c2, c6), and let c E 22k+1 such that for every R we have
poly(c, x = poly(c1,)) x) (1 + x poly(c2, x)) - poly(c2, x) (1 + x poly((,
Let f2 E. + [0, oo) denote the functions that map every y E X to fi())
1+ y poly(c,.1)
1
and f2(v) 1 y. xr) respectively. Let E X. We have
(oly(c1,
poly(e2,
|ratio(gn; x) ratio(?2,
1 polylpp,y)))))
1 nee-poly (22
(1I)
poly(c,2)
pplly(c x) fi(x) f2(x)),
(1 + x poly(4, (1 + x poly(c,, x))
where the second equality is by assigning the definition of c, and the third equality is by assigning the definition of fi and f2- Substituting X by [min(X), max(X)] and by ei in Corollary 3 yields that the function
f X - R
max 2EX
[f
that maps every E X to f(x) 1 poly(e,,)) is well defined, and satisfies
min [f(x)] 5
2 That is, since = (c1, c,), that is 2 well behaved over X; see Definition
Hence,
ratio(a,, x) ratio
poly(e, x) (1))
(12)
ratio(gı.0) 3) ratio 8)
pplly(c,)) f(()) f2(1))
VEX
WEX
max yE
(v)
max (2((v)
[poly(ex))
yEX
(13)
min yEX
[v]
min
[2(()]
(poly(c,v))
BEX
4 poll((,
(14)
|poly(c,v) v)l
DEX
<h s(x).
(15)
where Equation| i iss by Equation IT Equation 13 follows from assigning that æ E X, Equation 14 holds since ' and Q2 are 2--bnudded over X, and Equation 15 is by assigning the definition of in the lemma.
E.3 CORRECTNESS OF ALGORITHM 4 PROOF OF LEMMA
In the following lemma we show minor result that was used in Algorithm
Lemma 11. Let e E & and X {a,a 1... bb} C [n] be
empty interval of [n]. Let
f R + [0, 20) be the function that maps every x E R to f() = |1 + x poly(c, 2) There partition (X1,... X,)) of X into In) < 2k 1 sets, such that for every E (r] the function
31

---

Under review as a conference paper at ICLR 2023
is monotonic over min(X.),, max(Xi)). and for every i.j E [n], where + j we have X; n [min(X)), maxmmaxx) x,) 0. Moreover, this partition can be computed (I: + 1)0(1), [X] time.
Proof. Let 9 - [0, 20) be the function that maps every x E to g(x) + x poly (c, xt), which is an polynomial of degree at most k. Observe that, by the fundamental theorem of algebra, any non zero polynomial (due to its construction g is non zero) of degree at most & has at most roots. Thus, since the derivative of is a polynomial of degree at most k 1, has at most k - extrema. Hence, as any extrema of f is either a root or extrema of g. f has at most 2k extrema. Partitioning X according to the 2k 1 extrema of f yields the partition {X1,-.. .,, from the lemma.
Running time: Observe that in the root finding presented above (including in the computation of the extrema of g) it suffices to only search for roots in the range of X, and for the non integer roots only for which integer they in (a, a 1). Each integer candidate for the roots can be validated by simple assignment in the polynomial in (k- +++ 1)0() time. By Sturm' '-thhoremm Thomas 1941 can validate each interval candidate for root in (k- 1))(1)) time. Since there are | candidates for roots (intervals and integer), all of the roots can be computed for the sufficient precision in (A + 1)0(). |X] time, Since f has at most 2k - extrema, the partition of X can be computed in O(k (Xl) time. Hence, the overall running time is in (k + 1)0(). |
Lemma bounds the VC-dimension that corresponds P1, .Pn in a ne-signal projected unto its bicriteria; see Definition 2 and Definition S We now give similar bound for the distance function (g,, (z. y)) = rratio (g. x² y/ between every ratio- nal function to the point p; = (r, y). where the points are a general set of points in the plane.
the function D over the points
The following lemma, similarly to Lemma 5 is inspired by Theorem 12 in Lucic al. (017))
Lemma 12. Let P {[L, v1). (n, yn)) be an n-signal. For every pt (i.y) E P and any qE E (R+)² let (i(g) = D(q. p.) = |ratio(q, i) - yl; see Definition 2
Let G = {gi..... .nn). The
dimension of the range space Bizzip.c . that is induced by (R*)² and G is in O(k2).
Proof. For every (g.r) = (c, r)) E (RR))² x R. let (elee())) R + {0, 13 that maps every
i E [n] to (r) (i) = 1 if and only if fz(4) I r, and every x E R \ [n] to ((oee)))))) = 0. Let H. = {hg 0 E R2 For every c E R and any I E we can compute poly(c, with O(k) arithmetic operations on real numbers and jumps conditioned on comparisons of real numbers; see, for example, Horner's scheme Neumaier (2001), which is used in numpy's s implementation of the method polyval Harris et al. 2020). Therefore, for every x E R and any 0 E 2g+++1 by the definition of D. we can calculate he(z) with O(k) arithmetic operations on real numbers and jumps conditioned on comparisons of real numbers. Hence, substituting d := n, m == 2k + 1, h == h, H. : H. and t O(k) in Theorem yields that the VC-dimension of H is in O(P?). Hence, by the construction of H and the definition of range spaces in Definition 7 we have that the dimension of the range space R p.r that is induced by P and F is in O(k²).
This combined with the previous results yields the following restricted coreset construction that utilizes the previous reduction of the RFF sensitivity to polynomial sensitivity.
(Rk) 2 iie. E(P.q)
Lemma 13. Let an interval of a n-signal P which is projected unto some q
O. Let B == {(P,4)) which is (0, (0,1)-ap -)ppprooximtaoon B of P; see Definition coordinate of P. i.e, == {x| (a,y) E PJ. Put e, E (0, 1/10), and let
Let X be the first
XZ (a++1g2 + +1) ( 1o 1) + log
(klogn 8
be an inleger, where C² > 1 is constant that can that can be determined from the proof. Let (S, w) be the weighted set that is returned by a call to MINI-REDUCE(B, X); see Algorithm Then
|S| E O (kA- n) and, with probability at least 1 - 8, for every d' E (IR)) that is -bounded over X (see Definition 5 we have
Ie(P. e(S)) ())(s))))))) Se ((P.)).
(16)
32

---

Under review as a conference paper at ICLR 2023
Proof. By the construction of Algorithm 4 we have that |S| O (k) n). which follows from the bounds on the order of 7, and every m, stated in Algorithm
Let 8' == [c log n) / for a constant ca > 0 that can be determined from the proof, more specifically see Equation [9] Consider the set X C _X, for E [n] and j E [ma]] that was constructed during the execu- tion of the i-th iteration of the outer "for" loop and j-th iteration of the inner "for" loop in the call MINI-REDUCEL
Let (c, := q, and let D S R denote the extrema of the fune- tion ʃ that maps every I E R to f(x) = [1 + poly(c',=)), By the construction of Al- gorithm 4 the size or diameter of X is smaller than its distance from the edges of X,, i.e., |XJ] S min (|z max(X/), - min(x/))). Since X; has no extreme points, this implies that for every E X² we have min |r 7 |x?| = max 7ED
min(X;). Hence, assign- ing X . 9:92 q. and the function X - [0, oo) computed in the call to MINI-REDUCH(B,.) A) for X? Lemma 10 yields for every x E X that
(q,io ratiold', x
S 4h s(x).
(17)
Eyext ratio v) - ratio m)
Let P. and S be as defined in Line 10 and Line 11 respectively, during the execution of the call to MINI-REDUCE(B, B, A). and let wi
S + [0, oc) such that for every p E S we have wi (p) w(p).
Let Q denote the union over every of E (R*)² that is 2 -buunddd over X; see Definition
see
We now prove that S is an e-subset corset for the query space (P.) 2, D. Ili). Indeed, the cor-
responding dimension of lRg.a, where is G is as defined in Lemma 12 is in O(k²). The sensitivity of every (zz, y) : p E P is s(x) max ((g.p))
q) S (x) where the inequality
Ezex 4 s(x) E 4h O(k2), where the is by the inequality is by definition of s computed in the call to MINI-REDUCE(B, A). Thus, substituting 5 := 5', the query space, (P', 2, D, -lh) in Theorem 3 combined with the construction of Algo-
is by Equation 17 The total sensitivity is thus
rithm 4 yields that, with probability at least 8,, we have (S) w is an e-subset-coreset for the (P/, (P/, D, I-II). That is, with probability at least 1 - 8', for every g' E (IR*)
2 we
query space
have
((P) - E ((S), wz) (()) s c (P(((P/))))
(18)
Taking the union over every i E [v] and E [me)), under the assumption that Equation 18 holds for each pair, yields
e (PPP) - e ((//),w,)) wn))) .1))
(((P.))) (((S,
mi
ΣΣ e (P!") ( ((()).000)) .
e (P -..)) =1
where the first equality is by the construction of the weighed set (8, w) and the partition {p(") of P in Algorithm 4 the first inequality is by the triangle inequality, the second inequality is by assigning Equation 18 (which was assumed to hold for all the values), and the last equality follows
since { [1()} computed in Algorithm 4 is partition of P.
Since i E [n] by Line E [m,]] by Line 7ine Algorithm 4 we have at most O log n) sets Peşi follows by assigning the bounds on the order of 7, and every m, from Algorithm 4 By the union bound, Equation 18 hold simultaneously for every i E in] and j E [m,] with probability at least
7
m 2 1-
(19)
which holds for 8' := [c log /) for some constant c5 > 0. Hence, with probability at least 1 8 we have (((P.g') - E ((S, ()) s e ((P.d') as stated in Equation 16 which proves the lemma.
n
33

---

Under review as a conference paper at ICLR 2023
F COMBINING
(O.))-APPROXIMATTION -
ANALYSIS OF ALGORITHM 3
The imput for the algorithm is / an interval of n-signal which is projected onto some set of (a, 3)- approximations; see Definition 3 This projection is represented by the B, where each element B, E B is () apprroxximtio for some Pt, and {Pi. ....... P is consecutive partition of P. The algorithm returns B', a bicriteria-approximatii of P as in Definition 3 where the size of B' is smaller than D [ The algorithm runs in O([p)++e) time, for every constant 0.
The desired properties Algorithm Jrre stated and proved Lemma 14
For the sake of analysis, we will use the following corollary.
Corollary 4. Let {Ri, RR} be a set of B 2 6k equally sized distinct partitions of [n] such that for every i,j E [3]. + j we have R2 n mijn(B)), max((2)) = For every q E (IR*)² there is [3 = B - 6k + 3 such that q is 2 -bouuded over every for every i E C.
Proof. Let = c'), and let G be the set of the extrema of the function f IR + that maps every RRg]_ W.L.o.g. assume that for every i i [3 - 1] we have min(B;+1 > max R.]; i.c.. the sets are ordered in an increasing order. Let Ro {min(R;) r. .ii(mnn)))) (Ri) -} and Rø+1 {max(Rs) + 1,... max( + r). By the proof of Lemma I1 f has at most 2k - extrema. Therefore, removing from [8] every index i E [3] such that ff has an extrema in the range of either from {R.-1. 1, Rú, Re41) yields a set B 6k + 3 such that for every i E C we have Vr E R3 min [ gl 2
E to [(x 1 poly(c, ,,) Let
RR]
C' C [8],
SEG
max (R,) min( R.)) For every E C, substituting d' and X = R4 in Corollary yields that
the function X > I. that maps every Ra to g(x) 1+ poly(c', is well defined, and
max [(())
satisfies min [(()] S 2 Thus, q is 2 -oundedd over R2 for every E C; see Definition 5 Hence, =EX C' satisfies the corollary.
xEX
L
Combining a removal inspired by Rosman et al. (2014), with the coreset construction from the previous section, yields the following lemma.
Lemma 14. Let B (BI,... B3), where each B, B (0, rapproxaaitini of Ps, i.e. P; is projected unto B,, and (PI,... } is an equally-sized consecutive partition of P, some interval of n-signal; Figure and Definition Put c,8 (0, 1/00,, and let
km )
A =
(1 + 2
Log k + log2
be an integer, where c² 2 is a constant that can determined from the proof. Let B' be the output of REDUCEEB,, X, 6k 3); see Algorithm 3 With probability at least ò, we have that B' is
(1 + 10e, 3*) "')---pproxmmmation of P for some 3 Z 1; see Definition 3
Moreover, for = 1/10 we have that the running time of the call to REDUCE(B, x, 6k 3) is in
[P] g6k-3 40(*)) (log (n/8)31)00) where 3'
Σ |Bal
Proof. If 3 < 12k 6, by the construction of B' in Algorithm 3 Lines [ and 20 we have
8 B' = U Bi. Since B, is a (0, r.) approximation of P. for every i E [B] and {PI.... ... .P3) is i=1
partition of P, B' is an (0, -pprrx/ppoiiiaatoo of P which yields that the lemma trivially holds. Thus, from now on, we assume that this is not the case.
For every B, E identify BB" ...,,,..,........ ....,(()))
B, Let q arg arg min ((P,g). For ev- (E(R+)2
ery E [3], let R. (x (x.y) P.). i.e. the first coordinates of the points in P. Since
34

---

Under review as a conference paper at ICLR 2023
{Pi.... ,P3} is an equally-sized consecutive partition of some interval of n-signal P, we have that (R1..... Rg} is a set of equally-sized partitions of [n] such that for every i.j E [$]. * j we have R2 n min((2)) max(R,)] = 0. By Corollary 4 there is C [3], |G] = 3 - 64 + such that is 2*-bounded over Rd for every i E G. Consider the integration of the "for" loop in the call to AlgorithmB3 where G is computed, i.e., G := G.
Let G., Sg. wa. and 9G be defined as in the "for" loop iteration in the call to Algorithm Let G", respectively. Let Paxa denote
Pg and Po. be the union of P. over every G and
8
Po (P)PPP) The set {D!") l G" u G). B Bi is 0. [B:
Σ
approximation
for Payar. Hence, by the construction of B' in Line 20 of Algorithm 3 it is left to prove that
(Paro S (16) ((Po. g) & (1 + 10c) ((P.))-
(20)
The last inequality trivially holds since Pg S P. is left to prove the first inequality of
Eq. Equation 20 By Corollary 4 where we substitute 3 by |C], there is set G C G of size
|G = - 6k + such that qa is 2* 2*-bounded over R2 for every E G For every
G
and any BSd) E B; identify (pl() ) =B(").
B,S)) For every E G and any B(D) B; let
(5(0), w(!)) MINI-REDUCE ({ [(0) S {.2) as computed in Line 5 of the call to Algorithm 3
for B,O0 B.D Substituting P p()) 5 5/(2n), QG. and X = {ar (x, p (the
first coordinate of p!()) in Lemma 13 for every i E G and j E [[B:]] (by the choice of G", qa is 2 -oundedd over R,, which contains the first coordinate of p())) yields that with probability at least
8
we have
2n
((pl .96) - (4)) -c))))),
(.()).9))) s ((pl .96).
(21)
Let B B and w" S -> [0, oc) be the function that maps every p S
iE
to wn (p) = (p).). Applying Equation 21 for every i E G and j E [[ along with utilizing the union bound, yields that, with probability at least (1 52mm) " 2 1 - 6/2, we have
B2
|((Poro, 4a) - E((S(((""" w=)) x0))))))
Σ
(p(5) .qG) - -e(()))), _.(7) 9G))
(22)
KEG
==1
[B
((1) -p(").G)) - ((5))) m0(21) .96)
(23)
iEG* j=1
S c. E(Poro
(24)
where Equation 22 is by the constructions of Pg- and S* Eqqation 23 is by the triangle inequality, and Equation 24 is by Equation 21 Substituting P pp)) 8 8/(2n, g' q, and X == (zr v) p!u) (the first coordinate of p(D)) in Lemma 13 for every i E G and BU E B, (by the choice of G, q is 2* bounded over R, which contains the first coordinate of p(u) yields that with probability at least
8
we have
2n
(e(p!)). .q) - -=((s).w))))) S ((p!"..)
(25)
35

---

Under review as a conference paper at ICLR 2023
Applying Equation 25 for every i G and B B5, along with utilizing the union bound, yields
that, with probability least (1 6/(2)) 2 1 6/2, we have
|BI
(C(Po.)) - ([(P..))(((SC))))))) iEG j=1
i (p(().)) ((5)0) (o(
(26)
Bd
(p(D) e -e(()(),u))))
(u(0)))))) .9) .9)
(27)
iEG j=
S (PP..))
(28)
where Equation 26 is by the constructions of the Pg and Sg in Algorithm 3 Equation 27 is by the triangle inequality, and Equation 28 is by Equation 21
both Equation 22 to Equation 24 and Equation 26 to Equation
28 holds, which happens with
probability least
6, we have
8 PPPrro 9G) s P 9G)
(29)
1 ((5", wu))9G)
(30)
$
E((S, w),
(31)
1 1-c
E((S, ()),)),"')
(32)
1 -
1 +
<
E(Po.
(33)
x (1 + 10c) {(PG.g")
(34)
where Equation 29 is by the choice of G' Line 16 of Algorithm
Equation 30 is by Equation 22
Equation 24 Equation 31 is since S S, Equation 32 since
arg min ((S (by the
construction of Algorithm Equation 33 is by Equation 26 to Equation
28 and Equation 34 holds
since < 1/2.
Running time:
9
Let 8 = Σ 1=1
Bil and assign e
10"
8 < 6k - 3. then, by the construction of Algorithm assume this is not the case.
3 the output can be computed in O(IPI- -8").
Hence, from now
Consider a single "for" iteration over the values of C
[B] during the execution of Line in the call
3 By the construction of every (5()), w in Line 5 of Algorithm we have that
to Algorithm
|s(0) X, for every i [B] and [[B Hence, since |S&l is the union of s(1) over every i G 3 and j E [[],]], recalling the definition of 3' trivially yields |Sal E O (AB'). By Lemma g
Line can be computed (2k{S&:))O()) E (A-3r) O(k) time. The rest of the lines can be computed
in P +k+ (1))()))) time, therefore, every iteration can be computed |P| (k + 1)0()) + (A- O(1) 1 time. Assigning e in the definition of À in the lemma yields À E 40kk) log (n/8). Since
10
3
there are
O (36N-3) iterations of the "for" loop we obtain a total running time of [P| _6k-3, (0(9)) (log (n/ (0)
6k - 3)
36

---

Under review as a conference paper at ICLR 2023
G ALGORITHM
1 STREAMING
In this section we prove that Algorithm 1 which gets P an n-signal of length n 2 2k is a power of 2, and c, ó (0, 1/10], returns c-approximation of P with failure probability most 8. The formal statement and its proof is given in Theorem 5
For the analysis will use the following corollary, which is inspired by Lemma 3.6 in Braverman et al. (2200) and proves that projecting a dataset on corresponding approximation for some function yields coreset for this function.
Corollary 5. Let P be an n-signal. Let B == ((P1,1)). (Po. be an (a, appppoxxiiiiiooonn of P; see Definition 3
For every i [8] let P. == {(z, rattoo, r)) (I, E P.). and let
p U P.; ie., P is the projection of P onto B. Let q = (c,d) E (R+*) such that + x.
poly(c', x)) * for every (z.-) P. Then ((P".)) S (1 +a) E(P..).
Proof. Let q be defined in the corollary. We have
((P",
[ratio(g, ratio(g(,:))
(35)
(x.y)EP:
(Iratio(a,.)) y/ + |ratio(q, vl)
(36)
1=1 (P.N)E
8
D(g.p) p) + D(app)
(37)
1= PEP:
PEP
(1 a) ((P.)).
(38)
where Equation 35 is by assigning the definition of D and the definitions from the corollary, Equa-
tion 366 is by the triangle inequality, Equation 37 by the definition of D, and Equation 38 is by the
definitions from the corollary.
At first glance, it may seem that there would a significant problem using the previously discussed variant of the Merge-Reduce scheme presented in Braverman et al. (2020). Indeed, using the classic version where combining each pair of coresets would yield that the guarantee on the final approxi- mation would be that the cost of the up polynomial in the data-set's 's size factor from the optimal solution (hence, the sample in SAMPLE-CORESES would be larger than the original dataset).
This be fixed by combining significantly larger number of nodes, which by the following observation would yield that height the tree would be [log log n],, and as a consequence that the final approximation would be logaiitgai in the dataset size.
The following theorem and Algorithm| I are the main result of this work.
Theorem 5. Let P be an n-signal, for n that a power 2, and put e, (0,1/10) Let (B, C, w) be the output of call to CORESET (P k e, 8); see Algorithm I (B, C, w) is an e-coreset of P; see Definition Moreover, the computation time of (B, C, w) is
With probubility at least 1 - 6,
2002)) O(k)/ log log(n) log(n) (k( lloool//)) 1og((/8)0(8),
and the memory words required to store (B, C,w) are in
(2k) 00) log(n) Hog()) log 1/
Which, when considering ls and log as constants yields that the running time is in O (n +o(1)) and the space is in O (12(1)
Proof. Let B = |/2 log log(ni] and = [n/B] be the values that are defined in the call CORESET (,,,, e, 0). Let (B,,... Bay) be the output of the call BATCH-APPROX(P,
37

---

Under review as a conference paper at ICLR 2023
in Line 4 of Algorithm 1 see Algorithm 5 Let [3'] and identify (P.. = B Let P. (z.z) (z, ( i.e. , ;p) is the partition computed in the call to
BATCH- APPROOX, 3). By the construction B, in Line 3 of Algorithm [ we have qi
arg min { (P: g). Let @ be the union over the pairs (c, c', E (RR* such that 1 + x polyyc', x) o 0 QE(R*)²
for every (ar, .) P. Hence, for every q EE 2 by assigning ::= P. B ((P.)), P P; and o, = in Corollary 5 we obtain
((P. 2.222((P.)))
(39)
Let (Bi. ... B'y be a set of biciterias, as defined as in Line 6 during the first iteration of the "while" loop in the call Algorithm I see Definition Let [bb]. and P' :=
U Y.i.e.
(YA))EEEB;
the union of all the sets of points in the bicritrias in B Let B; REDUCE (B), X1) computed in Algorithm Identify B. {{ (1), (Pr, 9-) f. and put Pa :- (x, E P' (z, E Pa).
for every a E [r]. i.c. every Pa is the set of points in p' that are approximated by qa- Replacing with 1/10,, with Bú and 5 with 64(4 in Lemma 2 yields that there is \ as defined in Line x of
Algorithm such that B, with probability at least
8/(4n) is an (2, (Bl)) apprrxxmaxiiinooonn to P
That is, with probability least 1 - 84(4n) we have
Σ e(Pa. 9a) 2 min
Σ ((P..g).
(40)
qE(ak)2
For every Bd E B/, let P- (z. E P P.). by the biciteria Ba; see Definition Plugging Equation 39 in the right side of Equation 40 yields that, with probability at least 1 - 6/(4,, we have
i.e. i.e. the points in P which are approximated
Σ ((Pa (. S min
Σ ((Pa.g).
gE(Rk)2
That is, with probability at least 1 - -8/(4n), B₁ is (4, (Bl) approxxiitiii to U Pa. Let Q be
a=1
the union over the pairs (c, E (R*)² such that + x poly(c', x)) + 0 for every (x, :)
E P.". Put
Hence, with probability at least 5/(4n)) for every q E Q by assigning P = U Pay B =
B,, P" U 4 and B Bi} in Corollary 5 we obtain
a=1
Σ ((Pa. 9) 5 E ((Pa. q).
a=1
iterations of the "while" loop, and 2n calls REDUCE. Hence, repeating the proof above recursively for every iteration of the "while" loop and the last call to REDUCE in Line 10 yields that with probability at least (1 - )/(4 2 1 - 5/2 we have that B computed in Line 10 is an (3[log log(n)] 8*)- approximation to P. for some integer 8 2 1.
By the construction of Algorithm I it trivially holds there are [log [ogg)o(n)]
By the construction of Algorithms 3 and that there are [log [oog()]]= - iterations of the "while" loop we have 3 < (24k) [log log(n]] Therefore, combining this with Lemma yields that there is X2 as defined in the call to Algorithm and proves the theorem.
Space complexity. Let d as defined in Algorithm [ (conditions were set in the previous part of the proof). From the previous section we have that B is O (log(n), log(n) ((1)+ll(())))) ( -approximation
38

---

Under review as a conference paper at ICLR 2023
of P. Hence, by the construction of Algorithm and assigning X2 (conditions set in the previous section) we have that [B, C,w) can be represented in (2k))(1), log(n) (oon))))+.ooo((100)))) space, which proves the claim for memory size.
Running time.
Note that for every iteration of the "while" loop in the call to CORESET(P, k. 6):
. By Lemma CORESET P. e,,,
2 and the previous analysis, we have that each call to REDUCE
B/ i X1) in
e,,) 6) takes ny g0(k) + (33*)1)) ) where ni = Σ Σ
M
B:EB; (Ki)))
Put v S n as the number of sets B computed in this iteration of the "while" loop.
Hence, since n ns we have that the computation time of the iteration is in
n' (000) + (33" )0(8)) = = (0(K) + (B333*\1) S n g0(h) (8" {1
By the computation of X1, 3 in the call to CORESET(P,, k. 0), and that 3 E log(n) (oo)+) (from the previous sections) yields that the computation time of the iteration
20112) n 0 log log( log(n) ((klog(A)) 1og(1/8)0(8).
By the construction of Algorithm there are [log log log(n)] - iterations of the "while" loop. Hence, the while-loop takes 20(k)) n (k)/ log log(n)) log O lon(k)) 1og(1/8)00M) time. Therefore, we have that the running time of the call Algorithm Dis
20(k)) n n O(k)/ log log(n)) loggn) ((klog(A)) 1og((18)0(8)
H FAST PRACTICAL HEURISTIC; ANALYSIS OF ALGORITHM
Unfortunately.sinee for the slow solver we used Pizzo al. (2018) which utilizes polynomial pro- gramming which takes significant running time, the running time of our robust algorithms is still large. Therefore, we suggested heuristic in Algorithm to run on top of our coreset. In this section we prove that, under some assumptions, this heuristic gives constant factor approximation.
For the sake of the analysis of Algorithm 6 we prove the following result for fitting a hyperplane to set of points.
H.1 FITTING PLANE TO POINTS
In Lemma 17 we will prove that a common heuristic for fitting hyperplanes to points does give approximation guarantees for points of bounded coordinates. This result would later be combined with some assumptions to give the desired approximation guarantees for Algorithm 6
Lemma 15. Let { (1),, .i)..... ..., (In,ya)} be set of 1 points on the plane, where xı + 0 for
every i E [n], let =
bxgb and let ls 2 an integer such that
Ei [m]: 1o S | S ka.
(41)
For every i E (n) let q item from G, sampled uniformly. Then, with probability at least 1/2 we have
Yi and let G = .c., cn. be multi-set of size n. Let e be random xz
| c yal S (2k2+ +1)
min CER (E
Σ
los c' Vel.
(42)
(Z..
39

---

Under review as a conference paper at ICLR 2023
Proof. Let c²
arg argmin CEER
Σ (a.D))
l d yl. By Markov's inequality, with probability least 1/2
we have
2 cc-c" I
Σ d'EG
cc-
cl ==
(43)
Suppose this event indeed occurs. For every (ar, y) P and d' G such that xe' y (there exist such el by the definition of G in the lemma), we have
rc y
|CC- zc'l
(44)
|x|| Ic c'1
(45)
|z| |cc c² - d' + e¹1
(46)
I |a|| (Ie* cl + /e c²l)
(47)
< lx k' + |a| lcl -cl
(48)
S kk' a + 1e'x yl.
(49)
where Equation i4 by the choice of é G as a value satisfying xe' = y. Equation 45 and Equa- tion ar by reorganizing the expression. Equation 47 is by the triangle inequality, and Equation 48
by the definition of k from Equation 43 and Equation 49 by assigning that [x] I ka (from the definition of P in the lemma, substituting := r in Equation 41 and that ze' = (from the choice of q G).
Hence,
Σ I0C- yl - (E.0)EP
IIC" yl S nkk'a a (x,y)EP
Σ
(50)
2k
cj c²l
(51)
2k
(52)
[
alv xc"
2k
(53)
[x]
(2.))P
S 2k
Σ
klyy - xc²1
(54)
(x,y)EP
= =2h
I0e* (a.
yl.
(55)
where Equation 50 is by summing over every (x, y) utilizing Equation 44 to Equation 49 Equation 51 is by assigning the definition of k' from Equation 43, Equation 52 is multiplying and
1/i dividing the expression inside the sum by a, Equation 53 follow from the definition of c; as in 2;
the lemma, Equation 54 is by Equation and Equation 55 is by reorganizing the expression.
By assuming that similar assumptions hold for every dimension separately we can generalize the previous lemma for higher dimensions, as done in the following lemma.
Lemma 16. Let P = {((x))
(1) (2)
x (d))), }
Rdd R be set of points, where
i=1
for every (i.1) E [n] [d] we have 20(1) # 0. let a5)
for every E [d], and let k
be an integer such that
alا)
v(i,)) E [n]] [d]
<
la
())
< a (5)
k
40

---

Under review as a conference paper at ICLR 2023
For every S P of size d let es Rd such that a .cg cg y 0; there is such value by properties
of linear regression. Let G be the multi-set {es C P. |S| d). Let be random item from G, sampled uniformly. Then, with probability at least 2- we have
Σ (o.y)EG
a c- vi $ (2k² +1)
min Σ (0,3))G
|a7 d' Val.
(56)
Proof. Let = (c), ca) E Rd, and j' E [d]. For every i E [n]] let vi == 1i (5') let v/4 ==
Lf Let P' = [(11( Mi), .. (Zn, bn)). G = {er,... cat be
+ Σ x,C, z,d4 and let c ==
multi sets, both of size n. Let be random item from G', sample uniformly, and let ct be d' were we substitute the j'th entry by c. By the definition of P and d' we have
Σ
Ix c" -yl
Σ (M.
lx 1--c-20 y/.
(57)
(Z.D)
als) S /..51 ka
From the definition of P in the lemma, for every (i, E [n] x [d]
we have
Hence, by the construction of pa we have a ,0') = Σ
|z], and for every (zt, v) E P' we have
(A.N)E
al'') |11| S kalf")
Thus, by substituting P by P' and G by G' in Lemma 15 with probability
k:
least 1/2, have
Σ
l yl S (2h² +1)
Σ
1x.c y)-
(x.y))P
Combining this with Equation 57 yields that with probability at least 1/2 we have
Σ c=" -5 (2k +1) +1)
Σ
l.. u1 (2k² 1) Σ 1of d' 5/
(P:
(x.9)EP)
(a.9)EP
where the equality is by the construction of P"
Let d' = -ch, -., daa E argmin
Σ
la=Td' - yl. and let ca)= == c. For every j E [d] let
d'Edd
(a.)))
G (c1,... Cj Cg.c+ SHI Cd). Let cf = c. By the proof above, for every j E [d], with probability
at least 1/2, we have
Σ (T.8)EP
G yl S (2k² + +1).
Σ
ax=
C y/.
(x.E))
Assigning cj c' arg min
Σ 1 ya and c
c in the above, combined with the
d'ERa
(2.))E
construction of G in the lemma yields Equation 56
By repeatedly taking a sample from the set G in the lemma above we obtain the following lemma that gives the desired approximation guarantees for linear regression under assumptions.
Lemma 17. Let P
{(af)) (2)
(1)) be i=
}"" C Ied IR be a set of n 2 points, where
there is an integer 2 such that
v(i.)) E [n] [d]
1
Σ la
h:
a
(58)
nk
7m
For every P of size let Rd such that
Σ
a c u) there is such value by properties
(a.y)ES
of linear regression. Let G be the multi-set that is the union over every S P of size |S| d. Let
41

---

Under review as a conference paper at ICLR 2023
E (0,1),c=22 2 and let X == max { [ 11. Let S G. = À where each value is sampled i.i.d and uniformly. With probability at least there is E S such that
Σ (x.0)EP
|x c yl - (2k² + 1)"
min ERR
Σ (E.y)EP
x c' v/.
(59)
Proof. By Lemma 16 for uniformly sampled e G with probability most 1 we have
Σ
c - yl > (2k² + 1)
min
Σ
xx'd vl-
(60)
d'ERd
(2a))r
Hence, by the union bound, the probability that Equation 60
holds for every E S is at most
(1-e)* S (1 e) 10g =
where the inequality is since À 2 logi-c 6.
H.2 SOLVER COMPUTATION, SEE DEFINITION
In this section we prove, for S C IR2 of size 2k satisfying {x-3 (z, y) E S} = 2k, that SOLVER(S) is never empty and that it can be computed in O (k-²) time; see Definition 6
This method is a generalization of a technique shown in NIST/SEMATECH (2021). While it plausible that there previous work that show the robustness of equivalent method ours, this section still important for the self containment of the work.
For this we define the following global definitions which would be used in the following section.
Definition 12. Let S = (I1,81), (12, 82),-- (22R. y22) E IR?, where {x (x,, y) E S} and {or (x, :) E }} are both of size 2k. Let A1, A2 E ((22)xk as follows
1, 11, 11 x
-11 x
V1 x
1, D2, 22
2
122 12, -22 22
x2
A
.A =
(61)
1, F2d, 22
22
-U2k T2k: 1/2
22
1/22
Let A= (A1 A2) be (2k) (2k) matrix, and let ã., (51, T2. ... T2k ). (111 12,
yek)
In the following lemma we derive conditions that any value that satisfies them is a candidate for an output to SOLVER(S).
Lemma 18. Suppose that there is b (b1, b2, b2x) E 22 such that the following holds:
(i) It holds that A ÿ. i.e. b is the solution to the constructed linear equation.
(ii) For every (x. E S we have 1 + poly (be+1, bb42, ... x) # O.
Put c= =(bi,bb,- b.. (b.,bg....,bb by) and d' = (bx+1. bbt2, ... b2x). We have that
Vp e S:
=0
Proof. Using the notation from the lemma we obtain
A-b
(62)
A1 A2. - V(a,y) E S poly(c, y x poly(d, (c, x)) y
(63)
(64)
(2. V(z,g) E S poly(c, x) y + y poly(c',2)
(65)
((. E S xo y. (1 + poly(c, x²) poly(c,x)
(66)
((..y) ES: i x (oly(c', y,
(67)
42

---

Under review as a conference paper at ICLR 2023
where Equation 62 is by property (i) satisfied by b. Equation 63 is by the definition of c' as
c = (b1, b2. ... bk) and c' = (bx+1, bk+2. b2k), and by the definition of A as A = (A1 A2), Equation 64 is by the construction of A, and A2 in Eguation 61 Equation 665 is by adding y x poly(c', .t) to both sides of the equation, Equation 666 is by rewriting the right side of the
equation, Equation 67 is by dividing both sides of the equation by
pollyc',, (c',,r)), x),, which is
legal operation by property (i) satisfied by b.
In the following lemma we will prove the existence of as defined in the previous lemma. Lemma 19. There is = (bı, bz, b2x) E TR2* such that the following holds:
(i) holds that A b = y. i.e. b the solution the constructed linear equation.
(ii) For every (x, E S we have 1 + x -plyy (bb+1, bx42: ... b2x),,
,,bx,,) x)) + O.
Proof. Proving that is invertible, i.c., proving property (i):
Recall the definition of A1, A2, and A from Definition 12 Let
B1 B2
AI,
Bs Ba
A2, (Bi, B2, B3, Ba) E Rixk
Since B1 and B2 are Vandermonde matrix for different z-value de)( det()) * 0: the values are different by the definition of 5 from Definition 12 Hence, by block matrix properties
for A to be invertible it suffices that det (B4- ByB, B3) + 0; see Petersen & Pedersen Let
31. U2, 31, 22 I such that (31 822 y. (#1 (22) I; the definition of & and ý in Definition 12 For every c E R let diag(c) E B be diagonal matrix, whose diagonal is c. Let Y1 -diag( Y2 == -iig 122) X1 == diag( and X₂ = diag(E2) be I matrices. By the construction of A and the previous definitions we have (B3, B4) (B,Y B2Y2X2). Hence,
Ba B2 B B3 B4 B2 BT B1Y
(68)
B1
B B2Y B2Y = B2 (Y2X2-Vik)
By the definition of S in Definition 12 we have det (Y2 X2 - Vi xi) * O. Hence, assigning that (B2) # yields that det (B+ B2 BT² BB) # O. and consecutively that A is invertible.
Proving property (ii):
Let = (b1, b2.b............... b2x)) 2 such that A A.6 b ÿ; there is such value by the proof that A is invertible in the previous part of the proof. Let c' = (bx+1, bx42.-.., b2x).
It can be seen that even if there is (z,, y) E S such that 1 + poly(c', ; x) = 0, we can add arbitrarily small noise to the y values (without destroying the condition from the previous part), which would tweak c' such that for every (x, y) E S we would have 1 + poly(c', 2)) # O.
In the following lemma we combine the previous lemmas to obtain the previously mentioned desired properties SOLVER. Lemma 20. We have that SOLVER(S) never empty and can be computed in (I²) time.
Proof. Let and ÿ as defined in Definition
12 By the proof of Lemma we have (eg(A) + O. Let b E 2 such that b ÿ. Let e (b1, b..... ,ba) and c' [bk+1, bet2. bbx)).
By the of Lemma 19 for every (x, y) E S we have 1 + +-r--oollll poly(c,, x) * 0. Therefore, since b satisfies all the conditions in Lemma 18 (c, ) is candidate for an output for SOLVER(S).
Let (c",c') E (IR*) such that for every p E S we have D(c, c' p) = O. By the proof of Lemma 18 we have that (c*lc"t) satisfies that A- = ÿ. Since deg(A) # 0 we have that there a unique b E 22 such that A = ÿ. Therefore, (c", c'*) = (c,c'), which yields that (c, c') is the unique candidate for solution to SOLVER(S). Computation time:
By the previous part of the proof we have that SOLVER(S) (c, c'). The constructing of A in
43

---

Under review as a conference paper at ICLR 2023
Definition 12 takes O(k2) time. Solving system of linear equations with 2k equations and 2/: parameters can be done in O(k") time. Hence, we can compute in O(A*), which yields that (c, d') can be computed in (k3)) time.
H.3 ANALYSIS OF ALGORITHM 66 FAST-CENTROI--SET
In the following lemma we combine the previous result with some assumptions to obtain the desired guarantees for Algorithm
Lemma 21. Let P {(11, ((11,91).... (.n,)...,,,, C RR, where
2ki be a set of points with unique first coonlinates with non equal zero, and where for every S C P of size 2k we have
{ar y (I,y) E ES]
2k. For every (144)
P let T. (x* -(xWW) x²) R22
where x¹' (1, x..
For every [n] let (a : , ,a; a(ah)) Ir. Suppose there
is W E (1)) such that for every (i,5) E [m] x [2k] we have
51)
10001
S
nk' *E(n
Let 8 E (), = 4-k, and let X == max {[og 1}. Let G be the oulput of a call to
FAST-CENTROID-SETVEE SET(P, A); see Algorithm 6
Let (a, di) arg min (P, Let a (2k +1)2
QE(RT)2
and suppose that there is (c, c') E Such that
Σ
1 -clcd) - wilsa
Σ (PLN))E
- (c) Vil.
(69)
(Z..E)E
which, by the construction of FAST-CENTROODD-SEE happens with probability at least 1 8; follows from assigning P == {(81, ... (an, in Lemma 17 Suppose that there is p 2 1 such that
for every (I. y) E we have
1 + poly(c, x) S sp. + polyyooy),
(70)
then, we have that
(c, S ap- (c,,))))
Proof. We have that
poly 22:)
((P. (c,) = Σ
I x pooyy (c', xx.) V/
(71)
(E
poly(e, - y/ (1 (1+ xi poly(d(
Σ
(72)
1 I+ (o,
(E..)JPP)
J (c -
(73)
1 + D4 poly(c', (oly(c',zz) xx:)
(a..))eP
b (ci di) mi
Sa.
Σ (E
(74)
I x, poly(c'.n) ..,)
1 vy poly(d, 1 1 x poly(c,
+ (c) (G) 31
S app
Σ (E.
(75)
1 1 x. poly(c', .x:)
boT (cr d) - yal 1 x4 poly(ch, x.,)
ap-
(76)
(E.P))P
poly v2)
=ap
I x (oly(c,,
yb
(77)
(Z.D))P
= (c),
(78)
44

---

Under review as a conference paper at ICLR 2023
where Equation 71 is by the definition of l in Definition Equation 72 is by reorganizing the expression (taking common denominator), Equation 73 is by assigning the construction i; in
the lemma, Equation 74 is by assigning Equation 69 Equation 75 is by assigning Equation 70
+ x .poly (g,y( inside the absolute value which is legal operation Equation is by moving + poll(c',x))
since Vs, t ||| |t]
Ist.. Equation 77 is by reorganizing the expression and assigning the
definition of iet, and Equation 78 is by the definition of in Definition 2
1 FULL RESULTS FOR REAL LIFE DATA TESTS
1.1 FULL RESULTS FOR THE TEST OVER THE DATASET CHEN (2099)
Fig. presents the dataset readings along with the approximation computed in FRFF-coreses Scipy's rational function fitting computed via scipy.opp im ze mi minnimia ze, and 3th degree polynomial computed using the numpy- po yfit function, which minimizes the sum of squared distances between the polynomial and the input. For fair comparison, all three methods have been allowed free parameters. In particular, our rational function and Scipy's 's rational function have degree 1 in the enumerator and 2 in the denominator (there variable in the denominator is set to 1), while the polynomial is of degree 3.
free parameters, since the free
Observe that in the following examples the 3th degree polynomial yielded slightly smaller loss than our method, this is in contrast to the case in the example in Fig, where the 3th degree poly- nomial yielded significantly worse results. We believe that this occurred due the "un-noisy" data corresponding to a more "smooth" function, while in Fig. 4 the function was "less" smooth due to the data generation.
TEMP for year 2013
DEWP for year 2013
40
GT
GT
Sclpy
Sclpy
30
Ours
20
Curs
Poly-fit
Poly-fit
Value
Value
1000
2000
3000
4000
5000
6000
7000
1300 2000
3000
4000
5000
6000
7000
Incex
Incex
Figure 9: The n-signal corresponding TEMP and DEWP properties from the year 2013 of Dataset Chen (2019), along with three fitted functions: (i) the rational function of degree (i.c., degree in the enumerator and 2 in the denominator) computed in our algorithm CRFF-coreset (ii) the output of a call to scipy. opt imi ze . minimiiii ze that aims to fit rational function of de- gree 2 the input signal, and (iii) Polynomial of degree 3, computed using the numpy polyfit function. For fair comparison, all three methods use 4 free parameters.
In this section we include all the results computed for Chen (019) in section 3.2
As there is relatively little change in the computational time plot over the sample sizes and features we show the mean results for the year 2016 for the temperature feature in the following table.
Method
Time (seconds)
RFF-coreset
0.1361
FREF PRFF-coreset
0.1187
Gradient
0.0134
CorCeee
0.8334
RandomSample
0.0022
NearConvexCoreset
0.5045
45

---

Under review as a conference paper at ICLR 2023
The DEAP
for 2013
TEMe 2013
R
CuntiT
Ourdit
Ounder
Gindor
Grasleet
J000 20w.e 11
Carmmnt
HoarDrr Cortoreed
Hour Cor woxDrrsdd
6.0
630
5:35
6.20
0.25
6:30
6.5
0.10
0.15
0.20
0.25
0.30
0.5
0.3
8.35
650
0.25
0.33
235
The plot for DEWP
2014
The for FREES year 2014.
The poo TEMP year 2014.
177
OueTFIT
GuaFitr
Oradicn
Bandondargie
Rindernanpte
Fandordample
Year Car Coseeatt
Hear Corman
Comoatt CTP pe original Dara
Donoers Cre parcett crigina
The plot for DCWP for 2015
The for FRITS for 2015
The pltr for TEMP for year 2015
Crectent
Rinds réainie vnstoneet
Rendoriaaeee encerratt
The plot for DEWP for yoar 2016
Tre for PRES Seryear 2016
The plor for TEMP your 2016.
A.Corwet Rondondenccc
J--Coment
Nander Comade
Conaed's 21 percento original 1873
Conmufaabe Pn personts ofg
Consetts paIceno crigrna
Figure 10: results for the experiment from Section 3.2 the compression, in percents of the original data, and the -axxi presents the approximation error of each compression scheme, using Evaluation method (i). The plots corresponds: (left to right) to the DEWP, PRESS, and TEMP properties in the dataset (Chen (2019), and (top to bottom): to the years 2013, 2014, 2015, and 2016. Methods RandomSample and NearConvex very large errors and are clipped in some cases.
The X-axis presents, the size of the size of
produced
46

---

Under review as a conference paper at ICLR 2023
The piot DEWP year 2013
pit yoe
ditt TEMP
Apper spperiisan an eng sproort
Joreet
the
Craddba pepturr vaygiual sulu
Conodtaaa ro argiiaal
DEWP your
oee you 2014,
Duritr
1gon oite und cpecents
Gradect
8
5
0
0.32
C20
0.23
0.59
5:35
0.20
0.23
9:35
230
2015.
5.
2015
CunErT
QuediT
Ounder
craseett
Carnett
torestt
Hear Cndrrrat
Hear Cor Dereeett
0.85
COMMeTcIOn
335
235
3.55
1.30
1.0
0.55
0.3
5.35
6.20
of
0.25
0:30
3.55
332
835
5:50
0.30
The plot for DEMP Sor 2015.
5.0
gldt for PRES your 2015
The Dr TEMP 2015
orddent
Randondample
AindenGandte
RandorSemphe
Nour Oar Coroestr
0.15
0.20
0.35
232
6.15
0.20
2.25
Figure 11: Evaluation of Method (ii,, similar to Method(i) in Fig. 10
I.2 TEST FOR THE DATASET
ITO 2016
In this test we will use the dataset from Vito (0166) which contains a "yearly measurement of of gas multisensor device deployed on the field in an Italian city" (cited from Vito (0016)).
Fig. 12 presents the dataset readings along with the approximation computed in FRFF-coresed Scipy's rational function fitting computed via Scipy ootiiiiiiii minimizee, and Polynomial of degree 3, computed using the numpy. polyfit function, which minimizes the sum of squared distances between the polynomial and the input. For fair comparison, all three methods have been allowed free parameters. In particular, our rational function and Scipy's 's rational function have free parameters, since the free
degree 1 in the enumerator and 2 in the denominator (there variable in the denominator is set to 1), while the polynomial is of degree 3.
Observe (as in Fig. 9 that in the following examples the 3th degree polynomial yielded slightly smaller loss than our method, this is in contrast to the case in the example in Fig. where the 3th degree polynomial yielded significantly worse results. We believe that this occurred due the "un- noisy" data corresponding to more "smooth" function, while in Fig. 4 the function was "less" smooth due the data generation.
47

---

Under review as a conference paper at ICLR 2023
quality example. Temp
quality example, Humidity
GT
CT
Scipy
Ours Poly-fit
Our
Poly-fit
30
1.5
Value
Value
20
1.0
10
0.5
0.0
2000
Index
Figure 12: Visual illustration of the n-signal P corresponding to Temperature and Absolute Humid- ity properties of the Dataset Vito 2016), along with rational function fitting methods: (i) using the approximate rational function computed in our algorithm FRFF-coresed (ii) the output of call to Scipy. optimiie minimize ze that aims fit rational function of degree 2 to the input signal, and (iii) Polynomial of degree 3, computed using the numpy. polyff by iit function. For fair comparison, all three methods use 4 free parameters.
mi
Repeating the test
3.2 for this data set yields the following plots.
Approsimation erhor in percants
FUFFFRFF
Agproximation error in percents
FRFF
E. Coreset
fu-Coreset RandomSample NearCorvexCareset
NearCorwenConesst
0.10
percents original
orriginnal
14
DunRFF
Our
Aoprodmaaton in percents
Gradient
Approximation enror in percents
Gradient
Lu-Coreset
20
NeanCorvexCareset
RandomSamppe
30
RandomSample HesrtorwesCureset
0.05
0.10
0.15
0.20
0.25
0.30
0.05
0.10
0.15
0.20
0.25
0.30
Coreset's size percents of original data
Co size in percents of priginal data
Figure 13: Results for experiment similar to the the experiment from Section 3.1 but with dataset Vito (2016). The r-axis shows the compression ration, with respect to percents of the origi- nal data. The y-axis shows the approximation error of each compression scheme, for the properties Temperature (left column) and Absolute Humidity (right column). The upper and lower rows present Evaluations (i) and (ii) respectively. The error bars present the 25% and the 75% percentiles. Meth- ods RandomSample and NearConvexCoresee produced very large errors and are thus in some cases were clipped.
48

---

Under review as a conference paper at ICLR 2023
Due to there being relatively little change in the computational time over the features and sample sizes we show the mean results in the following table, which contains the times only for the Absolute Humidity feature in the dataset.
Method
Time for the Humidity feature (sec)
RFF-coreset Gradient
0,1422
0.1172
0.0434
Coreset
0.7476
RandomSample
0.0024
NearConvexCoreset
0.6247
ADDITIONAL DISCUSSION
J.1
FIG.
This figure demonstrates that rational function fitting is more suitable than polynomial fitting, for a data relatively normal dataset that is essentially is a set of samples from an exponential function. This also shows that computing any of those fitting functions either on top of the full data coreset produces similar results.
J.2 SECTION 3.1
In this section we demonstrated that our algorithms achieved the best accuracy consistently across the varying signal's length, where RFF corcorseet achieved the best performance and followed by coreset The main results are summarised in Fig. While when considering Evaluation (i) RandomSample, le, that is essentially random sample from the input, yielded good quality, in Evaluation (ii) the values where so large that they where clipped. We, informally, believe that it accrued since the near optimal query considered in Evaluation is not "very far" from any point in the generated data set and as such no point in the data is "very important" for the near optimal query, but as presented Observation this not the case for all the queries even for all the data sets (suppose dataset where all the points lay a query beside one point that has y-value approaching 0o, this single point would be "very important").
In this experiment we obtained significant speed improvement compared to all the other methods beside RandomSample and Gradient, where the later is based on SciPy's library Virtamen et al. (220)) function Scipy. opt wiriimiee mminimiize and it can be expected since random sample would obviously be efficient and the function Scipy. apptpimiii ze minimi ze (at least for our parameters and the best of knowledge) used optimization methods from Nocedal & Wright (2006) that at some cases can yield very fast a local minimum (but not a global one). Hence, while RandomSample and Gradient had lower running time as observed Fig. 2 they had significantly worse results.
Observe that while Loo Coreset which uses the guaranteed approximation for max deviation from Peiris et al. (2021) might seem valid heuristic at first glance, our results in Fig demon- strated that while was the closest contestant to our methods in terms of quality, it came at the price of significantly larger running time (it was the only time plot that was clipped). While is plausible that follows from our improper parameter tuning. we believe that comes from the use linear programming solvers which to the best of our knowledge there are no solvers with running time O (n²): to the best of our knowledge, for the time of writing, the lowest bound is the one in Cohen et al. (2019).
J.3 SECTION
In the experiments we obtained very similar results in the experiment in Section 3.1 which vali- dates our observation above. We note that at some cases TRFF-coreses achieved better quality than RFF-coreset, where this mostly occurred for Evaluation (i). Informally believe that this occurred since the approximation in FRFF FRFF-coreset was very similar the near optimal query considered, while the BI-criteria in RFF-coreset might had lower loss but farther from the
49

---

Under review as a conference paper at ICLR 2023
query considered. Hence, this difference effected the difference between the results for Evaluation (i) and (ii), where for the later RFF RFF-coreset achieved almost consistently better results while in the later lose in many cases. Observe especially the PRES property in Section 3.2 where in Eval- uation (i) we had RFF-coreset only worse equivalent results than PRFF-coresed but for Evaluation (ii) we had RFF-coreset that gave significantly better results than FRFF-coreset.
We note that for TEMP for the year 2013 in Fig. 11 where we used Evaluation (ii), and Fig. 3.1 for the Evaluation (ii) of the Temperature property we had equivalent quality between RFF coreset and FRFF-coreset, where the later had better results in some instances.
J.3.1 FIGURES AND
In contrast to the example in Fig. f in those examples the polynomial fitting with the same number of parameters yielded slightly better results. This is non surprising result that follows intuitively from considering that as rational functions might yield hetter fitting for some datasets (especially "non-smooth" |Peirss et al. (2021) ) for some datasets it is possible have an opposite effect where polynomial fitting outperforms the rational functions fitting. We believe that this is a specific exam- ple of Wolperl (1996) that is related the well known "No free lunch theorem") Wolpert & Maeready 1197..
Nonetheless, even those examples our approximation outperforms the Scipy's 's library Virtanen et al. (020) approximation via Scipy. opt imi ze minimizz by a significant margin and gives only slightly worse results than the Numpy's library Harris et al. (2020) polynomial fitting via numpy- polyfit..
Observe that this does not invalidate the real-world data experiments in Section 3 since while polynomial fitting yields lower loss we focused the task of fitting rational functions that is valid optimization problem on its own. Also we note that our rational function was obtained from and it is plausible that the optimal rational function (with non constant denomina- tor) would outperform the optimal fitting polynomial function with equal number of free parameters.
J.4 DISCUSSION ON THE THEORETICAL RESULT
Another contribution of this work is the theoretical results. Our main result which is the basis of our tested methods is Theorem 5 which informally can be summarised as follows.
Given an n-signal we can compress it sub-linear size in quasi-linear time, and the com- pression with defined probability allows use to compute {(P, q), for every query q E (R*) up to multiplicative factor of (1 c).
In our eyes another main contribution of this work is the very uncommon framework used in this work, whose overview is in Section 2.2 In particular we used the Merge- Reduce scheme presented in inBBravemman al. (2020) to maintain a B1- BI-CRITERIA tree, where it is usually presented to maintain on-line coresets. We also wish to mention the combination of the BI-CRITERIA approximations, where we essentially "trimmed" the approximation chunks where the data is "well-behaved" and this allowed use to compute a "leaky-corescr each query. this "leaky-coreset" used in union with an exhaustive search over the "leaks" that are the BI-CRITERIA in the input where the coreset fails.
that fails for a bounded number of BI-CRITERIA for
While those methods might be useful only the researchers in the coreset community, we hope that those novel methods might help build coresets for problems where there was coreset only for very specific case, which from bottom up look can be seen as the focus of this work. i.e., we start with a coreset only for very restricted case (both in query and form) and we build upon this to obtain an approximation and consecutively an e-coreset without any such limitations.
50


Reviews:
[{"review_id": "XxOeiucURj", "reviewer": "Reviewer_Vhf7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper is concerned with the problem of approximating a time-series by a rational function of degree at most k (which is the ratio of two polynomials of degree at most k each), and more specifically, with constructing a coreset for this problem. A coreset of a given problem instance is an instance of a much smaller related problem (typically a small weighted subset of the original instance), which approximately preserves the value (or loss) of every solution to the original problem. This is useful since an approximate solution can then be computed on the small coreset instead of the original large problem. This paper suggests a coreset of size polylog(n) * k^(loglog n) / epsilon^2, that preserves the approximation loss up to 1+/-epsilon, though the notion of coreset is non-standard (not a weighted subset).\n\nTechnically, the construction relies on the well-known sensitivity framework for constructing coresets. This framework is based on importance sampling, where the coreset is formed by sampling random points from the original problem with probability proportional to a measure called \"sensitivity\", which measures how important is the point for solving the problem on the given instance. The sensitivities are estimated by an initial coarse (bicriteria) solution to the problem. The majority of technical effort in this paper is constructing the initial bicriteria solution, where the notion of bicriteria here is that the time-series is approximated by a piecewise rational function degree k instead of just one such function.", "summary_of_the_review": "The paper studies a meaningful problem and seems to contain interesting ideas. However, there are some gaps and unclarities in the overall reasoning (how is the non-standard notion of coreset defined here used for fast approximation) and in the experimental design, that I would like to clarify before recommending to accept. I also found the technical writing rather unapproachable and was unable to verify correctness, though this may be partly because I lack background on the topic.", "strength_and_weaknesses": "Strengths: The problem studied seems meaningful and interesting, and the proposed solution also seems to be potentially interesting and contain new ideas. I am not familiar with prior work on this problem, but it seems to me an intriguing direction that restricting the solution space to degree-k rational functions could give rise to coresets of size proportional to only k, and it was interesting to me that the useful notion of bicriteria approximation here was a piecewise approximation (and not, say, a single rational function with degree somewhat larger than k, which would have been my first thought). Also, the problem and the algorithms and proofs are defined rigorously and in detail, which I appreciated.\n\nWeaknesses: the two big ones for me are the usability of the defined notion of coreset, and the experimental design; I hope to see some clarification from the authors on both. In more detail:\n\n1. How is this non-standard notion of coresets useful for approximation?Coresets are usually defined (for example in the context of clustering) as weighted subsets of the original set of points. This is useful since we can apply any exact or approximate (albeit slow) algorithm to the coreset instead of the original problem (for example, solve k-means on a subset instead of the whole set), and obtain a fast approximate algorithm.\n\nHere, the coreset is not a weighted subset, but a more general object (a combination of a weighted set and a piecewise rational function). Do we have algorithms to find an (exactly or approximately) optimal degree-k rational approximation for this object? I am not familiar with this space of problem and possibly I am missing something basic here, but I could not find it mentioned in the paper. This is important, since without such an algorithm it is not clear that this notion of coreset is of any use: once we constructed the coreset, what do we do with it to find a good approximation for the original problem? Typically, a coreset leads as a corollary to a theorem that states \"the original problem can be solved up to X approximation in running time Y\", the proof being by constructing the coreset and then running on it a known (exact or approximate) algorithm. Can you state such a theorem for RFF as a corollary of Theorem 1?\n\n2. Experimental design:Related to the above, I am not sure what the evaluation in the experiments is actually measuring, and whether it is actually constructing a degree-k rational approximation of the input signals, as Def 2 requires. The \"Evaluation\" paragraph in section 3 is too unclear and it would help to explain better and in more detail what is going on there. I understand that (as the paragraph mentions) finding the groundtruth solution to each signal is too computationally costly, but this is not necessary: the experiment I would have liked to see is using each of the evaluated coresets to construct a degree-k rational approximation, and measure the approximation loss (sum of differences) between the original signal and the approximation, and then compare the losses across the evaluated methods. This would have also answered my question about using the coresets to actually obtain an approximation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "MVGSADDiH4X", "reviewer": "Reviewer_EJmJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers the problem of fitting a rational function to a time series. The authors provide a coreset construction that gets a time-series and returns a small coreset that approximates its sum of (fitting) distances to any rational functions of constant degree. The size of the coreset is sub-linear in $n$ and quadratic in $\\varepsilon^{-1}$. The empirical results on real and synthetic datasets show that the coreset size and the estimation error is smaller compared to the baselines.", "summary_of_the_review": "The paper considers an interesting problem of fitting a rational function to a time series, and propose a coreset construction framework. The technical results are novel and solid. The writing and clarify can be improved and needs a more careful literature search. \n\nOverall, I do not recommend acceptance now. But I may raise my score if the authors can address my questions well.", "strength_and_weaknesses": "Strengths:\n- The problem of coreset construction for the rational function is well motivated. \n- The idea of combining the construction of a weaker coreset with a merge-reduce tree for maintaining a bi-criteria approximation is novel, and can significantly reduce the total sensitivity of points.\n\nWeaknesses:\n- Missing discussion on several related literature. The authors mentioned that \"To our knowledge, this is the first coreset for stochastic signals.\" As I know, time series coreset has been considered before, e.g., [Lingxiao Huang et al., Coresets for Regressions with Panel Data, NeurIPS 2020] and [Lingxiao Huang et al., Coresets for Time Series Clustering, NeurIPS 2021]. I think a comparison with models in these papers is necessary.\n- Def 4. The definition comes sudden and lacks explanations. Why including B in the coreset definition? What happens if B is the optimal solution to the fitting problem? How can we use this coreset for acceleration?\n- The empirical section is confusing. The authors only refer to figures and do not provide an analysis of the empirical results. At least, the authors should discuss what the advantage of their coresets compared to baselines, provide some concrete numbers or advantage ratios, and summarize the punchlines.\n- An advantage of coreset is to accelerate the original optimization algorithm due to the small size. However, I don't see the acceleration analysis in the empirical section.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "CQ_D_qqcnXV", "reviewer": "Reviewer_oFkV", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of building a coreset for fitting rational functions to time series data. In particular, suppose $y_1, ..., y_n \\in\\mathbb{R}$ is a time series. Then, in rational function fitting, we want to find a rational function $r$ of degree $k$ such that $r(i) \\approx y_i$. We formally measure error with the $\\ell_1$ metric, the sum of absolute errors.\n\nThis paper isn't as much about solving this problem, as it is about _compressing_ the problem, so we want to find a small data structure such that all rational functions $r$ have their loss with respect to $y$ preserved within a multiplicative $(1\\pm\\varepsilon)$ factor. So, in order to approximately solve the full problem on all $n$ time points, it suffices to minimize over rational functions on this smaller coreset.\n\nFor constant failure probability, the paper builds such a coreset in $\\tilde{O}(2^{O(k^2)} n^{O(\\frac{k}{\\log \\log n})})$ time and it uses $\\tilde{O}(\\frac{1}{\\varepsilon^2} \\text{poly}(k) \\log^{O(\\log(k))}(n) )$ space. For constant degree $k$, this is $O(n^{1+o(1)})$ time and $O(\n\\frac{\\text{polylog}(n)}{\\varepsilon^2})$ space.\n\nThe coreset is constructed in two parts:\n1. First, they use a bicriteria-approximation algorithm to partition the time domain into $O(\\log n)$ subintervals, and approximately fit a rational function $r_i$ to each subinterval. _This is an approximation because each $r_i$ is an approximate minimizer, and is bicriteria because it returns $O(\\log(n))$ rational functions instead of just one._\n2. Then, since this bicriteria approximation is not accurate everyone, a randomized \"sensitivity sampling\" stage explicitly stores the time points where both (i) the bicriteria approximation is inaccurate and (ii) where a rational function could be able interpolate that point.\n\nThe loss of an arbitrary rational $r$ function against the full dataset is then approximated by sum of the loss of $r$ on the sampled points and the sum of the distance between $r$ and $r_i$ on the subintervals created by the bicriteria approximation. The authors say that most of the technical novelty and effort goes into building the bicriteria approximation.", "summary_of_the_review": "The paper seems probably cool, and I want to like it, but the authors didn't give me good reason to think their claims are correct. As such, I reject the paper. A rewrite of the paper could definitely be published though (supposing the results are correct).", "strength_and_weaknesses": "[edit: fixed the block quote in _Part 1_ to correctly separate my writing from the paper's]\n\nThis paper gave me some whiplash. It's got some sections written really clearly, and some which are brutally opaque. I wrote a long summary for this paper because it took me a long time to just understand the algorithm and construction of the paper. In the places it's opaque, I'm not comfortable saying that I believe it's correct. Because of concern about correctness, I'm not comfortable accepting this paper.\n\n### Part 1: Introduction and Motivation\n\nThe paper starts with an interesting and compelling story about why MSE is a bad loss metric for fitting time series data: often time series models like the \"auto-regressive\" model have variance that grow exponentially, so minimizing the MSE is just fitting the last couple data points. So, we should consider fitting in some other metric that. The authors then define a generating function and seem to fail to give any fundamentally new metric, and end up using $\\ell_1$ error instead of MSE (i.e. $\\ell_2$) error.\n\nI'd like to know what the authors were going for, because minimizing the $\\ell_1$ loss would also just fit the last few data points from an exponentially growing time series.\n\nRegardless, fitting a time series in $\\ell_1$ norm is a perfectly well motivated problem, so it's not a huge problem, but it's certainly confusing. I really wished they stuck the landing and suggested a new way to talk about error in time series data though.\n\nThis question of error metric is a great example of how Section 1 of the paper is a mix of extremely clear and very confusing writing. Beyond this one example, there's also a few times where the authors just introduce a term from the literature without any explanation. As someone not familiar with this particular term from the prior work, I found the following line pretty funny:\n> This is due to the three main coreset properties: merge and reduce.\n\nI have no idea why \"merge and reduce\" is three properties, and this is not explained in the introduction. The authors similarly do this with \"$(\\alpha,\\beta)$-approximation\", which ends up being super important in this paper, and it was only by digging in the prior work that I figured out that \"$(\\alpha,\\beta)$-approximation\" means _bicriteria approximation_. \"Merge and reduce\", and bicriteria approximation are both heavily used in this paper, and not clearly saying what these intuitively are in the introduction is a huge misstep that really hurts the legibility of the paper.\n\n## Part 2: Describing how the Algorithms Work\n\nPage 5 of this paper is a summary of how they construct the bicriteria approximation and the subsampled dataset that comprise their coreset. This page took me an immense amount of effort to understand _what the algorithms intuitively are doing_, and I don't have an intuition for why these algorithm construct a near-optimal coreset. **The clarity issues from the introduction could be fixed with a minor revision, but the issue of clarity on this page is more brutal.**\n\nThis page is full of high-level technical descriptions of what the various parts of various algorithms do. I'm not going to belabor a huge list of points that confused me, but I will give a demonstrative example. I'll include broader frustrations about this writing in my list of typos & suggested edits.\n\nFor my example, consider the middle line from the first paragraph in the section \"Algorithm 3: the merge-reduce step\", which reads:\n> This is by computing the following for every possible subset $C \\subseteq B$ of size $\\beta − 6k + 3$\n\nI can understand that this algorithm is given a set $B$, and it can search over subsets of size $\\beta - 6k +3$. I have no idea why $-6k+3$ is meaningful, what's it's used for in the analysis, if the numbers $6$ and $3$ are important, or anything else about it. This whole page is full of instructions whose value is completely lost on me.\n\n### Part 2 again: The (hidden?) Strengths\n\nThe frustrating layer under this somewhat brutal writeup, was that as I progressed through page 5 of the paper, I could see there's a careful and clever design under all of this. The details seem precise. When I wanted to understand a claim in a bit more detail, there were easy-to-find formalisms in the appendix. I am emotionally convinced there's a cool result with a neat and careful construction under this all. I just haven't been given a correctness argument that I could review in the body of the paper.\n\nI think the authors could reduce the formal specification of the algorithms on page 5. Then, remove the formal algorithm from the body of the paper, and replace it with an informal pseudocode that skips over implementation details and covers more high-level ideas. Then, with the recovered space, justify more clearly why the construction is accurate with high probability.\n\n### Part 3: Experiments\n\nThe experiments are decently cool. It's a hard problem with an exponential dependence on the degree of the rational function, so the experiments are just stated for degree 2 rational functions. But, for this setting, the experiments are convincingly interesting, and show that the coresets can be pretty efficient for real data (figure 3 on page 9).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject