Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work presents an implementation of the Hessian approach for certifying the convexity of differential functions. It is argued that it complements the well-established disciplined convex programming (DCP). Some examples are presented to show that the proposed approach can be even more powerful than the DCP approach (e.g., in Section 7).
strengths_and_weaknesses: Strengths:
+ The paper is in general well-written, and the main message is easy to follow. 
+ The analysis is solid and correct, and the unique contributions are highlighted in a good way (unlike a few other Neurips submission I reviewed, which has obvious technical flaws or unclear contributions).
+ An implementation of the proposed approach is provided on an anonymized website.

Weakness
- Although well-motivated, it is unclear about the efficiency in terms of computation and storage to use the Hessian approach. Normally, people tend to avoid computing the Hessian explicitly, let alone verifying the positive semidefinitness of the Hessian over the entire domain. It seems like the proposed implementation can only deal with lower-dimensional problems or problems with very simple structures. What is the computational scalability in terms of time and storage?
- It is not very clear why the Hessian approach is better than the well-established DCP. For one thing, the DCP is more flexible (by simply adding more atoms) and requires less computation (without toughing the complicated Hessian computation). For another thing, the DCP is not just testing convexity, and it can further return a standard convex optimization (in a conic form) for practical computation. It seems that the Hessian approach can only test convexity in a large sense.
- From a technical-wise perspective, Proposition 1 is just another way to express the DCP rules for differential functions. It is unclear about differences in terms of the computational graphs as DAGs, compared to the DCP way. How do the DAGs work for a standard log det function, i.e. $f(X) = -\log \det(X)$?
questions: It would be better to clarify the computational properties of the proposal Hessian approach. 
limitations: The evaluation of the proposed Hessian approach is relatively limited and not solid. More practical examples will help convince the effectiveness.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper implements the Hessian approach for certifying the convexity of functions, which complements the well-established disciplined convex programming approach and works for non-differentiable functions.
strengths_and_weaknesses: Strengths:
- The paper writing is very good and the presentation is clear.
- The implementation is based on a formal language that is sufficiently rich to support a large class of problems. The anonymized implementation demo is promising.
- The fundamentals of the implementation seem to be solid by using computational graphs for Hessians, the rule set and atoms.

I would say I am not an expert on this field, i.e., computational frameworks for convex optimization. My best educated guess is that the paper has a solid background as well as an attractive web demo. I am willing to learn from other reviewers' comments and the rebuttal.
questions: See the comments above.
limitations: Yes.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors present a framework to certify the convexity of some functions from their computational graphs. The usual tool to show the convexity of functions is to either show it by hand or use CVX which implements classical rules to know whether some compositions of functions are convex. As pointed out by the authors and as well known by the community, cvx has several limitations. In particular numerous functions need to be added manually as base "atoms" (i.e., basic convex functions) to demonstrate the convexity of some more complex functions. Even with these atoms, cvx may not be able to certify the convexity of some functions. The authors propose an alternative set of rules based on certifying the positive definiteness of Hessians through simple algebraic rules plus a few additional ones. The authors chose to present their ideas through several examples and a few propositions rather than a constructive framework. The authors present how their framework can encompass and surpass CVX to certify the convexity of new convex functions. 
strengths_and_weaknesses: Strengths:
- The emergence of deep learning networks has diminished the appeal of convex modeling of problems. Yet, in numerous situations, practitioners may develop complex models (as in e.g. Bayesian statistics) where convexity could be a criterion to decide which model to prefer. So though the paper may seem not timely, I believe it can still be a very useful tool for the community. 
- While the rules proposed by the authors appear extremely simple (Proposition 1) and not new, they are able to circumvent the need for all "patches" done in CVX (that is adding more and more basic functions). In other words, the framework proposed by the authors appears to be a better path to building a sound framework to prove the convexity of functions. 
- The authors still require a few additional rules such as Proposition 2. But this might be where the paper appears the most interesting: finding as few additional and simple rules as possible to capture numerous cases beyond just adding log-sum-exp as an additional function.
- Overall, this is an original contribution to a topic that seems to have been often overlooked by either simply using CVX, or just checking the positive definiteness of the Hessian symbolically yet at low scale, or simply discarding the issue by saying that as long as the algorithm converges it could be enough. 
- The available code is user-friendly. 

Weaknesses:
While the idea is original and promising, there are several limitations, some can be seen as future directions, some are due in my opinion to the presentation.  
- The main issue for me is the lack of formalism. While I appreciate the examples, there is no pseudo-code shared to understand the mechanisms of the approach and help peers to build upon it. The approach proposed by the authors may be a very interesting starting point to understanding the completeness/limitations of DAG representations of functions to certify convexity. Yet, without a few more formalism it cannot be built upon. 
- There are also a few definitions that are simply not defined or understandable as detailed in the questions.  

Update after having personally explored a bit more frameworks such as JAX from Google:
- Though again, I would have liked to understand some pseudocode better to help other people build on this idea, I also realized that this could probably easily be implemented as part of homoiconic programming languages such as Julia or JAX. Namely, these languages parse functions in form of expressions which I think are quite similar to what the authors are doing. So I updated my score since I believe this is an original yet simple and really useful tool that the authors developed and that could readily be integrated into some machine learning packages. I would sincerely appreciate it if the authors could add more background (in the appendix with some pseudocode or some generic framework *if possible*), this could have the potential for further research maybe as long as the authors make the effort to help other researchers build on it. 
questions: - What is the definition of a normalized expression DAG? What is a normalized vectorized form?
- The authors mention a "language for representing multivariate function (see the supplementary material)" line 122 in the text. However, I do not see where this language is formally described. If the authors refer to Figure 1, this Figure is simply not understandable: what ['], [.] mean ? What is written in the factor line? The authors may come from a field where these expressions are obvious but if they wish their paper to be read they need to give proper definitions and gentler introductions to their formalism. 
- The proof of Propositions 1 and 3 are rather trivial and could be put in the Appendix in order to give a formal definition of the framework or at least a pseudocode of the algorithm. 
- An example motivated by real applications (such as the modeling of some data with a complex model) would greatly improve the relevance of the paper (though the current framework appears to be already a good tool for it). 
limitations: - As the authors mention, the current formalism does not incorporate non-smooth functions which are often used as when using a ReLU or the l1 norm. 
- The authors do not mention that convexity is not necessary to ensure convergence of e.g. first-order algorithms. Non-convex gradient dominating functions can also be optimized efficiently by a first-order method. This unfortunately limits the relevance of the approach for several problems that have been shown to satisfy a gradient dominating property while not convex.
review_title: null

Meta-review: metareview: This was a though call. Two reviewers were only slightly positive about the paper and one of them did not seem to understand it very much, while a third reviewer who is an expert, really like the paper very much and so I tend to accept.
confidence: Less certain
Decision: Accept