Fast Gradient Descent for Convex Minimization Problems with an Oracle Producing a (δ, L)-Model of Function at the Requested Point

A. Gasnikov; A. Tyurin

doi:10.1134/S0965542519070078

Publications

?

Fast Gradient Descent for Convex Minimization Problems with an Oracle Producing a (δ, L)-Model of Function at the Requested Point

Computational Mathematics and Mathematical Physics. 2019. Vol. 59. No. 7. P. 1085–1097.

Gasnikov A., Tyurin A.

A new concept of (δ ,L)-model of a function that is a generalization of the Devolder–Glineur–Nesterov (δ ,L)-oracle is proposed. Within this concept, the gradient descent and fast gradient descent methods are constructed and it is shown that constructs of many known methods (composite methods, level methods, conditional gradient and proximal methods) are particular cases of the methods proposed in this paper.

Language: English

DOI

Keywords: composite optimization conditional gradient method fast gradient descent gradient descent

Publication based on the results of:

Uncertainty quantification in high-dimensional statistics (2019)

ICC 2021-IEEE International Conference on Communications

Белоголовый А. В., IEEE, 2021.

In this paper, we present a gradient descent and Metropolis-Hastings (MH) principle based low-complexity, highly parallelizable, near-optimal MIMO demodulation framework. The optimal maximum-likelihood (ML) demodulation is a discrete optimization problem and is computationally infeasible for large MIMO dimensions. Many continuous-relaxed versions of ML, such as least-squares (LS) demodulation, have closedform solutions but are highly suboptimal to ML. However, the continuous surface ...

Added: April 7, 2026

Trade-off between memory usage and optimization speed in a simple machine learning task

Горюнов О. А., Соловьев И. А., Klinshov V., Proceedings of 2025 9th Scientific School Dynamics of Complex Networks and their Applications (DCNA), Publisher IEEE, Electronic ISSN: 2770-744X Print on Demand(PoD) ISSN: 2770-7431 2025 P. 42–44

—In modern machine learning, the efficiency of train ing is heavily influenced by the choice of optimization algorithm, with preconditioned methods offering significant speed improve ments at the cost of increased memory usage. This study explores the trade-off between memory consumption and optimization performance by generalizing the Shampoo preconditioning al gorithm to support arbitrarily sized ...

Added: November 12, 2025

Gradient descent clustering with regularization to recover communities in transformed attributed networks

Shalileh S., Social Network Analysis and Mining 2025 Vol. 15212 P. 137–148

Community detection in attributed networks aims to recover clusters in which the within-community nodes are as interconnected and as homogeneous as possible, while the between-communities nodes are as disconnected and as heterogeneous as possible. The current research proposes a straightforward data-driven model with an integrated regularization term to recover communities. For further improvement of the ...

Added: November 30, 2024

Inexact model: a framework for optimization and variational inequalities

Stonyakin F., Tyurin A., Gasnikov A. et al., Optimization Methods and Software 2021 Vol. 36 No. 6 P. 1155–1201

In this paper, we propose a general algorithmic framework for the first-order methods in optimization in a broad sense, including minimization problems, saddle-point problems and variational inequalities (VIs). This framework allows obtaining many known methods as a special case, the list including accelerated gradient method, composite optimization methods, level-set methods, Bregman proximal methods. The idea ...

Added: October 29, 2021

Derivative-Free Method For Composite Optimization With Applications To Decentralized Distributed Optimization

Beznosikov A., Gorbunov E., Gasnikov A., IFAC-PapersOnLine 2021 Vol. 53 No. 2 P. 4038–4043

In this paper, we propose a new method based on the Sliding Algorithm from Lan (2016, 2019) for the convex composite optimization problem that includes two terms: smooth one and non-smooth one. Our method uses the stochastic noised zeroth-order oracle for the non-smooth part and the first-order oracle for the smooth part and it is ...

Added: October 14, 2021

Accelerated and Unaccelerated Stochastic Gradient Descent in Model Generality

Dvinskikh D., Tyurin A., Gasnikov A. et al., Mathematical notes 2020 Vol. 108 No. 3-4 P. 511–522

A new method for deriving estimates of the rate of convergence of optimal methods for solving problems of smooth (strongly) convex stochastic optimization is described. The method is based on the results of stochastic optimization derived from results on the convergence of optimal methods under the conditions of inexact gradients with small noises of nonrandom ...

Added: February 5, 2021

Composite optimization for the resource allocation problem

Ivanova A., Dvurechensky P., Gasnikov A. et al., Optimization Methods and Software 2021 Vol. 36 No. 4 P. 720–754

In this paper, we consider resource allocation problem stated as a convex minimization problem with linear constraints. To solve this problem, we use gradient and accelerated gradient descent applied to the dual problem and prove the convergence rate both for the primal iterates and the dual iterates. We obtain faster convergence rates than the ones ...

Added: August 4, 2020