AKORN: Adaptive Knots generated Online for RegressioN splines

Thank you very much for your consideration.

Weaknesses 2 and 4

The weaknesses you point out in 2 and 4 are fully accurate, although we feel that the multivariate problem you mention in 4 is outside of the scope of this paper. High-dimensional nonparametric regression is often considered separately from univariate regression. If you are curious about the challenges that remain in extending AKORN to $TV_{k > 1}$, we expand on them in our response to Reviewer YjPY.

Worst-case analysis (Weakness 3)

To be clear, AKORN is minimax optimal over $TV_1(C) = \\{f \ : \ TV_1(f) \leq C\\}$, which is the only minimax result we are aware of for linear Trend Filtering. This is a corollary of the instance-dependent results.

Uneven Covariates (Weakness 1)

With respect to the spacing of the covariates. Since submitting this paper, we have discovered that we can generalize AKORN to handle uneven covariates by tweaking our proof in a few places. Specifically, ADDLE/AKORN can achieve the same rate for covariates $x_1, … x_n \sim p$, where $p$ is some density that is bounded below (that is, $p(x) \geq p_0 > 0$ for $0 \leq x \leq 1$ exactly as in [4]). We will list the technical steps as a the end of this rebuttal. If reviewers and AC approve, we would like to include this result in the paper. In order to maintain accessibility and consistency, we believe it makes sense to include the result in an appendix, as is done in Tibshirani 2014.

“What happens if AKORN misidentifies some change points?”

While it would be an interesting experiment to see how many knots we could perturb while retaining good performance, do note that our theoretical guarantee says that AKORN will not catastrophically misidentify knots. Another lens on this point is as follows. Each time we run AKORN with different realizations of the noise vector, it can potentially identify a different knot-set. But our theoretical and experimental results show that whatever knot-set AKORN selects is sufficient for (near-)optimal performance (whp). As a practical observation, the sensitivity of the knot-set to noise increases with $n$, but the sensitivity of the MSE to the knot-set decreases with $n$.

Technical steps for uneven covariates:

In this response, we explain the tweaks necessary to prove that ADDLE/AKORN achieve the rate $\tilde O(n^{-4/5}C^{2/5})$ with probability $1 - 2p_0n^{-10} - \delta$ when covariates are sampled iid from a density $p$ such that $p(x) \geq p_0 > 0$ for $0 \leq x \leq 1$.

Key lemma, "Lemma K" (The bias of linear regression error is controlled even on uneven points) Let $x_1, ..., x_n$ be a sorted list of design points whose max gap is bounded: \max_{i > 1\} x_i - x_{i - 1} = O(\log{n}/n). Let $l_{r:s}$ be the linear least squares fit on $(x_r, \theta_r), ... (x_s, \theta_s)$. Then $\sum_{j = r}^s (l_{r:s}(x_j) - \theta_j)^2 = \tilde O(\frac{|s - r|^3TV_1(\theta[r:s])^2}{n^2})$.

Lemma 5 from [4] Suppose $\{x_i\}$ is sampled iid from a pdf, p, that is bounded below by $p_0 > 0$. Lemma 5 from [4] implies that, w.h.p, the max gap between any two covariates in the set $\{x_i\}$ is bounded by $O(log(n)/n)$ with probability at least $1 - 2p_0n^{-10}$.

ADDLE generalization:

