RTM runs in polynomial time

The algorithm has nice convergence 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

1. in \(R_{II}\) and \(R_{III}\), each step reduces the objective values by at least a constant (Proposition 3.7), and

2. in \(R_{I}\), the algorithm first takes constrained steps and then followed by only unconstrained steps

3. objective is reduced by at least a fixed amount for each constrained step in \(R_{I}\), and

4. the distance to the local minimum drops quadratically for unconstrained steps in \(R_I\).