Pith. sign in

REVIEW 4 major objections 7 minor 51 references

MatRL: Provably Generalizable Iterative Algorithm Discovery via Monte-Carlo Tree Search

T0 review · 4 major / 7 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read MatRL uses Monte-Carlo tree search to automatically discover hybrid iterative algorithms for matrix functions, tailored to a matrix distribution and hardware, with a proof that the discovered algorithms generalize to large matrices from…

desk verdict MatRL is a genuinely useful search framework for composing classical matrix iterations, but the 'provable' generalization claim overshoots its own theorem because the sign experiments violate the continuity assumption. read the letter →

arxiv 2507.03833 v2 pith:X2MWYWNF submitted 2025-07-04 cs.LG

Sungyoon Kim , Rajat Vadiraj Dwaraknath , Longling geng , Mert Pilanci This is my paper
classification cs.LG MSC 65F6060B2068T20
keywords monte-carlotreesearchmatrixfunctionsiterativealgorithmdiscoveryreinforcementlearningrandomtheorygeneralizationsignsquareroot
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

MatRL treats the design of an iterative matrix-function algorithm as a sequential decision problem: at each step, choose which classical iteration (Newton, Newton-Schulz, Denman-Beavers, Visser, etc.) to apply and with what step sizes. Monte-Carlo tree search plans this hybrid sequence to minimize wall-clock time subject to an error tolerance, using only the eigenvalue spectrum as the state. The paper's central claim is that the search automatically finds algorithms faster than existing baselines and even than torch.linalg.eigh for the matrix sign function, while adapting to matrix distribution, size, precision, and hardware. It further claims a formal generalization guarantee: under assumptions of a common limiting eigenvalue spectrum with interval support and continuity of the eigenvalue transformations, the per-step loss on a large training-distribution matrix differs by less than $\epsilon$ from the loss on a large matrix from any distribution with the same limiting spectrum.

What carries the argument

The load-bearing machinery is the eigenvalue-spectrum parametrization of the search environment. Since every iteration and the loss are congruence-invariant and diagonal-preserving, the state $(X,Y)$ can be replaced by the diagonal matrices of eigenvalues relative to the eigenbasis of $A$, and both the transition and the loss depend only on the spectrum; the paper proves this as Proposition A.2. This reduction makes the random matrix theory argument possible: the empirical spectral measure of a large random matrix is close to its limiting measure, so for any fixed scalar eigenvalue transformation $f^\ast_k$, the per-step loss is close for two large matrices with the same limiting spectrum, yielding Proposition 1. The search itself is carried out by MCTS with UCT for node selection and progressive widening to handle the continuous step-size parameters, with rollout policies drawn from known good baselines and a coupling flag to manage coupled iterations such as Denman-Beavers.

What would settle it

Take a MatRL-discovered matrix-sign algorithm (e.g., the float GPU version) and evaluate it on two sequences of symmetric matrices with the same limiting spectral measure: one with eigenvalues capped at magnitude $10^{-3}$ as in the paper, and one with eigenvalues that decay toward zero (e.g., $1/k$). If the per-step loss difference between the two sequences does not go below $\epsilon$ for large matrix size, or if the uncapped sequence diverges, the interval-support and continuity assumptions of Proposition 1 are the reason, and the guarantee does not hold where claimed.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that algorithm design for matrix functions can be reduced to planning over scalar eigenvalue transformations, because all considered iterations are congruence-invariant and diagonal-preserving, so the full matrix state can be replaced by its spectrum. Monte-Carlo tree search with progressive widening then selects a sequence of iteration types and continuous parameters to minimize total wall-clock time subject to a loss tolerance. The key theoretical result, Proposition 1, states that if two random matrix ensembles have empirical spectral measures converging weakly to the same limit whose support is an interval, and if the target function, the discovered eigenvalue transformations, and the loss are continuous in a neighborhood of that interval, then for sufficiently large matrices the per-step loss on a sample from one ensemble is within $\epsilon$ of the per-step loss on a sample from the other, with high probability. Experiments show the resulting hybrid algorithms outperform a suite of classical baselines, beat torch.linalg for the matrix sign, and generalize across ensembles with the same limiting spectrum (e.g., Wishart to Wishart with uniform entries).

Load-bearing premise

The generalization proof assumes the eigenvalue distribution of the matrices eventually fills one unbroken interval and that every discovered step acts continuously on eigenvalues across that interval; the paper's own test distributions cap small eigenvalues at $10^{-3}$ and use Newton-style steps that divide by eigenvalues, so those conditions do not formally hold in the experiments.

