PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive piecewise polynomial estimation via trend filtering

Ryan J. Tibshirani

arXiv:1304.2986v2math.STstat.MEstat.ML

TL;DR

The paper studies whether trend filtering can provide adaptive spline-like regression while improving on the respective limitations of smoothing splines and locally adaptive regression splines. It analyzes trend filtering through discrete differences and lasso representations, establishing spline equivalences or approximations and minimax convergence under bounded variation. The resulting method is both locally adaptive and comparatively fast, though important extensions and scope boundaries remain.

  • Problem

    The paper examines whether trend filtering has a genuine spline-like structure and can combine the local adaptivity of locally adaptive regression splines with better computational tractability.

  • Method

    The paper analyzes discrete-difference trend filtering through continuous-time and lasso representations, then pairs its fitted values asymptotically with locally adaptive regression splines.

  • Results

    For bounded-variation kth derivatives, trend filtering attains the minimax squared-error convergence rate; it equals locally adaptive regression splines for k = 0,1 and is close for k ≥2.

  • Takeaways & Limitations

    Trend filtering offers a comparatively favorable balance of local adaptivity and computational speed relative to smoothing splines and locally adaptive regression splines.

  • Takeaways & Limitations

    A truly all-purpose method would need to handle arbitrary and multivariate inputs, which require extensions and leave questions for future work.

Abstract

from arXiv · show

We study trend filtering, a recently proposed tool of Kim et al. [SIAM Rev. 51 (2009) 339-360] for nonparametric regression. The trend filtering estimate is defined as the minimizer of a penalized least squares criterion, in which the penalty term sums the absolute $k$th order discrete derivatives over the input points. Perhaps not surprisingly, trend filtering estimates appear to have the structure of $k$th degree spline functions, with adaptively chosen knot points (we say ``appear'' here as trend filtering estimates are not really functions over continuous domains, and are only defined over the discrete set of inputs). This brings to mind comparisons to other nonparametric regression tools that also produce adaptive splines; in particular, we compare trend filtering to smoothing splines, which penalize the sum of squared derivatives across input points, and to locally adaptive regression splines [Ann. Statist. 25 (1997) 387-413], which penalize the total variation of the $k$th derivative. Empirically, we discover that trend filtering estimates adapt to the local level of smoothness much better than smoothing splines, and further, they exhibit a remarkable similarity to locally adaptive regression splines. We also provide theoretical support for these empirical findings; most notably, we prove that (with the right choice of tuning parameter) the trend filtering estimate converges to the true underlying function at the minimax rate for functions whose $k$th derivative is of bounded variation. This is done via an asymptotic pairing of trend filtering and locally adaptive regression splines, which have already been shown to converge at the minimax rate [Ann. Statist. 25 (1997) 387-413]. At the core of this argument is a new result tying together the fitted values of two lasso problems that share the same outcome vector, but have different predictor matrices.

1. Introduction.

The paper develops trend filtering as a locally adaptive nonparametric regression method, clarifies its piecewise-polynomial and spline-like structure, and compares its statistical and computational properties with smoothing splines and locally adaptive regression splines.

  • 1. Introduction.: Trend filtering penalizes discrete (k + 1)st differences, leading kth-order estimates with an expected piecewise-polynomial structure and adaptively selected knots.The difference operator is built recursively, and nonzero entries of D(k+1)β̂ identify knots.
  • 1. Introduction.: The paper asks whether trend filtering’s discrete estimates have a continuous-time spline representation, because lower-order discrete derivatives appear continuous across knots.This question motivates the paper’s theoretical treatment of trend filtering beyond its generalized-lasso formulation.
  • 1. Introduction.: Empirically, trend filtering is more locally adaptive than smoothing splines and closely resembles locally adaptive regression splines.These comparisons motivate theoretical analysis rather than relying only on empirical examples.
  • 1.2. Summary of our results.: For k = 0,1, continuous-time trend filtering is exactly equivalent to kth-order locally adaptive regression splines; for k ≥2, it is only close to spline-like.For higher orders, lower-order derivatives can have small discontinuities at knots, so the estimators are formally different.
  • 1.2. Summary of our results.: When the kth derivative of f0 has bounded variation, trend filtering attains the minimax squared-error convergence rate, unlike smoothing splines and other estimators linear in y.The proof uses asymptotic pairing with locally adaptive regression splines and a new bound for lasso problems sharing an outcome vector but having different predictor matrices.
  • 1.3. Why trend filtering?: Trend filtering balances local adaptivity with computational efficiency, requiring O(n3/2) worst-case complexity versus O(n) for smoothing splines and much slower locally adaptive regression splines.The paper reports that trend filtering can handle problems around n = 1,000,000 with an interior-point method, whereas locally adaptive regression splines become prohibitively slow around n = 10,000.

