首次实现非光滑分段函数优化的线性收敛，无需知道分段结构。
Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Pieces
- 基于束层级方法，无须预先知晓分段信息即可优化分段光滑函数。
- 在满足二次增长条件下实现全局线性收敛，优于现有最优复杂度。
- 提出可验证的终止准则，几乎不依赖参数，适合实际应用。
我们为分段光滑（PWS）函数优化开发了高效算法，其中域的光滑分段划分未知。对于满足二次增长（QG）条件的PWS函数，提出一种束层级（BL）型方法，实现全局线性收敛——据我们所知，这是该问题类别中首个此类结果。将该方法扩展至近似PWS函数及弱凸PWS问题，使复杂度达到平滑非凸优化的基准水平。此外，首次提出可验证且精确的终止准则，在QG条件下其紧致刻画最优性差距，且无需已知问题参数即可评估。通过设计搜索子程序并嵌入猜-检框架，构建出几乎无需参数的算法，适用于凸QG与弱凸场景。
原文摘要 · Abstract (English)
We develop efficient algorithms for optimizing piecewise smooth (PWS) functions where the underlying partition of the domain into smooth pieces is \emph{unknown}. For PWS functions satisfying a quadratic growth (QG) condition, we propose a bundle-level (BL) type method that achieves global linear convergence -- to our knowledge, the first such result for any algorithm for this problem class. We extend this method to handle approximately PWS functions and to solve weakly-convex PWS problems, improving the state-of-the-art complexity to match the benchmark for smooth non-convex optimization. Furthermore, we introduce the first verifiable and accurate termination criterion for PWS optimization. Similar to the gradient norm in smooth optimization, this certificate tightly characterizes the optimality gap under the QG condition, and can moreover be evaluated without knowledge of any problem parameters. We develop a search subroutine for this certificate and embed it within a guess-and-check framework, resulting in an almost parameter-free algorithm for both the convex QG and weakly-convex settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。