Cover Image

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kim, Donghwa, Lee, Jaewook, Yun, Chulhee
Format:	Preprint
Published:	2025
Subjects:	Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fundamental Benefit of Alternating Updates in Minimax Optimization
by: Lee, Jaewook, et al.
Published: (2024)

Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements
by: Chae, Jiseok, et al.
Published: (2024)

Nesterov Acceleration with Operator Decomposition
by: Lee, Jaewook, et al.
Published: (2026)

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
by: Kim, Yujun, et al.
Published: (2025)

Convergence and Implicit Bias of Gradient Descent on Continual Linear Classification
by: Jung, Hyunji, et al.
Published: (2025)

Gradient Descent with Polyak's Momentum Finds Flatter Minima via Large Catapults
by: Phunyaphibarn, Prin, et al.
Published: (2023)

Through the River: Understanding the Benefit of Schedule-Free Methods for Language Model Training
by: Song, Minhak, et al.
Published: (2025)

The Randomized Block Coordinate Descent Method in the Hölder Smooth Setting
by: Maia, Leandro Farias, et al.
Published: (2024)

Revisiting Stochastic Gradient Descent for Strongly Convex Objectives: Tight Uniform-in-Time Bounds
by: Chen, Kang, et al.
Published: (2025)

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
by: Vaswani, Sharan, et al.
Published: (2025)

Scaling Laws of SignSGD in Linear Regression: When Does It Outperform SGD?
by: Kim, Jihwan, et al.
Published: (2026)

Distributed Stochastic Block Coordinate Descent for Time-Varying Multi-Agent Optimization
by: Yu, Zhan, et al.
Published: (2019)

High-Probability Guarantees for Random Zeroth-Order (Stochastic) Gradient Descent
by: Ye, Haishan
Published: (2026)

Random Coordinate Descent on the Wasserstein Space of Probability Measures
by: Xu, Yewei, et al.
Published: (2026)

Does SGD really happen in tiny subspaces?
by: Song, Minhak, et al.
Published: (2024)

Quantum Natural Stochastic Pairwise Coordinate Descent
by: Sohail, Mohammad Aamir, et al.
Published: (2024)

The Sample Complexity of Gradient Descent in Stochastic Convex Optimization
by: Livni, Roi
Published: (2024)

Provably Convergent Plug-and-play Proximal Block Coordinate Descent Method for Hyperspectral Anomaly Detection
by: Liu, Xiaoxia, et al.
Published: (2024)

Differentially Private Random Block Coordinate Descent
by: Maranjyan, Artavazd, et al.
Published: (2024)

Learning Provably Improves the Convergence of Gradient Descent
by: Song, Qingyu, et al.
Published: (2025)

Frictionless Hamiltonian Descent and Coordinate Hamiltonian Descent for Strongly Convex Quadratic Problems
by: Wang, Jun-Kun
Published: (2024)

Implicit Bias of Per-sample Adam on Separable Data: Departure from the Full-batch Regime
by: Baek, Beomhan, et al.
Published: (2025)

Stochastic Adaptive Gradient Descent Without Descent
by: Aujol, Jean-François, et al.
Published: (2025)

Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent
by: Chu, Ya-Chi, et al.
Published: (2025)

Efficient Online Mirror Descent Stochastic Approximation for Multi-Stage Stochastic Programming
by: Zhang, Junhui, et al.
Published: (2025)

Stochastic Modified Equations for Stochastic Gradient Descent in Infinite-Dimensional Hilbert Spaces
by: Cerrai, Sandra, et al.
Published: (2026)

Block Coordinate Descent Network Simplex Methods for Optimal Transport
by: Li, Lingrui, et al.
Published: (2025)

Momentum Benefits Non-IID Federated Learning Simply and Provably
by: Cheng, Ziheng, et al.
Published: (2023)

Random Function Descent
by: Benning, Felix, et al.
Published: (2023)

Generalized Stochastic Gradient Descent with Momentum Methods for Smooth Optimization
by: Wang, Zimeng, et al.
Published: (2026)

A Randomized Block-Coordinate Primal-Dual Method for Large-scale Stochastic Saddle Point Problems
by: Hamedani, Erfan Yazdandoost, et al.
Published: (2019)

Provably Faster Gradient Descent via Long Steps
by: Grimmer, Benjamin
Published: (2023)

Provable Phase Retrieval with Mirror Descent
by: Godeme, Jean-Jacques, et al.
Published: (2022)

Convergence of Steepest Descent and Adam under Non-Uniform Smoothness
by: Vaswani, Sharan, et al.
Published: (2026)

Stochastic Gradient Descent with Strategic Querying
by: Jiang, Nanfei, et al.
Published: (2025)

Stochastic Gradient Descent with Adaptive Data
by: Che, Ethan, et al.
Published: (2024)

An Adaptive and Parameter-Free Nesterov's Accelerated Gradient Method for Convex Optimization
by: Suh, Jaewook J., et al.
Published: (2025)

Momentum Does Not Reduce Stochastic Noise in Stochastic Gradient Descent
by: Sato, Naoki, et al.
Published: (2024)

Approximating the Uniform Value in Hidden Stochastic Games with Doeblin Conditions
by: Chatterjee, Krishnendu, et al.
Published: (2026)

Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization
by: Jiang, Ruichen, et al.
Published: (2024)