# Variance estimation in graphs with the fused lasso

arXiv: https://arxiv.org/abs/2207.12638 · HTML: https://mlsanity.com/paper/2207.12638/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 68 references that are in the map.
- First posted on arXiv 26 Jul 2022.

## Builds on (most cited first, 20 of 20)

- [Adaptive piecewise polynomial estimation via trend filtering](https://mlsanity.com/paper/1304.2986/) (2013)
- [Trend Filtering on Graphs](https://mlsanity.com/paper/1410.7690/) (2014)
- [Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers](https://mlsanity.com/paper/1605.08400/) (2016)
- [On the Prediction Performance of the Lasso](https://mlsanity.com/paper/1402.1700/) (2014)
- [Modular proximal optimization for multidimensional total-variation regularization](https://mlsanity.com/paper/1411.0589/) (2014)
- [Adaptive Estimation of Multivariate Piecewise Polynomials and Bounded Variation Functions by Optimal Decision Trees](https://mlsanity.com/paper/1911.11562/) (2019)
- [False discovery rate smoothing](https://mlsanity.com/paper/1411.6144/) (2014)
- [Prediction bounds for higher order total variation regularized least squares](https://mlsanity.com/paper/1904.10871/) (2019)
- [Additive Models with Trend Filtering](https://mlsanity.com/paper/1702.05037/) (2017)
- [New Risk Bounds for 2D Total Variation Denoising](https://mlsanity.com/paper/1902.01215/) (2019)
- [Approximate l0-penalized estimation of piecewise-constant signals on graphs](https://mlsanity.com/paper/1703.01421/) (2017)
- [Non-parametric Quantile Regression via the K-NN Fused Lasso](https://mlsanity.com/paper/2012.01758/) (2020)
- [A causal fused lasso for interpretable heterogeneous treatment effects estimation](https://mlsanity.com/paper/2110.00901/) (2021)
- [Multivariate Trend Filtering for Lattice Data](https://mlsanity.com/paper/2112.14758/) (2021)
- [A Fast and Flexible Algorithm for the Graph-Fused Lasso](https://mlsanity.com/paper/1505.06475/) (2015)
- [On the total variation regularized estimator over a class of tree graphs](https://mlsanity.com/paper/1806.01009/) (2018)
- [Lattice partition recovery with dyadic CART](https://mlsanity.com/paper/2105.13504/) (2021)
- [Scalable Bayesian change point detection with spike and slab priors](https://mlsanity.com/paper/2106.10383/) (2021)
- [Graphon estimation via nearest neighbor algorithm and 2D fused lasso denoising](https://mlsanity.com/paper/1805.07042/) (2018)
- [Multiscale quantile segmentation](https://mlsanity.com/paper/1902.09321/) (2019)

## Built on by (most cited first, 2 of 2)

- [Conditional Mean and Variance Estimation via textitk-NN Algorithm with Automated Variance Selection](https://mlsanity.com/paper/2402.01635/) (2024)
- [Graph-dependent shrinkage priors for Bayesian trend filtering](https://mlsanity.com/paper/2608.23802/) (2026)

## Abstract (arXiv)

We study the problem of variance estimation in general graph-structured problems. First, we develop a linear time estimator for the homoscedastic case that can consistently estimate the variance in general graphs. We show that our estimator attains minimax rates for the chain and 2D grid graphs when the mean signal has total variation with canonical scaling. Furthermore, we provide general upper bounds on the mean squared error performance of the fused lasso estimator in general graphs under a moment condition and a bound on the tail behavior of the errors. These upper bounds allow us to generalize for broader classes of distributions, such as sub-exponential, many existing results on the fused lasso that are only known to hold with the assumption that errors are sub-Gaussian random variables. Exploiting our upper bounds, we then study a simple total variation regularization estimator for estimating the signal of variances in the heteroscedastic case. We also provide lower bounds showing that our heteroscedastic variance estimator attains minimax rates for estimating signals of bounded variation in grid graphs, and K-nearest neighbor graphs, and the estimator is consistent for estimating the variances in any connected graph.