A. Gasnikov

Complexity of Multiblock Convex-Concave Saddle-Point Problems with General Smooth Coupling

Nhat Trung Nguyen, Ivan Dorofeev, Irina Podlipnova +2

We study multiblock convex--concave saddle-point problems of the form $min_{x} max_{y} {f (x) + H (x, y) - g (y)}$ , with separately charged partial-gradient oracles for all three objective c…

Accelerated Consensus and Decentralized Optimization over Slowly Varying Networks

Darina Dvinskikh, Anton Novitskii, Demyan Yarmoshik +3

We study average consensus over slowly time-varying networks and its application to decentralized optimization. We introduce WAVE, a windowed Chebyshev method that limits the accum…

Decentralized Optimization with Cross-Coupled Mixed Affine Constraints

Ewsey Obzherin, Ilya Khomchenko, Natalia Shelegeda +4

We study decentralized optimization with cross-coupled mixed affine constraints, where local and shared variables interact through two affine channels. We show that the intrinsic d…

Saddle-Point Problems with a Low-Dimensional Block Do Not Need Accurate Inner Solves

Ivan Fomin, Alexander V. Gasnikov

Many learning problems couple a high-dimensional block of parameters with a handful of adversarial or dual variables: worst-group risk over a few groups, or learning under a few co…

Convex-Concave Interpolation and Application of PEP to Bilinear-Coupled Saddle-Point Problem

Valery Krivchenko, Alexander Gasnikov, Dmitry Kovalev

The Performance estimation problem (PEP) approach reformulates finding the exact worst-case performance of an algorithm as the solution to an optimization problem. Tractable formul…

Sliding Methods for Hölder-Smooth Convex--Concave Minimax Optimization with Bilinear Coupling

Nhat Trung Nguyen, Alexander Gasnikov

We study convex-concave minimax optimization problems with bilinear coupling of the form $min_{x \in X} max_{y \in Y} f (x) + ⟨ y, B x ⟩ - g (y),$ w…

Decentralized Inexact Cubic Newton Method with Consensus Procedure

Artem Agafonov, Anton Novitskii, Alexander Rogozin +5

Distributed optimization is widely used in large-scale and privacy-preserving machine learning, where each agent stores a local objective and communicates only with its neighbors i…

Exploring New Frontiers in Vertical Federated Learning: the Role of Saddle Point Reformulation

Aleksandr Beznosikov, Georgiy Kormakov, Alexander Grigorievskiy +7

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 o…

Decentralized Optimization with Mixed Affine Constraints

Demyan Yarmoshik, Nhat Trung Nguyen, Alexander Rogozin +1

This paper considers decentralized optimization of convex functions with mixed affine equality constraints involving both local and global variables. Constraints on global variable…

Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity

Boris Prokhorov, Semyon Chebykin, Alexander Gasnikov +1

This paper deals with stochastic optimization problems involving Markovian noise with a zero-order oracle. We present and analyze a novel derivative-free method for solving such pr…

Speeding up the Goemans-Williamson randomized procedure by difference-of-convex optimization

Hadi Salloum, Roland Hildebrand, Nhat Trung Nguyen +4

We present a novel approach to accelerate the Goemans-Williamson (GW) randomized rounding procedure for quadratic unconstrained binary optimization (QUBO) problems. Instead of solv…

Adaptive Regularized Newton Method with Inexact Hessian

Aleksandr Shestakov, Nail Bashirov, Andrei Semenov +4

Newton's method is the most widespread high-order method, demanding the gradient and the Hessian of the objective function. However, one of the main disadvantages of Newtons method…

Dual Smoothing for Decentralized Optimization

Alexander Rogozin, Nhat Trung Nguyen, Hamed Azami Zenuzagh +1

Decentralized optimization is widely used in different fields of study such as distributed learning, signal processing, and various distributed control problems. In these types of…

A Parameter-free Decentralized Algorithm for Composite Convex Optimization

Xiaokai Chen, Ilya Kuruzov, Gesualdo Scutari +1

The paper studies decentralized optimization over networks, where agents minimize a composite objective consisting of the sum of smooth convex functions--the agents' losses--and an…

Stochastic Decentralized Optimization of Non-Smooth Convex and Convex-Concave Problems over Time-Varying Networks

Maxim Divilkovskiy, Alexander Gasnikov

We study non-smooth stochastic decentralized optimization problems over time-varying networks, where objective functions are distributed across nodes and network connections may in…

Adaptive Stepsize Selection in Decentralized Convex Optimization

Ilya Kuruzov, Xiaokai Chen, Gesualdo Scutari +1

We study decentralized optimization where multiple agents minimize the average of their (strongly) convex, smooth losses over a communication graph. Convergence of the existing dec…

math.OC2024★ 1 cited

Method with Batching for Stochastic Finite-Sum Variational Inequalities in Non-Euclidean Setting

Alexander Pichugin, Maksim Pechin, Aleksandr Beznosikov +2

Variational inequalities are a universal optimization paradigm that incorporate classical minimization and saddle point problems. Nowadays more and more tasks require to consider s…

Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions

Andrey Sadchikov, Savelii Chezhegov, Aleksandr Beznosikov +1

Distributed optimization plays an important role in modern large-scale machine learning and data processing systems by optimizing the utilization of computational resources. One of…

Average-case optimization analysis for distributed consensus algorithms on regular graphs

Nhat Trung Nguyen, Alexander Rogozin, Alexander Gasnikov

The consensus problem in distributed computing involves a network of agents aiming to compute the average of their initial vectors through local communication, represented by an un…

Decentralized Optimization with Coupled Constraints

Demyan Yarmoshik, Alexander Rogozin, Nikita Kiselev +3

We consider the decentralized minimization of a separable objective $\sum_{i = 1}^{n} f_{i} (x_{i})$ , where the variables are coupled through an affine constraint $\sum_{i=1}^n\left(\math…

math.OC2024★ 1 cited

Accelerated Stochastic Gradient Method with Applications to Consensus Problem in Markov-Varying Networks

Vladimir Solodkin, Savelii Chezhegov, Ruslan Nazikov +2

Stochastic optimization is a vital field in the realm of mathematical optimization, finding applications in diverse areas ranging from operations research to machine learning. In t…