The paper doesn't address very much the "fully classical" approach to their problems, so I don't think they are making a judgment one way or another about quantum advantage with VQA. But they are part of a growing body of literature arguing very wisely that the complexity of classical optimization cannot be ignored, when assessing the complexity of hybrid quantum-classical algorithms.
In particular, this paper proves that optimizing even the simplest cost-functions and ansatze is generally NP-hard. I've not dug into the details of the proof, so I hope someone else can fill in my answer with the appropriate nuance, but I think their proof implies that any polynomial implementation of a classical optimization cannot guarantee the error in optimization is polynomially bounded, even when restricted to the simplest quantum problems. (Unless $P=NP$, that is.)
Super-polynomial error, or a super-polynomial algorithm, in your hybrid algorithm does not strictly preclude computational advantage over fully classical techniques, but it is certainly disheartening. That said, the authors do offer consolation in the last couple paragraphs. The penultimate paragraph concludes:
This result emphasizes the need for effective initialization procedures for VQA algorithms and poses the challenge of finding nonlocal heuristics for VQA optimization ... to reach smaller optimization errors.
In other words, the general solution might be NP-hard, but if we're careful and clever, we might still get answers that are "good enough".
(Of course, the same might be said of fully classical approaches. But the authors don't. ^_^)
