AKORN: Adaptive Knots generated Online for RegressioN splines
Authors: Sunil Madhow
Dheeraj Baby
Yu-Xiang Wang
Venue: ICML 2025 poster (2025)
Keywords: nonparametric regression
total variation
adaptive
splines
online learning
Primary area: theory->everything_else
TL;DR: We propose a knot-selection scheme for producing a knot set whose corresponding least-squares regression spline is optimal over the space of functions in  TV_1

Abstract: In order to attain optimal rates, state-of-the-art algorithms for non-parametric regression require that a hyperparameter be tuned according to the smoothness of the ground truth (Tibshirani, 2014). This amounts to an assumption of oracle access to certain features of the data-generating process. We present a parameter-free algorithm for offline non-parametric regression over $TV_1$-bounded functions. By feeding offline data into an optimal online denoising algorithm styled after (Baby et al., 2021), we are able to use change-points to adaptively select knots that respect the geometry of the underlying ground truth. We call this procedure AKORN (Adaptive Knots gener- ated Online for RegressioN splines). By combining forward and backward passes over the data, we obtain an estimator whose empirical performance is close to Trend Filtering (Kim et al., 2009; Tibshirani, 2014), even when we provide the latter with oracle knowledge of the ground truth’s smoothness.

AKORN: Adaptive Knots generated Online for RegressioN splines
Sunil Madhow Dheeraj Baby? 2 Yu-Xiang Wang'
Abstract
Consider the problem of non-parametric regression over total variation smoothness classes. For some covariates (=))==> we observe data
In order to attain optimal rates, state-of-the-ar algorithms for non-paraman non-parametrie regression require that hyperparameter be tuned according the smoothness of the ground truth (Tibshirani, 2014). This amounts to assumption of oracle access to certain features of the data-generating pro- cess. We present a parameter-free algorithm for offline panpaaamettri regression over 7 TV1- bounded functions. By feeding offline data into an optimal online denoising algorithm styled after (Baby et al., 2021), we are able to change- points to adaptively select knots that respect the geometry of the underlying ground truth. We call this procedure AKORN (Adaptive Knots gener- ated Online for RegressioN splines). By combin- ing forward and backward passes over the data, we obtain an estimator whose empirical perfor- mance is close to Trend Filtering (Kim al., 2009; Tibshirani, 2014), even when we provide the latter with oracle knowledge of the ground truth's smoothness.
yi = [xxs) +
(1)
where { are i..dd (O, o²) random variables and has bounded k-th order total variation, which means that the variation in its kth derivative is controlled.
Traditionally, the best solutions to this problem solve func- tional lokkminimization objectives with regularization on TVg-smoothness (Tibshirani, 2014). In order to enjoy opti- mal statistical rates, such methods require the regularization to be tuned in correspondence with tight upper-bound on the TV₁ of the ground truth. This makes it difficult for prac- titioners to be sure that they are benefiting from the powerful theory already established the literature (Tibshirani, 2014; Guntuboyina al., 2020).
Recent work uses algorithms from the Online Learning (OL) literature (Hazan et al., 2006; Baby al., 2021; Chatterjee & Goswami, 2023) to treat the online version of this regression problem, where points (I1, are revealed one at a time. Thanks to the powerful oracle inequalities enjoyed by OL algorithms, these methods attain optimal' statistical rates while obviating the necessity for priori knowledge of the smoothness of
1. Introduction
When applied directly in the offline setting, however, exist- ing OL-based methods have serious drawbacks. Principal among these is the fact that their output is not a function f. but rather a highly non- non-smooth sequence predictions, (......n)) This is problematic because inferring a smooth, functional form is one of the key goals in the regression liter- ature (Donoho & Johnstone, 1994). At the same time, each prediction, ÿt. is made with only knowledge of ./t-11 making it harder to pick up patterns in the data. The result is that, when specialized to the offline setting (for instance, by interpolating the predictions -n)), online algorithms are badly outperformed by traditional methods terms of both MSE and attractiveness of fit (Baby al., 2021).
When estimating a nonparametric function with noisy data, the key challenge knowing where to smooth observations and by how much. Because the "wiggliness" of the ground truth is unknown, practitioners are almost always left with hyperparameter to tune, which corresponds to the wiggliness of the fit. Attaining optimal statistical rates often requires this parameter to be tuned with oracle knowledge of the ground truth. In this paper, we propose a (near) optimaal, parameter-free algorithm for non- non-paramttric regression that uses techniques from online learning to automatically adapt to the smoothness of the ground truth.
'Halicioglu Data Science Institute, UC San Diego Amazon (Work was completed prior to joining.). Correspondence Sunil Madhow <smadhow @ ucsd.edu>.
Is it possible to inject the instance-dependee knowledge acquired by online algorithms into inherently offline algo-
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Optimal rates for online and offline regression over TV classes differ only in lower-order terms

---

