0
$\begingroup$

I am estimating the order of convergence of Projected Gradient Descent (GD) on quadratic polynomials with random coefficients independently drawn from Uniform(-1,1) and bounded by a unit hypercube. I'm using constant step size equal to the standard choice of the inverse of the Lipschitz constant of the objective.

The order of convergence is defined as (adapting the definition to the case of GD where the error is the objective value $p$ such that $\exists k_s$ such that $\forall k > k_s$

$\frac{\| f(x^{(k+1))} - f(x^*)\|}{\|f(x^{(k)}) - f(x^*)\|^p} \leq \gamma$ (Nocedal & Wright)

I use the fact that $$\log \| x^{(k+1)} - x^*\| \approx p\log + \log \gamma$$ so: $$p \approx \frac{\log\|(x^{(k)} - x^*)/(x^{(k-1)} - x^*)\|}{\log\|(x^{(k-1)} - x^*)/(x^{(k-2)} - x^*)\|}$$

I test with some sequences of know convergence order e.g. $1+ 0.5^{2^{k}}$ convergence quadratically to 1 so p should be 2. I estimate the convergence using a log-log plot with the successive errors plotted against each other like so:

enter image description here as expected the slope is 2. I will do for many runs - fitting a straight line to get some sort of average convergence and calculating the arithmetic average of the slopes.

But just out of interest I was wondering why my plots of $p$ as a function of iteration look the way they do - that is:

When I plot $p(k)$ for the same test sequence I get a straight line y=2, as expected:

enter image description here

but the same plot for my GD runs looks like this:

enter image description here

Relatedly, why plotting the errors against iteration number produce a plot like this: enter image description here

with the strange acceleration - increased rate of convergence - at the end?

I understand that there should be some instability at the beginning but why is there so much instability at the end and why does the curve rise (this happens consistently no matter what is the overall number of steps form of the quadratic etc) - could this be due to cancellation errors is numpy's float64 - (at the end of the run the errors are differences between very similar numbers)?

$\endgroup$
1
  • 1
    $\begingroup$ When your error is $\approx 10^{-14}$ already, you also suffer from round-off. $\endgroup$ Commented Jul 10 at 19:28

1 Answer 1

1
$\begingroup$

The theory of asymptotic convergence involves inequalities on the reduction in error. It's always possible that you'll take a step that makes better than expected progress- that isn't a violation of the theory.

If you look at the last 100 or so iterates, you might see a pattern in what's happening. For example, it wouldn't surprise me if some of the variables converge to their optimal values and stay fixed over those last 100 iterations and you're only optimizing in one of the dimensions. If that's happening the linear convergence rate constant could improve.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.