论文标题
条件梯度类型方法的下限，以最大程度地降低强烈凸功能
Lower bounds for conditional gradient type methods for minimizing smooth strongly convex functions
论文作者
论文摘要
在本文中，我们考虑条件梯度方法。这些方法是使用线性最小化甲骨文的方法，对于给定的向量$ p \ in \ mathbb {r}^n $，计算了子问题$$ $ \ arg arg \ min_ {x} {x} {\ langle p，x \ rangle}的解决方案。但是，在所有这些方法中，问题的维度都包含在收敛速率中，在现代应用中，这可能很大。在本文中，我们证明在强烈凸的情况下，最佳情况下条件梯度方法的收敛速率取决于问题$ n $的维度$ n $作为$ \ widetildemω（\ sqrt {n}）$。因此，有条件的梯度方法可能无法有效地解决大尺寸的强烈凸优化问题。同样，还考虑了将条件梯度方法应用于最小化二次形式的问题。 弗兰克·沃尔夫（Frank-Wolfe）方法在单纯化（pagerank）上解决二次优化问题的有效性已经被证明。这项工作表明，使用条件梯度方法在强凸状情况下解决二次形式的最小化问题是由于这些方法的收敛速率存在维度而无效的。因此，考虑了收缩条件梯度方法。它与条件梯度方法的差异是它使用了修改的线性最小化甲骨文。这种算法的收敛速率不取决于维度。使用缩小条件梯度方法，可以在$ \ infty $ -ball上解决二次形式的最小化问题的复杂性。该方法的结果评估与梯度方法的复杂性相当。
In this paper, we consider conditional gradient methods. These are methods that use a linear minimization oracle, which, for a given vector $p \in \mathbb{R}^n$, computes the solution of the subproblem $$\arg \min_{x\in X}{\langle p,x \rangle}.$$ There are a variety of conditional gradient methods that have a linear convergence rate in a strongly convex case. However, in all these methods, the dimension of the problem is included in the rate of convergence, which in modern applications can be very large. In this paper, we prove that in the strongly convex case, the convergence rate of the conditional gradient methods in the best case depends on the dimension of the problem $ n $ as $ \widetilde Ω (\sqrt {n}) $. Thus, the conditional gradient methods may turn out to be ineffective for solving strongly convex optimization problems of large dimensions. Also, the application of conditional gradient methods to minimization problems of a quadratic form is considered. The effectiveness of the Frank-Wolfe method for solving the quadratic optimization problem in the convex case on a simplex (PageRank) has already been proved. This work shows that the use of conditional gradient methods to solve the minimization problem of a quadratic form in a strongly convex case is ineffective due to the presence of dimension in the convergence rate of these methods. Therefore, the Shrinking Conditional Gradient method is considered. Its difference from the conditional gradient methods is that it uses a modified linear minimization oracle. The convergence rate of such an algorithm does not depend on dimension. Using the Shrinking Conditional Gradient method the complexity of solving the minimization problem of quadratic form on a $ \infty $-ball is obtained. The resulting evaluation of the method is comparable to the complexity of the gradient method.