2. Comparison to smoothing splines.

Trend filtering and smoothing splines both estimate spline-like functions, but their penalties produce different adaptivity. Empirical examples show trend filtering better captures spatially varying smoothness and generally achieves lower prediction loss.

  • Estimator structure: Trend filtering estimates exhibit adaptively chosen piecewise-polynomial structure, while smoothing splines are natural splines with knots at the input points.The trend filtering knot count is interpreted through nonzero entries of its discrete derivative vector.
  • Penalty comparison: Smoothing splines minimize a quadratic derivative penalty, whereas trend filtering uses an ℓ1 penalty on discrete derivatives.The quadratic penalty shrinks derivative components without setting them to zero, while the ℓ1 penalty can adaptively set discrete derivatives to zero.
  • Empirical comparisons: In the hills example, cubic trend filtering with 19 degrees of freedom adapts to smoothness on both sides, whereas smoothing splines require 30 degrees of freedom and then undersmooth the left side.With 19 degrees of freedom, the smoothing spline considerably undersmooths the wiggly right side; increasing flexibility fixes that side but harms the smooth left side.
  • Empirical comparisons: Across hills and Doppler simulations, trend filtering generally has better squared-error predictive accuracy, especially at low to intermediate model complexity.The losses were averaged over 50 simulated data sets, with dotted lines showing plus or minus one standard deviation.
  • Computation: Using a B-spline basis makes the smoothing-spline computation banded and allows fitted values to be computed in O(n) operations.The basis functions have local support, which makes the relevant matrix banded.

3. Comparison to locally adaptive regression splines.

Locally adaptive regression splines penalize total variation in the kth derivative, while trend filtering admits closely related lasso formulations. They are exactly equivalent for k=0 or 1 and practically very similar for higher orders, though computational scalability differs.

  • Locally adaptive regression splines: Locally adaptive regression splines estimate kth-degree splines with knots restricted to input-derived locations and penalize the total variation of the kth derivative.The restricted formulation is computationally tractable and has the same convergence rates as the unrestricted formulation for evenly spaced inputs.
  • Lasso representations: Using a truncated power basis converts the locally adaptive regression spline problem into a lasso problem with predictor matrix G.Trend filtering can likewise be written as a lasso problem, enabling direct comparison through their predictor matrices.
  • Exact equivalence: For k=0 or 1, the predictor matrices G and H coincide, so trend filtering and locally adaptive regression spline solutions match at the input points.For k≥2, G≠H, making the optimization problems formally different.
  • Computational considerations: Trend filtering is computationally more scalable because locally adaptive regression splines require a dense n×n predictor matrix.At n=10,000, 4,000 steps took under 2.5 minutes for trend filtering versus 1 hour for LARS, and larger problems raised memory concerns.

4. Continuous-time representation.

Trend filtering can be represented through continuous-time basis functions whose evaluations reproduce its discrete fitted values. This representation reveals piecewise-polynomial structure while also explaining why higher-order trend filtering need not be a classical spline.

  • Basis construction: Trend filtering’s lasso predictor matrix H is generated by evaluating explicitly defined basis functions h1,...,hn at evenly spaced input points.This provides a continuous-time parameterization of the discrete trend filtering problem.
  • Continuous-time equivalence: The continuous-time minimization problem using these basis functions has solutions matching trend filtering at the input points.The equivalence holds for evenly spaced inputs xi=i/n.
  • Function structure: The resulting continuous-time estimate is a degree-k piecewise polynomial with knots contained in the interior input points.For k≥1 it is continuous, but for k≥2 its lower-order derivatives may be discontinuous at input points.
  • Relation to spline bases: For k≥2, trend filtering basis functions resemble truncated power bases while retaining small discontinuities in lower-order derivatives.For k=3, the first and second derivatives are discontinuous, despite the visual similarity of the bases.
  • Asymptotic comparison: Trend filtering and locally adaptive regression splines converge to each other at the minimax rate over a broad class of functions.The paper uses this asymptotic pairing to show that trend filtering inherits the locally adaptive regression spline minimax rate.

