Weaknesses: There exist several limitations in experiments which are summarized as follows: 1-Authors need to show useful scenarios where binary representation is the best way to model the tensor. For instance, it seems count representation makes more sense rather than the binary representation. By binary representation, the quantity of crimes is ignored. For figures 6c, 6I, it is better to specify the number of patterns. Why not showing the scalability of GETF and other baselines as we increase 1- number of patterns 2- the size of a tensor dimension, and 3- number of non-zero elements in the tenor.

This paper presents a greedy sequential algorithm for decomposing a Boolean Nth-order tensor into a Boolean sum of rank 1 components, using Left-Triangular-like and geometric considerations. The paper includes detailed theory, algorithm development and some experiments. This makes the exposition rather dense but the authors have clearly invested a lot time and effort in the work. The task is interesting and the rank-1 pattern revealing algorithm looks nice and intriguing. The work received divergent scores with the main points of disagreement being the difficulty of following the exposition, the practical need for special methods dedicated to Boolean tensors, and the lack of comparative experiments with other algorithms and with (NP hard) exact minimal decompositions.

This paper studies a variational theoretical framework for stochastic optimization. In particular, the authors showed that finding the minimizer of stochastic optimization is equivalent to finding the solution of a variational problem over a latent function space and also equivalent to finding the solution of a forward backward SDE. They also showed how to recover some popular stochastic optimization algorithms through discretizing the optimality equations defined by the SDE. However, this part is not so clear in clarity and still requires more discussion on the theoretical behavior of these discretized algorithms. Overall, this paper is well written and has strong results.

This paper presents a latent variational framework for designing stochastic optimization algorithms using ideas from stochastic control. The main contribution of the paper is an action functional, such that the corresponding Euler-Lagrange (EL) equations give rise to a system of Forward-Backward stochastic differential equations (FB-SDEs). These equations are generalizations of the ODEs for deterministic optimization obtained by Wibisono et al., 2016. The paper also presents an analysis of the rate of convergence. The reviewers are uniformly positive about this work, and the authors' response has addressed most of their concerns.

The dependence of SNR is extreme. I wonder whether it only occurs in the proof or a fundamental limitation of the approach. The authors did not provide a empirical comparison to any competing method even to [27] on which the presented algorithm improves. It would be interesting to see how the algorithm competes with the state-of-the-art in its empirical performance particularly in the presence of noise. Isn't the proof providing any dependence on L? 3. Some key definitions are missing.

Overall the solid theoretical results in this paper were enough to push it over the bar, despite a few complaints of lack of experiments. The reviewers were in consensus to accept the paper.

Strengths: To the best of my knowledge, the BSGD algorithm is the first stochastic-gradient based algorithm that directly solves CSO problem itself. The two most relevant work that focus on CSO are [12] and [24]; [12] solves a saddle-point problem reformulation of CSO, while [24] resorts to providing sample complexities for SAA approach to solve general CSO problem. With respect to the SAA approach presented in [24], BSGD method improves in sample complexities (they remove the dependence on d) when F is general convex, matching the lower bounds they provide. Although BSGD is not optimal when F is strongly convex and smooth, it matches the complexities of SAA approach[24]. They also argue about the settings in which BSGD may not be optimal, providing a transparent evaluation of their algorithm.

During the rebuttal phase the reviewers did not come to a consensus. Two reviewers--especially R4, believe that the paper should not get accepted since the authors base their analysis on well known ideas. The other two think that the results are novel enough and are of the interest of the NeurIPS community. I tend to agree with the latter, so I will therefor accept.

Additional Feedback: I'd like to see main paper Figure 1 / supplementary figure 4.1 expanded. The two questions I have that I don't think the figure currently answers are (1) how does the variance in final \sigma {2}_{f} across trials compare to a full batch GP, and (2) if full batch GPs have smaller variance, do much larger batch sizes (e.g., say m 1000) decrease this variance further? In figure 4.1, it does not seem the variance decreases much from m 16 to m 64 -- it'd be nice to know whether the batch size is the source of the variance. If it is, then running with very large batch sizes even up to m 10000 may not be too challenging. To the point of running large batch sizes, while the ability to use SGD will clearly outperform full batch training at some size N (at a guess, probably somewhere in the the N 100k-500k range), I don't think the results in Table 1 are necessarily representative of the settings you might actually want to run sgGP or EGP with.

All the reviewers agree that the paper presents a worthwhile theoretical contribution, which may facilitate/motivate further work to tackle more challenging problems. The main limitation of the work is its practical impact as the proposed analysis does not apply to the lengthscales. Although R3 stands by their comments, they expressed their willingness to accept and recognized, during discussions, this work as an excellent attempt at the problem. Overall, I believe the NeurIPS community will benefit from this work and recommend the authors to take the reviewers' suggestions and comments into consideration.