Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.

This 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.

For 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(
\frac{\text{polylog}(n)}{\varepsilon^2})$ space.

The coreset is constructed in two parts:
1. 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._
2. 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.

The 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.
strength_and_weaknesses: [edit: fixed the block quote in _Part 1_ to correctly separate my writing from the paper's]

This 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.

### Part 1: Introduction and Motivation

The 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.

I'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.

Regardless, 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.

This 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:
> This is due to the three main coreset properties: merge and reduce.

I 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.

## Part 2: Describing how the Algorithms Work

Page 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.**

This 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.

For my example, consider the middle line from the first paragraph in the section "Algorithm 3: the merge-reduce step", which reads:
> This is by computing the following for every possible subset $C \subseteq B$ of size $\beta − 6k + 3$

I 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.

### Part 2 again: The (hidden?) Strengths

The 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.

I 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.

### Part 3: Experiments

The 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).

clarity,_quality,_novelty_and_reproducibility: I've already written a bunch about a lack of clarity leads to a certain lack of quality in this paper.

The paper definitely seems novel and significant enough for publication though. The results as written are compelling.

I devote the rest of this space to a list of typos.

### Typos

1. [Page 1, background paragraph] "the references therein" instead of "reference therein"
1. [Page 2, section 1.2 first paragraph] Say "Informally, given an input signal of d-dimensional points" instead. Also, why not just say 2-dimensional instead of d-dimensional?
1. [Page 2, section 1.2 last paragraph] If there's no coreset which is a weighted subset, then it makes sense to use a bicriteria approximation in addition. But, why restrict yourself to consequtive integers in the first dimension then? There's nothing wrong with assuming that to be the input data given to you, but the flow of this paragraph's logic / justification doesn't quiet stand up.
1. [Figure 4] Not a big deal, but this might read a bit more clearly if we also had an error plot, showing if any approximations are especially accurate or innacurate, and where those accuracies/innaccuracies are.
1. [Throughout the paper] Feldman & Langberg 2011a and 2011b are the same paper. This is cited a lot, so it's helpful to realize they're the same paper.
1. [Page 3, section 1.4 last paragraph] Say "believe" instead of "expect", or some other weaker language. This sentence comes off kinda weird with "expect" there.
1. [Page 3, section 1.4 last paragraph] I have no idea what the "have few dependent recursive functions ..." phrase means. No clue what message you're trying to send with this sentence.
1. [Page 3, section 2.1 first line] I'd probably say "set of k-dimensional" instead of "union of k-dimensional". Not sure what's getting union'ed here.
1. [Page 4, section 2.1 just before definition 2] "Projection of f onto P" makes _a lot_ more sense than the "Projection of P onto f". f exists where P doesn't, so we project f onto P by evaluating f on that interval.
1. [Page 4, definition 2] Why define a rational function this way? Why not just leave it be a ratio of two arbitrary polynomials. Justify this in text.
1. [Page 4, paragraph after definition 2] Remove the comma after "Definition 2"
1. [Page 4, paragraph after definition 2] "approximation _as_ Feldmen & Langberg (2011) defined"
1. [Page 4, paragraph after definition 2] Expliciltly site section 4.2 of Feldmen & Langberg (2011) and explicitly use the language "bicriteria approximation"
1. [Page 4, definition 3] Consider using the language "consecutive intervals" instead of "consecutive sets"
1. [Page 4, definition 3] Missing subscript on $P1$
1. [Page 5, first line] Use the standardized notation $n^{o(1)}/\varepsilon^2$ instead of this $n^{\phi}$ for any phi notation. It's standard in TCS
1. [Page 5, first line] If it's with probability $1-\delta$, then $\delta$ should appear in the space complexity
1. [Page 5, first line] Remove "; see Definition 4", that definition was 2 lines ago.
1. [Page 5, first paragraph] It's algorithm 2, not algorithm 1
1. [Page 5, first paragraph] I'd say something like "probability of placing a point $p \in P$ into the samplet set C"
1. [Page 5, first paragraph] Write out the formal probability proportionality, so it's more clear. It's quick to state something like $Pr[\text{picking } p_i] \propto D(q_i, p_i)$.
1. [Page 5, second paragraph] To clarify the break in the sentence, add "it has" after "$\beta$ child nodes, " and before "$O(\beta^i)$ leaves.
1. [Page 5, third paragraph] Don't use $C$ here. $C$ already means the subsampled points returned in the coreset.
1. [Page 5, third paragraph] Don't change the meaning of $i$ from the second paragraph to the third. Keep $i$ as the level, and let $j$ denote an element $B_j \in B$.
1. [Page 5, third paragraph] The $(0,r_i)$ notation is really unclear. As written, I think means that $B_i$ has $r_i$ subintervals which exactly interpolate the given dataset $y$, which I don't think is the case.
1. [Page 5, fifth paragraph] Lemma 8 isn't anything that the reader knows. It's burried in the appendix. Say somethign like "this can be solved using <brute force / greedy search / whatever>, with details shown in Lemma 8".
1. [Page 5, fifth paragraph] **As far as I understand, the input signals $C$ are arbitrary subsets of $\{B_1,...,B_{\beta}\}$ of size $\beta-6k+3$. Not consecutive. How does this mesh together with point (i) from the third paragraph on this page?**
1. [Page 5, fifth paragraph] Add "approximation" after "bicriteria"
1. [Page 5, last paragraph] Add "time" after "and thus the running"
1. [Page 5, last paragraph] Again, please abandon this "for all $\varepsilon>0$ notation". There's (in my opinion) a better notation to say what you're trying to say.
1. [Page 6, "optimal soloution" paragraph] The phrase "that minimizes 2" -- I've got no idea what 2 is here. There's no equation 2 in the body of the paper.
1. [Page 6, "efficient $(1,\beta)$" paragraph] "relatively fast" doesn't give me a good intuition. Give me a big-oh notation.
1. [Page 8, list of implimentations] Is one of these analogous to Lemma 8's algorithm? If not, would it be possible to add that to the experiments. If so, could you lable which one that is?
1. [Page 8, section 3.1 results] You don't explain what the error bars are here
1. [Page 8, "dataset" paragraph in section 3.2] Missing parentheses on the citations after "Beijing Air Quality Dataset" and "UCI Machine Learning Repository"
1. [Page 8, section 3.2 results] If you use 25th and 75th quantiles, you should probably use median for the central line instead of an average. Probably won't change the data much, but it's a bit more emotionally consistent.
1. [Page 9, section 3.3 results] Figure 4 shows a brutally hard adversarial edge case for polynomial, but no such example for rationals. It's not fair to point at Runge's phenominon and just say that polynomials are worse at fitting time series than rationals. There's arguments that can be made there, but this is unreasonable.
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).
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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).