Editorial extensions

If this is right

  • MatRL finds matrix-sign algorithms that are strictly faster in wall-clock time than torch.linalg.eigh, and square-root algorithms that reach comparable error in less time, so approximate matrix functions become cheaper for applications such as ZCA whitening.
  • The discovered algorithms generalize to new matrix distributions with the same limiting eigenvalue spectrum, so a single search result can be reused across ensembles, e.g., Wishart with Gaussian entries to Wishart with uniform entries.
  • Optimal iterations depend on the computing environment: double precision and CPU favor Newton steps, while float precision and GPU favor a mix of Newton-Schulz and Newton steps, so the search automatically adapts to hardware and precision.
  • On CIFAR-10 empirical covariance matrices, the discovered algorithm reaches machine precision roughly 1.8x faster than the best baseline, demonstrating practical impact for whitening pipelines.
  • MatRL can handle coupled iterations (Denman-Beavers, Newton-Schulz variant) by tracking a coupling flag and inserting coupling steps, so the search space includes both coupled and uncoupled iteration families.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: The formal guarantee's interval-support and continuity assumptions are not verified for the paper's own experimental ensembles—the Uniform and Quartic-Hessian distributions cap eigenvalues at $10^{-3}$ in magnitude, and Newton-style sign steps divide by eigenvalues—so the experiments are not covered by Proposition 1; a natural follow-up is a theorem for compact support with piecewise-co
  • Inference: Because the search uses only the spectrum as state, numerical stability (e.g., conditioning of the eigenbasis or round-off in matrix products) is invisible to the planner, which the authors note as the likely cause of diverging runs at test time; adding an entrywise or conditioning penalty to the reward could produce more robust algorithms.
  • Inference: The pattern observed in discovered square-root algorithms—cheap fixed-point Visser steps to obtain a good initialization followed by coupled Newton-Schulz steps—suggests a design heuristic that could be used as a rollout prior or to reduce the search space in new settings.
  • Inference: The framework is stated for symmetric matrices; extending the state parametrization to singular values, as the authors suggest, would open the same machinery to nonsymmetric and rectangular problems.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 7 minor

Summary. The paper proposes MatRL, a Monte-Carlo tree search framework that automatically discovers iterative algorithms for computing matrix functions such as sign, square root, inverse, and 1/3-root. The state of the search is the eigenvalue spectrum rather than the full matrices, which makes the search space tractable; actions are choices of iteration type and continuous coefficients; rewards are negative wall-clock time; and termination is controlled by a loss threshold. The authors report that the discovered algorithms outperform classical baselines in several settings and, for matrix sign, beat torch.linalg.eigh in wall-clock time at a given accuracy. The main formal contribution is Proposition 1 (Appendix A.4), which states that if two random matrix distributions have a common limiting empirical spectral measure with interval support, and if the target function, the discovered eigenvalue transformations, and the loss are continuous near that support, then the per-step empirical loss of a fixed discovered algorithm is close for large matrix sizes across the two distributions. The appendix contains the proof and detailed experimental settings, and the main text presents a generalization experiment transferring an algorithm learned on Wishart matrices to a different entry distribution with the same limiting spectrum.

Significance. MatRL addresses a real problem: iterative matrix function algorithms depend heavily on distribution, size, precision, and hardware, and hand-tuning them is labor-intensive. The spectral-state reduction is a clean and useful design choice, and the demonstration that different hybrid algorithms are discovered for different precisions and compute environments is compelling evidence of adaptivity. The formal generalization result is valuable in principle, and the Wishart-to-WishartUnif experiment is a genuinely out-of-sample transfer. However, as written the paper overclaims the reach of the theorem: the continuity assumptions exclude the matrix sign and indefinite-spectrum experiments that contain the headline speedups, and the empirical comparisons rely on best-of-five selection without showing run-to-run variability. The central idea is sound, but the scope of the claims needs to be narrowed or the theorem needs to be extended.

