Computation Effort of Algorithms

Question

Consider the strictly convex unconstrained optimization problem $\mathcal{O} := \min_{x \in \mathbb{R}^n} f(x).$ Let $x_\text{opt}$ denote its unique minima and $x_0$ be a given initial approximation to $x_\text{opt}.$We will call a vector $x$ an $\epsilon-$ close solution of $\mathcal{O}$ if \begin{equation} \frac{||x - x_{\text{opt}}||_2}{||x_0 - x_\text{opt}||_2} \leq \epsilon. \end{equation}

Suppose that there exists two iterative algorithms $\mathcal{A}_1$ and $\mathcal{A}_2$ to find an $\epsilon-$ close solution of $\mathcal{O}$ with the following properties:

1. For any $\epsilon > 0,$ the total computational effort, i.e. effort required per iteration $\times$ total number of iterations, to find an $\epsilon-$ close solution is same for both the algorithms.
2. The per iteration effort for $\mathcal{A}_1$ is $O(n),$ say, while that of $\mathcal{A}_2$ is $O(n^2).$

Are there situations, where one would prefer one algorithm over the other? Why?

Answer 1

It's typically very hard if not impossible to implement a parallel version of an iterative algorithm that paralellizes across iterations. The completion of one iteration is a natural sequence point. If one algorithm requires fewer iterations but more work per iteration, then it's more likely that this algorithm can be effectively implemented in parallel.

An example of this is linear programming, where the primal-dual barrier (interior point) method typically uses only a few dozen iterations even for very large problems, but the work per iteration is quite extensive. In comparison various versions of the simplex method typically require far more iterations, but the work per iteration is less. In practice, parallel implementations of interior point methods have shown far better parallel efficiency than parallel implementations of the simplex method.

Answer 2

I can think of some possibilities:

If both algorithms monotonically reduce the error with each iteration, then it might be preferable to some to have more, cheaper iterations since it gives you more choices about when to stop iterating.

If $\mathcal{A}_1$ is $O(n)$ work and time but $O(n^k)$ memory, you might prefer $\mathcal{A}_2$ if $k$ is large. $k=2$ might even be large enough to make you select $\mathcal{A}_2$ since memory use is more likely to constrain you here.

This probably applies whether we're talking about optimization or any other class of iterative problem.