Cover Image

First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Beznosikov, Aleksandr, Samsonov, Sergey, Sheshukova, Marina, Gasnikov, Alexander, Naumov, Alexey, Moulines, Eric
Format:	Preprint
Published:	2023
Subjects:	Optimization and Control Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Statistical inference for Linear Stochastic Approximation with Markovian Noise
by: Samsonov, Sergey, et al.
Published: (2025)

Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation
by: Sheshukova, Marina, et al.
Published: (2024)

High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation
by: Levin, Ilya, et al.
Published: (2025)

Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity
by: Prokhorov, Boris, et al.
Published: (2026)

Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability
by: Samsonov, Sergey, et al.
Published: (2023)

Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities
by: Beznosikov, Aleksandr, et al.
Published: (2023)

Optimal Analysis of Method with Batching for Monotone Stochastic Finite-Sum Variational Inequalities
by: Pichugin, Alexander, et al.
Published: (2024)

SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning
by: Mangold, Paul, et al.
Published: (2024)

Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent
by: Sheshukova, Marina, et al.
Published: (2025)

Accelerated Methods with Compression for Horizontal and Vertical Federated Learning
by: Stanko, Sergey, et al.
Published: (2024)

Optimal Data Splitting in Distributed Optimization for Machine Learning
by: Medyakov, Daniil, et al.
Published: (2024)

Extragradient Sliding for Composite Non-Monotone Variational Inequalities
by: Emelyanov, Roman, et al.
Published: (2024)

Method with Batching for Stochastic Finite-Sum Variational Inequalities in Non-Euclidean Setting
by: Pichugin, Alexander, et al.
Published: (2024)

Methods for Solving Variational Inequalities with Markovian Stochasticity
by: Solodkin, Vladimir, et al.
Published: (2024)

UVIP: Model-Free Approach to Evaluate Reinforcement Learning Algorithms
by: Belomestny, Denis, et al.
Published: (2021)

Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust Algorithms
by: Beznosikov, Aleksandr, et al.
Published: (2020)

Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guarantees
by: Medyakov, Daniil, et al.
Published: (2025)

High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise
by: Gorbunov, Eduard, et al.
Published: (2023)

Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailed
by: Chezhegov, Savelii, et al.
Published: (2024)

Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation
by: Levin, Ilya, et al.
Published: (2026)

Refined Analysis of Federated Averaging and Federated Richardson-Romberg
by: Mangold, Paul, et al.
Published: (2024)

Accelerated Methods with Complexity Separation Under Data Similarity for Federated Learning Problems
by: Bylinkin, Dmitry, et al.
Published: (2026)

Activations and Gradients Compression for Model-Parallel Training
by: Rudakov, Mikhail, et al.
Published: (2024)

Rosenthal-type inequalities for linear statistics of Markov chains
by: Durmus, Alain, et al.
Published: (2023)

Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness
by: Kornilov, Nikita, et al.
Published: (2025)

Accelerated Methods with Compressed Communications for Distributed Optimization Problems under Data Similarity
by: Bylinkin, Dmitry, et al.
Published: (2024)

High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise
by: Kar, Avik, et al.
Published: (2026)

Accelerated Zero-Order SGD Method for Solving the Black Box Optimization Problem under "Overparametrization" Condition
by: Lobanov, Aleksandr, et al.
Published: (2023)

On the Rate of Gaussian Approximation for Linear Regression Problems
by: Khusainov, Marat, et al.
Published: (2025)

Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning
by: Bylinkin, Dmitry, et al.
Published: (2024)

Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shuffling
by: Medyakov, Daniil, et al.
Published: (2025)

Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions
by: Sadchikov, Andrey, et al.
Published: (2024)

Accelerated Stochastic Gradient Method with Applications to Consensus Problem in Markov-Varying Networks
by: Solodkin, Vladimir, et al.
Published: (2024)

Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features
by: Beznosikov, Aleksandr, et al.
Published: (2023)

Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning
by: Samsonov, Sergey, et al.
Published: (2024)

Effective Method with Compression for Distributed and Federated Cocoercive Variational Inequalities
by: Medyakov, Daniil, et al.
Published: (2024)

Random-reshuffled SARAH does not need a full gradient computations
by: Beznosikov, Aleksandr, et al.
Published: (2021)

Convergence of Clipped-SGD for Convex $(L_0,L_1)$-Smooth Optimization with Heavy-Tailed Noise
by: Chezhegov, Savelii, et al.
Published: (2025)

Power of Generalized Smoothness in Stochastic Convex Optimization: First- and Zero-Order Algorithms
by: Lobanov, Aleksandr, et al.
Published: (2025)

The Black-Box Optimization Problem: Zero-Order Accelerated Stochastic Method via Kernel Approximation
by: Lobanov, Aleksandr, et al.
Published: (2023)