Safe Grid Search with Optimal Complexity
Safe Grid Search with Optimal Complexity
复制标题
DOI：
--
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Eugène Ndiaye;Tam Le;Olivier Fercoq;J. Salmon;I. Takeuchi
中科院分区：
文献类型：
--
作者：
Eugène Ndiaye;Tam Le;Olivier Fercoq;J. Salmon;I. Takeuchi
流行的机器学习估计器涉及正则化参数，这些参数可能很难调优，而标准策略依赖于网格搜索来完成这项任务。在本文中，我们重新讨论了在统一框架中逼近正则化路径到预定义容差$\epsilon$的技术，并证明了其复杂度对于阶为$d \geq 2$的一致凸损失和对于广义自洽函数的复杂度分别为$O(1/\sqrt[d]{\epsilon})$和$O(1/\sqrt{\epsilon})$。这个框架包括最小二乘，也包括逻辑回归，据我们所知，这种情况在以前的作品中没有得到精确的处理。我们利用我们的技术为验证误差提供了精确的界限，并为超参数调优提供了实用的算法。后者在验证集上以指定精度为目标时具有全局收敛性保证。最后但并非最不重要的是，我们的方法帮助从业者从（经常被忽视的）在优化训练集时选择停止标准的任务中解脱出来：我们的方法根据验证集上的目标精度自动校准该标准。
Popular machine learning estimators involve regularization parameters that can be challenging to tune, and standard strategies rely on grid search for this task. In this paper, we revisit the techniques of approximating the regularization path up to predefined tolerance $\epsilon$ in a unified framework and show that its complexity is $O(1/\sqrt[d]{\epsilon})$ for uniformly convex loss of order $d \geq 2$ and $O(1/\sqrt{\epsilon})$ for Generalized Self-Concordant functions. This framework encompasses least-squares but also logistic regression, a case that as far as we know was not handled as precisely in previous works. We leverage our technique to provide refined bounds on the validation error as well as a practical algorithm for hyperparameter tuning. The latter has global convergence guarantee when targeting a prescribed accuracy on the validation set. Last but not least, our approach helps relieving the practitioner from the (often neglected) task of selecting a stopping criterion when optimizing over the training set: our method automatically calibrates this criterion based on the targeted accuracy on the validation set.