351 citations · 835 across the 27 of their papers we have counts for
27 papers
Mirror descent algorithms with logarithmic barriers
Alberto De Marchi, Yura Malitsky, Adrien B. Taylor
This work derives convergence guarantees for mirror descent and proximal mirror descent algorithms when a logarithmic barrier is used as a distance-generating function. Standard ap…
Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias
Yura Malitsky, Alexander Posch
This paper focuses on applying entropic mirror descent to solve linear systems, where the main challenge for the convergence analysis stems from the unboundedness of the domain. To…
Adaptive Gradient Descent on Riemannian Manifolds with Nonnegative Curvature
Aban Ansari-Önnestam, Yura Malitsky
In this paper, we present an adaptive gradient descent method for geodesically convex optimization on a Riemannian manifold with nonnegative sectional curvature. The method automat…
Towards Weaker Variance Assumptions for Stochastic Optimization
Ahmet Alacaoglu, Yura Malitsky, Stephen J. Wright
We revisit a classical assumption for analyzing stochastic gradient algorithms where the squared norm of the stochastic subgradient (or the variance for smooth problems) is allowed…
A First-Order Algorithm for Decentralised Min-Max Problems
Yura Malitsky, Matthew K. Tam
In this work, we consider a connected network of finitely many agents working cooperatively to solve a min-max problem with convex-concave structure. We propose a decentralised fir…
Adaptive Proximal Gradient Method for Convex Optimization
Yura Malitsky, Konstantin Mishchenko
In this paper, we explore two fundamental first-order algorithms in convex optimization, namely, gradient descent (GD) and proximal gradient method (ProxGD). Our focus is on making…
Beyond the Golden Ratio for Variational Inequality Algorithms
Ahmet Alacaoglu, Axel Böhm, Yura Malitsky
We improve the understanding of the , which solves monotone variational inequalities (VI) and convex-concave min-max problems via the distinctive f…
Over-the-Air Computation for Distributed Systems: Something Old and Something New
Zheng Chen, Erik G. Larsson, Carlo Fischione +2
Facing the upcoming era of Internet-of-Things and connected intelligence, efficient information processing, computation, and communication design becomes a key challenge in large-s…
Over-the-Air Computation with Multiple Receivers: A Space-Time Approach
Zheng Chen, Yura Malitsky
The emerging concept of Over-the-Air (OtA) computation has shown great potential for achieving resource-efficient data aggregation across large wireless networks. However, current…
Distributed Forward-Backward Methods for Ring Networks
Francisco J. Aragón-Artacho, Yura Malitsky, Matthew K. Tam +1
In this work, we propose and analyse forward-backward-type algorithms for finding a zero of the sum of finitely many monotone operators, which are not based on reduction to a two o…
A first-order primal-dual method with adaptivity to local smoothness
Maria-Luiza Vladarean, Yura Malitsky, Volkan Cevher
We consider the problem of finding a saddle point for the convex-concave objective , where is a convex function with locally…
Resolvent Splitting for Sums of Monotone Operators with Minimal Lifting
Yura Malitsky, Matthew K. Tam
In this work, we study fixed point algorithms for finding a zero in the sum of maximally monotone operators by using their resolvents. More precisely, we consider the cla…
Stochastic Variance Reduction for Variational Inequality Methods
Ahmet Alacaoglu, Yura Malitsky
We propose stochastic variance reduced algorithms for solving convex-concave saddle point problems, monotone variational inequalities, and monotone inclusions. Our framework applie…
Convergence of adaptive algorithms for weakly convex constrained optimization
Ahmet Alacaoglu, Yura Malitsky, Volkan Cevher
We analyze the adaptive first order algorithm AMSGrad, for solving a constrained stochastic optimization problem with a weakly convex objective. We prove the $\mathcal{\tilde O}(t^…
A new regret analysis for Adam-type algorithms
Ahmet Alacaoglu, Yura Malitsky, Panayotis Mertikopoulos +1
In this paper, we focus on a theory-practice gap for Adam and its variants (AMSgrad, AdamNC, etc.). In practice, these algorithms are used with a constant first-order moment parame…
Adaptive Gradient Descent without Descent
Yura Malitsky, Konstantin Mishchenko
We present a strikingly simple proof that two rules are sufficient to automate gradient descent: 1) don't increase the stepsize too fast and 2) don't overstep the local curvature.…
Revisiting Stochastic Extragradient
Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin +2
We fix a fundamental issue in the stochastic extragradient method by providing a new sampling strategy that is motivated by approximating implicit updates. Since the existing stoch…
Shadow Douglas--Rachford Splitting for Monotone Inclusions
Ernö Robert Csetnek, Yura Malitsky, Matthew K. Tam
In this work, we propose a new algorithm for finding a zero in the sum of two monotone operators where one is assumed to be single-valued and Lipschitz continuous. This algorithm n…
Model Function Based Conditional Gradient Method with Armijo-like Line Search
Yura Malitsky, Peter Ochs
The Conditional Gradient Method is generalized to a class of non-smooth non-convex optimization problems with many applications in machine learning. The proposed algorithm iterates…
A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity
Yura Malitsky, Matthew K. Tam
In this work, we propose a simple modification of the forward-backward splitting method for finding a zero in the sum of two monotone operators. Our method converges under the same…
Golden Ratio Algorithms for Variational Inequalities
Yura Malitsky
The paper presents a fully explicit algorithm for monotone variational inequalities. The method uses variable stepsizes that are computed using two previous iterates as an approxim…
Block-coordinate primal-dual method for the nonsmooth minimization over linear constraints
D. Russell Luke, Yura Malitsky
We consider the problem of minimizing a convex, separable, nonsmooth function subject to linear constraints. The numerical method we propose is a block-coordinate extension of the…
The primal-dual hybrid gradient method reduces to a primal method for linearly constrained optimization problems
Yura Malitsky
In this work, we show that for linearly constrained optimization problems the primal-dual hybrid gradient algorithm, analyzed by Chambolle and Pock [3], can be written as an entire…
A first-order primal-dual algorithm with linesearch
Yura Malitsky, Thomas Pock
The paper proposes a linesearch for a primal-dual method. Each iteration of the linesearch requires to update only the dual (or primal) variable. For many problems, in particular f…