English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Frank-Wolfe methods are popular for optimization over a polytope. One of thereasons is because they do not need projection onto the polytope but onlylinear optimization over it. To understand its complexity, Lacoste-Julien andJaggi introduced a condition number for polytopes and showed linear convergencefor several variations of the method. The actual running time can still beexponential in the worst case (when the condition number is exponential). Westudy the smoothed complexity of the condition number, namely the conditionnumber of small random perturbations of the input polytope and show that it ispolynomial for any simplex and exponential for general polytopes. Our resultsalso apply to other condition measures of polytopes that have been proposed forthe analysis of Frank-Wolfe methods: vertex-facet distance (Beck and Shtern)and facial distance (Pe\~na and Rodr\'iguez).  Our argument for polytopes is a refinement of an argument that we develop tostudy 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 highprobability. This has consequences on results about the robust uniqueness oftensor decompositions.

The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes