Cyclic and randomized stepsizes can lead to heavier tails in SGD, improving generalization.
problem Understanding when and why cyclic and randomized stepsizes outperform constant stepsize in SGD.
method Examined a general class of Markovian stepsizes, focusing on their tail-index behavior.
result Markovian stepsizes can achieve heavier tails, improving generalization over constant stepsize.
A new approach to reinforcement learning by adjusting stepsize based on state criticality.
problem The bias-variance trade-off in n-step reinforcement learning algorithms.
method Adapting the stepsize (n) for each state based on a human trainer's criticality measure.
result Improved reinforcement learning performance by dynamically adjusting the stepsize.
Study on GD and SGD over diagonal networks, focusing on stepsizes and regularisation.
problem Understanding the impact of stochasticity and large stepsizes on gradient descent and SGD solutions.
method Investigation of GD and SGD over diagonal linear networks with macroscopic stepsizes, proving convergence and characterizing solutions.
result Large stepsizes consistently benefit SGD for sparse regression problems, but can hinder GD recovery of sparse solutions, especially in the edge of stability regime.
Paper examines constant stepsize in LSA for Markovian data inference.
problem Improving statistical inference with constant stepsize in LSA for Markovian data.
method Established CLT, used averaged LSA iterates, applied Richardson-Romberg extrapolation.
result Constant stepsize leads to better CI coverage, especially with limited data.
Last SGD iterate bounds for overparameterized linear regression.
problem Analyzing the last iterate risk bounds of SGD with decaying stepsize for overparameterized linear regression.
method Problem-dependent analysis of last iterate risk bounds of SGD with geometrically decaying stepsize.
result Proved nearly matching upper and lower bounds on the excess risk for last iterate SGD with geometrically decaying stepsize.
Large stepsizes can accelerate gradient descent for logistic regression.
problem Optimizing logistic regression with large stepsizes.
method Gradient descent with large stepsize for ℓ 2 \ell_2 ℓ 2 -regularized logistic regression. result Large stepsizes can achieve O ~ ( κ ) \widetilde{\mathcal{O}}(\sqrtκ) O ( κ ) convergence, improving over O ~ ( κ ) \widetilde{\mathcal{O}}(\sqrtκ) O ( κ ) from classical theory. Large stepsize GD for logistic regression converges faster than expected.
problem Optimizing logistic regression with large step sizes.
method Gradient descent with large stepsize applied to logistic regression.
result GD converges to a lower loss in fewer steps than expected.
We revisit the classical Douglas-Rachford (DR) method for finding a zero of the sum of two maximal monotone operators. Since the practical performance of the DR method crucially depends on the stepsizes, we aim at developing an adaptive stepsize rule. To that end, we take a closer look at a linear case of the problem a…
Paper proposes a coupling-based diagnostic for SGD stepsize optimization.
problem Optimizing stepsize for SGD convergence.
method Coupling-based convergence diagnostic for monitoring stationarity.
result Proposed stepsize scheme achieves superior performance across convex and non-convex problems.
Stochastic gradient descent is the method of choice for large scale optimization of machine learning objective functions. Yet, its performance is greatly variable and heavily depends on the choice of the stepsizes. This has motivated a large body of research on adaptive stepsizes. However, there is currently a gap in o…
Study state-dependent Hawkes processes for limit order book modeling.
problem Modeling feedback loop between order flow and limit order book shape.
method Existence and uniqueness of state-dependent Hawkes processes, simulation, maximum likelihood estimation.
result Excitation effects in order flow are strongly state-dependent.
New algorithm learns optimal stepsizes for SGD in noisy non-convex optimization.
problem Finding optimal stepsize for SGD in noisy non-convex optimization.
method Surrogate losses cast problem into online convex optimization, using no-regret algorithms.
result Self-tuned SGD algorithm with adaptive convergence rates.
New algorithms eliminate stepsize tuning for bilevel optimization problems.
problem Bilevel optimization problems with unknown parameters and stepsizes.
method D-TFBO and S-TFBO algorithms with adaptive stepsizes.
result Achieve performance comparable to well-tuned approaches with theoretical guarantees.
New adaptive stepsize method for stochastic approximation converges to target point.
problem Finding optimal step sizes for stochastic approximation algorithms.
method Adaptive block-coordinate stepsizes using online estimates of second moment.
result New method converges almost surely to a small neighborhood of the target point.
Study on nonsmooth contractive SA with constant stepsize and Q-learning.
problem Understanding convergence and bias in nonsmooth contractive SA with different noise types.
method Proposed prelimit coupling technique for steady-state convergence and derived asymptotic bias.
result Asymptotic bias of nonsmooth SA is proportional to the square root of the stepsize.
Adaptive-stepsize MCMC sampling inspired by Adam optimizer.
problem Improving numerical stability and convergence speed in MCMC sampling.
method Time-rescaled Langevin dynamics with an auxiliary relaxation equation and adaptive stepsize control.
result Automatic stepsize control improves accuracy and stability in numerical experiments.
Proposes a new framework for optimizing utility with state-dependent benchmarks.
problem Various interpretations of benchmarks in utility functions.
method General framework of state-dependent utility optimization with stochastic benchmarks.
result Provides optimal solutions and addresses issues of well-definedness and feasibility.
Unique optimal strategy identified for state-dependent risk aversion.
problem Consistency of optimal portfolio choice for varying risk aversion.
method Analysis of state-dependent exponential utilities in arbitrage-free markets.
result Uniqueness of optimal strategy across any time horizon.
Study Q-learning with constant stepsize, proving convergence and bias, and applying extrapolation.
problem Understanding and optimizing Q-learning with constant stepsize.
method Connecting Q-learning to a Markov chain, proving distributional convergence and bias, applying Richardson-Romberg extrapolation.
result Explicit expression for the linear coefficient of the asymptotic bias and improvement of RR extrapolation method.
A Hawkes process with state-dependent factor models order flows in limit order books.
problem Modeling order flows in limit order books for better market prediction.
method A Hawkes process with a state-dependent factor for conditional intensity estimation.
result State-dependent formulations improve the fit of LOB models to financial data.
Study of SGD with state-dependent noise, improving escape from local minima.
problem Understanding and improving the dynamics of SGD in non-convex optimization.
method Formal study on SGD with state-dependent noise, proposing power-law dynamic with state-dependent diffusion.
result Power-law dynamic can escape from sharp minima exponentially faster than flat minima.
Proposes a new metric selection for VM-PG with improved convergence.
problem Improves convergence of VM-PG methods for ill-conditioned problems.
method Diagonal Barzilai-Borwein stepsize for adaptive metric selection.
result Improved convergence results for ill-conditioned problems.
Adaptive stepsizing improves sampling in Bayesian neural networks.
problem Scalable sampling of posterior distributions in Bayesian neural networks.
method SA-SGLD, employing time rescaling to adapt stepsize dynamically.
result SA-SGLD achieves more accurate posterior sampling than SGLD.
This work analyzes Q Q Q -learning with adaptive stepsizes for finite-time convergence.
problem Finite-time convergence analysis for average-reward Q Q Q -learning with adaptive stepsizes. method Adaptive stepsizes as local clocks, time-inhomogeneous Markovian reformulation, almost-sure time-varying bounds, conditioning arguments, and Markov chain concentration inequalities.
result Convergence rates of i l d e O ( 1 / k ) ilde{\mathcal{O}}(1/k) i l d e O ( 1/ k ) for mean-square and pointwise mean-square convergence. Study Whittle index learning algorithms for restless bandits with constant stepsizes.
problem Optimizing decisions in restless multi-armed bandits with constant stepsizes.
method Developed Q-learning algorithms with constant stepsizes for index learning in restless bandits, extending to DQN and function approximations.
result The algorithms learn the Whittle index effectively.
Study on bias and extrapolation in LSA with Markovian data, showing bias reduction with Richardson-Romberg extrapolation.
problem Bias in LSA with constant stepsizes and Markovian data.
method Viewing LSA as a Markov chain, proving convergence and bias expansion, and applying Richardson-Romberg extrapolation.
result Bias is proportional to the stepsize up to higher order terms, and Richardson-Romberg extrapolation reduces the bias.
Large GD stepsizes improve margins and speed up training for non-homogeneous networks.
problem Training efficiency and margin improvement in non-homogeneous two-layer networks.
method Investigation of two distinct phases in GD training, showing margin growth and empirical risk decrease.
result Large GD stepsizes lead to faster convergence and improved margins in non-homogeneous networks.
The paper improves convergence for linear systems using entropic mirror descent with Polyak stepsizes.
problem Convergence analysis for linear systems with unbounded domain.
method Entropic mirror descent with Polyak stepsizes, sublinear and linear convergence results.
result Generalized convergence result for arbitrary convex functions.
OSGM uses online learning to adapt stepsize for faster convergence.
problem Improving convergence rates of first-order methods.
method OSGM combines online learning and feedback functions to adjust stepsize.
result OSGM achieves convergence rates asymptotically no worse than optimal.
Study controlled contagion with state-dependent killing, proving a comparison principle.
problem Analyzing controlled McKean--Vlasov contagion with state-dependent killing.
method Proof of a comparison principle using Wasserstein smooth-gauge comparison and killing-jump absorption estimates.
result Established a comparison principle for the two-population killed-particle HJB.
This work accelerates gradient descent with anytime convergence guarantees.
problem Improving the convergence rate of gradient descent methods.
method Proposes a stepsize schedule for gradient descent that achieves anytime convergence rates.
result Gradient descent can achieve convergence rates of O ( T − 1.119 ) O(T^{-1.119}) O ( T − 1.119 ) for any stopping time T T T . Approximate dynamic programming (ADP) has proven itself in a wide range of applications spanning large-scale transportation problems, health care, revenue management, and energy systems. The design of effective ADP algorithms has many dimensions, but one crucial factor is the stepsize rule used to update a value functi…
Gradient descent converges with arbitrary stepsize for separable data under Fenchel-Young losses.
problem Understanding the conditions under which gradient descent converges with arbitrary stepsize.
method Using Fenchel-Young losses and leveraging the classical perceptron argument to derive convergence rates.
result GD converges with arbitrary stepsize for a majority of Fenchel-Young losses, with better rates for specific loss functions.
Proposes a new adaptive gradient method based on gradient differences.
problem Manual tuning of stepsize in vanilla gradient methods.
method Adaptation driven by cumulative squared norms of gradient differences.
result More robust than AdaGrad in various settings.
The paper provides bounds for LSA with fixed stepsizes under random estimates.
problem Analyzing the performance of LSA algorithms with fixed stepsize.
method Non-asymptotic analysis based on new results about matrix moments and high probability bounds.
result Derives high probability bounds on LSA performance under weaker conditions than previous works.
Enhanced ROOT-SGD optimizes stochastic optimization with diminishing stepsizes.
problem Improving statistical efficiency in stochastic optimization.
method Integrates a diminishing stepsize strategy into ROOT-SGD.
result Achieves optimal convergence rates with improved stability and precision.
Theory integrates loss aversion into expected utility for monetary returns.
problem Modeling loss aversion in expected utility theory.
method Develops state-dependent linear utility functions incorporating loss aversion.
result Contracts from monopolists in insurance markets.
GD with large, adaptive stepsizes achieves optimal risk in logistic regression.
problem Optimizing logistic regression with large stepsizes.
method Gradient Descent with adaptive stepsizes.
result GD achieves minimax optimal convergence in logistic regression.
This paper improves credit risk analysis by incorporating state-dependent recovery rates into a factor model.
problem Accurate default forecasting in credit risk analysis.
method Extends a one-factor Gaussian copula model to include state-dependent recovery rates and a common factor.
result The proposed model outperforms other models in default prediction, especially during hectic periods.
We propose a stepsize adaptation scheme for stochastic gradient descent. It operates directly with the loss function and rescales the gradient in order to make fixed predicted progress on the loss. We demonstrate its capabilities by conclusively improving the performance of Adam and Momentum optimizers. The enhanced op…
Study efficient algorithms for nonconvex optimization with state-dependent Markov data.
problem Stochastic optimization with Markovian data and state-dependent transition kernels.
method Projection-based and projection-free algorithms for constrained nonconvex problems.
result The number of oracle calls to achieve an ε ε ε -stationary point is O ( 1 / ε 2.5 ) \mathcal{O}(1/ε^{2.5}) O ( 1/ ε 2.5 ) . Improved TD learning for non-i.i.d. Markovian data.
problem Convergence analysis of two time-scale TD learning under Markovian samples.
method Non-asymptotic convergence analysis of two time-scale TD with gradient correction under Markovian data.
result Two time-scale TD can converge as fast as O(log t/(t^(2/3))) under diminishing stepsize.
The paper defines and characterizes conditional nonlinear expectations.
problem Defining and characterizing conditional nonlinear expectations.
method Embedding in decision theory, using state-dependent preferences, and continuous utility representation.
result Consistent backward conditional projections are characterized by the Sure-Thing Principle.
In this article, we derive a new stepsize adaptation for the normalized least mean square algorithm (NLMS) by describing the task of linear acoustic echo cancellation from a Bayesian network perspective. Similar to the well-known Kalman filter equations, we model the acoustic wave propagation from the loudspeaker to th…
Generalizes SGD convergence analysis and optimizes stepsize.
problem Analyzes convergence of stochastic gradient descent (SGD) under arbitrary sampling.
method Introduces expected smoothness and derives convergence rates for various mini-batching strategies.
result Derives optimal mini-batch size and stepsize-switching rules.
Improves posterior approximation speed for Dirichlet process mixture models.
problem Inefficiency of stochastic variational inference in large datasets.
method Uses stochastic gradient ascent with adaptive stepsize optimization.
result Adaptive stepsize improves speed and performance of posterior approximation.
The paper tackles model-based RL's inaccuracy issue by dynamically adjusting planning horizons.
problem Model-based RL's failure due to model inaccuracy over long planning horizons.
method State-dependent planning horizon, learning cumulative model errors with Temporal Difference methods.
result The proposed method successfully adapts planning horizons to state-dependent model accuracy, improving policy learning efficiency.
Proposes blockwise adaptive stepsize for faster training and better generalization in deep learning.
problem Widespread use of coordinate-wise adaptive methods like RMSprop and Adam leads to worse generalization than SGD.
method Splits network parameters into blocks and uses a blockwise adaptive stepsize, balancing adaptivity and generalization.
result Blockwise adaptive gradient descent converges faster and has lower generalization error than coordinate-wise adaptive methods.