arXiv Machine Learning
6d ago
Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp
arXiv:2608. 11760v1 Announce Type: cross Abstract: We revisit the Sinkhorn-Knopp (SK) algorithm for the matrix scaling problem.
Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp
We revisit the Sinkhorn-Knopp (SK) algorithm for the matrix scaling problem. Despite extensive literature on the global convergence of SK and its variants, its local linear convergence behavior remains less understood.
Related stories
arXiv Machine Learning
Jul 21
Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization
arXiv:2602. 20376v3 Announce Type: replace-cross Abstract: We study the problem of maximizing a complex-valued quadratic form over the $K^{\text{th}}$ roots of unity.
arXiv Machine Learning
Jun 2
How Accurately Can a Gaussian Approximate Stochastic Approximation Iterates?
arXiv:2602. 13906v2 Announce Type: replace-cross Abstract: Stochastic approximation (SA) is a method for finding the root of an operator perturbed by noise.
arXiv Machine Learning
Jul 21
Scaling Limits of Constant-Stepsize SGD at Flat Minima
arXiv:2607. 16384v1 Announce Type: new Abstract: For stochastic gradient descent (SGD) with a constant stepsize $\alpha$, the invariant law of the iterates, centered at a minimizer, describes the behavior of the algorithm over long time horizons.
arXiv Machine Learning
Aug 4
Improved convergence rate of kNN graph Laplacians: differentiable self-tuned affinity
arXiv:2410. 23212v3 Announce Type: replace-cross Abstract: In graph-based data analysis, $k$-nearest neighbor ($k$NN) graphs are widely used due to their adaptivity to local data densities.
arXiv Machine Learning
5d ago
Fast Length-Squared Sampling for Positive-Semidefinite Matrices
arXiv:2608. 12503v1 Announce Type: cross Abstract: We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an $n \times n$ positive-semidefinite (psd) matrix: that is, to sample a column with probability proportional to its squared $\ell_2$-norm.
arXiv Machine Learning
Jun 2
Scale-Invariant Neural Network Optimization: Norm Geometry and Heavy-Tailed Noise
arXiv:2605. 18528v2 Announce Type: replace-cross Abstract: A growing lesson from neural network optimization is that optimizer design should respect how the model is parametrized.
arXiv Machine Learning
Jul 27
On the Convergence of Stochastic Low-Rank Adaptation
arXiv:2607. 21975v1 Announce Type: new Abstract: Low-rank adaptation (LoRA) optimizes $J(B,A)=\mathcal L(W_\mathrm{base}+sBA)$ over two adapters $B \in \mathbb{R}^{m \times r}$ and $A \in \mathbb{R}^{r \times n}$ that form a low-rank update to a frozen pretrained weight matrix $W_\mathrm{base} \in \mathbb{R}^{m \times n}$.
arXiv Machine Learning
Jun 9
Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCA
arXiv:2602. 03682v2 Announce Type: replace-cross Abstract: We analyze the Accelerated Noisy Power Method, an algorithm for Principal Component Analysis in the setting where only inexact matrix-vector products are available, which can arise for instance in decentralized PCA.
arXiv Machine Learning
Jun 24
Exact Schur-Sylvester Dimensionality Reductions for Non-Smooth Stochastic Complexity and Manifold Sampling
arXiv:2606. 23867v1 Announce Type: new Abstract: The exact computation of the Normalized Maximum Likelihood (NML) codelength for regular non-smooth estimators (e.
arXiv Machine Learning
Jul 16
Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration
arXiv:2607. 13414v1 Announce Type: cross Abstract: Non-expansive two-time-scale stochastic approximation is governed by a slow stochastic Krasnoselskii--Mann fixed-point iteration rather than by contraction to a unique equilibrium.
arXiv Machine Learning
Jun 2
A Note on Stability for Orthogonalized Matrix Momentum with Client Sampling
arXiv:2606. 01720v1 Announce Type: new Abstract: We study finite-sample generalization for a client-sampled distributed optimization scheme with matrix-valued parameters and orthogonalized momentum updates.