Maximin Optimization for Binary Regression
This addresses optimization challenges in constrained models for quantized learning and digital communication systems, but it appears incremental as it builds on existing maximin techniques.
The paper tackles the problem of regression with binary weights, which is common in quantized learning and digital communication, by using a maximin optimization approach. They prove optimality in linear regression under low noise and robust regression with few outliers, and show practical performance in cross-entropy loss regression and non-convex neural networks.
We consider regression problems with binary weights. Such optimization problems are ubiquitous in quantized learning models and digital communication systems. A natural approach is to optimize the corresponding Lagrangian using variants of the gradient ascent-descent method. Such maximin techniques are still poorly understood even in the concave-convex case. The non-convex binary constraints may lead to spurious local minima. Interestingly, we prove that this approach is optimal in linear regression with low noise conditions as well as robust regression with a small number of outliers. Practically, the method also performs well in regression with cross entropy loss, as well as non-convex multi-layer neural networks. Taken together our approach highlights the potential of saddle-point optimization for learning constrained models.