saddle point problem

Graph topology invariant gradient and sampling complexity for decentralized and stochastic optimization

  • Guanghui Lan
  • Yuyuan Ouyang
  • Yi Zhou
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Stochastic Programming Tags , , ,

    One fundamental problem in decentralized multi-agent optimization is the trade-off between gradient/sampling complexity and communication complexity. We propose new algorithms whose gradient and sampling complexities are graph topology invariant, while their communication complexities remain optimal. For convex smooth deterministic problems, we propose a primal dual sliding (PDS) algorithm that computes an $\epsilon$-solution with $O((\tilde{L}/\epsilon)^{1/2})$ gradient … Read more

    On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport

  • Minhui Huang
  • Shiqian Ma
  • Lifeng Lai
    • Categories Convex Optimization Tags , , , , , ,

    This paper studies the equitable and optimal transport (EOT) problem, which has many applications such as fair division problems and optimal transport with multiple agents etc. In the discrete distributions case, the EOT problem can be formulated as a linear program (LP). Since this LP is prohibitively large for general LP solvers, Scetbon \etal \cite{scetbon2021equitable} … Read more

    Equivalent second-order cone programs for distributionally robust zero-sum games

  • Ayush Agarwal
  • Abdel Lisser
  • Vikas Vikram Singh
  • Navnit Yadav
    • Categories Game Theory, Stochastic Programming Tags , , , ,

    We consider a two player zero-sum game with stochastic linear constraints. The probability distributions of the vectors associated with the constraints are partially known. The available information with respect to the distribution is based mainly on the two first moments. In this vein, we formulate the stochastic linear constraints as distributionally robust chance constraints. We … Read more

    A search direction inspired primal-dual method for saddle point problems

  • Shengjie Xu
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , , ,

    The primal-dual hybrid gradient algorithm (PDHG), which is indeed the Arrow-Hurwicz method, has been widely used in image processing areas. However, the convergence of PDHG was established only under some restrictive conditions in the literature, and it is still missing for the case without extra constraints. In this paper, from a perspective of the variational … Read more

    Stochastic model-based minimization under high-order growth

  • Damek Davis
  • Dmitriy Drusvyatskiy
  • Kellie J. MacPhee
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    Given a nonsmooth, nonconvex minimization problem, we consider algorithms that iteratively sample and minimize stochastic convex models of the objective function. Assuming that the one-sided approximation quality and the variation of the models is controlled by a Bregman divergence, we show that the scheme drives a natural stationarity measure to zero at the rate $O(k^{-1/4})$. … Read more

    Interior Point Methods and Preconditioning for PDE-Constrained Optimization Problems Involving Sparsity Terms

  • John W. Pearson
  • Margherita Porcelli
  • Martin Stoll
    • Categories Control Applications, Nonlinear Optimization, Systems governed by Differential Equations Optimization Tags , , , , ,

    PDE-constrained optimization problems with control or state constraints are challenging from an analytical as well as numerical perspective. The combination of these constraints with a sparsity-promoting L1 term within the objective function requires sophisticated optimization methods. We propose the use of an Interior Point scheme applied to a smoothed reformulation of the discretized problem, and … Read more

    The Proximal Alternating Minimization Algorithm for two-block separable convex optimization problems with linear constraints

  • Sandy Bitterlich
  • Radu Ioan Bot
  • Ernö Robert Csetnek
  • Gert Wanka
    • Categories Convex Optimization Tags , , , , ,

    The Alternating Minimization Algorithm (AMA) has been proposed by Tseng to solve convex programming problems with two-block separable linear constraints and objectives, whereby (at least) one of the components of the latter is assumed to be strongly convex. The fact that one of the subproblems to be solved within the iteration process of AMA does … Read more

    Golden Ratio Algorithms for Variational Inequalities

  • Yura Malitsky
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    The paper presents a fully explicit algorithm for monotone variational inequalities. The method uses variable stepsizes that are computed using two previous iterates as an approximation of the local Lipschitz constant without running a linesearch. Thus, each iteration of the method requires only one evaluation of a monotone operator $F$ and a proximal mapping $g$. … Read more

    Block Coordinate Descent Almost Surely Converges to a Stationary Point Satisfying the Second-order Necessary Condition

  • Zhubin Shen
  • Qingjiang Shi
  • Enbin Song
    • Categories Unconstrained Optimization Tags , , , , ,

    Given a non-convex twice continuously differentiable cost function with Lipschitz continuous gradient, we prove that all of the block coordinate gradient descent, block mirror descent and proximal block coordinate descent methods converge to stationary points satisfying the second-order necessary condition, almost surely with random initialization. All our results are ascribed to the center-stable manifold theorem … Read more

    DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization

  • Weizhu Chen
  • Qihang Lin
  • Lin Xiao
  • Wei Yu
    • Categories Convex and Nonsmooth Optimization, Parallel Algorithms Tags , , , , ,

    Machine learning with big data often involves large optimization models. For distributed optimization over a cluster of machines, frequent communication and synchronization of all model parameters (optimization variables) can be very costly. A promising solution is to use parameter servers to store different subsets of the model parameters, and update them asynchronously at different machines … Read more