Deflating Found Basins Inside a Tensor Train Search Model

Some global optimizers learn a probability distribution over the search space, draw candidate points from it, polish those points with a fast local solver, and then shift the distribution toward the points that polished best. When the distribution is stored as a tensor train, the method stays tractable in 100 dimensions. A tensor train is a chain of small matrices whose product gives the value at any grid point, so it avoids storing an exponentially large grid. The weakness is familiar from evolutionary search: the learned distribution piles its mass onto the first good valley it finds and stops proposing anything else. We propose to fix this in a way that only a tensor train allows. Each time the local solver lands in a valley, we build an exact low-rank "hole" shaped like that valley and multiply it into the distribution. The model can then neither sample the valley again nor keep learning toward it.

The mechanism works because a product of one-dimensional bumps, one per coordinate, is a rank-1 tensor train. Carving it out of the model is ordinary tensor train arithmetic. It adds a small, known amount of rank, and exact sampling from the result stays cheap. In plain terms, this is the deflation trick from eigenvalue and root-finding problems, applied to the search distribution rather than to the objective.

Core Claim

The closest existing methods are PROTES and TESALOCS. PROTES learns a tensor train distribution over a discrete grid by stochastic gradient descent on its best samples. TESALOCS feeds such samples to gradient-based local solvers and trains the model on the polished outcomes. Neither contains any mechanism against the distribution collapsing onto one basin. The research file names this gap for both.

We claim that algebraic deflation of already-found basins, applied both when sampling and when choosing training targets, raises the number of distinct basins discovered and the probability of reaching the global basin under a fixed evaluation budget. We further claim it does better than the cheaper fixes a reviewer would reach for: entropy regularization, rejection of candidates near known minima, and restarting the model.

The contribution is not "add diversity to a tensor train optimizer" in general. It is a specific and testable operator, together with an ablation separating its two roles. In the sampling role, it stops wasted draws. In the learning role, it redirects what the model learns.

Mechanism

Let $p_\theta$ be the tensor train model with rank at most $R$ on an $N^d$ grid with coordinates $x_k(i_k)$. Following Optimization of Functions Given in the Tensor Train Format, we treat $p_\theta$ as a square-root density and sample from its square, so the model entries may take either sign. After the local solver has converged to $M$ distinct minimizers with centers $c_j$, we define the deflation mask and the deflated sampling density as

$$m(i) = 1 - \sum_{j=1}^{M} \prod_{k=1}^{d} \exp\!\left(-\frac{(x_k(i_k)-c_{jk})^2}{2 s_{jk}^2}\right), \qquad q(i) \propto \big(p_\theta(i)\, m(i)\big)^2 .$$

The mask $m$ is an exact tensor train of rank $M+1$. The elementwise product $p_\theta m$ therefore has rank at most $R(M+1)$, and the square guarantees that $q$ is non-negative even where bumps overlap. We keep the rank bounded in two ways: by rounding the product back to a cap $R_{\max}$ with the standard tensor train SVD, and by merging bumps whose centers the local solver maps to the same minimizer.

The widths $s_{jk}$ are the design choice that matters most. An isotropic Euclidean kernel with one width would inherit the distance-concentration problem that limits Divergence-Guided PSO above about 50 dimensions. Instead, we set each $s_{jk}$ per coordinate from the local solver's own information. We will compare two sources: the inverse square root of the diagonal of the final quasi-Newton Hessian, and the spread of the solver's starting points that converged to $c_j$. With either choice, the hole has the valley's shape along each axis rather than the shape of a fixed ball.

The learning step then trains $p_\theta$ by the same stochastic gradient updates used in TESALOCS, but only on the elite points drawn from $q$. Mass that the model would otherwise pour into known basins is never rewarded.

Research Program

The work has three parts.

The first part is to measure the collapse before trying to cure it. We rerun TESALOCS on its own 100-dimensional suite and on problems with many optima. At each iteration we record the fraction of new samples whose polished result lands in an already-found basin, and the number of distinct basins found per $10^3$ evaluations. If this fraction does not approach one in the vanilla method, the premise is wrong and we stop.

The second part is to build the deflation operator. This includes the rank-rounding policy, the per-coordinate width rules, and a merge rule for bumps. We will characterize empirically how rank, sampling cost, and rounding error grow with $M$.

The third part runs the head-to-head comparisons and ablations described below. It also includes one domain where finding many solutions is itself the goal: multi-solution inverse kinematics, taken from TTGO.

A secondary question is whether deflation removes the need to tune TTGO's sharpness parameter $\alpha$. With deflation, a sharp $\alpha$ may become safe, because the method cannot stay stuck on one mode.

Baselines

