Minmax Trend Filtering: Generalizations of Total Variation Denoising via a Local Minmax/Maxmin Formula

• URL: http://arxiv.org/abs/2410.03041v3
• Date: Thu, 10 Apr 2025 16:25:03 GMT
• Title: Minmax Trend Filtering: Generalizations of Total Variation Denoising via a Local Minmax/Maxmin Formula
• Authors: Sabyasachi Chatterjee,
• Abstract summary: Total Variation Denoising (TVD) is a fundamental denoising and smoothing method.<n>In this article, we identify a new local minmax/maxmin formula producing two estimators.<n>We show how the proposed local definition of TVD/MTF estimator makes it tractable to bound pointwise estimation errors.
• Score: 4.07926531936425
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Total Variation Denoising (TVD) is a fundamental denoising and smoothing method. In this article, we identify a new local minmax/maxmin formula producing two estimators which sandwich the univariate TVD estimator at every point. Operationally, this formula gives a local definition of TVD as a minmax/maxmin of a simple function of local averages. Moreover we find that this minmax/maxmin formula is generalizeable and can be used to define other TVD like estimators. In this article we propose and study higher order polynomial versions of TVD which are defined pointwise lying between minmax and maxmin optimizations of penalized local polynomial regressions over intervals of different scales. These appear to be new nonparametric regression methods, different from usual Trend Filtering and any other existing method in the nonparametric regression toolbox. We call these estimators Minmax Trend Filtering (MTF). We show how the proposed local definition of TVD/MTF estimator makes it tractable to bound pointwise estimation errors in terms of a local bias variance like trade-off. This type of local analysis of TVD/MTF is new and arguably simpler than existing analyses of TVD/Trend Filtering. In particular, apart from minimax rate optimality over bounded variation and piecewise polynomial classes, our pointwise estimation error bounds also enable us to derive local rates of convergence for (locally) Holder Smooth signals. These local rates offer a new pointwise explanation of local adaptivity of TVD/MTF instead of global (MSE) based justifications.

Related papers

