9 papers
Information-Theoretic Upper Bounds for Deterministic Noise in Zeroth-Order Convex Optimization
Dmitry Pasechnyuk-Vilensky, Igor Pavlov, Martin TakÃ¡Ä +1
We study deterministic adversarial noise in zeroth-order convex optimization on Euclidean balls. The maximum admissible level of noise is the largest uniform error in function-valu…
Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees
Artem Agafonov, Vladislav Ryspayev, Samuel Horváth +3
Quasi-Newton methods are widely used for solving convex optimization problems due to their ease of implementation, practical efficiency, and strong local convergence guarantees. Ho…
Norm-Constrained Flows and Sign-Based Optimization: Theory and Algorithms
Valentin Leplat, Sergio Mayorga, Roland Hildebrand +1
Sign Gradient Descent (SignGD) uses only the coordinate-wise sign of the gradient. We study this method through norm-constrained continuous-time dynamics: at each point, the veloci…
Power of Generalized Smoothness in Stochastic Convex Optimization: First- and Zero-Order Algorithms
Aleksandr Lobanov, Alexander Gasnikov
This paper is devoted to the study of stochastic optimization problems under the generalized smoothness assumption. By considering the unbiased gradient oracle in Stochastic Gradie…
Linear Convergence Rate in Convex Setup is Possible! Gradient Descent Method Variants under -Smoothness
Aleksandr Lobanov, Alexander Gasnikov, Eduard Gorbunov +1
The gradient descent (GD) method -- is a fundamental and likely the most popular optimization algorithm in machine learning (ML), with a history traced back to a paper in 1847 (Cau…
Decentralised convex optimisation with probability-proportional-to-size quantization
Dmitrii Pasechniuk, Pavel Dvurechensky, César A. Uribe +1
Communication is one of the bottlenecks of distributed optimisation and learning. To overcome this bottleneck, we propose a novel quantization method that transforms a vector into…