Cover Image

Data Debugging is NP-hard for Classifiers Trained with SGD

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Guo, Zizheng, Chen, Pengyu, Fu, Yanzhang, Miao, Dongjing
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

Training Neural Networks is NP-Hard in Fixed Dimension
by: Froese, Vincent, et al.
Published: (2023)

Communication Complexity is NP-hard
by: Hirahara, Shuichi, et al.
Published: (2025)

NP-hardness of SVP in Euclidean Space
by: Wan, Daqing
Published: (2026)

Dashed Line Defense: Plug-And-Play Defense Against Adaptive Score-Based Query Attacks
by: Fu, Yanzhang, et al.
Published: (2026)

Optimizing for aggressive-style strategies in Flesh and Blood is NP-hard
by: Romão, Leonardo Gasparini, et al.
Published: (2025)

King Chasing Problem in Chinese Chess is NP-hard
by: Li, Chao, et al.
Published: (2026)

NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
by: Baraskar, Omkar, et al.
Published: (2024)

Quantum Max-Cut is NP hard to approximate
by: Piddock, Stephen
Published: (2025)

Computing the EHZ capacity is NP-hard
by: Leipold, Karla, et al.
Published: (2024)

Fast decision tree learning solves hard coding-theoretic problems
by: Koch, Caleb, et al.
Published: (2024)

Prove Symbolic Regression is NP-hard by Symbol Graph
by: Song, Jinglu, et al.
Published: (2024)

Freeze-Tag is NP-hard in 2D with $L_1$ distance
by: Silva, Lucas de Oliveira, et al.
Published: (2025)

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
by: Krokhin, Andrei, et al.
Published: (2025)

Two NP-hard Extensions of the Spearman Footrule even for a Small Constant Number of Voters
by: Durand, Martin
Published: (2026)

Diffusion Language Models are Provably Optimal Parallel Samplers
by: Jiang, Haozhe, et al.
Published: (2025)

When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?
by: Chen, Yuansi, et al.
Published: (2023)

Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
by: Bertschinger, Daniel, et al.
Published: (2022)

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
by: Gu, Shouzhen, et al.
Published: (2026)

Learnability of Parameter-Bounded Bayes Nets
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
by: Wang, Jie, et al.
Published: (2024)

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
by: Chandrasekaran, Gautam, et al.
Published: (2024)

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
by: Li, Zhiyuan, et al.
Published: (2024)

Ask, and it shall be given: On the Turing completeness of prompting
by: Qiu, Ruizhong, et al.
Published: (2024)

Large Language Models on Small Resource-Constrained Systems: Performance Characterization, Analysis and Trade-offs
by: Seymour, Liam, et al.
Published: (2024)

On the Hardness of Learning Regular Expressions
by: Attias, Idan, et al.
Published: (2025)

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
by: Merrill, William, et al.
Published: (2025)

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
by: Majumdar, Angshul
Published: (2026)

Spiky Rank and Its Applications to Rigidity and Circuits
by: Hambardzumyan, Lianna, et al.
Published: (2026)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
by: Li, Qian, et al.
Published: (2026)

Low-Rank Matrix Approximation for Neural Network Compression
by: Cherukuri, Kalyan, et al.
Published: (2025)

Proximity to Losslessly Compressible Parameters
by: Farrugia-Roberts, Matthew
Published: (2023)

Decision Tree Learning on Product Spaces
by: Moakahr, Arshia Soltani, et al.
Published: (2026)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
by: Amiri, Alireza, et al.
Published: (2025)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
by: Cao, Yang, et al.
Published: (2025)

A Logic for Expressing Log-Precision Transformers
by: Merrill, William, et al.
Published: (2022)

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
by: Jacobs, Peter Matthew, et al.
Published: (2026)

Distribution-Specific Agnostic Conditional Classification With Halfspaces
by: Huang, Jizhou, et al.
Published: (2025)

From Pseudorandomness to Multi-Group Fairness and Back
by: Dwork, Cynthia, et al.
Published: (2023)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
by: Rohatgi, Dhruv, et al.
Published: (2025)