acceptodds
Withdrawn from ICLR 2027

Monotone Optimisation with Learned Projections

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Optimisation algorithms typically assume oracle access to objectives and constraints, yet in many applications these functions are available only through data. To recover them, a common approach learns a surrogate for each function and optimises over it, but this can be unnecessarily expensive and may fail to preserve the structure required by the optimisation algorithm. We study this problem for monotone optimisation, a class of non-convex problems which can be solved globally using the Polyblock Outer Approximation (POA) algorithm. Our key observation is that POA does not require the constraint functions themselves, but only a scalar quantity we call the radial inverse. Learning this quantity directly replaces POA's inner bisection loop over a learned constraint with a single radial inverse evaluation. We characterise exactly which maps arise as radial inverses of monotone constraints, and relate their approximation error to perturbations of the feasible set and optimal objective value. Building on these results, we introduce Homogeneous-Monotone Radial Inverse (HM-RI) networks, structured min-max models that enforce the monotonicity and positive-homogeneity of radial inverses by construction. Across synthetic monotone optimisation problems and a cellular transmit-power application, HM-RI improves solution quality over direct constraint surrogates and local optimisation baselines by up to 58.6 percentage points relative to the Oracle reference objective, while achieving a speed-up over bisection-based POA with learned constraint surrogates, with the largest solution-quality gains occurring in data-limited and piecewise-constant settings.

Primary area:
optimization
Keywords:
global optimisation, branch and bound, monotonic optimisation, surrogate-based optimisation

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_aQgcOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper considers a constrained monotone optimization problem where oracle access to the objective function but some constraint functions are not directly accessible and are only available through data. The goal is to globally solve this nonconvex problem using the Polyblock Outer Approximation (POA) algorithm. While a direct adaptation can be done by using data to learn the unavailable constraint function, this involves repeated inner bisection loop to evaluate radial projections. The paper proposes to instead learn the so-called radial inverse, which they showed to be directly related to the radial projection. The proposed Homogeneous-Monotone Radial Inverse (HM-RI) networks learn the radial inverse using structured min-max models, which are used within POA. HM-RI is shown to improve solution quality across synthetic problems and a cellular transmit-power application.

Critical strengths

The observation in Proposition 2 that connects the radial projection to the radial inverse, and the recognition that positive-homogeneity, monotonicity and right-continuity properties are sufficient to construct a radial inverse (Proposition 3) are simple observations. Nevertheless, this led to the development of the paper's framework to apply POA by learning radial inverses as a surrogate for learning the constraint functions.

Critical weaknesses
  1. One of the main concerns is that this paper's theoretical guarantees are insufficient. Propositions 1 to 3 are basic properties that are likely well known. Proposition 4 is also not a surprising result given the construction of ϕθ\phi_{\theta}. Theorem 1 provides a known guarantee for POA, while Propositions 5 and 6 establish error bounds. However, a theoretical guarantee that the resulting overall algorithm (that includes the training to learn the radial inverse) converges to the (approximate) global solution of the original optimization problem is lacking. Overall, the paper offers only marginal contributions and may not meet the high standards expected at this conference.

  2. Another major issue is the evaluation metric. The paper's goal is to globally solve the monotone optimization problem where some constraint functions are not available directly. However, the authors used an evaluation metric that projects the obtained solution to the true feasible set using ground-truth constraint functions. Hence, feasibility is not guaranteed. Figure 3 provides some partial answers, but the proportion of feasible solutions obtained by the algorithms (if any) is not reported. The sizes of the experiments are also very small, and limited applicability to practical machine learning problems is a concern.

Questions for authors
  1. The approach is only applied to the g_i's. Is it possible to extend it to when the h_j's are also not directly available?
  2. The experiments are too small and most of them are synthetic. What is the largest size that can be reasonably handled? What are other applications that can be tackled?
  3. What is the proportion of the returned solutions that are feasible for the original problem?
  4. Does the runtime comparison in Section 5 include training costs? While reporting optimization time separately is reasonable when the learned models are reused across multiple problem instances, it would be helpful to report the training times for HM-RI and M-Net and discuss how many instances would be needed to amortize these costs.
Reviewer_9UySOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies monotone optimisation when the constraint functions are not directly available and must be learned from data. The authors propose learning the radial inverse required by the Polyblock Outer Approximation (POA) algorithm, thereby replacing repeated bisection-based projections with a single network evaluation. They characterise radial inverse functions through monotonicity, positive homogeneity and right-continuity, and introduce Homogeneous–Monotone Radial Inverse (HM-RI) networks that satisfy these properties by construction. The paper also establishes universal approximation and error propagation results relating radial-inverse approximation to feasible-set and objective-value perturbations. Experiments on four synthetic problem families and a cellular transmit-power application evaluate solution quality, runtime and the contribution of the architectural constraints.

