Venue: NeurIPS 2022 Conference

Reviews:

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 present a novel approach to multivariate optimisation of general objective functions making use of tensor-train decompositions over discrete state-spaces.   The TT Decomposition approximation is based on the cross-approximation method / TT-Cross of Oseledets, etc.   The main interest to use TT-cross is not for building a approximation but based on the observation that maximal elements of the tensor are highly likely to be in the maximum volume submatrix which is found using MAXVOL in TT-cross and the maximal element of
the sub-matrix increases monotonically over the iterations.    This result is hinted at, but unless I misunderstand, it is not proved or confirmed.  This is employed empirically to define a new optimisation algorithm.

The algorithm is deployed in the context of Reinforcement learning, as an alternative to evolutionary approaches, as well as some general optimisation baseline examples.  It is demonstrated that the method is competitive, and in many cases outperforms other approaches.
strengths_and_weaknesses: Strengths:
* (Originality) This work presents an interesting approach to optimisation of (possibly non-differentiable) high-dimensional functions, exploiting tensor train decompositions, which is novel.
* (Significance) This is important as the traditional approaches to high-dimensional gradient free optimisation (e.g. BO) do not necessarily scale well with dimension, so that this offers a plausible alternative.
* (Quality) The paper is generally well written.

Weaknesses:
* (Clarity): I do not understand why the authors felt the need to bring reinforcement learning into this work.  The TTOpt algorithm is a general purpose optimisation algorithm, it is unclear why the authors felt that RL would be a unique use-case for this method, particularly given that the examples studied do not appear to involve non-differentiable loss-functions, and moreover, could be solved using policy gradient approaches.    This feels quite odd to me.
* (Significance) The key assumption in the proposed iterative optimisation method is that the maximum volume sub-matrix should contain the absolute maximum element, thus justifying the iteration.   However, unless I misunderstand, this isn't justified by any argument provided in this work.
questions: * Why are the authors specifically considering RL as a test case for this method?  This seems to be shoe-horned in.  I don't see any necessary need for such non-differentiable optimisation methods, whereas I can think of many other situations involving high-dimensional non-differentiable objective functions.  I appreciate the motivation based on Saliman's work on Evolutionary algorithms in RL, but this seems tenuous.   Can the authors shed some light about why this is the *right* method for RL and when?  It seems that for all of the presented problems, policy gradient would've worked just fine.

* The key assumption in the proposed iterative optimisation method is that the maximum volume sub-matrix should contain the absolute maximum element, thus justifying the iteration.   However, unless I misunderstand, this isn't justified by any argument provided in this work, including the "intuition behind ttopt" presented in page 3.   I really think this needs to be studied more, because this is a crucial feature that needs to be justified.   I appreciate that this can be quite a challenge, but some intuition about why this property should be true is important.
limitations: I think the authors need to be a bit clearer about what can and cannot be guaranteed with this methodology.  It is ok if the method is heuristic but this needs to be made very explicit.
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: This paper implements a novel method to find maximum elements of a tensor-shaped object function by combining quantized tensor train representation and generalized maximum matrix volume principle. The author applied this method to minimization of multidimensional functions and reinforcement learning tasks.

strengths_and_weaknesses: Strengths:
The originality is good. The algorithm combining Tensor-train and maxvol algorithm is novel and clear. The writing quality is good. The complexity is also analysed. It should be a significant work if it can work well on a wide range of tensor-shaped object function.

Weekness:
On theoretical aspect, there are no guarantee on the stability nor convergence of the algorithm. 

questions: 1. The quantized Tensor train seems inconsistent with the subsection 2.4. The searching submatrix is R*R, but when the tensor is quantized to a 2-power tensor, usually R should larger than 2, thus there should be some initial step to start the algorithm.

2. As stated in line 137 and 129, each maxvol algorithm are worked in a reshaped submatrix with coloum indices randomly choosed. However, the author declare that the the algorithm will  converge to optimal row and coloum indice, which seems strange.
limitations: Comparison against bayesian optimization which is also a brunch of methods for black box optimization is missing in the paper.
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 paper presents a gradient-free optimization method, based on the tensor train approximation of the functional and the maximum volume principle, adapted to navigate the optimized parameter space instead of reconstructing the volume. Experiments on multidimensional analytical functions and reinforcement learning settings demonstrate superior convergence rates and efficiency in terms of calls to the black-box function.
strengths_and_weaknesses: Judging by the provided analysis and results, TTopt deserves membership in most gradient-free optimization toolboxes.
Extending maxvol principles for optimization and mandatory quantization of the continuous case are interesting, novel, and significant (conditioned on the presented results).
The study of TTopt on analytical functions is rich and deep, going as far as comparing with Bayesian optimization methods.

However, given the impressive results from Fig.3 in RL environments, too little space is allocated to explaining the setup and discussion of what makes two orders of magnitude improvement in reward possible. 
Additional explanations in the supplementary are helpful but do not leave the impression of self-contained work. Domain expertise in RL and evolutionary strategies is required to understand the paper. The paper would benefit from a brief recap of ingredients and an explanation of how TTopt plugs into the RL pipeline. The MDP formalism (B.3) does not elaborate on whether the setup is applicable in off-policy /on-policy settings, whether it makes sense to optimize the number of evaluations, and whether all requested evaluations can always be carried out. 
Discussion of what entails exceeding the target reward is missing.

