Editing Openai/693e3ce6-229c-8008-97dc-ab720cb1f95a (section)

==== If you mean a theorem of the form ====

: 

then my assessment is: very unlikely without adding extra safeguards or extra assumptions.

===== The ISTA/PGD sparsity proof in this setting hinges on very special monotonicity/order properties of the non‑accelerated proximal-gradient map for these PageRank/M‑matrix quadratics (this is what lets you argue you never need to “touch” most coordinates). Your note explicitly says that analysis “does not apply to the accelerated version.” open-problem-fountoulakis22a =====

Acceleration introduces an extrapolated point (schematically yk=xk+βk(xk−xk−1)y_k=x_k+\beta_k(x_k-x_{k-1})yk=xk+βk(xk−xk−1)), which breaks exactly the kind of order-preserving / “push”-style monotonicity that local PageRank proofs exploit. Once you lose that, it becomes extremely difficult to rule out “spurious activations” of many coordinates in a single iteration, because the prox step can turn on any coordinate whose pre-prox value crosses the threshold.

There’s also a broader, well-known phenomenon in composite/proximal methods:
* Finite-time support (manifold) identification is typically provable only under a nondegeneracy / strict complementarity margin at the solution.
* Without such a margin (degenerate cases), the active set can be “almost active” for many coordinates, and accelerated methods can oscillate around the threshold.

This is not specific to PageRank; it’s a general limitation noted in the manifold-identification literature. Optimization Online<ref>{{cite web|title=Optimization Online|url=https://optimization-online.org/wp-content/uploads/2019/03/7109.pdf|publisher=Optimization Online|access-date=2025-12-19}}</ref>

That matters here because your open problem is explicitly worst-case (“it is not even clear if acceleration would not lead to a worse running time complexity in the worst case”). open-problem-fountoulakis22a

Worst-case families can easily include symmetric/degenerate graphs where many coordinates sit exactly on (or arbitrarily close to) the activation boundary.