We analyze constant step-size and iterate averaging in linear stochastic approximation algorithms.
problem Policy evaluation in reinforcement learning using temporal difference algorithms.
method Constant step-size and Polyak-Ruppert averaging of iterates.
result MSE decays as O(1/t) for a range of constant step-sizes under certain conditions.
New optimal step sizes and mini-batch sizes for SAGA.
problem Finding optimal step sizes and mini-batch sizes for SAGA.
method Provided closed-form expressions for expected smoothness constant and suggested new step sizes and mini-batch sizes.
result Total complexity of SAGA decreases linearly with mini-batch size up to an optimal value.
Gradient descent can use larger step sizes to avoid strict saddle points.
problem Avoiding strict saddle points in non-convex optimization.
method Proving that gradient descent with step-size up to 2/L avoids strict saddle points with high probability.
result Gradient descent with step-size up to 2/L almost surely avoids strict saddle points.
Sparse Polyak improves high-dimensional statistical estimation.
problem High-dimensional statistical estimation problems with growing problem dimension.
method Sparse Polyak modifies Polyak's adaptive step size to estimate restricted Lipschitz smoothness.
result Sparse Polyak achieves optimal statistical precision with fewer iterations.
New algorithm framework solves stochastic composite nonconvex optimization problems efficiently.
problem Solving stochastic composite nonconvex optimization problems.
method ProxSARAH framework using SARAH estimator with proximal gradient and averaging steps.
result Achieves best-known complexity bounds with constant and adaptive step-sizes.
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.
Paper develops a constant step stochastic Douglas-Rachford algorithm for convex minimization.
problem Finding solutions to convex minimization problems with random functions.
method Stochastic Douglas-Rachford algorithm with constant step size.
result Iterates stay close to the solution set with high probability.
Random reshuffling leads to better convergence in stochastic learning.
problem Improving convergence rate in stochastic gradient optimization.
method Analyzes constant step-size case with random reshuffling for strongly convex loss functions.
result Random reshuffling achieves a smaller neighborhood around the optimizer.
We consider the least-squares regression problem and provide a detailed asymptotic analysis of the performance of averaged constant-step-size stochastic gradient descent (a.k.a. least-mean-squares). In the strongly-convex case, we provide an asymptotic expansion up to explicit exponentially decaying terms. Our analysis…
Improved variational inequality algorithms using adaptive step sizes.
problem Solving monotone variational inequalities and convex-concave min-max problems efficiently.
method Adaptive step sizes that eliminate hyperparameters and global Lipschitz continuity requirements.
result Eliminated the need for the golden ratio in the algorithm and improved complexity bounds.
Adaptive gradient methods converge faster with over-parameterization and line-search.
problem Training over-parameterized models using adaptive gradient methods.
method Simplified setting of smooth, convex losses with over-parameterized models, proving convergence rates and demonstrating improvements with line-search techniques.
result Adaptive gradient methods, particularly AMSGrad, converge faster with line-search techniques.
The paper analyzes NPG in finite-horizon MDPs and provides convergence guarantees.
problem Finite-horizon Markov Decision Processes with known dynamics and transition kernels.
method Exact analysis of Natural Policy Gradient (NPG) with constant and increasing step sizes.
result NPG converges sublinearly with a rate of O(H^2/t) and linearly with a rate of O((1-1/θρ)^t).
Paper develops an online learning algorithm for functional data models.
problem Recovering slope functions or predictors in functional data models.
method Online regularized learning algorithm in reproducing kernel Hilbert spaces with polynomially decaying step-size.
result Established fast convergence rates for estimation error without capacity assumption.
Proposes a new adaptive learning rate for SGD.
problem Finding an efficient learning rate for SGD.
method Stochastic Polyak step-size (SPS).
result SGD with SPS converges faster for over-parameterized models.
Paper develops a diagnostic test for detecting convergence in SGD with constant step size.
problem Detecting convergence in stochastic gradient descent with constant step size.
method Statistical diagnostic test to detect phase transition in convergence.
result The diagnostic region coincides with the convergence region for a class of loss functions.
This manuscript shows that AdaBoost and its immediate variants can produce approximate maximum margin classifiers simply by scaling step size choices with a fixed small constant. In this way, when the unscaled step size is an optimal choice, these results provide guarantees for Friedman's empirically successful "shrink…
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.
The paper analyzes SGD and its convergence using Markov chain theory.
problem Analyzing the convergence of SGD with constant step-size.
method Integrates Markov chain theory into SGD analysis and uses Richardson-Romberg extrapolation.
result Provides an explicit asymptotic expansion of SGD iterates moments.
Optimistic method adapted for faster convex-concave min-max problems.
problem Solving convex-concave min-max optimization problems efficiently.
method Adaptive, line search-free second-order methods combining optimistic updates and second-order information.
result Achieves optimal convergence rate without line search or backtracking.
New convergence analysis for ADAM algorithm in non-convex optimization with adaptive step size.
problem Convergence issues in ADAM algorithm for non-convex optimization.
method Study of ADAM algorithm under bounded adaptive step size assumption, providing safe step sizes.
result Novel first order convergence rate result in deterministic and stochastic contexts.
The article examines in some detail the convergence rate and mean-square-error performance of momentum stochastic gradient methods in the constant step-size and slow adaptation regime. The results establish that momentum methods are equivalent to the standard stochastic gradient method with a re-scaled (larger) step-si…
Step decay schedules improve convergence in non-convex optimization.
problem Improving convergence in non-convex optimization problems.
method Analyzing convergence rates of step decay schedules in non-convex, convex, and strongly convex problems.
result Step decay schedules achieve O ( ln T / T ) \mathcal{O}(\ln T/\sqrt{T}) O ( ln T / T ) convergence rates in various optimization scenarios. Paper proposes a new approach for stochastic gradient descent in probabilistic modeling.
problem Finding optimal predictions in probabilistic models with large step sizes.
method Averaging moment parameters instead of natural parameters for constant-step-size stochastic gradient descent.
result Constant-step-size SGD can lead to better predictions in some cases and always converges in infinite-dimensional models.
The paper interprets learned step sizes in deep-unfolded gradient descent.
problem Intuitive interpretation of learned non-constant step sizes in deep-unfolded gradient descent.
method Theoretical analysis and optimization of spectral radius.
result Chebyshev steps achieve the lower bound of convergence rate for first-order methods.
Adaptive step-size method improves compressed SGD performance in machine learning.
problem Communication bottleneck in distributed and decentralized optimization.
method Developed an adaptive step-size method for compressed SGD.
result Order-optimal convergence rates for various objective functions.
Proposes a neural network for learning step-size policies for L-BFGS optimization.
problem Optimizing step sizes for L-BFGS in large-scale problems.
method Neural network architecture using local iterate information, trained via stochastic optimization.
result Outperforms existing step size selection methods in training classifiers.
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.
The paper analyzes the performance of constant step-size stochastic approximation algorithms.
problem Approximating solutions to root finding problems in optimization and machine learning.
method Examines stochastic approximation algorithms with constant step-size, proving convergence and analyzing the limiting behavior of averaged estimates.
result The Polyak-Ruppert-style averaged estimates converge to the true solution with optimal covariance, providing insights for practitioners.
We show that accelerated gradient descent, averaged gradient descent and the heavy-ball method for non-strongly-convex problems may be reformulated as constant parameter second-order difference equation algorithms, where stability of the system is equivalent to convergence at rate O(1/n 2), where n is the number of ite…
SGLD with constant step size often diverges from target posterior, but SGLDFP improves accuracy.
problem Inaccurate posterior approximation by SGLD with constant step size.
method SGLDFP uses control variates to reduce stochastic gradient variance.
result SGLDFP provides approximate samples from the posterior with comparable accuracy to LMC.
Gradient descent dynamics in quadratic regression models are analyzed, revealing five phases: monotonic, catapult, periodic, chaotic, and divergent.
problem Analyzing the dynamics of gradient descent in quadratic regression models.
method Fine-grained bifurcation analysis of gradient descent dynamics using a cubic map parameterized by the step-size.
result Gradient descent dynamics in quadratic regression models exhibit five distinct phases: monotonic, catapult, periodic, chaotic, and divergent.
Gradient descent converges linearly for overparameterized linear networks.
problem Convergence of gradient descent for overparameterized neural networks.
method Local Polyak-Lojasiewicz and Descent Lemma for overparameterized linear models.
result Gradient descent achieves linear convergence for two-layer linear networks under relaxed assumptions.
CoT enhances transformer accuracy on serial tasks by enabling serial computation.
problem Improving accuracy of large language models on inherently serial problems.
method Integrating a chain of thought (CoT) into decoder-only transformers to enable serial computation.
result Constant-depth transformers with CoT can solve problems in AC^0, surpassing TC^0 without CoT.
Study on improving the linear two-time-scale stochastic approximation method with a restarting scheme.
problem Characterizing and optimizing the finite-time complexity of linear two-time-scale stochastic approximation.
method Analysis of mean square errors, introduction of a restarting scheme to improve performance.
result The method achieves an exact convergence to the desired solution with improved complexity under time-varying step sizes.
New algorithm optimizes AUC in binary classification and changepoint detection.
problem Difficult to optimize AUC in binary classification and changepoint detection.
method Proposes efficient path-following algorithms for choosing optimal learning rate.
result Proposed line search algorithm computes complete AUM/AUC representation.
SGD batch size affects autoencoder global minima sparsity and sharpness.
problem Investigating how batch size impacts autoencoder learning.
method Non-convex autoencoder training with SGD, varying batch sizes.
result SGD batch size influences global minimum sparsity and sharpness.
Boosted Frank-Wolfe accelerates optimization for nonconvex problems.
problem Optimizing nonconvex and quasar-convex objectives efficiently.
method Developed a novel step size strategy for stochastic Frank-Wolfe, extending it to various gradient estimators.
result Boosted Frank-Wolfe achieves faster convergence rates than non-boosted Frank-Wolfe.
Quantized Stochastic Primal-Dual Methods for Distributed Optimization
problem Distributed optimization with stochastic gradients and finite-bit communication
method q-PDGD, a quantized stochastic primal-dual method
result Linear contraction to an explicit neighborhood under RSI, O(1/k) convergence under PL inequality
ATLAS adapts HMC step size and trajectory length for complex geometries.
problem Sampling complex geometries with constant step size HMC/NUTS.
method Adapts step size and trajectory length using local Hessian and no U-turn condition.
result ATLAS accurately samples complex geometries, outperforming NUTS.
Online learners track optimal solutions with constant step-size.
problem Tracking optimal solutions in online learning settings.
method Established a link between steady-state performance and tracking performance using analogies with adaptive filters.
result Inferred tracking performance from steady-state expressions directly.
Finite-time bounds on error for linear stochastic approximation and TD learning.
problem Finite-time bounds on error for linear stochastic approximation and TD learning.
method Finite-time bounds derived using Lyapunov functions and Stein's method.
result Finite-time bounds on the moments of the error, including lower-order and higher-order moments.
Stochastic gradient descent (SGD) on a low-rank factorization is commonly employed to speed up matrix problems including matrix completion, subspace tracking, and SDP relaxation. In this paper, we exhibit a step size scheme for SGD on a low-rank least-squares problem, and we prove that, under broad sampling conditions,…
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.
New insights into stochastic methods for solving variational inequalities.
problem Understanding convergence behaviors of stochastic algorithms in variational inequalities.
method Re-casting SEG/SGDA as Markov Chains to analyze their probabilistic structures.
result The average iterate is asymptotically normal with a unique invariant distribution for various VIPs.
Study on bias of constant-step stochastic approximation with Markovian noise.
problem Understanding the bias in stochastic approximation algorithms with Markovian noise.
method Infinitesimal generator comparisons to analyze bias, Lyapunov equation for time-averaged bias, Richardson-Romberg extrapolation for bias reduction.
result Bias of the algorithm is of order O ( α ) O(α) O ( α ) and time-averaged bias is α V + O ( α 2 ) αV + O(α^2) α V + O ( α 2 ) , where V V V is a constant. New factorial power constants improve optimization convergence rates.
problem Optimization convergence rates depend on various constants.
method Proposes using factorial powers for defining these constants.
result Factorial powers simplify or improve convergence rates of optimization methods.
Paper analyzes convergence of OMD algorithms with geometric conditions.
problem Analyzing convergence of online mirror descent algorithms.
method Presented necessary and sufficient conditions for convergence of OMD with step size sequences.
result Established conditions for convergence and linear convergence under specific variances.