The naive reference point is multistart local search: uniform random starting points polished by BFGS, Newton-CG, or SLSQP. It uses the same $10^4$ evaluation budget TESALOCS used at $d=100$, and every polishing evaluation counts toward that budget. This point tells us whether any learned model helps at all.

The strongest existing method is TESALOCS itself, run with its published pipeline and the same local solvers. The benchmark figure the file reports for it is on 100-dimensional Alpine under $10^4$ evaluations: BFGS error fell from $3.8 \times 10^{-4}$ with random initialization to $1.8 \times 10^{-9}$ with TESALOCS (TESALOCS). Because that result is already near machine precision, beating TESALOCS on Alpine is not meaningful. We count a win only on functions where vanilla TESALOCS leaves a measurable gap to the known optimum, or on basin-count metrics. We will report the vanilla gaps ourselves, since the file gives only convergence plots for Ackley, Rastrigin, and Rosenbrock. PROTES is included as the pure-sampling variant without local polishing.

For the deterministic tensor train approach we run TT-IPP. It reports an error of $10^{-15}$ on the 50-dimensional DNA chain problem, where PSO, simulated annealing, and consensus-based optimization stayed above $1.0$. On that problem our target is to match its accuracy using fewer evaluations; we do not expect to beat the error itself. For inverse kinematics the reference is TTGO's reported 94% success with one sample at $\alpha=0.9$. There, a win means more distinct valid solutions per fixed number of samples at equal or better success rate.

The ablations are the heart of the study. The first is mask-at-sampling-only: $q$ is used for drawing, but $p_\theta$ is trained on all elites, including those in known basins. The second is mask-in-learning-only. The third replaces the per-coordinate widths with a single isotropic width, which tests the distance-concentration concern. The fourth is the full method.

All methods share the same grid resolution $N$, rank cap, local solver, and evaluation budget. Each gets the same number of hyperparameter configurations, tuned on a held-out subset of functions, and results are reported over 20 seeds.

Why not just…?

Why not just add an entropy bonus or a higher temperature to the model's training? This is the most natural fix, and it could work well on landscapes with evenly spaced minima such as Rastrigin. Its weakness is that it spreads mass everywhere rather than away from known basins. It therefore trades convergence precision for coverage, which is exactly the loss on unimodal problems that DPSO reports on Sphere. We run an entropy-regularized TESALOCS with a tuned coefficient as a baseline. If it matches deflation on both basin count and final error, the operator adds nothing, and we will say so.

Why not just reject sampled points that fall near a known minimum? Drawing samples from a tensor train costs no function evaluations, so rejection is cheap. It is a genuine threat. It differs from our method in one respect only: the model underneath still collapses. The acceptance rate should therefore fall toward zero, and the learning signal keeps reinforcing old basins. Our mask-at-sampling-only ablation is essentially exact rejection sampling without the waste. If it performs as well as the full method, the claim that deflation redirects learning fails. The contribution would then shrink to an efficiency trick, and we would report it as such.

Why not just restart the tensor train model when progress stalls, as Iterated Population-Based Training does? IPBT detects stagnation with a Gaussian process and resets with "shrink-perturb." Applied here, this would reinitialize the tensor train and keep an archive of results. A restart discards everything the model has learned about good regions that are not yet exhausted, and it can find the same basin again. Deflation removes only what has been found. We implement a stagnation-triggered restart variant of TESALOCS; it will lose to deflation on basin-count-per-evaluation if our argument is right.

Proposed Experiments

The analytic suite is Ackley, Rastrigin, Griewank, Rosenbrock, Alpine, Michalewicz, and Schwefel at $d \in \{10, 50, 100\}$ under $10^4$ evaluations. Sphere is included as the unimodal control, where we expect deflation to cost some evaluations but not to worsen the best value found. The applied problems are the 50-dimensional DNA chain problem from TT-IPP, and 7-DoF inverse kinematics plus the Himmelblau and Gaussian-mixture multi-mode tests from TTGO.

We report three metrics: final error relative to the known optimum, the fraction of seeds reaching the global basin, and the number of distinct basins found as a function of evaluations. We also report wall-clock time and the rank reached after rounding, so the arithmetic overhead is visible. The research file reports no result on Lacuna for any tensor train method paired with a diversity mechanism, so all such numbers here will be new.

Three checks decide the question. The first is whether vanilla TESALOCS's repeat-basin fraction actually approaches one; if not, there is no collapse to fix. The second is whether full deflation beats mask-at-sampling-only on global-basin success. That comparison is what shows deflation redirecting learning rather than merely filtering samples. The third is whether per-coordinate widths beat isotropic widths at $d=100$ but not at $d=10$. That pattern would confirm the distance-concentration argument as the reason tensor train deflation succeeds where Euclidean repulsion fades.