Back

TTOpt: A Maximum Volume Quantized Tensor Train-based Optimization and its Application to Reinforcement Learning

Konstantin SozykinAndrei ChertkovRoman SchutskiAnh-Huy PhanAndrzej S. CichockiIvan V. Oseledets

article2022NeurIPS62 citations

Develops a gradient-free optimization algorithm based on quantized tensor train decomposition and the maximum matrix volume principle, enabling direct training of quantized neural network policies for reinforcement learning with substantially fewer function evaluations than existing methods.

Listen

Many modern artificial intelligence and control applications require optimizing complex, non-differentiable target functions where traditional gradient-based methods fail. While gradient-free approaches such as evolutionary algorithms provide a flexible alternative, they typically suffer from slow convergence and demand massive numbers of function evaluations. Furthermore, deploying neural network policies directly onto low-power edge hardware requires quantized, discrete parameters, a constraint that traditional continuous optimization methods struggle to handle efficiently.

The article introduces and evaluates the Tensor Train Optimizer (TTOpt), a novel gradient-free algorithm designed to solve multivariable optimization problems across discrete and continuous domains. The primary objective is to demonstrate that tensor network decomposition combined with submatrix volume maximization can locate optimal parameters substantially faster and with fewer function evaluations than existing gradient-free benchmarks, particularly in reinforcement learning settings.

To evaluate this approach, the authors reformulated optimization problems into discrete multidimensional tensors and used low-rank Tensor Train structures alongside a maximum matrix volume selection principle to sample only a tiny fraction of total possibilities. They benchmarked TTOpt against standard zeroth-order methods (such as genetic algorithms and evolutionary strategies) and classical gradient-based algorithms across ten standard mathematical benchmark functions and four continuous-control reinforcement learning environments, testing problems scaling up to 500 dimensions on standard consumer computing hardware.

The findings show that TTOpt consistently achieved superior precision on mathematical benchmarks, maintaining stable accuracy even as problem dimensionality scaled from 10 to 500 variables while running in 2.3 to 2.6 seconds. In reinforcement learning tasks, TTOpt matched or exceeded baseline performance across coarse and fine discrete grids, notably solving the InvertedPendulum-v2 control task with a perfect cumulative reward (1000.00 with zero variance) where evolutionary baselines showed high variance. Additionally, the algorithm exhibited significantly faster execution times and more consistent convergence curves across multiple runs compared to popular evolutionary strategies.

These results demonstrate that direct optimization of heavily quantized, discrete model weights is practical and highly effective for continuous control tasks. This capability enables organizations to train compact neural network policies directly for low-power edge devices, drastically lowering computational runtime, hardware power demands, and cloud training costs without sacrificing control accuracy or policy performance.

Organizations developing edge-deployed artificial intelligence or complex control systems should consider testing tensor-based optimization workflows as an alternative to standard evolutionary search. Further development should focus on testing TTOpt in larger-scale industrial reinforcement learning pipelines and multi-agent systems to validate scaling trade-offs before broad production deployment.

While the empirical results are strong, users should note that the multidimensional sweep formulation currently lacks formal theoretical guarantees for global convergence rates. Readers should treat convergence behavior as monotonic but empirical, paying close attention to initial rank selection and computational query budgets when deploying on uncharacterized objective functions.

Artificial Intelligence Research Institute (AIRI)RIKEN AIPSkolkovo Institute of Science and TechnologySystems Research Institute, Polish Academy of Sciencesoptimizationquantizersreinforcement learningTTOpt algorithmquantized tensor trainreinforcement learning
arXiv: 2205.00293
  • Paper: Fast Tensor Completion via Approximate Richardson Iteration, Mehrdad Ghadiri et al. (2025). Develops fast approximate methods for completing missing data in tensor train and related decomposition formats, offering complementary algorithmic acceleration for low-rank tensor operations.
  • Paper: OMPQ: Orthogonal Mixed Precision Quantization, Yuexiao Ma et al. (2023). Explores layer-wise mixed-precision neural network quantization, extending the goal of deploying low-precision policies onto resource-constrained edge hardware.
  • Paper: Adaptive Data-Free Quantization, Biao Qian et al. (2023). Investigates low-bit neural network quantization under data-free constraints, complementing TTOpt's study of heavily quantized discrete parameter spaces.
Cover for TTOpt: A Maximum Volume Quantized Tensor Train-based Optimization and its Application to Reinforcement Learning

Abstract

We present a novel procedure for optimization based on the combination of efficient quantized tensor train representation and a generalized maximum matrix volume principle. We demonstrate the applicability of the new Tensor Train Optimizer (TTOpt) method for various tasks, ranging from minimization of multidimensional functions to reinforcement learning. Our algorithm compares favorably to popular gradient-free methods and outperforms them by the number of function evaluations or execution time, often by a significant margin.

Topics

optimizationquantizersreinforcement learning

Keywords

