Fast Min-$\epsilon$ Segmented Regression using Constant-Time Segment Merging
Authors: Ansgar Lößer
Max Schlecht
Florian Schintke
Joel Witzke
Matthias Weidlich
Björn Scheuermann
Venue: ICML 2025 poster (2025)
Keywords: Regression
Segmented Regression
Time-Series Analysis
Primary area: general_machine_learning

Abstract: Segmented regression is a statistical method that approximates a function $f$ by a piecewise function $\hat{f}$ using noisy data samples.
*Min-$\epsilon$* approaches aim to reduce the regression function's mean squared error (MSE) for a given number of $k$ segments.
An optimal solution for *min-$\epsilon$* segmented regression is found in $\mathcal{O}(n^2)$ time (Bai & Perron, 1998; Yamamoto & Perron, 2013) for $n$ samples. For large datasets, current heuristics improve time complexity to $\mathcal{O}(n\log{n})$ (Acharya et al., 2016) but can result in large errors, especially when exactly $k$ segments are used.
We present a method for *min-$\epsilon$* segmented regression that combines the scalability of top existing heuristic solutions with a statistical efficiency similar to the optimal solution. This is achieved by using a new method to merge an initial set of segments using precomputed matrices from samples, allowing both merging and error calculation in constant time.
Our approach, using the same samples and parameter $k$, produces segments with up to 1,000 times lower MSE compared to Acharya et al. (2016) in about 100 times less runtime on data sets over $10^4$ samples.

Fast Min-c Segmented Regression using Constant- Const Segment Merging
Ansgar LöBer! Max Schlecht Florian Schintke
Joel Witzke 3 Matthias Weidlich? Björn Scheuermann'
Abstract
involves specifying a segment for each interval of partition of the independent variables. See Figure 1, which models 14 sample values using three segments. Min-c segmented regression sets a fixed number of segments k and aims to construct these segments such that the estimation error is minimized.
Segmented regression is a statistical method that approximates function f' by a piecewise function f using noisy data samples. Min-e approaches aim to reduce the regression function's 's mean squared error (MSE) for a given number of seg- ments. An optimal solution for min-c segmented regression is found in Onn²) time (Bai & Perron, 1998; Yamamoto & Perron, 2013) for samples. For large datasets, current heuristics improve time complexity to On log n) (Acharya et al., 2016) but can result in large errors, especially when ex- actly & segments are used. We present a method for min-c segmented regression that combines the scalability of top existing heuristic solutions with statistical efficiency similar to the optimal so- lution. This is achieved by using a new method to merge an initial set of segments using precom- puted matrices from samples, allowing both merg- ing and error calculation in constant time. Our approach, using the same samples and parameter k. produces segments with up to 1,000 lower MSE compared to Acharya et al. (2016) in about x less runtime on datasets over 10a samples.
A common instance of the problem is polynomial regres- sion and the minimization of the mean-squared error (MSE) using ordinary least squares (OLS). For k = 1 and sam- ples, it is simple polynomial regression and takes O(n) time to solve. However, for & 2 2, finding the positions of breakpoints is challenging. Most previous work relies on dynamic programming (Bai & Perron, 1998; Yamamoto Perron, 2013). As shown by Acharya et al. (2016), finding the optimal solution with exactly segments requires Onn²) time.
In practice quadratic time complexity is increasingly prob- lematic because of the growing amount of available data. Using a large number of samples is desirable to reduce noise impact. Therefore, heuristic methods that reduce time com- plexity to On n) have been proposed (Acharya et al., 2016). These methods create many initial segments and then merge them based on the minimal error of consecutive segments. However, the merging is greedy, either assuming knowledge on the noise distribution's variance, or being conducted separately for log(n) buckets over the segments' lengths. In either case, many more than the desired k seg- ments are created, which generally hampers a qualitative analysis of the breakpoint positions. Reducing the num- ber of segments by post-processing in order to solve the actual segmented regression problem for a given k in turn, increases the MSE by orders of magnitude.
1. Introduction
Segmented regression models the relation between depen- dent (response) variable and set of independent (predictor) variables by a piecewise function (Draper & Smith, 1981; Chen & Wang, 2009). It has applications in fields such as ecology (Shao & Campbell, 2002), econometrics (Ya- mamoto & Perron, 2013), clinical guidelines (Ansari et al., 2003), spatial gene analysis (Chitra et al., 2025) and com- puter science (Galakatos et al., 2019; Dai et al., 2020). Seg- mented regression estimates a piecewise function f based on noisy samples of function denoting the true rela- tionship between predictor and response variables. This
In this paper, we present a new heuristic solution to the problem of min-e segmented regression that achieves near- optimal results and scales to large datasets, while using exactly k segments. Our approach does not rely on any knowledge about the noise distribution or its variance. It follows the general idea of merging initial set of seg- ments, but we introduce a novel method: By leveraging precomputed matrices derived from the samples and the ini- tial segment set, we achieve constant-time merging of two consecutive segments and computation of their combined error term.
'TU Darmstadt, Germany Cilumbolld-Universitee zu Berlin, Germany ZZuse Institute Berlin, Germany. Correspondence to: Ansgar Lößer <ansgar kom.tu www.tuddmssttd..d........
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Fast Min-c Segmented Regression using Constant-Time Segment Merging
In the remainder, after defining the problem (Sect. 2) and re- viewing the state of the art (Sect. 3), we make the following contributions:
5
y position a sample (dep. variable)
breakpoints between segments
4
We present greedy approach for min-e segmented regression that is based on constant-ting merging of
3
segments and maintenance of their errors (Sect. 4).
overall avg. MSE ss 11,83
We analyse the complexity of our solution in terms of time and space. It requires On log n) time and ((n) space for datasets with n samples (Sect. 5).
2
1
We demonstrate the efficiency and effectiveness of our solu- tion through a series of experiments (Sect. 6). For datasets exceeding 10a samples, our technique runs about two orders of magnitude faster than best current methods. At the same time, accuracy is greatly improved, reducing the MSE by up to three orders of magnitude in comparison, resulting in an error averaging just 3 % above the optimal solution.
0
2 4
8
10
12
14
X xposition of sample (independent variable)
Figure I. Illustration of segmented regression: For 14 samples (blue data points), three segments S2, Ss. gray lines) are structed, separated by breakpoints.
2. The Problem of Segmented Regression
two corresponding functions does not need to be equal, i.e., the overall piecewise function is not necessarily continuous.
For general regression, we are given n E N observed sam- ples of an underlying function ʃ Rd + R. sample defined by a vector of d independent variables z; E IRd and the dependent variable y; E R.. The dependent variables y; may suffer from noise measure- ment errors. Errors in the independent variables x; are not considered here, as in many use cases, they are not affected by errors or the error is small enough to be negligible. A typical regression model is then defined by:
In min-c segmented regression, a fixed number of segments k is given. The algorithm finds functions fj. S S k that minimize an error metric describing the distance between and ÿ (Chen & Wang. 2009). The solution should be as close as possible to the function f in order to accurately model the underlying correlation between x and y..
i E N, S S
A common general estimator for regressions is ordinary least squares (OLS). This estimator minimizes the mean-squared error (MSE) for a sampled dataset:
y/ = f(x)) + E2
The vector of error values E (n1 )rr is caused by noise in the measurement and is often considered con- sist of independent, identically distributed (i.i.d.) Gaussian noise values. The goal of a regression is to find function f. that is as close as possible to / and outputs a prediction I of the dependent variable.
MSE- = Σ (1 9²) 1=1
Σ (f(x)) - y²
According to the Gauss-Marken theorem, OLS is the esti- mator with the minimum variance of all estimators that are linear combinations of the samples' independent variables, as long as the errors in c are uncorrelated, have a mean of zero and constant variance a (Hallin, 2014). This results in a maximum likelihood estimation (MLE) for Gaussian error distribution. While these properties do not necessarily apply to other distributions, OLS is. nevertheless, often used for other or unknown error distributions, making it one of the most common regression methods.
A typical use case is polynomial regression. Given a sam-
ple at position p, the vector of independent variables for that sample can be defined as x; (p", _p', .p.,,..,p''" p 1)T resulting in a regression by a polynomial of degree d - 1. For polynomials of degree one (d = 2), this is called lin- ear regression. While all methods in this paper work with an arbitrary vector of independent values, we will present polynomial regression for the sake of simplicity.
For a function with i = 1, e.g., a simple polynomial regres- sion, the OLS can be computed analytically in ((n) time. However, for a piecewise function with k > 2, the problem is to find good positions for the breakpoints. The number of segmentation combinations resembles the composition of an integer in combinatorics. In our case, we want to compose the integer n with exactly k parts. The number of compo- sitions is given by the binomial coefficient (E=)). If every
For segmented regression, f is k-piecewise function, which is represented by l individual segments. Given one strict order for all samples (e.g., the x-coordinate for poly- nomial regression). every segment j is defined by its own mathematical function f, where < j < k, and the starting point of the segment. At the borders between two adjacent segments (called breakpoints), the predicted value of the
2

---

Fast Min-c Segmented Regression using Constant-Time Segment Merging
combination is tried, the OLS would need to be computed for every potential solution, so that this solution scales like @ (n²). Even if the number of segments is small, for k >> 1, computing all combinations becomes soon intractable for growing number of samples. Since more samples result in more accurate regression models by minimizing the effect of the noise, faster algorithms are desirable.
4. Novel Greedy Approach
To accurately approximate segment positions and their re- gression models, we developed a greedy algorithm. Min- imizing the global MSE of our regression function f is equivalent to minimizing the residual sum of squares (RSS), which means minimizing the RSS for all 8 segments to- gether:
3. State-of-the-art Segmented Regression
RSS MSE n = Σ (Us 0i)
RSS )
Solving the min-e segmented regression problem often relies heavily on dynamic programming, according to several stud- ies (Bai & Perron, 1998; Yamamoto & Perron, 2013). The algorithm considered folklore and explained in Acharya et al. (2016). It fills a table with optimal regression solu- tions for 1..k segments for the first I..n samples. Finding the best solution for one entry takes O(n d²) time, as- suming solutions for smaller l: and are already computed. Incrementally filling this table takes O(k n² - dd) time, scaling quadratically with the number of samples.
1=1
We start by creating as many segments as possible and calcu- late the individual regression functions using OLS. We also compute the potential additional merge error between neigh- boring segments. Then, we iteratively merge neighboring segments that increase the RSS the least (see Figure 2 for an exemplary illustration). Once two segments are merged, we recalculate the merge errors of the surrounding segments to decide which segment should be merged next with its neighbor. This process involves regenerating the model for the samples of those segments.
This method is more feasible than trying all combinations naively. It remains optimal in minimizing the global MSE for the sampled dataset and can be considered the OLS solu- tion in segmented regression. However, an O(n²) runtime is prohibitive for large datasets. More samples, often noisy but cheap or free to collect, can increase regression accuracy, as confirmed by our evaluation results in Sect. 6.
Using the typical approach to calculate the OLS, the time to compute this model generation scales linearly with the number of samples in the segment. The number of merge operations to reach k segments also scales linearly with the number of initial segments and therefore with the number of samples-resulting in a naive time complexity of (nn)) for n samples.
Since more samples lead to more accurate regression models by minimizing noise effects, faster, not necessarily optimal, algorithms desirable. Heuristic approaches for min-c segmented regression, such as those by Acharya et al. (2016) achieve this with time complexity of O(n logn). n). These methods start with some initial segments and merge them later either based on knowledge about a, the noise's vari- ance, or based on the error for segments grouped by their length. Although the practical statistical efficiency of the latter approach is unclear, regression functions derived from the former approach tend to have high error rates that do not substantially decrease with additional samples. To alleviate this issue, methods creating 2k or 4k piecewise functions are used. This decreases prediction errors with more seg- ments but restricts qualitative analysis, such as determining where the underlying function actually changes.
The heuristic approach of Acharya et al. (2016) employs similar greedy approach. They reduce time complexity by using multiple methods to reduce model recalculations. This
y position of sample (dependent variable)
additional error on segment merge (valurs stored in a priority queae)
4
.01
2
.3
.00
-20
step
0
4
2
1.9
0.002
step
0
4
2
1.9
.559
.01
step
0
Experiments by Acharya et al. (2016) show that adding more segments reduces error, but it remains two to four times larger than the optimal solution's 's error. Compensating this effect by using more data is possible, but also requires more compute time. In this trade-off between compute time and accuracy the state-of-the-ar heuristics often outperform the exact algorithms, but this is only feasible if sufficient samples are available and the specific usecase allows for the creation of more than & segments.
4
2
1.9
.6
step
0
1
2
3
4
5
6
7
8
9
10
11
12 13 14
position of a sample (independent variable)
Figure 2. Exemplary iterative merging of the segments for the solu- tion shown in Figure with our algorithm, where the least- possiiles additional error is added. Bold red highlights changes in cach step.
3

---

Fast Min-c Segmented Regression using Monstant-Time Segment Merging
includes starting with fewer initially placed segments and delaying recalculations until an error threshold is reached. These methods improve performance but reduce the achiev- able accuracy and require estimating sampling noise a. In contrast, we store segments in a way that allows constant time merging.
adjusted by a quarter of adjacent segment's size. Within this range, all possible positions are evaluated, and the one with the smallest RSS determines the final placement.
Optimizing one breakpoint influences the local models of surrounding segments. Larger segments are considered to be more stable because removing the first or last quarter of their samples typically has a smaller effect on the model. Therefore, we start with the breakpoints adjacent to the largest segments and continue in descending order.
4.1. Greedy Segmented Regression
The algorithm has three main phases: (1) place as many segments as possible and precalculate some attributes per segment, (2) reduce the number of segments to the target k by merging those that cause the smallest increase in overall RSS. (3) execute a post-optinization step to compensate for suboptimal initial segment placement.
4.2. Merging Segments in Constant Time
To show how we merge segments in constant time, we first look the calculation of a single segment's OLS. Caleulat- ing the OLS of n samples takes linear time. Given matrix X for independent variables of the samples and the corre- sponding vector of dependent variables ÿ. the vector with regression parameters for a polynomial of degree d - can be calculated as follows.
Initial placement. Initially, as many segments as possible are placed. Without overlapping segments, a maximum of 1 segments can be placed ge.g., linear regression means = 2), as at least d samples per segment are needed to compute a uniquely defined OLS regression (see Sect. 4.2).
x
For each placed segment, an optimal model is generated using OLS. Except for the last segment, the error for each segment is zero, since d points can be perfectly matched by exactly one specific polynomial of degree d - 1. It is now possible to calculate a merge cost (S,) for each segment Sy. This cost metric indicates how much the overall RSS will increase if the segment merged with its successor SJ+1, defined as follows:
22
22
22
x=
233
23
23
33
.B= = xx-xx-x) "xT
:
Since X is Vandermonde matrix, the Gram matrix X X is positive semidefinite and is invertible if X contains at least d distinct input samples (n 2 d). Given the vector 3, this regression model can be used to predict value Ot for the i-th sample. Here, X₃ is the matrix X, but only containing the independent variables vector of the i-th sample. It is also possible to calculate the minimized mean squared error.
(SS)) (S U S - (RSS(S)) + (SS(()+)))
This metric is never negative because combining segments cannot improve model performance or decrease total error. To quickly find which segment to merge next, we store the metric and its segment reference in a priority queue.
ú, = f(x)) = X33
n2 RSS
Σ (f(x.) - 81) |X - 17/²
Segment reduction. We keep taking the segment with the lowest merge cost from the queue and merge it with the next segment until we have the desired number of k segments. For each merge, this operation removes the original seg- ments and adds new merged one. It also shifts the indices of all following segments down by one.
RSS
X 57
MSE-
We introduce two additional matrices: A of dimension d d, and B of dimension d x 1. These matrices can be used to calculate the OLS in exactly the same way as shown above.
Merging two segments induces local changes in M. To draw the correct segment in the next iteration, we update the cost of the new segment and its predecessor in the priority queue after each merge operation (bold red numbers in Figure 2).
A = x B 3 xT 8 A
We can store a segment with the pre-computed matrices A and B with constant storage, independent of the number of points n. Assuming we have two segments with two distinct sets of samples S, and Sg, we can calculate the correspond- ing matrices. Furthermore, we can compute the matrices of a segment with the joint set by adding the matrices.
Placement optimization. Step 5 in Figure 2 would lead to segment S2 being merged into S3. Regardless of the specific last merge step, it is impossible to separate the two points of S2, as segments are never divided. To mitigate any negative impacts, we fine-tune breakpoint positions after reducing to le segments. Each breakpoint position can be
Anuo = Au + Au, BLuv B,, + B
4

---

