On the complexity of data debugging for classifiers trained with stochastic gradient descent

Data debugging seeks a subset of training data such that retraining a model on this subset leads to improved accuracy. While a number of heuristic methods have been explored, none are guaranteed to solve this problem effectively, leaving open the fundamental question of whether the task can be solved efficiently. To address this, we investigate the computational complexity of the problem named DEBUGGABLE. Given a machine learning model M trained on a dataset D and a misclassified test instance (x_test,y_test) with M(x_test)≠y_test, the problem asks whether there exists a subset D′ of D such that the model M^′ obtained by retraining on D′ satisfies M^′(x_test)=y_test. Focusing on SGD-trained linear classifiers, we derive three main results: (1) When neither the loss function nor the model dimension is fixed, DEBUGGABLE is NP-complete, and this holds regardless of the training order; (2) For hinge-like loss functions, we provide a comprehensive analysis of the computational complexity of DEBUGGABLE; (3) For linear loss functions, DEBUGGABLE can be solved in linear time, that is, data debugging can be solved easily in this case. These results not only highlight the limitations of current approaches but also offer new insights into data debugging.