AKORN: Adaptive Knots generated Online for RegressioN splines
Local Linear Regression
ADDLE
AKORN
Figure 1. "Attention Map" for AKORN compared ADDLE and Local Linear Regression for noisy evaluations of the Doppler function of (Donoho & Johnstone, 1994). Observe that ADDLE and AKORN can select the appropriate "bandwidth" for the local linear fit adaptively.
rithms? In this paper, we present an OL-based algorithm called AKORN (Adaptive Knots generated Online for Re- gressioN splines) for offline non-parametric regression that retains some of the best properties of online and offline methods:
1.1. Key Techniques and Other Contributions
We reduce knot-selection to optimal online denoising. By suitably measuring the stationarity an online learner's predictions, AKORN adaptively generates a set of knots, which, when used to fit a linear regression spline, gives optimal statistical rates.
1. AKORN adapts to the smoothness of the ground truth with no need for hyperparameter tuning. That is, with- out any knowledge of [V] AKORN outputs linear spline, f. satisfying
2.
To this end, we introduce ADDLE (Adaptive Denois- ing with Linear Experts), which optimally solves the online non- non-parametric denoising problem for functions of bounded 1st-order TV: an extension of "Aligator" from (Baby et al., 2021).
Σ (((x)) f(x;)) =ppn 10pi'p///(/niiiiii 1/
3.
We carry out the analysis for AKORN by introducing a fictitious estimator which allows us to deal with the statistical dependence between the adaptive knots and the data. This technique may be useful in other work knot-selection.
Furthermore, fis guaranteed to have number of knots scaling as ((22/5TVV/512/555
2. AKORN learns a function, f. rather than a sequence of point predictions. As such, AKORN offers a principled way of using online methodology for inference, rather than pure prediction.
2. Related Work
Regression over total variation classes is well-studied in the literature (Muller, 1992; Donoho & Johnstone, 1994; 1998; Tibshirani, 2014). Optimal techniques include wavelet smoothing (Donoho & Johnstone, 1994; 1998), Locally Adapive Regression Splines (Mammen van de Geer, 1997), and the now state-of-the-art Trend Filtering estimate (Kim et al., 2009; Tibshirani, 2014). Crucially, most of these methods require injection of priori knowledge of the smoothness of f via hyperparameter, unlike AKORN.
3. We can visualize AKORN's "attention map" as in Fig- ure 1. This highlights AKORN's ability to optimize a bias-variance tradeoff in neighborhood each covari- ate I2 a property inherited from its online subroutines. Details the attention map are in Section 5.1.
4. AKORN enjoys the optimal statistical rate for the of- fline regression problem without requiring strict attention to functions whose TV1 is bounded by a known constant. That is, the rate in item I is an instance-dependent rate that holds over the set of ground truths {f [V < oo} rather than just minimax rate over ( TV1 < a} for some a E R.
Some work makes use of Stein's 's Unbiased Risk Estima- tor (SURE) to select hyperparameters (Tibshirani & Taylor, 2012: Tibshirani. 2015; Donoho Johnstone, 1995). These methods are typically heuristic, as extracting provable guar- antees involves proving uniform convergence of SURE. The exception is (Donoho & Johnstone, 1995), which obtains this uniform convergence for wavelet smoothing. Though wavelets enjoy powerful adaptivity properties from a the- oretical perspective, Trend Filtering achieves much better results in practice (Tibshirani, 2014).
5. Empirically, AKORN is competitive with state of the art offline methods, even when they are artificially provided with the best possible hyperparameters.
2

---

AKORN: Adaptive Knots generated Online for RegressioN splines
There has also been interest in the online nonparametric regression setting, which surprisingly is not much harder than the offline setting (Rakhlin& & Sridharan, 2014). Re- cently, Baby et al. (2021) uses oracle inequalities from the online literature (Hazan et al., 2006) to design an optimal parameter-free algorithm called "Aligator" for the online regression problem over TV. Unfortunately, when special- ized to the offline setting, Aligator cannot compete with Trend Filtering empirically.
per, we use only the discrete total variation from Definition 3.1.
We assume that we are given data of the form {(2,, yc y:) according to Equation where f has bounded TV1. We reserve the letter C' to denote C == [V: {2x 1=1)-
Remark 3.3. Why TV? While TVo-functions can be approximated by a sparse combination of Heaviside func- tions, TV1-function with a sparse number of knots. Thus, in the TV, setting, it is "proper" to output a discontinuous, piecewise constant estimate ((Baby et al., 2023) provides a recipe for doing this with a sparse number of segments). On the other hand, "proper" estimates for TV1 functions (and TV+>1) should be continuous, addition to having a sparse number of change points. Thus, TV, is the first level at which the mismatch between inherently discontinuous online predictions and an inherently continuous ground truth must be addressed in ffline-to-onlingg reductions.
All minimax optimal estimates for TV classes must be non- linear functions of the responses in order to display local adaptivity, as shown in Donoho & Johnstone (1998). For our method, this means knots must be adaptively spaced according to the change-points of the ground truth. Many algorithms have been proposed for knot selection (Fried- man, 1991; Luo & Wahba, 1997; Wand, 2000), typically by choosing a large knotset and recursively purging knots (Goepp et al., 2025). To our knowledge, AKORN is the first knot selection algorithm with provable guarantees.
well approximated by linear splines
A more detailed discussion of related work is available in Appendix A.
In the online setting, each data point comes to us at time, and the goal is to produce a sequence of predictions d: so that Σx= (0t - 8 is as small as possible. In Section 4.1, we describe an optimal parameter-free algorithm for the online problem.
3. Problem Setup
We now instantiate the model in Equation 1 by defining our assumption on f. We impose regularity on the ground truth as measured by its Ist-order total
= [f(x))....
In the offline setting (our main target), we wish to produce model f such that (f=((())) - f(x))) 2 is small, as- suming simultancous access to all data points. Though the asymptotic rates for the offline setting and online setting are the same (up to lower-order terms) (Rakhlin & Sridharan, 2014; Baby & Wang, 2019), algorithms for the offline set- ting typically substantially outperform algorithms for the online setting. In Section 4.2, we propose a reduction from the offline setting to the online setting that mitigates the em- pirical drawbacks typically suffered by online algorithms.
variation.
Definition 3.1. The 1st-order total variation of a vector 0 E R" with respect to the points Dx {21, [nn is defined as
00 = Σ
T1
0: 0:11
0i-1 0i-2
x4 2
x4-1 - x2-2
By extension, we define the discrete total variation of function f with respect the points Dx= = (#1, (0i.-:.90 3n as
3.1. Additional assumptions
Dxl Dx
We assume that is bounded by an unknown constant, Ifl B. As mentioned in (Baby et al., 2021), this as- sumption is typically not made in the literature (Donoho & Johnstone, 1994; Tibshirani, 2014). When f is continuous, this assumption is vacuous. Without loss of generality, we let B 1.
where 0 = =..(
As we shall be computing TV1 with respect fixed covari- ates, we tend to suppress Dx in the above notation. Remark 3.2. The definitions adopted above, while standard (Guntuboyina et al., 2020), differ subtly from the definition of the true 1st-order total variation seminorm, || ||Tv, de- fined for weakly differentiable functions (Tibshirani, 2014). To our knowledge, neither is more general than the other. However for g differentiable, we have
In the body of this paper, we assume that the covariates are equally spaced: x; = i/n. This assumption is rather strong, but has been the starting point for many non- non-parametric regression algorithms, including Trend Filtering (Donoho & Johnstone, 1994; Tibshirani, 2014), where it was subse- quently relaxed (Wang et al., 2014; Sadhanala & Tibshirani, 2019). In Appendix F, we show how a modified version of AKORN can handle uneven and random covariates.
[Vi Dx] < ||g||v
for all Dx, implying that [f] can be replaced by [l in our bound when o is differentiable. Throughout this pa-
3

---

AKORN: Adaptive Knots generated Online for RegressioN splines
3.2. Additional Notation
ponential reweighting scheme update its weights each time-step according to observed losses. A formal descrip- tion of FLH/ADDLE appears in Appendix B.
For single natural number, a, we let [a] := { ..., a). For real number, 2, we let (z)+ max(2, 0). Let e; E Ie be the ith standard basis vector.
Since our end goal is to address offline data, we assume the data is revealed in isotonoic order (i.e., our 1-th observation is st), though this assumption can be relaxed by means of a geometric cover (Baby et al., 2021). Furthermore, the algorithm can be generalized to handle any TVk by augmenting the experts to perform online regression with kth degree polynomials.
We introduce the notation Dx = f and Dy = -yn). When k, k' E Dx with h < k. we define
[k, k3] = f Dx= : k S x k'}.
We also notate 0- = ..,, =
We assume that, for all [n], 24 i/n. Strictly speaking, matter of convenience,
each r; is scalar. However, we will sometimes notate [1, as z; when the distinction is clear from context. We define the truncated power basis,
Remark 4.1. Though ADDLE has not, to our knowledge, appeared in the literature, much of the technical scaffolding for online denoising over TV classes via expert aggregation appeared in (Baby et al., 2021). As such, the main technical contribution of this paper is AKORN.
{g: : [0, - ] as follows:
(5(x) = (x - zz)+ :iii<n----
4.2. AKORN
In (z) (1)== 1
As we have mentioned, one issue with ADDLE is that the predictions, {ú:}. are not very useful in the offline setting. We now present AKORN, which uses online forward and backward passes together with an adaptive restarting rule in order to curate a set of knots, K = (A1, C Dxx With these knots in hand, AKORN then returns the best linear regression spline with knots in K:
For any i, we vectorize the evaluations of gj on the data as 9, = (g)( (x.)))
Finally, for any set of (non-repeating) knots K = (kk) C Dx. we let ((K) = (g U {gylek. For this K, we also let Hx be the matrix whose columns are {1I, (1;-11)++ Ihi (1.)),..d .. (x.))" J We use S(K)= = span ((K) to denote the space of (evaluations of) linear splines with knotset K. We use F(K) (G U (fI...<KK))) where Ej = Σi= 6 to denote the space of (evaluations of) piecewise linear functions with knotset K.
f(x) [1, xz) Ih (I), ... Ih. (Hx
=: Ps(K)
where we recall from Section 3.2 that gk, is the truncated
We sometimes abuse notation by identifying functions p: 10, 1| + with the dimen-dimensional vector of their evaluations on Dx, (p(a1);--,,p*1
power basis function (xr - Ik.) )+ and Hx is the data- matrix whose columns are the features [1, (- x1)+, (-- k))+...(-- + I and we have engaged in the aforemen- tioned abuse of notation f = Ps(K)).
This is done only when the underlying function p is clear from context, as is the case when we are discussing the ground truth (f ==: 0), or any linear spline E/= (z) := 1,
To form K, AKORN begins by generating forward knot- set, Ky, and backward knotset, Ko. These are generated by feeding the data to Algorithm 1 in isotonic and reverse- isotonic order respectively. Algorithm is inspired by Al- gorithm 5 in (Baby et al., 2023), which was designed to impose a low-switching constraint on online predictions. Essentially, every time ADDLE starts (say, at time b E [n]). the predictions of ADDLE are compared to linear regres- sion that also starts at time b. When the total square distance between these sequences drifts above a certain constant, we conclude that we have exited the interval in which we can linearly approximate f. and we put down a knot. The effect is that ADDLE restarts only when a noisy surrogate of the TV; within the interval exceeds n/ (Interval Size)3/2 (see Lemma C.I).
4. ADDLE and AKORN
4.1. ADDLE: Online Denoising for TV1
We first introduce ADDLE (ADaptive Denoising with Lin- ear Experts) to treat the online problem of denoising the se- quence of responses } with sequence V..h. J.
where the responses come from the data model in Equation 1.
ADDLE operates by running Follow-the-Leading
(FLH) (Hazan et al., 2006) with experts given by online linear regression (Algorithm 3 in Appendix B) and loss functions f.).) (- 2 FLH predicts weighted com- bination of the predictions by each expert, and uses an ex-
To complete the construction of K, we generate preliminary fits g PF(K,) E IR" and h = PF(K,) Y E R and form K. the set of all crossover points of g and h. Crossover
Strictly speaking, ADDLE actually runs clipped version of linear regression. See Appendix B for details
4

---

AKORN: Adaptive Knots generated Online for RegressioN splines
Algorithm 1 FindKnots
4.3. Computational Complexity
Input: data {(12, W variance x²
Using an O(1)-time update rule for each linear expert, AD- DLE can be implemented in O time. AKORN also runs in O(n²). As aside, observe that Algorithm 1 can be viewed as an optimized form of ADDLE that adaptively purges the pool of experts. Using a Geometric Cover as in (Baby et al., 2021), is straightforward to reduce the run-time of ADDLE to O l). However, this does not immediately lead to an (n log n) runtime for AKORN.
b+0
- 0
Start ADDLE instance A
for [1,... do
0. < prediction for 2t from A
âe f LinearteastSquare For all j [tt]
(=b((-1)) {E IR))
I set 23 + 27
- Σj (w} - 0,)²
For comparison, the worst-case computational complexity of Trend Filtering is Onza/2 log {) to find an e-approximate solution (Tibshirani, 2014). This does not take into account the cost of parameter tuning. If we tune parameters heuristi- cally using Stein's 's Unbiased Risk Estimator at a discretiza- tion level A, we need to solve trend filtering C/A times and compute the the effective degrees of freedom (dof) of each fit. In general, the only possible a-priori upper bound C' is C O leading to generic complexity of Onn log 1/e). In practice, algorithms for solving trend filtering are extremely fast, and the main computational burden comes from computing dof for several candidate fits.
if > 50 log 8
2n then
K K U 1
b=t
Restart A endle if
Update A with yr end for output KC
Algorithm 2 AKORN
Input: data {Iz, V1 Hi-, variance o²
K + Lindknots((al (f2,, yr 1.
K2 t FindKnot i (f u Wi.inn
5. Experimental Results
g < PF(K))
5.1. Local adaptivity
< PF(K))Y
K + Crossovers(() h. (=1))=))
As matter of interest, we begin by noting that the fitted values from ADDLE can be expressed as
Keollision + -fxe (t <n - 1) A I+t1 E Ky n K&}
K = KUUKS U K Krolission
output f PS(KYUKKUK)
Y Vaddle = Waddte
for some hat-matrix W Waddle that depends on the weights of the ADDLE instance. We can do the same for AKORN:
points are defined as covariates z, where either of the fol- lowing holds
Yakorn Wakorn Y
1. h(2)) 2 g((e) and g((++)) h(2+11)
where Wakorn = (H Because the band- width of these matrices around each diagonal elment (i, corresponds to the neighborhood of the data used in forming the ith prediction, DJ, we dub W Waddle and Wakorn "attention maps."
2. g(zx) 2 (Zz)) and (((++1) g(z+1))
We then report K KK,K, and perform least-squares regression of Y onto the space S(K).
In effect, AKORN is forced to first think about the data from an online perspective- at this step it forms qualitative understanding of the ground truth f. summarized by the knot sets Ky and K₁. then combines this understanding with offline access to the data in order to produce a fit that simultancously attractive and adaptive.
It is informative to compare these learned attention maps to the static attention induced by local linear regression, as we do in Figure for Donoho Johnstone (1994)'s "Doppler" function. Unlike local linear regression, we can see that that ADDLE has learned how adaptively optimize bias- variance trade-off in the neighborhood of each data point by choosing a spatially varying "bandwidth". Similarly, we see that AKORN inherits ADDLE's s learned knowledge of the geometry of the ground truth. is well-known that this kind of local adaptivity is essential to getting optimal rates over TV classes (Donoho & Johnstone, 1994).
Remark 4.2. Strictly speaking, our proofs require that we also add to K all points in the set Keoltizion := (xx : (t < n 1) A 1 E K 0 K,). When n, the number data points, is large and σ > 0, it is rare that K2 and K,, share knots, so we mention this step only parenthetically.
5

---

AKORN: Adaptive Knots generated Online for RegressioN splines
Empirical
Rates
MSEs for Doppler Function (n = 1000)
PW-Lin
Doppler
Jump
0
Oracle TF
DoF TF
AKORN
Wavelets
Oracle TF
-0.95
-0.84
-0.37
0
0
0
AKORN
-1
-0.91
-0.7
0.1
0.0004
0.0006
0.0008
0.005
0.2
0.0012
0.0016
0.0023
0.014
Table 1. Estimated rates determined as the slopes of the lines
0.3
0.0023
0.003
0.0039
0.024
corresponding to Oracle TF and AKORN in Figure 2. Each entry the table gives the exponent, 7; the rate O(n²)
0.4
0.0034
0.0041
0.0052
0.034
0.5
0.0057
0.007
0.007
0.046
Table 2. Values averaged over 20 runs and rounded to the nearest 10-4
5.2. Performance comparison
While ADDLE's ability to learn the local smoothness of the ground truth is remarkable, it performs comparatively poorly offline datasets,
demonstrate in Figure 5 in Appendix G.2. In this section, we show that AKORN is able to use ADDLE's ss adaptivity while efficiently leveraging offline data. We compare several policies.
Table 1 validates that AKORN achieves the claimed rate of (nn11/3) on spatially heterogenous functions like the Doppler function of (Donoho & Johnstone, 1994).
The final example in Figure represents runs of each policy on the ground truths On [o" E RIXn-5 ,, 2, 4, 5, In this setting, the fast rates for Trend Filtering from (Gun- tuboyina al., 2020) do not apply, because the final lin- ear segment of the ground truth is small. Notice that in this case, TVi [0] = (n)), which means that the rate pre- dicted both by our theory and that of Trend Filtering is Ö(n 2/5 = Ö(n 2/5).. While this rate seems to be accurate for Oracle Trend Filtering, our experimental results seem to indicate that AKORN outperforms this rate substan- tially, as the least-squares slope of the orange line is about 00.7 (Table 1). These results indicate that AKORN's en- hanced adaptivity leads to favorable performance on highly irregular problem instances. Visually, we see that AKORN's proposed model is much more attractive than that of Trend Filtering.
1. Oracle linear trend filtering. We solve the variational problem described in Section A for grid of possible X. We then measure the true MSE against the ground truth, and return the best fit. We emphasize that this policy requires oracle knowledge of the ground truth.
2. DoF linear trend filtering. We solve the same trend filtering optimization problem for the same set of possi- ble A. We then form the Stein estimate of the risk by es- timating the degrees of freedom of each model (Tibshi- rani & Taylor, 2012), and choose the best fit. Note that this procedure has theoretical guarantees, is com- putationally intensive, and can require high-precision arithmetic when the dataset is large.
3. Wavelets. We use the sefttthresholding estimator of (Donoho & Johnstone, 1998) with Debauchies 2 wavelets. To our knowledge, apart from AKORN, this is the only optimal and parameter-free algorithm for estimating TV functions.
In Table 2, we report the MSEs of each policy for fixed and various noise levels From the table, we gather that AKORN is competitive with both Oracle and DoF Trend Filtering, especially for larger values of o. Wavelets is substantially behind all other policies.
4. AKORN. We run AKORN as described in Section 4.2, with failure probability 8 = 0.1.
In summary, AKORN'S performance is very close to both Oracle Trend Filtering and DoF Trend Filtering across all tests, and it outperforms even Oracle Trend Filtering such pathologies as the jump function of Figure 2. Wavelet denoising, which is the only other method we know of that provides adaptivity to [V], is behind the pack empirically. Code is available at github. com/ Suni Saladhow/AKORM,
In Figure 2, we display log-log plot of the error of each policy for various ground truths, against exponentially in- creasing values of n. In Table 1, we report the slope of the lines corresponding to Oracle Trend Filtering and AKORN, as estimated by the Linear Least Squares fit. This gives the approximate rate of each estimator. Across all ground truths, we observe that AKORN competes closely with Trend Fil- tering, despite the fact that the latter is provided with access to the ground truth.
6. Theoretical Results
We begin by confirming that ADDLE achieves the optimal total square error, ((n-/552/5) Note that this implies that the average square error (nearly) matches the optimal rate, Ö(n (4/5///2//5
The first example in Figure 2, together with the first col- umn in Table 1, suggests that AKORN adaptively achieves the parametric rate 1 on piecewise linear functions, as does trend filtering. The second example in Figure and
Theorem 6.1 (Bound on ADDLE error). Consider equally
6

---

AKORN: Adaptive Knots generated Online for RegressioN splines
soddete savelers dcl atom
Maanin
If S24 diocm
10-4
10"4
10
101
1000
2000
3000
4000
5000
2000 4000 3200
where Ô hides constants (including σ) and polylog factors of n and
Let emphasize the message of Theorem 6.2 by comparing it with the standard guarantees of Locally Adaptive Regres- sion Splines and Trend Filtering (Donoho & Johnstone, 1998; Mammen & van de Geer, 1997; Tibshirani, 2014), each of both of which provide an algorithm A, with hyper- parameter so that for any a E R, there exists A(a)) so that Ax(a) (nearly) achieves the minimax rate 2a22/5n 4/5) over {ʃ |Ifllv S Sa).
10" 127
On the other hand, Theorem 6.2 says that AKORN is not only (nearly) minimax over {f TViff S a} in parameter-free way, but it achieves the instance-dependent rate ((VV15512/5 10pmnn4// 4/5) over (s TV1 < <o).
Figure 2. Estimated rates for AKORN and Oracle Trend Filtering formed using 20 Monte-Carlo runs for cach n, together with rep- resentative fits for 5000. = 0.3, 8 0.1. Top left: PW Linear function; Top Right: Doppler function: Bottom: Jump func- tion.
In Appendix F, we describe how a modified version of ADDLE can achieve the same rate (up to log terms) when the covariates {x; /i=1 satisfy max;=2.... [2; 2;-1 I log This condition is satisfied with high probability when Pon
spaced design points {xi)i=1 and any with C [Vilf:Dxl < co. Let responses {yr} come from the model in Equation! 1. Let (ūe)r_ be the the predictions gener- ated by ADDLE when fed the data in isotonic order. With probability - 8, the total squared error satisfies:
2; Px(-), where Px is density with support on [0, 1] that satisfies px (xx 2 Po > 0 for & E [0, 1] (Wang et al., 2014). This implies an optimal variant of AKORN under the same conditions. Detailed theorem statements and proofs can be found Appendix F.
Σ U0 - -
where Ô hides constants (including σ) and polylog factors of n and 8.
7. Proof Sketches
7.1. Proof Sketch of Theorem 6.1
With this result in hand, we are able to prove that the func- tion, f. outputted by AKORN also adaptively achieves the rate of Ö(n C//552/5)
The proof of Theorem 6.1 follows along the lines of (Baby et al., 2021). The crucial component is the following classi- cal Lemma from (Hazan Seshadhri, 2007).
Theorem 6.2 (Bound on AKORN MSE). Consider equally spaced design points, {De t/n]i= and such that C= [V Dx] < co. Let responses {yr} come from the model in Equation! 1. Let f be the function returned by AKORN. Then, with probability 1 - 8, the average square error satisfies:
Proposition 7.1 ((Hazan & Seshadhri, 2007) informal), For any interval I [r, s] in time, the algorithm FLH (Fig.4) with learning rate Ç a applied to the loss func- tions E2(-) = (-- y²)² gives Ologr log (T)) regret against the best base learner in hindsight, where a upper bounds the parameter of exp-concavity for all &.-
2//5
For any fixed partition P of [ni] into intervals, this Lemma

---

AKORN: Adaptive Knots generated Online for RegressioN splines
directly controls the quantity
particular, ADDLE provides not only predictions with small error, but access to a sparse set of change-points that encode optimal bias/variance tradeoff around each covariate.
Σ E(. (0 -2r()) yv))²
P= P-MNEP LEp
The properties established in the Change-point Detection Lemma quickly imply that back-fitting piecewise linear functions on either K or Ks gives the optimal rate. In particular, the smallness of Ky (resp. K₁) allows us to control the variance of Pr(K,) (resp. Pr(k,) Y), while the approximate linearity property allows |B[PP(())Y)] 01 (resp. [[E[PP(K,))] mas C.3, C.4 and C.5 in the Appendix). This certifies that g = PF(K,) and h = PF(K.) have MSE scaling as ((21/5 While y and h are, in general, discontinu- ous (and therefore improper estimates of the ground truth f), we rely on their existence later in the proof. We summarize in the following Lemma:
where (t) is the prediction at time & of an online linear re- gression expert that starts at time r (Specifically, an instance of Algorithm 3 in Appendix B).
Appendix D concerns itself with establishing:
control 011 (Lem-
1. The existence of a partition, P=,,f f into Cn//5 roughly linear chunks, such that Equation (2) is ((1) for each p E P'.
2. A statistical control on the difference between Equation 2 and the corresponding quantity with noisy responses Yr replaced by the ground truth 8, = f(x)).
Lemma 7.3. |Corollary C.6 (informal)] With high proba- bility, we have
One appealing aspect of such proofs is that the heavy lifting is done by approximation theoretic analysis. That is, we can encode oracle knowledge about the structure of f into the partition Pd while proving theorems, and be sure that FLH will discover this structure without any additional algorith- mic input. This type of adaptivity is the core contribution that online learning can make to statistics. The complete proof for ADDLE is in Appendix D
[PP(K 01 ((11/5
and
[P - 0 032
Turning our attention to f= Y. Lemma C.2 provides us with the following bound, which relates the square error of f = PS(K) Y with that of fictitious estimator fy P.(K)
PS(K))
7.2. Proof Sketch of Theorem 6.2
In order to prove the optimality of f= PsCK) Y. we begin by establishing properties about the knotset K. Recall that K K U K, U K, where K3 and Ko, are generated according to the online passes of Algorithm 1. Using the optimality of ADDLE (Theorem 6.1), we can prove the following "Change-poin Detection Lemma," which tells us that K (and K₂) divide f into a small number of piecewise linear chunks.
[[PsK) -01 S 211Pp()) - -112+211 P(()) 0
01 (3)
This is crucial because we are able to cover the space of possible knot sets K in the first term on the right hand side by covering intervals independently. The first term is easily bounded using the methodology of Lemma 7.3. The second term is free from dependence on the responses, Y, and is bounded using the following approximation theoretic lemma, which asserts the existence of a linear spline e S(K, U K2 U K) whose curve lies in between the curves of any two functions g E F(K and h E F(K.).
Lemma 7.2 (Change-point Detection Lemma (Lemma C.I informal)). With high probability, we have
|K S max(21/552/5
Lemma 7.4. [Lemma C.7 (Informal)) If Kyn,, = O then for all g E F(K₁) and h E F(Ks) there exists s E S(K) that for all x: E Dx there exists Xx [0, 1] with
and for all Rf E Ky there is a linear function wi defined [k{ k44 )such that
s(x) = >ug(() + (1-1h (x)))((x))
(z.) - 02)2 S 11++ / 20/
Finally, we apply Lemma 7.4 with g PF(K,) Y and h Pr(K,)Y, in order assert the existence of S(K) with small error. Concretely, by the convexity of square loss, we have in Equation 3
While the adaptivity an online algorithm is typically eval- uated on the basis of its regret bound, the Change-point Detection Lemma tells us that online algorithms are im- plicitly making fairly deep inferences about their data. In
|Ss() 0- 011 < ||s 01 <
lgg 0 2 + |1h
01 = 061 22/5)
8

---

AKORN: Adaptive Knots generated Online for RegressioN splines
in Equation 3. The complete proof for Theorem 6.2 is in Appendix C.
Baby, D. and Wang, Y. Optimal dynamic regret in exp- concave online learning. In Conference Learning The- ory, Proceedings of Machine Learning Research, 2021.
8. Conclusion and Future Work
Baby, D. and Wang. Y. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. 2022.
The main contribution this paper is AKORN, a parameter- free algorithm which uses ideas from online learning to produce a function f that (a) empirically competes with the output of linear Trend Filtering, even when the latter is given oracle access to the ground truth for hyperparameter tuning (b) achieves the optimal rate for TVi-bounded functions by adapting to the local smoothness of f (c) operates by means of a reduction from knot-selection to adaptive online prediction.
Baby, D. and Wang. Y. Second order path variationals in non-stationary online learning. In International Confer- ence on Artificial Intelligence and Statistics, 2023.
Baby, D. and Wang, Y.-.. Adaptive online estimation of
piecewise polynomial trends. In Advances in Neural Information Processing Systems, 2020.
A major limitation of AKORN is that it does not handle higher order TV, classes. An extension arbitrary & would place AKORN on even footing with Trend Filter- ing theoretically. They key challenge here is generalizing Lemma 7.4 to splines of higher degree. Another limitation of AKORN is its (n²)) runtime. We believe that a more careful reduction to a geometric cover version of ADDLE (Baby al., 2021) may lead to an (n log n) algorithm, though in practice this may come the cost of additional MSE.
Baby, D., Zhao, X., and Wang. Y. An optimal reduction of tv-denoising to adaptive online learning. In International Conference on Artificial Intelligence and Statistics, 2021.
Baby, D., Garg. S., Yen, T., Balakrishnan, S., Lipton, Z. C.,, and Wang, Y. Online label shift: Optimal dynamic re- gret meets practical algorithms. In Advances in Neural Information Processing Systems, 2023.
Beygelzimer, A., Langford, J., Li, L., Reyzin, L., and Schapire, R. E. Contextual bandit algorithms with super- vised learning guarantees. In International Conference on Artificial Intelligence and Statistics, volume 15, 2011.
Online methods have long been promising to expand the scope of theory by eliminating assumptions on optimally tuned parameters and enhancing adaptivity to problem in- stances (Cutkosky Orabona, 8; Cutkosky et al., 2023). If, as AKORN suggests, such methods can be modified compete ex-situ with state-of-the-arr offline algorithms, offline-to-onlnee reductions could yield new theorems whose hypotheses are more likely to hold in real-world scenarios.
Cesa-Biancha N. and Lugosi, G. Prediction, learning, and games. Cambridge University Press, 2006. ISBN 978-0- 521-84108-5. doi: 10. 10.100///8998005111500
Chatterjee, S. and Goswami, S. Spatially adaptive online prediction of piecewise regular functions. In International Conference on Algorithmic Learning Theory, 2023.
Acknowledgments
We thank the anonymous reviewers for their thoughtful feedback, which helped improve the clarity and presentation of this paper. This work partially supported by NSF Awards #2 133421 and #2007117.
Chaudhuri, K., Freund, Y., and Hsu, D. J. A parameter-free hedging algorithm. In Advances in Neural Information Processing Systems, 2009.
Cutkosky, A. and Orabona, F. Black-box reductions for parameter-free online learning in banach spaces. Con- ference On Learning Theory, 2018.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Cutkosky, A., Mehta, H., and Orabona, F. Optimal stochas- tic non-smooth non-convex optimization through online- no-non-convex conversion. In International Conference on Machine Learning, 2023.
References
Daniely, A., Gonen, A., and Shalev-Shwartz, S. Strongly adaptive online learning. In International Conference on Machine Learning, 2015.
Baby, D. and Wang, Y. Online forecasting of fotal-variation- bounded sequences. In Advances in Neural Information Processing Systems, 2019.
Donoho, D. and Johnstone. I. Ideal spatial adaptation by wavelet shrinkage. Biometrika, 81(3), 1994.

---

AKORN: Adaptive Knots generated Online for RegressioN splines
Donoho, D. L.. and Johnstone, I. M. Adapting to unknown smoothness via wavelet shrinkage. Journal of the Ameri- can Statistical Association, 90(432), 1995.
Rakhlin, A. and Sridharan, K. Online nonparametric regres-
sion. In Conference on Learning Theory, 2014.
Rhee, W. and Talagrand, M. Uniform bound in the central limit theorem for banach space valued dependent random variables. Journal of Multivariate Analysis, 20(2), 1986.
Donoho, D. L. and Johnstone, I. M. Minimax estimation via wavelet shrinkage. The Annals of Statistics, 1998.
Foster, J., Rakhlin, A., and Sridharan, K. Adaptive online learning. Advances in Neural Information Processing Systems, 2015.
Rosenfeld, E., Ravikumar, P., and Risteski, A. An online learning approach to interpolation and extrapolation in domain generalization. In International Conference on Artificial Intelligence and Statistics, 2022.
Friedman, J. H. Multivariate Adaptive Regression Splines. The Annals of Statistics, 19(1), 1991.
Sadhanala, V. glmgen. URL https: http:/gttthh...ooooo
gimgen/ gimgen/g1mgen glmgen.
Goepp, V., Bouaziz, O., and Nuel, G. Spline regression with automatic knot selection. Computational Statistics Data Analysis, 202, 2025.
Sadhanala, V. and Tibshirani, R. J. Additive models with trend filtering, The Annals of Statistics, 47, 2019.
Sherman, J. and Morrison, W. Adjustment of an inverse matrix corresponding to a change in one element of given matrix. The Annals of Mathematical Statistics, 1950.
Gradu, P., Hazan, E., and Minasyan, E. Adaptive regret for control of time-varying dynamics. In Proceedings of The 5th Annual Learning for Dynamics and Control Conference, 2023.
Streeter, M. J. and McMahan, H. No-regret algorithms for unconstrained online convex optimization. In Advances in Neural Information Processing Systems. 2012.
Guntuboyina, A., Lieu, D., Chatterjee, S., and Sen, B. Adap- tive risk bounds in univariate total variation denoising and trend filtering The Annals of Statistics, 2020.
Tibshirani, R. J. Adaptive piecewise polynomial estimation via trend filtering. The Annals of Statistics, 42(1), 2014.
Hazan, E. and Seshadhri, C. Adaptive algorithms for on- line decision problems. Electron. Colloquium Comput. Complex, TR07-088, 2007.
Tibshirami, R. J. Degrees of freedom and model search. Statistica Sinica, 2015.
Hazan, E. and Seshadhri, for changing environments. Proceedings of the 26th Annual International Conference on Machine Learning, 2009.
C. Efficient learning algorithms
Tibshirani, R. J. Divided differences, falling factorials, and discrete splines: Another look at trend filtering and related problems, 2022.
Hazan, F., Kalai, A., Kale, S., and Agarwal, A. Logarithmic regret algorithms for online convex optimization. 2006.
Tibshirani, R. J. and Taylor, Degrees of freedom in lasso problems. The Annals of Statistics, 40, 2012.
Kim, S.-J., Koh, K., Boyd, S., and Gorinevsky, D. L trend filtering. SIAM review, (1))), 2009.
Wand, M. A comparison of regression spline smoothing procedures. Comput. Stat., 15(4), 2000.
Wang, Y.-X., Smola, A., and Tibshirani, R. The falling facto- rial basis and its statistical applications. In International Conference on Machine Learning, 2014.
Luo, Z. and Wahba, G. Hybrid adaptive splines. Journal of the American Statistical Association, 92(437), 1997.
Mammen, E. and van de Geer, S. Locally adaptive regres- sion splines. The Annals of Statistics, 25, 1997.
Wu, R., Guo, C., Su, Y., and Weinberger, K. Q. Online adap- tation to label distribution shift. In Advances in Neural Information Processing Systems 34: Annual Conference, 2021.
Muller, H.-G. Change-Points in Nonparametric Regression Analysis. The Annals of Statistics, 20(2), 1992.
Orabona, F. Simultaneous model selection and optimization through parameter-free stochastic learning. In Advances in Neural Information Processing System, 2014.
Zhang, K. and Wang, Y.-X. Deep learning meets nonpara- metric regression: Are weight-decayed dnns locally adap- tive? In International Conference on Learning Represen- tations, 2022.
Parhi, R. and Nowak, R. D. Banach space representer the- orems for neural networks and ridge splines. Journal of Machine Learning Research, 22(43), 2021.
10

---

AKORN: Adaptive Knots generated Online for RegressioN splines
1. For 1...T
(a) Player plays action E V
(b) Universe chooses a loss function f+
(c) Player suffers loss (z)
Figure 3. Online interaction protocol
A. More Background on Related Work
One solution to the non-parane non-parametric problem of Equation is given by k-th order trend filtering (Kim al., 2009; Tibshirani, 2014), which efficiently solves the minimization problem
fez arg min
Σ (u s(x,))² + XTVx(o)
(4)
gEU
where U is the span of a certain collection of functions called the falling factorial basis functions (Wang et al., 2014;
Tibshirani, 2022). For ( ari3 C (2k-11
the loss of fis satisfies
n - = =Op(n (25+3) CariT
(2k-2)
where C is an upper bound on (V)()), which is known to be the minimax-optimal rate. Crucially, in order to benefit from tight bounds, a practitioner would need to choose À with knowledge of the smoothness of the the ground truth, f. Said another way, Trend Filtering optimal only over the class functions F&(C)) = [ʃ (V) S C} and requires knowledge of C. For comprehensive treatment of the theory underlying Trend Filtering, which the state of the art solution for regression over TV, classes, refer the reader to (Tibshirani, 2022).
Regression over non-parametric classes is much broader field, with well-developed theory of minimaxity (Donoho & Johnstone, 1994; Mammen & van de Geer, 1997; Rakhlin & Sridharan, 2014; Tibshirani, 2014; Baby & Wang, 2019). In particular, (Rakhlin & Sridharan, 2014) observes that the complexity of the online problem typically does not differ too much from that the offline problem.
TV, function classes admit functions whose smoothness varies spatially, which makes the estimation problem especially challenging. While Holder Sobolev functions can be optimally estimated by linear smoothers, optimal estimators for TV, must display local adaptivity to the smoothness of the ground truth (Muller, 1992; Donoho & Johnstone, 1994; Mammen & van de Geer, 1997; Tibshirani, 2014).
A.1. Online learning
Online learning studies algorithms for playing the game in Figure 3.
The goal is to choose actions such that the cumulative loss is small (with respect to some comparator). This setting is entirely non-stochastic, and we therefore measure an algorithm's 's performance in terms of the regret of its predictions against a comparator:
Regret(21,....2 = (f((2) - f((u))
1=1
If we let fe(-) (.- ? have stochastic relaxation of the adversarial setting. When specialized to stochastic/batch settings, OL algorithms often enjoy remarkable adaptivity to problem features (Orabona, 2014; Baby et al., 2021; Wu et al., 2021; Cutkosky et al., 2023). In our setting, particularly relevant is the Aligator algorithm (Baby et al., 2021). which addresses online nonparametric denoising over TV by using an expert aggregation algorithm to adaptively select the best window in which to perform averaging for each Vg. For i = 0, Aligator's 's predictions incur the optimal error of (/1//3

---

AKORN: Adaptive Knots generated Online for RegressioN splines
Central our work is the theory of adaptivity in OL (Hazan & Seshadhri, 2009; Daniely al., 2015), which seeks guarantee that the regret within each interval is small with respect some set of comparators. In particular, will make use of the Sellow-te--Leadin--- property that, in any interval, the aggregate prediction competes with each individual expert.
expert aggregation algorithm from (Hazan et al., 2006), which has the remarkable
Online forecasting over TVg-bounded sequences has also been addressed for = 0, in the fully adversarial setting in a sequence papers by (Baby& Wang, 2021; Baby et al., 2021; Baby Wang, 2023).
More broadly, it widely believed that hyperparameters, which can typically only be tuned heuristically, are responsible for large gaps between learning theory and practice across the entire discipline of Machine Learning (Chaudhuri et al., 2009). This has led to growing movement design parameter-free algorithms, whose theoretical guarantees reasonably be expected to hold in real-world scenarios (Cutkosky & Orabona, 201 8; Chaudhuri et al., 2009; Orabona, 2014).
B. Algorithm descriptions
The following algorithm, due to Hazan & Seshadhri (2007), called Maalhe-LLedign-iiiieeee (FLH). ADDLE operates by running FLH with online linear regression experts.
FLH: inputs Learning rate and n base learners E* ,..., E"
1. For each 1s (v," (1)
(t) is probability vector in R., Initialize of
2. In round set Vj t, o E (t) (the prediction of the jth bas learner at time t). Play
#t = Ej= U/ 10))))))
(f+1) 0 and perform update for 1 Sii t: 3. After receiving /t, set 121
U1 (1) Sf
(5)
41
Σj= u/ (fCii(a)))
4. Addition step Set ut1
(++1)
to 1/(t + 1) and for t 1:
( u+ (1 + 10!
(6)
Figure 4. FLH algorithm (copied verbatim from (Baby & Wang, 2021))
In the course of the paper, we will make references to both bounded linear regression experts and unbounded linear regression experts, described in Algorithms 3 and 4 respectively.
Algorithm 5 gives the full description of ADDLE, which technically requires to the bounded linear regression expert.
Algorithm 3 Bounded Linear Regression Expert
Input: history C (X x [0, 1))", feature æ, bound B (Generates B B-bounded prediction given history H.)
if H is empty then
Output
else if H. = [x }} then
Output [- [=A.,) clips real number between and B)
else
i linear least squares on H
Output [[.)
end if
12

---

AKORN: Adaptive Knots generated Online for RegressioN splines
Algorithm 4 Linear regression expert
Input: history H C (X's x [0, 1I)", feature x GGeneaaes prediction given history }}
if H. is empty then
Output
else if' H. { (a11 }} then
Output v/
else
+ linear least squares fit on H
Output ((x)
end
Algorithm 5 ADDLE
input D. a
B é max; lys| + / 4n/6,
Run FLH with learning rate 1) 8(1+o 210g2//822
base learners E F² (t) =Predict (((Fk, yk Wi Rz, B)
C. Proofs for AKORN
C.1. Properties of Knot Selection
For fixed, and some interval 1 = [r, s] C [m]. we introduce the notation (V) (0 a))] we prove that Algorithm induces not-too-large partition of f into roughly linear segments.
In the following lemma,
Lemma C.1 (Compare to Theorem 18 (Baby et al., 2023)), Consider the set of knots, Ko (ki,...k,, ki41 == In+th outputted by Algorithm I when exposed data isotonically, as well as the induced partition
p = {p- = k 1]]ie [1]
Let n4 be the size pi.
Then, for any 8 > O, there is an event (8) which holds with probability at least and upon which
IP| S max(n 22/5
and
Vi 3 w" linear
(ww(xe)) - -01) -,,)2251 211 n. 1/5
(V:
tEPx
where S hides constants and polylog factors of 6,
Proof. We follow the methodology of Theorem 18 from (Baby et al., 2023). Suppose that for time i, line the condition inside the if-statement of Algorithm is executing for the ith time. We start by bounding C2 == TV ([b,t))) t)).
Σ j=b+1
(1f - -0,² < Σ (10) - Bloa]] + E[wi']
03 + 0, - 0,)
1=b+1
<
Σ (wi) - B
(E[vof) - 0,) +4 Σ (0, - 02
-=b+1
-=
j=b+1
By Lemma C.10. the first term bounded by 4o log (1/8) with probability 1-6 8. The second term bounded by C2 /n?. which can be shown by direct computation, in Appendix E. By Theorem D.1 (Optimality of ADDLE), the final term is bounded (with probability 1 - 5) by un; ////////5 combining this with the condition inside the if statement, we see that with probability 1 we have:
3/5 2/5 2/5 where i contains constants and log- factorss Union bounding and then
13

---

AKORN: Adaptive Knots generated Online for RegressioN splines
4o log (4/8) + +4 max 2/5 3/5 "i /n Cnn 2 50 log 4/6
(8)
Regardless of which value the maximum takes, we conclude that
C₁ 2 n/n 2/2
(9)
At the same time, on this same event, we have by definition that
Σ
(wj) 0²) 2 Σ (1i))) 0x) +2 Σ (0, 0,) 11 m C 5=b+1
j=b+1
5=
We may now cover all n² possible intervals, which amounts adding an n² in the log and yields (6).
Now let M 1 be the total number of times that the if-block is executed. So M |P] is the number of bins spawned.
Returning to Equation 9, Jensen's 's inequality with @ + x
3/2 -322 gives
M M-1
Σ
C
3/2
M-
1
n (M - 1)3 (M -1) 1)
M-1
2 Φ
n2
n (M- - 1
i=1
2 66n (M - 1) = (M - /n²
So for M >> 1, we have
P = M M -
C.2. Introducing the fictitious estimator: Ps(K)Y Y versus PF(K)Y
In our analysis, it is necessary introduce fictitious estimator that conducts independent fits within each partition. This will allow to cover knot-sets more efficiently. The following lemma relates the error of f to the fictitious estimator, fy- Recall the definitions of F(K) and S(K) for knotsets K from Section 3.2. Note that, in the following lemma, we abuse notation by identifying f with (f..)),... (and likewise for fy), which allows us use the notation (s) for (H (=) -R) OxO = Eo [f() for fixed K.
[1, (= - x1) +1)+,919 99,, (=), 99,,
Lemma C.2. Let K = ( be (possibly random) set of knot points in the data, and Y be the vector of responses.
Let F(K) be the subspace vectors in R" representable as evaluations piecewise- functions with optional disconti- muities at points K. Let S(K) be the subspace of vectors in R" representable as evaluations (on the data) of linear splines with knots in K. Let P(g be the projection map. Now consider the following two estimators:
1. fy is the fictitious estimator, whose predictions are given by:
(f((a)).. P
14

---

AKORN: Adaptive Knots generated Online for RegressioN splines
2. f is AKORN's output, whose predictions are given by:
(((n))-- = Ps( Y
Then the following holds deterministically
( 2 (z)) - -2 Σ
((x))) - f(x:))
==1
Proof. We abuse notation by letting == (fx)), (zx,) and f (f (x.)),...f(t [x(n) and suppressing the dependence of the spaces S(K) and ((K) on K. Now, with || 112. we obtain
Ilfy f [PPaff Psfl PPsPpPY Psfl
|PsY - Psf Pslll ž Ill ffl -| fill
Psfll
Where the first inequality is because projections are contractions, the second equality is because S C F. By the reverse triangle inequality, we obtain
Thus
If f 1f, I flll
C.3. Analysis for Piecewise Linear Estimates: [P
01
For any random knot-set K,, we now analyze the quality of the fit PF(K.) Y. This is necessary in two parts of our proof: for providing certificates g and h to be plugged into Lemma C.7 (with Kr Ky and K, K₁ respectively) and for bounding the error of the fictitious estimator Lemma C.2 (with K, K K U Ko U K).
The next Lemma gives bias- variance decomposition of [|Pr(K,) 012..
Lemma C.3. There exists event Eo(5) which holds with probability least 1 upon which the following holds for all knot-sets K, {k1 (..,, k141 = n} with their associated fit fy PF(KK)Y
ks+1
n
- f(x)))
(f(a.) -mo²2
Σ of log
()))))
where h4 and of are the mean and variance of (xt) respectively, treating the knots as fixed.
Proof. Begin by fixing static interval p; [R;, ki41 1). Further, fix some t Pi- For any vector RP, let g² [gn, ....... 1 FT. Let X; collect only the covariates in pt. Now note that
f((x)) = x. (xxx7)--xxx) (N),,
where Mr = (2e,
and of - o2 (X;Xf) -tx..
Thus, letting We fx( ae
we have that
Pr||Wa| 22 (2n/8) > -8/n
Or equivalently
Pr(]ff(*t)= - 144 S of 2 (2m/5) > 6/n
(10)
15

---

AKORN: Adaptive Knots generated Online for RegressioN splines
By reverse triangle inequality,
(ml=))-l=11p)) (f(())) 02 -mz --000 1fs(2re) 0c)l 1 Ozl
So that Equation (10) implies
1f(x))) 0gl 1pr Ozl + oz serv2lou log (2n²/5)
holds with probability at least - 8/n
Squaring each side and summing (and union bounding) over from k; to k241 1, this implies that with probability
1 8/n²:
k141 -1
k141-1
k4--11
2n
Σ (f(x)) -0)= 2
Σ
(x- +4
(m
Σ
0f log(
t=
t=k;
t=k:
where we have used (a + 6)2 < 2a² + 22b
To finish, cover all n realizations of p:. This means that with probability - for all ki, k541
k
2n
(1))) Σ (m -4-- ((xe)) +4
Σ
o log(
In particular, we have the claimed decomposition for all K,.
We elaborate on the bias and variance terms in the following two lemmas.
Lemma C.4. |Variance of PF(K.)Y] Within the setting of Lemma C.3, we have that for each kiş E K2
k
2T oi log
))
s o²
Proof.
R141
k++111
Σ of
(X,X7))- "4 = 20²
t=ki
t=
because the sum of the leverage scores is the number of parameters in the model.
For K, = Kg a knot-set from Lemma C.I (on either a forward or backward pass), we have a control on the total bias of P.(Ko)Y. Lemma C.5. [Bias] setting of Lemma C. we have the following on the good event & (8):
[P 0
((22//82/5)
Proof. Lemma C.1's success event guarantees that there is vector 17 E F(Ko) with
|| 0
D2 2/5
n
S 1+
n
| 2/5
3/5
16

---

AKORN: Adaptive Knots generated Online for RegressioN splines
Now using Holder's inequality with the dual norm pair (5/3, 5/2), we obtain
2/5 3/5 1
1 2/5 n4) n4)3/5 S 11 n2/5 S C22
An application of the previous three lemmas shows that Pr(K)) Y has small error for Kn coming from the knot selection algorithm (i.c. both with Ko = y and Ko = Kt).
Corollary C.6. Let 66(6/2) be the good event from Lemma C.3 and {8/2) be the good event from Lemma C.I. Then on Eo( E we have
||PE(K) 01l2
Proof.
On E0(//2 we have
k4t1
k+4-11
[| - 0112 (fx)))) [(x)))
x
(f(x.) - -ue)
Σ of logl t=ki
t=ki
On the event (6//2 from Lemma C.5 we can bound the bias term by O(nnn'(('')) On this same event, can bound the variance term by 0n C22/) by Lemma C.4.
C.4. Spline Existence
Lemma C.7. Suppose ((K)) and h E F(Ko) for Ky n nKKK 0]. Let KK UK where K contains all the
crossover points between gg and h. Then there exists S(K) such that for all x E [0, 1] there exists d2 E [0, 1) such that
f(x) = >=)(T) + (1 - )2)h(z)
(11)
The idea behind the proof is simple. We construct a linear spline left-to-right that greedily sticks with whichever function of g and is furthest from a change point, transitioning linearly between the two necessary. We must include crossover points in order to ensure do not exit the region between the curves g and h when perform "slide" from one the other.
Proof. Assume K = ki,...k is ordered. Let k4+1 1 for convenience.
We prove a stronger result, where we enforce the following additional requirements at each knot k;
1. f(k)) = g(k;) or f(k;) = (kks))
2. If E [ 1] is such that ky E K and ki+1 Ky, we have that f(kx) h((k)).
3. If E [[ - 1] is such that K; e K and k41 E Ko. we have that f(k.) = g(k:).
We construct f in cases while iterating over knots.
Base case: If l E Ky, let f(2) = h22) for 2 E [0, k1]. If h2 E K2, let f(2) = g(2) for 2 E [0, If kr E K, then let f(=) = (=) for z [0, ki) 22 E K₁ and f(=) = h(=) for z E [0, ki] k2 Ky.
"Inductive" step: Assume that (f [0, k + R) E S(k),..,, ...) constructed such that the above requirements are satisfied for all knots 1 We now extend f to (f [0, k,] + R) E S(ki,,..k:))
Case 0: f(k=1) = g(k-1) and - is the last knot (i - 1= =1)
We can extend f to [0, 1-1 = [0, 1] by letting f() g(2) for z E [k k.). Because is linear on 1 f is in S(K). Equation holds by construction, and requirements 1, 2 and all hold by our iterative hypothesis.
Case 1: f(k=1)) = -(k-1) and k; E K₁
17

---

AKORN: Adaptive Knots generated Online for RegressioN splines
Extend by letting [2) g(z) for all [k-1, k.]. Because g is linear on [ki_1; Ais and g(ki-1) ((k-1)), we still have that f ((ll). We also have f(z) = g(2) for all E [ ks) and f(k) g(k.).
Case 2: f(k;-1) = (k and K; E K
Extend f by letting f(z) g(z) + (h(=) - ((2)) for [ By construction, we are also assured that kG-1 K (because otherwise we would have (k;-1) = h(k;-1)). Because g and h do not cross on the interval [K--1, ki]. have that f is in S(Kk,, k;]) and satisfies Equation 11 (with restricted to [0, k,] U k,).,, By construction,
also have that f((k;) h(k:) (satisfying requirement 1). By our inductive hypothesis, the extended version of satisfies requirements 2 and 3.
Case 3: f(k;-1) = 1 and & E K and k++1 E K2 U [kt+1]
kt]. Because g is linear on [k), we still have that f (((k....))))) We also have f(22 (2) for all [k--1, ki] and f(k)) = (k.) h(k:).
Define f()) g(2) for all 2 E [k:-1,
Further, by construction we have that requirements and hold after extension. By hypothesis, requirement 2 still holds.
Case 4: f(k;-1) = 1k and K; E K and ki+1 E K
ks]. Because h; K, we know that g and h do not cross the interval [k; k; Because g and & do not cross on the interval [k;-1,;;] k;,, we have that f satisfies Equation 11 (with x restricted to [0, kx] U [kg-1, k.).
Define f()) g(2) (h(z) s(=)) بامي for [kg-1Ass]:
k
Furthermore, by construction, requirements and 2 hold after extension. By hypothesis, requirement 3 still holds.
The remaining cases symmetric to the above ones (i.e. the orders of and h and Ky and K₁ are flipped). We can iterate this scheme left-to-right over all knots k E K to prove the result.
Generally speaking, the odds of K and K2 sharing knots when generated according to AKORN not high. However, the following corollary shows that can handle this case should it occur.
Corollary C.8. Suppose g E F(K)) and h E F(K)), with K2 n KG + (.. Let Ky U Kg U K UUQ where
Q = [ri-1 Iy E KG n } and K is the set of crossover points of and h. Then there exists & E S(K) such that for all x [0, 1] there exists x2 E [0, 1] such that
xx) = ==)==>o(1)) + (11-x))M(z)
(12)
Proof. Let Q Dog be ordered. On each interval ( 1] we may construct a corresponding linear spline st using Lemma C.7. We then construct by linearly interpolating between the various s; using the knots in Q.
C.5. Proof of Theorem 6.2
Theorem C.9 (Theorem 6.2).
Proof. Let f f. f. Let (6/2) be the event from Lemma C.3. On Eo(6/2), the following holds for all knot-sets K ki), with P[E)] 2 - 5/2.
n
ff(z) f(x1)) < Σ (f((z) + Σ (((x))(a)))(()))
-1
n
(
of((6) + Σ (
1411-
1
Σ
(f(x)) -
Elfr -(ft)
20 Σ
(pst ((x)))
(13)
k
18

---

AKORN: Adaptive Knots generated Online for RegressioN splines
where the first line holds deterministically by Lemma C.2, the second line holds the event & from Lemma C.3, and the third line holds by Corollary C.4.
Now, let y and K2 be the random knot-sets from isotonic and reverse isotonic runs of Algorithm and let K = KJUK,KK. Let E (6/4) be the event from Lemma C.1 applied to the forward run of AKORN. By the conclusion of Lemma C.I, we have KKyl = O(n ((//5)) By corollary C.5, we also have |I - Pr(ky) fl2 & / on E (6/4). Similarly, we let (6 ( /4) be the event from Lemma C. applied to the backward run of AKORN, upon which we have [&b]
on E (6/4) and ||s PF(Ks)/lB
Let E Ef n Eg. By union bound, Pr(Ei] 2 1 - 6/2. On Ei. we may bound the first term in Equation 13 as
Ra-1
ΣΣ
E
E[fr(x)))) ((la))B(f((x))))) (f(z))
Ilf PF(R)) llf PFIK) -0
because F(K)) C F(K)
and the second term as 20 < (4 [K] = (2/5)
All that remains to bound the final term of Equation 13. To do this, first define &g = Eo n &g. By construction, all the previous bounds still hold on Es, and we have Pr[Ea] > 1 8 (by a union bound). Now apply Lemma C.7 g PF(K,) Y and PF(K,) Y get function S(K) that lies in between g and h for all E [0, 1] (i.e. s(x,) (x))( + de. )x(,,) for dz. [0, 1J.. Using convexity of square loss and the bounds the error of g and h from the previous paragraph, we have
n
|Ps(K)] f1 ||s f112
Σ
g(a)) + (1 (M))))))) fxx)))
Am. ((x))) + Σ (h(x)))) (() ==1
Where the inequality holds by convexity of foloss and the final bound holds on &3 due to Lemma C.6, which guarantees small error for and h on & E c E3 and & n c &3 respectively.
C.6. Helper Lemmas
Lemma C.10. (Simplification of Lemma 4 from (Rhee & Talagrand, 1986)] Let ~ N(0, E). Then
Pr|] 2 fl S exp 2tr(E)
D. Proofs for ADDLE
The proof's in this section represent fairly straightforward extensions of those found in (Baby et al., 2021).
We will prove the following theorem. If N = n., then Theorem D.I becomes Theorem 6.1.
Theorem D.1. Consider equally spaced design points, {a+ = 1/n)ety for p 2 and p + N S n. Let
C = TV1 [[(e,,te,) Let (er) be the the predictions generated by Algorithm 5 when fed these data in order. With probability 1- 8, the total squared error satisfies:
Emh Ö(N (n2/
where Ô hides constants (including a) and polylog factors of n and
19

---

AKORN: Adaptive Knots generated Online for RegressioN splines
Proof Sketch: The proof of the bound for ADDLE in Theorem 6.1 follows along the same lines as the proof of Aligator in (Baby et al., 2021). The idea is that, for any there exists not-too-large partition of {21:-...fx)] } into intervals such that is approximately linear within each interval (as measured by TV)). On each of these intervals, the linear expert who starts at the beginning of the interval achieves low error. Furthermore, by the adaptivity property of FLH (Proposition D.2 below), ADDLE competes with the best expert on each interval. Thus, summing over intervals, we observe that ADDLE achieves the optimal rate.
Beginning of formal proof
The main tool is the following lemma, which states that FLH competes with each expert in each interval.
Proposition D.2 ((Hazan & Seshadhri, 2007)). Suppose the loss functions are exp-concave with parameter a. For any interval I = [r in time, the algorithm FLH Fig.4 with learning rale Ç = a gives O( ((ogr llog [T)) regret against the base learner in hindsight.
The following lemma follows instantly from a subgaussian tail bound and union bound.
Lemma D.3 (Lemma 16 from (Baby et al., 2021)). Let V be the event that [ee] S a / log 4n/ō. Then Pr[V] 8/2
Note that, conditioned on V, the quantity B from Algorithm 5 upper bounds 0, for all 6.
Define the filtration F, = (y1. and let E,1-1 = B[-155] and Vary[:] = Var[-
Let D/ be ADDLE's prediction at time t. Let 2 be the prediction at time t of the linear expert that starts at time r. Let
R2 = 16(1 + a /ooloo 4m/5)². Let ē max / log 4m/5, 1}.
The following Lemma ensures that B, as defined in Algorithm is an upper-bound on f Lemma D.4. Let B max; |y + ö. On the event V, we have that [f(x:)] s S + 26 for every E [n]]
Proof. On V, we have that, for any i, 9: E (f(x;) - ã, f(x;) + (ō). Therefore, B 2 Wual + Z If(x:)).
Also,
BSS max; Ind + ō S
1 + 26.
Lemma D.5. Let I = [r, s] be any interval. On the event V, the predictions ús made by ADDLE satisfy:
2 log n
-0,--1) - v1) S Σ (2j
- -2²)² +
R.
/=r
j=r
Proof. On the event V. each loss function (.- R² = n exp-concave.
Now apply Lemma D.2 and bound r, S
The following Lemma is proved as Lemma 18 in (Baby et al., 2021), recalling that | | - 0,1
s 2(1 +
Lemma D.6. For any j E [n], we have
1. E,((y, 22)² - (u, -| - 0,)3(V]
2. Vary[(y; x²)) -w,,-,,,,,, 0,)3 Rs E, - -0)) 0,)
-
Lemma D.7. (Freedman type inequality, (Beygelzimer et al., 2011)) For any real valued martingale difference sequence {ZiTT with Z,| < R it holds that,
R Rog (1/8)
Σ Z. S n(e 2) Σ Var, [Zi]
(14)
7
with probability atleast for all n E 10.
20

---

AKORN: Adaptive Knots generated Online for RegressioN splines
We these Lemmas to define and bound two Martingale Difference Sequences (MDS). Again, compare Lemma 19 in (Baby et al., 2021).
Lemma D.8. Condition on V. For any interval [r, it holds with probability at least 1 - 8 that
1. (y- 2 (w; -0²² < (e 1) 0,)² R2 log 4/6,
2. (y=
(3, - 0,)² - -w, -, 2 (3 c) (0)
0,)² -
R² log 4/6.
Proof. We continue to condition on V. By Lemma D.6, Z, == (2) y,) (y/ 0,)2 (2) - 0,)² 00)==220 30f==;;f0 [2, 8,) is an
MDS. Note that, because of the truncation step, 17 [ - (.) va)1 S 2(2B)² s + (11+28) R.
By Lemma D.7 with 1) Rs
therefore obtain
1
Σ jmr
[e3 1-),))) (3) - 0,)² (2) - 0 $ (e - 2) 1 (2j - 0₁)² + R log
8
with probability 8. We obtain the second inequality by an identical argument with the MDS
i0 - 0,)² (0) 0,)² - (0) y²)
Union bounding over and gives the result.
Now, note that by Lemma D.5, we have that
log Rs
Σ (0, - w,)² (y5 -0, s [ej - 21)² - (y) - -0,) + j=r
j=r
So that, by Lemma D.8
4 - 505
4
2 2
Ug 0,)
R3 log
(0s 0;) (u, (,)= < 2 (2) 0,)² + R2 log
R.
j=r
which (for fixed r, s) leads to the following high-probability relation:
' - (o)- 1)
Σ (2) 0,) 2R² log 4/6 + 2logn/R, R,
Let's union bound over the n² possibilities for r, to get that, with probability 1 - 8 for all intervals [r, s]
Σ -Ú ~,) (e 1) 0,) + 2R log 4n²/5 / + 2 logn/R. n/R. Ra
(15)
(3
Since we're conditioning on V. observe that, if df PPrdiic(f2z, 31 2,} is the prediction from hypothetical unbounded linear expert (Algorithm 4), (27 03)² < (10) 10--01 0,)2. Thus, from this point forward, we consider w instead of 27.
Now, noting that (for > + 1) 05 ~ Nws.. 222 (X )æy), we have by direct computation (Lemma E.2 in
Appendix E)
21

