Prediction bounds for higher order total variation regularized least squares

1.3. Main result for trend filtering

• For k = 1, 2, 3, 4, the estimator has adaptive prediction bounds governed by the approximation–estimation trade-off and can adapt to the number of jumps in the (k −1)th discrete derivative.The bounds also allow a sparse approximation to the underlying signal; the theorem imposes conditions on segment lengths and the tuning parameter.Source: §1 · p. 1, §1.3 · p. 4

1. Introduction

• The trend-filtering estimator is a least-squares method with an ℓ1 penalty on coefficients selected by the kth-order difference operator.The paper formulates it as an analysis problem with that difference operator as its analysis matrix.Source: §1 · pp. 1–2
• Interpolating vectors bound effective sparsity in a general analysis-Lasso oracle inequality, providing the proof route from the analysis problem to trend filtering.The paper describes the interpolating vector as a quantified noisy version of the dual certificate used in basis pursuit.Source: §1 · p. 2

1.1. Related work

• For k ≥ 2, the paper reports an improved prediction-error rate over Guntuboyina et al. [2020] under a minimum-length condition and an appropriate tuning parameter.The cited comparison is (s0 + 1) log(n/(s0 + 1)) log n/n versus (s0 + 1)2k/n; here s0 counts jumps in the (k −1)th discrete derivative.Source: §1.1 · p. 3
• For k = 1, the result has an extra log factor attributed to projection arguments; entropy arguments can remove it while retaining interpolating vectors and effective sparsity.The comparison is to the rate stated in Guntuboyina et al. [2020].Source: §1.1 · p. 3

Remark 1.3

• The theorem’s tuning requirement depends on the active set, so a fixed data-independent tuning parameter restricts which active sets satisfy the stated result.The restriction is expressed through an upper bound on nmax.Source: Remark 1.3 · p. 5

Remark 1.4

• The paper sketches how to establish the trend-filtering bound for general k, beyond the proved cases k = 1, 2, 3, 4.The calculations and adaptive result are given for the four listed orders.Source: §1 · p. 1, Remark 1.4 · p. 5

Remark 1.6

• The same proof approach yields square-root trend filtering with a universal tuning choice that does not depend on the noise variance.This is stated as a corollary of Ortelli and van de Geer [2020].Source: Remark 1.6 · p. 6

2. Adaptive bounds for the general analysis estimator

• Applying Theorem 2.2 requires upper-bounding effective sparsity; Lemma 2.4 does this by invoking interpolating vectors, defined in Definition 2.3, and together they provide the starting point for proving the trend-filtering result.Source: §2 · p. 6

2.2. The dictionary

• The dictionary represents the part of a vector orthogonal to the augmented comparison space, which is the component targeted by the penalty.For trend filtering, the dictionary is uniquely defined under the stated invertibility condition.Source: §2.2 · p. 7

2.3. Effective sparsity

• The effective sparsity is introduced to establish adaptive bounds, with noiseless and noisy versions defined under a tuning-parameter condition.The setup includes an active-set sign vector and weights for nonactive indices.Source: §2.3 · p. 8

Remark 2.1

• The tuning parameter may need to be strictly larger than the stated requirement, though it can remain of the same order, to obtain well-behaved effective sparsity.The authors also note that weighted empirical-process bounds may improve the parameter choice in some settings.Source: Remark 2.1 · p. 8

2.4. Main result for the general analysis problem

• Theorem 2.2 gives adaptive bounds by allowing the active set and comparison vector to trade off approximation error against estimation error.The trade-off depends on the unknown signal.Source: §2.4 · p. 8

Remark 2.2

• Theorem 2.2 modifies prior analysis-problem results by allowing augmentation of the comparison space and using an improved compatibility quantity.The authors connect the analysis formulation to prior results on the Lasso and square-root analysis problem.Source: Remark 2.2 · p. 9

2.5. Interpolating vectors

• Interpolating vectors complete the signs on the active set and provide a bound on effective sparsity.Lemma 2.4 uses this approach for the noiseless case; the proof also gives the noisy-case argument.Source: §2.5 · pp. 9–10

Remark 2.3

• The general analysis result modifies earlier Lasso work, while the connection between interpolating vectors, dual certificates, and compatibility is presented as previously unmade.The discussion relates these ideas to work on superresolution and notes differences in compatibility conditions.Source: Remark 2.3 · p. 10

3.1.1. The dictionary for general k: upper bounds

• For general k, the dictionary analysis upper-bounds column lengths of ∆(k)+ and uses these bounds to control columns of Ψ−S.The stated approach disconnects the system into s + 1 components; its augmented space has dimension k(s + 1).Source: §3.1.1 · p. 11

Theorem 3.4

• Theorem 3.4 applies the non-adaptive part of Theorem 2.2 to obtain a bound for every f ∈ R^n with probability at least 1 − e^(−u) − e^(−v).The tuning parameter must satisfy condition (8).Source: Theorem 3.4 · p. 14

Corollary 3.5

• For n^(k−1)||∆(k)f||_1 ≤ 1, the corollary gives the minimax rate up to a log factor [1998].This is stated for f = f0 and identified as the minimax rate over the specified class.Source: Corollary 3.5 · p. 14

3.3. Interpolating vectors and effective sparsity and for D = ∆(k)

• In the noisy case, interpolation near active points uses powers (2k − 1)/2, which introduces an additional logarithmic factor compared with the noiseless case.The modification addresses the constraint |q_j| ≤ 1 − w_j for j ∈ D.Source: §3.3 · p. 14

3.3.1. Construction of an interpolating vector

• The proposed interpolating vector is built by splitting intervals, using piecewise degree-k polynomials, and matching discrete derivatives; monotonicity is checked for k = 1, 2, 3, and 4.The general construction uses a continuous interpolation idea and a discrete version at sign changes.Source: §3.3 · p. 15, §3.3.1 · pp. 15–17

