- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies the problem of min- segmented regression. Given datapoints from and a number , the goal is to find a piecewise-linear function with at most segments which minimizes the residual sum of squares. The problem is solvable by dynamic programming in time and a recently proposed heuristic from ICML 25 solves it in time. This paper proposes an -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)?