acceptodds
Under review as a conference paper at ICLR 2027

Recognizing Signomial Convexity is Hard

Abstract

Signomials—finite sums of generalized monomials with real exponents—are a natural machine learning model, combining parsimonious representations of power laws, inverse relationships, and multiplicative interactions with universal approximation and interpretable parameters. In fact, 45 of the 100 equations in the AI Feynman benchmark admit signomial representations. Moreover, signomial optimization is widely used in engineering design, communications, economics, and machine learning, but is computationally intractable in general. Convexity, the gold standard for efficient optimization, offers three routes to tractability for signomials: a signomial may be convex in its original variables, become convex after a logarithmic change of variables, or, when positive, become convex after additionally taking the logarithm of its value—the structure underlying disciplined geometric programming. We show that recognizing each form is strongly NP-hard, both on compact domains and globally. Our proofs start from gap-promise variants of polynomial convexity and develop polynomial-to-signomial reductions that preserve curvature gaps under the relevant logarithmic transformations.

Primary area:
optimization
Keywords:
signomial optimization, convexity recognition, strong NP-hardness, hidden convexity, log-log convexity

Reviews

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

The paper studies the complexity of recognizing three notions of signomial convexity: ordinary convexity, log-coordinate convexity, and log-log convexity. It establishes strong NP-hardness for all three notions, both on compact boxes and globally. The ordinary-convexity results follow directly from known polynomial-convexity hardness results. The main technical contributions concern the transformed notions: exponential approximations preserve curvature gaps, while coupled exponential auxiliary terms extend the constructions globally, preserve nonconvexity witnesses, and ensure positivity in the log-log case. The results are established through explicit polynomial-time reductions, supported by quantitative Hessian and log-curvature estimates, positivity guarantees, and polynomial bounds on the numerators and denominators of the rational input data.

Critical strengths

The main strength is establishing hardness of recognizing log-coordinate and log-log convexity, which does not follow directly from existing polynomial results. The reductions preserve curvature gaps under these transformations and extend to the global setting while ensuring positivity in the log-log case. These results clarify a fundamental limitation of automatic convexity recognition for signomials and are the main reason I support acceptance.

Critical weaknesses

None.

Questions for authors

I have no further clarification questions that would materially affect my current assessment.

1 comment

We thank the reviewer for the careful reading, positive assessment, and recognition of our technical contributions.

Reviewer_shYFOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper shows that recognizing whether a given signomial function, i.e.,

\qquad x\in R_{++}^{n},$$ where $A\subset\mathbb{R}^{n}$ is finite and $c_\alpha\in\mathbb{R}$, is convex, log-coordinate convex, or log-log convex is strongly NP-hard, both on compact domains and globally. For log-log convexity, the function is assumed to be positive throughout the relevant domain.
Critical strengths

Clear Contribution
The contribution is very straightforward and easy to understand. It shows that recognizing whether a given signomial function is convex is strongly NP-hard.

Novelty
The results have not been shown before.

Critical weaknesses

Importance for ML
It is not clear how the results impact and relate to ML. Yes, the paper states that 45 of th 100 AI Feynman benchmark examples can be stated as signomials. Yet, the paper does not establish how the recognition of convexity is important in ML. It states that

Such problems arise in machine learning, wireless communications, inventory management, biotechnology, aerospace engineering, and chemical engineering,

yet it never provides a concrete example. Hence, the importance within ML of recognizing whether a given signomial function is convex is left open.

Questions for authors

Could you please provide concrete examples from ML where you show that recognizing whether a given signomial function is convex? Please go beyond disciplined geometric programming (DGP) where we can formulate geometric programming problems that are by construction log-log convex. Usually, we provide a (loss) function that we want to minimize and show/state, that it is convex or not. In such cases, it is not important that it is NP-hard to decide whether general functions are convex. So where is it important here for ML?

3 comments
AuthorsOpenReview ↗

Relevance to Machine Learning

