Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: null
review_content: I'd like to thank the authors for the important work they put during the rebuttal. I believe that quality of the paper has been improved a lot since the initial submission. I am particularly happy to see the experimental results have improved.

Note that with state index it is now a MDP again (with non zero reward received at states of index K+1) so Split-POMDP machinery may not be necessary anymore. But I don't want to be picky !

I do not have any remaining remark related to soundness or clarity of the paper. As promised, I increase my rating to reflect my new opinion on the current state of the manuscript. Congrats !
review_title: Thank you for re-runing experiments

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Authors propose to learn coefficients and symbols connections in the problem of Symbolic Regression (SR) by combining Q learning and neural networks. They rely on the convexity properties of of ICNN to ensure that the Q function and the rewards R() are convex wrt the state S and the action A of the MDP defined.

They use the convexity properties and the determinism of the MDP to derive several guarantees on their method - namely, that the exact symbols can be recovered for noiseless datasets because the problem is locally convex in a neighborhood of the true minimum.


strengths_and_weaknesses: Strengths:

- i) solving complex combinatorial problem with RL is always an interesting approach
- ii) using ICNN to enforce good properties (and particular that the minimum is uniquely defined and easy to find) is a good take-home message from the paper
- iii) the experimental part contains numerous tasks and comparisons against other SOTA approaches, with figures and examples
- iv) experimental results are convinving about the eficiency of the method - even though I am not familiar with the field

Weaknesses:

major issues:

The whole approach consists in using Reinforcement Learning (RL), and more specifically Q-learning (and its neural network variants). Howerver RL requires to work on a Markov Decision Process (MDP), the Markov property must hold : P(s_2 | s_1, a_1) = P( s_2 | s_1, a_1, s_0, a_0). However it seems that the object defined here is not a proper MDP. Indeed, since the state s belongs to {0, 1} ^n_k we only have access to the activations of the layer k : no information about the previous activations, not mentioning the input x itself. Here, the state s has no knowledge of how "deep" we are in the equation being built. It feels weird : how a neural network can take the right actions if it does not "see" the whole input ? Moreover, in MDP, the reward depends of the current state s and action a, or of the current state s and future state s' (depending of the literature). This is not fulfilled by the construction given by the authors in either case.

If the problem is not a MDP, the Q function has no reason to exist, and fixed point based algorithms like value iteration (and variants such as Deep Q learning) are not guaranteed to converge. Even if the optimal Q function exists, it has no reason to be convex in general. This is not a property to be enforced with ICNN, it is a property of the MDP itself, that must be defined as such (Markov property must be fufilled !).

As said by authors in literature review, the problem of SR is NP hard. Hence, an attempt to convexify the problem that would yield polynomial time algorithm would fail. So either the problem cannot be cheaply convexified, either it induces a bias that prevents to find the global optimum of the original problem.

Even if it was a MDP, there are other issues. For example, the complexity of value iteration is O(S² * A) with A and S the action and space states respectively. For S defined by the authors, there is only 2^n_s states and 2^(n_s * n_s) actions. The total complexity of value iteration would be O( 2^(n_s  * n_s)). How does it compare to Deep Q learning in sample efficiency ? For dataset (1) the pool of activations is small, for (2) and (3) the pool of activations is only a singleton (!) the number of variables in input is also very small for (1) : only 3, while for (2) it is 5 nodes and for (3) it is 10 nodes. On those toy examples, the search space is so small that value iteration seems sufficient, no need for Deep Q learning

Theorem 1 is false. Since it is not a MDP, Q function is not defined. There is no reward in this MDP, only a convex surrogate function R() paramatrized by ICNN, that looks like the reward R received at each time step. But in reality, this R is not a Markvovian reward (that depends of state/action pair), it is a surrogate that depends of the final return of the trajectory. 

Forcing the surrogate R and the network Q to be convex using ICNN induces a bias, but can not be used to prove anything about the underlying MDP. 

l192 : "Then, we 192 prove that the convexity of the negative optimal Q-function eventually yields the exact equations."
Well, then, why is there a non zero error in experiments Fig. 3 ? Such error is not negligible.

minor issues:

i) It it not clear what neural networks bring here. In general their power in combinatorics is their generalization capabilities - i.e their capacity to interpolate the value of unseen inputs. Paper lack details about this precise contribution of NN.  

