Efficiently implements MEG for low-rank matrix optimization problems.
problem Optimization over spectrahedron with low-rank matrices.
method Matrix Exponentiated Gradient (MEG) method with efficient implementations.
result Methods converge from a warm-start initialization with similar rates to full-SVD-based counterparts.
We propose novel first-order stochastic approximation algorithms for canonical correlation analysis (CCA). Algorithms presented are instances of inexact matrix stochastic gradient (MSG) and inexact matrix exponentiated gradient (MEG), and achieve ε-suboptimality in the population objective in $\operatorname{poly}(\fr…
We present Matrix Krasulina, an algorithm for online k-PCA, by generalizing the classic Krasulina's method (Krasulina, 1969) from vector to matrix case. We show, both theoretically and empirically, that the algorithm naturally adapts to data low-rankness and converges exponentially fast to the ground-truth principal su…
QBVI uses natural gradients for efficient Bayesian learning.
problem Efficient Bayesian learning in complex models.
method Natural gradient updates in a black-box framework for exponential-family distributions.
result QBVI framework is effective for a wide range of Bayesian inference problems.
We study the dynamics of gradient descent on objective functions of the form f(∏i=1kwi) (with respect to scalar parameters w1,…,wk), which arise in the context of training depth-k linear neural networks. We prove that for standard random initializations, and under mild assumptions on f, the n…
Incorporates matrix exponential into generative flows for improved performance.
problem Improving generative flow models for better density estimation.
method Integrates matrix exponential into generative flows, proposing new layers and modifying network architecture.
result The proposed model achieves great performance on density estimation.
sgdGMF efficiently estimates generalized matrix factorization models for single-cell RNA sequencing data.
problem Challenges in dimensionality reduction for large single-cell RNA sequencing datasets.
method Scalable adaptive stochastic gradient descent algorithm for generalized matrix factorization models.
result sgdGMF outperforms existing methods in scalability and accuracy for large datasets.
A new machine learning model uses matrix exponentials for universal approximation.
problem Developing a robust and efficient machine learning model.
method Introduces a novel architecture using matrix exponentials as the only nonlinearity.
result The model achieves universal approximation properties and outperforms other models on benchmark tasks.
Adaptive stochastic gradient methods such as AdaGrad have gained popularity in particular for training deep neural networks. The most commonly used and studied variant maintains a diagonal matrix approximation to second order information by accumulating past gradients which are used to tune the step size adaptively. In…
Black-box optimization is primarily important for many compute-intensive applications, including reinforcement learning (RL), robot control, etc. This paper presents a novel theoretical framework for black-box optimization, in which our method performs stochastic update with the implicit natural gradient of an exponent…
The (stochastic) gradient descent and the multiplicative update method are probably the most popular algorithms in machine learning. We introduce and study a new regularization which provides a unification of the additive and multiplicative updates. This regularization is derived from an hyperbolic analogue of the entr…
Training avoids edge of stability by aligning Jacobian matrices.
problem Training neural networks on the edge of stability causes inaccuracies.
method Used an exponential Euler solver to prevent entering the edge of stability.
result Alignment of Jacobian matrices causes sharpness increase in Hessian.
We propose expected policy gradients (EPG), which unify stochastic policy gradients (SPG) and deterministic policy gradients (DPG) for reinforcement learning. Inspired by expected sarsa, EPG integrates (or sums) across actions when estimating the gradient, instead of relying only on the action in the sampled trajectory…
Sub-gradient method recovers low-rank matrices robustly from noisy measurements.
problem Recovering low-rank matrices from noisy measurements with unknown rank.
method Sub-gradient method with small initialization, robust to over-parameterization and noise.
result Sub-gradient method converges exponentially fast to the true solution under noisy and over-parameterized conditions.
SNN architecture shows gradient descent converges to regularized solution in matrix sensing problems.
problem Understanding implicit regularization in neural networks for matrix sensing.
method Developed Spectral Neural Networks (SNN) for matrix learning problems, rigorously demonstrating implicit regularization.
result Gradient descent converges to the solution of a regularized learning problem in matrix sensing problems.
We develop a more efficient NGD method for structured parameters.
problem Computational challenges in NGD for structured parameter spaces.
method Local-parameter coordinates to simplify Fisher-matrix computations.
result New structured second-order algorithms and learning methods.
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.
For a Morse map f:M→S1 Novikov [11] has introduced an analog of Morse complex, defined over the ring $\ZZZ[[t]][t^{-1}]$ of integer Laurent power series. Novikov conjectured, that generically the matrix entries of the differentials in this complex are of the form ∑iaiti, where ai grow at most exponenti…
New algorithm reduces complexity for SPD manifold optimization.
problem Efficiently minimize functions over SPD manifold.
method Low-complexity Riemannian subspace descent with sparse updates.
result Innovative updates avoid costly matrix operations.
Bounds on chemical reaction network relaxation rates using convex analysis.
problem Understanding relaxation dynamics in chemical reaction networks.
method Convex analysis, generalized gradient flows, singular values of stoichiometric matrix.
result Bounds on Kullback-Leibler divergence to equilibrium for CRNs.
Gradient-based algorithms are effective for many machine learning tasks, but despite ample recent effort and some progress, it often remains unclear why they work in practice in optimising high-dimensional non-convex functions and why they find good minima instead of being trapped in spurious ones. Here we present a qu…
We study the problem of computing the matrix exponential of a block triangular matrix in a peculiar way: Block column by block column, from left to right. The need for such an evaluation scheme arises naturally in the context of option pricing in polynomial diffusion models. In this setting a discretization process pro…
Gradient flow on softmax attention minimizes nuclear norm of weight matrices.
problem Classification with separate key and query weight matrices.
method Gradient flow on exponential loss, separability assumption, reparameterization, approximate KKT conditions.
result Gradient flow implicitly minimizes nuclear norm of weight matrices, contrasting with Frobenius norm minimization.
We introduce a covariance matrix estimator that both takes into account the heteroskedasticity of financial returns (by using an exponentially weighted moving average) and reduces the effective dimensionality of the estimation (and hence measurement noise) via techniques borrowed from random matrix theory. We calculate…
Characterizes uncertainty in low-rank matrix completion with noisy data.
problem Uncertainty quantification in low-rank matrix completion with heterogeneous sub-exponential noise.
method Characterizes the distribution of estimated matrix entries under low-rank estimators with heterogeneous sub-exponential noise.
result Explicit formulas for the distribution of estimated matrix entries under Poisson and Binary noise.
Gradient descent outperforms ridge regression under certain covariance matrix decay conditions.
problem Comparing the performance of gradient descent and ridge regression in linear models.
method Investigated gradient descent and ridge regression for linear regression with random isotropic ground truth.
result Gradient descent outperforms ridge regression under specific covariance matrix decay conditions.
A new method for efficiently computing derivatives of skew-symmetric matrix exponentials.
problem Efficient computation of derivatives for skew-symmetric matrices.
method Characterization of invertibility, construction of nearby logarithm, and efficient implementation.
result Explicit formulae for differentiation and its inverse of skew-symmetric matrix exponentials.
The paper introduces a new class of multivariate mixtures for actuarial applications.
problem Developing a new class of multivariate mixtures for actuarial calculations.
method Proposed a class of multivariate matrix-exponential affine mixtures with matrix-exponential marginals.
result Explicit calculations of actuarial quantities are possible due to the proposed class's properties.
Training very deep networks is an important open problem in machine learning. One of many difficulties is that the norm of the back-propagated error gradient can grow or decay exponentially. Here we show that training very deep feed-forward networks (FFNs) is not as difficult as previously thought. Unlike when back-pro…
We present a new method for online prediction and learning of tensors (N-way arrays, N>2) from sequential measurements. We focus on the specific case of 3-D tensors and exploit a recently developed framework of structured tensor decompositions proposed in [1]. In this framework it is possible to treat 3-D tensors …
Develops a gradient flow for Muon optimizer, a method for optimization.
problem Optimization of complex systems with matrix-valued parameters.
method Gradient flow on probability measures induced by regularized Muon optimizer.
result Derives continuous-time limits and proves Hamiltonian dissipation.
Gradient-free optimizers are ineffective on barren plateaus in quantum computing.
problem Effect of barren plateaus on gradient-free optimization in quantum computing.
method Numerical simulations and theoretical analysis of gradient-free optimization algorithms.
result Gradient-free optimizers are not effective in barren plateau landscapes due to exponentially suppressed cost function differences.
The matrix completion problem consists in reconstructing a matrix from a sample of entries, possibly observed with noise. A popular class of estimator, known as nuclear norm penalized estimators, are based on minimizing the sum of a data fitting term and a nuclear norm penalization. Here, we investigate the case where …
Exponentially fast SMF algorithm for multi-class classification.
problem Learning interpretable features from high-dimensional data.
method Novel framework that 'lifts' SMF as a low-rank matrix estimation problem.
result Provable exponential convergence to global minimizer under mild assumptions.
While deep learning is successful in a number of applications, it is not yet well understood theoretically. A satisfactory theoretical characterization of deep learning however, is beginning to emerge. It covers the following questions: 1) representation power of deep networks 2) optimization of the empirical risk 3) g…
AdaX improves Adam by exponentially accumulating past gradients, leading to better performance in machine learning tasks.
problem Adam's fast convergence can lead to local minimums in non-convex problems.
method AdaX exponentially accumulates past gradients to adaptively tune the learning rate.
result AdaX outperforms Adam in various machine learning tasks, including computer vision and natural language processing.
Random Matrix Theory explains loss surface Hessians in neural networks.
problem Understanding the loss surfaces of neural networks.
method Investigation of local spectral statistics of neural network Hessians.
result Excellent agreement with Gaussian Orthogonal Ensemble statistics.
A new method for learning Bayesian neural networks using layerwise inference.
problem Learning Bayesian neural networks efficiently and accurately.
method Bayesian layerwise inference, treating neural networks as stacked Bayesian linear models, with pseudo-targets defined by backpropagated gradients.
result The method converges quickly and performs well on various benchmarks.
Neural networks solve copositive programs, revealing insights into training problems.
problem Training two-layer vector-output ReLU neural networks.
method Convex analysis and copositive programming.
result Neural networks solve copositive programs, providing insights into training problems.
We introduce a framework to study the transformation of problems with manifold constraints into unconstrained problems through parametrizations in terms of a Euclidean space. We call these parametrizations "trivializations". We prove conditions under which a trivialization is sound in the context of gradient-based opti…
Unified framework for analyzing gradient flows of measures with exponential decay of entropy.
problem Analyzing exponential decay of entropy functionals in gradient flows of measures.
method Characterization of global exponential decay behaviors using Hellinger-Kantorovich geometry, shape-mass decomposition, and Polyak-Łojasiewicz-type inequalities.
result Unified theoretical framework for gradient flows with complete analysis of exponential decay behaviors.
Improved SVI with adjustable annealing for better optimization.
problem Improving optimization in stochastic variational inference.
method Tuneable stochastic annealing in SVI with adjustable batch size.
result Approximation to maximum entropy stochastic gradient at desired variance level.
Improved stability for large-scale Bayesian sampling.
problem Reducing instability in Langevin dynamics for large datasets.
method Introducing a modified CCAdL thermostat with a scaling and squaring method and a truncated Taylor series approximation.
result Significantly improved numerical stability and accuracy over existing methods.
Accelerated gradient method's stability deteriorates exponentially with steps.
problem Algorithmic stability of Nesterov's accelerated gradient method.
method Analysis of two notions of algorithmic stability for Nesterov's accelerated gradient method.
result Stability of Nesterov's accelerated method deteriorates exponentially with the number of gradient steps.
Gradient descent proves global convergence for 4-layer matrix factorization.
problem Global convergence of gradient descent on four-layer matrix factorization under random initialization.
method New techniques to show saddle-avoidance properties and extend eigenvalue theories.
result Polynomial-time global convergence guarantee for randomly initialized gradient descent on four-layer matrix factorization.
Gradient descent achieves exact linear convergence rate for symmetric matrix completion.
problem Low-rank symmetric matrix completion using gradient descent.
method Local analysis of gradient descent for symmetric matrices without additional assumptions.
result Closed-form expression of exact linear convergence rate matches practice.
Matrix completion aims to reconstruct a data matrix based on observations of a small number of its entries. Usually in matrix completion a single matrix is considered, which can be, for example, a rating matrix in recommendation system. However, in practical situations, data is often obtained from multiple sources whic…
Analytical solution found for a three-layer network with a specific activation function.
problem Understanding the power of depth in neural networks.
method Found analytical solutions for a three-layer network with a matrix exponential activation function.
result Analytical solutions for equations involving a three-layer network with a matrix exponential activation function.