1. Change online linear regression experts to (clipped) VAW forecasters. This very minor algorithmic change does not affect computational efficiency.
2. VAW linear forecasters enjoy the same upper bound as offline linear regression up to an additive constant This follows from Theorem 11.8 in [1] paired with Corollary 40 in [2] to control the norm of the least-squares comparator.
3. We can reduce the error of ADDLE on an interval $[r, s]$ to the error of the (clipped) expert that starts at $r$ using the same argument as before (i.e., Appendix D's proof up to Equation (15) doesn’t need to change).
4. The error (unclipped) expert can then be bounded using part (2). Instead of line 1157 of the submission, we use part (2) above to bound the online experts error by $\sum_{j = r}^s (\hat l_{r:s}(x_j) - \theta_j)^2 + O(1)$, where $\hat l_{r:s}$ is batch regression of the noisy responses $y_r, ... y_s$ onto $x_r, ... x_s$. We then use concentration of $\hat l_{r:s}$ to $E[\hat{l}_{r:s}]$ and Lemma "K" to finish the bound.
5. We can use the same oracle partitioning scheme as before to produce a set of intervals of size $O(n^{1/5}C^{2/5})$ together with experts who achieve constant error on each interval.

AKORN generalization The proof for AKORN now needs only trivial changes.

More detailed treatment can be found at this anonymized link: https://anonymous.4open.science/r/AKORN-uneven-D6FB/akorn_non_evenly_spaced_points.pdf

[1] Prediction Learning and Games. Cesa-Bianchi and Lugosi.

[2] Adaptive Online Estimation of Piecewise Polynomial Trends. Baby and Wang, 2020

[3] Multivariate trend filtering for lattice data, Sandhalana et al., 2024.

[4] The falling factorial basis and its statistical applications. Wang et al., 2014

Thank you for your attention to this work!

Non-evenly spaced design points

Since submitting this paper, we have discovered that we can generalize AKORN to handle uneven covariates by tweaking our proof in a few places. Specifically, ADDLE/AKORN can achieve the same rates for covariates $x_1, … x_n \sim p$ where $p$ is a pdf that is bounded below (as in Wang et al., 2014). We enumerate the necessary changes in our response to Reviewer V1hW and would like to include the generalized result as an appendix of the final version of this paper (as is done in Tibshirani, 2014). Your input on this extension would be greatly appreciated.

Proof sketches

Thank you for mentioning the informality in the proof sketches section. The Change-point Detection lemma that you mention is an informal statement of Lemma C.1 in the Appendix, which we forgot to mention during the proof sketch. This will be fixed in future versions of the paper. More generally, the reason that the proof-sketch lemmas are informally stated is space. We hope that the informal statements are understandable, and welcome input on this front (we are aware of a typo in Lemma 7.3 – the projection operator should be applied to Y rather than $\theta$). Rigorous statements are all available in the appendices, and the main theorems of the paper are formally stated in Section 6.

Higher-order Smoothness Classes

There are two main steps to generalizing to higher-order smoothness classes. The first (relatively easy) step is generalizing the computations in Appendix E.1 to polynomial regression. For unevenly spaced design points, this corresponds to the generalizing the (much cleaner) "Lemma K" given in the response to V1hW. The second task is in generalizing the Spline Existence Lemma (Lemma C.7) to higher order splines. Specifically, given two kth-order piecewise polynomial functions with disjoint knot-sets, we need to show that there is a kth-order spline on some augmented knot-set that lies between the two curves (or some strategic weakening of this). We do not yet know how to do this. Apart from these steps, the bulk of the proof can be adapted to the higher-order cases fairly trivially.

Thank you very much for this detailed review. Firstly, thank you for mentioning the typos. We will make appropriate adjustments (e.g. remove the use of $T:=n$ to avoid confusion with the transpose operation).

Uniform spacing:

Since submitting this paper, we have discovered that we can generalize AKORN to handle uneven covariates by tweaking our proof in a few places. Specifically, we can achieve the same result for covariates $x_1, … x_n \sim p$ and $p$ bounded below (exactly as in Wang et al., 2014). In light of reviewers’ comments, we would like to include this result as an appendix. In our response to Reviewer V1hW, we outline the tweaks that are required. These turn out not to be too extensive; from a technical perspective, fixed uniform design is not too different from iid samples from a (nice) distribution. We would greatly appreciate your feedback on this point.

“Given the existence of several methods achieves a minimax-optimal convergence rate and comparable runtime, it's unclear if AKORN provides significant advantages over other adaptive regression methods.”

As you mention, AKORN is adaptive and empirically competitive with Trend Filtering, Locally Adaptive Regression Splines. We aren’t aware of other adaptive methods with comparable empirical performance (see comparison with Wavelets in Section 5 of the paper).

Computational complexity:

It’s true that the computational complexity of AKORN is slightly prohibitive, but we elaborate on the topic now.

Firstly, note that the $O(n^2)$ upper bound is, in practice, somewhat loose. This is because AKORN periodically restarts ADDLE during the online pass, meaning that we do not perform $t$ regression steps at timestep $t$. Furthermore, when we perform regression onto the knotset K, whose size is $d = O(n^{1/5}C^{2/5})$, we use $O(d^2n) = O(n^{7/5}C^{2/5})$ compute. So even without any tweaks, real performance is often better than the $O(n^2)$ suggests.

On top of this, it is possible (as you mention) to run ADDLE with a smaller set of experts to get an $O(n\log{n})$ online algorithm. In practice, this may lead to significant speed-up when ADDLE is called as a subroutine by AKORN. However, due to the definition of AKORN, this doesn’t shave any compute off of the asymptotic runtime on the offline problem (at least not trivially).

Lastly, allow us to note that, technically speaking, the worst-case compute of SOTA Trend Filtering (TF) is superlinear: $O(n^{3/2}\log{1/\epsilon})$ to output an $\epsilon$-suboptimal solution for the associated optimization problem (Tibshirani, 2014). On the other hand, AKORN computes an exact solution.

Furthermore, the $O(n^{3/2}\log{1/\epsilon})$ bound for Trend Filtering doesn’t take into account the cost of parameter tuning. If we do this with SURE, for an upper bound $C$ on $TV_1[f]$ and at discretization level $\Delta$, then we need to solve TF $C/\Delta$ times while also computing DoF for each solution. Furthermore, in general, the only a-priori upper bound on $C$ that is possible is $C = O(n^2)$.

So while, practically speaking, people know how to do TF extremely efficiently, the theoretical picture is slightly complicated.

We appreciate your time and consideration.