We study the computational aspects of the task of multivariate convex regression in dimension $d \geq 5$. We present the first computationally efficient minimax optimal (up to logarithmic factors) estimators for the tasks of (i) $L$-Lipschitz convex regression (ii) $\Gamma$-bounded convex regression under polytopal support. The proof of the correctness of these estimators uses a variety of tools from different disciplines, among them empirical process theory, stochastic geometry, and potential theory. This work is the first to show the existence of efficient minimax optimal estimators for non-Donsker classes that their corresponding Least Squares Estimators are provably minimax sub-optimal; a result of independent interest.
翻译:我们用 $d\ geq 5$ 来研究多变量共振回归任务的计算方面。 我们展示了第一个计算高效的小型最大最佳( 直至对数系数) 估计器, 用于以下任务:(一) $L$- Lipschitz convex 回归 (二) $\\Gamma$- 绑定 convex回归在多面支持下。 证明这些估计器正确性的证据使用了来自不同学科的各种工具, 包括实证过程理论、 随机几何和潜在理论。 这项工作首先展示了非唐氏类的有效小型最佳估测器的存在, 其相应的最小广场模拟器具有可辨称的微缩成形亚最佳; 这是独立兴趣的结果 。