Applying standard Markov chain Monte Carlo (MCMC) algorithms to large data sets is computationally infeasible. The recently proposed stochastic gradient Langevin dynamics (SGLD) method circumvents this problem in three ways: it generates proposed moves using only a subset of the data, it skips the Metropolis-Hastings a…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “Decreasing Step Size”
The CSA-ES is an Evolution Strategy with Cumulative Step size Adaptation, where the step size is adapted measuring the length of a so-called cumulative path. The cumulative path is a combination of the previous steps realized by the algorithm, where the importance of each step decreases with time. This article studies …
Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximationstat.ML
Paper improves CLT and bootstrap approximations for LSA with decreasing step size.
problem Improving normal approximation and bootstrap methods for LSA with decreasing step sizes.
method Refined Berry-Esseen bounds and multiplier bootstrap procedure for LSA.
result Approximation rates up to for LSA rescaled error distribution.
Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizescs.LG
Avare improves optimization and sampling with adaptive importance sampling.
problem Improving convergence rate of stochastic gradient-based algorithms.
method Adaptive importance sampling with decreasing step-sizes.
result Achieves dynamic regret bounds of and .
In an adaptive population which models financial markets and distributed control, we consider how the dynamics depends on the diversity of the agents' initial preferences of strategies. When the diversity decreases, more agents tend to adapt their strategies together. This change in the environment results in dynamical…
GradaGrad adapts learning rate non-monotonically, overcoming AdaGrad's step size decrease.
problem Fixed learning rate in AdaGrad leads to step size decrease over time.
method Introduces GradaGrad, which grows or shrinks the learning rate based on a different accumulation in the denominator.
result GradaGrad achieves similar convergence rates as AdaGrad and demonstrates non-monotone adaptation.
Applying standard Markov chain Monte Carlo (MCMC) algorithms to large data sets is computationally expensive. Both the calculation of the acceptance probability and the creation of informed proposals usually require an iteration through the whole data set. The recently proposed stochastic gradient Langevin dynamics (SG…
Gradually Truncated Log-normal distribution - Size distribution of firmscond-mat.stat-mech
Gradually Truncated Log-normal distribution - Size distribution of firms Abstract Many natural and economical phenomena are described through power law or log- normal distributions. In these cases, probability decreases very slowly with step size compared to normal distribution. Thus it is essential to cut-off these di…
Adaptive step-size improves optimization in complex geometries.
problem Optimizing functions with non-Euclidean geometries.
method Adaptive step-size strategy for optimization algorithms.
result Guaranteed convergence for Adaptive Conditional Gradient Descent.
We propose a statistical adaptive procedure called SALSA for automatically scheduling the learning rate (step size) in stochastic gradient methods. SALSA first uses a smoothed stochastic line-search procedure to gradually increase the learning rate, then automatically switches to a statistical method to decrease the le…
New convergence results for NGVI with various step sizes and sample sizes.
problem Understanding convergence of stochastic NGVI for various schedules.
method Projected stochastic NGVI for exponential family variational distributions.
result Geometric convergence and $\mathcal{O}\left(\frac{1}{T^ρ}
ight)$ rates for different schedules.
Recently it has been shown that the step sizes of a family of variance reduced gradient methods called the JacSketch methods depend on the expected smoothness constant. In particular, if this expected smoothness constant could be calculated a priori, then one could safely set much larger step sizes which would result i…
Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximationstat.ML
Paper develops Gaussian approximations and bootstrap for federated LSA with trade-off bounds.
problem Analyzing convergence rates and trade-offs in federated linear stochastic approximation.
method Established Berry-Esseen-type bounds for federated LSA, developed multiplier bootstrap for inference.
result First federated Gaussian approximations with explicit trade-off terms and non-asymptotic validity guarantees.
Paper proposes a new method to detect convergence in SGD.
problem Detecting the transition from fast progress to oscillation in SGD.
method Analyzes Pflug's test and proposes a novel statistical procedure.
result The novel procedure accurately detects stationarity in SGD.
GD monotonically decreases GFS sharpness in neural networks and scalar models.
problem Oscillatory behavior of loss in GD training.
method Analysis of GFS sharpness and empirical validation.
result GFS sharpness decreases monotonically during GD training.
Characterizes corridors in loss surfaces for gradient-based optimization.
problem Understanding and mitigating training instabilities in gradient-based optimization.
method Characterizes corridors as regions where gradient descent and gradient flow trajectories are linearly related.
result Corridors indicate regions without implicit regularization effects, leading to better learning rate adaptation schemes.
Deep networks run with low precision operations at inference time offer power and space advantages over high precision alternatives, but need to overcome the challenge of maintaining high accuracy as precision decreases. Here, we present a method for training such networks, Learned Step Size Quantization, that achieves…
In this paper, we consider multi-agent learning via online gradient descent in a class of games called -cocoercive games, a fairly broad class of games that admits many Nash equilibria and that properly includes unconstrained strongly monotone games. We characterize the finite-time last-iterate convergence rate for …
New SAGA algorithm with decreasing step for stochastic optimization.
problem Analysis of SAGA algorithm and its convergence properties.
method Introducing a new λ-SAGA algorithm with decreasing step, investigating convergence and establishing a central limit theorem.
result Established convergence and central limit theorem for λ-SAGA algorithm.
Recent advances in Bayesian learning with large-scale data have witnessed emergence of stochastic gradient MCMC algorithms (SG-MCMC), such as stochastic gradient Langevin dynamics (SGLD), stochastic gradient Hamiltonian MCMC (SGHMC), and the stochastic gradient thermostat. While finite-time convergence properties of th…
Gradient descent on neural nets often operates at the Edge of Stability, where loss behavior is complex but loss decreases over time.
problem Understanding the optimization dynamics of neural networks at the Edge of Stability.
method Empirical demonstration of gradient descent behavior in neural network training.
result Gradient descent on neural networks typically occurs at the Edge of Stability, where loss behavior is non-monotonic but loss decreases over time.
Stochastic Gradient Langevin Dynamics (SGLD) has emerged as a key MCMC algorithm for Bayesian learning from large scale datasets. While SGLD with decreasing step sizes converges weakly to the posterior distribution, the algorithm is often used with a constant step size in practice and has demonstrated successes in mach…
We propose a method to decrease the number of hidden units of the restricted Boltzmann machine while avoiding decrease of the performance measured by the Kullback-Leibler divergence. Then, we demonstrate our algorithm by using numerical simulations.
Stagewise training strategy is widely used for learning neural networks, which runs a stochastic algorithm (e.g., SGD) starting with a relatively large step size (aka learning rate) and geometrically decreasing the step size after a number of iterations. It has been observed that the stagewise SGD has much faster conve…
Novel bounds for SGLD show generalization error decreases with more samples.
problem Understanding the generalization error of SGLD in non-convex optimization.
method Information-theoretic approach focusing on Kullback-Leibler divergence and sub-exponential loss function.
result Time-independent generalization bounds for SGLD, independent of step size and number of iterations.
Mini-batch stochastic gradient descent and variants thereof have become standard for large-scale empirical risk minimization like the training of neural networks. These methods are usually used with a constant batch size chosen by simple empirical inspection. The batch size significantly influences the behavior of the …
Although stochastic gradient descent (SGD) method and its variants (e.g., stochastic momentum methods, AdaGrad) are the choice of algorithms for solving non-convex problems (especially deep learning), there still remain big gaps between the theory and the practice with many questions unresolved. For example, there is s…
This paper establishes risk convergence and asymptotic weight matrix alignment --- a form of implicit regularization --- of gradient flow and gradient descent when applied to deep linear networks on linearly separable data. In more detail, for gradient flow applied to strictly decreasing loss functions (with similar re…
Adapts SGD to noise and problem specifics for faster convergence.
problem Minimizing smooth, strongly-convex functions with varying noise and problem constants.
method Adaptive SGD with exponentially decreasing step-sizes, Nesterov acceleration, and stochastic line-search.
result Achieves near-optimal convergence rates without knowing noise or problem specifics.
Decentralized Bayesian learning reduces KL-divergence exponentially.
problem Efficiently learning posterior distributions in a decentralized setting.
method Decentralized Langevin dynamics in a non-convex setting.
result The algorithm converges to the target posterior distribution with exponential decrease in KL-divergence and polynomial decrease in error contributions.
New method improves convergence and reduces variance in noisy optimization problems.
problem Computing exact minimizers with noisy gradient information.
method Stochastic mirror descent with interacting particles.
result Interaction helps improve convergence and reduce variance.
Neural network has attracted great attention for a long time and many researchers are devoted to improve the effectiveness of neural network training algorithms. Though stochastic gradient descent (SGD) and other explicit gradient-based methods are widely adopted, there are still many challenges such as gradient vanish…
MiFID II impacts European stock liquidity and price formation.
problem Impact of MiFID II on European stock liquidity and price formation.
method Analyzed effects of MiFID II on European stock markets, focusing on intraday and closing auction liquidity and tick size changes.
result Closing auction volumes increased and price formation became more efficient after MiFID II.
Improved averaging method for noisy observations converges strongly.
problem Noisy observations from random dynamical systems require stable estimates.
method Introduced -EMA, a modified exponential moving average with subharmonic weight decay.
result Stochastic convergence guarantees for -EMA under mild assumptions.
The Expectation-Maximization (EM) algorithm for mixture models often results in slow or invalid convergence. The popular convergence proof affirms that the likelihood increases with Q; Q is increasing in the M -step and non-decreasing in the E-step. The author found that (1) Q may and should decrease in some E-steps; (…
Study on RF regression with SGD shows double descent phenomenon.
problem Understanding generalization in RF models trained with SGD.
method Precise non-asymptotic error bounds derived for RF regression under constant and polynomial-decay step-size SGD.
result RF regression generalizes well for interpolation learning and exhibits double descent behavior.
Improved analysis of extragradient methods for structured VIPs.
problem Efficiently solving large-scale VIPs with weaker conditions.
method Single-call stochastic extragradient methods with expected residual condition.
result Convergence guarantees for quasi-strongly monotone and weak Minty VIPs.
Transfer learning is a recent field of machine learning research that aims to resolve the challenge of dealing with insufficient training data in the domain of interest. This is a particular issue with traditional deep neural networks where a large amount of training data is needed. Recently, StochasticNets was propose…
Implicit Q-learning and SARSA adjust step-sizes automatically, improving stability and performance.
problem Numerical instability and slow progress in Q-learning and SARSA due to step-size calibration.
method Reformulate iterative updates as fixed-point equations, scaling step-sizes inversely with feature norms.
result Implicit methods maintain stability over broader step-size ranges and achieve comparable convergence rates.
ContinuousNet generalizes ResNets to continuous dynamical systems.
problem ResNets fail to be meaningful dynamical integrators.
method Embedding continuous dynamical systems into higher-order numerical integration schemes (Runge Kutta).
result ContinuousNet exhibits invariance to discrete time step sizes and numerical integration schemes.
LSD distills high-quality samplers for DDMs with fewer steps.
problem Inefficient sampling in DDMs leads to low quality and high computational cost.
method LSD employs a distillation approach to train fast samplers with learnable coefficients and time schedules.
result LSD+ achieves higher sampling quality with fewer steps compared to existing samplers.
SGD converges to global minimum for structured non-convex functions.
problem Optimizing non-convex functions using SGD with slow convergence rates.
method Convergence theorems for SGD on structured non-convex functions, including Quasar and PL conditions.
result SGD converges to global minimum for specific non-convex functions under certain conditions.
The only input to attain the portfolio weights of global minimum variance portfolio (GMVP) is the covariance matrix of returns of assets being considered for investment. Since the population covariance matrix is not known, investors use historical data to estimate it. Even though sample covariance matrix is an unbiased…
We revisit the fundamental problem of prediction with expert advice, in a setting where the environment is benign and generates losses stochastically, but the feedback observed by the learner is subject to a moderate adversarial corruption. We prove that a variant of the classical Multiplicative Weights algorithm with …
The paper analyzes fixed step-size SA schemes on Riemannian manifolds.
problem Developing efficient algorithms for optimization on curved spaces.
method Fixed step-size stochastic approximation schemes in a Riemannian framework.
result The schemes converge to the solution as the step-size approaches zero.
Paper improves confidence intervals for LSA with multiplier bootstrap.
problem Improving confidence intervals for parameter estimation in LSA.
method Berry-Esseen bound for multivariate normal approximation and multiplier bootstrap.
result Valid confidence intervals for parameter estimation in LSA.
Recent reports have described that the equivalent sample size (ESS) in a Dirichlet prior plays an important role in learning Bayesian networks. This paper provides an asymptotic analysis of the marginal likelihood score for a Bayesian network. Results show that the ratio of the ESS and sample size determine the penalty…
In this paper, we introduce a method for adapting the step-sizes of temporal difference (TD) learning. The performance of TD methods often depends on well chosen step-sizes, yet few algorithms have been developed for setting the step-size automatically for TD learning. An important limitation of current methods is that…