用差值最大仿射函数表示分段线性回归，实现高维下近优解。
Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions
- 将分段线性函数建模为两个最大仿射函数之差，设计自适应块梯度下降算法。
- 在噪声方差σ²ₙ条件下，仅需约O~(d)个样本即可精确恢复模型。
- 理论证明收敛速率接近最优，且在真实数据上表现优于主流方法。
本文提出一种基于自适应块梯度下降（ABGD）的分段线性回归参数化方法，核心思想是将分段线性函数表示为最大仿射函数之差（DoMA）。在亚高斯协变量和噪声分布下，提供了非渐近局部收敛分析。通过改进已有最大仿射函数初始化算法，使ABGD在适当初始化后以线性速度收敛至ε-精度估计，所需样本量为$ ilde{/mathcal{O}}(d ext{max}(σ_z/ε,1)^2)$，其中$σ_z^2$为噪声方差。当噪声为零时，仅需$ ilde{/mathcal{O}}(d)$样本即可实现精确恢复，且该采样率在对数因子意义下达到极小极大最优。合成实验验证了理论结果，真实数据集上表现亦优于当前先进方法。
原文摘要 · Abstract (English)
This paper presents a parametric solution to piecewise linear regression through the Adaptive Block Gradient Descent (ABGD) algorithm. The heart of the method is the parametrization of piecewise linear functions as the difference of max-affine (DoMA) functions. A non-asymptotic local convergence analysis for ABGD is provided under sub-Gaussian covariate and noise distributions. To initialize ABGD, we adapt a prior algorithm originally developed for the simpler setting of max-affine functions. When suitably initialized, ABGD converges linearly to an $ε$-accurate estimate given $\tilde{\mathcal{O}}(d\max(σ_z/ε,1)^2)$ observations where $σ_z^2$ denotes the noise variance. This implies exact recovery given $\tilde{\mathcal{O}}(d)$ samples in the noiseless case. Also, such a rate is shown to be minimax optimal up to logarithmic factors. Synthetic numerical results corroborate the theoretical guarantees for ABGD. We also observe competitive performance compared to the state-of-the-art methods on real-world datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。