Technically, 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.
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.

Weaknesses: 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:

1. 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.

Here, 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?

2. 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.
clarity,_quality,_novelty_and_reproducibility: Clarity: The introduction is generally well written. Things get murkier in the technical content, with relatively little intuition and explanation given around the technical definitions, which would have helped a reader such as me who is not familiar with the prior work on this problem (for example, why does the definition of "ratio" in RFF (def 2) increase the degree of the polynomial in the denominator from k to k+1? What is the intuition behind the non-standard definition of coreset in Def 4, which uses both a weighted set and a bicriteria solution to approximate the loss?) The description of the algorithm was also rather on the technical rather than intuitive side, and unfortunately I couldn't glean what are the main insights driving the algorithm.

Small comments:

- Section 1.2 states that: "this is due to the three main coreset properties: merge and reduce [citations]" - what? What are the three properties?

- In Figure 2 there is some mismatch between the coreset sizes stated in the textual caption and the figure captions.

Reproducibility: I wouldn't deem the results reproducible unless code is released, since the algorithms are stated toward analysis rather than implementation (there are parameters and O-notations etc). The description of the experimental design was also not entirely clear to me (see above).

Novelty: I am not sufficiently familiar with the area to say.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strengths:
- The problem of coreset construction for the rational function is well motivated. 
- 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.

Weaknesses:
- 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.
- 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?
- 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.
- 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.
clarity,_quality,_novelty_and_reproducibility: Clarify: Writing needs to be improved, specifically Definition 4 and the empirical section.

Quality: The technical results are solid.

Originality: The considered problem is new and the proposed results are original.
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. 

Overall, I do not recommend acceptance now. But I may raise my score if the authors can address my questions well.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors present a new algorithm for finding a “coreset for rational functions”, a small subset of a training set for which all rational functions of a certain degree have nearly the same loss as the original training set.  They also reported on experiments comparing the method with software provided with numpy and scipy.  Reviewers had concerns about clarity significant enough to doubt the correctness of the analysis, and these were not fully resolved.

justification_for_why_not_higher_score: Please see the above.

justification_for_why_not_lower_score: N/A
Decision: Reject