Pith. sign in

REVIEW 4 cited by

A Tighter Complexity Analysis of SparseGPT

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2408.12151 v2 pith:XEJJBVLP submitted 2024-08-22 cs.DS cs.AIcs.CLcs.LG

Xiaoyu Li , Yingyu Liang , Zhenmei Shi , Zhao Song This is my paper · ORCID
classification cs.DScs.AIcs.CLcs.LG
keywords omegaanalysisrunningtimeicmlsongsparsegptzhou
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

In this work, we improved the analysis of the running time of SparseGPT [Frantar, Alistarh ICML 2023] from $O(d^{3})$ to $O(d^{\omega} + d^{2+a+o(1)} + d^{1+\omega(1,1,a)-a})$ for any $a \in [0, 1]$, where $\omega$ is the exponent of matrix multiplication. In particular, for the current $\omega \approx 2.371$ [Alman, Duan, Williams, Xu, Xu, Zhou 2024], our running time boils down to $O(d^{2.53})$. This running time is due to the analysis of the lazy update behavior in iterative maintenance problems such as [Deng, Song, Weinstein 2022; Brand, Song, Zhou ICML 2024].

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse

    cs.LG 2025-05 reject novelty 4.0 of 10

    A residual self-attention network with all weight entries bounded by a small η can be approximated by one layer to error O(η)‖X‖∞, so skip connections do not prevent layer collapse.

  2. Universal Approximation of Visual Autoregressive Transformers

    cs.LG 2025-02 reject novelty 4.0 of 10

    The paper's headline claim that VAR transformers universally approximate all Lipschitz image maps is not supported, because the theorem restricts the target class and its key lemma has an invalid linearity step.

  3. High-Order Matching for One-Step Shortcut Diffusion Models

    cs.CV 2025-02 reject novelty 4.0 of 10

    HOMO extends shortcut diffusion with acceleration and jerk supervision, but the proof of superior approximation is not supported and experiments lack error bars.

  4. Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolation

    cs.CV 2025-02 reject novelty 4.0 of 10

    VLFM models video latent patches as a HiPPO-LegS polynomial flow and trains a flow matching model to generate frames, claiming bounded interpolation and extrapolation error.

Pith tools