Cover Image

Median Clipping for Zeroth-order Non-Smooth Convex Optimization and Multi-Armed Bandit Problem with Heavy-tailed Symmetric Noise

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kornilov, Nikita, Dorn, Yuriy, Lobanov, Aleksandr, Kutuzov, Nikolay, Shibaev, Innokentiy, Gorbunov, Eduard, Nazin, Alexander, Gasnikov, Alexander
Format:	Preprint
Published:	2024
Subjects:	Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise
by: Gorbunov, Eduard, et al.
Published: (2021)

Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems
by: Puchkin, Nikita, et al.
Published: (2023)

Linear Convergence Rate in Convex Setup is Possible! Gradient Descent Method Variants under $(L_0,L_1)$-Smoothness
by: Lobanov, Aleksandr, et al.
Published: (2024)

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

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

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 Zero-Order SGD Method for Solving the Black Box Optimization Problem under "Overparametrization" Condition
by: Lobanov, Aleksandr, et al.
Published: (2023)

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

Randomized gradient-free methods in convex optimization
by: Gasnikov, Alexander, et al.
Published: (2022)

Avoiding Bias in Clipped SGD for Overparameterized Models under Generalized Smoothness
by: Lobanov, Aleksandr, et al.
Published: (2026)

Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values
by: Lobanov, Aleksandr, et al.
Published: (2024)

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

Optimal Flow Matching: Learning Straight Trajectories in Just One Step
by: Kornilov, Nikita, et al.
Published: (2024)

Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity
by: Gorbunov, Eduard, et al.
Published: (2024)

Stochastic Decentralized Optimization of Non-Smooth Convex and Convex-Concave Problems over Time-Varying Networks
by: Divilkovskiy, Maxim, et al.
Published: (2025)

Nesterov's method of dichotomy via Order Oracle: The problem of optimizing a two-variable function on a square
by: Chervonenkis, Boris, et al.
Published: (2024)

Geometry-Aware Multi-Armed Bandits for Antenna Beam Selection on Spheres, Tori, $\SO(3)$, and Reconfigurable Intelligent Surfaces
by: Dorn, Yuriy, et al.
Published: (2026)

Improved Iteration Complexity in Black-Box Optimization Problems under Higher Order Smoothness Function Condition
by: Lobanov, Aleksandr
Published: (2024)

Exploring Applications of State Space Models and Advanced Training Techniques in Sequential Recommendations: A Comparative Study on Efficiency and Performance
by: Obozov, Mark, et al.
Published: (2024)

On the Equivalence of Optimal Transport Problem and Action Matching with Optimal Vector Fields
by: Kornilov, Nikita, et al.
Published: (2025)

UCB-type Algorithm for Budget-Constrained Expert Learning
by: Latypov, Ilgam, et al.
Published: (2025)

Gradient-free algorithm for saddle point problems under overparametrization
by: Statkevich, Ekaterina, et al.
Published: (2024)

Accelerated zero-order SGD under high-order smoothness and overparameterized regime
by: Bychkov, Georgii, et al.
Published: (2024)

Optimal spanning tree reconstruction in symbolic regression
by: Neychev, Radoslav G., et al.
Published: (2024)

Optimizing Online Advertising with Multi-Armed Bandits: Mitigating the Cold Start Problem under Auction Dynamics
by: Soboleva, Anastasiia, et al.
Published: (2025)

Last Iterate Convergence of AdaGrad-Norm for Convex Non-Smooth Optimization
by: Preobrazhenskaia, Margarita, et al.
Published: (2026)

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

About some works of Boris Polyak on convergence of gradient methods and their development
by: Ablaev, Seydamet, et al.
Published: (2023)

VK-LSVD: A Large-Scale Industrial Dataset for Short-Video Recommendation
by: Poslavsky, Aleksandr, et al.
Published: (2026)

SCOPE: Smooth Convex Optimization for Planned Evolution of Deformable Linear Objects
by: Jnadi, Ali, et al.
Published: (2026)

Differentially Private Clipped-SGD: High-Probability Convergence with Arbitrary Clipping Level
by: Khah, Saleh Vatan, et al.
Published: (2025)

Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks
by: Kovalev, Dmitry, et al.
Published: (2024)

Manifold-Aware Information Gain and Lower Bounds for Gaussian-Process Bandits on Riemannian Quotient Spaces
by: Dorn, Yuriy, et al.
Published: (2026)

Shortfall-Aware Decomposed Allocation with Repair for Heterogeneous GPU Clusters: Reproduction Artifact
by: Dorn, Yuriy
Published: (2026)

AdLoCo: adaptive batching significantly improves communications efficiency and convergence for Large Language Models
by: Kutuzov, Nikolay, et al.
Published: (2025)

Smoothed Gradient Clipping and Error Feedback for Decentralized Optimization under Symmetric Heavy-Tailed Noise
by: Yu, Shuhua, et al.
Published: (2023)

Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences
by: Malinovsky, Grigory, 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)

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

Double Momentum and Error Feedback for Clipping with Fast Rates and Differential Privacy
by: Islamov, Rustem, et al.
Published: (2025)