In smooth strongly convex optimization, knowledge of the strong convexity parameter is critical for obtaining simple methods with accelerated rates. In this work, we study a class of methods, based on Polyak steps, where this knowledge is substituted by that of the optimal value, . We first show slightly improved …
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,694 papers · 148 categories
Trend · papers per month
48 results for “Polyak Steps”
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.
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.
Polyak step size GD reaches final radius of convergence after log iterations.
problem Statistical and computational complexities of Polyak step size GD.
method Generalized smoothness and Lojasiewicz conditions, stability of gradients.
result Polyak step size GD reaches final statistical radius of convergence after logarithmic number of iterations.
New step-size methods improve SHB convergence for stochastic optimization.
problem Tuning step-size and momentum parameters in SHB is challenging.
method Proposed MomSPS, MomDecSPS, and MomAdaSPS for SHB.
result Convergence guarantees for SHB to solution neighborhoods and exact minimizers.
Improved Sparse Polyak for high-dimensional M-estimation with sparser solutions.
problem High-dimensional M-estimation problems with potential loss of sparsity and accuracy.
method Variant of Sparse Polyak with optimal thresholding operators.
result Retains desirable scaling properties while achieving sparser and more accurate solutions.
Adaptive Sharpness-Aware Minimization with a Polyak-type Step size: A Theory-Grounded Schedulermath.OC
New adaptive scheduler improves SAM for better model training.
problem Training machine learning models requires selecting a learning rate, which is often difficult and time-consuming.
method Derive Polyak schedulers tailored to SAM-style updates, proving linear convergence for strongly convex objectives and an O(1/T) rate for convex objectives.
result Polyak schedulers achieve comparable or better performance than tuned SAM baselines, reducing the need for learning-rate tuning.
New SPS variant improves non-smooth optimization without small gradients.
problem Improving non-smooth optimization without small gradients.
method Safeguarded Stochastic Polyak Step Size (SPS) for non-smooth optimization.
result Rigorous convergence guarantees for non-smooth convex optimization without strong assumptions.
On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationstat.ML
Study on stochastic approximation with Polyak-Ruppert averaging for linear systems.
problem Understanding the asymptotic and non-asymptotic properties of stochastic approximation procedures.
method Detailed analysis of linear stochastic approximation with Polyak-Ruppert averaging, focusing on asymptotic and non-asymptotic properties.
result Proves CLT and non-asymptotic concentration inequality for averaged iterates, providing refined understanding of linear stochastic approximation.
Adaptive SGD with Line-Search and Polyak Stepsizes: Nonconvex Convergence and Accelerated Ratesmath.OC
Improved SGD methods converge faster for nonconvex optimization.
problem Nonconvex optimization challenges in machine learning.
method Adaptive SGD with line-search and Polyak stepsizes.
result Unified convergence rates for various nonconvex functions.
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.
A Local Polyak-Lojasiewicz and Descent Lemma of Gradient Descent For Overparametrized Linear Modelscs.LG
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.
New insights into SGD and SGD-M in high dimensions.
problem Understanding and comparing SGD and SGD-M in high-dimensional settings.
method Developed high-dimensional scaling limits for SGD-M and online SGD, examining their dynamics and performance.
result SGD-M amplifies high-dimensional effects, potentially degrading performance compared to online SGD.
Gradient method converges locally linearly for overparameterized Gaussian mixtures.
problem Learning Gaussian mixtures under overparameterization.
method Gradient-based method alternating short descent steps and long Polyak steps.
result Gradient method converges locally linearly to minimizers.
ProxSPS improves on SPS for regularization tasks, offering better stability and performance.
problem Handling regularization terms in adaptive step size schemes for stochastic gradient descent.
method Developed a proximal variant of the stochastic Polyak step size (SPS) scheme.
result ProxSPS is easier to tune and more stable with regularization, and performs well in image classification tasks.
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.
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.
The paper offers precise bounds for averaged LSA iterates in linear systems.
problem Computing approximate solutions of linear systems with noisy observations.
method Finite-time analysis of LSA algorithms with Polyak-Ruppert averaging.
result Sharp high-probability bounds for averaged LSA iterates.
Study Q-learning with averaging for reinforcement learning, proving efficient inference and error bounds.
problem Efficient inference and error bounds for Q-learning with averaging.
method Functional central limit theorem and asymptotic linear estimator for optimal Q-value function.
result Standardized partial-sum process converges weakly to a rescaled Brownian motion, matching instance-dependent lower bound for error.
Gradient descent converges linearly in finite-width networks with positive NTK and compatible conditions.
problem Local convergence of gradient descent in finite-width networks.
method Positive Neural Tangent Kernel (NTK), local Polyak-Łojasiewicz inequality, fixed-step containment in Locally Quasi-Convex Region (LQCR).
result Linear convergence achieved under specific conditions.
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.
The paper explores how dynamic preconditioning affects the CLT in online averaging.
problem When does dynamic preconditioning preserve the Polyak-Ruppert CLT?
method The authors decompose the averaged error and identify a stabilization-rate threshold for the CLT to hold.
result The CLT holds if the dynamic remainder vanishes in and the stabilization rate exceeds a threshold.
Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Conditioncs.LG
In 1963, Polyak proposed a simple condition that is sufficient to show a global linear convergence rate for gradient descent. This condition is a special case of the Łojasiewicz inequality proposed in the same year, and it does not require strong convexity (or even convexity). In this work, we show that this much-older…
Formulae for Vassiliev invariants derived from Kauffman polynomial.
problem Computing Vassiliev invariants from knot polynomials.
method State model of Kauffman polynomial, Gauss diagram identities, arrow diagram identities.
result Gauss diagram formulae for Vassiliev invariants of order 3.
Polyak-Ruppert CLT for SA-Adam with momentum and non-convergent adaptive preconditioning
problem Adaptive optimizers combining momentum and non-convergent preconditioning
method Proving positive drift stability and a non-autonomous Polyak-Ruppert CLT for SA-Adam
result The iterate-marginal covariance is exactly the plain stochastic gradient descent (SGD) sandwich
Improved convergence analysis for decentralized non-convex optimization.
problem Minimizing a sum of smooth non-convex functions over a network.
method Gradient tracking in decentralized stochastic gradient descent (GT-DSGD).
result GT-DSGD achieves network-independent performances matching centralized SGD under certain conditions.
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.
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.
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.
New findings show convergence in SA without square summable step sizes.
problem Finding optimal step sizes for stochastic approximation algorithms.
method Analyzed step-size sequences of the form with , and derived convergence and rate results.
result Convergence of parameter estimates with probability one and in for any ; MSE rate of convergence is , improved to with averaging.
Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometrymath.OC
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
Polyak's momentum accelerates training of neural networks.
problem Understanding and explaining the acceleration effect of Polyak's momentum in neural network training.
method Modular analysis of Polyak's momentum for training wide ReLU networks and deep linear networks.
result Polyak's momentum achieves an accelerated linear rate of for training wide ReLU networks and deep linear networks.
On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimizationcs.LG
Multiple gossip steps improve decentralized optimization convergence.
problem Efficiently optimizing large-scale machine learning models with limited communication.
method Integrates multiple gossip steps between gradient descent iterations in compressed decentralized optimization.
result Convergence to within ε of the optimal value for smooth non-convex objectives.
Stochastic Gradient Descent (SGD) is a popular tool in training large-scale machine learning models. Its performance, however, is highly variable, depending crucially on the choice of the step sizes. Accordingly, a variety of strategies for tuning the step sizes have been proposed, ranging from coordinate-wise approach…
We describe the space of arrow diagram formulas for virtual knot diagrams in the annulus as the kernel of a linear map, inspired from a conjecture due to M. Polyak. As a main application, we slightly improve Grishanov-Vassiliev's theorem for planar chain invariants.
Two-Tailed Averaging improves generalization by optimizing the number of leading iterates to ignore.
problem Improving generalization in stochastic optimization with limited resources and hyperparameters.
method An anytime adaptive algorithm that balances the number of leading iterates to ignore for better generalization.
result Approximates the optimal tail at all optimization steps, improving generalization without hyperparameters.
In this paper, it is shown that there are no nonconstant Goussarov-Polyak-Viro finite-type invariants that are invariant under the virtualization move. As an immediate corollary, we obtain the theorem which states none of the Birman coefficients of the Jones-Kauffman polynomial are of GPV finite type.
New theory sharpens Q-learning with LDTZ rate, proving it's best of both worlds.
problem Improving Q-learning's theoretical and practical performance.
method Developed a sharp non-asymptotic error bound and central limit theory for Q-learning with PD2Z-ν schedule.
result Q-learning with LDTZ schedule achieves rapid decay and asymptotic convergence guarantees.
We describe the Polyak-Viro arrow diagram formulas for the coefficients of the Conway polynomial. As a consequence, we obtain the Conway polynomial as a state sum over some subsets of the crossings of the knot diagram. It turns out to be a simplification of a special case of Jaeger's state model for the HOMFLY polynomi…
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.
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 and time-averaged bias is , where is a constant.
Finite Type Enhancementsmath.GT
We enhance the biquandle counting invariant using elements of truncated biquandle-labeled Polyak algebras. These finite type enhancements reduce to the finite type enhancements defined by Goussarov, Polyak and Viro for the trivial biquandle of one element and determine (but are not determined by) the biquandle counting…
We present a new method to produce simple formulas for 1-cocycles of knots over the integers, inspired by Polyak-Viro's formulas for finite-type knot invariants. We conjecture that these formulas always represent finite-type cohomology classes in the sense of Vassiliev. An example of degree 3 is studied, and shown to c…
Formula for Milnor triple linking number in link diagrams with multiple crossings.
problem Calculating Milnor triple linking number for complex link diagrams.
method Polyak-Viro type formula with explicit computation of configuration space integral.
result Formula applicable to diagrams with triple or more crossings.
We consider -dimensional linear stochastic approximation algorithms (LSAs) with a constant step-size and the so called Polyak-Ruppert (PR) averaging of iterates. LSAs are widely applied in machine learning and reinforcement learning (RL), where the aim is to compute an appropriate (that is a…
AGD converges in polynomial iterations to optimal matrix factorization.
problem Matrix factorization optimization with alternating gradient descent.
method Alternating gradient descent with fixed step size, proving convergence in polynomial iterations.
result AGD reaches ε-optimal factorization in T iterations with high probability.
Although it is known that the dimension of the Vassiliev invariants of degree three of long virtual knots is seven, the complete list of seven distinct Gauss diagram formulas have been unknown explicitly, where only one known formula was revised without proof. In this paper, we give seven Gauss diagram formulas to pres…
Proposes momentum methods for Lie groups, improving on classical algorithms.
problem Optimization on nonlinear spaces, especially Lie groups.
method Generalizes Nesterov's Accelerated Gradient method to Lie groups.
result Demonstrates faster convergence for NAG-like methods on Lie groups.