论文标题
大约确切的线路搜索
Approximately Exact Line Search
论文作者
论文摘要
我们提出了大约确切的线路搜索（AELS），该搜索仅使用函数评估来在单峰目标的确切线搜索最小化器的恒定分数中选择一个步长。我们绑定了AELS的迭代次数和功能评估的数量，显示了平滑，强烈凸目标上的线性收敛性，不依赖三种下降方法的初始步骤大小：使用真实梯度，使用梯度近似和随机方向搜索的真实梯度，最陡峭的下降最陡峭的下降。与Armijo线搜索和其他基线相比，我们证明了实验速度，以及其他使用Quasi-Newton搜索指示的梯度下降和Minibatch随机梯度下降以及Minibatch随机梯度下降以及基准的无衍生化优化目标的基准。我们还分析了一条简单的线路搜索强大的狼条件，找到了类似于AEL的迭代和功能评估复杂性的上限。在实验上，我们发现AELS在确定性和随机的Minibatch逻辑回归上的速度要快得多，而Wolfe Line搜索在DFO基准上的速度略快。我们的发现表明，尤其是线条搜索和AEL可能比通常认为的随机优化方案更有用。
We propose approximately exact line search (AELS), which uses only function evaluations to select a step size within a constant fraction of the exact line search minimizer of a unimodal objective. We bound the number of iterations and function evaluations of AELS, showing linear convergence on smooth, strongly convex objectives with no dependence on the initial step size for three descent methods: steepest descent using the true gradient, approximate steepest descent using a gradient approximation, and random direction search. We demonstrate experimental speedup compared to Armijo line searches and other baselines on weakly regularized logistic regression for both gradient descent and minibatch stochastic gradient descent and on a benchmark set of derivative-free optimization objectives using quasi-Newton search directions. We also analyze a simple line search for the strong Wolfe conditions, finding upper bounds on iteration and function evaluation complexity similar to AELS. Experimentally we find AELS is much faster on deterministic and stochastic minibatch logistic regression, whereas Wolfe line search is slightly faster on the DFO benchmark. Our findings suggest that line searches and AELS in particular may be more useful in the stochastic optimization regime than commonly believed.