major comments (4)
  1. [§4, Proposition 1 (Appendix A, Proposition A.4)] The continuity hypothesis that f, f*_k, and L be continuous on [a-ε0, b+ε0] is violated by the paper's own sign and inverse experiments. For matrix sign, the target f(x)=sign(x) is discontinuous at 0, and the discovered algorithms (e.g., Algorithm 3 steps 1-2 and Algorithm 4) apply scalar maps f*_k(x)=0.5(ax+1/(ax)) with a pole at 0. Since the limiting spectra of the Uniform[-1,1] and Quartic-Hessian ensembles contain 0, there is no interval around the limiting support on which the required continuity holds. Consequently Proposition 1 cannot justify the word 'provably' for the sign results in Figures 1, 4, 7-9, including the claim of beating torch.linalg.eigh. The only experiment that clearly satisfies the hypotheses is the Wishart square-root transfer in Figure 2. The authors should either restrict the generalization theorem and all related claims to cases where the continuity assumptions hold (e.g., positive-definite targets with polynomial or Newton-Schulz iterations), or extend the theorem to functions with finite discontinuities by assuming the limiting measure assigns zero mass to a neighborhood of the discontinuities and bounding the contribution of the remaining eigenvalues.
  2. [Appendix A, proof of Proposition A.4] The choice ε' = max{ε0, ε/(8A)} makes the proof of the bound |∫ L̃ dμ_m − ∫ L(f,f_k) dμ_m| ≤ 2ε'A ≤ ε/4 incorrect. If ε' = ε0, the final inequality does not follow unless ε0 ≤ ε/(8A); if ε' > ε0, the extension L̃ is used on points outside [a-ε0, b+ε0], where no continuity or boundedness of L was assumed. The proof also needs ε' ≤ ε0 so that the support-concentration assumption (iii) applies inside the controlled interval. The correct choice is ε' = min{ε0, ε/(8A)}, with the case A=0 handled separately. This is a local fix, but it is necessary for the proof to establish the stated proposition.
  3. [§5.1 and Appendix C.2] The reported empirical speedups are selected as the best of five MCTS runs ('We repeated the experiments five times and picked the best algorithm' in Appendix C.2), and Figures 1, 4, 7-9 show single curves without error bars or run-to-run variability. Because 'MatRL is strictly better than torch.linalg.eigh' is a headline empirical claim, best-of-five selection is a selection bias that can make a stochastic discovery method look better than its typical performance. The paper should report the full distribution of runs (e.g., median and interquartile range over a fixed number of independent MCTS budgets) and state clearly how many seeds were used for both discovery and evaluation, and how baseline timings were averaged.
  4. [§5.2] The generalization experiment tests only the square-root algorithm learned on Wishart matrices and transferred to WishartUnif (Figure 2). This is a good test but it is the only case that satisfies the continuity assumptions of Proposition 1. To support the general claim in the abstract and introduction that 'learned algorithms provably generalize', the paper should either add analogous transfer experiments for sign and inverse under settings where the theorem applies, or explicitly state in the abstract and introduction that the formal guarantee is restricted to cases where the target and the discovered eigenvalue maps are continuous on the limiting spectral support.
minor comments (7)
  1. [§3.2, Definition 1] The congruence relation f(QX_1Q^T, ..., QX_kQ^T) = Q f(X_1, ..., X_k) Q^T is undefined when the input dimension n and output dimension m differ because Q is an n×n orthogonal matrix. The definition should either set m=n or state the convention for rectangular outputs.
  2. [Eq. (3) and Table 8] The parameter notation is inconsistent between the main text (a11, a12 in Eq. (3) and a21, a22) and the parameterized-action table (a_k, b_k). Use a single naming convention throughout to improve reproducibility.
  3. [Algorithm 2] Algorithm 2 contains the explicit inverse computation Y_6 = X_6 A^{-1}. The paper should clarify whether the reported wall-clock time includes this inversion and why this is consistent with the stated goal of discovering iterations that avoid direct matrix inverses.
  4. [Appendix B.2] The statement that the 'NewtonVariant' iteration X_{k+1}=2X_k(I+X_k^2)^{-1} is the inverse of SignNewton is not correct for the scalar map g(x)=0.5(x+x^{-1}); the statement should be corrected or qualified.
  5. [Conclusion and general presentation] There are several typos ('singuar', 'neceessary', 'tendancy'), and Proposition 1 is labelled A.4 in the appendix but 1 in the main text; these should be harmonized.
  6. [Figure 2] Figure 2a would be more informative if it overlaid the theoretical Marchenko-Pastur density on the empirical histograms and stated the matrix size and number of samples used for the histograms.
  7. [Table 3] Table 3 reports means and standard deviations, but it is not stated how many independent CIFAR-10 batches were used or whether the MCTS discovery was repeated across seeds. This information should be added to Appendix C.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: MatRL's generalization theorem is a genuine out-of-sample statement; the sign-experiment assumption gap is a scope issue, not a circular reduction.

full rationale

