GPU-Enabled Large-Scale Optimization Using Randomized Linear Algebra

• URL: http://arxiv.org/abs/2609.08136v1
• Date: Tue, 08 Sep 2026 02:14:05 GMT
• Title: GPU-Enabled Large-Scale Optimization Using Randomized Linear Algebra
• Abstract summary: This paper introduces rlaopt, a PyTorch-based package for large-scale optimization and scientific computing using randomized numerical linear algebra (RandNLA)<n>Rlaopt addresses this gap by providing GPU-enabled solvers for positive-definite linear systems and convex empirical risk minimization with constraints and regularizers.<n>Rlaopt automatically checks compatibility with the selected solver and performs the required problem decomposition.
• Score: 13.9407640377773
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper introduces rlaopt, a PyTorch-based package for large-scale optimization and scientific computing using randomized numerical linear algebra (RandNLA). Despite substantial progress in RandNLA-based algorithms, few implementations combine GPU acceleration with a simple interface for specifying optimization problems. rlaopt addresses this gap by providing GPU-enabled solvers for positive-definite linear systems and convex empirical risk minimization with constraints and regularizers. These solvers use RandNLA to accelerate conjugate gradient (NystromPCG), operator splitting (NysADMM), and stochastic gradient methods (SAPPHIRE). Moreover, rlaopt includes a modeling language that lets users specify problems using natural mathematical syntax. rlaopt automatically checks compatibility with the selected solver and performs the required problem decomposition. The solvers also support differentiation through their iterations, enabling applications such as hyperparameter tuning. Experiments on ridge regression, bounded multinomial logistic regression, and bounded elastic net identify when randomized preconditioning improves performance and demonstrate substantial speedups from GPU execution. The package is open-source under an Apache license, with source code at https://github.com/udellgroup/rlaopt and version 0.1.0 available on PyPI.

Related papers

• Scaling Nonlinear Optimization: Many Problems One GPU [45.58567999526917]
  We introduce textttjaxipm, the first GPU-batched NLP solver, based on IPOPT.<n>We demonstrate up to a $32.85times$ increase in throughput over IPOPT.
  arXiv  Detail & Related papers  (2026-06-24T19:34:41Z)
• INC: An Indirect Neural Corrector for Auto-Regressive Hybrid PDE Solvers [61.84396402100827]
  We propose the Indirect Neural Corrector ($mathrmINC$), which integrates learned corrections into the governing equations.<n>$mathrmINC$ reduces the error amplification on the order of $t-1 + L$, where $t$ is the timestep and $L$ the Lipschitz constant.<n>We test $mathrmINC$ in extensive benchmarks, covering numerous differentiable solvers, neural backbones, and test cases ranging from a 1D chaotic system to 3D turbulence.
  arXiv  Detail & Related papers  (2025-11-16T20:14:28Z)
• Learning Sparse Approximate Inverse Preconditioners for Conjugate Gradient Solvers on GPUs [25.22023084590467]
  Concomitant gradient solver (CG) is a prevalent method for solving symmetric and positive definite linear systems Ax=b.<n>Existing learning-based methods often utilize Graph Neural Networks (GNNs) to improve the performance and speed up the construction.<n>We propose a learning-based method to generate GPU-friendly preconditioners, particularly using GNNs to construct Sparse Approximate Inverse (SPAI) preconditioners.
  arXiv  Detail & Related papers  (2025-10-31T14:42:48Z)
• A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions [75.69959433669244]
  We study the problem of online sparse linear regression (OSLR) where the algorithms are restricted to accessing only $k$ out of $d$ per instance for prediction.<n>We introduce a new extend-time algorithm, which significantly improves previous regret bounds.
  arXiv  Detail & Related papers  (2025-10-31T05:02:33Z)
• NGPU-LM: GPU-Accelerated N-Gram Language Model for Context-Biasing in Greedy ASR Decoding [54.88765757043535]
  This work rethinks data structures for statistical n-gram language models to enable fast and parallel operations for GPU-optimized inference.<n>Our approach, named NGPU-LM, introduces customizable greedy decoding for all major ASR model types with less than 7% computational overhead.<n>The proposed approach can eliminate more than 50% of the accuracy gap between greedy and beam search for out-of-domain scenarios while avoiding significant slowdown caused by beam search.
  arXiv  Detail & Related papers  (2025-05-28T20:43:10Z)
• The Polar Express: Optimal Matrix Sign Methods and Their Application to the Muon Algorithm [24.020943794160555]
  We introduce Polar Express, a new method for computing the polar decomposition.<n>We prove that this strategy minimizes error in a worst-case sense, allowing Polar Express to converge as rapidly as possible.<n>When integrated into the Muon training framework, our method leads to consistent improvements in validation loss.
  arXiv  Detail & Related papers  (2025-05-22T17:23:14Z)
• Training Deep Learning Models with Norm-Constrained LMOs [56.00317694850397]
  We propose a new family of algorithms that uses the linear minimization oracle (LMO) to adapt to the geometry of the problem.<n>We demonstrate significant speedups on nanoGPT training using our algorithm, Scion, without any reliance on Adam.
  arXiv  Detail & Related papers  (2025-02-11T13:10:34Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  We propose two variance reduced ZO estimators for complex gradient problems. We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
  arXiv  Detail & Related papers  (2024-10-03T15:04:01Z)
• DOGE-Train: Discrete Optimization on GPU with End-to-end Training [28.795080637690095]
  We present a fast, scalable, data-driven approach for solving relaxations of 0-1 integer linear programs. We use a combination of graph neural networks (GNN) and the Lagrange decomposition based algorithm FastDOG.
  arXiv  Detail & Related papers  (2022-05-23T21:09:41Z)
• Accelerating Genetic Programming using GPUs [0.0]
  Genetic Programming (GP) has multiple applications in machine learning such as curve fitting, data modelling, feature selection, classification etc. This paper describes a GPU accelerated stack-based variant of the generational GP algorithm which can be used for symbolic regression and binary classification.
  arXiv  Detail & Related papers  (2021-10-15T06:13:01Z)
• Adaptive Elastic Training for Sparse Deep Learning on Heterogeneous Multi-GPU Servers [65.60007071024629]
  We show that Adaptive SGD outperforms four state-of-the-art solutions in time-to-accuracy. We show experimentally that Adaptive SGD outperforms four state-of-the-art solutions in time-to-accuracy.
  arXiv  Detail & Related papers  (2021-10-13T20:58:15Z)
• Implementation of Parallel Simplified Swarm Optimization in CUDA [2.322689362836168]
  In optimization computing, intelligent swarm algorithms (SIAs) method is suitable for parallelization. This paper proposed a GPU-based Simplified Swarm Algorithm Optimization (PSSO) based on the platform considering computational ability and versatility. As the results showed, the time complexity has successfully reduced by an order of magnitude of N, and the problem of resource preemption was avoided entirely.
  arXiv  Detail & Related papers  (2021-10-01T00:15:45Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  Kernel methods provide an elegant and principled approach to nonparametric learning, but so far could hardly be used in large scale problems. Recent advances have shown the benefits of a number of algorithmic ideas, for example combining optimization, numerical linear algebra and random projections. Here, we push these efforts further to develop and test a solver that takes full advantage of GPU hardware.
  arXiv  Detail & Related papers  (2020-06-18T08:16:25Z)

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.