Provably Training Overparameterized Neural Network Classifiers with Non-convex Constraints

Abstract

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.

References in corpus (18)

• Equality of Opportunity in Supervised Learning
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• On Lazy Training in Differentiable Programming
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
• On the Convergence Rate of Training Recurrent Neural Networks
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Convergence of Adversarial Training in Overparametrized Neural Networks
• A Selective Overview of Deep Learning
• Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
• Capuchin: Causal Database Repair for Algorithmic Fairness
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• Optimizing Generalized Rate Metrics through Game Equilibrium