arXiv：cs.LG· Zhe Zhang, Suvrit Sra·· 4 小时前
无需预知光滑区域：分段光滑问题的全局线性收敛算法
Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Regions
AI 导读
研究提出针对光滑区域未知的分段光滑（PWS）函数的优化算法：对满足二次增长（QG）条件的凸 PWS 函数，bundle-level（BL）型方法实现全局线性收敛，作者称这是该问题类的首个此类结果。方法被扩展到弱凸 PWS 问题，复杂度与光滑非凸优化同阶，并引入无需问题参数即可验证的终止判据，嵌入 guess-and-check 框架后得到近乎无参数的算法。
正文
Abstract:We develop efficient algorithms for optimizing piecewise smooth (PWS) functions when their smooth regions are \emph{unknown} to the algorithm. For convex PWS functions satisfying a quadratic growth (QG) condition, we demonstrate that the bundle-level (BL)-type method~\cite{lemarechal1995new} achieves global linear convergence---to our knowledge, the first such result for any algorithm for this problem class. We extend the method to solve weakly convex PWS problems, achieving the same order of complexity as in smooth non-convex optimization. Furthermore, we introduce a verifiable and accurate termination criterion for PWS optimization. Like the gradient norm in smooth optimization, this certificate tightly characterizes the optimality gap under the QG condition and can 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 almost parameter-free algorithms for both convex QG and weakly convex PWS problems.
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG) |
| Cite as: | arXiv:2507.19465 [math.OC] |
| (or arXiv:2507.19465v2 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2507.19465 arXiv-issued DOI via DataCite |
Submission history
From: Zhe Zhang [view email]
[v1]
Fri, 25 Jul 2025 17:50:43 UTC (1,363 KB)
[v2]
Tue, 13 Oct 2026 23:13:52 UTC (1,349 KB)
来源：arXiv：cs.LG · arxiv.org