ii) Theorem 4 is very ad-hoc due to its complicated form. i,j and k variables are not defined. Even the appendix does not contain a clear statement o the theroem, only the proof. Hence, it is hard to understand what the objets clearly are. 

l 202 : what "exact equations" mean ? In general there might be no unicity of the equations, so that true equation and the one returned by the network might be different. 

iii) theorem 2 is assumes that the optimal W* is recovered (why ? How ?) and that the sequence of actions is selected according to the optimal policy Q*, assuming it exists, such that the optimum of Q* corresponds to exact equations (using the fact that the dataset is noiseless). Authors conclude the exacts equations can be recovered. This is essentially trivial : authors are concluding that under the hypothesis that the optimum exists and has been found, it has beend found... 

iv) theorem 3: it seems that authors are saying that in the neighborhood of the minimum, if for one of the examples there is no plateau (assumption 2), the second orer derivative (assuming it exists, assumption 1) is positive. For unconstrained minimization of twice differentiable function, this is a well known property: https://math.stackexchange.com/a/19473 (second paragraph)
questions: Could you clarify how W* is found ? By minimizing MSE with SGD over some randomly initialized W ? 

l 202 : what "exact equations" mean ? In general there might be no unicity of the equations, so that true equation and the one returned by CONSOLE might be different. 

Could you clarify what is the MDP exactly ? My whole understanding might be wrong ; but currently I feel like there is a recursive argument : a not well defined MDP is used to define a Q function (that should not exist) and a return (sum of the rewards received an the end of an episode - not markovian becasue states are too small and too poor to encode the equation being built), that is transformed into a convex reward R() given a ICNN surrogate, which is itself (using Theorem 1) used to explain that the aforementioned MDP is well defined (?) and that its Q function is convex.

Proof of theorem 4 (in appendix): authors uses the trick "x = s exp(log (|x| ))" with s the sign of x. This is always dangerous : s is not a constant, it it depends of x so one should write s(x) instead. Authors proceed with the proof for a fixed (chosen in advance) x_i until line 578 : then they introduce the objetcs y' and y'' which are defined for x_1..x_N. Since the notation s(x) is not used, it is not obvious (by reading the proof) that the differents values of s have been taken into account. I am not saying it is false, but it is worth explaining in the proof whether or not this is correct. This trick is sometimes fishy because of that.  


limitations: With my current understanding of the paper, the whole theoretical framework used in the paper is invalid, which seriously impedes its impact. Moreover the experiments seem to be very small, specially when there is only linear {x} symbol pools.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers the problem of symbolic learning using neural networks. The paper is focused on designing symbolic search algorithms with correctness guarantees. This is achieved by using a $Q$-learning framework, where the $Q$ function is modeled using an input convex neural network, ensuring exact temporal difference updates can be computed efficiently. The authors provide theoretical guarantees for the correctness of their algorithm, modulo a requirement to be able to fix neural network parameters exactly (a non-convex problem). This is balanced, however, by a follow up result showing that globally optimal points always lie in (strictly) convex neighborhoods. The method is tested on equation learning tasks, performing favorably.
strengths_and_weaknesses: Thanks to the authors for an interesting work on the salient topic of neural-symbolic learning. I enjoyed reading the paper, and certainly felt like I learned something. Some 

- The convexity results are really nice, and well supported by the ablations. It is worth noting of course that the overall procedure is not fully convex (which it cannot be due to NP-hardness results) but the non-convexity comes from needing to fit  neural network parameter, arguably a fairly benign form of non-convexity. 
- Experiments cover a number of different tasks, and appear thorough. Results seem promising, for instance the proposed method is considerably closer to the ground truth equations in Table 1 than the other methods. 

Stepping back a moment, the paper is well organized, although I found it quite information dense. The paper went through the important steps to make the work properly complete, including good, simple theoretical results, and an experiment section with comparisons to alternate methods, and ablations. The ablation section provides useful insights. For instance, the double-convexity of the $Q$ function is doing a lot of heavy lifting—removing it significantly impacts performance. This is encouraging, suggesting that the input convex network design is working well.

