We developed a new method PROTES for black-box optimization, which is based on the probabilistic sampling from a probability density function given in the low-parametric tensor train format. We tested it on complex multidimensional arrays and discretized multivariable functions taken, among others, from real-world applications, including unconstrained binary optimization and optimal control problems, for which the possible number of elements is up to $2^{100}$. In numerical experiments, both on analytic model functions and on complex problems, PROTES outperforms existing popular discrete optimization methods (Particle Swarm Optimization, Covariance Matrix Adaptation, Differential Evolution, and others).
Paper
Similar papers
Peer review
Summary
The authors present the algorithm PROTES for solving discrete optimization problems. The method uses probabilistic sampling to obtain a probability function of minimal (or maximal) values of a target function. This probability function takes the same shape as the target tensor. Alternatively, this could be described as a likelihood score for the optimal values of the discrete variables. To make the algorithm more efficient, the authors use the tensor train (TT)-representation for tensors. This is a low-rank approximation of a tensor, which makes the iterative computations faster. This TT-representation is used for the probability function. The authors test their method on 20 different problem instances and compare their method to seven other methods. The results show that PROTES works well, and is stable for the instances it was tested on.
Strengths
The paper has a clear structure and is well written.
Weaknesses
The method was not well motivated and the update rule was unclear to the reader. This makes is it very hard to assess whether there is sufficient contribution to the research area. The comment on the application of the method on constrained optimization is too short-sighted. In other words, such an important topic deserves more explanation. The current version does not clearly explain how general constrained optimization problems can be handled, particularly the feasibility concerns. The instance sizes of the QUBO problems are very small compared to what is now possible with the constrained version of these problems. Although the method was tested on 20 different problems, compared to seven benchmarks, only one instance per problem (size) was tested. For instance, for P-11 to P-13, it looks like only one instance was selected, which was not specified whether random problem parameters or something else was used as input. Therefore, the reader cannot tell if the proposed method works well in general for the tested problems or only on the tested instance.
Questions
- What is the reason for using gradient ascent for updating the the probability distribution? Cannot alternatively a cheaper updating rule be used? Think for instance of increasing the likelihood of the selected candidates by some value in each iteration (similar to weighing). - In line 62 of the paper, it is mentioned that the probability distribution is expected to present a Kronecker delta-function. It sounds more like an indicator function with a peak in the value of the minimum target function. Moreover, why is this function expected? - Please address why only one instance was tested per problem (size), and why this is enough evidence of the efficacy of the method for the type of problem. - In line 182, it is mentioned that related methods in the TT-format should be used for approximation. Is the approximation of the optimum meant here? It is a bit confusing since in the sentence before the (TT-)approximation of the original tensor is mentioned. - What are the specifications (CPU etc) of the ‘regular laptop’?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
2 fair
Contribution
2 fair
Limitations
Not applicabel.
Summary
This paper presents a study on black-box optimization. The authors propose a new method based on sampling from the probability density defined in the tensor train (TT) format (extension effort). The experiments have shown that PROTES outperforms existing efforts.
Strengths
(Overall) This paper is well organized. The technical soundness and practical performance are strong. 1. This paper has given a detailed motivation and an analysis of the computational complexity of the method. This makes the work appear comprehensive. 2. The research on gradient-free optimization plays a crucial role in various fields. Despite its significance, it often receives relatively low attention compared to gradient-based optimization methods. This effort tries to add distribution sampling for new tech, "TT-tensor."
Weaknesses
1. The method section "Optimization method PROTES" is hard to follow and what's the relationship between this section and others? 2. The experiment (P1-P20) seems too simple to fully demonstrate the method's effectiveness. 3. This paper also uses the gradient ascent for the TT-tensor, so there lacks more discussion about the model design and gradient-free optimization.
Questions
1. Does dimension d have an impact on the experiment? Why was it fixed at 50?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
3 good
Contribution
2 fair
Limitations
No negative societal impact.
Summary
The paper proposes PROTES, a new method for multi-dimensinoal discrete black-box optimization based on adaptive probablistic sampling in the tensor train representation.
Strengths
- The technical method is simple and intuitive, with a clear presentation. - Diverse benchmark problems and comprehensive comparisons to relevant SOTA baselines. - Good empirical performance under the tested experimental setup.
Weaknesses
- Besides presenting and describing the results, lack of intuition/discussion on why the proposed approaches outperform baselines (both classical and tensor-based). - It’s encouraged to have a wider spectrum of dimensionalities of the test problems besides 7 and 50 used. - It's not the most efficient method for any given number of requests (evaluation budgets), as seen in Fig 3. The method gains more advantage as requests become closer to 10^4.
Questions
N/A
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
The authors discussed the limitations of the paper which include the inability to handle large dimensions (>1000) and explicit constraint consideration.
Summary
This paper proposes a novel algorithm to estimate global extrema of discrete black-box target functions. The approach proposes learning a probability distribution, represented as a multidimensional tensor and efficiently stored using a TT-decomposition, that is trained to favor multi-indices that achieve high/low values in the target function. The approach, PROTES, draws inspiration from the REINFORCE algorithm, and can be trained using gradient-based optimization techniques. Extensive experiments are conducted to demonstrate the competitive performance and robustness of PROTES.
Strengths
- The paper is quite self-contained and well written, concepts are introduced gradually and are easy to understand - The connection to REINFORCE is informative and helpful - Experiments are compelling, detailed ablation analyses are included demonstrating the robustness of PROTE
Weaknesses
Clarity/Notation: - "Gradient-free" is defined very late in the paper but is used frequently throughout the earlier sections. This is confusing since the optimization of the probability tensor is done with gradient based optimization. I would suggest providing a clear description of this in the introduction. - It is stated in the footnote on page 1 that upper case letters are used to denote matrices, but they are used several times in the paper to refer to scalars i.e. $N_i$, $R_i$, etc. - In figure 2, the tensor network diagram needs further explanation. It is not clear what is being conveyed from the figure and the current caption. Comparison to Existing Approaches: - While the experiments empirically demonstrate the efficacy of the proposed approach, the computation complexities of prior works is not stated anywhere in the paper. Is it the case that the performance benefits are attained by adding significant computational costs? This should be discussed in the comparison. - Since the proposed approach is probabilistic, it would be useful to include error bars in the experimental section.
Questions
- What are the computational complexities of the baselines? - Does this method work especially well when there is a particular structure in the target function? Clearly this method, and any of the baselines would fail if $\mathcal{Y}$ is random. - How is the probability tensor parametrized? Are the values of the tensor learnt directly? Could there be a benefit to alternative parametrizations (i.e. having a multilayer structure)?
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.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Discussed in detail
Summary
The paper targets the challenging gradient-free discrete multidimensional optimization. It is formalized as finding a vector of d indices whose associated entry in a d-dimensional tensor is minimized, where the tensor contains all the possible values for the black-box objective function. There are an exponential number of entries in the tensor for brute-force search. Instead of enumerating all of them, the paper proposes to optimize a low-rank tensor whose each entry represents the probability of selecting the corresponding entry as the minimum in the objective value tensor. The algorithm starts from a random probability tensor and updates it using a similar trick as REINFORCE algorithm. In experiments on benchmark tasks, it performs comparably or better than the baselines evaluated.
Strengths
1. It targets an important and challenging problem interesting to many practical problems. 2. The idea of using a low-rank tensor can reduce the cost of brute-force search. 3. Evaluation of different tasks and robustness to the hyperparameters.
Weaknesses
1. It is a combinatorial search problem from an exponential number of candidates so some structural information of the problem has to be used. However, it is not clear why and when the low-rank probability tensor assumption holds, and if so, for which classes of problems. 2. The technical contribution is ad-hoc to some extent by combining tensor-train decomposition with REINFORCE trick. 3. I like the explanation of the intuition starting at line 122 but the approximation in Eq. (5) does not hold rigorously without using the true Monte-Carlo samples as in REINFORCE (the proposed alg instead uses the best k samples) 4. The complexity analysis assumes a fixed number of queries to the black-box function and does not study the number of iterations required to reach a sufficiently good local minimum. 5. The proposed method does not show advantages to BS-1 and BS-2 in Table 1 on analytic functions. Figure 3 does not show a clear advantage in the sample efficiency.
Questions
1. Can you elaborate on when and why the combinatorial optimization problem's structure is consistent with the low-rank probability assumption? Some concrete examples can be helpful. 2. How to balance the exploration and exploitation in the black-box optimization problem? It seems like the proposed algorithm mainly focuses on exploitation (always selecting the top-k candidates).
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
3 good
Contribution
2 fair
Limitations
The author did not discuss the potential limitations. An efficient solver for combinatorial black-box optimization can be used for attacks such as threats to cybersecurity. It would be nice to have some discussions on that.
Thank the authors for the clarifications. After reviewing the entire paper again, I tend to keep my current score.
Thank you very much for your review and additional thorough analysis of our work! While "rebuttal", we did the best of ourself to fix the points you mentioned in the Weaknesses section. If you have any additional questions for us that may affect your assessment of our work, we will be happy to answer them within the remaining time for discussion. If not, we thank you once again for your positive evaluation of our proposal.
Thanks for your effort during the entire rebuttal period. This work has been very solid, even without high novelty. After carefully reviewing the comments from the other reviewers, I would like to raise your score from a 5 to a 6.
Thank you very much for raising the rating and positive evaluation of our proposal!
Thanks for the detailed response to my concerns! The rebuttal addressed some of my concerns but the major ones still remain after reading the rebuttal and the general response PDF. Here is some detailed feedback: - Re 1: This is still my major concern. Most combinatorial optimization problems have rich structures and solving them relies on such structures to shrink the search space. In addition, different problems have different structures. However, I do not see any theoretical analysis (even on some concrete examples of combinatorial optimization problems) in this paper showing a low-rank matrix of probabilities assigned to the candidate solutions is versatile and accurate enough to encode different structures. Low-rank approximation might be overly smooth for the approximation of many non-smooth combinatorial optimization problems. - Re 2: Eq. 2 is a log-likelihood and its gradient is computed using the same log-derivative trick of REINFORCE. Their algorithmic details are not exactly the same but I am not sure this computation of gradient can be a major novelty. - Re 3 & 7: It is good to know this is not a practical issue if the choices of E and T are correct. Empirical performance largely depends on the combinatorial problems included in the evaluation. But I am still not sure if it holds rigorously in theory and in general. The gradient computed based on the top-k samples can have a bias due to the lack of exploration on other candidates. This is also related to the exploration-exploitation trade-off mentioned in 7. Top-k selection is a greedy strategy so the exploration can be very weak unless you use a large k. But the cost of using such a large k is usually not affordable. - Re 4: This is a theoretical concern regarding the complexity analysis because assuming a fixed number of iterations cannot guarantee many favorable properties of the solution, e.g., local minimum, equilibrium, etc. This makes the conclusion of complexity very weak. - Re 5 & 6: Thanks for the explanation and experimental results in the PDF! They addressed some of my initial concerns. It seems like PROTES only outperforms baselines and shows better convergence speed in the very later stage. What happens in the earlier stages and how to explain this observation? - Re 8: This concern aims to point out that there does not exist a limitation section in the submission discussing the potential security risk of publishing such techniques proposed in the paper. It would be helpful to add such discussions to the paper. While I greatly appreciate the authors for their responses, my main concerns still remain on the main contribution/novelty and the theoretical correctness. In essence, this is a **low-rank approximation of the multi-linear extension in combinatorial optimization. But it is not convincing to me (both intuitively and theoretically) that this is guaranteed to be a good approximation in general.** Experiments did show the effectiveness of the method on some exemplar problems. But as I mentioned before, combinatorial optimization problems can be very different from each other. Hence, I will maintain my original score at this time.
Thank you very much for your additional detailed comments. Below we present our responses to each of them [we split our response into two messages due to the text length limits]. 1. [Re 1] About structures in the optimization problems. - We fully agree that specialized solvers adapted for specific classes or types of problems (for example, there are a lot of specialized methods for QUBO problems) can be potentially more efficient than our optimizer on the corresponding class of problems. However, we have proposed a black box optimizer, and we compare its effectiveness with baselines operating in the same paradigm (PSO, SPSA, etc.). We note that baselines are also heuristic methods, but they have proven to be effective for many applied problems. Therefore, our goal was to consider several different classes of problems and show that our optimizer outperforms baselines on average over all the classes considered. As follows from the numerical experiments, for various analytic functions, QUBO problems, ODE-based optimal control and optimization of reinforcement learning agents, our method is stable and superior to alternative approaches. We will add relevant comments to the Conclusion section. - We want to emphasize that we use the low-rank tensor train (TT) decomposition (with a fixed rank). It has a rich complex internal structure, and allows building accurate approximations for complex non-smooth functions, which is confirmed by many publications in various applied fields, including machine learning applications (we have provided some references in the text of the paper). - At the same time, it is important to take into account that we do not approximate the objective function or loss function in the TT-format. We only use the approximation of the distribution, which can be sampled near the optimum of the objective function. Our hypothesis is that sufficient number of points closest to the optimum value of the target function lie on the low-rank manifold. Moreover, since the tensor changes with iterations, we do not approximate all the points closest to the current local optimum, but go along some "low-rank path" to the global optimum. 2. [Re 2] About the novelty and gradient computation. - We want to note that we consider, in contrast to formula 5, an unweighted probability distribution, that is, we take top-k candidates and do not use the values of the target function. In addition to the empirical fact that this provides greater stability of the method, it can also be especially relevant in the presence of constraints on the objective function (values that do not satisfy the constraint can be easily discarded) or in the case of functions for which it is easy to select top-k candidates from a batch, but it is difficult to provide specific numerical values (for example, when choosing the best images from a set, etc.). 3. [Re 3 & 7] About the lack of exploration. - We agree that selecting top-k candidates from a batch is consistent with a greedy strategy. However, when sampling from a probability distribution in the TT-format, we form a batch that will contain samples not only close to the current found local optimum, but also samples far from it ("random"), which relates to exploration. As follows from the numerical experiments, including the Table 1 in the Appendix, our method effectively finds a good approximation (and even exactly) of the global optimum. 4. [Re 4] About the fixed number of iterations. - We want to note that in practical optimization applications, the budget is usually limited. Also, in many works, the evaluation of the effectiveness of methods is carried out with a fixed budget. In the main numerical experiments, we limited the budget for all considered optimizers to 10 K requests. Since we considered many different model tasks, it was difficult to use higher budget values for all tasks. However, as you noted ("About the convergence speed"), as the budget grows, the advantages of our method become even more significant. - We also note that Table 1 in the Appendix, shows the results of multiple (10) runs of all optimizers for a specific problem with a known exact optimum value. As follows from the reported results, only our method and BS7 successfully find the exact optimum with 10 restarts, while the average result of our method is significantly better.
5. [Re 5 & 6] About the convergence speed. - According to the graphs in the file, our method becomes the most accurate starting from 1-2 thousand requests to the black box. We want to note that further there is a significant increase in the accuracy of the result (by the 10 K requests). In other words, for extremely low computational budgets (providing extremely low accuracy of the solution), our method (for the chosen fixed hyperparameters) does not exceed the BS-7, however, with an increase in the number of iterations, our method turns out to be much more accurate. - We cannot conduct an additional numerical experiment within the framework of this discussion, however, we believe that by reducing the batch size for our method, its advantage will manifest itself at lower budget values (however, the final result on a large budget will be less accurate). - It is also possible to give an intuitive explanation for this observation. The considered tensor-based methods (PROTES, TTOpt, Optima-TT) build some kind of internal model (TT-representation), and at the initial iterations until the model of sufficient quality is built, the sampling turns out to be of insufficient quality. Please pay attention to the behavior of the TTOpt method on these graphs - with small budgets, it has a significantly low accuracy, but then it starts to increase rapidly. 6. [Re 8] About the potential security risk. - Thank you! We have included comments on this point in our original response. This is an important point, and we will add, as you recommend, appropriate explanations to the text of the paper.
Response to rebuttal
I thank the authors for their explanations to my questions. Due to the extra experiments and the well clarification on why gradient ascent is useful for this approach, I have raised my score.
Thank you very much for your positive evaluation of our work! Your comments allowed us to improve the presentation of the proposal, and we thank you for that as well.
Thank you very much for the positive assessment of our work and the increase in the rating! We are very pleased that we were able to improve the quality of the presentation of the work based on your comments.
Thank you for your response and additional experiments. Overall my concerns are mostly addressed, though it would be more informative to see full convergence curves rather than tables showing only the final performance, e.g. for Table 1 and 2 in the rebuttal pdf. The rebuttal didn't fully address this concern from my earlier review: > It's not the most efficient method for any given number of requests (evaluation budgets), as seen in Fig 3. The method gains more advantage as requests become closer to 10^4. But given the speed efficiency and a good final performance at 10^4, along with the interesting idea, I remain positive and would like to keep my current score.
Thank you for the positive assessment of our work and constructive comments, which allowed us to improve the quality of its presentation! We understand your remark on convergence, and we would like to make a small comment. According to the graphs for 1000-dimensional QUBO problems in the attached PDF file, our method becomes the most accurate starting from 2 thousand requests to the black box, and further there is a significant increase in the accuracy of the result (by the 10 K requests). In other words, for low computational budgets (providing low accuracy of the solution), our method (for the chosen fixed hyperparameters) does not exceed the BS-7, but, with an increase in the number of iterations, our method turns out to be much more accurate. However, you are absolutely right that the issues of convergence of our method (and the optimal choice of its hyperparameters) for significantly small computational budgets should be investigated as part of the further development of our approach. In particular, a heuristic for choosing the optimal batch size and top-k candidates depending on the available budget can be developed. Please note that in the current research, we used a single set of optimizer hyperparameters for all considered numerical problems.
Decision
Accept (poster)