[tomrod]

> because, gradient descent is linear in the number of dimensions

Yes, but increasing dimensions does not mean the manifold of the problem space increases the same.