linear convergence

Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server

  • Arda Aytekin
  • Hamid Reza Feyzmahdavian
  • Mikael Johansson
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Parallel Algorithms Tags , , , ,

    This paper presents an asynchronous incremental aggregated gradient algorithm and its implementation in a parameter server framework for solving regularized optimization problems. The algorithm can handle both general convex (possibly non-smooth) regularizers and general convex constraints. When the empirical data loss is strongly convex, we establish linear convergence rate, give explicit expressions for step-size choices … Read more

    On the convergence of a regularized Jacobi algorithm for convex optimization

  • Goran Banjac
  • Paul J. Goulart
  • Kostas Margellos
    • Categories Nonsmooth Optimization Tags , , ,

    In this paper we consider the regularized version of the Jacobi algorithm, a block coordinate descent method for convex optimization with differentiable objective function and block-separable constraints that has been recently proposed in the literature. Under certain regularity assumptions on the objective function, this algorithm has been shown to satisfy the so-called sufficient decrease condition, … Read more

    New analysis of linear convergence of gradient-type methods via unifying error bound conditions

  • Hui Zhang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , , ,

    The subject of linear convergence of gradient-type methods on non-strongly convex optimization has been widely studied by introducing several notions as sufficient conditions. Influential examples include the error bound property, the restricted strongly convex property, the quadratic growth property, and the Kurdyka-{\L}ojasiewicz property. In this paper, we first define a group of error bound conditions … Read more

    Polytope conditioning and linear convergence of the Frank-Wolfe algorithm

  • Javier F. Peña
  • Daniel Rodriguez
    • Categories Convex Optimization Tags , ,

    It is known that the gradient descent algorithm converges linearly when applied to a strongly convex function with Lipschitz gradient. In this case the algorithm’s rate of convergence is determined by condition number of the function. In a similar vein, it has been shown that a variant of the Frank-Wolfe algorithm with away steps converges … Read more

    Newton-like method with diagonal correction for distributed optimization

  • Dragana Bajović
  • Dušan Jakovetić
  • Nataša Krejić
  • Nataša Krklec Jerinkić
    • Categories Nonlinear Optimization Tags , , ,

    We consider distributed optimization problems where networked nodes cooperatively minimize the sum of their locally known convex costs. A popular class of methods to solve these problems are the distributed gradient methods, which are attractive due to their inexpensive iterations, but have a drawback of slow convergence rates. This motivates the incorporation of second-order information … Read more

    On the von Neumann and Frank-Wolfe Algorithms with Away Steps

  • Javier F. Peña
  • Daniel Rodriguez
  • Negar Soheili
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    The von Neumann algorithm is a simple coordinate-descent algorithm to determine whether the origin belongs to a polytope generated by a finite set of points. When the origin is in the interior of the polytope, the algorithm generates a sequence of points in the polytope that converges linearly to zero. The algorithm’s rate of convergence … Read more

    Quadratic regularization projected alternating Barzilai–Borwein method for constrained optimization

  • Yakui Huang
  • Hongwei Liu
  • Sha Zhou
    • Categories Applications - Science and Engineering, Nonlinear Optimization Tags , , , ,

    In this paper, based on the regularization techniques and projected gradient strategies, we present a quadratic regularization projected alternating Barzilai–Borwein (QRPABB) method for minimizing differentiable functions on closed convex sets. We show the convergence of the QRPABB method to a constrained stationary point for a nonmonotone line search. When the objective function is convex, we … Read more

    Alternating projections and coupling slope

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
  • Alexander D. Ioffe
    • Categories Nonsmooth Optimization, Other Topics Tags , , , ,

    We consider the method of alternating projections for finding a point in the intersection of two possibly nonconvex closed sets. We present a local linear convergence result that makes no regularity assumptions on either set (unlike previous results), while at the same time weakening standard transversal intersection assumptions. The proof grows out of a study … Read more

    Gradient methods for convex minimization: better rates under weaker conditions

  • Wotao Yin
  • Hui Zhang
    • Categories Convex Optimization Tags , , , , , , ,

    The convergence behavior of gradient methods for minimizing convex differentiable functions is one of the core questions in convex optimization. This paper shows that their well-known complexities can be achieved under conditions weaker than the commonly assumed ones. We relax the common gradient Lipschitz-continuity condition and strong convexity condition to ones that hold only over … Read more

    On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers

  • Wei Deng
  • Wotao Yin
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    The formulation min f(x)+g(y) subject to Ax+By=b, where f and g are extended-value convex functions, arises in many application areas such as signal processing, imaging and image processing, statistics, and machine learning either naturally or after variable splitting. In many common problems, one of the two objective functions is strictly convex and has Lipschitz continuous … Read more