Near-optimal Delta-convex Estimation of Lipschitz Functions

Problem Statement
This paper addresses the fundamental problem of nonparametric regression in a random design setting. The goal is to estimate an unknown real-valued regression function $f^*$ from $n$ independent and identically distributed (i.i.d.) noisy observations $(X_i, Y_i)$, where $Y_i = f^*(X_i) + \xi_i$. The function $f^*$ is assumed to be $\lambda^*$-Lipschitz continuous on an unknown domain $X^* \subseteq \mathbb{R}^d$ with respect to the Euclidean norm, but the Lipschitz constant $\lambda^*$ is unknown. The performance of estimators is evaluated using the excess risk under squared loss. The theoretical benchmark for this problem is the minimax convergence rate of $\Theta(n^{-2/(2+d^*)})$, where $d^*$ is the intrinsic dimension of the data. While methods exist for convex shape-restricted regression (using max-affine functions) and for general Lipschitz regression (using nearest-neighbor or kernel methods), there is a gap in the literature regarding tractable algorithms for general Lipschitz functions that achieve near-minimax rates without requiring prior knowledge of $\lambda^*$ or external model selection procedures like cross-validation.

Methodology: Delta-Convex Fitting (DCF)
The authors propose a tractable algorithm called Delta-Convex Fitting (DCF). The core of the approach extends max-affine methods from convex regression to the general Lipschitz setting by utilizing a nonlinear feature expansion that maps functions into a subclass of delta-convex (DC) functions. DC functions are defined as the difference of two convex functions.

The algorithm proceeds in three main stages:

1. Adaptive Partitioning: The algorithm first computes a finite set of center points $\hat{X}_K$ using the Adaptive Farthest-Point Clustering (AFPC) method. This step adaptively determines the partition size $K$ based on the intrinsic dimension $d^*$ of the covariate data, aiming for $K \approx n^{d^*/(2+d^*)}$.
2. Convex Initialization: The algorithm solves a regularized empirical risk minimization (ERM) problem over a class of functions $F_p(\hat{X}_K)$. These functions are defined as the maximum of finitely many affine functions augmented with a norm term (e.g., $\|x - \hat{x}_k\|_p$). The optimization problem is a Second-Order Cone Program (SOCP) that is convex and solvable in polynomial time. Crucially, the algorithm imposes constraints only at the center points, resulting in $K^2$ constraints rather than the $nK$ constraints typical of similar methods, significantly reducing computational complexity.
3. Refinement and Pruning: An optional refinement step performs local optimization to minimize the empirical risk plus a penalty term, initialized at the convex solution. Finally, the algorithm prunes parameters that do not affect the empirical risk and centers the estimator to ensure the average response matches the data mean.

A key innovation is the regularization mechanism. The algorithm does not require knowledge of the true Lipschitz constant $\lambda^*$. Instead, it uses a penalty-based regularization that bounds the uniform Lipschitz constant of the estimator, allowing the method to adapt to the unknown smoothness of the target function.

Key Contributions

• Near-Optimal Convergence Rate: The paper establishes that the DCF estimator achieves a near-minimax convergence rate of $O(n^{-2/(2+d^*)} \cdot \text{polylog}(n))$ with respect to the intrinsic dimension $d^*$, under squared loss and subgaussian noise assumptions. This holds for subgaussian distributions in the random design setting.
• Tractability: Unlike previous approaches to Lipschitz regression that may rely on non-convex optimization or lack theoretical guarantees, DCF formulates the estimation as a tractable convex optimization problem (SOCP).
• Adaptivity without External Selection: The method adapts to the intrinsic dimension of the data via the AFPC step and does not rely on external model selection procedures (such as cross-validation or sample splitting) to attain near-optimal guarantees.
• Unknown Lipschitz Constant: The algorithm operates without requiring prior knowledge of the Lipschitz constant $\lambda^*$, a significant advantage over methods that require uniform bounds on the function or its derivatives.
• Extension to Convex Regression: The framework is shown to be adaptable to convex shape-restricted regression, providing a Probably Approximately Correct (PAC) bound for all $n \geq 2$ without knowing $\lambda^*$, improving upon existing results that were limited to specific dimensions or asymptotic probability bounds.

Results and Experimental Performance
Theoretical analysis confirms that the DCF estimator, when using specific regularization parameters, satisfies the near-minimax rate. The proof relies on the approximation properties of the function class $F_p(\hat{X}_K)$, which can uniformly approximate any Lipschitz function with an error proportional to the covering radius of the center points.

Experimental evaluations on the Delve Project datasets (cpusmall, pumadyn-8nm, pumadyn-8nh) compare DCF against k-nearest neighbors (k-NN), Nadaraya-Watson (NW) kernel regression, Ordinary Least Squares (OLS), Random Forests (RF), and XGBoost.

• DCF variants using symmetric function classes (delta-max-affine) achieved Mean Squared Errors (MSE) competitive with or superior to k-NN and NW, and comparable to tree-based methods (RF, XGBoost).
• The experiments highlight the sensitivity of DCF to the regularization parameter $\theta_2$. A stronger regularizer prevents overfitting in noisy settings but may lead to underfitting if the partition size is small.
• Computationally, DCF training times are comparable to kernel methods (NW) for moderate sample sizes, and inference is fast due to parameter pruning.

Significance
The paper claims to fill a critical gap in the literature by providing the first tractable method for estimating general Lipschitz functions that achieves a near-minimax rate in the random design setting without requiring knowledge of the Lipschitz constant or external model selection. By extending max-affine methods to the delta-convex setting, the authors bridge the gap between the theoretical optimality of convex regression and the broader applicability required for general Lipschitz functions. The work demonstrates that it is possible to construct estimators that are both computationally efficient (polynomial time) and statistically optimal (near-minimax), offering a robust alternative to partitioning-based or kernel-based methods that often require heuristic tuning or lack such strong theoretical guarantees.