?
Algorithms for Solving Variational Inequalities and Saddle Point Problems with Some Generalizations of Lipschitz Property for Operators
Ch. 6. P. 86–101.
Titov A., Stonyakin F., Alkousa M., Gasnikov A.
Agafonov A., Petr Ostroukhov, Mozhaev R. et al., , in: 38th Conference on Neural Information Processing Systems (NeurIPS 2024).: [б.и.], 2024. P. 115816–115860.
Variational inequalities represent a broad class of problems, including minimization and min-max problems, commonly found in machine learning. Existing second-order and high-order methods for variational inequalities require precise computation of derivatives, often resulting in prohibitively high iteration costs. In this work, we study the impact of Jacobian inaccuracy on second-order methods. For the smooth and ...
Added: July 15, 2025
Statkevich E., Bondar S., Dvinskikh D. et al., Chaos, Solitons and Fractals: X 2024 Vol. 185 Article 115048
This paper focuses on solving a stochastic saddle point problem (SPP) under an overparameterized regime for the case, when the gradient computation is impractical. As an intermediate step, we generalize Same-sample Stochastic Extra-gradient algorithm (Gorbunov et al., 2022) to a biased oracle and estimate novel convergence rates. As the result of the paper we introduce ...
Added: February 7, 2025
Чупров И. А., Gao J., Efremenko D. et al., Светотехника (перевод) 2024 Vol. 32 P. 11–19
The retrieval of parameters for a turbid medium presents a challenging and ill-posed inverse problem. In this paper, we investigate the effectiveness of utilizing global optimization algorithms to determine optical properties of the medium such as the optical thickness, the single scattering albedo, the single scattering phase function, and the extinction profile from multi-angle radiance ...
Added: February 7, 2025
Gladin E., Sadiev A., Gasnikov A. et al., , in: Mathematical Optimization Theory and Operations Research: 20th International Conference, MOTOR 2021, Irkutsk, Russia, July 5–10, 2021, Proceedings.: Cham: Springer, 2021. P. 19–40.
In this paper, we consider two types of problems that have some similarity in their structure, namely, min-min problems and min-max saddle-point problems. Our approach is based on considering the outer minimization problem as a minimization problem with an inexact oracle. This inexact oracle is calculated via an inexact solution of the inner problem, which ...
Added: November 29, 2024
Gladin E., Borodich E., Computer Research and Modeling 2022 Vol. 14 No. 2 P. 257–275
The paper is devoted to convex-concave saddle point problems where the objective is a sum of a large number of functions. Such problems attract considerable attention of the mathematical community due to the variety of applications in machine learning, including adversarial learning, adversarial attacks and robust reinforcement learning, to name a few. The individual functions ...
Added: November 29, 2024
Rogozin A., Beznosikov A., Dvinskikh D. et al., Optimization Methods and Software 2025 Vol. 40 No. 5 P. 1127–1152
We consider smooth convex-concave saddle point problems in the decentralized distributed setting, where a finite-sum objective is distributed among the nodes of a computational network. At each node, the local objective depends on the groups of local and global variables. For such problems, we propose a decentralized distributed algorithm with O(ϵ−1) communication and oracle calls complexities to ...
Added: March 26, 2024
Beznosikov A., Samsonov S., Sheshukova M. et al., , in: Advances in Neural Information Processing Systems 36 (NeurIPS 2023).: Curran Associates, Inc., 2023. P. 44820–44835.
This paper delves into stochastic optimization problems that involve Markovian noise. We present a unified approach for the theoretical analysis of first-order gradient methods for stochastic optimization and variational inequalities. Our approach covers scenarios for both non-convex and strongly convex minimization problems. To achieve an optimal (linear) dependence on the mixing time of the underlying ...
Added: February 17, 2024
Beznosikov A., Richtarik P., Diskin M. et al., , in: Thirty-Sixth Conference on Neural Information Processing Systems : NeurIPS 2022.: Curran Associates, Inc., 2022. P. 14013–14029.
Added: January 27, 2023
Gladin E., Sadiev A., Gasnikov A. et al., Communications in Computer and Information Science 2021 Vol. 1476 P. 19–40
In this paper, we consider two types of problems that have some similarity in their structure, namely, min-min problems and min-max saddle-point problems. Our approach is based on considering the outer minimization problem as a minimization problem with an inexact oracle. This inexact oracle is calculated via an inexact solution of the inner problem, which ...
Added: October 14, 2021
Sadiev A., Beznosikov A., Dvurechensky P. et al., Communications in Computer and Information Science 2021 Vol. 1476 P. 71–85
Saddle-point problems have recently gained an increased attention from the machine learning community, mainly due to applications in training Generative Adversarial Networks using stochastic gradients. At the same time, in some applications only a zeroth-order oracle is available. In this paper, we propose several algorithms to solve stochastic smooth (strongly) convex-concave saddle-point problems using zeroth-order ...
Added: October 14, 2021
Beznosikov A., Sadiev A., Gasnikov A., Communications in Computer and Information Science 2020 Vol. 1275 P. 105–119
In the paper, we generalize the approach Gasnikov et al. 2017, which allows to solve (stochastic) convex optimization problems with an inexact gradient-free oracle, to the convex-concave saddle-point problem. The proposed approach works, at least, like the best existing approaches. But for a special set-up (simplex type constraints and closeness of Lipschitz constants in 1 ...
Added: October 14, 2021
Vorontsova E., Gasnikov A., Dvurechensky P. et al., Automation and Remote Control 2019 Vol. 80 No. 8 P. 1487–1501
We propose an accelerated gradient-free method with a non-Euclidean proximal operator associated with the p-norm (1 ⩽ p ⩽ 2). We obtain estimates for the rate of convergence of the method under low noise arising in the calculation of the function value. We present the results of computational experiments. ...
Added: December 10, 2019
NY: Springer, 2013.
Optimization, simulation and control are very powerful tools in engineering and mathematics, and play an increasingly important role. Because of their various real-world applications in industries such as finance, economics, and telecommunications, research in these fields is accelerating at a rapid pace, and there have been major algorithmic and theoretical developments in these fields in ...
Added: December 19, 2012