---

AKORN: Adaptive Knots generated Online for RegressioN splines
Σ (aj - 0,) 1=
$30 30 log 2n/ log en
Σ (w) 8
5=++2
Plugging this result into Equation 15, we summarize in the following lemma.
Lemma D.9. Condition on V. Within this conditioning, With probability 1 - -8/2, the following bound holds over all intervals s]
(0 5 0(1+
Σ (w]-0;) 02, + +33) j=++2
j=r
where O() hides only constants, well as log factors of and 6, and where the sum is considered to be zero if S r 1.
We also uncondition V, and union bound over v and V VnG C where C is the good event from Lemma D.9
Lemma D.10. With probability 1 1 5, the following bound holds over all intervals (r, s]
' 0,) 1099000 O(1+ Σ (wg (w5--)) - 0,) +
j=r
j=r+2
where (-) hides only constants, as well as log factors of n and 8, and where the sum is considered to be zero if S r
As compute in Appendix E (Equation 16 Lemma E.2), 2j of = Ó(). By Lemma E.I we obtain Σj 2
(V Ir) s|²/n² for equally spaced {2, = j This leads the follow lemma.
Lemma D.11. Lef |n 1, U (1r, T++1 - 11} U [ri-1.7 be any partition of [m] into contiguous intervals with r + 1. Lef n, ri+1 r3 be the length of the ith interval, and TV1(0) = TV1 (0(r ri-1 - 1]) Then, with
probability 1 - 6:
5 (TV(())22)2)) + +))
Now consider the partitioning scheme that scans left to right from to p + N, and adds points to the current bin so long as TVi (0(curret bin))= current bin 3/2 It follows immediately that, the TV1 inside each bin satisfies TVi < n² n2ii 3i This is analagous to the TV, case from (Baby et al., 2021). As can be seen in Lemma 23 in (Baby & WWang, 2020), the total number of bins in this partition is bounded by ((N3/5 /n22/5). Thus, letting P be this partition, Lemma D.11 becomes Theorem D.I.
a
E. Some missing computations
Lemma E.1 (Bias of linear regression). Suppose T1, sorted covariates such that max (z) Z3-1) S log n/ (pon) for some constant po 0. Let 0,- := f(zz), so that our data is {zz,, ) Further, consider some subset [1 0,)) Let i(z) + bæ be the linear least squares fit trained on this subset. Then the error of i is bounded as
Σ (((m)) 0:)² ( 21)2log" n/ (păn²)
In the special case where 2, i/n 1,.... n, we have
N
Σ ((xx)) - 0,)2 s N0TV :N])2/n2
Proof. WLOG suppose r
22