We thank the reviewers for carefully reading our work and for recognizing its technical quality, novelty, and clarity. The principal concern raised in the reviews is its relevance to machine learning and ICLR. While it is certainly true that signomial optimization is not central to, say, training state-of-the-art transformer models, we believe it is within the scope of ICLR: optimization for ML is one of the areas explicitly listed in the call for papers. Existing work on signomial optimization that has appeared in ML venues includes applications to learning, e.g., Zhao et al. (NeurIPS 2016) [1] and Choi et al. (AAAI 2020) [2], as well as work on signomial regression, e.g., Calafiore et al. (IEEE TNNLS 2020) [3], Błądek and Krawiec (IEEE TEVC 2023) [4], and ECSEL (ICML 2026) [5].

Convexity recognition has immediate algorithmic consequences. First, for signomial optimization, if the problem is (log) convex, it can be handled by convex optimization after the corresponding transformation, providing reliable algorithms and global optimality guarantees. Secondly, convexity is a natural prior when learning regressors from data. Utility functions, for example, are commonly assumed to be concave to capture diminishing marginal returns [6]. Moreover, for a conic optimization problem with cost direction cc and right-hand-side vector bb, the map (b,c)↦OPT(b,c) \mapsto \mathrm{OPT} is convex in bb when cc is fixed and concave in cc when bb is fixed [7].

Our hardness results have important implications: We show that checking whether a signomial optimization problem is (log) convex, or solving a general (log) convex signomial regression problem, are hard. Consequently, as the reviewer correctly observes, it is natural to resort to the use of disciplined (log) convex optimization methods, for which the desired property of the problem/regressors holds by construction, e.g., [8]. Our results help explain why such restrictions, efficiently checkable sufficient conditions, and incomplete or heuristic certification methods are natural and valuable.

If our response addresses the reviewers' concerns about the relevance of our work to ICLR, we respectfully ask them to reconsider their scores and/or their confidence. We would be happy to address any remaining questions during the discussion period.

[1] Han Zhao, Pascal Poupart, and Geoffrey J. Gordon. A Unified Approach for Learning the Parameters of Sum-Product Networks. Advances in Neural Information Processing Systems, 29:433–441, 2016.

[2] YooJung Choi, Golnoosh Farnadi, Behrouz Babaki, and Guy Van den Broeck. Learning Fair Naive Bayes Classifiers by Discovering and Eliminating Discrimination Patterns. Proceedings of the AAAI Conference on Artificial Intelligence, 34(6):10077–10084, 2020.

[3] Giuseppe C. Calafiore, Stéphane Gaubert, and Corrado Possieri. Log-Sum-Exp Neural Networks and Posynomial Models for Convex and Log-Log-Convex Data. IEEE Transactions on Neural Networks and Learning Systems, 31(3):827–838, 2020.

[4] Iwo Błądek and Krzysztof Krawiec. Counterexample-Driven Genetic Programming for Symbolic Regression With Formal Constraints. IEEE Transactions on Evolutionary Computation, 27(5):1327–1339, 2023.

[5] Adia C. Lumadjeng, Ilker Birbil, and Erman Acar. ECSEL: Explainable Classification via Signomial Equation Learning. Proceedings of the 43rd International Conference on Machine Learning (ICML), PMLR 306:82102–82140, 2026.

[6] Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. Microeconomic Theory. Oxford University Press, 1995.

[7] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

[8] Akshay Agrawal, Steven Diamond, and Stephen Boyd. Disciplined Geometric Programming. Optimization Letters, 13(5):961–976, 2019.

Calafiore et al. [3] are a clear case where curvature matters for design, but their model class guarantees the required curvature by construction, so they don’t need to recognize it post-fit. Błądek and Krawiec [4] verify shape constraints in symbolic regression, but don’t show signomial convexity recognition as a bottleneck. The other cited learning papers show signomials arise, but don’t make clear how the recognition result would affect their methods.

The direct implications for the cited ML workflows remain unclear to me. I nevertheless view the hardness result as a valuable contribution to optimization and have adjusted my score accordingly.

Thank you for your thoughtful follow-up and for reconsidering your assessment. We would like to clarify the role of convexity recognition in these learning workflows.

Błądek and Krawiec [4] heuristically construct regressors intended to be convex. They test Jensen’s inequality and, when a violation is found, update the regressor to address that counterexample. However, satisfying Jensen’s inequality at the tested points alone does not guarantee that the final regressor is globally convex. Our results show that exact verification of convexity of a signomial regressor constructed in such a manner is hard.

