Non-Parametric Estimation under Shape/Norm Constraints

这个项目是关于推进方法论和对某些算法的理论理解，这些算法目前在机器学习和统计学中广泛使用。决策树是一种重要的预测建模方法。它们有着悠久的历史，像随机森林这样的现代变体是可用的最强大的技术之一。该项目的一部分将开发新的理论上合理的决策树，并辅之以软件实施。该项目的另一部分适用于信号处理。全变差去噪是图像处理中常用的去噪方法。目前的算法并不是完全自动化的。该项目将开发该算法的全自动版本，这在理论上是有效的。从更大的角度来看，这项研究将产生这些经过时间考验的算法的改进版本，我们对它们如何工作以及为什么工作的理解将得到完善。该项目的一个主要焦点是研究高维非光滑函数的非参数估计，如分段常数/线性/多项式函数。这里的一个主要议程是为Cart式估计器提供理论保证。这些保证将证明对回归函数的矩形水平集的数目和排列具有适应性。文献中对CART类估计量的这种适应性的理论理解在很大程度上是缺失的，这项研究应该是填补这一空白的第一步。在这个项目中，提出了一种扩展的并元CART估计器，称为模型选择CART(MS CART)，作为一种在计算上和理论上易于处理的方法来实现期望的自适应性。我们已经开发了一个基于动态规划方法的算法(将被实现并公开可用)，它可以被证明有效地计算MS CART估计器。我们目前正在为MS Cart提供理论上的保证。该提案的另一个主要重点是研究全变差去噪(TVD)的方法。该技术是一种广泛应用于图像处理领域的非线性图像去噪技术。本提案在这一专题下谈到的第一个问题是朝着严格理解TVD估计器的统计风险迈出的一步。对这种风险的最坏情况分析现在在文献中得到了很好的理解。本文提出的研究将超越最坏情况分析，并揭示TVD估计器的适应性。第二个提出的问题涉及以完全数据驱动的方式选择TVD的调谐参数的非常实际的问题。本文提出了一种新的无参数调谐估值器，它的实际性能已经在仿真中得到了彻底的检验。我们将证明我们提出的估计器是最小极大速率最优的，同时完全是数据驱动的。到目前为止，文献中还没有这样的估计值。这种估计器有可能使TVD方法比现在更加用户友好，因为选择调优参数可能是一个微妙的问题。PI还将解决分位数回归和一般指数族等环境中的几个非参数估计问题。特别是，这里的一个议程是研究分位数回归中的形状约束估计，这将是超越现有文献中经常做出的限制性线性假设的第一步。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

This project is about advancing methodology and theoretical understanding of certain algorithms that are widely used today in machine learning and statistics. Decision Trees are an important type of predictive modelling method. They have a long history and modern variations like random forest are among the most powerful techniques available. One part of the project would develop new and theoretically sound decision trees accompanied by software implementation. The other part of the project applies to signal processing. Total Variation Denoising is a popular method used in image processing to do noise removal. The current algorithm as it stands, is not fully automated. This project would develop a fully automated version of this algorithm which is theoretically valid. In the bigger picture, the research would generate improved versions of these time tested algorithms and our understanding of how and why they work would be refined. A main focus of the project is to study non parametric estimation of non smooth functions such as piecewise constant/linear/polynomial functions, in high dimensions. One major agenda here is to give theoretical guarantees for CART like estimators. These guarantees would provably demonstrate adaptivity to the number and arrangement of rectangular level sets of the regression function. Theoretical understanding of such adaptivity for CART like estimators are largely absent in the literature and this research should be a first step towards filling this gap. In this project, an extension of the Dyadic CART estimator, called Model Selection Cart (MS Cart) is proposed as a computationally and theoretically tractable method to achieve the desired adaptivity. We have already developed an algorithm (to be implemented and made publicly available), based on a dynamic programming approach, which provably computes the MS Cart estimator efficiently. We are currently working on showing theoretical guarantees for MS Cart. Another main focus of the proposal is to study the methodology of Total Variation Denoising (TVD). This technique is a non linear image denoising technique heavily used in the image processing community. The first problem talked about in this proposal, under this topic, is a step towards rigorous understanding of the statistical risk of the TVD estimator. Worst case analysis of this risk is now well understood in the literature. The research proposed here will go beyond worst case analysis and reveal the adaptivity of the TVD estimator. The second proposed problem deals with the very practical issue of choosing the tuning parameter for TVD in a fully data driven way. A new tuning parameter free estimator is proposed here whose practical performance has been thoroughly checked by us in simulations. We will show that our proposed estimator is minimax rate optimal while being fully data driven. Such an estimator is not available in the literature, as of now. This estimator has the potential to make the TVD methodology much more user friendly than it already is as choosing a tuning parameter can be a delicate issue. The PI will also address several non parametric estimation problems in settings such as quantile regression and in general exponential families. In particular, one agenda here is to study shape constrained estimation in quantile regression which would be a first step towards going beyond restrictive linear assumptions often made in the existing literature.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.