?
Об ускоренных методах поиска канонического тензорного разложения
Труды Московского физико-технического института. 2020. Т. 12. № 4(48). С. 61–71.
Tupitsa N., Меркулов Д. М.
Language:
Russian
Keywords: выпуклая оптимизация
Beznosikov A., Kormakov G., Grigorievskiy A. et al., Journal of Optimization Theory and Applications 2026 Vol. 209 Article 18
The objective of Vertical Federated Learning (VFL) is to collectively train a model using features available on different devices while sharing the same users. This paper focuses on the saddle point reformulation of the VFL problem via the classical Lagrangian function. We first demonstrate how this formulation can be solved using deterministic methods.More importantly, we explore various stochastic modifications to ...
Added: June 17, 2026
Gladin E., Alkousa M., Gasnikov A., Automation and Remote Control 2021 Vol. 82 P. 1679–1691
The article deals with some approaches to solving convex problems of the min-min type with smoothness and strong convexity in only one of the two groups of variables. It is shown that the proposed approaches based on Vaidya’s method, the fast gradient method, and the accelerated gradient method with variance reduction have linear convergence. It ...
Added: November 29, 2024
Gladin E., Gasnikov A., Ermakova E., Mathematical notes 2022 Vol. 112 No. 1 P. 183–190
The paper deals with a general problem of convex stochastic optimization in a space of small dimension (for example, 100 variables). It is known that for deterministic problems of convex optimization in small dimensions, the methods of centers of gravity type (for example, Vaidya’s method) provide the best convergence. For stochastic optimization problems, the question ...
Added: November 29, 2024
Gladin E., Gasnikov A., Dvurechensky P., Journal of Optimization Theory and Applications 2025 Vol. 204 No. 1 Article 1
Accuracy certificates for convex minimization problems allow for online verification of the accuracy of approximate solutions and provide a theoretically valid online stopping criterion. When solving the Lagrange dual problem, accuracy certificates produce a simple way to recover an approximate primal solution and estimate its accuracy. In this paper, we generalize accuracy certificates for the ...
Added: November 29, 2024
Gladin E., Зайнуллина К. Э., Компьютерные исследования и моделирование 2021 Т. 13 № 6 С. 1137–1147
The article considers minimization of the expectation of convex function. Problems of this type often arise in machine learning and a variety of other applications. In practice, stochastic gradient descent (SGD) and similar procedures are usually used to solve such problems. We propose to use the ellipsoid method with mini-batching, which converges linearly and can ...
Added: November 29, 2024
Rudenko V., Yudin N., Васин А. А., Компьютерные исследования и моделирование 2023 Т. 15 № 2 С. 329–353
This article reviews both historical achievements and modern results in the field of Markov Decision Process (MDP) and convex optimization. This review is the first attempt to cover the field of reinforcement learning in Russian in the context of convex optimization. The fundamental Bellman equation and the criteria of optimality of policy — strategies based on it, ...
Added: November 29, 2024
Puchkin N., Gorbunov E., Kutuzov N. et al., , in: Proceedings of The 27th International Conference on Artificial Intelligence and Statistics (AISTATS 2024), 2-4 May 2024, Palau de Congressos, Valencia, Spain. PMLR: Volume 238Vol. 238.: Valencia: PMLR, 2024. P. 856–864.
We consider stochastic optimization problems with heavy-tailed noise with structured density. For such problems, we show that it is possible to get faster rates of convergence than 𝑂(𝐾^{−2(𝛼−1)/𝛼}), when the stochastic gradients have finite 𝛼-th moment, 𝛼∈(1,2]. In particular, our analysis allows the noise norm to have an unbounded expectation. To achieve these results, we stabilize stochastic gradients, ...
Added: April 22, 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
Воронцова Е. А., Gasnikov A., Gorbunov E., Автоматика и телемеханика 2019 Т. 80 № 4 С. 126–143
We consider smooth convex optimization problems whose full gradient is not available for their numerical solution. In 2011, Yu.E. Nesterov proposed accelerated gradient-free methods for solving such problems. Since only unconditional optimization problems were considered, Euclidean prox-structures were used. However, if one knows in advance, say, that the solution to the problem is sparse, or ...
Added: October 10, 2020
Воронцова Е. А., Gasnikov A., Gorbunov E. et al., Автоматика и телемеханика 2019 № 8 С. 149–168
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: October 10, 2020
Ingacheva A., Кохан В. В., Ershov E. et al., Сенсорные системы 2018 Т. 32 № 4 С. 332–341
In this paper we consider the task of inner objects mapping for the building with a bunch of moving around it autonomous agents which use narrow beam of radio waves using WiFi frequency (2.4 GHz). Linear model of pixel-wise radio waves attenuation is considered. SIRT algorithm with TV and Tikhonov regularizations is used for the ...
Added: February 9, 2020
Gasnikov A., Tyurin A., Журнал вычислительной математики и математической физики 2019 Т. 59 № 7 С. 1137–1150
Предлагается новая концепция ( δ, L ) -модели функции, которая обобщает концепцию ( δ, L ) -оракула Деволдера–Глинера–Нестерова. В рамках этой концепции строятся градиентный спуск, быстрый градиентный спуск и показывается, что многие известные ранее конструкции методов (композитные методы, методы уровней, метод условных градиентов, проксимальные методы) являются частными случаями предложенных в данной работе методов. ...
Added: December 8, 2018
Gasnikov A., Баяндина А. С., Лагуновская А. А., Автоматика и телемеханика 2018 № 8 С. 38–49
Изучаются негладкие выпуклые задачи стохастической оптимизации с двухточечным оракулом нулевого порядка, т.е. на каждой итерации наблюдению доступны значения реализации функции в двух выбранных точках. Эти задачи предварительно сглаживаются с помощью известной техники двойного сглаживания (Б. Т. Поляк), а затем решаются с помощью стохастического метода зеркального спуска. Получены условия на допустимый уровень шума неслучайной природы, проявляющегося при вычислении реализации функции, при котором сохраняется ...
Added: October 31, 2018
Dvurechensky P., Gasnikov A., Gasnikova E. et al., В кн.: Proceedings of DOOR 2016 Conference, special issue of CEUR Workshop ProceedingsVol. 1623.: CEUR Workshop Proceedings, 2016. С. 584–595.
In this paper, we consider a large class of hierarchical congestion population games. One can show that the equilibrium in a game of such type can be described as a minimum point in a properly constructed multi-level convex optimization problem. We propose a fast primal-dual composite gradient method and apply it to the problem, which ...
Added: November 17, 2017
Akimov P. A., Matasov A. I., IEEE Transactions on Automatic Control 2015 Vol. 60 No. 4 P. 1050–1063
The mixed-norm cost functions arise in many applied optimization problems. As an important example, we consider the state estimation problem for a linear dynamic system under a nonclassical assumption that some entries of state vector admit jumps in their trajectories. The estimation problem is solved by means of mixed l1/l2-norm approximation. This approach combines the ...
Added: November 5, 2017
Chepyzhov V. V., Бедринцев А. А., Чернова С. С., Искусственный интеллект и принятие решений 2015 № 2 С. 35–44
This paper proposes an approach to obtaining of the set of admissible values of the optimization variables (design space) in the form of extreme ellipsoids describing a given set of points and inscribed in a given set of linear constraints. Considered ellipsoids include Principal Component’s ellipsoid, minimal volume ellipsoid and ellipsoid with minimal trace of ...
Added: March 25, 2016