Find Optimal Piecewise Constant Regression Parameters

Given a dataset of one-dimensional training examples \((x_i, y_i)\) for \(i = 1, \dots, n\), fit a one-split piecewise constant regression model: \[ \hat{y}_i = \begin{cases} b_1, & x_i \le t \\ b_2, & x_i > t \end{cases} \] Find the values of \(b_1\), \(b_2\), and threshold \(t\) that minimize the mean squared error: \[ \frac{1}{n}\sum_{i=1}^{n}(y_i - \hat{y}_i)^2. \] Explain the optimal choice of \(b_1\) and \(b_2\) for a fixed threshold, and describe an efficient algorithm for finding the globally optimal threshold.