2 citations · 2 across the 5 of their papers we have counts for
12 papers · 1 filter
The Minimax Complexity of Federated Optimization under Interpolation: The Role of Oracle Models
Kirill Novoselov, Yuriy Dorn, Darina Dvinskikh +1
We study the minimax complexity of smooth convex stochastic optimization with intermittent communication: workers run for rounds, and between consecutive communication roun…
Adaptive two-points zero-order accelerated methods for stochastic convex optimization problems
Yuriy Dorn, Osman Osmanov, Timofei Loginov +3
We study stochastic convex optimization, where each sampled function can be evaluated at two arbitrary points. Our accelerated method chooses step sizes, batch sizes and smoothing…
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 , with separately charged partial-gradient oracles for all three objective c…
Optimal Rates for Federated Variational Inequalities under different relaxations of bounded variance assumption
Kirill Novoselov, Yuriy Dorn, Darina Dvinskikh +1
We study how interpolation affects local steps and parallel sampling in monotone variational inequalities (VIs), with workers, oracle calls per worker per round, and ro…
Minimax Oracle Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions
Timofei Loginov, Darina Dvinskikh, Nazarii Tupitsa +3
We study zeroth-order optimization of convex and strongly convex functions with Hölder smoothness of order from values corrupted by random noise with bias independent of the…
Asking the Crowd the Right Question: Bias-Cancelling Weights for Federated Learning
Ilya Kuruzov, Dmitrii Vishovan, Kirill Novoselov +3
A federated objective is a weighted sum of client risks, and the weights are almost always fixed in advance. We treat them instead as the only instrument of a wisdom-of-crowds mech…
Lower Bounds For Gradient-Free Convex Optimization And Convex-Concave Saddle-Point Problems
Yuriy Dorn, Darina Dvinskikh, Timofei Loginov +4
We study the query complexity of optimization with exact scalar-value information. For globally -smooth convex functions on with a minimizer in a Euclidean ball of…
The Complexity of Convex Optimization with Mismatched Geometry
Timofei Loginov, Alexander Gasnikov, Yuriy Dorn +4
Optimal first-order methods on non-Euclidean domains such as the ball pair the prox-function with the norm in which smoothness…
Smooth or Separable? Sparse Block Acceleration for Entropy-Regularized Linear Programs
Irina Podlipnova, Maxim Mashtaler, Artem Agafonov +2
We study entropy-regularized linear programs with sparse affine constraints and compare two exact dual representations induced by whether a redundant normalization constraint is re…
Median Clipping for Zeroth-order Non-Smooth Convex Optimization and Multi-Armed Bandit Problem with Heavy-tailed Symmetric Noise
Nikita Kornilov, Yuriy Dorn, Aleksandr Lobanov +5
In this paper, we consider non-smooth convex optimization with a zeroth-order oracle corrupted by symmetric stochastic noise. Unlike the existing high-probability results requiring…
Searching equillibriums in Beckmann's and Nesterov--de Palma's models
Alexander Gasnikov, Pavel Dvurechensky, Yuriy Dorn +1
In this paper we propose and develop classical Frank--Wolf algorithm for Beckmann's type models. This is not new, but we investigate details that allows us to speed up. We also con…
On the three-stage version of stable dynamic model
Alexander Gasnikov, Yuriy Dorn, Yurii Nesterov +1
An attempt to merge into a single model, which reduces to the solution of non-smooth convex optimization problem: calculation model of OD-matrix (entropy model), the mode split mod…