Provably Training Overparameterized Neural Network Classifiers with Non-convex Constraints
This work provides theoretical guarantees for training neural networks under non-convex constraints, which is a significant problem for researchers and practitioners applying machine learning to fairness and imbalanced data.
This paper tackles the problem of training neural network classifiers under non-convex constraints, a common challenge in areas like algorithmic fairness and class-imbalanced classification. The authors demonstrate that overparameterized neural networks can achieve near-optimal and near-feasible solutions using projected stochastic gradient descent.
Training a classifier under non-convex constraints has gotten increasing attention in the machine learning community thanks to its wide range of applications such as algorithmic fairness and class-imbalanced classification. However, several recent works addressing non-convex constraints have only focused on simple models such as logistic regression or support vector machines. Neural networks, one of the most popular models for classification nowadays, are precluded and lack theoretical guarantees. In this work, we show that overparameterized neural networks could achieve a near-optimal and near-feasible solution of non-convex constrained optimization problems via the project stochastic gradient descent. Our key ingredient is the no-regret analysis of online learning for neural networks in the overparameterization regime, which may be of independent interest in online learning applications.