REVIEW 4 major objections 5 minor 37 references
High-dimensional Optimization with Low Rank Tensor Sampling and Local Search
T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read A tensor-train sampler can feed a local optimizer better starting points, and the paper shows this cuts error by orders of magnitude.
desk verdict A plausible hybrid optimizer whose central empirical claim is not isolated: the baseline is a single random-start local search while TESALOCS runs many restarts inside the same budget, so the tensor sampler's contribution is unproven. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the TT-surrogate: a $d$-dimensional tensor stored as $d$ TT-cores, each of size at most $R \times N \times R$ (here $R=5$, $N=2^{20}$), whose normalized entries define a discrete probability distribution over grid points. Sampling from it costs linear time in $d$ via the procedure of Dolgov et al., and the SGD update on the log-likelihood of elite points moves probability mass toward basins found by local search. The low parameter count of the TT representation is what makes this density expressive enough for 100 dimensions while memory and sampling cost stay linear in $d$.
What would settle it
Run TESALOCS against a same-budget random multi-start baseline, for example the same local optimizer launched from many uniformly random points totaling $10^4$ evaluations, on the same 20 functions in 100 dimensions; if the random multi-start matches or beats TESALOCS' errors, the central empirical claim is refuted.
Extended reading notes
Core claim
TESALOCS alternates between a discrete surrogate and a continuous local method. A $d$-dimensional tensor in TT-format with rank $r$ is initialized randomly and acts as a discrete probability distribution over an $N$-point grid; each iteration samples $k=100$ multi-indices from it, projects them onto continuous points, runs a local optimizer from each, keeps the best $k_{\mathrm{top}}=10$ refined points, projects them back, and performs an SGD step on the negative log-likelihood of those elite points. The claim is that this loop concentrates the sampler around basins that the local optimizer can actually polish, so the same number of function evaluations spent on these informed restarts yields lower error than spending them on one run from a random point. Across 20 100-dimensional benchmark functions with budget $10^4$ and fixed hyperparameters ($r=5$, $N=2^{20}$, $k=100$, $k_{\mathrm{top}}=10$), the paper reports best results in 15 to 20 of 20 cases against each gradient-based method and similar gains over gradient-free baselines, often by orders of magnitude and with lower variance.
Load-bearing premise
The experimental comparison uses a single local search from one random starting point as the baseline, while TESALOCS effectively spends the same budget on many restarts; if a same-budget random multi-start baseline performs just as well, the tensor sampler adds no measurable value.
Editorial extensions
If this is right
- Any local optimizer can be wrapped by TESALOCS; the paper demonstrates this with six gradient-based solvers and three gradient-free heuristics, so future local solvers could inherit the same global exploration layer.
- Under a fixed budget of $10^4$ evaluations, informed restarts produced by the TT sampler reduce average error and variance relative to single random-start runs on nearly all 20 test problems.
- Because the TT-format's storage and sampling scale linearly in dimension, the method is intended to remain practical as $d$ grows, as long as the target landscape is smooth enough for local refinement.
- For non-differentiable or noisy objectives, the local phase can be a derivative-free heuristic, which extends the method past the requirement of gradient availability.
Reading between the lines
- Editorial inference: the reported gains may come substantially from restarting many local searches rather than from information carried by the tensor surrogate; a same-budget random multi-start baseline would separate these two effects.
- Editorial inference: the log-likelihood update is a form of density focusing, so TESALOCS can be viewed as an implicit niching or racing mechanism; comparing it to a covariance-matrix-adaptation strategy with restarts would test whether the TT representation adds value beyond standard distribution adaptation.
- Editorial inference: fixing $N=2^{20}$ and $r=5$ means the grid is extremely fine, so a testable prediction is that performance should degrade gracefully as $N$ or $r$ shrink, and the sampler's marginal value should vanish on unimodal landscapes where one local run suffices.
- Editorial inference: because the scheme is decoupled from the decomposition format and the local solver, a natural extension is constrained or noisy optimization by restricting the sampling support or using robust local refiners.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes TESALOCS, a hybrid optimizer that alternates between sampling candidate starting points from a low-rank tensor-train surrogate model over a discrete grid and refining those candidates with an arbitrary local optimizer (e.g., BFGS, PSO). The surrogate is updated by an SGD step on the log-likelihood of elite refined points. The authors claim that, under a budget of 10^4 function evaluations on 20 100-dimensional benchmark functions, TESALOCS improves on random initialization by orders of magnitude when wrapped around six gradient-based and three gradient-free optimizers. The main contribution is the algorithmic framework rather than a new tensor decomposition, with a stated emphasis on the plug-and-play nature of the local-search component.
Significance. If the empirical claims were established, TESALOCS would be a practically relevant contribution: it offers a dimension-scalable, budget-controlled way to turn any local optimizer into a global method, leveraging the low-parameter TT representation for exploration. The paper explicitly presents fixed hyperparameters across all benchmarks, which is a step toward a fair comparison, and the algorithmic description in Section 2 is clear enough to reimplement. The conceptual bridge between discrete tensor sampling and continuous local refinement is timely given the recent success of TT-based black-box optimizers like PROTES. However, the significance is currently conditional on a comparison that is not yet properly controlled, and on data that show signs of reporting errors.
major comments (4)
- [Section 3, Algorithm 2.1, Tables 1-3] The central comparison lacks a same-budget random multi-start baseline. In Algorithm 2.1, each iteration samples k=100 candidates and runs an independent local search from each, charging all evaluations to the budget M=10^4; this makes TESALOCS a multi-start method with many restarts per run. The 'Random' baseline in Section 3, described as 'random selection of the starting point,' appears to be a single local search per benchmark. The reported gains, including the abstract's 'orders of magnitude,' may therefore reflect the number of restarts rather than the tensor sampler's ability to identify promising basins. A control in which the same local optimizer is run from the same number of randomly chosen starting points under the same total evaluation budget is required to isolate the contribution of the TT-based sampling; the paper cites restarted local search but never runs it as a comparison. Without this control, the central empirical claim is not established.
- [Tables 1-3] Several variance entries appear to be duplicated across unrelated benchmark functions in a way that cannot reflect independent 10-run experiments. For example, in Table 1 under BFGS the 'Random' column reports σ=7.2e-01 for Sphere, Squares, and also for Schaffer and Yang (7.3e-01, 7.2e-01), and the same pattern recurs under CG and L-BFGS-B; in Table 2, the TNC 'Random' column shows σ=1.3e-12 for both Chung and Alpine, and σ=4.9e-01 for both Exp and Griewank. Since these functions have completely different landscapes and scales, identical variances across all functions and methods are implausible. This indicates a reporting or data-processing error that undermines confidence in the numerical results and in the claim that TESALOCS reduces variance.
- [Section 3, reproducibility] No code, data, or detailed experimental configuration is released, and the paper does not state how the 'Random' baseline is run for the gradient-free methods (e.g., whether PSO is run once with a random initial population or with multiple restarts). Given the absence of a baseline and the irregularities in the variance tables, the reported numbers cannot be independently verified. For a paper whose main evidence is empirical, providing the implementation or at least a precise pseudocode for the baseline and the local-search budget allocation is necessary.
- [Abstract and Tables 1-3, 'orders of magnitude' claim] The abstract claims improvement 'by orders of magnitude with the same computing budget,' but several benchmark rows show only modest gains. For instance, in Table 1, Ackley improves from 2.0e+01 to 1.8e+01 (roughly 10%), Pathological from 3.8e+01 to 3.0e+01, and Wavy from 5.9e-01 to 3.6e-01. The order-of-magnitude framing is not representative of all 20 functions, and the summary statistics ('# of best results') mix cases where TESALOCS is slightly better with cases where it is dramatically better. The claim should be made precise, for example by reporting geometric mean ratios or a distribution of improvements, rather than relying on headline counts.
minor comments (5)
- [Section 1] In the introduction, 'particle swarm optimization (PSA)' is a typo; the correct abbreviation is PSO, as used elsewhere in the paper.
- [Section 3, Table 3] In the Wavy row, TESALOCS with PSO reports E=4.4e-01 versus Random PSO E=3.1e-01, yet the table still counts this row as a TESALOCS victory in the '# of best results' count (18). Either the row is an error or the counting rule needs clarification.
- [Section 3, paragraph after Table 2] The term 'co-convergence' is used without definition; it should be stated explicitly that 'both approaches achieve errors < 1e-8' and what action is taken in that case for the victory count.
- [Algorithm 2.1] The input list includes an 'SGD algorithm' but the stopping criterion for the SGD update, its learning rate, and the number of epochs are not specified. Since these are fixed hyperparameters, they should be reported to make the experiments reproducible.
- [Figure 2] The caption lists 'six optimization algorithms (Newton-CG, SLSQP, TNC, BFGS, CG, and L-BFGS-B)' and the figure shows six curves per plot, but the legend is not described; please clarify which line corresponds to which algorithm, as the current text is ambiguous.
Circularity Check
No significant circularity: TESALOCS is evaluated on external benchmarks and no load-bearing premise reduces to a fitted input or a self-cited theorem.
full rationale
The paper is an empirical algorithmic contribution, not a derivation from fitted constants. The TT surrogate is initialized randomly and updated online from objective-function evaluations via a log-likelihood step; this is standard adaptive optimization rather than a hidden fit whose output is then relabeled as a prediction. No parameter is calibrated to the known global minima of the benchmark functions and then reported as an independent result. The tensor sampling components cite prior work, including work by overlapping authors (PROTES, TTopt), but the citations are used as background or implementation references, not as load-bearing justification of TESALOCS's central claim. There is no invoked uniqueness theorem, no ansatz smuggled in through citation, and no renaming of a known result. The main experimental weakness is the absence of a same-budget random multi-start control, since TESALOCS launches many local searches while the baseline appears to be a single local search; however, that is a fairness-of-comparison concern, not a circularity concern. The central claim does not reduce to its inputs by construction, so the circularity score is 0.
Assumptions & free parameters
free parameters (6)
- TT-rank r =
5
- Grid size N =
2^20
- Batch size k =
100
- Elite size ktop =
10
- Evaluation budget M =
10^4
- SGD hyperparameters =
unspecified
assumptions (5)
- standard math A non-negative TT tensor can be normalized to define a discrete probability distribution, and samples can be drawn from it in O(d) using the procedure of Dolgov et al. (2020).
- domain assumption A uniform grid with N=2^20 nodes per dimension, together with the projection operators Pr and Pr^{-1}, faithfully represents the continuous search space.
- domain assumption SGD on the log-likelihood of the top-k refined points concentrates future samples near promising basins of the objective.
- ad hoc to paper A fixed TT-rank r=5 is sufficient to represent promising regions for all 20 benchmark functions.
- domain assumption Comparing methods by counting objective function evaluations is a fair measure of computational budget, ignoring TT sampling, SGD, and tensor storage overhead.
Cite this review
Pith. "Pith review of High-dimensional Optimization with Low Rank Tensor Sampling and Local Search." pith.science (2026). https://pith.science/paper/XWAKAO5X
@misc{pith2026250512383,
author = {Pith},
title = {Pith review of: High-dimensional Optimization with Low Rank Tensor Sampling and Local Search},
year = {2026},
howpublished = {\url{https://pith.science/paper/XWAKAO5X}},
note = {Machine review of arXiv:2505.12383}
}
read the original abstract
We present a novel method called TESALOCS (TEnsor SAmpling and LOCal Search) for multidimensional optimization, combining the strengths of gradient-free discrete methods and gradient-based approaches. The discrete optimization in our method is based on low-rank tensor techniques, which, thanks to their low-parameter representation, enable efficient optimization of high-dimensional problems. For the second part, i.e., local search, any effective gradient-based method can be used, whether existing (such as quasi-Newton methods) or any other developed in the future. Our approach addresses the limitations of gradient-based methods, such as getting stuck in local optima; the limitations of discrete methods, which cannot be directly applied to continuous functions; and limitations of gradient-free methods that require large computational budgets. Note that we are not limited to a single type of low-rank tensor decomposition for discrete optimization, but for illustrative purposes, we consider a specific efficient low-rank tensor train decomposition. For 20 challenging 100-dimensional functions, we demonstrate that our method can significantly outperform results obtained with gradient-based methods like Conjugate Gradient, BFGS, SLSQP, and other methods, improving them by orders of magnitude with the same computing budget.
Figures
Reference graph
Works this paper leans on
-
[1]
PROTES : probabilistic optimization with tensor sampling
Anastasiia Batsheva, Andrei Chertkov, Gleb Ryzhakov, and Ivan Oseledets. PROTES : probabilistic optimization with tensor sampling. Advances in Neural Information Processing Systems, 36: 0 808--823, 2023
work page 2023
-
[2]
Efficient leverage score sampling for tensor train decomposition
Vivek Bharadwaj, Beheshteh T Rakhshan, Osman A Malik, and Guillaume Rabusseau. Efficient leverage score sampling for tensor train decomposition. Advances in Neural Information Processing Systems, 37: 0 73726--73744, 2024
work page 2024
-
[3]
Kewei Bian and Rahul Priyadarshi. Machine learning optimization techniques: a survey, classification, challenges, and future research issues. Archives of Computational Methods in Engineering, 31 0 (7): 0 4209--4233, 2024
work page 2024
-
[4]
Tensor Train Decomposition for Adversarial Attacks on Computer Vision Models
Andrei Chertkov and Ivan Oseledets. Tensor train decomposition for adversarial attacks on computer vision models. arXiv preprint arXiv:2312.12556, 2023
work page Pith review arXiv 2023
-
[5]
Tensor extrema estimation via sampling: A new approach for determining min/max elements
Andrei Chertkov, Gleb Ryzhakov, Georgii Novikov, and Ivan Oseledets. Tensor extrema estimation via sampling: A new approach for determining min/max elements. Computing in Science & Engineering, 2023
work page 2023
-
[6]
Translate your gibberish: black-box adversarial attack on machine translation systems
Andrei Chertkov, Olga Tsymboi, Mikhail Pautov, and Ivan Oseledets. Translate your gibberish: black-box adversarial attack on machine translation systems. Journal of Mathematical Sciences, 285 0 (2): 0 221--233, 2024
work page 2024
-
[7]
Andrzej Cichocki, Namgil Lee, Ivan Oseledets, Anh-Huy Phan, Qibin Zhao, and Danilo Mandic. Tensor networks for dimensionality reduction and large-scale optimization: Part 1 low-rank tensor decompositions. Foundations and Trends in Machine Learning, 9 0 (4-5): 0 249--429, 2016
work page 2016
-
[8]
Andrzej Cichocki, Anh Phan, Qibin Zhao, Namgil Lee, Ivan Oseledets, Masashi Sugiyama, and Danilo Mandic. Tensor networks for dimensionality reduction and large-scale optimization: Part 2 applications and future perspectives. Foundations and Trends in Machine Learning, 9 0 (6): 0 431--673, 2017
work page 2017
Show all 37 references
-
[9]
Dembo and Trond Steihaug
Ron S. Dembo and Trond Steihaug. Truncated-newton algorithms for large-scale unconstrained optimization. Mathematical Programming, 26 0 (2): 0 190--212, Jun 1983. ISSN 1436-4646
1983
-
[10]
Approximation and sampling of multivariate probability distributions in the tensor train decomposition
Sergey Dolgov, Karim Anaya-Izquierdo, Colin Fox, and Robert Scheichl. Approximation and sampling of multivariate probability distributions in the tensor train decomposition. Statistics and Computing, 30: 0 603--625, 2020
2020
-
[11]
A new scheme for the tensor representation
Wolfgang Hackbusch and Stefan K \"u hn. A new scheme for the tensor representation. Journal of Fourier analysis and applications, 15 0 (5): 0 706--722, 2009
2009
-
[12]
Comparison of optimization techniques based on gradient descent algorithm: A review
Saad Hikmat Haji and Adnan Mohsin Abdulazeez. Comparison of optimization techniques based on gradient descent algorithm: A review. PalArch’s Journal of Archaeology of Egypt/Egyptology, 18 0 (4): 0 2715--2743, 2021
2021
-
[13]
Cma-es: evolution strategies and covariance matrix adaptation
Nikolaus Hansen and Anne Auger. Cma-es: evolution strategies and covariance matrix adaptation. In Proceedings of the 13th Annual Conference Companion on Genetic and Evolutionary Computation, GECCO '11, page 991–1010, New York, NY, USA, 2011. Association for Computing Machinery
2011
-
[14]
Foundations of the PARAFAC procedure: Models and conditions for an explanatory multimodal factor analysis
Richard A Harshman et al. Foundations of the PARAFAC procedure: Models and conditions for an explanatory multimodal factor analysis. UCLA Working Papers in Phonetics, 16: 0 1--84, 1970
1970
-
[15]
Mmes: Mixture model-based evolution strategy for large-scale optimization
Xiaoyu He, Zibin Zheng, and Yuren Zhou. Mmes: Mixture model-based evolution strategy for large-scale optimization. IEEE Transactions on Evolutionary Computation, 25 0 (2): 0 320--333, 2021
2021
-
[16]
A literature survey of benchmark functions for global optimization problems
Momin Jamil and Xin-She Yang. A literature survey of benchmark functions for global optimization problems. Journal of Mathematical Modelling and Numerical Optimisation, 4 0 (2): 0 150--194, 2013
2013
-
[17]
Particle swarm optimization
James Kennedy and Russell Eberhart. Particle swarm optimization. In Proceedings of ICNN'95-international conference on neural networks, volume 4, pages 1942--1948. ieee, 1995
1942
-
[18]
Cma-es with optimal covariance update and storage complexity
Oswin Krause, D\' dac Rodr\' guez Arbon\` e s, and Christian Igel. Cma-es with optimal covariance update and storage complexity. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associat...
2016
-
[19]
Effective training of PINN s by combining CMA-ES with gradient descent
Lin Liu and Yuan Yuan. Effective training of PINN s by combining CMA-ES with gradient descent. In 2024 IEEE Congress on Evolutionary Computation (CEC), pages 1--8. IEEE, 2024
2024
-
[20]
Are quantum computers practical yet? a case for feature selection in recommender systems using tensor networks
Artyom Nikitin, Andrei Chertkov, Rafael Ballester-Ripoll, Ivan Oseledets, and Evgeny Frolov. Are quantum computers practical yet? a case for feature selection in recommender systems using tensor networks. arXiv preprint arXiv:2205.04490, 2022
2022 arXiv
-
[21]
Jorge Nocedal and Stephen J. Wright. Numerical Optimization . Springer Series in Operations Research and Financial Engineering. Springer, New York, 2 edition, 2006
2006
-
[22]
Tensor-train density estimation
Georgii S Novikov, Maxim E Panov, and Ivan V Oseledets. Tensor-train density estimation. In Uncertainty in artificial intelligence, pages 1321--1331. PMLR, 2021
2021
-
[23]
Tensor-train decomposition
Ivan Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33 0 (5), 2011
2011
-
[24]
Black-box solver for multiscale modelling using the qtt format
Ivan V Oseledets, Maxim V Rakhuba, and Andrei V Chertkov. Black-box solver for multiscale modelling using the qtt format. Proc. ECCOMAS. Crete Island, Greece, 2016
2016
-
[25]
Probabilistic tensor optimization of quantum circuits for the max-k-cut problem
GV Paradezhenko, AA Pervishko, and D Yudin. Probabilistic tensor optimization of quantum circuits for the max-k-cut problem. Physical Review A, 109 0 (1): 0 012436, 2024
2024
-
[26]
Restarted local search algorithms for continuous black box optimization
Petr Po s \' k and Waltraud Huyer. Restarted local search algorithms for continuous black box optimization. Evolutionary computation, 20 0 (4): 0 575--607, 2012
2012
-
[27]
Fast gradient-free activation maximization for neurons in spiking neural networks
Nikita Pospelov, Andrei Chertkov, Maxim Beketov, Ivan Oseledets, and Konstantin Anokhin. Fast gradient-free activation maximization for neurons in spiking neural networks. Neurocomputing, page 129070, 2024
2024
-
[28]
Constructive TT -representation of the tensors given as index interaction functions with applications
Gleb Ryzhakov and Ivan Oseledets. Constructive TT -representation of the tensors given as index interaction functions with applications. In 11th International Conference on Learning Representations, ICLR , 2023
2023
-
[29]
An elegant multi-agent gradient descent for effective optimization in neural network training and beyond
Mohammad Sakka and Mohammad Reza Bahrami. An elegant multi-agent gradient descent for effective optimization in neural network training and beyond. Applied Sciences, 15 0 (4): 0 2008, 2025
2008
-
[30]
Schönborn, Stefan Goedecker, Shantanu Roy, and Artem R
Sandro E. Schönborn, Stefan Goedecker, Shantanu Roy, and Artem R. Oganov. The performance of minima hopping and evolutionary algorithms for cluster structure prediction. The Journal of Chemical Physics, 130 0 (14): 0 144108, 04 2009. ISSN 0021-9606
2009
-
[31]
Global optimization of surface warpage for inverse design of ultra-thin electronic packages using tensor train decomposition
Cheryl Selvanayagam, Pham Luu Trung Duong, Brett Wilkerson, and Nagarajan Raghavan. Global optimization of surface warpage for inverse design of ultra-thin electronic packages using tensor train decomposition. IEEE Access, 10: 0 48589--48602, 2022
2022
-
[32]
Tensor train for global optimization problems in robotics
Suhan Shetty, Teguh Lembono, Tobias Loew, and Sylvain Calinon. Tensor train for global optimization problems in robotics. arXiv preprint arXiv:2206.05077, 2022
2022 arXiv
-
[33]
TTOpt : A maximum volume quantized tensor train-based optimization and its application to reinforcement learning
Konstantin Sozykin, Andrei Chertkov, Roman Schutski, Anh-Huy Phan, Andrzej Cichocki, and Ivan Oseledets. TTOpt : A maximum volume quantized tensor train-based optimization and its application to reinforcement learning. Advances in Neural Information Processing Systems, 35: 0 2...
2022
-
[34]
Multivariate stochastic approximation using a simultaneous perturbation gradient approximation
James C Spall. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE transactions on automatic control, 37 0 (3): 0 332--341, 1992
1992
-
[35]
Policy gradient method for robust reinforcement learning
Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In International conference on machine learning, pages 23484--23526. PMLR, 2022
2022
-
[36]
A limited-memory bfgs-based differential evolution algorithm for optimal control of nonlinear systems with mixed control variables and probability constraints
Xiang Wu and Kanjian Zhang. A limited-memory bfgs-based differential evolution algorithm for optimal control of nonlinear systems with mixed control variables and probability constraints. Numerical Algorithms, 93 0 (2): 0 493--542, 2023. ISSN 1572-9265
2023
-
[37]
Local optima networks for reinforcement learning - a case study: Coupled inverted pendulum task
Yuyang Zhou, Alexander Turner, and Ferrante Neri. Local optima networks for reinforcement learning - a case study: Coupled inverted pendulum task. In 2024 IEEE Conference on Artificial Intelligence (CAI), pages 865--870, 2024
2024
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.