Black-Box Approximation and Optimization with Hierarchical Tucker Decomposition

Dear Reviewer, thank you very much for your comments, which allowed us to correct the shortcomings and improve the quality of our work. Below are our responses for your comments.

1. A brief description of the rationale behind the TT-Cross and TTOpt should be given...

We have presented our method in the text, with corresponding references to original papers for TT-Cross and TTOpt approaches. Given the limitations of the text size, it seems difficult to present descriptions of known methods TT-Cross and TTOpt. If you insist on the need for such a description, we can add it to Appendix.

2. ...is not quite clear what is the output of Algorithm 1 ...

Thank you! We modify the text.

3. A careful revision is needed ...

Thank you for the typos pointed out, we have corrected them.

4. Write Algorithm 1 in a more explicit fashion, clearly stating its inputs and outputs, using a more formal notation.

Thank you! We extend its description.

5. In Section 3, the authors state that by HT they "mean a tensor tree that is not necessarily balanced". Thus, the topology of the HT structure used in the numerical experiments should be specified. Is it always taken to be simply a balanced tree?

Yes, but maybe with unused indices (as in Figure 3, where unused leafs [green boxes] as well as their parents [purple circles] are never visited) since balance tree has exactly $2^n$ elements. It's roughly equivalent to a slightly trimmed tree. However, our algorithm can also support completely unbalanced trees, for example, we can consider a nearly one-dimensional Tucker-TT structure, but we have not yet found the practical advantages of these structures, this is future work.

6. ... how is this topology chosen in practice?

Just empirically for now.

7. ... can you give any approximation guarantees of your method ...

We have no theoretical guarantees. But the theorem from in Buczy´nska et al. (2015) states that HT is more expressive. Note that the original TT-Cross paper and the TTOpt paper also lacked the convergence or approximation guarantee.

8. ... is the novelty here all in the way where HTBB selects the next node that should be visited, the rest of it being similar to TT-Cross and TTOpt?

Our main contribution is the ability to obtain an approximation of a multidimensional tensor, such that it does not fit in the memory of a computing system, in the well-known Hierarchical Tucker format. This format was known before us, and various results exist for it, in particular theorems on the expressivity of the format. Thus, this work cannot be considered incremental with respect to the TT-cross algorithm work. In addition, we have combined both approximation and optimization of a black-box function in one algorithm. Our algorithm was inspired by the TT-cross algorithm, we use the same idea of getting the right indices using the MaxVol algorithm. But our difference is not only in the new index traversal procedure. In TT-decomposition each core is as 3-dimensional as in HT. But there each core has a free index that corresponds to the component argument. And when MaxVol is used, the corresponding matrix is unfolded by this index. In the case of HT, all cores dimensions (except leaf cores) are latent and thus symmetric. It is not obvious in this case how to perform unfolding, since the latent core dimensions do not correspond to the argument of the tensor (and black box). In order to work in such a situation, we proposed to associate indices with the connections of cores (nodes) rather than with the cores themselves, we introduced two types of indices - "up" and "down", and the possibility of going in any direction (by any connection of a given node with other node). All this is a novelty.

9. Some details and relevant discussion are lacking in the numerical experiments...

We used the most efficient (in terms of approximation quality) rank-adaptive version of the TT-cross algorithm (i.e. the method automatically adaptively increases the TT-rank what corresponds to the number of optimizable parameters until the budget is exhausted). As noted in the text, for all methods (HTBB and baselines) we set the same limitation on the number of requests to the black box.

Dear reviewer, thank you very much for your analysis of our work and the specific notes you formulated! Below we provide our responses to them. We will be happy to answer any additional questions you may have.

1. ... what problem is being solved.

As written in Sec. 2 "MOTIVATION AND OVERALL IDEA" (L086--100), our goal is to extend the TT-Cross and TTOpt algorithms to HT tensors. These algorithms perform black-box approximation of a given surrogate model and find the optimum of a black-box function, correspondingly. We write about the same in "our main contributions are the following:" (L068-L072). We also have separately added a corresponding explanation in the revised version of the manuscript.

2. ... the difference between your approach and other existing works.

The closest approaches to our one are the TT-Cross and TTOpt algorithms, which work with TT decomposition. We deal with the HT decomposition, and this is our main difference. We write about it in Sec. 2 MOTIVATION AND OVERALL IDEA (L085 - 102).

3. The good ideas in this work are getting lost ... relies too much on pointing to related work.

We have added a mathematical statement to the revised version of the manuscript. As for references to similar papers, we mostly cite them as motivation and justification for why we expect our algorithm to work well. But our algorithm differs significantly from those already published, and thus we describe its work in enough detail to make its essence clear even to a reader not familiar with previous papers. Please clarify what terms or mathematical expressions relating specifically to our algorithm that we have not disclosed that could potentially interfere with understanding how our algorithms work?

4. Related works cover many different method types (e.g., particle swarm optimization). How many of these solve the same problem and could be compared against in the experiments?

We note that our method combines approximation and optimization, so we compared it separately with an alternative approximation method (TT-cross) and various optimization methods (TTOpt, One+One SPSA, and PSO, i.e., Particle Swarm Optimization).

5. For the 14 benchmark instances, [Jamil-Yang, J. of Math. Modeling and Num. Opt. 2013] has 100+ tensors in their dataset. How did you choose this subset of 14 across multiple works?

Among those 100+ functions many have the same properties or even just the same functions, but in different benchmarks. Also, many functions are formulated only for a specific dimension (for example, 2). We've made a representative compilation of functions from benchmarks, you've mentioned above based on the following principles: functions should be different, and functions should be hard to optimize using gradient-based methods.