Critical strengths
  • The algorithm-aware idea to learn the projection primitive POA needs (the radial inverse) instead of the full constraint is clear and motivating.
  • Every HM-RI model is the radial inverse of some increasing constraint function, so its learned projection is the exact monotone projection for a learned monotone problem (Prop. 3).
  • The power-mean smoothing preserves monotonicity and positive homogeneity exactly.
  • The experiments are performed with care, including structural ablations, paired bootstrap intervals, a noise study and a dimension sweep.
  • Useful observation that held-out loss and solver quality are almost uncorrelated (Table 7).
Critical weaknesses
  • The fixed-threshold part of Prop. 3 has a close classical antecedent (Rubinov and Glover, 1998, Prop. 3.3 and Cor. 3.4), which is not cited.
  • P-Obj uses the true constraints to re-project returned points and mainly measures direction. Figure 3 and the cellular analysis (App. G.1) give aggregate violation values, but true-feasibility rates are not reported.
  • No baseline learns a non-monotone surrogate of the constraint function itself. On P-Obj, POA on M-Net performs close to local solvers on M-Net (Tables 1, 4, 6), so the value of global over local optimisation is not isolated.
  • The error guarantees cover only part of the experiments:
    • App. B.4 excludes lower-bound constraints, but the experiments use x ≥ 0.1.
    • Prop. 6 assumes a uniform error bound that training does not certify.

Rubinov, A. M., & Glover, B. M. (1998). “Duality for increasing positively homogeneous functions and normal sets.” RAIRO – Operations Research, 32(2), 105–123.

Questions for authors
  1. Rubinov and Glover (1998, Proposition 3.3 and Corollary 3.4) establish a correspondence between closed normal sets and increasing positively homogeneous gauge functions. Could the authors clarify which aspects of Proposition 3 go beyond this classical result, particularly the threshold-dependent characterisation?

  2. Why is there no baseline that learns the constraint function using an unconstrained, non-monotone surrogate? Also, POA on M-Net appears to perform similarly to local solvers on the same surrogate in several settings. Could the authors further separate the benefits of learning the radial inverse from those of using a global rather than local optimisation method?

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

This paper studies monotone optimisation when constraint functions are available only through data. The authors propose directly learning the radial inverse functions required by the Polyblock Outer Approximation (POA) algorithm, replacing bisection in the projection step with a single network forward pass. To this end, they introduce HM-RI networks that enforce monotonicity and positive homogeneity, and provide a structural characterisation of radial inverses, universal approximation results, and an analysis of error propagation. Experiments cover four synthetic problem families and a cellular network power optimisation task. The results show advantages in solution quality and runtime over directly learning the constraint functions.

Critical strengths
  1. Directly learning the projection information that the solver actually needs is a valuable idea. The authors further enforce monotonicity and positive homogeneity through the network architecture and analyse how learning errors affect the feasible region and the optimal objective value. This establishes a coherent connection between the method's design and its theoretical analysis.

  2. The experiments compare different constraint representations using the same data, and the ablations examine the contributions of the two structural properties, helping explain the performance gains. Compared with the direct constraint surrogate, HM-RI achieves better solutions on several problems while achieving a speedup of approximately 3.0-4.7 times, demonstrating the potential of this design.

Critical weaknesses
  1. There remains a gap between the primary evaluation metric and the practical usability of the solutions returned by the methods. P-Obj in Section 5 requires reprojecting the returned point using the true constraints, so it primarily measures the quality of the search direction. Figure 3 usefully supplements this with the original objective values and constraint violations, but feasibility rates for the solutions as returned, and comparisons of objective values under a common feasibility tolerance, are still missing. For applications in which the true constraints cannot be queried directly, it remains unclear how much of the reported improvement translates into directly usable optimisation results.

  2. The experimental settings do not yet adequately represent practical data-driven scenarios. In the synthetic experiments, the models receive the complete instance parameters zz that determine the constraint functions. The application experiment also uses a simplified setting that excludes inter-cell interference. While these experiments validate the method's design, the current evidence does not establish whether similar advantages would hold when only limited observations and incomplete instance information are available. This makes it difficult to assess the method's range of practical applicability.

Questions for authors
  1. What fraction of the solutions returned by each method satisfy the true constraints without post hoc correction? Under a common constraint violation tolerance, does HM-RI retain its advantage in objective value? These results would help clarify how much practical optimisation benefit the improvement in P-Obj represents.

  2. What observable information do the instance parameters zz correspond to in practical applications? If only partial instance features are available, rather than the complete parameters determining the constraint functions, does the current training and optimisation procedure remain applicable? Is there experimental or analytical evidence supporting this setting?

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

Related papers

Discussion (0)

Sign in to comment.