提出一种高效算法，可精准估计未知的 Lipschitz 函数。
Near-optimal Delta-convex Estimation of Lipschitz Functions
- 用非线性特征扩展将分段线性函数映射为 delta-凸函数，逼近 Lipschitz 函数。
- 在随机设计下达到最优收敛率（对数因子内），无需已知真实 Lipschitz 常数。
- 适用于高维数据，适合需要理论保障的回归任务，如医疗或金融建模。
本文提出一种可计算的算法，用于从噪声观测中估计未知的 Lipschitz 函数，并建立了其收敛速率的上界。该方法将最大仿射方法从凸形状约束回归推广至更一般的 Lipschitz 设置。核心是通过非线性特征扩展，将最大仿射函数映射到 delta-凸函数子类，该类函数可作为 Lipschitz 函数的通用近似器，同时保持 Lipschitz 常数不变。利用此性质，该估计器在平方损失和子高斯分布的随机设计下，达到关于数据内在维度的极小极大收敛率（对数因子内）。算法结合自适应划分以捕捉内在维度、基于惩罚的正则化机制（无需知道真实 Lipschitz 常数），以及两阶段优化：先进行凸初始化，再局部精修。该框架亦可直接应用于凸形状约束回归。实验表明，其性能优于其他具有理论保障的方法，包括最近邻与核回归方法。
原文摘要 · Abstract (English)
This paper presents a tractable algorithm for estimating an unknown Lipschitz function from noisy observations and establishes an upper bound on its convergence rate. The approach extends max-affine methods from convex shape-restricted regression to the more general Lipschitz setting. A key component is a nonlinear feature expansion that maps max-affine functions into a subclass of delta-convex functions, which act as universal approximators of Lipschitz functions while preserving their Lipschitz constants. Leveraging this property, the estimator attains the minimax convergence rate (up to logarithmic factors) with respect to the intrinsic dimension of the data under squared loss and subgaussian distributions in the random design setting. The algorithm integrates adaptive partitioning to capture intrinsic dimension, a penalty-based regularization mechanism that removes the need to know the true Lipschitz constant, and a two-stage optimization procedure combining a convex initialization with local refinement. The framework is also straightforward to adapt to convex shape-restricted regression. Experiments demonstrate competitive performance relative to other theoretically justified methods, including nearest-neighbor and kernel-based regressors.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。