Golden-section search and bisection search are the two main principled
algorithms for 1d minimization of quasiconvex (unimodal) functions. The first
one only uses function queries, while the second one also uses gradient
queries. Other algorithms exist under much stronger assumptions, such as
Newton's method. However, to the best of our knowledge, there is no principled
exact line search algorithm for general convex functions -- including
piecewise-linear and max-compositions of convex functions -- that takes
advantage of convexity. We propose two such algorithms: $\Delta$-Bisection is a
variant of bisection search that uses (sub)gradient information and convexity
to speed up convergence, while $\Delta$-Secant is a variant of golden-section
search and uses only function queries.
While bisection search reduces the $x$ interval by a factor 2 at every
iteration, $\Delta$-Bisection reduces the (sometimes much) smaller $x^*$-gap
$\Delta^x$ (the $x$ coordinates of $\Delta$) by at least a factor 2 at every
iteration. Similarly, $\Delta$-Secant also reduces the $x^*$-gap by at least a
factor 2 every second function query. Moreover, the $y^*$-gap $\Delta^y$ (the
$y$ coordinates of $\Delta$) also provides a refined stopping criterion, which
can also be used with other algorithms. Experiments on a few convex functions
confirm that our algorithms are always faster than their quasiconvex
counterparts, often by more than a factor 2.
We further design a quasi-exact line search algorithm based on
$\Delta$-Secant. It can be used with gradient descent as a replacement for
backtracking line search, for which some parameters can be finicky to tune --
and we provide examples to this effect, on strongly-convex and smooth
functions. We provide convergence guarantees, and confirm the efficiency of
quasi-exact line search on a few single- and multivariate convex functions.

提出了两种使用凸性来加速收敛的具有指导意义的准确线搜索算法，其中一种使用函数查询，而另一种还使用梯度查询。在一些凸函数上的实验证实了这些算法通常快于其凸单峰函数对应的算法超过两倍，并提供了收敛保证。

凸优化的线搜索

Line Search for Convex Minimization

We extend the well-known BFGS quasi-Newton method and its memory-limited
variant LBFGS to the optimization of nonsmooth convex objectives. This is done
in a rigorous fashion by generalizing three components of BFGS to
subdifferentials: the local quadratic model, the identification of a descent
direction, and the Wolfe line search conditions. We prove that under some
technical conditions, the resulting subBFGS algorithm is globally convergent in
objective function value. We apply its memory-limited variant (subLBFGS) to
L_2-regularized risk minimization with the binary hinge loss. To extend our
algorithm to the multiclass and multilabel settings, we develop a new,
efficient, exact line search algorithm. We prove its worst-case time complexity
bounds, and show that our line search can also be used to extend a recently
developed bundle method to the multiclass and multilabel settings. We also
apply the direction-finding component of our algorithm to L_1-regularized risk
minimization with logistic loss. In all these contexts our methods perform
comparable to or better than specialized state-of-the-art solvers on a number
of publicly available datasets. An open source implementation of our algorithms
is freely available.

本研究将众所周知的 BFGS 拟牛顿方法及其内存限制变种 LBFGS 扩展到非平滑凸目标的优化，提出了 subBFGS 算法，其全局收敛，并使用其记忆限制变体（subLBFGS）来最小化 L2 正则化风险并开发了新的多类和多标签设置下的准确搜索算法。