Cover Image

Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bai, Cedar Site, Bullins, Brian
Format:	Preprint
Published:	2024
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

Faster Acceleration for Steepest Descent
by: Bai, Cedar Site, et al.
Published: (2024)

Federated Composite Saddle Point Optimization
by: Bai, Site, et al.
Published: (2023)

Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points
by: Vyas, Abhijeet, et al.
Published: (2026)

Tight Bounds for Online Convex Optimization with Adversarial Constraints
by: Sinha, Abhishek, et al.
Published: (2024)

Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles
by: Ji, Kaiyi
Published: (2025)

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

On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms
by: Kovalev, Dmitry, et al.
Published: (2024)

Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm
by: Wu, Yuman, et al.
Published: (2026)

Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness
by: Crawshaw, Michael, et al.
Published: (2025)

Non-Euclidean High-Order Smooth Convex Optimization
by: Contreras, Juan Pablo, et al.
Published: (2024)

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

Muon Converges under Heavy-Tailed Noise: Nonconvex Hölder-Smooth Empirical Risk Minimization
by: Iiduka, Hideaki
Published: (2026)

New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition
by: Saad, El Mehdi, et al.
Published: (2025)

Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness
by: Zhao, Yuheng, et al.
Published: (2025)

Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance
by: Fazla, Arda, et al.
Published: (2026)

Stacey: Promoting Stochastic Steepest Descent via Accelerated $\ell_p$-Smooth Nonconvex Optimization
by: Luo, Xinyu, et al.
Published: (2025)

A Unified Lyapunov-IQC Framework for Uniform Stability of Smooth Quadratic First-Order Accelerated Optimizers
by: Li, Don, et al.
Published: (2026)

Smooth Quasar-Convex Optimization with Constraints
by: Martínez-Rubio, David
Published: (2025)

Beyond First-Order Methods for $\ell_p$-Structured Non-Monotone Variational Inequalities
by: Vyas, Abhijeet, et al.
Published: (2026)

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)

Tight Generalization Bounds for Noiseless Inverse Optimization
by: Fatemi, Pouria, 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)

On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Łojasiewicz Condition
by: Bai, Yunyan, et al.
Published: (2024)

On Convergence of Incremental Gradient for Non-Convex Smooth Functions
by: Koloskova, Anastasia, et al.
Published: (2023)

Stochastic Non-Smooth Convex Optimization with Unbounded Gradients
by: Kovalev, Dmitry
Published: (2026)

Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization
by: Armacki, Aleksandar, et al.
Published: (2026)

Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity
by: Cao, Daniel Yiming, et al.
Published: (2025)

Model Immunization from a Condition Number Perspective
by: Zheng, Amber Yijia, et al.
Published: (2025)

An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization
by: Cao, Jincheng, et al.
Published: (2024)

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

Provable Reduction in Communication Rounds for Non-Smooth Convex Federated Learning
by: Palenzuela, Karlo, et al.
Published: (2025)

Byzantine-Robust Distributed SGD: A Unified Analysis and Tight Error Bounds
by: Ruan, Boyuan, et al.
Published: (2026)

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

Methods with Local Steps and Random Reshuffling for Generally Smooth Non-Convex Federated Optimization
by: Demidovich, Yury, et al.
Published: (2024)

Adam-SHANG: A Convergent Adam-Type Method for Stochastic Smooth Convex Optimization
by: Yu, Yaxin, et al.
Published: (2026)

Tight Lower Bounds for the Bit and Inner Product Oracle for Constrained Convex Optimization
by: Basu, Amitabh, et al.
Published: (2025)

Universal Online Convex Optimization Meets Second-order Bounds
by: Zhang, Lijun, et al.
Published: (2021)

Can Entry-Wise Clipping Give Spectral Control of Stochastic Gradients?
by: Song, Zitao, et al.
Published: (2026)

AdaGrad under Anisotropic Smoothness
by: Liu, Yuxing, et al.
Published: (2024)

Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing
by: Aghasi, Alireza, et al.
Published: (2024)