Filters

2019 - 201912020 - 20223

More filters

2022 - 20234
Reset filters

Settings

Author: Uribe, César A. ×

Search Results

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Hyperfast second-order local solvers for efficient statistically preconditioned distributed optimization
    (Amsterdam : Elsevier, 2022) Dvurechensky, Pavel; Kamzolov, Dmitry; Lukashevich, Aleksandr; Lee, Soomin; Ordentlich, Erik; Uribe, César A.; Gasnikov, Alexander
    Statistical preconditioning enables fast methods for distributed large-scale empirical risk minimization problems. In this approach, multiple worker nodes compute gradients in parallel, which are then used by the central node to update the parameter by solving an auxiliary (preconditioned) smaller-scale optimization problem. The recently proposed Statistically Preconditioned Accelerated Gradient (SPAG) method [1] has complexity bounds superior to other such algorithms but requires an exact solution for computationally intensive auxiliary optimization problems at every iteration. In this paper, we propose an Inexact SPAG (InSPAG) and explicitly characterize the accuracy by which the corresponding auxiliary subproblem needs to be solved to guarantee the same convergence rate as the exact method. We build our results by first developing an inexact adaptive accelerated Bregman proximal gradient method for general optimization problems under relative smoothness and strong convexity assumptions, which may be of independent interest. Moreover, we explore the properties of the auxiliary problem in the InSPAG algorithm assuming Lipschitz third-order derivatives and strong convexity. For such problem class, we develop a linearly convergent Hyperfast second-order method and estimate the total complexity of the InSPAG method with hyperfast auxiliary problem solver. Finally, we illustrate the proposed method's practical efficiency by performing large-scale numerical experiments on logistic regression models. To the best of our knowledge, these are the first empirical results on implementing high-order methods on large-scale problems, as we work with data where the dimension is of the order of 3 million, and the number of samples is 700 million.
  • Thumbnail Image
    Item
    On primal and dual approaches for distributed stochastic convex optimization over networks
    (Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2020) Dvinskikh, Darina; Gorbunov, Eduard; Gasnikov, Alexander; Dvurechensky, Alexander; Uribe, César A.
    We introduce a primal-dual stochastic gradient oracle method for distributed convex optimization problems over networks. We show that the proposed method is optimal in terms of communication steps. Additionally, we propose a new analysis method for the rate of convergence in terms of duality gap and probability of large deviations. This analysis is based on a new technique that allows to bound the distance between the iteration sequence and the optimal point. By the proper choice of batch size, we can guarantee that this distance equals (up to a constant) to the distance between the starting point and the solution.
  • Thumbnail Image
    Item
    Distributed optimization with quantization for computing Wasserstein barycenters
    (Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2020) Krawchenko, Roman; Uribe, César A.; Gasnikov, Alexander; Dvurechensky, Pavel
    We study the problem of the decentralized computation of entropy-regularized semi-discrete Wasserstein barycenters over a network. Building upon recent primal-dual approaches, we propose a sampling gradient quantization scheme that allows efficient communication and computation of approximate barycenters where the factor distributions are stored distributedly on arbitrary networks. The communication and algorithmic complexity of the proposed algorithm are shown, with explicit dependency on the size of the support, the number of distributions, and the desired accuracy. Numerical results validate our algorithmic analysis.
  • 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.