TTOpt algorithmquantized tensor trainreinforcement learningblack-box optimizationtensor decompositionsmaxvol algorithmpolicy optimizationglobal optimizationgradient-free optimizationtensor networks

Table of Contents

  • 1 Introduction
  • 2 Optimization with tensor train
  • 2.1 Discrete formulation of optimization problems
  • 2.2 Tensor Train decomposition
  • 2.3 Maximal element in a matrix
  • 2.4 Optimization in the multidimensional case
  • 2.5 Complexity of the algorithm
  • 2.6 Implementation details
  • 3 Experiments
  • 3.1 Benchmark functions minimization
  • 3.2 Application of TTOpt to Reinforcement Learning
  • 4 Related work
  • 5 Conclusion
  • Acknowledgments and Disclosure of Funding
  • References
  • Checklist

Knowls

  1. Knowl 1 — TTOpt Multidimensional Optimization Algorithm

    algorithm

    The Tensor-Train Optimizer (TTOpt) solves multivariable optimization problems by discretizing each parameter θk∈[a,b]\theta_k \in [a, b] for k∈{1,…,d}k \in \{1, \dots, d\} into a grid of size NkN_k, treating the target function J(θ)J(\theta) as an implicitly defined dd-dimensional tensor J∈RN1×N2×⋯×Nd\mathcal{J} \in \mathbb{R}^{N_1 \times N_2 \times \cdots \times N_d}. Rather than constructing the full tensor or its low-rank approximation everywhere, TTOpt performs alternating forward and backward sweeps across unfolding matrices, adaptively querying submatrices of maximal volume to find the global optimum.

    Input: Black-box objective function J(θ)J(\theta), dimension dd, mode sizes N1,…,NdN_1, \dots, N_d, target ranks R1,…,Rd−1R_1, \dots, R_{d-1}, max sweeps TT, query budget MM
    Output: Approximate global optimum θopt\theta_{\text{opt}} and optimal value JoptJ_{\text{opt}}
    Initialize row multi-index sets Ik(R)I_k^{(R)} and column multi-index sets Ik(C)I_k^{(C)} for unfoldings k=1,…,d−1k=1, \dots, d-1
    Initialize Jmin⁡←∞J_{\min} \leftarrow \infty and set dynamic mapping g(x)=π2−atan⁡(J(x)−Jmin⁡)g(x) = \frac{\pi}{2} - \operatorname{atan}(J(x) - J_{\min})
    for sweep t=1t = 1 to TT do
        // Forward sweep
        for mode k=1k = 1 to d−1d-1 do
            Construct column submatrix Jk(C)J_k^{(C)} by evaluating gg at Cartesian product of Ik−1(R)I_{k-1}^{(R)}, mode kk grid, and sampled multi-indices Ik(C)I_k^{(C)}
            Update best encountered function value Jmin⁡J_{\min} and mapping gg
            Compute QR factorization Jk(C)=QkRkqrJ_k^{(C)} = Q_k R_k^{\text{qr}}
            Apply rect_maxvol on QkQ_k to select RkR_k maximal-volume row multi-indices Ik(R)I_k^{(R)}
        end for
        // Backward sweep
        for mode k=d−1k = d-1 down to 1 do
            Construct row submatrix Jk(R)J_k^{(R)} using Ik(R)I_k^{(R)} and mode k+1k+1 grid points
            Update best encountered function value Jmin⁡J_{\min} and mapping gg
            Compute QR factorization (Jk(R))T=QkrowRkqr(J_k^{(R)})^T = Q_k^{\text{row}} R_k^{\text{qr}}
            Apply rect_maxvol on QkrowQ_k^{\text{row}} to update column multi-indices Ik(C)I_k^{(C)}
        end for
        if total function queries exceeds MM then
            break
        end if
    end for
    Return θopt\theta_{\text{opt}} corresponding to the overall minimal J(θ)J(\theta) evaluated during all sweeps

  2. Knowl 2 — Quantized Tensor Train Mode Representation in TTOpt

    model/method

    When grid mode sizes NkN_k are large, the unfolding matrices become excessively wide or tall, causing the computational complexity of the maximum volume algorithm to grow rapidly. TTOpt overcomes this via quantized tensor train (QTT) structuring: assuming each mode size satisfies Nk=PqN_k = P^q (where P≥2P \ge 2 is a small submode base, typically P=2P = 2, and q≥2q \ge 2 is the number of submodes per dimension), the original dd-dimensional tensor J∈RN1×⋯×Nd\mathcal{J} \in \mathbb{R}^{N_1 \times \dots \times N_d} is reshaped into a higher-dimensional quantized tensor J~∈RP×P×⋯×P\tilde{\mathcal{J}} \in \mathbb{R}^{P \times P \times \dots \times P} of effective dimension d⋅qd \cdot q.

    TTOpt is executed on this (d⋅q)(d \cdot q)-dimensional quantized tensor with mode size PP. Given a query budget MM and a minimum number of sweeps TT (set to T=5T=5), since each forward and backward pass queries approximately 2⋅T⋅(d⋅q)⋅P⋅R22 \cdot T \cdot (d \cdot q) \cdot P \cdot R^2 entries, the maximum rank RR is configured via the heuristic bound:

    R≤M2⋅T⋅d⋅q⋅PR \le \sqrt{\frac{M}{2 \cdot T \cdot d \cdot q \cdot P}}

  3. Knowl 3 — Dynamic Mapping Function for Extremum Finding in TTOpt

    equation

    The maximum volume principle identifies submatrices that maximize the modulus of the determinant, thereby selecting elements with maximal absolute value without distinguishing between signs or targeting minima versus maxima. To find the minimum of an objective function J(x)J(x), TTOpt applies a dynamic, strictly monotone, continuous transformation g(x)g(x) at each step:

    g(x)=π2−atan⁡(J(x)−Jmin⁡)g(x) = \frac{\pi}{2} - \operatorname{atan}(J(x) - J_{\min})

    where Jmin⁡J_{\min} denotes the lowest objective function value discovered up to the current step. When J(x)→Jmin⁡J(x) \to J_{\min}, g(x)→π2g(x) \to \frac{\pi}{2}, and when J(x)>Jmin⁡J(x) > J_{\min}, g(x)g(x) decreases smoothly towards 00. This transformation ensures that points close to the current global minimum produce the largest positive values, guiding the maximum volume search directly toward minimizing J(x)J(x).

  4. Knowl 4 — Matrix Maximum Volume Submatrix Bound for Global Extremum

    theoretical result

    For an implicitly given matrix J∈RN1×N2J \in \mathbb{R}^{N_1 \times N_2}, let J^∈RR×R\hat{J} \in \mathbb{R}^{R \times R} be an R×RR \times R submatrix of maximal volume (defined as having the maximum absolute determinant among all non-degenerate R×RR \times R submatrices spanning selected rows and columns). The maximal absolute element J^max⁡=max⁡i,j∣J^i,j∣\hat{J}_{\max} = \max_{i, j} |\hat{J}_{i,j}| contained within J^\hat{J} bounds the global absolute maximum element Jmax⁡=max⁡i,j∣Ji,j∣J_{\max} = \max_{i, j} |J_{i,j}| across the entire matrix JJ according to:

    J^max⁡⋅R2≥Jmax⁡\hat{J}_{\max} \cdot R^2 \ge J_{\max}

    For R=1R = 1, the bound is exact (J^max⁡≥Jmax⁡\hat{J}_{\max} \ge J_{\max}). For R>1R > 1, finding a maximal volume submatrix J^\hat{J} guarantees that its entries contain an element proportional to the global extremum within a factor of R2R^2.

  5. Knowl 5 — Computational and Query Complexity of TTOpt

    theoretical result

    For a discrete objective tensor of dimension dd with mode sizes NkN_k and approximation ranks RkR_k across TT forward and backward sweeps:

    1. The total number of function evaluations (queries to the objective function JJ) is: O(T⋅d⋅max⁡1≤k≤d(NkRk2))\mathcal{O}\left(T \cdot d \cdot \max_{1 \le k \le d} (N_k R_k^2)\right)

    2. When function calls are computationally cheap and the submatrix maximum volume selection dominates the running time, the computational time complexity of TTOpt is: O(T⋅d⋅max⁡1≤k≤d(NkRk3))\mathcal{O}\left(T \cdot d \cdot \max_{1 \le k \le d} (N_k R_k^3)\right)

  6. Knowl 6 — Comparative Optimization Performance on 10-Dimensional Analytical Benchmarks

    data/table

    TTOpt was evaluated on ten 10-dimensional benchmark functions (F1F1 to F10F10, including non-separable and multimodal functions like Ackley, Alpine, Exponential, Griewank, Michalewicz, Picheny, Qing, Rastrigin, Rosenbrock, and Schwefel) against zeroth-order methods (GA, OpenES, CMA-ES, Differential Evolution, NoisyBandit, PSO) and first-/second-order methods (BFGS, L-BFGS, CG, NCG, Newton, Trust-Region NCG, Trust-Region Exact). All methods were given a maximum evaluation budget of M=105M = 10^5. For TTOpt, parameters were R=4R = 4, P=2P = 2, and q=25q = 25.

    Method Metric F1 F2 F3 F4 F5 F6 F7 F8 F9 F10
    TTOPT ϵ\epsilon 3.9E-06 2.9E-07 1.8E-12 4.4E-15 2.8E-02 1.1E-01 5.5E-09 4.6E-11 1.8E-01 1.3E-04
    τ\tau (s) 2.61 2.44 2.45 2.52 2.40 2.48 2.39 2.60 2.32 2.44
    GA ϵ\epsilon 9.7E-02 8.4E-03 5.8E-03 2.0E+00 3.9E-04 1.0E+01 1.2E-01 7.9E-01 6.2E-03 4.2E+03
    τ\tau (s) 6.21 4.56 5.09 4.87 5.85 5.69 5.05 5.04 5.04 4.70
    OPENES ϵ\epsilon 1.8E-01 1.2E-02 1.7E-02 2.0E+00 1.2E-03 9.7E+00 3.8E+00 2.1E+00 1.8E-02 4.2E+03
    τ\tau (s) 2.62 1.08 1.62 1.08 2.41 2.04 1.30 1.39 1.62 1.12
    CMAES ϵ\epsilon 5.1E+287 3.1E-01 9.3E-77 2.0E+00 7.6E+289 1.9E+01 5.5E-02 9.3E+01 5.3E+289 1.7E+282
    τ\tau (s) 10.36 8.50 9.40 9.13 12.86 9.76 9.04 9.13 11.15 8.86
    DE ϵ\epsilon 1.1E+00 4.3E-02 3.3E-02 9.0E-05 1.8E-01 2.6E-01 2.0E-01 6.2E+00 6.6E-01 3.8E+02
    τ\tau (s) 38.91 38.06 51.05 39.48 41.35 41.40 41.34 41.31 37.97 38.64
    NB ϵ\epsilon 1.5E+01 6.5E+00 3.9E+01 1.2E-01 2.4E+01 6.6E+00 2.6E+10 6.3E+01 3.4E+00 3.2E+03
    τ\tau (s) 45.23 46.98 37.50 45.91 48.03 37.16 40.05 44.95 44.06 46.91
    PSO ϵ\epsilon 1.2E+01 5.3E+00 3.5E+01 9.8E-02 2.0E+01 2.5E-01 2.0E+10 2.3E+01 5.1E-01 2.9E+03
    τ\tau (s) 47.19 47.04 45.50 43.39 46.80 44.97 46.46 42.78 43.15 47.13

    Values represent average absolute error ϵ=∣J^min⁡−Jmin⁡∣\epsilon = |\hat{J}_{\min} - J_{\min}| and running time τ\tau (in seconds) over 10 independent runs. TTOpt consistently converged to high precision without falling into local minima or experiencing the severe convergence failures seen in CMA-ES (e.g., F1F1, F5F5, F9F9, F10F10) while maintaining low execution times ( ≈2.4 s\,\approx 2.4\,\text{s}).

  7. Knowl 7 — Scalability to High Dimensions on Ackley Benchmark Function

    data/table

    The performance of TTOpt was tested on the multimodal Ackley benchmark function (F1F1) across dimensions d∈{10,50,100,500}d \in \{10, 50, 100, 500\}. The query budget was scaled proportionally as M=104⋅dM = 10^4 \cdot d, with rank R=4R = 4, base P=2P = 2, and submode count q=25q = 25.

    Dimension d=10d = 10 d=50d = 50 d=100d = 100 d=500d = 500
    Error ϵ\epsilon 3.9E-06 3.9E-06 3.9E-06 3.9E-06
    Time τ\tau (s) 3.1 40.1 143.9 3385.3

    TTOpt maintained an identical absolute error of ϵ=3.9×10−6\epsilon = 3.9 \times 10^{-6} across all dimensions up to d=500d = 500, demonstrating that the quantized tensor train formulation scales without degradation in optimization precision.

  8. Knowl 8 — Quantized Policy Optimization Performance in Continuous Control RL

    data/table

    TTOpt was applied to train reinforcement learning policies represented by neural networks (3 convolutional hidden layers with tanh and ReLU activations) on continuous control MuJoCo and Gym environments: Swimmer-v3 (S), LunarLanderContinuous-v2 (L), InvertedPendulum-v2 (I), and HalfCheetah-v3 (H). Weights were discretized to coarse 3-level grids (N=3N = 3, bounds [−1,1][-1, 1]) and fine 8-bit grids (N=28=256N = 2^8 = 256, bounds [−1,1][-1, 1]).

    Coarse Grid (N=3N = 3) Fine Grid (N=256N = 256)
    Method S(3) L(3) I(3) H(3) S(282^8) L(282^8) I(282^8) H(282^8)
    TTOPT 357.50±6.59\mathbf{357.50}_{\pm 6.59} 290.29±24.40\mathbf{290.29}_{\pm 24.40} 1000.00±0.00\mathbf{1000.00}_{\pm 0.00} 4211.02±211.94\mathbf{4211.02}_{\pm 211.94} 311.82±29.61311.82_{\pm 29.61} 286.87±21.65\mathbf{286.87}_{\pm 21.65} 1000.00±0.00\mathbf{1000.00}_{\pm 0.00} 2935.90±544.112935.90_{\pm 544.11}
    GA 349.91±10.04349.91_{\pm 10.04} 283.05±16.28283.05_{\pm 16.28} 893.00±283.10893.00_{\pm 283.10} 2495.37±185.112495.37_{\pm 185.11} 359.79±4.21\mathbf{359.79}_{\pm 4.21} 213.75±99.67213.75_{\pm 99.67} 222.86±342.79222.86_{\pm 342.79} 3085.80±842.76\mathbf{3085.80}_{\pm 842.76}
    CMAES 342.31±36.07342.31_{\pm 36.07} 214.55±93.79214.55_{\pm 93.79} 721.00±335.37721.00_{\pm 335.37} 2549.83±501.082549.83_{\pm 501.08} 340.54±78.90340.54_{\pm 78.90} 221.95±133.80221.95_{\pm 133.80} 621.00±472.81621.00_{\pm 472.81} 2879.46±929.552879.46_{\pm 929.55}
    OPENES 318.39±44.61318.39_{\pm 44.61} 114.97±113.48114.97_{\pm 113.48} 651.86±436.37651.86_{\pm 436.37} 2423.16±602.432423.16_{\pm 602.43} 109.39±40.11109.39_{\pm 40.11} 73.08±163.3373.08_{\pm 163.33} 224.71±217.51224.71_{\pm 217.51} 1691.22±976.961691.22_{\pm 976.96}

    Reported values are mean E\mathbb{E} and standard deviation σ\sigma of cumulative episode reward over 10 random seeds. On the coarse discrete domain (N=3N = 3), TTOpt outperforms all evolutionary baselines across all tasks (e.g., reaching 4211.02 on HalfCheetah-v3 vs 2495.37–2549.83 for baselines) while maintaining low dispersion. On fine 8-bit grids (N=256N = 256), TTOpt outperforms baselines on InvertedPendulum and LunarLander, while training quantized policies with substantially faster wall-clock execution time.

  9. Knowl 9 — Stabilization via QR Factorization and Rectangular Maximum Volume

    model/method

    Two algorithmic enhancements ensure numerical stability and rank flexibility during TTOpt iterations:

    1. QR Stabilization: The generated column submatrices Jk(C)J_k^{(C)} or row submatrices Jk(R)J_k^{(R)} can become ill-conditioned or degenerate during optimization sweeps, causing direct maximum volume selection to fail. TTOpt resolves this by computing the QR factorization Jk(C)=QkRkqrJ_k^{(C)} = Q_k R_k^{\text{qr}} and executing the maximum volume search on the orthogonal factor QkQ_k.

    2. Rectangular Maximum Volume (rect_maxvol): Because optimal ranks RkR_k of the tensor unfoldings are unknown a priori, TTOpt employs rect_maxvol instead of standard square maxvol. This procedure selects Rk+ΔRkR_k + \Delta R_k rows to form rectangular maximal-volume submatrices J^k(C)∈R(Rk+ΔRk)×Rk\hat{J}_k^{(C)} \in \mathbb{R}^{(R_k + \Delta R_k) \times R_k}. If necessary, rank overestimation can be compressed post hoc using truncated SVD.

  10. Knowl 10 — Theoretical Limitations on Multidimensional Convergence Guarantees

    limitation

    Unlike the 2D matrix case where a maximal volume submatrix J^\hat{J} satisfies the global element bound J^max⁡⋅R2≥Jmax⁡\hat{J}_{\max} \cdot R^2 \ge J_{\max}, there is currently no proven theoretical bound or guarantee of convergence to the global optimum for alternating sweeps across multidimensional tensor decompositions (d>2d > 2). TTOpt provides only a guarantee of monotonic non-decreasing (or non-increasing) improvement across sweep iterations, with no formal theoretical bound on the convergence rate or suboptimality gap in general multidimensional problems.

