Page MenuHomec4science
Files F69410443

journal_main.aux
No OneTemporary
Actions

File Metadata

Created
Mon, Jul 1, 16:31

journal_main.aux
View Options

\relax
\providecommand\hyper@newdestlabel[2]{}
\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
\global\let\oldcontentsline\contentsline
\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global\let\oldnewlabel\newlabel
\gdef\newlabel#1#2{\newlabelxx{#1}#2}
\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\ifx\hyper@anchor\@undefined
\let\contentsline\oldcontentsline
\let\newlabel\oldnewlabel
\fi}
\fi}
\global\let\hyper@last\relax
\gdef\HyperFirstAtBeginDocument#1{#1}
\providecommand\HyField@AuxAddToFields[1]{}
\providecommand\HyField@AuxAddToCoFields[2]{}
\citation{khot2011grothendieck,lovasz2003semidefinite}
\citation{mossel2015consistency,song2007dependence}
\citation{singer2011angular,singer2011three}
\citation{raghavendra2008optimal}
\citation{yurtsever2018conditional}
\citation{burer2003nonlinear,burer2005local}
\citation{pataki1998rank,barvinok1995problems}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{2}{section.1}}
\newlabel{intro}{{1}{2}{Introduction}{section.1}{}}
\newlabel{prob:01}{{1}{2}{Introduction}{equation.1.1}{}}
\newlabel{eq:smoothness basic}{{2}{2}{Introduction}{equation.1.2}{}}
\@writefile{toc}{\contentsline {paragraph}{\textbf {Vignette: Burer-Monteiro splitting.}}{2}{section*.1}}
\newlabel{eq:sdp}{{3}{2}{\textbf {Vignette: Burer-Monteiro splitting.}}{equation.1.3}{}}
\citation{boumal2016non,waldspurger2018rank}
\citation{luenberger1984linear}
\newlabel{prob:nc}{{4}{3}{\textbf {Vignette: Burer-Monteiro splitting.}}{equation.1.4}{}}
\newlabel{eq:minmax}{{5}{3}{\textbf {Vignette: Burer-Monteiro splitting.}}{equation.1.5}{}}
\newlabel{eq:Lagrangian}{{6}{3}{\textbf {Vignette: Burer-Monteiro splitting.}}{equation.1.6}{}}
\newlabel{e:exac}{{7}{3}{\textbf {Vignette: Burer-Monteiro splitting.}}{equation.1.7}{}}
\newlabel{eq:dual-update}{{8}{3}{\textbf {Vignette: Burer-Monteiro splitting.}}{equation.1.8}{}}
\@writefile{toc}{\contentsline {paragraph}{\emph {\textbf {Contributions.}} }{3}{section*.2}}
\newlabel{eq:new update}{{9}{3}{\emph {\textbf {Contributions.}}}{equation.1.9}{}}
\citation{rockafellar2009variational}
\newlabel{sec:preliminaries}{{2}{4}{Preliminaries}{section.2}{}}
\@writefile{toc}{\contentsline {section}{\numberline {2}Preliminaries }{4}{section.2}}
\@writefile{toc}{\contentsline {paragraph}{\textbf {\emph {Notation.}}}{4}{section*.3}}
\newlabel{eq:defn of prox}{{10}{4}{\textbf {\emph {Notation.}}}{equation.2.10}{}}
\newlabel{sec:opt cnds}{{2}{4}{\textbf {\emph {{Necessary optimality conditions.}}}}{section*.4}{}}
\@writefile{toc}{\contentsline {paragraph}{\textbf {\emph {{Necessary optimality conditions.}}} }{4}{section*.4}}
\newlabel{e:inclu1}{{12}{4}{\textbf {\emph {{Necessary optimality conditions.}}}}{equation.2.12}{}}
\newlabel{e:inclu2}{{13}{4}{\textbf {\emph {{Necessary optimality conditions.}}}}{equation.2.13}{}}
\citation{bolte2014proximal}
\newlabel{eq:local-min}{{14}{5}{\textbf {\emph {{Necessary optimality conditions.}}}}{equation.2.14}{}}
\@writefile{toc}{\contentsline {paragraph}{\emph {\textbf {Technical lemmas.}}}{5}{section*.5}}
\newlabel{lem:smoothness}{{1}{5}{\emph {\textbf {Technical lemmas.}}}{lemma.1}{}}
\newlabel{eq:smoothness of Lagrangian}{{17}{5}{\emph {\textbf {Technical lemmas.}}}{equation.2.17}{}}
\newlabel{def:grad map}{{1}{5}{\emph {\textbf {Technical lemmas.}}}{definition.1}{}}
\newlabel{eq:grad map}{{19}{5}{\emph {\textbf {Technical lemmas.}}}{equation.2.19}{}}
\citation{bolte2018nonconvex}
\newlabel{lem:11}{{2}{6}{\emph {\textbf {Technical lemmas.}}}{lemma.2}{}}
\newlabel{e:deslem}{{21}{6}{\emph {\textbf {Technical lemmas.}}}{equation.2.21}{}}
\newlabel{lem:eval Lipsc cte}{{3}{6}{\emph {\textbf {Technical lemmas.}}}{lemma.3}{}}
\newlabel{eq:defn of x+gamma}{{22}{6}{\emph {\textbf {Technical lemmas.}}}{equation.2.22}{}}
\newlabel{eq:defn of gamma line search}{{23}{6}{\emph {\textbf {Technical lemmas.}}}{equation.2.23}{}}
\newlabel{eq:moreover}{{24}{6}{\emph {\textbf {Technical lemmas.}}}{equation.2.24}{}}
\newlabel{sec:slater}{{3}{6}{Uniform Regularity}{section.3}{}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Uniform Regularity }{6}{section.3}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Solving (1) can be particularly difficult, even when it is a convex program. As an example, this figure shows a pathological case, where the Slater\IeC {\textquoteright }s condition does not apply. See Section\nobreakspace {}\ref {sec:slater} for more details.}}{6}{figure.1}}
\newlabel{fig:convex_slater}{{1}{6}{Solving (1) can be particularly difficult, even when it is a convex program. As an example, this figure shows a pathological case, where the Slater’s condition does not apply. See Section~\ref {sec:slater} for more details}{figure.1}{}}
\newlabel{defn:nonconvex slater}{{2}{7}{Uniform Regularity}{definition.2}{}}
\newlabel{eq:new slater defn}{{25}{7}{Uniform Regularity}{equation.3.25}{}}
\@writefile{toc}{\contentsline {paragraph}{\textbf {\emph {Jacobian $\operatorname {D}A$.}}}{7}{section*.6}}
\@writefile{toc}{\contentsline {paragraph}{\textbf {\emph {Subspace $S$.}}}{7}{section*.7}}
\newlabel{eq:defn_nu_A}{{26}{7}{\textbf {\emph {Subspace $S$.}}}{equation.3.26}{}}
\@writefile{toc}{\contentsline {paragraph}{\emph {\textbf {Convex case.}}}{7}{section*.8}}
\newlabel{eq:nu for cvx}{{27}{8}{\emph {\textbf {Convex case.}}}{equation.3.27}{}}
\newlabel{prop:convex}{{1}{8}{\emph {\textbf {Convex case.}}}{proposition.1}{}}
\@writefile{toc}{\contentsline {paragraph}{\emph {\textbf {Beyond the Slater's condition.}}}{8}{section*.9}}
\citation{bertsekas1976penalty}
\@writefile{toc}{\contentsline {section}{\numberline {4}Linearized AL Algorithm}{9}{section.4}}
\newlabel{Algo:2}{{4}{9}{Linearized AL Algorithm}{section.4}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces HoLAL algorithm for solving problem \textup {\hbox {\mathsurround \z@ \normalfont (\ignorespaces \ref {prob:01}\unskip \@@italiccorr )}}}}{9}{algorithm.1}}
\newlabel{lem:bnd bnd Ak}{{4}{9}{Linearized AL Algorithm}{lemma.4}{}}
\newlabel{eq:low-bnd-on-nu-lemma}{{28}{9}{Linearized AL Algorithm}{equation.4.28}{}}
\newlabel{eq:bnd on Ak final}{{29}{10}{Linearized AL Algorithm}{equation.4.29}{}}
\newlabel{thm:main}{{1}{10}{Linearized AL Algorithm}{theorem.4.1}{}}
\newlabel{eq:low-bnd-on-regularity}{{32}{10}{Linearized AL Algorithm}{equation.4.32}{}}
\citation{nouiehed2018convergence}
\newlabel{eq:rates-thm}{{33}{11}{Linearized AL Algorithm}{equation.4.33}{}}
\@writefile{toc}{\contentsline {paragraph}{\textbf {\emph {Convergence rates.}}}{11}{section*.10}}
\@writefile{toc}{\contentsline {paragraph}{\emph {\textbf {Uniform regularity.}}}{11}{section*.11}}
\@writefile{toc}{\contentsline {paragraph}{\emph {\textbf {Subspace $S$.}}}{11}{section*.12}}
\@writefile{toc}{\contentsline {paragraph}{\textbf {\emph {Faster rates.}}}{11}{section*.13}}
\citation{o2017behavior}
\citation{Glowinski1975,Gabay1976,Boyd2011}
\newlabel{sec:local-opt}{{5}{12}{Local Optimality}{section.5}{}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Local Optimality }{12}{section.5}}
\@writefile{toc}{\contentsline {paragraph}{\emph {\textbf {Special case.}}}{12}{section*.14}}
\@writefile{toc}{\contentsline {paragraph}{\textbf {\emph {General case.}}}{12}{section*.15}}
\@writefile{toc}{\contentsline {section}{\numberline {6}Linearized ADMM}{13}{section.6}}
\newlabel{eq:admm 2}{{37}{13}{Linearized ADMM}{equation.6.37}{}}
\newlabel{eq:smoothness basics admm}{{38}{13}{Linearized ADMM}{equation.6.38}{}}
\newlabel{eq:lagrangian admm}{{39}{13}{Linearized ADMM}{equation.6.39}{}}
\newlabel{eq:admm main}{{40}{13}{Linearized ADMM}{equation.6.40}{}}
\newlabel{eq:grad map admm}{{41}{13}{Linearized ADMM}{equation.6.41}{}}
\newlabel{eq:line search x admm}{{44}{14}{Linearized ADMM}{equation.6.44}{}}
\newlabel{eq:defn of gamma line search admm}{{45}{14}{Linearized ADMM}{equation.6.45}{}}
\newlabel{Algo:3}{{6}{14}{Linearized ADMM}{equation.6.45}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {2}{\ignorespaces Linearized ADMM for solving problem \textup {\hbox {\mathsurround \z@ \normalfont (\ignorespaces \ref {eq:admm main}\unskip \@@italiccorr )}}}}{14}{algorithm.2}}
\newlabel{thm:main admm}{{2}{14}{Linearized ADMM}{theorem.6.2}{}}
\citation{hestenes1969multiplier,powell1978fast}
\citation{bertsekas1999nonlinear,bertsekas2014constrained,lan2016iteration,nedelcu2014computational}
\citation{wang2015global,liu2017linearized}
\citation{burer2003nonlinear,burer2005local}
\citation{BKS15:Dropping-Convexity}
\citation{park2016provable}
\newlabel{eq:low-bnd-on-regularity}{{47}{15}{Linearized ADMM}{equation.6.47}{}}
\newlabel{eq:rates-thm}{{48}{15}{Linearized ADMM}{equation.6.48}{}}
\newlabel{sec:related work}{{7}{15}{Related Works}{section.7}{}}
\@writefile{toc}{\contentsline {section}{\numberline {7}Related Works }{15}{section.7}}
\citation{boumal2014manopt,boumal2016global}
\citation{boumal2016global}
\citation{clason2018acceleration}
\citation{chambolle2011first}
\citation{bhojanapalli2018smoothed}
\citation{doi:10.1137/15M1031631}
\newlabel{sec:experiments}{{8}{16}{Experiments}{section.8}{}}
\@writefile{toc}{\contentsline {section}{\numberline {8}Experiments }{16}{section.8}}
\newlabel{sec:proof-of-main}{{A}{16}{Proof of Theorem \ref {thm:main}}{appendix.A}{}}
\@writefile{toc}{\contentsline {section}{\numberline {A}Proof of Theorem \ref {thm:main} }{16}{appendix.A}}
\newlabel{eq:update uk recall}{{49}{16}{Proof of Theorem \ref {thm:main}}{equation.A.49}{}}
\newlabel{eq:y update recall}{{50}{16}{Proof of Theorem \ref {thm:main}}{equation.A.50}{}}
\newlabel{eq:grad map recall}{{51}{17}{Proof of Theorem \ref {thm:main}}{equation.A.51}{}}
\newlabel{eq:smoothness rep}{{53}{17}{Proof of Theorem \ref {thm:main}}{equation.A.53}{}}
\newlabel{eq:y update unfolded}{{54}{17}{Proof of Theorem \ref {thm:main}}{equation.A.54}{}}
\newlabel{eq:key ineq}{{55}{17}{Proof of Theorem \ref {thm:main}}{equation.A.55}{}}
\newlabel{eq:long chain broken}{{57}{18}{Proof of Theorem \ref {thm:main}}{equation.A.57}{}}
\newlabel{eq:defn mu}{{58}{18}{Proof of Theorem \ref {thm:main}}{equation.A.58}{}}
\newlabel{eq:beta n sigma}{{59}{18}{Proof of Theorem \ref {thm:main}}{equation.A.59}{}}
\newlabel{eq:consequences}{{60}{19}{Proof of Theorem \ref {thm:main}}{equation.A.60}{}}
\newlabel{eq:long chain broken 10}{{61}{19}{Proof of Theorem \ref {thm:main}}{equation.A.61}{}}
\newlabel{eq:to be used for feas pre}{{63}{20}{Proof of Theorem \ref {thm:main}}{equation.A.63}{}}
\newlabel{eq:defn of BK}{{65}{20}{Proof of Theorem \ref {thm:main}}{equation.A.65}{}}
\newlabel{eq:to be used for feas}{{66}{20}{Proof of Theorem \ref {thm:main}}{equation.A.66}{}}
\newlabel{eq:to be used later on}{{67}{20}{Proof of Theorem \ref {thm:main}}{equation.A.67}{}}
\newlabel{eq:final bnd on G}{{68}{20}{Proof of Theorem \ref {thm:main}}{equation.A.68}{}}
\newlabel{eq:final bnd on feas gap}{{69}{21}{Proof of Theorem \ref {thm:main}}{equation.A.69}{}}
\newlabel{eq:overall bnd raw}{{70}{21}{Proof of Theorem \ref {thm:main}}{equation.A.70}{}}
\newlabel{eq:dual growth}{{71}{21}{Proof of Theorem \ref {thm:main}}{equation.A.71}{}}
\newlabel{eq:Bk evaluated}{{72}{21}{Proof of Theorem \ref {thm:main}}{equation.A.72}{}}
\newlabel{eq:smoothness at k}{{73}{21}{Proof of Theorem \ref {thm:main}}{equation.A.73}{}}
\newlabel{eq:low bnd on gammas}{{74}{21}{Proof of Theorem \ref {thm:main}}{equation.A.74}{}}
\newlabel{eq:exact dependences}{{76}{22}{Proof of Theorem \ref {thm:main}}{equation.A.76}{}}
\newlabel{eq:rate of feas gap}{{77}{22}{Proof of Theorem \ref {thm:main}}{equation.A.77}{}}
\newlabel{eq:suff cnd on nu-1}{{79}{22}{Proof of Theorem \ref {thm:main}}{equation.A.79}{}}
\newlabel{eq:cnd-on-nu-proof}{{82}{23}{Proof of Theorem \ref {thm:main}}{equation.A.82}{}}
\newlabel{sec:ADMM theory}{{B}{23}{Proof of Theorem \ref {thm:main admm}}{appendix.B}{}}
\@writefile{toc}{\contentsline {section}{\numberline {B}Proof of Theorem \ref {thm:main admm} }{23}{appendix.B}}
\newlabel{lem:smoothness admm}{{5}{23}{Proof of Theorem \ref {thm:main admm}}{lemma.5}{}}
\newlabel{eq:smoothness of Lagrangian admm}{{85}{23}{Proof of Theorem \ref {thm:main admm}}{equation.B.85}{}}
\newlabel{eq:local-lipschitz-admm}{{86}{23}{Proof of Theorem \ref {thm:main admm}}{equation.B.86}{}}
\newlabel{def:grad map admm}{{3}{23}{Proof of Theorem \ref {thm:main admm}}{definition.3}{}}
\newlabel{eq:grad map admm}{{87}{23}{Proof of Theorem \ref {thm:main admm}}{equation.B.87}{}}
\newlabel{lem:11 admm}{{6}{23}{Proof of Theorem \ref {thm:main admm}}{lemma.6}{}}
\newlabel{e:deslem}{{6}{23}{Proof of Theorem \ref {thm:main admm}}{equation.B.88}{}}
\newlabel{eq:deslem admm}{{89}{23}{Proof of Theorem \ref {thm:main admm}}{equation.B.89}{}}
\newlabel{lem:eval Lipsc cte admm}{{7}{24}{Proof of Theorem \ref {thm:main admm}}{lemma.7}{}}
\newlabel{eq:defn of gamma line search admm}{{91}{24}{Proof of Theorem \ref {thm:main admm}}{equation.B.91}{}}
\newlabel{eq:moreover admm}{{92}{24}{Proof of Theorem \ref {thm:main admm}}{equation.B.92}{}}
\newlabel{eq:ADMM updates recall}{{93}{24}{Proof of Theorem \ref {thm:main admm}}{equation.B.93}{}}
\newlabel{eq:decrease twice}{{96}{24}{Proof of Theorem \ref {thm:main admm}}{equation.B.96}{}}
\newlabel{eq:defn of w}{{97}{25}{Proof of Theorem \ref {thm:main admm}}{equation.B.97}{}}
\newlabel{eq:to-be-projected-admm}{{103}{25}{Proof of Theorem \ref {thm:main admm}}{equation.B.103}{}}
\newlabel{sec:proof of smoothness lemma}{{C}{25}{Proof of Lemma \ref {lem:smoothness}}{appendix.C}{}}
\@writefile{toc}{\contentsline {section}{\numberline {C}Proof of Lemma \ref {lem:smoothness}}{25}{appendix.C}}
\newlabel{sec:proof of descent lemma}{{D}{26}{Proof of Lemma \ref {lem:11}}{appendix.D}{}}
\@writefile{toc}{\contentsline {section}{\numberline {D}Proof of Lemma \ref {lem:11}}{26}{appendix.D}}
\newlabel{eq:descent pr 1}{{111}{26}{Proof of Lemma \ref {lem:11}}{equation.D.111}{}}
\newlabel{eq:opt of prox}{{112}{26}{Proof of Lemma \ref {lem:11}}{equation.D.112}{}}
\newlabel{sec:proof of linesearch}{{E}{27}{Proof of Lemma \ref {lem:eval Lipsc cte}}{appendix.E}{}}
\@writefile{toc}{\contentsline {section}{\numberline {E}Proof of Lemma \ref {lem:eval Lipsc cte}}{27}{appendix.E}}
\newlabel{eq:optimality of uplus}{{114}{27}{Proof of Lemma \ref {lem:eval Lipsc cte}}{equation.E.114}{}}
\newlabel{sec:proof of prop}{{F}{27}{Proof of Proposition \ref {prop:convex}}{appendix.F}{}}
\@writefile{toc}{\contentsline {section}{\numberline {F}Proof of Proposition \ref {prop:convex} }{27}{appendix.F}}
\newlabel{eq:no feas}{{116}{27}{Proof of Proposition \ref {prop:convex}}{equation.F.116}{}}
\newlabel{eq:counter-assump}{{117}{27}{Proof of Proposition \ref {prop:convex}}{equation.F.117}{}}
\newlabel{eq:counter-assump-rewritten}{{118}{27}{Proof of Proposition \ref {prop:convex}}{equation.F.118}{}}
\newlabel{sec:proof of bnd Ak}{{G}{28}{Proof of Lemma \ref {lem:bnd bnd Ak}}{appendix.G}{}}
\@writefile{toc}{\contentsline {section}{\numberline {G}Proof of Lemma \ref {lem:bnd bnd Ak} }{28}{appendix.G}}
\newlabel{eq:bndness in slater proof}{{119}{28}{Proof of Lemma \ref {lem:bnd bnd Ak}}{equation.G.119}{}}
\newlabel{eq:to be projected}{{121}{28}{Proof of Lemma \ref {lem:bnd bnd Ak}}{equation.G.121}{}}
\newlabel{eq:defn of dual cone}{{122}{28}{Proof of Lemma \ref {lem:bnd bnd Ak}}{equation.G.122}{}}
\newlabel{eq:before Sk}{{123}{28}{Proof of Lemma \ref {lem:bnd bnd Ak}}{equation.G.123}{}}
\newlabel{eq:defn of S}{{124}{28}{Proof of Lemma \ref {lem:bnd bnd Ak}}{equation.G.124}{}}
\newlabel{eq:pre norm}{{125}{28}{Proof of Lemma \ref {lem:bnd bnd Ak}}{equation.G.125}{}}
\newlabel{eq:post norm}{{126}{28}{Proof of Lemma \ref {lem:bnd bnd Ak}}{equation.G.126}{}}
\newlabel{eq:slater proof 0}{{127}{29}{Proof of Lemma \ref {lem:bnd bnd Ak}}{equation.G.127}{}}
\newlabel{eq:slater proof 1}{{129}{29}{Proof of Lemma \ref {lem:bnd bnd Ak}}{equation.G.129}{}}

Event Timeline

c4science · Help