Fast Min-c Segmented Regression using Constant-Ting Segment Merging
Merging two segments with these pre-computed matrices is an operation of (d²)) time and will not scale with the number of samples. By subtracting instead of adding the matrices, it is also possible to remove subset of samples from a segment. A and B can also be calculated for single samples. While it is not possible to calculate the inverse of A and derive the model parameters 3 if d > 1 for individ- ual samples, it is valid strategy to be able to add single samples to segment remove individual samples. This is beneficial in the placement optimization step.
Combining segments is still possible in (dP)) time by adding the matrices C. and C. for two segments and v. To calculate the error, we need to calculate D and, there- fore, need the model parameters. This involves calculating the inverse of A or solving the linear system of 8 = A- B, which is typically done in (dd) time. All of these oper- ations are independent of the number of points, so for a typical regression algorithm with a constant number of di- mensions we are able merge two segments and calculate the resulting RSS in constant time.
The cost of merging two segments can be further reduced. For high values of d, there are more efficient ways of cal- culating B. If just a single point is added to a segment, it is possible to use the Sherman-Morrison formula to do a rank-1 update of the already known matrix inverse in (dP) time. However, since our algorithm often merges segments much larger than a single point and the number of dimen- sions is often limited e.g. d = 2 for segmented linear regression-we consider this to be minor optimization and not relevant for the evaluation of our algorithm.
4.3. Calculating the Error of a Segment
In our algorithm, after merging, we need compute the er- ror of the resulting segment to update the merge cost metric. To avoid iterating over every sample, we demonstrate how to derive the RSS in constant time.
In this section, we only consider samples inside the current segment, where n is the number of samples inside that segment. We introduce two new square matrices, C' and D, both of dimension d + 1. C' can be defined for subset of samples, similar to X. A and B. C; is the matrix C for a single sample. The matrix C; only depends on the values in A, and B; and the value y/ for the i-th sample. D can be calculated using the regression parameters B. By transposing and simplifying the equation, where '0' is the Hadamard product (element-wise product of two matrices of same size), we can show' that:
5. Complexity Analysis
In this section, we study the time and memory complexity of our algorithm with a focus on the influence of the number of samples n. We also consider how the number of dimensions d affects these metrics. However, since n > d must hold true, and d is often a chosen constant for a specific regression model, will not be the focus of our research.
A
BTT
3
T
B
C =
D =
Bi
-1
The data structures to store segments have great impact on the complexity of our algorithm. We use a double-linked list to quickly find the predecessor and successor of a segment and delete merged segments. Additionally, we implement a priority queue using a binary heap with reference tracking, which quickly identifies the next segment for merging and updates the merge costs of neighboring segments.
RSS: = (X,3- - y1)²
expand X
d+1
= Σ
(D 2 C.)em
t,m=1
d+1 Calem C= Σ C
RSS-
RSS:- = Σ Σ
(D
5.1. Memory Complexity
==1
4-m=1
1=1
As described in Sect. 4, our algorithm first creates L individual segments. Afterwards, the number of segments is continuously reduced until only i segments are left.
d+1
Σ 1,
(D cm
For every segment, we need to store the summed-up matrix C. As shown in Sect. 4.3, this matrix is squared symmetric matrix of dimension d d+1 1. It can be stored with (d 1) values. We need to store the size or position of a segment and the current merge cost, both with fixed sizes. Also, we need to reference all segments in a heap and linked list. The size of linked list grows linearly with the number of elements. While the overhead of typical heap is constant, the reference tracking adds constant overhead per entry. The overall memory overhead of these data structures scales linearly with the number of elements. Hence, it is equivalent
The error of a segment is computed by the grand sum of the element-wise multiplication of the products of regression parameters D and the products of all dependent and inde- pendent variables summed for all samples C. All described properties of matrices A and B also apply for C: C is a square symmetric matrix that can be combined for multiple sample sets by addition. As matrices A and B are submatri- ces of C, only matrix C has to be stored for every segment, along with the size or position of the segment.
detailed derivation shown the appendix.
5

---

Fast Min-c Segmented Regression using Constant-Tims Segment Merging
constant overhead per segment.
6. Evaluation
Since we know the maximum number of segments and how the amount of data scales for single segment, we can conclude that the memory complexity is given by:
We use real and synthetic data to compare the accuracy and the runtime of our algorithm with the established approaches. The best exact solution, dynamic program (DP), is compared to approach and the state-of-the -f-tthe-rt heuristic (Acharya et al., 2016). Table 1 shows the algorithms' properties.
m : (1a
(d [ 0 ( ((n.a) dd)
o
2
The amount of memory needed scales linearly with the number of data points n. If all samples need to fit into memory anyway, this can be considered optimal.
Table I. Qualitative Comparison of Approaches
Our Appr.
Acharya
Feature
DP
2k
4k
Correct k
4
X
x
5.2. Time Complexity
Qualitative BP Exact
4
X
X
X
V
X
X
We amalyze the time complexity for the three phases of our algorithm individually.
Memory compl.
71
71
T6
Time compl.
n²
72 nlo 12
17 log 7
Rel. MSE ($6.1)
1.00
1.03
495. 13
3.43
4.95
Initial placement. First, L' segments are placed and inserted into the linked list. For every segment, we calculate the merge error cost with its successor, resulting in 2 L model generations, with a time complexity of (dd)) All merge costs need to be inserted into the binary heap. This would normally result in time complexity of O(s ss log s) for segments. However, the initial insertion of many elements into a binary heap-often called heapify- can be optimized to run in amortized complexity of (ss). The resulting time complexity for the initial phase is defined by:
Acharya's method places k; 2k or 4k segments. While the first version places the intended k segments, it fails to accurately find the breakpoint positionns (BP), where changes in ff occur, with real data (Sect. 6.2), leading to high error in the regression results. Placing more segments drastically reduces the error for synthtetic data but still less effective than our approach (Sect. 6.1).
The dataset generation and measurement code use Python. The optimal dynamic program and heuristic were taken from Acharya et al. (2016). For exact control of data struc- tures, we implemented our approach in C++. While pro- gramming language and implementation details might influ- ence runtime, they should not change the results by orders of magnitude in this case. According to Acharya et al. (2016), their operations run similarly fast in C and Julia.
o 0
+
On d²)
Segment reduction. To reduce the number of segments to k. we perform L k merge-iterations. Since & is considered to be a small constant, we perform ((L) iter- ations. In every iteration, we take an element from the heap (Oog s)). remove that element from the linked list (O(1), generate the new models (dP) and update the values in the heap (Ollo s)). The overall time complexity is:
All experiments were done on an AMD Ryzen Threadripper PRO 5955WX system with Ubuntu 24.04 LTS. Details, mea- surement data, source code, experiment setup, our analysis pipeline, and an additional evaluation regarding parameter d are included in the supplemental material of this paper?.
A o (1a) (10g
[log]
n T
+ d3) = O(n -log n + d²))
Placement optimization. To optimize the determined seg- ments, we vary the positions of the breakpoints. Moving a breakpoint by one sample is similar to removing and adding a segment of size one. By storing and updating A-1 with the Sherman-Morrison formula, this can be done in OdP). This operation is done for z samples, resulting in time complexity of Onn d²).
6.1. Synthetic Data
Akin to Acharya et al. (2016), we generate piecewise con- tinuous function with k 6 segments for evaluation points. Five random positions are chosen as segment start points between 0 and n. The first segment starts at O, and the last ends at n. At each joint, we randomly select a y value between 0 and 1. Segments interpolate linearly from their start to end points.
Thus, the overall time complexity of our algorithm is given by the maximum of the three steps above:
We take evenly spaced points from a function, add Gaussian noise using two fixed standard deviation (o) values, and measure the time needed for k-segmented regression. We
(n log n d))
Considering the number of samples n, the runtime of our algorithm scales with On log n).
Thhe supplemental material is available at https:// g wccmm//oosggr///srr//eeeee
25.
6

---

Fast Min-c Segmented Regression using Constant-Timg Segment Merging
Runtime (s)
MSE
Relative Speedup
Relative MSE
10a
10a
10-3
104
10a
0 0.01
10a
10-5
10
10a
10-3
10-7
10a
109
10a
10a
10
10?
10
10a
10
10a
10
10a
10-2
10c
10-3
0 0.1
10a
10
10-4
10
10a
10-5
10-3
10a
10-6
109
10
10a
107
10
10a
104
10a
10a
number of samples (n)
number of samples (n)
number of samples (n)
number of samples (n)
Exact (DP)
Our Approach
Acharya
Acharya
Acharya 4k
Figure 3. Evaluation results (log-log scale) from synthetic data with Gaussian noise. For each point, 100 functions / with k segments were tested across all regression algorithms. Data points show average measurements. Due to excessive runtime, we limited maximum sample size the other approaches. Error bars mark the interquartile range (50 % of all values). MSE measures error between predicted and the actual value (x)) Relative figures compare individual results to those from the exact dynamic program on the same function.
calculate the MSE using the true values from the original function, not the noisy data. This eliminates the impact of high noise and shows how error decreases as more samples are used in the regression.
10-2
WORSE
10-3
nm512
Figure 3 shows performance results for values of 0.01 and 0.1 (equivalent to 1 % and 10 % of the value range). The correct was also used as an input parameter for the competing heuristic, which our algorithm did not require.
202144
2048
10
2044
16994
MSE
The results are similar to those of Acharya al. (2016). They reported an MSE of 2 to 4 times higher than the dy- namic program. We observed range
10
n 10504
times, the values and trends matching theirs, confirming their findings. Additionally, we validated that the 1 approach's 's accuracy does not improve with more samples. Our approach consis- tently outperforms existing heuristics both runtime and MSE, even those using more segments. Our approach's runtime is consistent for given number of inputs with little variation. The linear appearance on log-log graph suggests initial slowdown might be from measurement inaccuracy and overhead, not the actual performance.
10-6
n=-26214
BETTER
10-7
1-1677226
10-8
10
10
3
10
10'
10a
Runtime (s)
Exact (DP)
Our Approach
Acharya
Acharya 2k
Acharya 4k
Our approach sometimes outperforms the exact dynamic program. The exact algorithm minimizes enror based on sampled data, so possible to find a solution that is similar but slightly less accurate the sampled data, yet closer the true function f. This often happens in high- noise scenarios.
Figure 4. By varying sample size nı we can compare each algorithm's 's accuracy within fixed computation time (based on results Figure with a = 0.1). Our algorithm outperforms all evaluated solutions, especially if many samples are available.

---

