acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
optimization
Keywords:
min-max optimization, minimax theorem, saddle-point problems

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_839HOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper presents a framework for the unrolling of optimization methods for solving min-max and max-min problems using majorization-majorization. The authors claim that their approach allows to swap between min-max and max-min formulations of the MM problem without loss of accuracy, which allows the practitioner to pick whichever is easier computationally. They provide a guarantee of objective decrease. The paper includes experiments which show a significant improvement in solution accuracy on several problem instances.

Critical strengths
  1. The idea of using majorization-minorization in the unrolling of optimization methods for min-max and max-min problems is novel and well-motivated.
  2. The numerical experiments are realistic, and the proposed method shows a significant gain in performance against the baselines. The code to reproduce the experiments is provided in the supplementary material and appears sound, with the baseline (competing) methods implemented faithfully.
Critical weaknesses
  1. The overall readability of the paper requires significant improvement; as it is, the paper is difficult to parse due to an abundance of flair and imprecise wording; refer to Questions for Authors for main comments.

  2. Some of the mathematical derivations in the proofs are questionable, and sometimes contradict the statement of the theorems. It is possible that the theoretical results are not wrong, but are still hard to reproduce due to poor readability of the paper (see point above). Again, refer to Questions for Authors.

Questions for authors

Mathematical results

The core theorem of the paper is Theorem 1, which is necessary for the other theoretical results of the paper. As stated, It assumes either $ \mathcal{X} $ is compact ("hypothesis (i)"), or $ \mathcal{Z} $ compact and $ g_s(\cdot, \mathbf{z} \mid \mathbf{x}^t) $ has bounded sublevel sets for some $ \mathbf{z} \in \mathcal{Z} $ ("hypothesis (ii)"). The proof is presented in Appendix C.2. However:

  1. The section of the proof corresponding to hypothesis (i) requires both $ \mathcal{X} $ and $ \mathcal{Z} $ to be compact. Could the authors clarify this?
  2. In the section of the proof corresponding to hypothesis (ii), the last step in the chain of derivations

max⁡zgs(x,z∣xt)≥gs(x,z0∣xt)>gs(xt,z0∣xt)≥min⁡x′max⁡zgs(x′,z∣xt)\max_{\mathbf{z}} g_s(\mathbf{x}, \mathbf{z} \mid \mathbf{x}^t) \geq g_s(\mathbf{x}, \mathbf z_0 \mid \mathbf{x}^t) \gt g_s(\mathbf{x}^t, \mathbf z_0 \mid \mathbf{x}^t) \geq \min_{\mathbf{x}'} \max_{\mathbf{z}} g_s(\mathbf{x}', \mathbf{z} \mid \mathbf{x}^t)