3.3.2. Interpolating vector and effective sparsity for k = 1

• For k = 1, linear interpolation across a sign change over an interval of length n_i contributes 4/n_i to the effective-sparsity bound.The passage also notes boundary effects on the left and right intervals.Source: §3.3.2 · p. 17

Remark 3.1

• A staircase pattern in the signs of (Df)_S can favor prediction, although it is known to harm model consistency when f = f0 [2016].At locations without sign changes, the interpolating vector can use less-steep interpolations.Source: Remark 3.1 · pp. 17–18

3.3.4. Interpolating vector and effective sparsity for k = 3

• Under condition (10) on λ, the k = 3 interpolating-vector construction gives the effective-sparsity bound (3).Boundary intervals are handled with analogous expressions, and the construction uses a scaled, discrete version of q.Source: §3.3.4 · p. 20

3.3.5. Interpolating vector and effective sparsity for k = 4

• For k = 4, a scaled, discrete q defined by eight equations yields effective-sparsity bound (3) when λ satisfies (8).The function q is decreasing, with q and its first three derivatives continuous.Source: §3.3.5 · p. 21

3.4. Proof of Theorem 1.1

• Dictionary-column control verifies the λ requirement under (8), and strengthening to (10) bounds effective sparsity, yielding Theorem 1.1 from Theorem 2.2.The proof combines the dictionary bound from Subsection 3.1.1 with effective-sparsity bounds from Subsections 3.3.2–3.3.5.Source: §3.4 · p. 21

4. Conclusion

• For k in {1, 2, 3, 4}, sharp oracle inequalities give finite-sample prediction bounds and adaptation to the unknown number of jumps in the (k −1)th discrete derivative.The prediction error is upper bounded by the optimal trade-off between approximation error and estimation error.Source: §4 · p. 22
• Bounding effective sparsity with interpolating vectors is the key tool for these results.The paper also describes extensions to higher-dimensional problems, graph total variation, and losses other than least squares.Source: §4 · p. 22
• For graph total variation, the dictionary can be formed by counting how often an edge is used along paths from a node to other nodes.For graphs with cycles, paths may be chosen to allow a smooth interpolating vector.Source: §4 · p. 22

Appendix A: Proof of Theorem 2.2

• The proof begins with the basic inequality and controls empirical-process increments by decomposing them into a projection onto an enlarged space and a remainder.The enlarged space includes mock variables.Source: Appendix A · p. 24
• Concentration bounds control the empirical-process terms, yielding a high-probability bound with failure probabilities e^-u and e^-v.The proof uses a chi-square concentration inequality and a bound for the maximum of standard Gaussian variables.Source: Appendix A · pp. 24–25
• The proof establishes non-adaptive and adaptive bounds separately, using ∥w−S∥∞≤1 for the former and weighted inequalities for the latter.It then applies the conjugate inequality 2ab ≤ a^2 + b^2 to complete the bounds.Source: Appendix A · pp. 25–26

B.1. Proof for the result in Subsection 3.1.1

• Since ∆(k) has full rank, its Moore–Penrose inverse is ∆(k)′(∆(k)∆(k)′)−1.The proof examines symmetry in the rows of ∆(k)′ and in the columns of (∆(k)∆(k)′)−1.Source: §B.1 · pp. 26–27
• The falling factorial basis for equidistant design forms a complete dictionary for the general analysis problem.The proof uses this dictionary in the trend-filtering construction.Source: §B.1 · p. 27
• A symmetry argument establishes the claim about the column lengths of ∆(k)+.The proof invokes Lemma B.1 to obtain the result.Source: §B.1 · pp. 26–27

• The target is the anti-projection of each ψ_j, j ∈ [3:n], onto the span of ψ_1 and ψ_2.Source: §B.2 · p. 28
• Gram–Schmidt orthonormalizes the projection basis, beginning with u_1 = ψ_1 and constructing u_2 by removing ψ_2’s component along e_1.The text denotes the normalized orthogonal vectors by e_1 and e_2.Source: §B.2 · p. 28
• The anti-projection length is computed from the projection coefficients onto e_1 and e_2 and the squared norm of ψ_j.The stated calculations were performed with Wolfram Mathematica 11.Source: §B.2 · p. 28
• The proof presents the resulting anti-projection length as an exact expression.Source: §B.2 · p. 29

• The proof reuses e_1 and e_2 from Lemma 3.2 and applies Gram–Schmidt in its computations.The calculations are reported as performed with Wolfram Mathematica 11.Source: §B.3 · p. 29
• It computes the projection coefficients onto e_1 and e_2, including an explicit formula for ⟨ψ_j, e_2⟩.The supplied expression is (n + 3 − j)(n + 2 − j)(n + 1 − j)(n + j − 2).Source: §B.3 · p. 29
• The proof obtains the anti-projection of ψ_3 onto span(ψ_1, ψ_2) and identifies the third orthonormal basis vector e_3.Source: §B.3 · pp. 29–30
• It then computes projection coefficients onto e_3 and combines the formulas to establish the claim.Source: §B.3 · p. 30

• The proof expands around x = 0 and identifies the Taylor coefficients and a remainder rem(x).Source: §C.1 · p. 30
• For 0 ≤ x ≤ 1/2, the remainder satisfies sup |rem(x)| ≤ C_k|x|^k for some constant C_k.Source: §C.1 · p. 30
• A polynomial of degree k − 1 has zero k-th order difference, and the proof invokes this for j ≥ 2k.Source: §C.1 · p. 31

• The section opens with the proof of Lemma 3.7.Source: §C.2 · p. 31