The paper is well-written and mainly easy to follow, except for frequent redirections to the supplement and related work for specific and essential parts of the narrative. Perhaps pivoting some text from pages 3 and 4 into the supplement won't hurt and would allow for streamlining the "story" since understanding the concepts of the tensor train decomposition does not really help to understand what is under the hood of TTopt without going into the supplement. In a sense, the matrix case (very well-written) is not representative of the multi-dimensional case due to many special handling bits.
questions: 1. L47 "Our algorithm can directly train quantized neural networks" - can the authors explain this? I understand the concept of QTT, but this point is only seen in the introduction and slightly touched around the RL part. Also, L235 "These experiments model the case of quantized neural networks which use q-bits quantization." - please elaborate on how NN parameter quantization relates to TT mode quantization.
2. In relation to Table 3, please discuss why some environments benefit from finer quantization while others don't, especially given the low variance of curves?
3. What are the convergence guarantees of TTopt?
4. The paper mentions "up to machine precision" (L40), and by the look of fp exponent of results in Table 1 and on, single-precision was used. Do the results improve further with double precision?
5. In Algorithm A1, rank selection only accounts for the left-hand side constraint on the ranks but does not enforce the right-hand side constraint. Shouldn't it also be the $\min(R_{i-1} N_i, R_i N_i, r_{max})$? This obviously cannot be done in a single loop due to double-side recursion; however, two loops can do. Wouldn't it be better than the reduction procedure from LL58-61 of the supplementary?
6. In Algorithm A1, "Set $G_i = \mathrm{random}(R_i N_i , R_{i+1})$, random how? Does the distribution matter?
7. Why is the case of linear policies important to consider TTopt with?

Writing tips:
- Order of environments in the left and right parts of Table 3 is different for no good reason
- Consider enabling line numbering built into algorithmicx for ease of referring to line numbers
- Annotating algorithms with shapes of operands would help in understanding
- Consider prioritizing a self-contained intro into the experimental domains and smooth explanation of TTopt plugging into the big picture, over explanations of TT and maxvol, provided that the main paper cannot fit the core algorithms anyway due to limited space.
limitations: Answers to several questions asked above, in combination with the rather deep analysis of rank and number of evaluation dependencies,  cover the most interesting limitation scenarios.
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 paper proposes an optimization method for multivariate functions of discrete arguments by considering their low-rank tensor decomposition in terms of Tensor Train structure. The method is compared to gradient-free methods, and is evaluated on Reinforcement Learning tasks and on functions with continuous arguments.
strengths_and_weaknesses: The main text is clear and well written. This work combines various solutions to solve this optimization problem, that is, extending the maxvol function to higher order tensors, replacing high dimensions by decomposing them to lower ones, and applying an updated mapping function to deal with algorithmic constraints. Additional experiments  testing different hyper-parameters appear in the appendix. The paper lacks, however, experiments that demonstrate the contribution of each individual part of the method empirically, such as the mapping function and the mode compression.

If the landscape of RL consisted of only of gradient-free methods, then the presented low execution time of the method, together with its ability to solve the problems successfully, makes this work significant. The fact there is no comparison to gradient-based methods is a major weakness and complicates the assessment of the possible impact of this work.

Strengths:
* Extends a matrix-based method to higher order tensors.
* Low execution time in comparison to other gradient-free approaches.
* Various experiments regarding the hyperparameters of the method appear in the appendix.

Weaknesses:
* No comparison with gradient-based methods.
* The comparison to RL is lacking. There is no comparison to any gradient-based method.
* There are no ablations to the benefits of using either the mapping functions (Eq. 7) or mode compression.
questions: * Questions 
	- Maximum Value in matrix is bounded by $\hat{J}_{max} \geq \frac{J}{R^2}$, for tensors with $d$ indices, would this bound grow to the power of $d$, doesn't this bound increase with the compression trick? 
	- What happens when you have a tensor train of $d=2$, where there are two minimal values of $-1$ in each, and a maximal value of $0.5$ in each? the total maximal value is $1$, isn't it? (The mapping function in equation 7 is applied at the end)
	- Why are the values in Table 2 in the appendix are of order of magnitude different than presented in Table 1 of the main text? of instance, the absolute deviation from the minimum of the Ackley function is $1.2$ (the absolute minimum is at $0$), but the relative deviation is $3.9e-6$.
    - It seems all the test functions have the symmetry of $x_i \rightarrow -x_i$. How would the method work for non-symmetric test functions?
   

* Suggestions
	- Perhaps add the definition for "Maximum modulus element" to the main text.
	- Perhaps add an evaluation of the method with the compression to modes and without (line 178).
	- It would be interesting to see how the approach handles non-differentiable functions as it is gradient-free.
	
	
* Minor corrections:
  - line 181 "Let assume" -> Assume that
  - Appendix Table 2 Grienwank -> Griewank
limitations: * I believe that when the method is applied to continuous functions, it is sensitive to the chosen discretization grid. Moreover, the complexity of the method increases for finer grids, as the $N_k$ increases.
review_title: null

Meta-review: metareview: The basic ideas and contribution of this paper have been positively evaluated by the reviewers.
There were a few questions, but many of them have been resolved by the authors' careful replies.
There is an opinion that the comparison with reinforcement learning is inadequate, but since it is an application, this is not a major problem.

confidence: Certain
Decision: Accept