• Local Polynomial Lp-norm Regression [0.0]
  Local least squares estimation cannot provide optimal results when non-Gaussian noise is present. It is suggested that $L_p$-norm estimators be used to minimize the residuals when these exhibit non-normal kurtosis. We show our method's superiority over local least squares in one-dimensional data and show promising outcomes for higher dimensions, specifically in 2D.
  arXiv  Detail & Related papers  (2025-04-25T21:04:19Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  We introduce a new adaptive $k$-nearest neighbours ($kK$-NN) algorithm that explores the local curvature at a sample to adaptively defining the neighborhood size. Results on many real-world datasets indicate that the new $kK$-NN algorithm yields superior balanced accuracy compared to the established $k$-NN method.
  arXiv  Detail & Related papers  (2024-09-08T13:08:45Z)
• Multivariate root-n-consistent smoothing parameter free matching estimators and estimators of inverse density weighted expectations [51.000851088730684]
  We develop novel modifications of nearest-neighbor and matching estimators which converge at the parametric $sqrt n $-rate. We stress that our estimators do not involve nonparametric function estimators and in particular do not rely on sample-size dependent parameters smoothing.
  arXiv  Detail & Related papers  (2024-07-11T13:28:34Z)
• A Biased Estimator for MinMax Sampling and Distributed Aggregation [0.786519149320184]
  We propose a biased MinMax estimation scheme, B-MinMax, which trades an increase in estimator bias for a reduction in variance. B-MinMax is preferable when sample sizes are small or the number of aggregated vectors is limited.
  arXiv  Detail & Related papers  (2024-04-26T20:39:08Z)
• Adaptive and non-adaptive minimax rates for weighted Laplacian-eigenmap based nonparametric regression [14.003044924094597]
  We show both adaptive and non-adaptive minimax rates of convergence for a family of weighted Laplacian-Eigenmap based nonparametric regression methods.
  arXiv  Detail & Related papers  (2023-10-31T20:25:36Z)
• Online Laplace Model Selection Revisited [0.6355355626203273]
  Online variants of the Laplace approximation have seen renewed interest in the Bayesian deep learning community. This work re-derives online Laplace methods, showing them to target a variational bound on a mode-corrected variant of the Laplace evidence. We demonstrate that these optima are roughly attained in practise by online algorithms using full-batch gradient descent on UCI regression datasets.
  arXiv  Detail & Related papers  (2023-07-12T11:36:27Z)
• Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient [4.478941279527423]
  Backtracking linesearch is the de facto approach for minimizing continuously differentiable functions with locally Lipschitz gradient. In recent years, it has been shown that in the convex setting it is possible to avoid linesearch altogether. We propose an adaptive proximal gradient method, adaPG, that uses novel estimates of the local smoothness modulus.
  arXiv  Detail & Related papers  (2023-01-11T12:19:28Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  We present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems. Our work is based on the fact that the update rule of the Proximal Point method can be approximated up to accuracy.
  arXiv  Detail & Related papers  (2023-01-10T12:18:47Z)
• Scalable Gaussian-process regression and variable selection using Vecchia approximations [3.4163060063961255]
  Vecchia-based mini-batch subsampling provides unbiased gradient estimators. We propose Vecchia-based mini-batch subsampling, which provides unbiased gradient estimators.
  arXiv  Detail & Related papers  (2022-02-25T21:22:38Z)
• Localization with Sampling-Argmax [45.408767601013786]
  We propose sampling-argmax, a differentiable training method that imposes implicit constraints to the shape of the probability map. We show that sampling-argmax can seamlessly replace the conventional soft-argmax operation on various localization tasks.
  arXiv  Detail & Related papers  (2021-10-17T13:56:25Z)
• Fast Batch Nuclear-norm Maximization and Minimization for Robust Domain Adaptation [154.2195491708548]
  We study the prediction discriminability and diversity by studying the structure of the classification output matrix of a randomly selected data batch. We propose Batch Nuclear-norm Maximization and Minimization, which performs nuclear-norm on the target output matrix to enhance the target prediction ability. Experiments show that our method could boost the adaptation accuracy and robustness under three typical domain adaptation scenarios.
  arXiv  Detail & Related papers  (2021-07-13T15:08:32Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  Even simple methods like least squares can exhibit non-normal behavior when data is collected in an adaptive manner. We propose a family of online debiasing estimators to correct these distributional anomalies in at least squares estimation. We demonstrate the usefulness of our theory via applications to multi-armed bandit, autoregressive time series estimation, and active learning with exploration.
  arXiv  Detail & Related papers  (2021-07-05T21:05:11Z)
• Rao-Blackwellizing the Straight-Through Gumbel-Softmax Gradient Estimator [93.05919133288161]
  We show that the variance of the straight-through variant of the popular Gumbel-Softmax estimator can be reduced through Rao-Blackwellization. This provably reduces the mean squared error. We empirically demonstrate that this leads to variance reduction, faster convergence, and generally improved performance in two unsupervised latent variable models.
  arXiv  Detail & Related papers  (2020-10-09T22:54:38Z)
• Manifold-adaptive dimension estimation revisited [0.0]
  We revisit and improve the manifold-adaptive Farahmand-Szepesv'ari-Audibert dimension estimator. We compute the probability density function of local FSA estimates. We derive the maximum likelihood formula for global intrinsic dimensionality.
  arXiv  Detail & Related papers  (2020-08-07T15:27:26Z)
• Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization [101.5159744660701]
  In distributed second order optimization, a standard strategy is to average many local estimates, each of which is based on a small sketch or batch of the data. Here, we introduce a new technique for debiasing the local estimates, which leads to both theoretical and empirical improvements in the convergence rate of distributed second order methods.
  arXiv  Detail & Related papers  (2020-07-02T18:08:14Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  We propose differentially private (DP) algorithms for bound non-dimensional optimization. We demonstrate two popular deep learning methods on the empirical advantages over standard gradient methods.
  arXiv  Detail & Related papers  (2020-06-24T06:01:24Z)
• A Convergent and Dimension-Independent Min-Max Optimization Algorithm [32.492526162436405]
  We show that a distribution which the min-player uses to update its parameters depends on a smooth and bounded nonnon-concave function. Our algorithm converges to an approximate local equilibrium in a number of iterations that does not depend on the iterations.
  arXiv  Detail & Related papers  (2020-06-22T16:11:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.