5. Rates of convergence.

The paper establishes minimax-rate convergence for trend filtering over functions whose kth derivative has bounded variation by asymptotically pairing it with locally adaptive regression splines. The argument relies on new stability bounds for lasso fits with different predictor matrices but the same outcome.

  • 5.1. Minimax convergence rate.: Smoothing splines are suboptimal over F_k(C), whereas locally adaptive regression splines achieve the minimax rate.The comparison concerns squared-error convergence over the bounded-variation function class.
  • 5.2. Trend filtering convergence rate.: The proof compares trend filtering with locally adaptive regression splines because direct spline interpolation arguments do not extend easily to trend filtering.For k = 0 or k = 1, the two estimators are exactly the same; the asymptotic comparison is mainly needed for k ≥2.
  • 5.2. Trend filtering convergence rate.: Both estimators can be represented as lasso fits, enabling a bound on their fitted-value difference through the similarity of their predictor matrices.The new stability result is driven primarily by the maximum elementwise difference between the predictor matrices G and H.
  • 5.1. Minimax convergence rate.: Trend filtering achieves the minimax convergence rate over F_k(C), the class of functions with bounded variation in their kth derivative.The result uses an appropriate tuning parameter and extends the known minimax guarantee for locally adaptive regression splines.
  • 5.3. Functions with growing total variation.: For growing total variation C_n, trend filtering retains the corresponding convergence rate when C_n = O(n^((k+2)/(2k+2))).This growth restriction is unnecessary for the locally adaptive regression spline result, but it is unnecessary for trend filtering when k = 0 or k = 1.

6. Astrophysics data example.

In simulated quasar-spectrum data, trend filtering adapts to the spectrum’s changing smoothness and outperforms smoothing splines at lower model complexity. A split smoothing spline with separate parameters on either side of the main peak performs comparably to trend filtering.

  • Data characteristics: The quasar spectrum is highly wiggly on the left and much smoother on the right, with larger errors around the wiggly region.These features create a setting where local adaptivity is important.
  • Function estimates: Trend filtering captures many features of the true curve, including the large spike just before x = 3.6, but misses some left-side detail.The estimates were tuned to 81 degrees of freedom in the displayed example.
  • Squared-error comparison: Trend filtering has significantly lower squared error loss than smoothing splines at low model complexity, while both outperform wavelets.The losses were averaged over 20 simulated data sets across degrees-of-freedom values.
  • Locally varying smoothness: A smoothing spline with separate tuning parameters on the two sides of x = 3.6 performs basically on par with trend filtering.The split spline was introduced to provide a finer level of local adaptivity.

7. Extensions and discussion.

The discussion positions trend filtering as a relatively fast, locally adaptive estimator and develops extensions based on sparse, mixed-order, additive, and analysis-formulation ideas. A truly multivariate extension remains an ambitious open direction.

  • Discussion: Trend filtering combines local adaptivity with computational complexity O(n^3/2), compared with O(n) for smoothing splines.Its convergence rate matches that of locally adaptive regression splines over a broad function class and is minimax there.
  • Computational representation: Trend filtering replaces the dense inverse associated with spline basis matrix G by a falling-factorial matrix H with a sparse banded inverse.This representation provides a computational advantage while retaining the estimator’s adaptive structure.
  • Multivariate extensions: For multivariate inputs, the paper distinguishes a difficult truly multivariate extension from a more modest additive model using univariate trend filtering.Additive fitting can scale better with dimension p in computational and statistical efficiency.
  • Analysis and synthesis: The analysis formulation penalizes discrete-derivative jumps, whereas the synthesis formulation constructs estimates from basis functions.Trend filtering admits both views because its penalty matrix has full row rank.
  • Further extensions: Sparse trend filtering can produce estimates that are identically zero on selected stretches, while mixed trend filtering allows different polynomial orders across the domain.These structures appear difficult to construct generically from the synthesis perspective.

SUPPLEMENTARY MATERIAL

The supplement supplies proofs for the paper’s theoretical results and discusses arbitrary input points.

  • Supplementary material: The supplement provides proofs for the results in Sections 3 and 4 and the theoretical framework for the convergence rates in Section 5.It also discusses an extension of trend filtering to arbitrary input points.
Loading 1304.2986v2…