Abstract
Solving non-convex, NP-hard optimization problems is crucial for trainingmachine learning models, including neural networks. However, non-convexityoften leads to black-box machine learning models with unclear inner workings.While convex formulations have been used for verifying neural networkrobustness, their application to training neural networks remains lessexplored. In response to this challenge, we reformulate the problem of traininginfinite-width two-layer ReLU networks as a convex completely positive programin a finite-dimensional (lifted) space. Despite the convexity, solving thisproblem remains NP-hard due to the complete positivity constraint. To overcomethis challenge, we introduce a semidefinite relaxation that can be solved inpolynomial time. We then experimentally evaluate the tightness of thisrelaxation, demonstrating its competitive performance in test accuracy across arange of classification tasks.