Coverage note — None was omitted. All primary contributions—including the TTOpt multidimensional algorithm, QTT formulation, dynamic mapping equation, maxvol bound, computational complexity, 10D benchmark results, high-dimensional scaling, RL policy quantization experiments, stabilization techniques, and theoretical limitations—are fully covered.

References

  1. 1.Salman Ahmadi-Asl, Cesar F Caiafa, Andrzej Cichocki, Anh Huy Phan, Toshihisa Tanaka, Ivan Oseledets, and Jun Wang. Cross tensor approximation methods for compression and dimensionality reduction. IEEE Access, 9:150809–150838, 2021.
  2. 2.Stéphane Alarie, Charles Audet, Aïmen E. Gheribi, Michael Kokkolaras, and Sébastien Le Digabel. Two decades of blackbox optimization applications. EURO Journal on Computational Optimization, 9:100011, 2021.
  3. 3.Kai Arulkumaran, Antoine Cully, and Julian Togelius. Alphastar: An evolutionary computation perspective. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’19, page 314–315, New York, NY, USA, 2019. Association for Computing Machinery.
  4. 4.Amir F. Atiya, Alexander G. Parlos, and Lester. Ingber. A reinforcement learning method based on adaptive simulated annealing. In 2003 46th Midwest Symposium on Circuits and Systems, volume 1, pages 121–124 Vol. 1, 2003.
  5. 5.Pauline Bennet, Carola Doerr, Antoine Moreau, Jeremy Rapin, Fabien Teytaud, and Olivier Teytaud. Nevergrad: Black-box optimization platform. SIGEVOlution, 14(1):8–15, apr 2021.
  6. 6.Rafał Biedrzycki. Handling bound constraints in CMA-ES: An experimental study. Swarm and Evolutionary Computation, 52:100627, 2020.
  7. 7.Alexey I. Boyko, Ivan V. Oseledets, and Gonzalo Ferrer. Tt-qi: Faster value iteration in tensor train format for stochastic optimal control. Computational Mathematics and Mathematical Physics, 61(5):836–846, 2021.
  8. 8.Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. ArXiv, abs/1606.01540, 2016.
  9. 9.Cesar F. Caiafa and Andrzej Cichocki. Generalizing the column–row matrix decomposition to multi-way arrays. Linear Algebra and its Applications, 433(3):557–573, 2010.
  10. 10.Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 970–978. PMLR, 10–15 Jul 2018.
  11. 11.Krzysztof M Choromanski, Aldo Pacchiano, Jack Parker-Holder, Yunhao Tang, and Vikas Sindhwani. From complexity to simplicity: Adaptive ES-active subspaces for blackbox optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  12. 12.Andrzej Cichocki and Shun-ichi Amari. Adaptive Blind Signal and Image Processing: Learning Algorithms and Applications. John Wiley & Sons, Inc., USA, 2002.
  13. 13.Andrzej Cichocki, Namgil Lee, Ivan Oseledets, Anh-Huy Phan, Qibin Zhao, and Danilo P. Mandic. Tensor networks for dimensionality reduction and large-scale optimization: Part 1 lowrank tensor decompositions. Foundations and Trends® in Machine Learning, 9(4-5):249–429, 2016.
  14. 14.Paul G. Constantine. Active subspaces - emerging ideas for dimension reduction in parameter studies. In SIAM spotlights, 2015.
  15. 15.Edoardo Conti, Vashisht Madhavan, Felipe Petroski Such, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. Improving exploration in evolution strategies for deep reinforcement learning via a population of novelty-seeking agents. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, page 5032–5043, Red Hook, NY, USA, 2018. Curran Associates Inc.
  16. 16.Rémi Coulom. Reinforcement Learning Using Neural Networks, with Applications to Motor Control. PhD thesis, Institut National Polytechnique de Grenoble, 2002.
  17. 17.Aleksandra Faust, Anthony G. Francis, and Dar Mehta. Evolving rewards to automate reinforcement learning. In 6th ICML Workshop on Automated Machine Learning, 2019.
  18. 18.Sergei A Goreinov, Ivan V Oseledets, Dimitry V Savostyanov, Eugene E Tyrtyshnikov, and Nikolay L Zamarashkin. How to find a good submatrix. In Matrix Methods: Theory, Algorithms And Applications: Dedicated to the Memory of Gene Golub, pages 247–256. World Scientific, 2010.
  19. 19.Alex Gorodetsky, Sertac Karaman, and Youssef Marzouk. High-dimensional stochastic optimal control using continuous tensor decompositions. The International Journal of Robotics Research, 37(2-3):340–377, 2018.
  20. 20.David Ha and Jürgen Schmidhuber. Recurrent world models facilitate policy evolution. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  21. 21.Wolfgang Hackbusch and Stefan Kühn. A new scheme for the tensor representation. Journal of Fourier analysis and applications, 15(5):706–722, 2009.
  22. 22.Nikolaus Hansen. The CMA Evolution Strategy: A Comparing Review, pages 75–102. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
  23. 23.Verena Heidrich-Meisner and Christian Igel. Neuroevolution strategies for episodic reinforcement learning. Journal of Algorithms, 64(4):152–168, 2009. Special Issue: Reinforcement Learning.
  24. 24.Daniel Hein, Alexander Hentschel, Thomas Runkler, and Steffen Udluft. Particle swarm optimization for generating interpretable fuzzy reinforcement learning policies. Engineering Applications of Artificial Intelligence, 65:87–98, 2017.
  25. 25.J. Michael Herrmann, Adam Price, and Thomas Joyce. 3. Ant colony optimization and reinforcement learning, pages 45–62. De Gruyter, 2020.
  26. 26.John H. Holland. Genetic algorithms. Scientific American, 267(1):66–73, 1992.
  27. 27.Sebastian Holtz, Thorsten Rohwedder, and Reinhold Schneider. The alternating linear scheme for tensor optimization in the tensor train format. SIAM Journal on Scientific Computing, 34(2):A683–A713, 2012.
  28. 28.Shauharda Khadka and Kagan Tumer. Evolution-guided policy gradient in reinforcement learning. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, page 1196–1208, Red Hook, NY, USA, 2018. Curran Associates Inc.
  29. 29.Boris N. Khoromskij. O(dlog n)-quantics approximation of n-d tensors in high-dimensional numerical modeling. Constructive Approximation, 34(2):257–280, Oct 2011.
  30. 30.Tamara G. Kolda, Robert Michael Lewis, and Virginia Torczon. Optimization by direct search: New perspectives on some classical and modern methods. SIAM Review, 45(3):385–482, 2003.
  31. 31.Oliver Kramer. A review of constraint-handling techniques for evolution strategies. Appl. Comp. Intell. Soft Comput., 2010, January 2010.
  32. 32.Joel Lehman, Jay Chen, Jeff Clune, and Kenneth O. Stanley. ES is more than just a traditional finite-difference approximator. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’18, page 450–457, New York, NY, USA, 2018. Association for Computing Machinery.
  33. 33.Tundong Liu, Liduan Li, Guifang Shao, Xiaomin Wu, and Meng Huang. A Novel Policy Gradient Algorithm with PSO-Based Parameter Exploration for Continuous Control. Eng. Appl. Artif. Intell., 90(C), apr 2020.
  34. 34.Anuj Mahajan, Mikayel Samvelyan, Lei Mao, Viktor Makoviychuk, Animesh Garg, Jean Kossaifi, Shimon Whiteson, Yuke Zhu, and Animashree Anandkumar. Tesseract: Tensorised actors for multi-agent reinforcement learning. In International Conference on Machine Learning (ICML), volume 139, pages 7301–7312, 2021.
  35. 35.Niru Maheswaranathan, Luke Metz, George Tucker, Dami Choi, and Jascha Sohl-Dickstein. Guided evolutionary strategies: augmenting random search with surrogate gradients. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4264–4273. PMLR, 09–15 Jun 2019.
  36. 36.Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive for reinforcement learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  37. 37.Erich Merrill, Alan Fern, Xiaoli Fern, and Nima Dolatnia. An empirical study of Bayesian optimization: Acquisition versus partition. Journal of Machine Learning Research, 22(4):1–25, 2021.
  38. 38.Laurent Meunier, Herilalaina Rakotoarison, Pak Kan Wong, Baptiste Roziere, Jérémy Rapin, Olivier Teytaud, Antoine Moreau, and Carola Doerr. Black-box optimization revisited: Improving algorithm selection wizards through massive benchmarking. IEEE Transactions on Evolutionary Computation, pages 1–1, 2021.
  39. 39.Aleksandr Mikhalev and Ivan V Oseledets. Rectangular maximum-volume submatrices and their applications. Linear Algebra and its Applications, 538:187–211, 2018.
  40. 40.Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529–533, Feb 2015.
  41. 41.John A. Nelder and Roger Mead. A simplex method for function minimization. Computer Journal, 7:308–313, 1965.
  42. 42.Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527–566, Apr 2017.
  43. 43.Barry D. Nichols. Continuous action-space reinforcement learning methods applied to the minimum-time swing-up of the acrobot. In 2015 IEEE International Conference on Systems, Man, and Cybernetics, pages 2084–2089, 2015.
  44. 44.Alexander Novikov, Maxim Rakhuba, and Ivan Oseledets. Automatic differentiation for Riemannian optimization on low-rank matrix and tensor-train manifolds. SIAM Journal on Scientific Computing, 44(2):A843–A869, 2022.
  45. 45.Ivan V Oseledets. Approximation of 2 d × 2 d matrices using tensor decomposition. SIAM J. Matrix Anal. Appl., 31(4):2130–2145, 2010.
  46. 46.Ivan V Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33(5):2295–2317, 2011.
  47. 47.Ivan V Oseledets and Eugene E Tyrtyshnikov. Breaking the curse of dimensionality, or how to use SVD in many dimensions. SIAM Journal on Scientific Computing, 31(5):3744–3759, 2009.
  48. 48.Ivan V Oseledets and Eugene E Tyrtyshnikov. TT-cross approximation for multidimensional arrays. Linear Algebra and its Applications, 432(1):70–88, 2010.
  49. 49.David Pfau, James S. Spencer, Alexander G. D. G. Matthews, and W. M. C. Foulkes. Ab initio solution of the many-electron schrödinger equation with deep neural networks. Phys. Rev. Research, 2:033429, Sep 2020.
  50. 50.Anh-Huy Phan, Andrzej Cichocki, André Uschmajew, Petr Tichavský, George Luta, and Danilo P. Mandic. Tensor networks for latent variable analysis: Novel algorithms for tensor train approximation. IEEE Transactions on Neural Networks and Learning Systems, 31(11):4622–4636, 2020.
  51. 51.Zhiwei Qin, Weichang Li, and Firdaus Janoos. Sparse reinforcement learning via convex optimization. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 424–432, Bejing, China, 22–24 Jun 2014. PMLR.
  52. 52.Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. ArXiv, abs/2102.12092, 2021.
  53. 53.Tim Salimans, Jonathan Ho, Xi Chen, and Ilya Sutskever. Evolution strategies as a scalable alternative to reinforcement learning. ArXiv, abs/1703.03864, 2017.
  54. 54.John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1889–1897, Lille, France, 07–09 Jul 2015. PMLR.
  55. 55.John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv, abs/1707.06347, 2017.
  56. 56.Hans-Paul Schwefel. Evolutionsstrategien für die numerische Optimierung, pages 123–176. Birkhäuser Basel, Basel, 1977.
  57. 57.Artur M. Schweidtmann and Alexander Mitsos. Deterministic global optimization with artificial neural networks embedded. Journal of Optimization Theory and Applications, 180(3):925–948, Oct 2018.
  58. 58.Alexandra Senderovich, Ekaterina Bulatova, Anton Obukhov, and Maxim Rakhuba. Towards practical control of singular values of convolutional layers. In Advances in Neural Information Processing Systems, 35, 2022.
  59. 59.Rainer Storn and Kenneth Price. Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4):341–359, Dec 1997.
  60. 60.Felipe Petroski Such, Vashisht Madhavan, Edoardo Conti, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. Deep neuroevolution: Genetic algorithms are a competitive alternative for training deep neural networks for reinforcement learning. ArXiv, abs/1712.06567, 2017.
  61. 61.Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026–5033, 2012.
  62. 62.Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander S. Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom L. Paine, Caglar Gulcehre, Ziyu Wang, Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782):350–354, Nov 2019.
  63. 63.Lev Vysotsky and Maxim Rakhuba. Tensor rank bounds and explicit qtt representations for the inverses of circulant matrices. arXiv preprint arXiv:2205.04335, 2022.
  64. 64.Pawel Wawrzynski. Learning to control a 6-degree-of-freedom walking robot. In EUROCON 2007 - The International Conference on "Computer as a Tool", pages 698–705, 2007.
  65. 65.Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. Journal of Machine Learning Research, 15(27):949–980, 2014.
  66. 66.Qibin Zhao, Masashi Sugiyama, Longhao Yuan, and Andrzej Cichocki. Learning efficient tensor representations with ring-structured networks. In ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8608–8612, 2019.

