FedLoRU improves FL efficiency by using low-rank updates.
problem Communication inefficiency and performance reduction in Federated Learning.
method Proposes FedLoRU, a low-rank update framework for FL, which reduces communication costs while maintaining performance.
result FedLoRU achieves convergence rates similar to FedAvg and is robust to heterogeneous and large numbers of clients.
A new method for efficient neural network fine-tuning using queryable low-rank update atoms.
problem Rigidity of static low-rank adaptation methods when input and depth-wise computation vary.
method A shared queryable memory of low-rank update atoms, allowing dynamic and context-sensitive adaptation.
result Improves final test performance and training stability compared to standard low-rank adaptation.
Develops efficient method for updating models with small data changes.
problem Efficiently updating models when data changes (e.g., adding/removing instances/features).
method Generalized Low-Rank Update (GLRU) for non-linear estimators.
result Provides updated solutions with computational complexity proportional to dataset changes.
PSI-LinUCB improves scalability for large recommender systems.
problem Efficiently training and inferring for large action spaces in recommender systems.
method Represent inverse design matrix as diagonal + low-rank correction, derive stable rank-1 and batched updates, use projector-splitting integrator.
result Demonstrated effectiveness on recommender system datasets, achieving scalable training and inference.
A new method for efficiently updating large-scale matrices in real-time.
problem Updating large-scale matrices with evolving data in real-time.
method Incremental SVD approach that handles row/column appends, rank-1 updates, and refresh strategies.
result Incremental SVD achieves accuracy close to full SVD with a fraction of the computational cost.
Flora uses random projections to achieve high-rank updates with low memory usage.
problem Excessive memory usage in large neural networks during training.
method Flora approximates LoRA using random projections to enable high-rank updates with sublinear space complexity.
result Flora achieves high-rank updates with significantly reduced memory usage compared to LoRA.
PLUMAGE improves large model training efficiency and stability.
problem Accelerator memory and networking constraints during large model training.
method Probabilistic Low rank Unbiased Minimum Variance Gradient Estimator (PLUMAGE) that resolves bias and variance issues.
result PLUMAGE reduces training loss by 28% on average across the GLUE benchmark.
New method improves compatibility of risk stratification models without sacrificing accuracy.
problem Compatibility issues arise when updating clinical machine learning models.
method Proposes rank-based compatibility measure and new loss function.
result Increased compatibility of models by 0.019 with no loss in discriminative performance.
Optimizes neural network training by dynamically updating Tucker decomposition ranks.
problem Redundant parameters in neural network architectures.
method Geometry-aware training of factorized layers in tensor Tucker format.
result Optimal locally approximating the original dynamics without initial rank knowledge.
Paper proposes recycling model updates in federated learning by exploiting low-rank gradient subspaces.
problem Large parameter transmissions in federated learning.
method Look-back Gradient Multiplier (LBGM) algorithm exploiting low-rank property of gradient subspaces.
result LBGM reduces communication overhead with minimal performance loss.
In this paper, we provide local and global convergence guarantees for recovering CP (Candecomp/Parafac) tensor decomposition. The main step of the proposed algorithm is a simple alternating rank-1 update which is the alternating version of the tensor power iteration adapted for asymmetric tensors. Local convergence g…
Paper presents a rank-1 approximation method for natural policy gradients in deep RL.
problem Computing natural gradients requires inverting the Fisher Information Matrix, which is computationally expensive.
method Develops a rank-1 approximation to the inverse Fisher Information Matrix for efficient natural policy optimization.
result The rank-1 approximation converges faster and has similar sample complexity to stochastic policy gradient methods.
Improves BBVI for high-dimensional Gaussian approximations by using low-rank approximations.
problem Scalability issues with BBVI for high-dimensional multivariate Gaussian approximations.
method Extends BaM framework to handle full covariance matrices by integrating patch step for low-rank parameterization.
result Shows improved efficiency and scalability on synthetic and real-world high-dimensional inference problems.
Improved tensor GLM estimation for complex data.
problem Complex tensor data in GLMs leads to high-dimensional, ill-posed estimation.
method Proposed LSRTR-M algorithm using Muon updates for faster convergence and lower errors.
result LSRTR-M converges faster and achieves lower errors than LSRTR.
New method finds efficient low-rank neural networks during training.
problem High memory and computational demands of neural networks.
method Restricts weight matrices to a low-rank manifold and updates low-rank factors.
result Significantly reduced time and memory resources required for training and evaluation.
LR-EDNN reduces PDE solver complexity by limiting network weights to low-rank subspace.
problem Efficiently solving time-dependent PDEs with deep neural networks.
method Low-rank constraint on network weights using SVD for efficient parameter updates.
result LR-EDNN achieves comparable accuracy to full EDNN with fewer parameters and lower cost.
Spectral gradient methods outperform Euclidean in certain deep learning scenarios.
problem When do spectral gradient updates outperform Euclidean in deep learning?
method Layerwise condition comparing squared nuclear-to-Frobenius ratio to stable rank of activations.
result Spectral updates can be more effective than Euclidean in deep networks and transformers.
Muon replaces matrix gradient with polar factor, optimizing flat spectrum updates
problem Optimization bias in matrix updates
method Using polar factor of gradient
result Muon update maximizes entropy among bounded updates
This work presents GROUSE (Grassmanian Rank-One Update Subspace Estimation), an efficient online algorithm for tracking subspaces from highly incomplete observations. GROUSE requires only basic linear algebraic manipulations at each iteration, and each subspace update can be performed in linear time in the dimension of…
To continuously improve quality and reflect changes in data, machine learning applications have to regularly retrain and update their core models. We show that a differential analysis of language model snapshots before and after an update can reveal a surprising amount of detailed information about changes in the train…
Improves graph-based active learning for non-Gaussian models.
problem Efficiently selecting data points for labeling in graph-based semi-supervised learning.
method Approximates non-Gaussian distributions, introduces rank-one update and model change acquisition function.
result Enhanced active learning for graph-based SSL under non-Gaussian models.
Efficiently completes low-rank matrices with nearly linear time complexity.
problem Completing low-rank matrices from a few observed entries.
method Robust alternating minimization framework with approximate updates.
result Achieves nearly linear time complexity in matrix completion.
Improved MORE algorithm reduces regret in black-box optimization and RL tasks.
problem Noisy fitness evaluations and poor sample quality in black-box optimization.
method Decouples mean and covariance updates, uses entropy scheduling, and simplifies model learning.
result Significantly reduces regret in black-box optimization and RL tasks.
In this paper, we propose a low-rank approximation method based on discrete least-squares for the approximation of a multivariate function from random, noisy-free observations. Sparsity inducing regularization techniques are used within classical algorithms for low-rank approximation in order to exploit the possible sp…
Paper improves recommendation systems by optimizing sequence of items for clicks.
problem Improving recommendation systems robustness against bots and clicks.
method Minimizing pairwise ranking loss over sequences of items, with thresholds to prevent bot influence.
result The proposed algorithms converge and outperform existing methods in various ranking measures.
In this paper, we propose exact passive-aggressive (PA) online algorithms for learning to rank. The proposed algorithms can be used even when we have interval labels instead of actual labels for examples. The proposed algorithms solve a convex optimization problem at every trial. We find exact solution to those optimiz…
A new method reduces high-dimensional filtering to quadratic complexity.
problem High-dimensional dynamical systems inference and simulation.
method Low-rank Kalman filtering using dynamical low-rank integrator.
result The method reproduces exact Kalman filter in low-rank limit.
We analyze the computational limits of LoRA for transformer models using fine-grained complexity theory.
problem Computational efficiency of LoRA fine-tuning for transformer models.
method Fine-grained complexity theory, identifying phase transitions, almost linear algorithms.
result Existence of almost linear algorithms for LoRA adaptation based on specific norms.
SGD updates align with a low-rank subspace but do not lead to further loss reduction.
problem Understanding the training dynamics of deep neural networks, particularly the role of the dominant subspace.
method Exploring whether neural networks can be trained within the dominant subspace of the loss Hessian.
result SGD updates, when projected onto the dominant subspace, do not decrease the training loss further, suggesting spurious alignment.
Principal components analysis (PCA) is a fundamental algorithm in data analysis. Its memory-restricted online versions are useful in many modern applications, where the data are too large to fit in memory, or when data arrive as a stream of items. In this paper, we propose ROIPCA and fROIPCA, two online PCA algorithms …
In designing personalized ranking algorithms, it is desirable to encourage a high precision at the top of the ranked list. Existing methods either seek a smooth convex surrogate for a non-smooth ranking metric or directly modify updating procedures to encourage top accuracy. In this work we point out that these methods…
The paper updates SVD of evolving matrices using projection techniques.
problem Updating the rank-k truncated SVD of evolving matrices.
method Projection viewpoint, building subspaces to approximate singular vectors.
result The proposed algorithm leads to higher accuracy, especially for large singular values.
In this paper, we propose an online algorithm to compute matrix factorizations. Proposed algorithm updates the dictionary matrix and associated coefficients using a single observation at each time. The algorithm performs low-rank updates to dictionary matrix. We derive the algorithm by defining a simple objective funct…
Paper studies asymmetric matrix sensing, proving gradient descent converges to low-rank solutions.
problem Reconstructing asymmetric low-rank matrices from linear measurements.
method Factorized gradient descent with coupling and regularization properties.
result Gradient descent from small random initialization converges to globally optimal and generalizing solutions.
Nonnegative matrix factorization (NMF), a dimensionality reduction and factor analysis method, is a special case in which factor matrices have low-rank nonnegative constraints. Considering the stochastic learning in NMF, we specifically address the multiplicative update (MU) rule, which is the most popular, but which h…
Algorithm recovers factors of rank-1 matrices from noisy measurements.
problem Estimating factors of a rank-1 matrix from nonlinearly transformed and noisy measurements.
method Alternating minimization with random initialization and analysis of empirical error recursion.
result Algorithm converges geometrically fast from random initialization, with sharp guarantees.
We present online boosting algorithms for multilabel ranking with top-k feedback, where the learner only receives information about the top k items from the ranking it provides. We propose a novel surrogate loss function and unbiased estimator, allowing weak learners to update themselves with limited information. Using…
Several important applications, such as streaming PCA and semidefinite programming, involve a large-scale positive-semidefinite (psd) matrix that is presented as a sequence of linear updates. Because of storage limitations, it may only be possible to retain a sketch of the psd matrix. This paper develops a new algorith…
This work introduces 'Artificial Entanglement' to understand LLMs' fine-tuning effectiveness.
problem Understanding the effectiveness of parameter-efficient fine-tuning methods for large language models.
method Adopting a quantum-information-inspired perspective, the study measures 'Artificial Entanglement' in neural networks.
result LoRA and FFT induce distinct internal entanglement signatures but not external ones, suggesting a 'no-hair' property.
A new method reduces data movement in neural network training.
problem Large data movement during neural network training.
method Streaming batch principal component analysis for low-rank updates.
result Effective training of convolutional neural networks with low overhead.
E2M optimizes tensor density estimation by relaxing α-divergence to KL-divergence.
problem Analytical challenges in traditional α-divergence optimization for tensor-based density estimation. method E2M algorithm: relaxes optimization to KL-divergence, then applies tensor many-body approximation. result Flexible modeling of various low-rank structures and their mixtures.
GeLoRA optimizes LoRA fine-tuning by dynamically adjusting ranks based on intrinsic dimensionality.
problem Efficient fine-tuning of large language models with limited computational resources.
method GeLoRA computes intrinsic dimensionality to adaptively select LoRA ranks, balancing expressivity and efficiency.
result GeLoRA consistently outperforms recent baselines within the same parameter budget on multiple tasks.
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.
IRCUR accelerates RPCA by using CUR decomposition for efficient low rank estimation.
problem Dimension reduction in robust principal component analysis.
method IRCUR employs CUR decomposition to update the low rank component efficiently.
result IRCUR achieves significant computational efficiency compared to existing algorithms.
Novel algorithm for Markov decision processes using rank-one approximation.
problem Solving planning and learning problems of Markov decision processes.
method Policy iteration with rank-one approximation of transition probability matrix.
result The proposed algorithm consistently outperforms first-order algorithms and their accelerated versions.
A new method for machine learning updates reduces complexity and improves robustness.
problem Stochastic gradient updates are inefficient and sensitive to feature scaling.
method Incremental Gauss-Newton Descent (IGND) reduces the need for matrix operations and improves robustness.
result IGND improves robustness to sensitivity scaling and can be competitive with common stochastic optimizers.
New PFPPs based on rank-dependent utility for better performance control.
problem Improving performance prediction in systems with short-term control.
method Introduces rank-dependent PFPPs, solves integral equations via Volterra theory.
result Existence of rank-dependent PFPPs under specific market conditions.
New framework explains why nonconvex methods work well in low-rank matrix estimation.
problem Nonconvex low-rank matrix estimation problems in machine learning.
method Developed a theoretical framework revealing a benign regularizer.
result Nonconvex procedures can behave well due to a disguised convexity.