Scalable algorithm for sampling Gaussian processes using sparse grids and preconditioners.
problem Generating high-dimensional Gaussian random vectors for GP sampling is computationally challenging.
method Proposes a scalable algorithm using inducing points approximation with sparse grids and additive Schwarz preconditioners.
result Demonstrates the efficacy and accuracy of the proposed method through experiments and comparisons.
New MCMC method learns sparse preconditioner for high-dimensional problems.
problem High-dimensional sampling with complex correlation structures.
method Adaptive MCMC with sparse preconditioner using online PCA.
result Significant reduction in computational complexity and improved performance.
NeuralIF uses neural networks to improve preconditioning for faster CG convergence.
problem Improving convergence of conjugate gradient method for large-scale sparse systems.
method Data-driven approach using graph neural networks to generate incomplete factorization.
result Data-driven preconditioners accelerate convergence of conjugate gradient method.
New lower bounds show sparse recovery is hard even with multiple preconditioners.
problem Sparse recovery with ill-conditioned designs is hard for certain algorithms.
method Constructing a single signal distribution that multiple preconditioned Lasso programs fail on.
result Standard sparse random designs are robust to erasures, aiding sparse recovery.
AI-driven framework optimizes MCMC-based preconditioners for faster linear system solving.
problem Slow convergence of Krylov subspace solvers for ill-conditioned matrices.
method Graph neural surrogate and Bayesian optimization for AI-tuned MCMC parameters.
result 50% reduction in iterations to convergence on unseen system.
When the design matrix has orthonormal columns, "soft thresholding" the ordinary least squares (OLS) solution produces the Lasso solution [Tibshirani, 1996]. If one uses the Puffer preconditioned Lasso [Jia and Rohe, 2012], then this result generalizes from orthonormal designs to full rank designs (Theorem 1). Theorem …
PEARL uses reinforcement learning to improve matrix preconditioners.
problem Learning effective preconditioners for iterative solvers is challenging.
method PEARL employs an actor-critic reinforcement learning framework to learn preconditioners dynamically.
result PEARL outperforms traditional and neural preconditioners in flexibility and solving speed.
We study two types of preconditioners and preconditioned stochastic gradient descent (SGD) methods in a unified framework. We call the first one the Newton type due to its close relationship to the Newton method, and the second one the Fisher type as its preconditioner is closely related to the inverse of Fisher inform…
New preconditioners speed up SGD on Lie groups.
problem Accelerating SGD convergence on Lie groups.
method Online updating of low-rank and matrix-free preconditioners.
result Preconditioners maintain symmetry and invariance.
The task of choosing a preconditioner M \boldsymbol{M} M to use when solving a linear system A x = b \boldsymbol{Ax}=\boldsymbol{b} Ax = b with iterative methods is difficult. For instance, even if one has access to a collection M 1 , M 2 , … , M n \boldsymbol{M}_1,\boldsymbol{M}_2,\ldots,\boldsymbol{M}_n M 1 , M 2 , … , M n of candidate preconditioners, it is currently …
New analysis for learning and applying preconditioners in MCMC improves efficiency.
problem Improving efficiency of MCMC algorithms by modifying them with preconditioners.
method Analyzes and compares computational costs of MCMC schemes with and without preconditioners.
result Establishes non-asymptotic guarantees for MCMC algorithms that learn and use preconditioners.
Analyzes learning and applying preconditioners in MCMC for efficiency.
problem Improving efficiency of MCMC algorithms.
method Non-asymptotic analysis of schemes that learn preconditioners.
result Established non-asymptotic guarantees for preconditioned ULA.
A new method reduces complexity of normalizing flows for MCMC preconditioning.
problem Improving sampling efficiency in MCMC algorithms for complex target distributions.
method Factorized preconditioning architecture combining a linear component and a conditional NF.
result Significantly better tail samples and higher effective sample sizes on various distributions.
Nystrom approximation speeds up kernel model training.
problem Slow convergence in kernel models due to poor conditioning.
method Spectral preconditioning with Nystrom approximation for scalability.
result Nystrom approximation accelerates gradient descent nearly as well as exact preconditioner.
We present a novel preconditioning technique for proximal optimization methods that relies on graph algorithms to construct effective preconditioners. Such combinatorial preconditioners arise from partitioning the graph into forests. We prove that certain decompositions lead to a theoretically optimal condition number.…
The paper studies efficient Hessian fitting methods for stochastic optimization.
problem Efficient Hessian fitting for stochastic optimization.
method Preconditioned Stochastic Gradient Descent (PSGD) method and Lie groups.
result Hessian fitting problem is strongly convex in certain Lie groups.
Shampoo optimizes preconditioners for faster convergence in machine learning.
problem Improving convergence speed in machine learning optimization.
method Explicit connection between Shampoo's Kronecker product approximation and optimal matrix approximations.
result The square of Shampoo's approximation is equivalent to a single power iteration step for optimal Kronecker product approximation.
Stochastic gradient descent (SGD) still is the workhorse for many practical problems. However, it converges slow, and can be difficult to tune. It is possible to precondition SGD to accelerate its convergence remarkably. But many attempts in this direction either aim at solving specialized problems, or result in signif…
This paper investigates Shampoo's heuristics and decouples preconditioner updates.
problem Improving Shampoo's heuristics for training neural networks.
method Decomposing preconditioner updates, correcting eigenvalues, and adapting eigenbasis computation frequency.
result Principled techniques to remove Shampoo's heuristics and improve training algorithms.
This paper proposes a family of online second order methods for possibly non-convex stochastic optimizations based on the theory of preconditioned stochastic gradient descent (PSGD), which can be regarded as an enhance stochastic Newton method with the ability to handle gradient noise and non-convexity simultaneously. …
Solving systems of linear equations is a problem occuring frequently in water engineering applications. Usually the size of the problem is too large to be solved via direct factorization. One can resort to iterative approaches, in particular the conjugate gradients method if the matrix is symmetric positive definite. P…
Bias correction improves language model training performance.
problem Stochastic update bias in preconditioned optimizers.
method Cross-fitted preconditioning and variance-corrected inversion.
result Reduces held-out pretraining loss by 0.15 nats.
Adaptive methods such as Adam and RMSProp are widely used in deep learning but are not well understood. In this paper, we seek a crisp, clean and precise characterization of their behavior in nonconvex settings. To this end, we first provide a novel view of adaptive methods as preconditioned SGD, where the precondition…
New iterative methods improve scalability of Gaussian process approximations for large data.
problem Scalability issues in Gaussian process approximations for large spatial data.
method Iterative methods combined with preconditioners to reduce computational costs.
result Preconditioners accelerate convergence and improve predictive variances.
Dual Space Preconditioning speeds up gradient descent in overparameterized models.
problem Improving convergence of gradient descent in overparameterized linear models.
method Introducing a novel preconditioner of the form a b l a K
abla K ab l a K for convex K K K and applying it to overparameterized linear models. result The iterates of the preconditioned gradient descent converge to a solution W ∞ {W}_{\infty} W ∞ satisfying X W ∞ = Y {X}{W}_{\infty} = {Y} X W ∞ = Y . This paper optimizes diagonal preconditioning to improve matrix condition numbers.
problem Optimizing diagonal preconditioning to reduce matrix condition numbers.
method Reformulated as a quasi-convex problem, solved with bisection and Newton updates.
result Optimal diagonal preconditioners can significantly improve iterative methods.
New neural operators learn structured patterns efficiently.
problem Learning and representing complex, structured patterns in data.
method Sparse autoencoder neural operators (SAE-NOs) parameterize concepts as functions, enabling efficient and structured representation.
result SAE-FNOs learn localized patterns and generalize across different scales and discretizations.
RL accelerates portfolio optimization and option pricing by dynamically adjusting preconditioner sizes.
problem Large linear systems in portfolio optimization and option pricing lead to slow convergence.
method Reinforcement Learning (RL) dynamically adjusts block-preconditioner sizes to accelerate convergence.
result RL-driven solver significantly reduces computational cost and accelerates convergence.
We propose two methods for exact Gaussian process (GP) inference and learning on massive image, video, spatial-temporal, or multi-output datasets with missing values (or "gaps") in the observed responses. The first method ignores the gaps using sparse selection matrices and a highly effective low-rank preconditioner is…
Bayesian sparse learning method improves deep neural network efficiency.
problem Sparse learning in deep neural networks with complex geometry.
method Preconditioned stochastic gradient Langevin Dynamics (PSGLD) for sampling and adaptive optimization of hyperparameters.
result The proposed algorithm achieves asymptotic convergence with controlled bias.
New research shows how preconditioning can solve sparse linear regression problems efficiently.
problem Efficiently solving sparse linear regression problems without restrictive conditions.
method Preconditioned Lasso approach to solve sparse linear regression problems.
result Preconditioning can solve a large class of sparse linear regression problems nearly optimally.
New method speeds up kernel-based machine learning for force field reconstruction.
problem Scalability issues in kernel-based machine learning for force field reconstruction.
method Nyström-type methods to construct preconditioners based on low-rank approximations of the kernel matrix.
result Effective preconditioners lead to super-linear convergence in kernel-based machine learning.
Unified framework for training neural networks with non-smooth, non-convex regularizers.
problem Training neural networks with non-smooth, non-convex regularizers.
method ProxGen framework for stochastic proximal gradient descent.
result ProxGen framework achieves the same convergence rate as standard methods and outperforms subgradient-based approaches.
Muon outperforms GD in associative memory learning by balancing frequency components.
problem Training dynamics and scaling behavior of Muon in associative memory learning.
method Study of Muon in a linear associative memory model with softmax retrieval and hierarchical frequency spectrum over query-answer pairs.
result Muon achieves exponential speedup over GD in noiseless case and superior scaling efficiency in noisy case.
Optimizes nonconvex optimization by converting it to static regret minimization.
problem Nonconvex optimization challenges in machine learning.
method Black-box online-to-nonconvex conversion with static regret minimization oracles.
result Achieves optimal convergence rates for nonconvex optimization.
ASTRA improves TDA by more accurately approximating iHVP.
problem Improving insights into training data attribution.
method ASTRA uses EKFAC-preconditioner on Neumann series iterations to accurately approximate iHVP.
result Improving iHVP approximation significantly improves TDA performance.
New methods improve solving linear systems and preconditioning with reduced complexity.
problem Efficiently solving linear systems and preconditioning matrices.
method Developed structured semidefinite programming algorithms.
result Improved runtimes for preconditioning and solving linear systems.
Flow Annealing Posterior Sampling unifies stochastic-process regression and PDE inverse problems.
problem Function-space posterior sampling for stochastic processes and inverse problems.
method Flow Annealing Posterior Sampling (FAPS) using pretrained function-space flow-matching priors.
result Coherent posterior samples with accurate uncertainty quantification.
New algorithm learns LQR with O ( T ) O(\sqrt{T}) O ( T ) regret using Langevin dynamics and excitation.
problem Learning LQR with a O ( T ) O(\sqrt{T}) O ( T ) regret bound. method Thompson sampling with Langevin dynamics and excitation mechanism.
result Achieved O ( T ) O(\sqrt{T}) O ( T ) regret bound for LQR learning. The successive projection algorithm (SPA) can quickly solve a nonnegative matrix factorization problem under a separability assumption. Even if noise is added to the problem, SPA is robust as long as the perturbations caused by the noise are small. In particular, robustness against noise should be high when handling th…
A new method improves convergence in low-rank approximation.
problem Efficiently solving large-scale numerical linear algebra problems.
method Error-Powered Sketched Inverse Iteration (EPSI) Method.
result Convergence rate improves at least linearly with sketch size.
The study explores various localized bases and their duals for scattered data approximation.
problem Scattered data approximation using radial basis functions.
method Examines different localized bases including Lagrange, Newton, and multiresolution versions, and their duals.
result Localized orthogonal bases, such as the Newton basis, offer symmetric preconditioners and are feasible for scattered data approximation.
HIP-GP improves GP inference for inter-domain observations with millions of inducing points.
problem Inference for Gaussian Processes across different domains.
method Hierarchical inducing point Gaussian process with grid structure and stationary kernel assumption.
result Improved approximation accuracy through increased number of inducing points.
A new ML method speeds up PDE simulations without needing classical training.
problem Accelerating transient PDE simulations using machine learning.
method Online-learned preconditioners using a bandit algorithm.
result One-shot acceleration of PDE simulations.
LoRA-One uses one-step full gradient to align adapters for efficient large model fine-tuning.
problem Fine-tuning large language models efficiently and accurately.
method Properly initializing LoRA adapters using the one-step full gradient and incorporating preconditioners.
result LoRA-One achieves significant empirical improvements over existing methods.
The paper analyzes Adam and SGD in nonstationary optimization, revealing tradeoffs between noise and drift.
problem Analyzing Adam and SGD in nonstationary optimization problems.
method Theoretical analysis of Adam and SGD under non-stationary stochastic objectives, separating two regimes.
result Characterizes the tradeoff between noise and drift in Adam and SGD, revealing when adaptive step-sizing is beneficial or harmful.
Paper analyzes Langevin dynamics for solving infinite-dimensional Bayesian inverse problems.
problem Solving high-dimensional Bayesian inverse problems in infinite-dimensional function spaces.
method Preconditioned Langevin dynamics with score-based generative models (SGMs).
result Derives error estimates and sufficient conditions for global convergence in Kullback-Leibler divergence.
New iterative methods improve Vecchia-Laplace approximations for large data sets.
problem Inaccurate and slow Vecchia-Laplace approximations for large data sets.
method Iterative methods to improve Vecchia-Laplace approximations, including preconditioners and novel methods for predictive variances.
result Order of magnitude speed-up and threefold increase in prediction accuracy compared to state-of-the-art methods.