---

AKORN: Adaptive Knots generated Online for RegressioN splines
Define a to be equal to 01 and b be + E== 8y, where for j > 1 we let 83 --
o, 05-0z-1 be the slope from the datapoint
j - 1 to j. We then have
N
Σ
(a + bz; 0,)²
(1)
Σ
+ b(r; 221) - 01 Σ
sk(Tx 1))1
k=2
N
6
(kk- Ik-1) Σ (2k - xk-1)sk)
81x x))²
5k)) 2
(okk xk-
i=
k=2
k=
N
N Nlog* n
NTV1 NJ)² x
pîn
< (01:: x lo xlogn?/<rmn?
(1) holds because à, b minimize square loss among linear functions. (2) holds because for any vector IR4 have Σd
=)² < Vo))), where = >/ 2/d. This fact is applied with 2ÿ 8j for j I,,,, which leads TVo(2) = TV: N)).
(=1)] (2|1]
The equal-spacing case follows from an identical argument where (ax 1x-1) is instead set to 1 n2
Lemma E.2 (Running variance for ADDLE). Consider a set of covariates, {x, = t/n)izz, and responses {y f(x.) )- For any interval [a, bj C [1, m| with length > 2, consider &, to be the prediction of online linear regression (Algorithm at time t after starting at time a. Let 2 E[ Then with probability 8
2n (2 - =2)² s 20 log
log en + o² log 2/8
8
tma
Proof. Without loss of generality let [a, 6) = [1, Start by fixing t E [3,1-12 Let X, 22xt have columns {[x, H
2+41 2441 = 2T, (x,x7) X,( - 0) ~ N' xI, (xxx,) 2141)
Letting of = =02241 (Xxx?) -1 11441 and applying gaussian tail bound, obtain:
Pr[lér41 2+11 < oz 2og 2m/0 2 1 - 5/n
So that
Squaring each side, then union bounding over t E [3, l and summing up, we have that, with probability 1 1-6 8:
(841 241)² < 20 log (2n/8)
Σ o (X,X?) 1x
(16)
Thus, we need to analyze the "out-of-sample leverage scores". Observe that (X,XF) is given by:
23

---

AKORN: Adaptive Knots generated Online for RegressioN splines
(x,x))--=
-= 2 i= x
Σ, (2 - x)2
i=1
If we assume equally spaced points with pairwise distance 1 1/n, we can compute
n (t + 1) 1) [-(e+ -1(1+1)/+)
-t(t + 11/22m ut+ 1)(1 + 1)/6n²
[n?/t(t + +1((t-) -1) -1) -n/2((1-1)
-n/2t(t - 1)
(21+ 1)/6((1 1)]
So that
" Z10441 1)
n²
(t+ 1) 21(1
2t +
2t +
1 1
n²
x
1(1 + 1)(1 -
22
1)
+
6(t 1)t
6t 1
x
7
Thus, using Ei=1 S logn + log(en) when we plug in to Equation 16, we are left with:
(B++1 2141)² s 20 log (2n/6) log en
(17)
To finish, recall that for which will yield a (0, o²) summand, which can be bounded with high probability. We tack these terms onto the above display after a union bound.
t 1, online regression predicts 0 deterministically, that & - 0. For t = 2, it predicts y
F. Uneven and Random Covariates
F1. Theorem statements for uneven covariates
In this section, we explain how ADDLE can be generalized to handle the case of uneven covariates. These proofs rely on minor algorithmic change: We replace each clipped online linear regression expert of Figure 4 by a clipped Vovk- (VAW) forcaster with the same start-point (see (Baby & Wang, 2020; Cesa-Bianchi & Lugosi, 2006) for descriptions of the VAW forcaster).
We show how to prove the following generalization of Theorems 6.1
Theorem F.1. For some po > O, consider sorted design points 0 S Z1, S 1 such that max |z, - x--1| I log n
pou Let f be function with C TViff. Dxl, and consider responses {ya} } coming from the regression model. Let {ūe /7 be the the predictions generated by ADDLE, now with (clipped) VAW forcasters as experts. With probability 1 - 6, the total squared error satisfies:
Σ -0())))
0(n2/5
where Ô hides constants (including σ) and polylog factors of n and 6.
This leads directly to the corresponding generalization of Theorem 6.2.
Theorem F2. For some po > 0, consider sorted design points 0 S #1,... S 1 such that maxj-2.... (ar, 1J S log n
pon
Let f be a function with C [f. Dx], and consider responses {yr} coming from the regression model. Let of be the function returned by AKORN. Then, with probability 1 the average square error satisfies:
1 - f(xx)) = =On Onnnn(((nnn 4/5 22/5)
where Ô hides constants (including a) and polylog factors of n and 8.
24

---

AKORN: Adaptive Knots generated Online for RegressioN splines
F.2. Proof steps for Theorem's F.1 and F.2
Steps for Theorem F.1
We now consider starting at time r for each [n]] This is very minor change from the original linear regression experts, and does not affect computational or statistical efficiency. The VAW expert starting at r is fed data Dr. == fashion, and produces estimates vi,,,...0
experts clipped linear Vovk-Azoury- (VAW) forecasters (Cesa-Biandee & Lugosi, 2006))
in an online
Notice that, even with these changes to our setting, we can run the proof of Appendix D up until Equation (15), where now 23 is the clipped VAW expert that starts at time r. We can still replace this expert with a hypothetical unclipped expert, viz.
By Lemma 24 of (Baby & Wang, 2020), we have:
(0,--077 (0.- + 1u112 Õ(1)
j=P
where (x:) = wFxx, x; the offline linear least squares estimate trained on noiseless data (x,, j= r,...s From Corollary 40 (Baby& & Wang. 2020), we have ||u||2 O(1). By Lemma E.1 we have that the first term is bounded by |r TVi >))²/n²
Plugging this argument into Equation (15), we recover Lemma D.11's statement that, with high probability, for any partition [T,, -111-11
p = Pt with
100 - 0,)² = 2 (TV())nn//2+))) +1)
(0s
To complete the proof, we may now construct the oracle partition in the same way as before, where TV1 of a bin is computed with respect to realized covariate spacing.
Steps for Theorem F.2
All of the spline approximation results of Appendix C go through without technical changes. Now that ADDLE has been generalized to the uneven covariate setting, Lemma C.I. also goes through by an application of Lemma E.1 to the bias of the linear fits à, (concentration is not an issue, as we still have Σド= 2² (XXT)=2 -2a; = 20
F.3. Theorem for random covariates
First, we cite result that tells us that draws are roughly evenly spaced when they come from a distribution whose density is bounded below on [0, 1]. We do not have control over the probability of the good event in this lemma.
Lemma F3 (Lemma 5 of (Wang et al., 2014)). Suppose is a pdf with support in [o, 1] and such that p(x) 2 Po > O. Let II,...T be a sorted list of iid draws from Then, with probability at least 2pon 10, the maximum gap between two draws satisfies
clogn n por
max
[ I;-1| s>1
where e is a universal constant.
By including the bad event of Lemma F.3 in a union bound, we have the following corollary of Theorem F.1. Notice that now, [V ; Dx] is a random variable depending on the sampled covariates. In the special case where f is differentiable, then [f; Dx] S Ilf a.s.
Corollary F.4. Suppose the same setting as Theorem F.1, except that I ... In are sorted draws from pdf p with support in [0, 1] and such that p(x) 2 po 0. Then, with probability at least Port 8, the error satisfies
n ( O0
where Ô hides constants (including a) and polylog factors of n, Po and 8.
25

---

AKORN: Adaptive Knots generated Online for RegressioN splines
Similarly, for AKORN's Theorem F.2:
Corollary F.5. Suppose now that , In are sorted draws from a pdf p with support [0, 1] and such that p(x) 2 Po
Then, with probability at least Pon 10 6, the error of f satisfies
Σ f(x))) - OV
where Ô hides constants (including σ) and polylog factors of n, Po and 8.
G. Experimental Details and Additional Simulations
G.1. Details
single run of AKORN, Oracle Trend Filtering, and DoF Trend Filtering is performed follows
1. Generate c ~ N(00,2I,)
2. Get f AKORN((2; (x:) G).0)
3. Get fil for data {a,, (x;) (i) and parameter X, We use the library glmgen: https//ggthub.commiggggnngggggnn
4. Let fo-es be the Pig which has the smallest MSE with respect to the noiseless data
5. Let f--1== = ftg where A = arg minmieeee xe fllf YI + 200=0 where L(g) gives the number of linear pieces of g.
6. Produce fitted values - (f()))... and ύo-1ş (fo- and ůz-Ls (fo-ey(tts---Bb---1l for comparison
This procedure used subroutine for producing Tables 1, 2, and Figure 2.
G.2. ADDLE is worse than AKORN
In this appendix, we back up the statement made in Section 5.2 that ADDLE is not competitive with offline methods. In Figure 5, we reproduce couple entries of Figure 2, substituting TF-DoF with ADDLE.
26

---

AKORN: Adaptive Knots generated Online for RegressioN splines
akorn, rate -0.8781
oracle trend filtering, rate -0.80947
addle, rate -0.73821
10
MSE
10-2
10-3
102
1000
2000
3000
4000
5000
akorn, rate = -0.67642
oracle trend filtering, rate -0.35314
addle, rate -0.78537
10-1
MSE
10-2
102
103
1000
2000
3000
4000
5000
Figure Same methodology as Figure 2 applied the Doppler function Jump Function, this time comparing ADDLE to AKORN and Trend Filtering. There is roughly an order of magnitude difference in the MSEs for all
27


Reviews:
[{"review_id": "8So0PTZD1L", "reviewer": "Reviewer_tkPX", "summary": "The authors consider the problem of nonparametric regression over the class of $TV_1$-bounded functions. Crucially, the authors aim to overcome the issue of needing oracle knowledge regarding certain features of the data-generating process, while still achieving optimal error rates. Despite being in an offline setting, the authors leverage existing online denoising algorithm with both forward and backward passes over the offline data. The authors show that their approach performs empirically well relative to other baselines in the literature.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time and consideration.", "claims_and_evidence": "Yes, the claims seem reasonable given the empirical performance of this approach.", "methods_and_evaluation_criteria": "All experiments are reasonable evaluations of their method to baselines that (1) take oracle knowledge, which serves as an upper bound on  performance (i.e., impressive to perform as good as this) and (2) same theoretical guarantees without oracle knowledge, which serves as the baseline to beat. One minor change that would be helpful in assessing numerical results would be to have error bars on Tables 1 and 2.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "To the best of my knowledge, this would be the second work that provides optimal error rates beyond another baseline that these authors test. However, this work improves upon the empirical performance of the first paper greatly.", "essential_references_not_discussed": "I am unaware of other essential references not mentioned here.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BmtQjlyg4A", "reviewer": "Reviewer_Rwji", "summary": "This paper studies the non-parametric regression over TV_1-bounded functions. The paper proposes a parameter-free algorithm (AKORN) which leverages online learning techniques to select knots for regression splines. The algorithm proposed achieves near-optimal rates without hyperparameter tuning. Both theoretical and empirical results are presented.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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). \n\n### Uniform spacing:\nSince 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. \n\n### “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.”\n\nAs 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). \n\n### Computational complexity:\n\nIt’s true that the computational complexity of AKORN is slightly prohibitive, but we elaborate on the topic now. \n\nFirstly, 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. \n\nOn 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). \n\nLastly, 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.\n\nFurthermore, 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)$. \n\nSo while, practically speaking, people know how to do TF extremely efficiently, the theoretical picture is slightly complicated.", "claims_and_evidence": "As a theoretical work, most of the claims are well-supported by providing rigorous proof. Given that most related work on this problem achieves O(n) or O(nlogn) computational complexity, it would better to explore in detail how to reduce the O(n^2) complexity in this paper with the geometric cover trick.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the problem studied under the setting of this work.", "theoretical_claims": "Reviewed the proof sketches in the main body and verified the theorem and lemma statements, along with select proof details in the appendix. The overall proof structure appears sound and well-reasoned.", "experimental_designs_or_analyses": "The experimental design is sound.", "relation_to_broader_scientific_literature": "n/a", "essential_references_not_discussed": "I am not aware of essential references that are missing.", "other_strengths_and_weaknesses": "Strengths:\n-The idea of leveraging online learning techniques and learning forward and backwardly to design the adaptive method is interesting.\n-Processes data sequentially, adjusting knots based on residuals, similar to no-regret learning techniques.\n-AKORN does not require tuning smoothing penalties or pre-specifying the number of knots.\n-Proposed method matches minimax-optimal convergence rates for TV₁ functions.\n-The experimental results demonstrate that AKORN performs competitively with oracle-tuned Trend Filtering.\n\nWeaknesses:\n-Uniform spacing avoids knowing smoothness knowledge but uniform spacing is also a strong assumption as it reveals more structural information as knowing smoothness. \n-As a consequence, it cannot directly handle scattered data or missing time-series values without preprocessing.\n-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.", "other_comments_or_suggestions": "Few typos:\n1.\\hat{y_i} should be replaced with \\hat{y}_i on line 046\n2.\"where \\tilde{O} and \\lesssim hide...\" should be replaced with \"where \\lesssim hides...\" on line 698\n3. Using T to denote transposing is a bit misleading (for example on line 170)", "questions_for_authors": "I have no further questions for the authors.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YErwTuxvAL", "reviewer": "Reviewer_YjPY", "summary": "This paper proposes AKORN, a novel approach for offline non-parametric regression that adaptively selects spline knots without requiring manual hyperparameter tuning. The proposed method yields estimators competitive with oracle-enhanced Trend Filtering, attaining near-optimal theoretical performance for TV-bounded regression functions. The theoretical guarantees provided are thorough and rigorously developed, showcasing that AKORN's performance is competitive with the state-of-the-art offline methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your attention to this work! \n\n### Non-evenly spaced design points\nSince 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.\n\n### Proof sketches\nThank 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. \n\n### Higher-order Smoothness Classes\nThere 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.", "claims_and_evidence": "I think the claims are clearly supported.", "methods_and_evaluation_criteria": "The methods and evaluation criteria, such as Doppler, jump functions, and evaluation metric (mean squared error, MSE), are appropriate.", "theoretical_claims": "I checked Theorem 6.1 (Bound on ADDLE error) and Theorem 6.2 (Bound on AKORN MSE). During the proof, the \"Change-point Detection Lemma\" (Lemma 7.2) is pivotal, rigorously connecting the adaptively chosen knots to a sparse and statistically efficient linear spline. However, the Lemma 7.2 is informal and the authors didn't provide the formal expression or the source. Additionally, in the Proof Sketches section, the statements of theorems are all informal. Why doesn't the author provide a formal statement directly?", "experimental_designs_or_analyses": "Experimental design is generally sound. The synthetic functions (piecewise linear, Doppler, Jump) ensure theoretical and empirical coherence. However, there is no performance stability discussion", "relation_to_broader_scientific_literature": "AKORN builds upon previous work on trend filtering, wavelet smoothing, and online regression techniques. Unlike prior methods, AKORN adaptively chooses knots without needing explicit smoothness information. It extends influential approaches such as Trend Filtering (Kim et al., 2009; Tibshirani, 2014) and wavelet-based smoothing (Donoho & Johnstone, 1998), providing an integrated, parameter-free alternative that automatically adjusts to the underlying structure of data.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Strengths:\n1. The proposed AKORN algorithm is highly original in combining offline spline regression with adaptive online learning.\n2. The theoretical framework and results are well-established.\n\nWeaknesses:\n1. In the Proof Sketches section, the statements of theorems are all informal. \n2. Practical applications on real-world datasets would greatly strengthen the paper’s appeal to applied researchers and practitioners.\n3. The assumption of equally spaced covariates is restrictive. The authors acknowledge this limitation but should ideally outline a more explicit path forward for generalizing to unevenly spaced data.\n4. What are the primary theoretical or computational barriers to extending AKORN to higher-order smoothness classes?", "other_comments_or_suggestions": "I think the structure of the article needs to be readjusted. Articles usually start with theoretical analysis and then conduct experimental verification. Your appendix is very rich and can fill eight pages.", "questions_for_authors": "See Weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4WeAhw6yJA", "reviewer": "Reviewer_V1hW", "summary": "This paper introduces AKORN (Adaptive Knots generated Online for RegressioN splines), a parameter-free algorithm for offline non-parametric regression over total variation (TV1)-bounded functions. AKORN leverages online learning techniques to automatically adapt knot selection for spline regression, eliminating the need for oracle knowledge of function smoothness, which is a major drawback of traditional non-parametric regression methods. The contributions of this paper include the following points\n1. It achieves optimal rates without hyperparameter tuning (it adaptively selects knots based on change points in function smoothness).\n2. It proposes a new online learning-based method for knot selection: AKORN uses ADDLE (Adaptive Denoising with Linear Experts), an online regression technique, to identify smooth and rough regions of the function.\n3. Unlike existing online methods that output noisy pointwise predictions, AKORN reconstructs a continuous function.\n4. Its Computational Efficiency and Scalability. It runs in O(n^2) time (comparable to other spline methods).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your consideration. \n\n### Weaknesses 2 and 4\nThe 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.\n \n### Worst-case analysis (Weakness 3) \nTo 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. \n\n### Uneven Covariates (Weakness 1)\nWith 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.\n\n### “What happens if AKORN misidentifies some change points?”\nWhile 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$.\n\n## Technical steps for uneven covariates:\n\nIn 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$.\n\n**Key lemma, \"Lemma K\"** (The bias of  linear regression error is controlled even on uneven points)\nLet $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)$. \nLet $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})$.\n\n\n**Lemma 5 from [4]**\nSuppose $\\{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}$.\n\n**ADDLE generalization:**\n1) Change online linear regression experts to (clipped) VAW forecasters. This very minor algorithmic change does not affect computational efficiency. \n2) **VAW linear forecasters enjoy the same upper bound as offline linear regression up to an additive constant**\nThis follows from Theorem 11.8 in [1] paired with Corollary 40 in [2] to control the norm of the least-squares comparator.\n3) 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).\n4) 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. \n5) 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.\n\n**AKORN generalization**\nThe proof for AKORN now needs only trivial changes. \n\nMore detailed treatment can be found at this anonymized link: https://anonymous.4open.science/r/AKORN-uneven-D6FB/akorn_non_evenly_spaced_points.pdf\n\n[1] Prediction Learning and Games. Cesa-Bianchi and Lugosi. \n\n[2] Adaptive Online Estimation of Piecewise Polynomial Trends. Baby and Wang, 2020\n\n[3] Multivariate trend filtering for lattice data, Sandhalana et al., 2024.\n\n[4] The falling factorial basis and its statistical applications. Wang et al., 2014", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "This paper introduces AKORN (Adaptive Knots generated Online for RegressioN splines). It makes sense to non-parametric regression problems.", "theoretical_claims": "Yes, I checked the proof of their main results Theorem 6.1-6.2 and they look correct to me.", "experimental_designs_or_analyses": "For the experiment, AKORN selects knots adaptively, but the paper does not test how sensitive its performance is to different knot placements, i.e., what happens if AKORN misidentifies some change points? This issue seems important to their proposed method.", "relation_to_broader_scientific_literature": "The key contributions are related to non-parametric regression, eliminating the need for oracle knowledge of function smoothness, which is a major drawback of traditional non-parametric regression methods. This is a commonly studied statistical and machine learning problem.", "essential_references_not_discussed": "The paper has discussed a sufficient amount of relevant papers for showing and understanding their contributions.", "other_strengths_and_weaknesses": "Strength is clear: Their proposed method AKORN (Adaptive Knots generated Online for RegressioN splines) can automatically adapt knot selection for spline regression, eliminating the need for oracle knowledge of function smoothness, which is a major drawback of traditional non-parametric regression methods. Moreover, it achieves optimal rates without hyperparameter tuning (it adaptively selects knots based on change points in function smoothness).\n\nWeakness: \n1. The method assumes that covariates $x_i$ are equally spaced, which is a strong and unrealistic assumption in non-parametric regression. Although the paper mentioned that but it is a starting point for many non-parametric regression algorithms, it weakens the contribution of this paper significantly. For example, some other papers on trend filtering and wavelets have been extended to handle uneven spacing (Wang et al., 2014; Sadhanala & Tibshirani, 2019), but AKORN has not.\n2. The paper only considers TV1-bounded functions, but many real-world applications involve smoother functions (e.g., TV2, TV3).\n3. The paper claims AKORN achieves an instance-dependent rate Theorem 6.1-6.2, but there is no worst-case analysis. Trend filtering and spline methods have worst-case minimax bounds, ensuring robustness across all function classes.\n4. The method is designed for one-dimensional regression problems. There is no discussion on whether AKORN extends to multivariate or high-dimensional settings.", "other_comments_or_suggestions": "Please see \"Other Strengths And Weaknesses\".", "questions_for_authors": "Please see the four questions of weakness in \"Other Strengths And Weaknesses\".", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}]

Author rebuttal:

Meta-review: This paper presents a parameter-free algorithm for offline non-parametric regression over TV-1 bounded functions. The proposed method (referred to as AKORN) does not require knowledge of the ground-truth smoothness, and results in an estimator whose empirical performance is similar to an oracle Trend Filtering baseline.

The reviewers unanimously agree that the paper is well-written, and its contributions merit acceptance. After carefully reading the rebuttal/discussion, I tend to agree. Please incorporate the following comments in the final version of the paper. In particular, addressing the following concerns will help strengthen the current version of the paper:
- Including the proof handling uneven covariates (response to Rev. Rwji, Rev. YjPY)
- Clear description of the method's computational complexity and its comparison with existing work  (response to Rev. Rwji)
- Including the discussion about higher-order smoothness classes (response to Rev. YjPY, Rev. V1hW)
Decision: Accept (poster)