In all, this paper presents a method for neural-symbolic learning that appears non-trivial and effective. Importantly, it is accompanied by correctness guarantees for (large parts of) the learning algorithm. This is an especially promising sign in the context of symbolic learning, where finding exact solutions is of comparatively greater importance than in other areas. Overall I am broadly positive about this work. A disclaimer, however, is that I am not familiar with recent related works in this area. This is reason for the given confidence score, and will pay careful attention to any related works that may emerge during discussions. 
questions: - Why are you allowed to restrict the negative reward function to be convex? Of course it is permissible to model the $Q$ function, but rewards usually come from a ground truth. 
- Is  $Q(s, a)$ differentiable in $a$? It appears that for non-integral $a$, $Q$ is computed using a thresholding at $0.5$. This seems to me to introduce discontinuities. If so, why does this not make optimizing $\min_a Q(s,a)$ difficult?
limitations: Yes.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors propose a two-stage symbolic learning approach, where each stage is solvable with convex optimization. They then provide experiments validating their proposed approach.
strengths_and_weaknesses: Strengths
- The use of an ICNN for modeling the negative reward function is quite clever.
- The experimental evaluation seems quite robust. The results compared to competing methods seem very strong. Note that this is not exactly my field, so I am not completely aware if these are good benchmarks to evaluate against. 
- The ablations on SNR and different components of CoNSoLe are great to see, especially because the theoretical results only analyze the noiseless case. 

Weaknesses
- In the notations section (line 114) it is stated that $h_K = y$, which is not exactly correct. $h_K$ *regresses* or is in some way a *prediction* of $y$, but to say that the output of the network exactly is equal to the labels is not quite precise. 
- For global optima in neural networks, some background is lacking. For example, [1] was the first to demonstrate that two-layer ReLU neural networks can actually be expressed as convex optimization problems (over the weights), and thus can be solved to their global optimum.

[1] "Neural networks are convex regularizers", Pilanci & Ergen, 2020
questions: N/A
limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors propose a method for symbolic regression based on deep Q-learning, that learns to chose which symbols to combine in the LoCal model. To provide formal guarantees, the authors use input convex neural networks to model both the Q-function and the Reward function. Experiments suggest that the method is able to accurately recover true underlying equations from data.
strengths_and_weaknesses: Strength

- Elegant use of input convex neural networks for Deep Q-learning
- Theorem 1 shows that modeling Q as a convex function is a consequence of modeling R as a convex function
- Theorem 3 shows that the loss landscape of chosing optimal multiplicative weights in the model has local convex region under mild assumptions. Hence we can find it with gradient descent methods if the initialization is lucky.
- Strong experimental evaluation on synthetic problems as well as systems from physics and electrical engineering. Several benchmark methods are considered, the ableation study highlights the importance of each component of the contribution
- Figure 1 is very informative.

Weaknesses:

-The authors claim  that "Q-learning can hardly be applicable when the state and action spaces are large, e.g., SR problem." but then proceed to do so anyways?
- Code is not available to reviewers, so I cannot confidently attest to reproducibility

Minor Comments

- There are some redundancies between Introduction and Related Work.
- Table 1 violates the margins
- Authors use references [x] as subject in sentences. This should generally be avoided, use author names as subject instead.
- Personally I'd like to have Algorithm~1 in the main text. I know space is tight, but the code helps a lot for understanding the interplay of all the components you propose




questions: Initially I was puzzled as to why the authors were so keen on maintaining convexity in R and Q for the deep Q-learning procedure. Is it just such the optimal action is uniquely defined and there's an algorithm to find it? Or does it help with the large state and action space?

When R is convex, the optimal Q is convex. But how reasonable is it to model R as a convex function?

limitations: The authors have adequately addressed the limitations of their work.
review_title: null

Meta-review: metareview: Authors propose to learn coefficients and symbols connections in the problem of Symbolic Regression (SR) by combining Q learning and neural networks. They rely on the convexity properties of of ICNN to ensure that the Q function and the rewards R() are convex wrt the state S and the action A of the MDP defined. They use the convexity properties and the determinism of the MDP to derive several guarantees on their method - namely, that the exact symbols can be recovered for noiseless datasets because the problem is locally convex in a neighborhood of the true minimum.

There were a number of questions and concerns regarding the theoretical results raised the reviewers which were addressed during the discussion period. I'd like to thank the authors for the important work they put during the rebuttal. The quality of the paper has been improved a lot since the initial submission and the experimental results have improved.
confidence: Less certain
Decision: Accept