Filters

20192

More filters

20222
Reset filters

Settings

search.filters.applied.f.access: openAccess × Author: Gasnikov, Alexander × End date: 2024 × Start date: 2020 × End date: 2019 × Start date: 2019 × WGL Institute: WIAS ×

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    On the complexity of approximating Wasserstein barycenter
    (Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2019) Kroshnin, Alexey; Dvinskikh, Darina; Dvurechensky, Pavel; Gasnikov, Alexander; Tupitsa, Nazarii; Uribe, César A.
    We study the complexity of approximating Wassertein barycenter of discrete measures, or histograms by contrasting two alternative approaches, both using entropic regularization. We provide a novel analysis for our approach based on the Iterative Bregman Projections (IBP) algorithm to approximate the original non-regularized barycenter. We also get the complexity bound for alternative accelerated-gradient-descent-based approach and compare it with the bound obtained for IBP. As a byproduct, we show that the regularization parameter in both approaches has to be proportional to ", which causes instability of both algorithms when the desired accuracy is high. To overcome this issue, we propose a novel proximal-IBP algorithm, which can be seen as a proximal gradient method, which uses IBP on each iteration to make a proximal step. We also consider the question of scalability of these algorithms using approaches from distributed optimization and show that the first algorithm can be implemented in a centralized distributed setting (master/slave), while the second one is amenable to a more general decentralized distributed setting with an arbitrary network topology.
  • Thumbnail Image
    Item
    Adaptive gradient descent for convex and non-convex stochastic optimization
    (Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2019) Ogaltsov, Aleksandr; Dvinskikh, Darina; Dvurechensky, Pavel; Gasnikov, Alexander; Spokoiny, Vladimir
    In this paper we propose several adaptive gradient methods for stochastic optimization. Our methods are based on Armijo-type line search and they simultaneously adapt to the unknown Lipschitz constant of the gradient and variance of the stochastic approximation for the gradient. We consider an accelerated gradient descent for convex problems and gradient descent for non-convex problems. In the experiments we demonstrate superiority of our methods to existing adaptive methods, e.g. AdaGrad and Adam.