As illustrated by the examples in our first response, convexity is a natural structural requirement for learned regressors. However, as an immediate consequence of our hardness results, it follows that the problem of convex signomial regression is computationally hard.

We thank the reviewer again for raising their score. We hope this clarification alleviates any remaining concerns the reviewer may have.

Reviewer_orDLOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper presents proofs of the strong NP-hardness of determining the convexity of signomials (and closely related classes of functions), both globally and on compact domains. The paper uses established and new techniques to derive a curvature-preserving gap reduction to known results in polynomial optimization, in particular, gap-promise problems for polynomial convexity. The proofs presented in this work use an exponential deformation formulation to derive a reduction in the constrained case. In the unconstrained setting, the proofs rely on a cleverly designed auxiliary function to address curvature separation globally.

Critical strengths

S1. Novel Technical Insight

The paper presents elegant reductions using signomial approximations to prove its key results. The use of the canonical exponential deformation in the constrained case and the coupled hyperbolic cosines in the unconstrained case is clever and may be of independent interest. The proofs are stated rigorously and are, to the best of the reviewer’s understanding, correct.

S2. Strong Scholarship

The paper is very well presented. The notation is consistent, and key concepts are easy to follow. The proofs (and proof sketches) are well written, and the paper is self-contained.

Critical weaknesses

W1. Venue Fit

This work is of high quality and may be more suitable for publication at a more appropriate venue, and may be of little interest to much of the ICLR optimization community, as it has no connection to statistical or learning theory.

Questions for authors

Clarifications

  1. In the proof of Theorem 2.1, can the authors provide a brief sketch of the proof when the dimension of the problem (n) is odd in the unconstrained case? Perhaps a more general linear map may suffice.

Nitpicks not affecting the overall assessment:

  1. Line 404, index of summation missing brackets

  2. Style: Could the authors provide fully self-contained versions of the theorems presented in the main body, and provide a more clearly stated definition of their stated sense of "strong" NP Hardness (Lines 188-192)?

Score Justification

Given the short review period for this ICLR, I keep a low confidence score as I may not have fully understood a few nuances of this work. My review is constrained by the new review guidelines of this ICLR, and I would be pleased to expand on the points raised in the review. I am eager to engage with the authors in the rebuttal period to improve their manuscript and revise my score. In particular, I would be pleased to raise the score if the authors can make the case for ICLR as a suitable venue for publication.

4 comments
AuthorsOpenReview ↗

Machine Learning Relevance and Technical Clarifications

We thank the reviewers for carefully reading our work and for recognizing its technical quality, novelty, and clarity. Below, we clarify its relevance to ICLR, address the question on odd dimensions, and describe the planned presentation improvements.

W1: Venue Fit.

The principal concern raised in the reviews is its relevance to machine learning and ICLR. While it is certainly true that signomial optimization is not central to, say, training state-of-the-art transformer models, we believe it is within the scope of ICLR: optimization for ML is one of the areas explicitly listed in the call for papers. Existing work on signomial optimization that has appeared in ML venues includes applications to learning, e.g., Zhao et al. (NeurIPS 2016) [1] and Choi et al. (AAAI 2020) [2], as well as work on signomial regression, e.g., Calafiore et al. (IEEE TNNLS 2020) [3], Błądek and Krawiec (IEEE TEVC 2023) [4], and ECSEL (ICML 2026) [5].

Convexity recognition has immediate algorithmic consequences. First, for signomial optimization, if the problem is (log) convex, it can be handled by convex optimization after the corresponding transformation, providing reliable algorithms and global optimality guarantees. Secondly, convexity is a natural prior when learning regressors from data. Utility functions, for example, are commonly assumed to be concave to capture diminishing marginal returns [6]. Moreover, for a conic optimization problem with cost direction cc and right-hand-side vector bb, the map (b,c)↦OPT(b,c) \mapsto \mathrm{OPT} is convex in bb when cc is fixed and concave in cc when bb is fixed [7].

