acceptodds
Under review as a conference paper at ICLR 2027

Linear-Time Segmented Regression

Abstract

We present a linear-time algorithm for min- segmented regression, which fits a piecewise-linear function with a prescribed number of segments to a given dataset while minimizing the residual sum of squares. Such learning settings arise in many applications, including the general compression of time series data, the detection of economic indicators, or the identification of abrupt shifts in climate data. Exact solutions can be obtained via dynamic programming. However, the runtime scales quadratically with the dataset size. Recently, a greedy approach based on merging and subsequently fine-tuning segments has been proposed, which achieves a log-linear runtime in the number of data points. In this work, we propose an approach based on a greedy splitting and fine-tuning of segments, which exhibits a linear runtime with respect to the dataset size. In our experiments, we assess the runtime behavior and the achieved quality of our scheme and compare the results with dynamic programming and the recently proposed greedy approach, using both synthetic and real-world data. Our results indicate that our method scales linearly in practice, runs faster than the competing heuristic, and matches the exact solutions more often than the other approximation scheme.

Primary area:
learning on time series and dynamical systems
Keywords:
Segmented Regression, Piecewise Linear Functions, Time-Series Analysis

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_5rYiOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the problem of min-ϵ\epsilon segmented regression. Given NN datapoints from Rd\mathbb R^d and a number kk, the goal is to find a piecewise-linear function with at most kk segments which minimizes the residual sum of squares. The problem is solvable by dynamic programming in O(N2)O(N^2) time and a recently proposed heuristic from ICML 25 solves it in O(Nlog⁡N)O(N\log N) time. This paper proposes an O(Nd2)O(Nd^2)-time heuristic SPLIT+FIT based on greedy splitting into segments and fine-tuning. The fine-tuning step is the same as proposed in the ICML 25 paper. The only difference is the greedy splitting step (instead of greedy merging). The authors provide experiments on synthetic and real-world data comparing their approach with the DP and the Merge+Fit algorithms. Their algorithm finds close to optimal solutions within a considerable shorter time.

The results look decent and the presentation is adequate (but could be improved).

Critical strengths

The proposed heuristic seems to beat the state-of-the-art algorithms in practice.

Critical weaknesses

The overall idea is not very sophisticated. It simply does top-down greedy splitting instead of merging and uses existing fine-tuning. I am not sure whether this is interesting enough for ICLR.

Questions for authors

I am confused by your definition of piecewise-linear function, especially your examples and Figure 2. How can arbitrary polynomials be piecewise-linear? It seems like our definition differs from the one common in the literature.

Do you have any explanation why your splitting approach is beneficial over merging (both regarding runtime and solution quality)?

Reviewer_13f7OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Split+FT, a heuristic algorithm for segmented regression that combines greedy splitting with iterative local breakpoint refinement. The method achieves a time complexity of O(Nd2k)O(Nd^2k), which is linear in the number of data points NN for fixed input dimension dd and number of segments kk. Experiments on synthetic and real-world datasets demonstrate improved computational efficiency and approximation quality compared with a recent greedy merging baseline.

Critical strengths
  1. The paper is clearly written, and the proposed algorithm is simple and easy to follow.
  2. The computational complexity is well analyzed, demonstrating the algorithm's linear scalability with respect to the dataset size for fixed dd and kk.
Critical weaknesses

1.The proposed method combines classical greedy splitting with the local breakpoint refinement procedure introduced by Lößer et al. (2025). While the resulting algorithm is computationally efficient, the methodological novelty beyond combining existing techniques is limited.

2.The combination of greedy selection and local breakpoint estimation is conceptually related to prior change-point detection methods, such as Wu et al. (2024). Although the problem formulations differ, the authors should better clarify the methodological distinctions and position their contribution within the broader literature on change-point detection and segmentation.

Wu, Daoping, et al. "Unsupervised Change Point Detection in Multivariate Time Series." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

Questions for authors

see above

Reviewer_X4mrOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes Greedy Splitting and Fine-Tune (SPLIT+FT) for segmented regression. Given a number k, the goal is to find k segments while minimizing residual sum of squares when doing least square regression on these segments. The algorithm repeatedly inserts the breakpoint that most reduces error (SPLIT), then locally adjusts existing breakpoints (FT). In contrast with greedy merging + FT in the literature which has runtime O(Nlog⁡N+Nd2)O(N\log N + Nd^2) and memory O(Nd)O(Nd), the proposed algorithm has runtime O(Nd2k)O(Nd^2k) and memory O(Nd2)O(Nd^2). The runtime is improved in the regime where the number of data points N≫d2kN \gg d^2k. Experiments show faster execution and more frequent agreement with exact dynamic programming than greedy merging+FT.

Critical strengths
  • The main strength of the paper is in the simplicity of the algorithm. The algorithm can scale to a large number of datapoints on low dimensional datasets
  • Empirically, the algorithm shows promising results and stronger than the baseline of the merging based algorithm.
Critical weaknesses

There are a few weaknesses.

  • The algorithm is a heuristic with no approximation guarantee. The novelty also appears limited: it simply replaces the merging procedure with a splitting procedure and combines with the FT step which already exists.
  • The algorithm only has advantages against prior work when the number of datapoints is exponential in terms of d2kd^2k which can be very large when dd grows. The memory requirement is also worse by a factor dd.
  • Empirically evaluation is quite narrow, only one real-world dataset (although I'm not sure whether how many benchmark datasets for segmented regression exists, Lößer et al, 2025 use the same dataset).
Questions for authors

How does your algorithm compare with greedy splitting followed by a single final fine-tuning step at the end, in both accuracy, runtime and performance?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.