We propose and analyze asymptotic proximal point (APP) methods to find the global minimizer for a class of nonconvex, nonsmooth, or even discontinuous multiple minima functions. The method is based on an asymptotic representation of nonconvex proximal points so that it can find the global minimizer without being trapped in saddle points, local minima, or even discontinuities. Our main result shows that the method enjoys the global linear convergence for such a class of functions. Furthermore, the method is derivative-free and its per-iteration cost, i.e., the number of function evaluations, is also bounded, so it has a complexity bound $\mathcal{O}(\log\frac{1}{\epsilon})$ for finding a point such that the gap between this point and the global minimizer is less than $\epsilon>0$. Numerical experiments and comparisons in various dimensions from $2$ to $500$ demonstrate the benefits of the method.


翻译:我们提出并分析无症状准点(APP) 方法, 以找到某类非convex、 非smooth、 甚至不连续的多重微型函数的全球最小化器。 方法基于非convex 准点的无症状代表, 这样它就可以找到全球最小化器, 而不被困在马鞍点、 本地微型, 甚至不连续 。 我们的主要结果表明, 该方法拥有这一类函数的全球线性趋同 。 此外, 该方法是无衍生的, 其每层成本, 即功能评估的数量也受约束, 所以它有一个复杂性绑定 $\ mathcal{O} (\log\ frac{1\ unsilon}), 以便找到一个点, 这个点与全球最小化器之间的差距小于 $\ epsilon > 0 。 数值实验和不同层面的比较, 从 $2美元到 500美元不等的数值实验和比较, 证明了该方法的好处 。

0
下载
关闭预览

相关内容

Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
111+阅读 · 2020年5月15日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
60+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
181+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
已删除
将门创投
4+阅读 · 2017年12月5日
Arxiv
0+阅读 · 2021年2月26日
Arxiv
0+阅读 · 2021年2月26日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
已删除
将门创投
4+阅读 · 2017年12月5日
Top
微信扫码咨询专知VIP会员