Fast Min-c Segmented Regression using Constant-Timg Segment Merging
Samples Exact (DP)
Our Approach
Acharya 2k
800
Acharya
Acharya 4k
600
CPU (%)
400
200
40000
80000
120000
160000
148000
150000
152000
154000
156000
Time (s)
Figure 5. Segmented regression results on real data. The data show samples from a timeseries, the CPU usage of an execution of the common scientific program 'bwa' of the scientific workflow 'sarek'. The first segment especially large, followed by multiple short periods of different behavior. The later part, starting at roughly 148,000s is magnified on the right. The optimal solution (DP) is equal to our approach (red).
We analyzed the tradeoff between compute time and MSE for 0.1 by varying the number of input samples n, ensuring competing algorithms had similar average runtime. The results are shown in Figure 4. Our approach has nearly optimal error with much faster computation, outperforms all competitors, even those using more segments.
Table 2. Evaluation results for the dataset shown in Figure 5.
Our Appr.
Acharya
Attribute
DP
h:
2h
1k
Runtime
2938.33
0.01
0.30
0.33
0.34
MSE (x10*)
1.82
1.82
1.87
2.05
1.99
Rel. Runtime
x2.9 10
x1
X30
x33
x34
Rel. Error (+%)
0.00
0.00
2.61
12.20
9.18
Our method is slightly less accurate than the exact dynamic program if the computing power is not taken into account. The exact method usually performs better in this situation. On average, with noise level of a = 0.01, our approach only increased the MSE by 3 % (see Table 1).
Table shows that using Acharya does not match our method or DP. While DP gives an accurate result, it needs more than forty minutes. Our approach finds the exact same solution in a few milliseconds.
6.2. Practical Data
This specific scenario shows that more segments not nec- essarily yield more accurate results. Acharya performed worse when placing 2k or 4k segments. Only with exactly segments Acharya created a breakpoint that was very close to a breakpoint DP and our approach.
To evaluate our algorithm, we used time series data showing CPU usage during the 43-hour execution of the bwa pro- gram (Li, 2013) from sarek workflow (Garcia et al., 2020).
Every two seconds a sample was measured, resulting in 70,607 samples. The dataset shows roughly four execution stages with different behavior. Unlike synthetic data, it is diverse: noise is not normally distributed, variance is high and varies between segments. Most samples belong to the first stage, while all other stages share fewer samples.
7. Related Work
The Python module "piecewise- regression and the R pack- age 'segmented' use an algorithm by Muggeo for fitting line segments and breakpoints in continuous piecewise regres- sion functions (Pilgrim, 2021; Muggeo, 2008; 2003). The 'pwlf' Python module optimizes breakpoint locations with either differential evolution algorithm faster gradient based method (Jekel & Venter, 2019). However, due to the focus on continuity, their performance is worse than our proposed algorithm, which is more reliable and can handle non-continuous data. Our algorithm effectively identifies segment positions for piecewise continuous functions and
Figure 5 shows the dataset and the regression functions i using different algorithms. Our approach matches the optimal solution from DP exactly, clearly identifying the execution phases. The competing heuristic Acharya fails to detect correct breakpoints, places unnecessary segments inside the first execution phase. Since the exact ground truth is unknown, we cannot calculate MSE against it. Instead, we calculated MSE between sampled data and predictions.
8

---

Fast Min-c Segmented Regression using Constant-Tine Segment Merging
can be adapted to create continuous piecewise functions from the segmentation results. The effectiveness of this adaptation compared to existing approaches is beyond the scope of this paper.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
The algorithm from Acharya et al. (2016), compared above, was later extended by Diakonikolas et al. (2020) to segment along multidimensional breakpoints (e.g. place rectangles). They claim to be the first efficient multidimensional seg- mented regression algorithm that works in any fixed dimen- sion. Our algorithm might also be extended for arbitrary dimensions similarly. Evaluating its performance in multi- dimensional setting is open for future research.
References
Acharya, J., Diakonikolas, I., Li, J., and Schmidt, L. Fast algorithms for segmented regression. In Balcan, M. F. and Weinberger, K. Q. (eds.), Proceedings of The 33rd International Conference on Machine Learning, vol- ume 48 of Proceedings of Machine Learning Research, pp. 2878-2886, New York, New York, USA, 20-22 Jun 2016. PMLR. URL https: ppooeeedinggs .mlr. press v 8/ haaachaaraall. h.mmm.
The related min-# problem involves finding a function f close enough to another within an error limit while us- ing the fewest segments (Chen& & Wang, 2009). It easier than related problems, with solutions that run in (nn) time (Tomek, 1974; Imai & Iri, 1987; Neubauer, 2009). Solv- ing min-# can often be extended to solving min-e, but this increases complexity to about (n n).
Ansari, F., Gray, K., Nathwani, D., Phillips, G., Ogston, S., Ramsay, C., and Davey, P. Outcomes of intervention to improve hospital antibiotic prescribing: interrupted time series with segmented regression analysis. Journal of Antimicrobial Chemotherapy, 52(5):842-848, 2003.
Recent works by Warwicker & Rehennack (2023; 2024) focus on solving the min-# problem with strict continuity in regression functions. Some of their algorithms only handle continuous functions, not discrete data points, which limits comparisons to our work.
Bai, J. and Perron, P. Estimating and testing linear models with multiple structural changes. Econometrica, pp. 47- 78, 1998.
8. Conclusion
Chen, D. and Wang. H. Approximating points by piece- wise linear function: I. Algorithmica, 66:224-233, 12 2009. doi: 10.1007/978-3-644 10631-6 24.
We presented a new heuristic to solve the min-c segmented regression problem. The greedy algorithm merges neigh- boring segments in constant time. Our algorithm finds solution using exactly k segments without needing any spe- cific information about the input. We showed that it can analyse n samples in a runtime of On log n) and has a memory complexity of (n).
Chitra, U. Arnold, B. J., Sarkar, H., Sanno, K., Ma, C., Lopez-Darwin, S., and Raphael, B. J. Mapping the topog- raphy of spatial gene expression with interpretable deep learning. Nature Methods, pp. 1-12, 2025.
We evaluated the algorithm's 's speed and accuracy against state-of-the-art heuristic and optimal solutions. The result- ing regressions close to the optimum, outperforming all other presented heuristics, while our algorithm is orders of magnitudes faster. The algorithm provided the best balance of speed and accuracy compared to others. Our algorithm is usually the best option. However, if there are only a few samples and very large computing resources, the competing dynamic program on average, slightly more accurate.
Dai, Y., Xu, Y., Ganesan, A., Alagappan, R., Kroth, B., A., and Arpaci- Dussea, { (WiscKey) to bourbon: A learned index for {Log- Structured] merge trees. In 14th USENIX Symposium Operating Systems Design and Implementation (OSDI 20), pp. 155-
From
Diakonikolas, I., Li. J., and Voloshinov, A. Efficient algo- rithms for multidimensional segmented regressioon 2020. URL /ttps:///avvvvva/ /ttp///awwvv.or////////0003
Acknowledgements
Draper, N. R. and Smith, H. Applied regression analysis (2. ed.). J. Wiley series in probability and mathematical statistics. Wiley, 1981. ISBN 978-0-471-02995-33
This work received funding from the German Research Foundation (DFG), CRC 1404: FONDA: Foundations of Workflows for Large-Scale Scientific Data Analysis.
Galakatos, A., Markovitch, M., Binnig, C., Fonseca, R.,
and Kraska, T. Fiting-tree: A data-aware index structure. Proceedings of the 2019 international conference on management of data, pp. 1189-1206. 2019.

---

Fast Min-c Segmented Regression using Constant-Timg Segment Merging
Warwicker, J. A. and Rebennack, S. Efficient continuous piecewise linear regression for linearising univariate non- linear functions. IISE Transactions, 0(0): 2024. doi: 10. 10.10000224725554222223333 00000002277888882222722288888880 229999922299998898 1 doi coi.org/10. 080
Garcia, M., Juhos, S., Larsson, M., Olason, P. I., Martin, M., Eisfeldt, J., DiLoornzo, S., Sandgren, J., De Ståhl, T. D., Ewels, P., al. Sarek: A portable workflow for whole- genome sequencing analysis of germline and somatic variants. F/000Research, 9, 2020.
URL https: ///////////22222 240000447725544 2 2299809.
Hallin, M. Gauss-Markon theorem in statisties. Wiley Stat- sRef: Statistics Reference Online, 2014.
Yamamoto, Y. and Perron, P. Estimating and testing multiple structural changes in linear models using band spectral regressions. The Econometrics Journal, 16(3):400-44 4299 2013.
Imai, and Iri, M. An optimal algorithm for approximat- ing piecewise linear function. Journal of Information Processing, 139:119-- 1987.
Jekel, C. and Venter, G. pwlf: A python library for fitting continuous piecewise linear functions. 2019. doi: 10. 1.114//RG..22.28555 2...4//.....225550.....
Li, H. Aligning sequence reads, clone sequences and assembly contigs with bwa-mem. arXiv preprint arXiv:1303.3999, 2013.
Muggeo, V. Segmented: An R package to fit regression models with broken-line relationships. R News, 8:20-25, 01 2008.
Muggeo, V. M. R. Estimating regression models with unknown break-points. Statistics in Medicine, 22(19): 3055-3071, 2003. doi: https://doi.or//10.0000//
1545. URL https:/ http://nnnnnnniarreeeeee wiley. com/do http:///./a///....1/a htt.:.............mm....mm.m.... 1545.
Neubauer, S. Space efficient approximation of piecewise lin- ear functions. Studienarbeit, KIT, Institute of Theoretical Informatics, Algorithm Engineering, 2009. URL ht https: sh 253 php.
//ae. it .iit.kt... edu/ wwt.kk....eeeeee.e..e
Pilgrim, C. piecewise-regression (aka segmented regression) in python. Journal of Open Source Software, 6(68):3859, 2021. doi: 10.21 10211ossssss003859 URL https://doi. org/10- 211.1 03s.0. 03859.
Shao, Q. and Campbell, N. Applications: Modelling trends in groundwater levels by segmented regression with con- straints. Australian & New Zealand Journal of Statistics,
1292):129-141, 2002.
Tomek, I. Two algorithms for piecewise-linear continuous aorooimmattin of functions of one variable. IEEE Trans. Computers, 23(4):445 448, 1974. doi: 10.1109/T-C. 1974.223961. URL https: httpp:::////ioooo/o http://ooo.or//1.11/.... 1-7. 223961.
Warwicker, J. A. and Rebennack, S. Generating opti- mal robust continuous piecewise linear regression with outliers through combinatorial Benders decomposition. IIEE Transactions, 55(8):755-767, 2023. doi: 1080/ 115255854..22222223333 URL attps: /ww...oooo. /rg/
24725864..2022.217722..
10. 00.11000/24225854...0 200.:/2224472555.222220000000000
10

