RUN: A Relaxation-Free Bridge from Min-Max/Max-Min Optimization to Neural Networks

Min–max problems sit at the centre of worst-case machine learning, and yet they have remained almost closed to neural networks. A saddle point is not the minimizer of any single objective, so a network asked to find one must either play the two-player game explicitly, and inherit the instability of gradient descent–ascent, or replace the stated objective by a relaxed proxy (meaning a loss of tightness). Algorithm unrolling, the established way of turning an optimization algorithm into a network, applies only to problems in a single vector variable. In this paper we remove that restriction, and, to the best of our knowledge, the passage we construct has not been available before. Building on the majorization–minimization principle, we replace the min–max problem at each iteration by a surrogate saddle point that is convex in the primal variable and concave in the dual one, and show that it reduces to a single-variable problem in two ways. Eliminating the dual variable in closed form leaves a plain minimization, while eliminating the primal variable and exchanging the two operators — an exchange that Sion's minimax theorem licenses precisely here — leaves a plain maximization. The saddle point is therefore gone before any network is built, the problem that remains is the worst-case one that was posed, and what solves it is an ordinary solver whose iterations become layers and whose step sizes are the only weights. We derive one architecture per reduction and prove that they decrease the original objective at every layer whatever their weights, with a convergent objective and bounded iterates whose limit points are stationary when the inner problem is solved exactly. Which reduction to open is decided by the conditioning of the problem and the cost of the inner solve. On min–max quadratics, fair principal component analysis and worst-case-group risk, the network built on the chosen reduction outperforms, at a matched budget, the saddle-point methods it replaces.