this is for holding javascript data
Richard Guo edited paragraph_RTM_runs_in_polynomial__.tex
over 8 years ago
Commit id: b7bec5a84f7772e0f57ce4af9507188223bcd472
deletions | additions
diff --git a/paragraph_RTM_runs_in_polynomial__.tex b/paragraph_RTM_runs_in_polynomial__.tex
index eec32e0..6f4d6ba 100644
--- a/paragraph_RTM_runs_in_polynomial__.tex
+++ b/paragraph_RTM_runs_in_polynomial__.tex
...
\paragraph{RTM runs in polynomial time}
The algorithm has nice convergence
property: property (Theorem 3.1 and Theoreom 3.2): for a given accuracy $\| \hat{\mathbf{q}} - \mathbf{q}_{\ast} \|_2 \leq \epsilon$, it takes RTM a polynomial number (in $p$ and $n$) of iterations to converge to $\hat{\mathbf{q}}$.
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 followed by \textit{all 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}