Proposition 1 is not equivalent to its inputs. It takes the fixed scalar eigenvalue maps produced by MCTS and proves, via weak convergence of empirical spectral measures and a bounded-continuous extension argument, that per-step losses on two large matrices with a common limiting spectrum are close. The proof is self-contained and standard; it does not presuppose the conclusion, and the WishartUnif test in Section 5.2 uses a distribution not seen during fitting, so the reported generalization is a real out-of-sample prediction. Proposition A.2's spectrum-state reduction is an induction from congruence invariance, not a restatement of the goal. The paper has no load-bearing self-citations and does not invoke any author-origin uniqueness theorem. The one substantive gap is that Proposition 1's continuity hypothesis is not verified for the sign algorithms (Algorithms 3-4, 8-13) whose first steps apply (aX)^{-1}, a map with a pole at 0 lying in the Uniform/Quartic limiting spectrum; this means the 'provable' claim does not cover those headline experiments. That is a correctness and scope concern, not a circular reduction, and the authors acknowledge related numerical-instability limitations in Section 6.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The ledger lists the fitted coefficients and hand-chosen constants the experimental claims depend on, plus the unverified assumptions that the generalization theorem requires. Note that the theorem's assumptions (i)-(iii) are stated as axioms in Proposition 1 and are not proved for the specific ensembles; the continuity of f*_k is not checked. No new physical or mathematical entities are postulated.

free parameters (4)
  • Discovered algorithm coefficients (a_i, b_i) for each task = e.g., Algorithm 2: a=[2.092,1.891,3.714,1.063,0.920,1], b=[1.983,0.586,2.385,0.452,0.900,0.946] for Wishart sqrt on GPU
    These coefficients are tuned by the MCTS search on the training distribution; the central experimental claims (speedups, generalization) depend on these specific fitted values.
  • Eigenvalue stabilization cap = 1e-3
    Uniform and Quartic-Hessian distributions cap eigenvalues with absolute value < 1e-3 to 1e-3 (Appendix C.4). This choice changes the support of the distribution and is needed to avoid division by zero, but it breaks the interval-support assumption of Proposition 1.
  • Stability shift epsilon_stb = 1e-3
    Added to Wishart and CIFAR-10 covariance matrices for numerical stability; shifts the spectrum and affects the loss curves.
  • MCTS hyperparameters (C_pw, alpha_pw, C_ucb, E) = C_pw=2, alpha_pw=0.3, C_ucb=5, E=5 (Appendix C.3)
    Chosen by hand; the paper does not study sensitivity of the results to these values, so they are free parameters of the search procedure.
assumptions (5)
  • domain assumption Empirical spectral measures of the random matrix ensembles converge weakly to a common limiting distribution with probability 1 (assumption (i) of Proposition 1).
    Used in the proof of Proposition 1 and in Section 5.2 to justify generalization for Wishart vs WishartUnif via Marchenko-Pastur. Standard random matrix theory results, but not proven in the paper.
  • domain assumption Support of the limiting spectrum is an interval [a,b] and eigenvalue supports converge to [a-epsilon,b+epsilon] with high probability (assumptions (ii) and (iii) of Proposition 1).
    Assumed in Proposition 1. Not verified for the capped Uniform and Quartic-Hessian ensembles used in experiments, whose supports are not intervals.
  • ad hoc to paper The discovered algorithm's eigenvalue transformations f*_k and the loss function are continuous on [a-epsilon_0,b+epsilon_0].
    Assumed in Proposition 1. Iterations like sign-Newton involve division by eigenvalues and are discontinuous at 0; the paper does not check this for the found algorithms.
  • domain assumption The reward (negative wall-clock time) is deterministic and independent of the matrix values.
    Used implicitly when transferring loss generalization to time-based optimality; the theorem only covers the loss curve, while the search objective minimizes time. The paper does not formally connect the two.
  • domain assumption Matrix iterations and loss functions are congruence invariant and diagonal preserving (Definition 1).
    Proven for rational functions in Proposition A.3; needed for the spectrum-only state representation in Section 3.2. This is a design restriction of the framework rather than an unproved external fact.

how reviews work

0 comments
Cite this review

Pith. "Pith review of MatRL: Provably Generalizable Iterative Algorithm Discovery via Monte-Carlo Tree Search." pith.science (2026). https://pith.science/paper/X2MWYWNF

@misc{pith2026250703833,
  author       = {Pith},
  title        = {Pith review of: MatRL: Provably Generalizable Iterative Algorithm Discovery via Monte-Carlo Tree Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X2MWYWNF}},
  note         = {Machine review of arXiv:2507.03833}
}
read the original abstract

