# Estimating the rate of convergence of Projected Gradient Descent on constrained polynomial objectives

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:

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:

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

Relatedly, why plotting the errors against iteration number produce a plot like this:

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)?

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