6. "gradient-free" methods are mentioned regularly throughout the paper. Can you give an example of an effective method that you compare against that is gradient-based?

As we've stated in our research task, the sole focus of our work is on the functions, for which gradient information either cannot be obtained or just is not useful. In both cases comparison with any gradient-based methods makes no sense. For example, in Appendix, we presented the results of additional experiments for four challenging problems of maximization of the cumulative reward for reinforcement learning agents by the proposed method HTBB and various baselines, and gradients are not available for these problems.

7. Are the sizes (i.e., the number of optimizable parameters) in HTBB and TT-cross equivalent in Table 1?

We used the most efficient (in terms of approximation quality) rank-adaptive version of the TT-cross algorithm (i.e. the method automatically adaptively increases the TT-rank what corresponds to the number of optimizable parameters until the budget is exhausted), so for different benchmarks the ratio in the number of parameters between the two methods turns out to be different.

8. In Figure 4, why are the SPSA and OPO methods better up until requests?

Both of the methods, you've mentioned, belong to a different family of black-box optimization techniques, so we have neither intuition, nor explanation on the observed behavior. However, even with the limited knowledge, one can notice, that both of the methods have a quite good initial guess and then improve only a little.

9. The [Goreinov et al., 2010] citation should include the journal.

Thank you for noticing this inaccuracy in the citation. We will correct this oversight.

Dear Reviewer, thank you very much for your high evaluation of our work and constructive comments! Below we provide our responses.

1. The introduction of the equation in Section 3 appears abrupt. It is recommended that the authors include a figure to provide further illustration and clarity.

Fig. 3 in the manuscript relates to this equation. We additionally add the following text in the beginning of Sec. 2: "(see Fig. 3 for a visual example of HT structure)" for the convenience of readers.

2. What would be the performance of Algorithm 2 if QR decomposition were replaced with singular value decomposition (SVD)?

Just slower. SVD could, theoretically, show more stability, but the results of QR decomposition are simply fed into MaxVol, which itself works with some accuracy, and go nowhere else. So we decided to use QR for acceleration. However, we assume that the black-box computation takes much longer than the internal procedures of our algorithm (and this is exactly what usually happens in practice when approximating or optimizing complex black boxes).

2. Given the existence of a canonical form for the hierarchical Tucker decomposition, could the authors provide a comparison between the cross-approximation method and an SVD-based method in the context of hierarchical Tucker?

Our goal is to work with tensors that do not fit completely in memory (here we follow the ideology of the TT-Cross algorithm, which can be replaced by a sequential SVD call if the original tensor fits in the memory of the computer system). Of course, if the tensor is small enough and we have the computer memory for SVD-based algorithms, they will be more accurate (and likely faster, for the very small tensors) than ours.

3. In the first experiment, in addition to the TT cross-approximation, the Tucker cross-approximation should be considered, as hierarchical Tucker is an extension of the Tucker decomposition.

Here we want to note that in our work we consider essentially multidimensional tensors (for example, of dimension 256 or 1024). The Hierarchical Tucker (HT) decomposition, as well as the TT decomposition, are free from the curse of dimensionality, while the ordinary Tucker decomposition contains a kernel with an exponential number of parameters and therefore its use in our case is extremely difficult or impossible.

4. The experimental results should include performance comparison with regard to different tensor orders, as this would provide insight into the scalability of the proposed method.

We would like to note that within the framework of the problem statement we are considering, it is assumed that the time it takes to calculate the black box can be significantly longer than to perform internal operations of the algorithm and therefore it is logical to measure the efficiency of the algorithm not in its operating time, but in the number of queries made to the black box. As noted in the text, for all methods (HTBB and baselines) we set the same limitation on the number of requests to the black box.

5. All experimental results should be normalized for comparability.

In the tables we present relative approximation errors and absolute optimization errors (since for many functions the true optimum is at zero).

Dear reviewer, Thank you very much for analyzing our work and formulating the specific questions you asked! Below are our responses.

1. The algorithm seems too heuristic to me and the contribution is not enough for an ICLR publication.

We agree with the reviewer that our algorithm is quite heuristic, and we leave strict guarantees of convergence, accuracy, etc. to future work, presenting in this paper only the essence of the algorithm and numerical results. However, the papers on TT-Cross and TTOpt (which was published on A* NIPS conference) are similar in spirit and do not contain theoretical discussions of aspects of the algorithm. In very general terms, we expect our algorithm to produce better results than the above, since TT-Cross and TTOpt methods work with TT-decomposition, while we operate with HT-decomposition. It has been proved to be more expressive for HT. We write about this on page 2, L085--087. This fact was proved in Buczy´nska et al. (2015). We have extended the corresponding text in the revised version of the paper. Could you please specify to what extent you think theoretical justifications should have been presented and what kind of theorems you would expect to be enough for an ICLR publication?

2. In the numerical experiments, all functions have well-behaved analytical expressions, which may not reflect real-world scenarios. It remains unclear whether the approach would perform well in applications where functions may lack favorable properties, such as continuity or convexity.

We demonstrate the effectiveness of the proposed approach for 14 multidimensional analytical functions, many of which have complex landscape with several local extremas. This set of functions is often used to test optimization algorithms and surrogate modeling. In Appendix, we also presented the results of additional experiments for four challenging problems of maximization of the cumulative reward for reinforcement learning agents by the proposed method HTBB and various baselines. Could you please clarify which BB you would recommend for further validation of our algorithm?

3. The presentation of the paper, particularly in terms of English language usage, could be improved.

Thank you, we have proofread the text of the manucript and tried to make improvements to the presentation.

4. Questions.

Thank you for the typos pointed out, we have corrected them.