Our hardness results have important implications: We show that checking whether a signomial optimization problem is convex, or solving a general (log) convex signomial regression problem, are hard. Consequently, as Reviewer shYF correctly observes, it is natural to resort to the use of disciplined (log) convex optimization methods, for which the desired property of the problem/regressors holds by construction, e.g., [8]. Our results help explain why such restrictions, efficiently checkable sufficient conditions, and incomplete or heuristic certification methods are natural and valuable.

If our response addresses the reviewers' concerns about the relevance of our work to ICLR, we respectfully ask them to reconsider their scores and/or their confidence. We would be happy to address any remaining questions during the discussion period.

[1] Han Zhao, Pascal Poupart, and Geoffrey J. Gordon. A Unified Approach for Learning the Parameters of Sum-Product Networks. Advances in Neural Information Processing Systems, 29:433–441, 2016.

[2] YooJung Choi, Golnoosh Farnadi, Behrouz Babaki, and Guy Van den Broeck. Learning Fair Naive Bayes Classifiers by Discovering and Eliminating Discrimination Patterns. Proceedings of the AAAI Conference on Artificial Intelligence, 34(6):10077–10084, 2020.

[3] Giuseppe C. Calafiore, Stéphane Gaubert, and Corrado Possieri. Log-Sum-Exp Neural Networks and Posynomial Models for Convex and Log-Log-Convex Data. IEEE Transactions on Neural Networks and Learning Systems, 31(3):827–838, 2020.

[4] Iwo Błądek and Krzysztof Krawiec. Counterexample-Driven Genetic Programming for Symbolic Regression With Formal Constraints. IEEE Transactions on Evolutionary Computation, 27(5):1327–1339, 2023.

[5] Adia C. Lumadjeng, Ilker Birbil, and Erman Acar. ECSEL: Explainable Classification via Signomial Equation Learning. Proceedings of the 43rd International Conference on Machine Learning (ICML), PMLR 306:82102–82140, 2026.

[6] Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. Microeconomic Theory. Oxford University Press, 1995.

[7] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

[8] Akshay Agrawal, Steven Diamond, and Stephen Boyd. Disciplined Geometric Programming. Optimization Letters, 13(5):961–976, 2019.

Clarification on odd dimensions.

Thank you for requesting this clarification. Hardness on the even-dimensional subfamily already establishes NP-hardness of the unrestricted problem. Odd-dimensional target instances can be obtained by introducing an additional variable through an affine term, whose Hessian is zero and hence does not affect convexity. For example, define

\qquad (u,v,t)\in\mathbb R_{++}^{2n+1}.$$ Then $\nabla^2\widetilde f=\operatorname{diag}(\nabla^2 f,0)$, so $\widetilde f$ is convex if and only if $f$ is convex, which is equivalent to convexity of $p$ on $\mathbb R^n$. This construction also preserves the fixed degree and polynomial encoding length. We will add this observation to the proof. > Nitpicks: notation, theorem statements, and strong NP-hardness. We will correct the summation index at Line 404 to $s,t\in\\{-1,1\\}$. We will make the main theorems self-contained by explicitly specifying their inputs, numerical encoding, domains, and convexity properties, including the positivity promise for log-log convexity, either in the statements or in the text immediately preceding them. We will clarify Lines 188–192 by first giving the general definition: a numerical decision problem is strongly NP-hard if it remains NP-hard when its integer numerical data are bounded by a fixed polynomial in the structural instance size. In our setting, rational data are represented by integer numerators and positive denominators in lowest terms. Our NP-hardness results hold even when the numerators and denominators of both signomial coefficients and exponent entries are polynomially bounded in the number of variables, thereby establishing strong NP-hardness. For the gap-convexity problems, these bounds also apply to the positive rational thresholds $\gamma_+$ and $\gamma_-$, ensuring that $\gamma_+,\gamma_-\ge 1/\operatorname{poly}(n)$.

I thank the authors for their clarifications. I appreciate the inclusion of the odd-dimension case, while I agree that the main claim of the paper did not require it.


I believe that they have sufficiently addressed my major concern, and I am raising my score from 3 to 4 and my confidence from 2 to 3. I strongly believe the paper merits acceptance at ICLR.

Thank you for taking the time to engage with our work and reconsider your assessment. We sincerely appreciate your support and will revise the manuscript in light of your feedback.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.