Minmax Trend Filtering: A Locally Adaptive Nonparametric Regression Method via Pointwise Min Max Optimization

• URL: http://arxiv.org/abs/2410.03041v1
• Date: Thu, 3 Oct 2024 23:15:35 GMT
• Title: Minmax Trend Filtering: A Locally Adaptive Nonparametric Regression Method via Pointwise Min Max Optimization
• Authors: Sabyasachi Chatterjee,
• Abstract summary: There seems to be no unanimously agreed upon definition of local adaptivity in the literature. We first derive a new pointwise formula for the Fused Lasso estimator in terms of min-max/max-min optimization of penalized local averages. We then propose higher order versions of Fused Lasso which are defined pointwise in terms of min-max/max-min optimization of penalized local regressions.
• Score: 4.07926531936425
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Trend Filtering is a nonparametric regression method which exhibits local adaptivity, in contrast to a host of classical linear smoothing methods. However, there seems to be no unanimously agreed upon definition of local adaptivity in the literature. A question we seek to answer here is how exactly is Fused Lasso or Total Variation Denoising, which is Trend Filtering of order $0$, locally adaptive? To answer this question, we first derive a new pointwise formula for the Fused Lasso estimator in terms of min-max/max-min optimization of penalized local averages. This pointwise representation appears to be new and gives a concrete explanation of the local adaptivity of Fused Lasso. It yields that the estimation error of Fused Lasso at any given point is bounded by the best (local) bias variance tradeoff where bias and variance have a slightly different meaning than usual. We then propose higher order polynomial versions of Fused Lasso which are defined pointwise in terms of min-max/max-min optimization of penalized local polynomial regressions. These appear to be new nonparametric regression methods, different from any existing method in the nonparametric regression toolbox. We call these estimators Minmax Trend Filtering. They continue to enjoy the notion of local adaptivity in the sense that their estimation error at any given point is bounded by the best (local) bias variance tradeoff.

Related papers

• LASER: A new method for locally adaptive nonparametric regression [5.926203312586109]
  We introduce textsfLASER (Locally Adaptive Smoothing Estimator for Regression), a computationally efficient locally adaptive nonparametric regression method. We prove that it adapts (near-)optimally to the local H"older exponent of the underlying regression function textttsimultaneously at all points in its domain.
  arXiv  Detail & Related papers  (2024-12-27T18:59:03Z)
• 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)
• 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)
• 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)

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.