is unclear. Could the authors explain how gs(xt,z0∣xt)≥min⁡x′max⁡zgs(x′,z∣xt)g_s(\mathbf{x}^t, \mathbf z_0 \mid \mathbf{x}^t) \geq \min_{\mathbf{x}'} \max_{\mathbf{z}} g_s(\mathbf{x}', \mathbf{z} \mid \mathbf{x}^t) is justified (and, relatedly, which set does $ \mathbf{x}' $ live in here)?

  1. Related to 1: the problem statement in Section 2 does not mention a requirement on compactness of either of the two variable sets, but it is required in Theorem 1.

Readability

As stated in Weaknesses, the readability of the paper needs significant improvement. The following are the major points which, in my opinion, need to be addressed the most to this end, in order as they come up in the paper:

  1. The statement "No single objective has a saddle point for its minimizer" is broad and poorly worded. Given that the paper repeatedly refers to "eliminating the saddle point" as one of its core contributions, the statement should be replaced with a more precise one.
  2. In my opinion, the introduction and contributions sections could, and should, be condensed significantly without losing meaning.
  3. The restriction of the class of functions $ f $ on line 165 reads as a restriction of the entire class of functions for which the method described in the paper is applicable, and not a particular application. Similar issues of conflating the general problem statement and the worst-case-loss instance appear throughout the work. The paper would benefit from a more precise separation of the two.

Related works

The authors compare their proposed method to the Learned Primal-Dual of Adler & Öktem (2018). Although they do not employ majorization-minorization, the methods superficially appear similar. In my opinion, the paper would benefit from a more detailed discussion of Learned Primal-Dual. Particularly, I would be interested to see how the RUN-D network differs from Unrolled GDA in the setup of the logistic loss experiment, if first-order gradient method was chosen instead of Newton, and, futhermore, if closed-form solutions or specialized solvers are unavailable in neither "window".

Reviewer's Conclusion

The contribution that the paper claims - relaxation-free unrolling of min-max/max-min optimization using majorization-minorization - is non-trivial and would warrant publication. The experimental results show clear advantage over state-of-the-art on realistic instances. However, given the points outlined above, I am hesitant whether the method's theoretical guarantees indeed hold up; moreover, the presentation of needs significant work. I would be willing to increase my score if:

  1. The presentation is vastly improved.
  2. The authors address the questions regarding the mathematical results and the positioning of the paper.
Reviewer_zKZxOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper uses majorization and variable elimination to turn a min–max problem into a sequence of single-variable problems. RUN-P and RUN-D learn the remaining solver's step sizes and reject proposals that increase the surrogate. The experiments cover quadratics, fair PCA, and worst-group logistic regression.

Critical strengths
  1. Comparing the two routes is useful. It shows when the extra cost of an inner solve can be worthwhile.
  2. The experiments include tuned baselines, a trained GDA control and held-out instances, which make the comparisons more convincing.
Critical weaknesses
  1. It seems that the two reductions already appear in MM4MM [A]. I find the learned unrolling interesting, but the comparison with MM4MM is not clear to me.

  2. Newton-3 is counted as four budget units, but the Hessian and linear solves add extra work. Table S8 gives runtimes at the largest budget, but the final objective values differ. I still wonder which method reaches the same objective value faster.

  3. The experiments are still on small problems, including synthetic data and DIGITS. Although Table S6 increases the quadratic dimension to 200, I wonder whether the same gains would hold on larger datasets

[A] Saini et al. (2024). Min-Max Framework for Majorization-Minimization Algorithms in Signal Processing Applications: An Overview.

Questions for authors

see weakness

Reviewer_otSPOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper titled “ RUN: A Relaxation-Free Bridge from Min-Max/Max-Min Optimization to Neural Networks " tackles the min-max problem which has notoriously hard combinatorial structure and saddle point solution, that makes it hard to solve specially with deep neural networks. Unlike previous approaches, the authors find an exact, relaxation-free bridge that eliminates the two-player saddle point prior to unrolling, transforming the problem into a sequence of standard single-variable problems suitable for deep unrolled networks. They also show some convergence results. On the experimental front, they show the network built on the chosen reduction outperforms saddle point based methods on min–max quadratics,fair principal component analysis and worst-case-group risk, at a matched budget.

Critical strengths

Bypassing the two-player game by combining Majorization-Minimization with Sion's minimax swap is creative and mathematically sound. Removing the saddle point algebraically before constructing the network also eliminates adversarial cycling. RUN guarantees monotonic descent across every layer, even when weights are randomized which is a good result. The paper also provides clear criteria for choosing between architectures: RUN-D eliminates primal conditioning and does well excels primal dimension n > m, whereas RUN-P operates cheaply per layer when m is large.

Critical weaknesses

The experiments are reported on modest size low-dimensional and/or synthetic datasets only. The method is not evaluated on larger modern machine learning datasets which are common in, such as adversarial training or vision/NLP benchmarks, Therefore the issue scalability to deep non-convex parameter spaces has not been shown. When the dual RUN-d is applied to non-quadratic losses (e.g., logistic regression in group-DRO) which do not admit easy closed form solutions, the dual window must be solved using iterative Newton steps. This reintroduces nested optimization loops and significantly weakens the claim of an exact, parameter-free elimination. The model performance is dependent on \tau, whereby setting it too small or too large has consequences on the performance. The paper does not include analysis on how much this the sensitivity of \tau affects model performance.

Questions for authors

na

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.