RMNP: Row-Momentum Normalized Preconditioning for Scalable Matrix-Based Optimization

• URL: http://arxiv.org/abs/2603.20527v1
• Date: Fri, 20 Mar 2026 21:55:28 GMT
• Title: RMNP: Row-Momentum Normalized Preconditioning for Scalable Matrix-Based Optimization
• Abstract summary: We introduce textscMuon (Row Momentum Normalized Preconditioning) an operation that replaces Newton-Schulz with a simple row-wise $ell$ normalization.<n>This substitution reduces the complexity from $mathcalO(mncmin(mn))$ to $mathcalO(mn) for an $mtimes n$ weight matrix while maintaining comparable optimization performance.
• Score: 28.107175154772264
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Preconditioned adaptive methods have gained significant attention for training deep neural networks, as they capture rich curvature information of the loss landscape . The central challenge in this field lies in balancing preconditioning effectiveness with computational efficiency of implementing the preconditioner. Among recent advances, \textsc{Muon} stands out by using Newton-Schulz iteration to obtain preconditioned updates without explicitly constructing the preconditioning matrix. Despite its advantages, the efficiency of \textsc{Muon} still leaves room for further improvement. In this paper, we introduce \textsc{RMNP} (Row Momentum Normalized Preconditioning), an optimizer that replaces Newton-Schulz iteration with a simple row-wise $\ell_2$ normalization operation, motivated by the empirically observed diagonal block structure of the Transformer layerwise Hessian. This substitution reduces the per-iteration computational complexity from $\mathcal{O}(mn\cdot\min(m,n))$ to $\mathcal{O}(mn)$ for an $m\times n$ weight matrix while maintaining comparable optimization performance. Theoretically, we establish convergence guarantees for \textsc{RMNP} in the non-convex setting that match recent results for \textsc{Muon} optimizers, achieving the information-theoretic minimax optimal complexity. Extensive experiments on large language model pretraining show that \textsc{RMNP} delivers competitive optimization performance compared with \textsc{Muon} while substantially reducing preconditioning wall-clock time. Our code is available at \href{https://anonymous.4open.science/r/RMNP-E8E1/}{this link}.

Related papers

• Nora: Normalized Orthogonal Row Alignment for Scalable Matrix Optimizer [52.9566744833465]
  Matrix-based approaches to training Large Language Models (LLMs) have demonstrated immense potential.<n>A superior must satisfy three core desiderata: efficiency, achieving Muon-like preconditioning to accelerate optimization; stability, strictly adhering to the inherent in neural networks; and speed, minimizing computational overhead.<n>We propose Nora, which rigorously satisfies all three requirements and is highly promising for large-scale training.
  arXiv  Detail & Related papers  (2026-05-05T14:00:27Z)
• Less is More: Convergence Benefits of Fewer Data Weight Updates over Longer Horizon [42.1998022417145]
  We analyze the convergence behavior of data mixing with a finite number of inner steps $T$.<n>We show that the optimal $T$ scales as $(log N)$ (resp., $((N log N)1/2)$) for the data mixing problem with access to full.
  arXiv  Detail & Related papers  (2026-02-23T04:50:13Z)
• Evolution Strategies at the Hyperscale [57.75314521465674]
  We introduce EGGROLL, an evolution strategies (ES) algorithm designed to scale backprop-free optimization to large population sizes.<n>ES is a set of powerful blackbox optimisation methods that can handle non-differentiable or noisy objectives.<n>EGGROLL overcomes these bottlenecks by generating random matrices $Ain mathbbRmtimes r, Bin mathbbRntimes r$ with $rll min(m,n)$ to form a low-rank matrix perturbation $A Btop$
  arXiv  Detail & Related papers  (2025-11-20T18:56:05Z)
• Dynamic Regret Reduces to Kernelized Static Regret [63.36965242404415]
  We study dynamic regret in online convex optimization, where the objective is to achieve low cumulative loss relative to an arbitrary benchmark sequence.<n>By constructing a suitable function space in the form of a Reproducing Kernel Hilbert Space (RKHS), our reduction enables us to recover the optimal $R_T(u_1,ldots,u_T) = mathcalO(sqrtsum_t|u_t-u_t-u_t-1|T)$ dynamic regret guarantee.
  arXiv  Detail & Related papers  (2025-07-07T21:09:33Z)
• ReFill: Reinforcement Learning for Fill-In Minimization [3.9134031118910264]
  Minimizing fill-in is NP-hard, and existing minimizations like Minimum Degree and Nested Dissection offer limited adaptability.<n>We introduce textitReFill, a reinforcement learning framework enhanced by Graph Neural Networks (GNNs) to learn adaptive ordering strategies for fill-in.
  arXiv  Detail & Related papers  (2025-01-27T15:20:41Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  We provide a unified analysis of two-timescale gradient ascent (TTGDA) for solving structured non minimax optimization problems.<n>Our contribution is to design TTGDA algorithms are effective beyond the setting.
  arXiv  Detail & Related papers  (2024-08-21T20:14:54Z)
• Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
  This paper aims to recover the intrinsic model parameters given the leverage scores gradient. We specifically scrutinize the inversion of the leverage score gradient, denoted as $g(x)$.
  arXiv  Detail & Related papers  (2024-08-21T01:39:42Z)
• Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
  First-order algorithms require at least $mathcalO(varepsilonepsilon-4)$ complexity to find an $varepsilon-stationary point.<n>We introduce novel momentum algorithms utilizing efficient variable complexity.<n>The effectiveness of the method is validated through robust logistic regression using real-world datasets.
  arXiv  Detail & Related papers  (2024-06-18T20:14:52Z)
• From CNNs to Shift-Invariant Twin Models Based on Complex Wavelets [7.812210699650151]
  We replace the first-layer combination "real-valued convolutions + max pooling" We claim that CMod and RMax produce comparable outputs when the convolution kernel is band-pass and oriented. Our approach achieves superior accuracy on ImageNet and CIFAR-10 classification tasks.
  arXiv  Detail & Related papers  (2022-12-01T09:42:55Z)
• Optimal Diagonal Preconditioning: Theory and Practice [23.79536881427839]
  This paper presents the problem of optimal diagonal preconditioning to achieve maximal reduction in any full-rank number of rows or columns or simultaneously. We provide a baseline bisection algorithm that is easy to implement in practice. Next, we specialize to one-sided optimal diagonal preconditioning problems, and demonstrate that they can be formulated as standard dual SDP problems.
  arXiv  Detail & Related papers  (2022-09-02T04:21:28Z)
• Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization [44.54772242784423]
  We develop an efficient non regularization algorithm for low-rank learning matrix. The proposed algorithm can avoid expensive folding/unfolding problems. Experiments show that the proposed algorithm is efficient and more space than the existing state-of-the-world.
  arXiv  Detail & Related papers  (2022-05-06T07:47:10Z)
• DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
  We develop and analyze DASHA: a new family of methods for noneps distributed optimization problems. Unlike MARINA, the new methods DASHA, DASHA-MVR send compressed vectors only and never synchronize the nodes, which makes them more practical for learning.
  arXiv  Detail & Related papers  (2022-02-02T20:10:40Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. We show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching. We prove that Newton-LESS enjoys nearly the same problem-independent local convergence rate as Gaussian embeddings.
  arXiv  Detail & Related papers  (2021-07-15T17:33:05Z)
• Reducing the Variance of Gaussian Process Hyperparameter Optimization with Preconditioning [54.01682318834995]
  Preconditioning is a highly effective step for any iterative method involving matrix-vector multiplication. We prove that preconditioning has an additional benefit that has been previously unexplored. It simultaneously can reduce variance at essentially negligible cost.
  arXiv  Detail & Related papers  (2021-07-01T06:43:11Z)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  We propose a new non scalable low-rank regularizer called "nuclear Frobenius norm" regularizer, which is adaptive and sound. It bypasses the computation of singular values and allows fast optimization by algorithms. It obtains state-of-the-art recovery performance while being the fastest in existing matrix learning methods.
  arXiv  Detail & Related papers  (2020-08-14T18:47:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.