论文标题
弗兰克 - 沃尔夫方法的平滑复杂性通过随机矩阵和多面体的调节
The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes
论文作者
论文摘要
Frank-Wolfe方法是在多层室中优化的流行。原因之一是因为它们不需要投影到多型物体上，而只需要对其进行线性优化。为了了解其复杂性，Lacoste-Julien和Jaggi引入了多面体的条件号，并显示了该方法几种变化的线性收敛。在最坏的情况下（条件号为指数时），实际运行时间仍然可能是指数的。我们研究了条件数的平滑复杂性，即输入多层的小小型随机扰动的条件数量，并表明它对于任何单纯形成了多项式，对于一般多层型都是多项式的。我们的结果还适用于已提出用于分析弗兰克 - 沃尔夫方法的其他多面有条件：顶点 - 面距离（贝克和shter）和面部距离（Peña和Rodríguez）。 我们对多面体的论点是对我们发展以研究随机矩阵条件的论点的改进。基本参数表明，对于$ c>> 1 $ a $ d $ -n $ n $随机高斯矩阵，带有$ n \ geq cd $具有$ d $ -by-d $ d $ subbastrix，其最低奇异值呈指数较小，概率很高。这对张量分解的稳健唯一性的结果产生了影响。
Frank-Wolfe methods are popular for optimization over a polytope. One of the reasons is because they do not need projection onto the polytope but only linear optimization over it. To understand its complexity, Lacoste-Julien and Jaggi introduced a condition number for polytopes and showed linear convergence for several variations of the method. The actual running time can still be exponential in the worst case (when the condition number is exponential). We study the smoothed complexity of the condition number, namely the condition number of small random perturbations of the input polytope and show that it is polynomial for any simplex and exponential for general polytopes. Our results also apply to other condition measures of polytopes that have been proposed for the analysis of Frank-Wolfe methods: vertex-facet distance (Beck and Shtern) and facial distance (Peña and Rodríguez). Our argument for polytopes is a refinement of an argument that we develop to study the conditioning of random matrices. The basic argument shows that for $c>1$ a $d$-by-$n$ random Gaussian matrix with $n \geq cd$ has a $d$-by-$d$ submatrix with minimum singular value that is exponentially small with high probability. This has consequences on results about the robust uniqueness of tensor decompositions.