---

Fast Min-c Segmented Regression using Constant-Tims Segment Merging
Appendix
This document represents the technical appendix of the the paper Fast Min-e Segmented Regression using Constant- Time Segment Merging. The main contribution the clarifi- cation and better explanation of the mathematical formulas in Section 4 of the paper and an experimental evaluation of the influence of the parameter d on the computation time and accuracy of our algorithm.
C122 =x / x + +22 22
+
23
3
+
+ 2 In
C1 = Σ (x) xx))
1=1
Ie., single value in the matrix C is the sum of a product of two values of a single sample, for every sample. There is never a product of two values that depend on two differ- ent samples. Adding more samples only results in longer columns in X Calculating C. on a subset of the sam- ples and adding it later to C2 containing the rest of the samples is exactly the same as calculating C' for all samples in the first place. The only thing that might change is the order of the additions. This is irrelevant since addition is a commutative operation.
A. Constant- Tonstant-Time Segment Merging
This section describes the mathematical formulas from Sec- tion 4. We will use the same connotations and names in the paper without further explanation.
A.1. Segment Merging
The paper presented multiple matrices A, B, and C' based on X (the matrix containing the independent variables of a sample for polynomial regression) and iJ (the vector con- taining the dependent variables of the samples). It is stated that these matrices can be calculated for individual samples or sets of samples and can later be added together to get the matrices of the combined sample set. Since A and B are submatrices of C, we will focus on showing this property for C.
A.2. Error Calculation
We now show how to use the matrix C to calculate the RSS. The paper already shows how the OLS paramter vector / can be calculated using the submatrices A and B. The RSS for the sample can be calculated the following way:
RSS. = (f(xz) - v.)² (X,8 v1)²
expand X,8
The paper defines the matrix C' the following way:
= =x + 2, +.... - Ba y1)²
x
x
This can be further expanded, resulting in the following term:
xf
x
2
X
33
F3
33
20
x B1
2
+
x 1::31
y
A
XT X,
B
XT
T
+
x B2
+
x
y/
A
BT
C
B
Σ y
+
d d-1
Ba
x 31
+
3a
yi
x 31
Yi
y/
Another way to represent C is by introducing a new matrix X which is similar to X but contains all information of the samples (including the dependent variable).
Local reordering inside the addends lets us write the term the following way:
y1
Di
22
x2
d
g22
31
+
+
yoo! you!
(1(-1)
x+ = X
23
23
x3
d-1
y3
+
828
+
+
32(-1)
:
+
BaB1 (-1)
+
+
yoo d-1 y:Ui
Ba(-1)
+
xQ yi
+
(-1)
The matrix can now easily be calculated from X since ===x* x+T x+, Any single element in the resulting matrix C' is the sum of the element-wise products of two columns in X The following equation shows this for the value
The left parts of the products (bluc) correspond exactly to the elements of the matrix C₁ (the matrix C from exactly one sample i), the right parts can be calculated by the matrix D.
C2

---

Fast Min-c Segmented Regression using Constant- Constant-Time Segment Merging
31
81(-1) 82(-1)
3
8 T
-1
Ba
Ba(-1) (-1)(-1))
1)31
In conclusion, the RSS of sample i, given the OLS model defined by 3 in the matrix D, can be calculated by the grand sum of the Hadamard product @ (the element-wise product of two matrices of the same size) of and C..
d+1
RSS,- = Σ (DOC))e tm==1
To calculate the overall RSS of a sample set with n samples, we need to add the RSS of all individual samples together.
RSS-
RSS.
i=1
n
D C.)em
factor
2m==1
Ci
c= Σ C
tm=1
tm
1=1
D 3 C)
1,m=1
Given any sample set defined by C and OLS model defined by the vector 3 in D, can calculate the RSS of the samples in C' with the great sum of the matrix D O C. Dividing this value by the number of samples n results in the MSE.
12

---

