Prediction bounds for higher order total variation regularized least squares
We establish adaptive results for trend filtering: least squares estimation with a penalty on the total variation of $(k-1)^{\rm th}$ order differences. Our approach is based on combining a general oracle inequality for the $\ell_1$-penalized least squares estimator with "interpolating vectors" to upper-bound the "effective sparsity". This allows one to show that the $\ell_1$-penalty on the $k^{\text{th}}$ order differences leads to an estimator that can adapt to the number of jumps in the $(k-1)^{\text{th}}$ order differences of the underlying signal or an approximation thereof. We show the result for $k \in \{1,2,3,4\}$ and indicate how it could be derived for general $k\in \mathbb{N}$.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Higher-Order Total Variation Classes on Grids: Minimax Theory and Trend Filtering Methods
We consider the problem of estimating the values of a function over $n$ nodes of a $d$-dimensional grid graph (having equal side lengths $n^{1/d}$) from noisy observations. The function is assumed to be smooth, but is al…
Higher-Order Generalization Bounds: Learning Deep Probabilistic Programs via PAC-Bayes Objectives
Deep Probabilistic Programming (DPP) allows powerful models based on recursive computation to be learned using efficient deep-learning optimization techniques. Additionally, DPP offers a unified perspective, where infere…
Generalization BoundsMeta-LearningProbabilistic ProgrammingLower Bounds on the Total Variation Distance Between Mixtures of Two Gaussians
Mixtures of high dimensional Gaussian distributions have been studied extensively in statistics and learning theory. While the total variation distance appears naturally in the sample complexity of distribution learning,…
Learning TheoryTotal Variation Rates for Riemannian Flow Matching
Riemannian flow matching (RFM) extends flow-based generative modeling to data supported on manifolds by learning a time-dependent tangent vector field whose flow-ODE transports a simple base distribution to the data law.…
Guaranteed Deterministic Bounds on the Total Variation Distance between Univariate Mixtures
The total variation distance is a core statistical distance between probability measures that satisfies the metric axioms, with value always falling in $[0,1]$. This distance plays a fundamental role in machine learning …
Two-sample testing