Buchumschlag

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Alman, Josh, Song, Zhao
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Machine Learning Computational Complexity Computation and Language Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Asymptotic Rank Speedup Theorems, Revisited
von: Alman, Josh, et al.
Veröffentlicht: (2026)

Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
von: Alman, Josh, et al.
Veröffentlicht: (2025)

Learning Functions of Halfspaces
von: Alman, Josh, et al.
Veröffentlicht: (2026)

A Refined Laser Method and Faster Matrix Multiplication
von: Alman, Josh, et al.
Veröffentlicht: (2020)

The Computational Complexity of Almost Stable Clustering with Penalties
von: Khodamoradi, Kamyar, et al.
Veröffentlicht: (2025)

The Fine-Grained Complexity of Episode Matching
von: Bille, Philip, et al.
Veröffentlicht: (2021)

More Asymmetry Yields Faster Matrix Multiplication
von: Alman, Josh, et al.
Veröffentlicht: (2024)

The Sample Complexity of Replicable Realizable PAC Learning
von: Larsen, Kasper Green, et al.
Veröffentlicht: (2026)

Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
von: Alman, Josh, et al.
Veröffentlicht: (2025)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

Computational-Statistical Tradeoffs from NP-hardness
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Fine-Grained Complexity of Continuous Euclidean k-Center
von: Blank, Lotte, et al.
Veröffentlicht: (2026)

Fine-Grained Complexity of Regular Path Queries
von: Casel, Katrin, et al.
Veröffentlicht: (2021)

Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
von: Blanchard, Moise
Veröffentlicht: (2024)

Diversity-aware clustering: Computational Complexity and Approximation Algorithms
von: Thejaswi, Suhas, et al.
Veröffentlicht: (2024)

The Computational Complexity of Positive Non-Clashing Teaching in Graphs
von: Ganian, Robert, et al.
Veröffentlicht: (2025)

Fine-Grained Classification Of Detecting Dominating Patterns
von: Dransfeld, Jonathan, et al.
Veröffentlicht: (2025)

InstaHide's Sample Complexity When Mixing Two Private Images
von: Huang, Baihe, et al.
Veröffentlicht: (2020)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
von: Rohwedder, Lars, et al.
Veröffentlicht: (2024)

Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
von: Sato, Atsuki, et al.
Veröffentlicht: (2025)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
von: Nederlof, Jesper
Veröffentlicht: (2026)

Computational Complexity in Property Testing
von: Pinto Jr., Renato Ferreira, et al.
Veröffentlicht: (2025)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Superconstant Inapproximability of Decision Tree Learning
von: Koch, Caleb, et al.
Veröffentlicht: (2024)

Fast decision tree learning solves hard coding-theoretic problems
von: Koch, Caleb, et al.
Veröffentlicht: (2024)

Adaptive and oblivious statistical adversaries are equivalent
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

Private graphon estimation via sum-of-squares
von: Chen, Hongjie, et al.
Veröffentlicht: (2024)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
von: Gopalan, Parikshit, et al.
Veröffentlicht: (2024)

On the Power of Interactive Proofs for Learning
von: Gur, Tom, et al.
Veröffentlicht: (2024)

Low-degree phase transitions for detecting a planted clique in sublinear time
von: Mardia, Jay, et al.
Veröffentlicht: (2024)

Hardness of Learning Boolean Functions from Label Proportions
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

Exact and Approximate Algorithms for Polytree Learning
von: Harviainen, Juha, et al.
Veröffentlicht: (2026)

Differentially Private Verification of Distribution Properties
von: Du, Elbert, et al.
Veröffentlicht: (2026)

Efficient and Private Property Testing via Indistinguishability
von: Dwork, Cynthia, et al.
Veröffentlicht: (2025)

A Distributional-Lifting Theorem for PAC Learning
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Low-Degree Method Fails to Predict Robust Subspace Recovery
von: Jia, He, et al.
Veröffentlicht: (2026)

Feature Selection and Junta Testing are Statistically Equivalent
von: Beretta, Lorenzo, et al.
Veröffentlicht: (2025)

Samplability makes learning easier
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Efficient Turing Machine Simulation with Transformers
von: Li, Qian, et al.
Veröffentlicht: (2025)

Is nasty noise actually harder than malicious noise?
von: Blanc, Guy, et al.
Veröffentlicht: (2025)