Improved sampling efficiency with Random Reshuffling for Langevin dynamics.
problem Sampling efficiency in stochastic gradient algorithms.
method Random Reshuffling for Stochastic Gradient Langevin Dynamics (SGLD).
result Random Reshuffling leads to improved performance in sampling.
Several useful variance-reduced stochastic gradient algorithms, such as SVRG, SAGA, Finito, and SAG, have been proposed to minimize empirical risks with linear convergence properties to the exact minimizer. The existing convergence results assume uniform data sampling with replacement. However, it has been observed in …
Study shows how mini-batch GD with random reshuffling affects least squares regression dynamics.
problem Analyzing the error dynamics of mini-batch GD with random reshuffling for least squares regression.
method Represented training and generalization errors through a sample cross-covariance matrix Z, compared with sample covariance matrix of original features X, and used linear scaling rule for analysis.
result Mini-batch GD with random reshuffling exhibits subtle step-size dependence not detectable by gradient flow analysis, converging to a limit dependent on the step size.
New analysis of signSGD with random reshuffling shows faster convergence rates.
problem Understanding the convergence of signSGD with random reshuffling in nonconvex optimization.
method Developed new sign-based algorithms (SignRVR, SignRVM) and analyzed convergence rates.
result Achieved faster convergence rates for signSGD with random reshuffling.
In empirical risk optimization, it has been observed that stochastic gradient implementations that rely on random reshuffling of the data achieve better performance than implementations that rely on sampling the data uniformly. Recent works have pursued justifications for this behavior by examining the convergence rate…
Improved convergence for VIPs with SEG-RR, a variant of SEG with random reshuffling.
problem Solving variational inequality problems (VIPs) in machine learning.
method Stochastic Extragradient with Random Reshuffling (SEG-RR).
result SEG-RR achieves faster convergence rates than with-replacement variants for certain VIP classes.
Random Reshuffling outperforms Stochastic Gradient Descent in smooth convex optimization.
problem Theoretical limitations of Random Reshuffling in smooth convex optimization.
method Random Reshuffling (RR) as a variant of Shuffling Stochastic Gradient Descent (Shuffling SGD).
result Random Reshuffling (RR) dominates Stochastic Gradient Descent (SGD) in smooth convex optimization under any reasonable stepsize after any finite number of epochs.
In this paper, we explore a general Aggregated Gradient Langevin Dynamics framework (AGLD) for the Markov Chain Monte Carlo (MCMC) sampling. We investigate the nonasymptotic convergence of AGLD with a unified analysis for different data accessing (e.g. random access, cyclic access and random reshuffle) and snapshot upd…
New SGDA method speeds up nonconvex minimax optimization.
problem Improving convergence of nonconvex minimax optimization.
method SGDA with random reshuffling for nonconvex-PŁ objectives.
result Convergence rates faster than with-replacement SGDA.
FedShuffle improves local updates in FL, especially with data imbalance.
problem Data imbalance in FL leads to different clients performing different numbers of local updates.
method FedShuffle incorporates random reshuffling, data imbalance, and client sampling.
result FedShuffle improves upon FL methods that assume homogeneous updates in heterogeneous setups.
RR algorithm improves convergence rate without strong convexity assumptions.
problem Minimizing finite-sum functions efficiently.
method Iterative gradient descent with data reshuffling, removing strong convexity assumptions.
result Improved convergence rate and variance for RR, matching lower bounds.
Reshuffling splits improves hyperparameter optimization's generalization performance.
problem Improving peak performance of machine learning models through better hyperparameter optimization.
method Reshuffling splits for every hyperparameter configuration improves generalization performance.
result Reshuffling leads to better generalization performance compared to fixed splits.
New method improves optimization algorithms without Lipschitz smoothness.
problem Improving optimization algorithms in the absence of Lipschitz smoothness.
method Dual kernel conditioning (DKC) to provide dual Lipschitz continuity.
result First complexity bounds and iterate convergence for random reshuffling mirror descent.
New bounds for SGD show improved performance in various settings.
problem Improving convergence bounds for SGD with random permutations.
method Analyzing convergence of SGD with random reshuffling and arbitrary permutations.
result Tighter lower bounds for weighted average iterates in both convex and strongly-convex cases.
New convergence bounds for shuffling-based SGD methods in distributed learning.
problem Analyzing the performance of shuffling-based variants of SGD in distributed learning.
method Study of minibatch and local Random Reshuffling methods, proving convergence bounds and lower bounds.
result Shuffling-based variants converge faster than with-replacement sampling methods, and the bounds are tight.
The paper analyzes the variance of different shuffling methods in stochastic gradient descent.
problem Understanding the variance of different shuffling methods in stochastic gradient descent.
method Power spectral density analysis to study the noise sequences of stochastic gradients.
result The stationary variances of iterates decrease in the order of SGD, SGD-RR, and SGD-SO.
New estimator improves policy evaluation in resource allocation RCTs.
problem Difficulty in evaluating policies optimizing limited resource allocation through RCTs.
method Proposes a novel estimator involving retrospective reshuffling of participants across experimental arms.
result The new estimator provides more accurate policy evaluations than common methods.
Improved shuffling gradient methods converge faster for nonsmooth convex optimization.
problem Improving convergence rates for nonsmooth convex optimization problems.
method Analysis of shuffling gradient methods, focusing on Random Reshuffle and Single Shuffle strategies.
result Shuffling gradient methods, particularly Random Reshuffle and Single Shuffle, converge faster than Proximal Gradient Descent for nonsmooth convex optimization.
New algorithms improve DRSL for large-scale problems.
problem Distributionally robust learning for real-world applications.
method Variance-reduced stochastic extra-gradient algorithms for min-max optimization.
result Provable faster convergence rates than existing approaches.
Paper provides linear convergence guarantees for KZIHT and KZPT methods.
problem Solving linear equation systems with sparse constraints.
method Combines Kaczmarz and iterative thresholding methods, using reshuffling data sampling.
result KZIHT and KZPT converge linearly to sparse solutions.
Doubly SGD improves convergence for intractable objective optimization.
problem Optimizing objectives in sum of intractable expectations.
method Doubly SGD with doubly stochastic gradients and independent minibatching.
result Established convergence of doubly SGD under general conditions, including dependent component gradient estimators.
The paper finds a surprising positive correlation between upstreamness and downstreamness in global value chains.
problem The puzzling positive correlation between upstreamness and downstreamness in industries and countries.
method Analysis of a simple model of random Input/Output tables and experiments on empirical data.
result Upstreamness and downstreamness of the same industrial sector/country are positively correlated with a slope close to +1.
Exact recovery of tensor decomposition (TD) methods is a desirable property in both unsupervised learning and scientific data analysis. The numerical defects of TD methods, however, limit their practical applications on real-world data. As an alternative, convex tensor decomposition (CTD) was proposed to alleviate thes…
Signatures of universality are detected by comparing individual eigenvalue distributions and level spacings from financial covariance matrices to random matrix predictions. A chopping procedure is devised in order to produce a statistical ensemble of asset-price covariances from a single instance of financial data sets…
New algorithm guarantees optimal convergence rate for stochastic optimization.
problem Optimal convergence rate for stochastic optimization algorithms.
method Regularized versions of Minimization by Incremental Surrogate Optimization (MISO) with arbitrary recurrent data sampling.
result Expected optimality gap converges at O(n−1/2) under general recurrent sampling schemes. In this paper, we propose a unified convergence analysis for a class of generic shuffling-type gradient methods for solving finite-sum optimization problems. Our analysis works with any sampling without replacement strategy and covers many known variants such as randomized reshuffling, deterministic or randomized singl…
New shuffling methods improve convergence without Lipschitz smoothness.
problem Lack of convergence guarantees for shuffling methods under non-Lipschitz conditions.
method Revisit shuffling methods, prove convergence under general bounded variance condition.
result Matched current best-known convergence rates without Lipschitz smoothness.
We study the performance of stochastic gradient descent (SGD) on smooth and strongly-convex finite-sum optimization problems. In contrast to the majority of existing theoretical works, which assume that individual functions are sampled with replacement, we focus here on popular but poorly-understood heuristics, which i…
New convergence rates for shuffling gradient methods without strong convexity.
problem Theoretical gap between shuffling gradient methods' empirical success and established convergence rates.
method Proved last-iterate convergence rates for shuffling gradient methods using function value gap.
result First last-iterate convergence rates for shuffling gradient methods without strong convexity.
Unified analysis of asynchronous-SGD algorithms for distributed learning.
problem Analyzing asynchronous-SGD in heterogeneous settings with varying speeds and data distributions.
method Unified convergence theory for non-convex smooth functions, including pure asynchronous SGD and its modifications.
result Unified convergence rates for various asynchronous algorithms, including novel methods.
New minibatching strategy reduces stochastic gradient bias in optimisation.
problem Reducing bias in stochastic gradient descent.
method Symmetric Minibatching Strategy combined with momentum.
result Reduced stochastic gradient bias from O(h2) to O(h4). Sampling without replacement speeds up optimization in minimax problems.
problem Optimizing minimax problems with faster convergence rates.
method Analysis of gradient descent ascent and proximal point method with two sampling strategies.
result Sampling without replacement leads to faster convergence rates in minimax optimization.
A new amortized variance-reduced gradient (AVRG) algorithm was developed in \cite{ying2017convergence}, which has constant storage requirement in comparison to SAGA and balanced gradient computations in comparison to SVRG. One key advantage of the AVRG strategy is its amenability to decentralized implementations. In th…
Study shows XRP price correlates with transaction network metrics.
problem Understanding the relationship between cryptoasset price and network metrics.
method Analysis of correlation tensor spectra, random matrix theory comparison, singular values investigation.
result Distinct correlation between XRP price and singular values during bubble and non-bubble periods.
Study examines how crypto arbitrage affects XRP price and network correlation.
problem Impact of crypto arbitrage on XRP price and network correlation.
method Examined XRP price fluctuations and correlation tensor spectra of transaction networks across crypto exchanges.
result Arbitrage opportunities across crypto exchanges anti-correlate with XRP price during bubble periods.
Develops a generalized version of Chung's Lemma for stochastic optimization methods.
problem Establishing asymptotic convergence rates for stochastic optimization methods under various step size rules.
method Generalized version of Chung's Lemma for a broader family of step size rules.
result Demonstrates tight non-asymptotic convergence rates for various stochastic methods.
We propose a novel kinetic exchange model differing from previous ones in two main aspects. First, the basic dynamics is modified in order to represent economies where immediate wealth exchanges are carried out, instead of reshufflings or uni-directional movements of wealth. Such dynamics produces wealth distributions …
TS-Fault benchmarks TSF models against structural faults.
problem Evaluating the robustness of time series forecasting models against structured events.
method TS-Fault uses parameterized fault scenarios with controllable difficulty.
result Three findings contradict common leaderboard intuition.
Proves local convergence of various online and recurrent optimization algorithms.
problem Proves local convergence of online and recurrent optimization algorithms not covered by standard stochastic gradient descent theory.
method Uses a general set of assumptions for learning dynamical systems online, adopting an 'ergodic' viewpoint.
result Local convergence results for online and recurrent optimization algorithms, including RMSProp, NoBackTrack, UORO, Adam, and RTRL.
Optimizer memory affects learning rate sensitivity in shuffle order, impacting fine-tuning noise.
problem Optimizer memory affects the learning rate sensitivity in shuffle order, leading to fine-tuning noise.
method Isolated the mechanism of fixed-clock optimizer memory affecting the learning rate sensitivity in shuffle order, deriving a fit-free way to size the noise.
result Fixed-clock optimizers like AdamW produce a larger first-order noise channel compared to memoryless optimizers, affecting fine-tuning comparisons.
This paper surveys various methods for dimensionality reduction and nearest neighbor search.
problem Efficiently reducing high-dimensional data to lower dimensions while preserving essential information.
method Linear and nonlinear random projections, including sparse random projections, random Fourier Features, and Random Kitchen Sinks.
result Various methods for dimensionality reduction and nearest neighbor search are explained and compared.
The paper studies how norms of random vectors are preserved by random projections.
problem Understanding how random matrix affects norms of random vectors.
method Proved the distribution of the norm of random vector is preserved by random projection.
result Random matrix preserves the distribution of the norm of random vectors with i.i.d. entries.
Orthogonal random features approximate a Bessel kernel, offering sharper bounds than random Fourier features.
problem Approximating Gaussian kernel efficiently for large datasets.
method Use of Haar orthogonal matrices to construct orthogonal random features and analyze their bias and variance.
result Orthogonal random features approximate a Bessel kernel, not the Gaussian kernel, with sharper bounds.
New methods improve prediction performance and reduce computation time in boosting and random forest models.
problem Improving prediction performance and reducing computation time in boosting and random forest models.
method Random tree depth injection approach for Boosting and Random Forests.
result The new methods can improve prediction performance and reduce computation time by up to 40%.
Proposes a method for modeling random objects in metric spaces using random effects.
problem Modeling random objects in non-Euclidean spaces with random effects.
method Nonlinear Fréchet-based algorithm for M-estimation.
result Consistent estimation of prediction target under random-effects formulation.
Enhances random forest performance with exogenous randomness.
problem Improving random forest performance through exogenous randomness.
method Developed non-asymptotic MSE expansions for individual trees and forests, identified two types of randomness, and conducted simulations.
result Exogenous randomness, particularly feature subsampling, reduces both bias and variance of random forests.
New random forest method provides optimal rates and confidence bands.
problem Improving random forest regression rates and constructing confidence bands.
method Proposed Ehrenfest centered purely random forests achieve optimal rates; used Gaussian approximation for supremum of empirical processes.
result Explicit asymptotic uniform confidence bands constructed for both random forest types.
Much is known about random right-angled Coxeter groups (i.e., right-angled Coxeter groups whose defining graphs are random graphs under the Erdös-Rényi model). In this paper, we extend this model to study random general Coxeter groups and give some results about random Coxeter groups, including some information about t…