Richard Guo edited paragraph_RTM_runs_in_polynomial__.tex  over 8 years ago

Commit id: d493e80c05955665dab58da698f3aaef29e0c013

deletions | additions      

       

This is proved by showing   \begin{enumerate}  \item in $R_{II}$ and $R_{III}$, each step reduces the objective values by at least a constant (Proposition 3.7), and  \item in $R_{I}$, the algorithm first takes \textit{constrained steps} and then  followed by \textit{all unconstrained only \textit{unconstrained  steps} \item objective is reduced by at least a fixed amount for each constrained step in $R_{I}$, and   \item the distance to the local minimum drops quadratically for unconstrained steps in $R_I$.   \end{enumerate}