We develop a framework for the average-case analysis of random quadratic problems and derive algorithms that are optimal under this analysis. This yields a new class of methods that achieve acceleration given a model of the Hessian's eigenvalue distribution. We develop explicit algorithms for the uniform, Marchenko-Pastur, and exponential distributions. These methods are momentum-based algorithms, whose hyper-parameters can be estimated without knowledge of the Hessian's smallest singular value, in contrast with classical accelerated methods like Nesterov acceleration and Polyak momentum. Through empirical benchmarks on quadratic and logistic regression problems, we identify regimes in which the the proposed methods improve over classical (worst-case) accelerated methods.


翻译:我们开发了随机二次问题平均分析框架, 并得出了根据本分析最理想的算法。 这产生了一种新的方法, 有了赫西安的二元值分布模型, 加速了 。 我们为制服、 Marchenko- Pastur 和指数分布开发了明确的算法 。 这些方法都是基于动力的算法, 在不了解赫西安人最小单值的情况下, 其超参数可以被估计, 与古典加速法( Nesterov 加速法 ) 和 Polyak 动力法( Polyak 动力法) 不同。 通过关于二次回归和物流回归问题的经验基准, 我们找出了拟议方法比古典( 微量) 加速法改进的制度 。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
专知会员服务
159+阅读 · 2020年1月16日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【推荐】卷积神经网络类间不平衡问题系统研究
机器学习研究会
6+阅读 · 2017年10月18日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
On Variance Estimation of Random Forests
Arxiv
0+阅读 · 2022年2月18日
Arxiv
4+阅读 · 2021年7月1日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
专知会员服务
159+阅读 · 2020年1月16日
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【推荐】卷积神经网络类间不平衡问题系统研究
机器学习研究会
6+阅读 · 2017年10月18日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员