In this paper, we study the Kurdyka-{\L}ojasiewicz (KL) exponent, an important quantity for analyzing the convergence rate of first-order methods. Specifically, we develop various calculus rules to deduce the KL exponent of new (possibly nonconvex and nonsmooth) functions formed from functions with known KL exponents. In addition, we show that the well-studied Luo-Tseng error bound together with a mild assumption on the separation of stationary values implies that the KL exponent is $\frac12$. The Luo-Tseng error bound is known to hold for a large class of concrete structured optimization problems, and thus we deduce the KL exponent of a large class of functions whose exponents were previously unknown. Building upon this and the calculus rules, we are then able to show that for many convex or nonconvex optimization models for applications such as sparse recovery, their objective function's KL exponent is $\frac12$. This includes the least squares problem with smoothly clipped absolute deviation (SCAD) regularization or minimax concave penalty (MCP) regularization and the logistic regression problem with $\ell_1$ regularization. Since many existing local convergence rate analysis for first-order methods in the nonconvex scenario relies on the KL exponent, our results enable us to obtain explicit convergence rate for various first-order methods when they are applied to a large variety of practical optimization models. Finally, we further illustrate how our results can be applied to establishing local linear convergence of the proximal gradient algorithm and the inertial proximal algorithm with constant step-sizes for some specific models that arise in sparse recovery.


翻译:在本文中, 我们研究 Kurdyka- {L} ojasiewicz (KL) exponent, 这是分析一级方法趋同率的重要数量。 具体地说, 我们开发了各种计算规则, 以推断由已知 KL Exponent 函数构成的新功能( 可能非 convex 和非 smooth) 的 KL Exponent 。 此外, 我们显示, 精心研究的 Luo- Tseng 错误, 加上对固定值分离的轻度假设, 意味着 KL exponent 是 $\ frac12$。 Luo- Tseng 错误组合是已知的, 用来控制大量具体结构优化问题的 KLLL Excregional, 因此我们推导出大量功能的 KLLL exponalent expregionalal 。 以此方法可以显示, 对于许多配置或非conforal 优化的应用程序来说, 它们的目标函数是首次应用 $\\ conforxxxxxxxx 。 。 rolation rocal rolation rolation rolation rolation 。 。 最后, rolal rolational rolation rolation rolal rolal rolation rolation roal a fal 和 rolation rogal rolation rolup rolation 。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2021年8月8日
剑桥大学《数据科学: 原理与实践》课程,附PPT下载
专知会员服务
49+阅读 · 2021年1月20日
【ACML2020】张量网络机器学习:最近的进展和前沿,109页ppt
专知会员服务
54+阅读 · 2020年12月15日
专知会员服务
50+阅读 · 2020年12月14日
已删除
将门创投
5+阅读 · 2019年6月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关资讯
已删除
将门创投
5+阅读 · 2019年6月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Top
微信扫码咨询专知VIP会员