Fast Min-c Segmented Regression using Constant-Timg Segment Merging
B. Multidimensional Evaluation
time complexity. This can be solved using the following equation:
This section evaluates the runtime and accuracy of our ap- proach relative to the parameter d (the number of input dimensions). The behavior in relation to parameter is not fundamental novelty of our approach and therefore not the main contribution of our paper. All other mentioned approaches share the runtime complexity of (dP) with our approach.
(A + un ---=""-==--- A- (A- A 1 2² A
Since matrix multiplication (including matrix-vecton multi- plication) is an associative operation, the above formula is mathematically identical to the first formula, but it consists of two matrix-vector multiplications and one final vector- vector multiplication. All these operations are trivially com- putable in quadratic time complexity.
At the same time, there are multiple key insights that are noteworthy to share. As representative real data for multidi- mensional datasets is hard to find and obtain, this analysis focuses synthetic data. The general setup resembles the experiments done in Section 6.1 of the main paper.
A Although the optimized rank-1 update is widely recognized, this particular implementation detail is easy to miss. For ex- ample, Acharya et al.'s DP algorithm overlooks this aspect- likely an unintentional oversight that could affect both ac- curacy and performance of the baseline algorithm, though its impact is minimal for d 2 (the primary case evalu- ated in their work). Despite being theoretically quadratic in time complexity, their implementation does not achieve such efficiency.
B.1. Discussion of the Sherman-Morrison Formula
For the evaluation with d = 2, all relevant matrices are at most symmetric matrices of dimension 3 x 3, the matrix A, which must be inverted-or decomposed and solved for a specific system of equations is a symmetric matrix of dimension 2 x 2. The specific approach to do these operations has a negligible impact on the overall runtime of the algorithm. This drastically changes when scaling up d.
ACCURACY
Using the Mherman-Morriso formula may raise concerns regarding numerical stability. Continuously updating A-1 instead of recalculating it from all available data can lead to gradual buildup of rounding errors over time. Although this issue appears less severe for well-conditioned matrices, even these cases have shown signs of reduced stability.
RUNTIME COMPLEXITY
To achieve runtime complexity of O(F), the exact dy- namic program (DP) and the last optimization step of our approach rely on precomputing the inverse of matrix A and updating it when adding or subtracting one sample. The naïve way of inverting a square matrix would result in a run- time of (d While there are approaches reduce this runtime complexity for large matrices, no known method reduces it to (d.). The update of an inverted matrix with one additional sample is also called a rank-1 update (RIU) and can be done more efficiently than a matrix inversion, us- ing the special attention in the detailed implementation.
In our evaluation, we used 64-bit fixed-size floating- -ponnt numbers- commonly known as doubles-fio the compu- tations. This approach aligns with standard practices in similar calculations, though it can introduce the rounding errors mentioned carlier. Although a detailed analysis of the Sherman- Moriison formula's 's outcomes is beyond the scope of this paper, we provide several anecdotal insights based on our specific use case.
formula. However, this requires
Low Impact on Well-Conditioned Data: In the final stage of our algorithm, we ensure that nearly all samples come from single segment, yielding regression function f that closely approximates the true underlying function- with only a few outliers misassigned during the initial seg- ment placement. Under these conditions, we assume that our matrices are well-conditioned. Employing the Sherman- Morrison rank-1 update never lead to any noticeable drop in accuracy-even when dealing with very high dimensions d or large numbers of samples This is clearly demonstrated by comparing the performance of our algorithm both with and without the rank-1 update.
Given the matrix A with precomputed matrix A-1, and the vectors and v, the updated inverse value of A + uo can be computed as follows?:
A uv A-
(A + ue -' A
1 oF A-1u
Directly using the above formula typically results in triv- ial evaluation from left to right in the individual subterms. In case of the term A A-'ue uu -1 in the dividend, this is detrimental, since it results in multiplication of two matri- ces of size d x d, which cannot be computed in quadratic
'The vectors u and u can be different in the generic version of the formula, but in this scenario they are always the same vector, describing all independent values of single sample. The matrix A of an individual sample i can he calculated by A, = wv" = x.a!?"
Well-Conditioned Data Reduces the Impact: The DP often calculates the regression function across multiple seg- ments (e.g., over the whole sample set). Using the optimized
13

---

Fast Min-c Segmented Regression using Constant-Timg Segment Merging
Runtime (s)
MSE
Relative Speedup
Relative MSE
10a
10a
10-2
10
10a
0.01
10"
10-1
10-5
10'
10-3
4096
4
16
256
2
8
32
256
16
32
8
10a
n1
10a
10a
0.1
10'
10-1
10
10
10'
100
4 16
256
2
8
32
256
16
32
64
8
dimension (d)
dimension (d)
dimension (d)
dimension (d)
Exact (DP)
Our Approach
Acharya
Acharya 4k
Exact (DP,R1U)
Our Approach (RIU)
Acharya
Figure 6. Varying number of arbitrary input dimensions with constant number of samples. The dotted lines mark versions of the algorithms using the Sherman-Morriso formula quick rank-1 update (RIU). An outlier 0.01, 4 caused high mean value, which is accentuated by the log-scale.
rank-l update, resulted in significantly higher error for DP but not for our algorithm. For n = 8192, the error was sometimes large enough let the matrix seem like a singu- lar matrix, which cannot be inverted all. We assume this is due to the added samples significantly changing the current inverse. We observed no such issues with algorithm- even at much larger values for n and d d--indicaing minimal accuracy loss on well-conditioned matrices.
B.2. Fixed Number of Samples
Our experiment setup resembles the synthetic evaluation in the main paper. We measure both accuracy and runtime across 100 randomly generated piecewise functions. Ac- curacy is quantified using the mean squared error (MSE) between the estimated regression function f and the true underlying function f at the positions of the input samples. The samples are uniformly distributed and the breakpoints (BP) are selected at random.
Worse Accuracy with Trivial Implementation: As men- tioned above, Acharya et al.'s original implementation of the rank-1 update suffers more than necessary terms of speed for large values of At the same time, this implementation also seems yield much worse accuracy. Although these results not shown here, they can be reproduced using the code provided in the supplemental material.
Unlike the original evaluation, we do not fit polynomials; instead, we use input data from multiple truly independent dimensions. For fair comparison, it still necessary that n d because only one reasonable solution exists at d k. Since computational time is limiting factor in our evaluation when using DP- we reduced the number of breakpoints to k 4, set n to fixed value, and varied parameter
To ensure a fair comparison between the algorithms, we employ two modified variants of the dynamic program based on Acharya et al.'s implementation. The first variant, DP, avoids using the rank-1 update by solving linear equa- tions explicitly-thie guarantees high accuracy at the ex- pense of slower execution times. In contrast, the fast vari- ant, DP (RIU), incorporates fast rank- update described above to achieve quadratic time complexity while accepting slight reduction in accuracy. We also present results for our algorithm with and without the rank-1 update, demon- strating that its performance remains robust under these different configurations.
Results for n = 4096 are presented Figure 6. The figure demonstrates that, on occasion, our algorithm produces a suboptimal solution-an effect that is accentuated when the log-log scale. In contrast, plotting
mean value is plotted the median aligns perfectly with the baseline curve for DP. Additionally, the rank-1 update significantly accelerates both DP and our algorithm for large values d; however, unlike our approach, DP suffers from reduced accuracy when using the rank-1 update. The results also confirm that our algorithm consistently achieves higher accuracy than
14

---

Fast Min-c Segmented Regression using Constant-Tims Segment Merging
Runtime (s)
MSE
Relative Speedup
Relative MSE
10a
10a
d 0.01
10
10a
10
10"
10-1
10a
10-3
10
n1 = 8192
4
16
256
2
8
32
256
16
32
8
10a
10a
0.1
10a
10-3
10a
10"
10-1
10a
10-3
4
16
256
2
8 32
256
16
32
64
2
8
dimension (d)
dimension (d)
dimension (d)
dimension (d)
Exact (DP)
Our Approach
Acharya Acharya
Acharya 4k
Exact (DP,R1U)
Our Approach (R1U)
Figure 7. Similar experiment to the one shown in Figure 6, but using 8192 samples. The DP using the rank- update formula failed at due to rounding errors.
the solution proposed by Acharya al. al.-especially when exactly segments are placed and remains faster overall, although the gap in both performance metrics narrows as d increases.
Observations indicate that the performance gap compared Acharya al. remains significantly larger and narrows later. This trend is particularly evident in the relative performance graphs. The impact of collapsing solution space becomes especially prominent when comparing the runtimes of the 2k and 4k variants of Acharya et al. For n 4096, the variant starts outperforming the 2k variant just beyond d whereas for n 8192, this advantage emerges between d 16 and d 32.
The primary reason behind Acharya et al.'s improved perfor- mance narrowing solution space as increases while remains fixed. A valid solution requires each segment have least d samples. For example, with d 256, 4096, and A 4, there are only four times the min- imum number of required samples. However, when con- sidering Archarya et al.'s variant that places four times the segments (effectively resulting in 16), the method forced into a scenario where only one viable solution ceisss-namely: an even distribution of breakpoints across the samples. This not only explains why Acharya al. are closing the performance gap in terms of both speed and accuracy, but it also accounts for why at high d values the 4k version outperforms the 2k version due to its more rapid collapse of the solution space.
B.3. Variable Number of Samples
Due the algorithm's runtimes, increasing n arbitrarily is not tractable. To keep the solution space size fixed, adjust by scaling relative to d instead of maintaining constant number of input samples. Specifically, we set n = 64 d, which ensures that the solution space remains constant while keeping the DP runtime manageable. The results are shown in Figure
The effects of employing rank-1 update remain evident in the runtimes of both DP and our approach-wil with its impact limited solely to DP's accuracy. Moreover, our method again is affected by an isolated outlier in two distinct scenarios, much like when n 4096. In all other cases, however, our accuracy aligns closely with that of the optimal baseline.
To further validate our analysis, we conducted the same experiment using n 8192. The results are shown in Figure 7. In this trial, the rank-1 update version of DP encountered early failure at d because the accumulated rounding errors resulted in matrix that behaved like singular one, i.e., matrix that has a determinant of 0, which cannot be inverted. Although the naïve DP variant did not fail completely, too struggled with accuracy issues at d 4 and 16 with 0.1. In contrast, our algorithm remained unaffected by these problems.
RUNTIME
For small values of d, the gap relative Acharya et al.'s results is smaller; however, this may be due measurement
15

---

Fast Min-c Segmented Regression using Constant-Tims Segment Merging
Runtime (s)
MSE
Relative Speedup
Relative MSE
10a
10
10
0.01
10a
10a
10a
10
10
10a
10-3
7. 64 d.
109
4
16
64
256
2
8
32
256
16
32
64
8
16
10a
10a
10a
10a
10a
10
10
10-3
10-3
10
109
4
16
256
2
8
32
256
16
32
64
8
dimension (d)
dimension (d)
dimension (d)
dimension (d)
Exact (DP)
Our Approach
Acharya
Acharya 4k
Exact (DP,RIU)
Our Approach (R1U)
Acharya
Figure 8. Similar experiment to the ones shown in Figure and Figure 7, but this time the number of samples is not fixed. It is always 64 times the number dimensions.
overhead since our timings were under one-tenth of mil- lisecond. For larger values, there are two key observations.
instead tends to stabilize at a near-constant value. Conse- quently, even a slight misalignment in the breakpoint has diminishing impact as the number of samples used for calculating the MSE continues grow.
From onward, the time for solving the linear equa- tions begins to increasingly influence overall runtime. The version without the rank-1 update takes longer and ap- proaches the runtime of Acharya et al., even though the runtime to break even is very large, probably somewhere between 10 and 10 seconds.
The relative error plot does not clearly show that Acharya al.'s 's version that places exactly i segments begins to narrow the performance gap when both d and n increase. This uncertainty is especially pronounced for a = 0.01.
Incorporating the rank-1 update into our algorithm yields constant speedup relative Acharya al.'s method, which demonstrated by the parallel lines in the log-log runtime graphs. This is expected given that both approaches share identical asymptotic complexity with respect to parameters and n. In this specific configuration, we observe an ap- proximate x00 speedup, depending on the exact version.
B.4. Conclusion
In evaluations using fixed-size solution space, we consis- tently observe a constant speedup factor in runtime. As and n increase, accuracy tends to level off-likely due to limitations in the experimental design or challenges with high-dimensional data, especially since improvements in the optimal bascline accuracy have platcaued.
ACCURACY
Except for some rare outliers, our method is on par with the optimal solution and is significantly more accurate than Acharya et al. al.-especilly compared their version using exactly segments. is also faster than all other algorithms, though its speed advantage relative Acharya al. remains consistent.
Measuring accuracy proves challenging and appears be in- fluenced by the noise variance present in the input data. The 2k and 4k variants of Acharya al.'s method seem to verge toward the baseline as more samples and dimensions are added-this observation holds at least for 0.01. This behavior may be linked to what is commonly known as the curse of dimensionality, where the space defined by increasing sample sizes expands much faster than linearly, resulting in sparse representation of that space. Unlike experiments conducted with fixed d, the baseline error does not decrease continuously with additional samples but
Our main paper showed that using more samples increases the gap in speed and accuracy between our algorithm and others. We expect a similar trend if we increase the ratio of n to d beyond 64. A much lower value is not suitable in practice, since it approaches the minimum amount of needed samples and probably results in overfitting.
16


Reviews:
[{"review_id": "uOeUtb1UuJ", "reviewer": "Reviewer_iMfW", "summary": "The authors present a new method and algorithm for min-$\\epsilon$ segmented\nregression. The main contributions are primarily algorithmic but also related\nto software engineering, as the authors implement highly efficient programming\ntechniques to enhance their implementation. The greedy algorithm they propose\nmerges neighboring segments in constant time. The paper includes one real-data\nexample and several synthetic benchmarks that demonstrate the efficiency of the\nmethod.\n\n## Update After Rebuttal\n\nI stand by my original, high, score of the paper. I think it is valuable and interesting work\nand that the paper is well-written and showcases strong results for the method. The\nauthors have also clarified some of my initial minor concerns.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable and constructive feedback regarding our paper, including the code and experiment setting.\n\n**Evaluation design and constraints:** The alternatives in our 'related work' section solve a slightly different problem, e.g., by enforcing continuity of the resulting piecewise function.\nWhile we did not conduct a full evaluation, we first tried to analyze the shown real-world data using these algorithms, but the runtimes were intractably high for our use case (5-10 minutes for pwlf, compared to the sub-second runtimes of the presented heuristics, see Table 2).\nAt the same time, the results were worse than the regression functions from the Acharya et al. heuristic, sometimes aborting because they did not converge to a solution at all.\nDirectly comparing these runtimes or errors to our work in the evaluation seemed unfair, since the additional constraints change the problem.\nFor the use case considered here, it does not make sense to choose these algorithms over any of the evaluated ones. We will rephrase the corresponding paragraph to express this setting more clearly.\n\n**Figure 5 and minor clarification:** We appreciate the additional feedback and the constructive suggestions to improve our work very much.\nOur goal was to plot the dataset in Figure 5 as accurately as possible. Still, we will change this by rasterizing the data or the whole image since the raw data is available digitally.\nFurthermore, we will definitely rephrase our statement regarding the programming language performance. It was meant with regards to the rest of the paragraph, i.e., in the context of our evaluation. We see that this sentence can be misleading if it is quoted separately.", "claims_and_evidence": "The claims are generally convincing and the results are strong. The\nproblem is well-motivated and the method is clearly explained.\n\nI would like to offer a couple of constructive suggestions:\n\n- On line 431, first column, you mention that your algorithm performs better\n  than certain alternatives from R and Python. However, I don't see evidence of\n  direct comparisons to these alternatives in the paper. If such comparisons were\n  conducted, including these experimental results would strengthen your claims.\n  If not, it might be helpful to clarify this statement and perhaps explain why\n  these comparisons weren't included. **Edit: I understand that these might not be \n  warranted after all, so please disregard this comment.**\n- It would be valuable to see an analysis of how well the theoretical\n  complexity of your method is reflected in practical performance.", "methods_and_evaluation_criteria": "The benchmarks presented are appropriate for the problem at hand. Additional\nbenchmarks would further strengthen the paper, and perhaps the supplementary\nmaterial could be utilized to provide these.", "theoretical_claims": "I briefly checked the complexity analysis and could not find any issues.", "experimental_designs_or_analyses": "The experiments are well-designed and the results are convincing.", "relation_to_broader_scientific_literature": "The relevant preceding papers appear to be appropriately cited and discussed.\nTable 1 effectively summarizes previous related contributions. The contribution\nof the current paper is straightforward, aiming to improve complexity and\npractical performance of this method.", "essential_references_not_discussed": "None that I could identify.", "other_strengths_and_weaknesses": "The paper is well-written and easy to follow, with a clear structure and\nhelpful illustrations that aid the reader in understanding the method. The\nplots are well-designed and clearly convey the relevant information.", "other_comments_or_suggestions": "- Figure 5 is large (in file size) and could benefit from being rasterized to\n  improve loading times of the PDF.\n- On line 307, second column, you suggest that results should not change by\n  orders of magnitude due to the implementation language. While this is likely\n  true when comparing Julia to C++, the statement may not hold for all language\n  comparisons. A slight rephrasing might more accurately reflect this nuance.", "questions_for_authors": "No", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NFRtEWnguX", "reviewer": "Reviewer_9p1E", "summary": "This paper proposes a new heuristic method for the $\\\\min$-$\\\\epsilon$ segmented regression problem. Some prior works propose two types of algorithms for this problem. One line of work (Bai & Perron, 1998; Yamamoto & Perron, 2013) gives optimal solutions for this problem with computational complexity $\\\\mathcal{O}(n^2)$, where $n$ is the number of samples. Another work (Acharya et al., 2016) focuses on the case where $n$ is large and provides a heuristic algorithm with computational complexity $\\\\mathcal{O}(n \\\\log n)$, though it can result in large errors. This paper proposes a new heuristic method that achieves: (1) computational complexity $\\mathcal{O}(n \\\\log n)$, and (2) (empirically) comparable to the optimal solutions. This paper provides computational complexity analysis for the proposed method and experiments showing the effectiveness of the proposed methods in terms of solutions quality and running time compared to prior works.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our work and for the suggestions for improvement.\n\n**Broader subject relevance:** We consider the topic of regression to be a fundamental building block for statistical analysis and machine learning.\nAs mentioned in Section 7, Diakonikolas et al. (2020) have shown that an approach for multidimensional breakpoints based on the algorithm published by Acharya et al. at ICML 2016 outperforms CART, even when using constant segment models (for fairness against CARTs limitations).\nThis suggests that fundamentally improving the basic segmented regression approach can lead to an improvement for those other problems.\n\n**Contribution:** From our perspective, our algorithm first and foremost drastically increases accuracy, rather than aiming to reduce computational complexity.\nIf, for a given use case, sufficient resources are available, it is already possible to use the dynamic program.\nOur evaluation shows that this is not favorable for large datasets, as the number of samples would need to be reduced.\nIn this case, the heuristics perform better.\nWhile our solution seems to be faster than Acharya's solution, the main contribution is its much higher accuracy and the focus on finding the correct breakpoints of the underlying data distribution.\nTherefore this work presents the first suitable algorithm if a time complexity of $O(n^2)$ is not acceptable and the exact positions of the breakpoints are important.\n\nIt is also important to mention that our algorithm does not scale with $\\mathcal{O}(nd^3 + n\\log{n})$.\nThis is true only for the specific implementation used in the evaluation, and it was mentioned only for transparency reasons.\nAs stated in Section 5, our algorithm scales with $\\mathcal{O}(nd^2+n\\log{n})$.\nThis is at least as good as the runtime complexity of Acharya's heuristic (cf. $\\mathcal{O}(nd^2\\log{n})$ in Section 3 of their paper).\nThe limitation regarding the number of dimensions is based on the OLS and affects all competing algorithms in the same way.\n\nThe reasons for the small value of $d$ in our evaluation are that (a) linear segmented regression is one of the most common use cases and best to illustrate, (b) $d$ and $k$ are typically constants that are chosen to model the data, which do not change, and (c) this allows us to perform a comparable evaluation to Acharya et al. (2016).\n\n**Relevance for ICML conference:** As stated above, we consider regression as a fundamental aspect of machine learning, that can be used on its own, but is also a building block to efficiently solve other problems in the domain of machine learning (as shown by Diakonikolas et al.). This is further underlined as the most relevant state of the art approach, Acharya et al. (2016), was also published at ICML.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. However, the theoretical side of this paper is minimal.", "experimental_designs_or_analyses": "Yes. This paper contains two main experiments: (1) one with synthetic data, where they generate piecewise continuous functions with the number of pieces $k = 6$, and create data sets of $n$ points using the generated functions plus Gaussian noises. The results of this experiment are shown in Figure 3. (2) Another experiment with real data of 43 hours of CPU usage, measured every two seconds, resulted in 70,607 samples. The results of this experiment are shown in Table 2 and Figure 5.", "relation_to_broader_scientific_literature": "Some prior works propose two types of algorithms for this problem. One line of work (Bai & Perron, 1998; Yamamoto & Perron, 2013) gives optimal solutions for this problem with computational complexity $\\\\mathcal{O}(n^2)$, where $n$ is the number of samples. Another work (Acharya et al., 2016) focuses on the case where $n$ is large and provides a heuristic algorithm with computational complexity $\\\\mathcal{O}(n \\\\log n)$, though it can result in large errors. This paper proposes a new heuristic method that achieves: (1) computational complexity $\\mathcal{O}(n \\\\log n)$, and (2) (empirically) comparable to the optimal solutions. This paper provides computational complexity analysis for the proposed method and experiments showing the effectiveness of the proposed methods in terms of solutions quality and running time compared to prior works.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Firstly, I am not an expert in this field so my opinion should be taken lightly. \n\n## Strengths\nThe proposed method for $\\\\min-\\\\epsilon$ $k$-segment regression is computationally efficient (comparable to the prior heuristic approach) and achieves good performance (shown empirically, comparable to the optimal solution). I also appreciate that the paper presentation is straightforward to follow. \n\n## Weaknesses\n\nTo me, the contribution of this paper is somewhat niche, and the contribution in the \"machine learning\" aspect does not meet the bar of a top ML conference. Here are the reasons. \n\n### The problem considered is (somewhat) niche \n   1. This paper considers the problem of $\\\\min$-\\$\\epsilon$ $k$ segmented regression. Though dealing with multi-dimensional data, the algorithm first has to choose a single axis/coefficient of the input and then perform segmenting along that particular axis. I know that this is not an issue with some specific types of data (e.g., time series), but it restricts the application of this method. \n\n  2. Many other methods can deal with this general case (e.g., classification and regression tree (CART), multivariate adaptive regression splines (MARS), or regression tree, to name but a few), which is segmenting using multiple axes. I know that those methods had their own limitations, but the point I am making here is that the setting this paper considered is just a sub-case of a much broader problem.\n\n  3. Besides, even if one restricts themselves to choosing only one axis to perform segmenting, choosing the axis itself is also a challenge.\n\n### The main contribution lies in the computational aspect; contribution in the machine learning aspect is limited\n   1. As far as I understand, the general idea of performing redundant segmentations along an axis and then merging was introduced by Arycha et al. (2016). I know it is controversial, but I think that the novelty of this paper lies in introducing a smarter way of merging segments that lead to improved solution quality (empirically). \n\n   2. Moreover, though claiming that this method works well on a large dataset, it is only in terms of the number of samples $n$. As said, there is another critical factor in their computation cost, which is $\\mathcal{O}(nd^2)$, where $d$ is the dimension of the input. This can scale up to $\\\\mathcal{O}(nd^3)$ if using standard implementation for calculating the inversed matrix, which is bad for high-dimensional data. Maybe that is why the experiments demonstrated in this paper were only conducted with data with small $d$. \n\n  3. Most importantly, the machine learning contribution of this paper is limited. For example, I want to see how the predicted (segmented) functions perform on unseen data or extrapolate to data that lies outside the interval. I know that this is the limitation of the considered problem itself, not necessarily of the proposed method, and it is just my taste.", "other_comments_or_suggestions": "I reiterate that I am not an expert in this field. Though I do not underestimate the contribution of this paper, I believe that the contribution in the ML aspect is not enough for an ICML publication. Since the main contribution lies in the algorithmic/computational aspect, I believe this paper should be submitted to other venues focusing on those aspects (e.g., STOC, SODA, or (somewhat) lesser conference like ITCS, etc.), or venues for data-mining (ICDM), or a more generic one like AAAI. **Though my overall recommendation is Weak Accept, my opinion is actually borderline, and I believe that the AC and other reviewers will have better judgement than me.**\n\n### Other minor comments\n\n1. At the beginning of page 2, please use itemize for the first paragraph (since the two contribution paragraphs also use itemize).", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7LxyflMWiJ", "reviewer": "Reviewer_Qyh8", "summary": "The paper addresses min-epsilon segmented regression, where the goal is to minimize the mean squared error (MSE) for a given number of segments. While the optimal solution has O(n^2)complexity (Bai & Perron, 1998), heuristics like Acharya et al. (2016) improve efficiency to O(n) but often introduce significant errors. The authors propose a method that merges segments using precomputed matrices, achieving 1,000 times lower MSE and 100 times faster runtime on large datasets. While promising, further clarification on theoretical guarantees and comparisons with recent heuristics would strengthen the evaluation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback.\n\n**Theoretical guarantees:** We would like to highlight that contrary to the reviewer's summary, the approach by Acharya et al. (2016), for a fixed value of $d$, improves the runtime of the approach to $\\mathcal{O}(n\\log{n})$, not $\\mathcal{O}(n)$. This can be seen in Table 1 of our paper, and is stated in Section 3 of the paper by Acharya et al. (2016).\n\n**Related work and state of the art:** We discuss multiple different approaches in our related work.\nAs discussed there, we believe that it would not be fair to compare against those, because they solve related, yet different problems.\nThis is clarified in further detail in our answer to another review (please see our answer to Reviewer iMfW).\n\nWhile the approach of Acharya et al. (2016) is used and extended to solve further problems (e.g., segmentation with multidimensional breakpoints), it denotes the state of the art for min-$\\epsilon$ segmented regression, together with the DP baseline. This is further underlined by it still being used in recent applications, for instance in a work [1] on gene expression analysis published in Nature Methods, which employs segmented regression to distinguish between different cell types, which we will mention and cite in the camera-ready paper.\n\n[1] Chitra, Uthsav, et al. \"Mapping the topography of spatial gene expression with interpretable deep learning.\" Nature Methods (2025): 1-12.", "claims_and_evidence": "The claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed method and evaluation criteria make sense for the problem considered in the paper", "theoretical_claims": "I reviewed them, but I didn't check the details.", "experimental_designs_or_analyses": "More comprehensive comparision results with the exisintg method shoud be provided and discussed", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths\n\n- The paper appears to be novel.\n- The paper is well-organized.\n\n\nWeaknesses\n\n- A more comprehensive comparison with existing methods should be provided and discussed, as the current results are relatively weak.\n\n- The authors state that the state-of-the-art (SOTA) method is Acharya et al. (2016), which seems unusual given that it was proposed nine years ago. Why have no more recent approaches been considered? Are there other baselines that could be included?", "other_comments_or_suggestions": "Please see Weaknesses.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bmKymwgc54", "reviewer": "Reviewer_Tjsb", "summary": "This paper provides a heuristic method to compute segmented regression. Instead of looking for the best segments directly, the algorithm finds as many segments as possible and then merges them until only k segments are left. The authors evaluate the algorithm on the synthetic datasets. The authors' method shows runtime or performance improvement compared to previous methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our work, for the constructive improvement ideas and for pointing out the interesting direction of isotonic regression.\n\n**Relation to isotonic regression** (we assume that the review refers to isotonic regression): While isotonic regression is also based on an ordered sample set, it results in a predicted increasing constant per sample, using linear interpolation between the sample positions. The resulting regression is a (not necessarily strict) monotonically increasing piecewise linear function, where the number of pieces (i.e. segments) can be very high ($k \\le n$). This problem setting is quite different to us, due to (a) the dynamic number of segments, (b) the enforced continuity, (c) the limitation to constant (or linear) models and (d) the restriction to monotonically increasing regressions. While the relation of isotonic regression to our approach is very interesting, we consider it to be a different type of problem.\n\n**Theoretical guarantees**: Indeed, based on the the way our algorithm works, we expect the accuracy guarantees of Acharya et al. (2016) to also hold true for our algorithm. At the same time, it is only possible to prove these statements for data with a very specific noise distribution. We instead focus on experiments with known distributions and real-world data with very unusual attributes to show the accuracy of our algorithm relative to the competing approaches.\n\n**Applications of segmented regression**: Despite the use cases listed in our introduction (ranging from ecology to econometrics to clinical guidelines), multiple approaches use these regressions for more efficient data structures [2,3]. A Nature Methods paper from this year [1] uses segmented regression as a step to model genetic data of tissue slices. In this example, it is not only necessary to have a small MSE, but to be able to get valuable breakpoint positions.\n\nWe see regression in general as a fundamental building block in statistical analysis and machine learning. This can also be seen in the work of Diakonikolas et al. (2020), where segmented regression (Acharya et al. (2016)) was used to present a more efficient alternative to the CART-algorithm.\n\n[1] Chitra, Uthsav, et al. \"Mapping the topography of spatial gene expression with interpretable deep learning.\" Nature Methods (2025): 1-12.\n\n[2] Galakatos, Alex, et al. \"FITing-Tree: A data-aware index structure.\" Proceedings of the 2019 international conference on management of data. 2019.\n\n[3] Dai, Yifan, et al. \"From WiscKey to bourbon: A learned index for Log-Structured merge trees.\" 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 2020.", "claims_and_evidence": "The authors' claims are proved by runtime analysis and experimental results.", "methods_and_evaluation_criteria": "The MSE used in the evaluation is very standard.", "theoretical_claims": "The runtime analysis looks good to me.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "I think this paper proposed an interesing heuristic method for segmented regressiion", "essential_references_not_discussed": "I think it would be nice for the authors to discuss a bit about the relation between segmented regression and istronic regression in the literature review.", "other_strengths_and_weaknesses": "I am wondering if the authors can provide any theoretical guarantee for accuracy. I think this would definitely make the paper more interesting.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "I am wondering if the authors can mention a bit more about why segmented regression is an interesting problem, like what application it has.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Overall, the reviewers found that the paper is well-written, and a valuable and interesting work. However, they also raised some concerns, including about limited theoretical novelty and insufficient comparison with existing methods, which should be carefully addressed.
Decision: Accept (poster)