Fast Min-ε Segmented Regression using Constant-Time Segment Merging
Key: LSSW+25
Author: Ansgar Lößer, Max Schlecht, Florian Schintke, Joel Witzke, Matthias Weidlich, Björn Scheuermann
Date: October 2025
Kind: In proceedings
Publisher: PMLR
Book title: Proceedings of the 42nd International Conference on Machine Learning
Abstract: Segmented regression is a statistical method that approximates a function f by a piecewise function f^ using noisy data samples. Min-ϵ approaches aim to reduce the regression function’s mean squared error (MSE) for a given number of k segments. An optimal solution for min-ϵ segmented regression is found in O(n²) time (Bai & Perron, 1998; Yamamoto & Perron, 2013) for n samples. For large datasets, current heuristics improve time complexity to 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-ϵ 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.
View Full paper (PDF) | Download Full paper (PDF)
Official URL

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, not withstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.