Citation

MLA
Sozykin, K., et al. “TTOpt: A Maximum Volume Quantized Tensor Train-based Optimization and Its Application to Reinforcement Learning”. Advances in Neural Information Processing Systems, vol. 35, 2022, pp. 26052–65, https://proceedings.neurips.cc/paper_files/paper/2022/file/a730abbcd6cf4a371ca9545db5922442-Paper-Conference.pdf.
APA
Sozykin, K., Chertkov, A., Schutski, R., Phan, A.-H., CICHOCKI, A. S., & Oseledets, I. (2022). TTOpt: A Maximum Volume Quantized Tensor Train-based Optimization and its Application to Reinforcement Learning. Advances in Neural Information Processing Systems, 35, 26052–26065. https://proceedings.neurips.cc/paper_files/paper/2022/file/a730abbcd6cf4a371ca9545db5922442-Paper-Conference.pdf
Chicago
Sozykin, K., A. Chertkov, R. Schutski, A.-H. Phan, A. S. CICHOCKI, and I. Oseledets. 2022. “TTOpt: A Maximum Volume Quantized Tensor Train-based Optimization and Its Application to Reinforcement Learning”. Advances in Neural Information Processing Systems 35: 26052–65. https://proceedings.neurips.cc/paper_files/paper/2022/file/a730abbcd6cf4a371ca9545db5922442-Paper-Conference.pdf.
Harvard
Sozykin, K. et al. (2022) “TTOpt: A Maximum Volume Quantized Tensor Train-based Optimization and its Application to Reinforcement Learning”, Advances in Neural Information Processing Systems. Curran Associates, Inc., pp. 26052–26065. Available at: https://proceedings.neurips.cc/paper_files/paper/2022/file/a730abbcd6cf4a371ca9545db5922442-Paper-Conference.pdf.
Vancouver
1. Sozykin K, Chertkov A, Schutski R, Phan A-H, CICHOCKI AS, Oseledets I (2022) TTOpt: A Maximum Volume Quantized Tensor Train-based Optimization and its Application to Reinforcement Learning. In: Advances in Neural Information Processing Systems. Curran Associates, Inc., pp 26052–26065

BibTeX

@inproceedings{sozykin2022ttopt,
  title = {TTOpt: A Maximum Volume Quantized Tensor Train-based Optimization and its Application to Reinforcement Learning},
  author = {Sozykin, Konstantin and Chertkov, Andrei and Schutski, Roman and Phan, Anh-Huy and CICHOCKI, Andrzej S and Oseledets, Ivan},
  year = {2022},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {35},
  pages = {26052-26065},
  url = {https://proceedings.neurips.cc/paper_files/paper/2022/file/a730abbcd6cf4a371ca9545db5922442-Paper-Conference.pdf}
}
Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: Authors