Iterative methods for computing matrix functions have been extensively studied and their convergence speed can be significantly improved with the right tuning of parameters and by mixing different iteration types. Handtuning the design options for optimal performance can be cumbersome, especially in modern computing environments: numerous different classical iterations and their variants exist, each with non-trivial per-step cost and tuning parameters. To this end, we propose MatRL -- a reinforcement learning based framework that automatically discovers iterative algorithms for computing matrix functions. The key idea is to treat algorithm design as a sequential decision-making process. Monte-Carlo tree search is then used to plan a hybrid sequence of matrix iterations and step sizes, tailored to a specific input matrix distribution and computing environment. Moreover, we also show that the learned algorithms provably generalize to sufficiently large matrices drawn from the same distribution. Finally, we corroborate our theoretical results with numerical experiments demonstrating that MatRL produces algorithms that outperform various baselines in the literature.

Figures

Figures reproduced from arXiv: 2507.03833 by the authors.

Figure 1
Figure 1. Time versus loss curve for matrix sign and square root. Each iterative algorithms are plotted [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. How generalization guarantee in Proposition 1 works. Here we have two different random [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Computing matrix inverse with NewtonSchulz and variants [PITH_FULL_IMAGE:figures/full_fig_p024_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Computing matrix sign with NewtonSchulz and variants [PITH_FULL_IMAGE:figures/full_fig_p024_4.png]
Figure 5
Figure 5. Figure 5: Computing matrix square root with NewtonSchulz and variants [PITH_FULL_IMAGE:figures/full_fig_p024_5.png]
Figure 6
Figure 6. Figure 6: Examples of matrix distributions: structural or spectral views. [PITH_FULL_IMAGE:figures/full_fig_p025_6.png]
Figure 7
Figure 7. Figure 7: Computing matrix sign for different matrix sizes [PITH_FULL_IMAGE:figures/full_fig_p025_7.png]
Figure 8
Figure 8. Figure 8: Computing matrix sign for different precision [PITH_FULL_IMAGE:figures/full_fig_p027_8.png]
Figure 9
Figure 9. Figure 9: Computing matrix sign on different machines [PITH_FULL_IMAGE:figures/full_fig_p027_9.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

51 extracted references · 40 canonical work pages

  1. [1]

    Dion: A communication-efficient optimizer for large models

    Kwangjun Ahn and Byron Xu. Dion: A communication-efficient optimizer for large models. arXiv preprint arXiv:2504.05295, 2025

    arXiv 2025

  2. [2]

    independent components

    Anthony J Bell and Terrence J Sejnowski. The “independent components” of natural scenes are edge filters.Vision research, 37(23):3327–3338, 1997

    work page 1997

  3. [3]

    A survey of monte carlo tree search methods.IEEE Transactions on Computational Intelligence and AI in games, 4(1):1–43, 2012

    Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods.IEEE Transactions on Computational Intelligence and AI in games, 4(1):1–43, 2012

    2012

  4. [4]

    Solving the algebraic riccati equation with the matrix sign function.Linear Algebra and its Applications, 85:267–279, 1987

    Ralph Byers. Solving the algebraic riccati equation with the matrix sign function.Linear Algebra and its Applications, 85:267–279, 1987

    work page 1987

  5. [5]

    A new scaling for newton’s iteration for the polar decomposition and its backward stability.SIAM Journal on Matrix Analysis and Applications, 30(2):822–843, 2008

    Ralph Byers and Hongguo Xu. A new scaling for newton’s iteration for the polar decomposition and its backward stability.SIAM Journal on Matrix Analysis and Applications, 30(2):822–843, 2008

    work page 2008

  6. [6]

    Monte-carlo tree search in production management problems

    Guillaume Chaslot, Steven De Jong, Jahn-Takeshi Saito, and Jos Uiterwijk. Monte-carlo tree search in production management problems. InProceedings of the 18th BeNeLux Conference on Artificial Intelligence, volume 9198, 2006

    work page 2006

  7. [7]

    Progressive strategies for monte-carlo tree search.New Mathematics and Natural Computation, 4(03):343–357, 2008

    Guillaume M Jb Chaslot, Mark HM Winands, H Jaap van den Herik, Jos WHM Uiterwijk, and Bruno Bouzy. Progressive strategies for monte-carlo tree search.New Mathematics and Natural Computation, 4(03):343–357, 2008

    work page 2008

  8. [8]

    Jie Chen and Edmond Chow. A newton-schulz variant for improving the initial convergence in matrix sign computation.Preprint ANL/MCS-P5059-0114, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, 60439, 2014

    work page 2014

Show all 51 references
  1. [9]

    Continuous upper confidence trees

    Adrien Couëtoux, Jean-Baptiste Hoock, Nataliya Sokolovska, Olivier Teytaud, and Nicolas Bonnard. Continuous upper confidence trees. InLearning and Intelligent Optimization: 5th International Conference, LION 5, Rome, Italy, January 17-21, 2011. Selected Papers 5, pages 433–445...

    2011

  2. [10]

    Convolutional neural networks on graphs with fast localized spectral filtering.Advances in neural information processing systems, 29, 2016

    Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering.Advances in neural information processing systems, 29, 2016

    2016

  3. [11]

    The matrix sign function and computations in systems.Applied mathematics and Computation, 2(1):63–94, 1976

    Eugene D Denman and Alex N Beavers Jr. The matrix sign function and computations in systems.Applied mathematics and Computation, 2(1):63–94, 1976

    1976

  4. [12]

    An introduction to mathematical optimal control theory version 0.2.Lecture notes available at http://math

    Lawrence C Evans. An introduction to mathematical optimal control theory version 0.2.Lecture notes available at http://math. berkeley. edu/evans/control. course. pdf, 1983

    1983

  5. [13]

    Discovering faster matrix multiplication algorithms with reinforcement learning.Nature, 610(7930):47–53, 2022

    Alhussein Fawzi, Giacomo De Palma, Ankit Goyal, Gary Becigneul, Mohammad Barekatain, Sam Bond-Taylor, et al. Discovering faster matrix multiplication algorithms with reinforcement learning.Nature, 610(7930):47–53, 2022

    2022

  6. [14]

    Zolotarev iterations for the matrix square root.SIAM journal on matrix analysis and applications, 40(2):696–719, 2019

    Evan S Gawlik. Zolotarev iterations for the matrix square root.SIAM journal on matrix analysis and applications, 40(2):696–719, 2019

    2019

  7. [15]

    On newton’s method and halley’s method for the principal pth root of a matrix

    Chun-Hua Guo. On newton’s method and halley’s method for the principal pth root of a matrix. Linear algebra and its applications, 432(8):1905–1922, 2010

    1905

  8. [16]

    Shampoo: Preconditioned stochastic tensor optimization

    Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimization. InInternational Conference on Machine Learning, pages 1842–1850. PMLR, 2018

    2018

  9. [17]

    Stable iterations for the matrix square root.Numerical Algorithms, 15:227–242, 1997

    Nicholas J Higham. Stable iterations for the matrix square root.Numerical Algorithms, 15:227–242, 1997

    1997

  10. [18]

    SIAM, 2008

    Nicholas J Higham.Functions of matrices: theory and computation. SIAM, 2008. 11

    2008

  11. [19]

    Fast polar decomposition of an arbitrary matrix

    Nicholas J Higham and Robert S Schreiber. Fast polar decomposition of an arbitrary matrix. SIAM Journal on Scientific and Statistical Computing, 11(4):648–655, 1990

    1990

  12. [20]

    Intelligent agents for the game of go.IEEE Computational Intelligence Magazine, 5(4):28–42, 2010

    Jean-Baptiste Hoock, Chang-Shing Lee, Arpad Rimmel, Fabien Teytaud, Mei-Hui Wang, and Oliver Teytaud. Intelligent agents for the game of go.IEEE Computational Intelligence Magazine, 5(4):28–42, 2010

    2010

  13. [21]

    A faster, more stable method for computing the pth roots of positive definite matrices.Linear Algebra and Its Applications, 26:139–163, 1979

    WD Hoskins and DJ Walton. A faster, more stable method for computing the pth roots of positive definite matrices.Linear Algebra and Its Applications, 26:139–163, 1979

    1979

  14. [22]

    A note on computing the matrix square root.Calcolo, 40(4):273–283, 2003

    Bruno Iannazzo. A note on computing the matrix square root.Calcolo, 40(4):273–283, 2003

    2003

  15. [23]

    On the newton method for the matrix p th root.SIAM journal on matrix analysis and applications, 28(2):503–523, 2006

    Bruno Iannazzo. On the newton method for the matrix p th root.SIAM journal on matrix analysis and applications, 28(2):503–523, 2006

    2006

  16. [24]

    Muon: An optimizer for hidden layers in neural networks, 2024

    Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks, 2024

    2024

  17. [25]

    Deep generative symbolic regression with monte-carlo-tree-search

    Pierre-Alexandre Kamienny, Guillaume Lample, Sylvain Lamprier, and Marco Virgolin. Deep generative symbolic regression with monte-carlo-tree-search. InInternational Conference on Machine Learning, pages 15655–15668. PMLR, 2023

    2023

  18. [26]

    Learning to relax: Setting solver parameters across a sequence of linear system instances

    Mikhail Khodak, Edmond Chow, Maria-Florina Balcan, and Ameet Talwalkar. Learning to relax: Setting solver parameters across a sequence of linear system instances. InProceedings of the International Conference on Learning Representations (ICLR), 2024

    2024

  19. [27]

    Bandit based monte-carlo planning

    Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. InEuropean conference on machine learning, pages 282–293. Springer, 2006

    2006

  20. [28]

    Learning multiple layers of features from tiny images

    Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009

    2009

  21. [29]

    Chebyshev- type methods and preconditioning techniques.Applied Mathematics and Computation, 218(2):260–270, 2011

    Hou-Biao Li, Ting-Zhu Huang, Yong Zhang, Xing-Ping Liu, and Tong-Xiang Gu. Chebyshev- type methods and preconditioning techniques.Applied Mathematics and Computation, 218(2):260–270, 2011

    2011

  22. [30]

    Learning to optimize neural nets.arXiv preprint arXiv:1703.00441, 2017

    Ke Li and Jitendra Malik. Learning to optimize neural nets.arXiv preprint arXiv:1703.00441, 2017

    2017 arXiv

  23. [31]

    An effec- tive mcts-based algorithm for minimizing makespan in dynamic flexible job shop scheduling problem.Computers & Industrial Engineering, 155:107211, 2021

    Kexin Li, Qianwang Deng, Like Zhang, Qing Fan, Guiliang Gong, and Sun Ding. An effec- tive mcts-based algorithm for minimizing makespan in dynamic flexible job shop scheduling problem.Computers & Industrial Engineering, 155:107211, 2021

    2021

  24. [32]

    Towards faster training of global covariance pooling networks by iterative matrix square root normalization

    Peihua Li, Jiangtao Xie, Qilong Wang, and Zilin Gao. Towards faster training of global covariance pooling networks by iterative matrix square root normalization. InProceedings of the IEEE conference on computer vision and pattern recognition, pages 947–955, 2018

    2018

  25. [33]

    Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems

    Lin Lin, Jianfeng Lu, Lexing Ying, Roberto Car, and Weinan E. Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems. 2009

    2009

  26. [34]

    Faster sorting algorithms discovered using deep reinforcement learning.Nature, 618(7964):257–263, 2023

    Daniel J Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent, Shariq Iqbal, Jean-Baptiste Lespiau, Alex Ahern, et al. Faster sorting algorithms discovered using deep reinforcement learning.Nature, 618(7964):257–263, 2023

    2023

  27. [35]

    A fractional graph laplacian approach to oversmoothing.Advances in Neural Information Processing Systems, 36:13022– 13063, 2023

    Sohir Maskey, Raffaele Paolino, Aras Bacho, and Gitta Kutyniok. A fractional graph laplacian approach to oversmoothing.Advances in Neural Information Processing Systems, 36:13022– 13063, 2023

    2023

  28. [36]

    Evaluation of simulation strategy on single-player monte-carlo tree search and its discussion for a practical scheduling problem

    Shimpei Matsumoto, Noriaki Hirosue, Kyohei Itonaga, Kazuma Yokoo, and Hisatomo Futahashi. Evaluation of simulation strategy on single-player monte-carlo tree search and its discussion for a practical scheduling problem. InWorld Congress on Engineering 2012. July 4-6, 2012. Lon...

    2012

  29. [37]

    Optimizing halley’s iteration for computing the matrix polar decomposition.SIAM Journal on Matrix Analysis and Applications, 31(5):2700– 2720, 2010

    Yuji Nakatsukasa, Zhaojun Bai, and François Gygi. Optimizing halley’s iteration for computing the matrix polar decomposition.SIAM Journal on Matrix Analysis and Applications, 31(5):2700– 2720, 2010

    2010

  30. [38]

    Computing fundamental matrix decompositions accurately via the matrix sign function in two iterations: The power of zolotarev’s functions

    Yuji Nakatsukasa and Roland W Freund. Computing fundamental matrix decompositions accurately via the matrix sign function in two iterations: The power of zolotarev’s functions. siam REVIEW, 58(3):461–493, 2016

    2016

  31. [39]

    An improved newton iteration for the generalized inverse of a matrix, with applications.SIAM Journal on Scientific and Statistical Computing, 12(5):1109– 1130, 1991

    Victor Pan and Robert Schreiber. An improved newton iteration for the generalized inverse of a matrix, with applications.SIAM Journal on Scientific and Statistical Computing, 12(5):1109– 1130, 1991

    1991

  32. [40]

    The edge of orthogonality: A simple view of what makes byol tick

    Pierre Harvey Richemond, Allison Tam, Yunhao Tang, Florian Strub, Bilal Piot, and Felix Hill. The edge of orthogonality: A simple view of what makes byol tick. InInternational Conference on Machine Learning, pages 29063–29081. PMLR, 2023

    2023

  33. [41]

    Optimization of the nested monte-carlo algorithm on the traveling salesman problem with time windows

    Arpad Rimmel, Fabien Teytaud, and Tristan Cazenave. Optimization of the nested monte-carlo algorithm on the traveling salesman problem with time windows. InApplications of Evolutionary Computation: EvoApplications 2011: EvoCOMNET, EvoFIN, EvoHOT, EvoMUSART, EvoSTIM, and EvoTRA...

    2011

  34. [42]

    Guiding combinatorial optimization with uct

    Ashish Sabharwal, Horst Samulowitz, and Chandra Reddy. Guiding combinatorial optimization with uct. InIntegration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems: 9th International Conference, CPAIOR 2012, Nantes, France, May 28–June1, 2...

    2012

  35. [43]

    Iterative berechung der reziproken matrix.ZAMM-Journal of Applied Math- ematics and Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik, 13(1):57–59, 1933

    Günther Schulz. Iterative berechung der reziproken matrix.ZAMM-Journal of Applied Math- ematics and Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik, 13(1):57–59, 1933

    1933

  36. [44]

    Mastering the game of go without human knowledge.nature, 550(7676):354–359, 2017

    David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge.nature, 550(7676):354–359, 2017

    2017

  37. [45]

    Tactical planning using mcts in the game of starcraft.Master’s thesis, Maastricht University, 2014

    Dennis Soemers. Tactical planning using mcts in the game of starcraft.Master’s thesis, Maastricht University, 2014

    2014

  38. [46]

    Yue Song, Nicu Sebe, and Wei Wang. Why approximate matrix square root outperforms accurate svd in global covariance pooling? InProceedings of the IEEE/CVF International Conference on Computer Vision, pages 1115–1123, 2021

    2021

  39. [47]

    Fast differentiable matrix square root.arXiv preprint arXiv:2201.08663, 2022

    Yue Song, Nicu Sebe, and Wei Wang. Fast differentiable matrix square root.arXiv preprint arXiv:2201.08663, 2022

    2022 arXiv

  40. [48]

    A monte-carlo aixi approximation.Journal of Artificial Intelligence Research, 40:95–142, 2011

    Joel Veness, Kee Siong Ng, Marcus Hutter, William Uther, and David Silver. A monte-carlo aixi approximation.Journal of Artificial Intelligence Research, 40:95–142, 2011

    2011

  41. [49]

    Deep cnns meet global covariance pooling: Better representation and generalization.IEEE transactions on pattern analysis and machine intelligence, 43(8):2582–2597, 2020

    Qilong Wang, Jiangtao Xie, Wangmeng Zuo, Lei Zhang, and Peihua Li. Deep cnns meet global covariance pooling: Better representation and generalization.IEEE transactions on pattern analysis and machine intelligence, 43(8):2582–2597, 2020

    2020

  42. [50]

    On fractional powers of a matrix.Journal of the American Statistical Association, 62(319):1018–1021, 1967

    Frederick V Waugh and Martin E Abel. On fractional powers of a matrix.Journal of the American Statistical Association, 62(319):1018–1021, 1967. 13 A Technical Proofs We first show that the environment can be parametrized by the spectrum. Proposition A.2.Let {fk(X, Y, A)}m k=1 ...

    1967

  43. [51]

    difference

    The second equality comes from congruent invariance, and the third equality follows from diagonal preservence. Hence, Xt+1 =U D′ 1U T and Xt+1 and A are similar, Yt+1 =U D′ 2U T andY t+1 andAare also similar. ii) From the proof of i) we know that f(D 1, D2, DA) = (D′ 1, D′ 2),...

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.