On the Complexity of a Practical Primal-Dual Coordinate Method

• URL: http://arxiv.org/abs/2201.07684v1
• Date: Wed, 19 Jan 2022 16:14:27 GMT
• Title: On the Complexity of a Practical Primal-Dual Coordinate Method
• Authors: Ahmet Alacaoglu, Volkan Cevher, Stephen J. Wright
• Abstract summary: We prove complexity bounds for primal-dual algorithm with random and coordinate descent (PURE-CD) It has been shown to obtain good extrapolation for solving bi-max performance problems.
• Score: 63.899427212054995
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove complexity bounds for the primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD), which has been shown to obtain good practical performance for solving convex-concave min-max problems with bilinear coupling. Our complexity bounds either match or improve the best-known results in the literature for both dense and sparse (strongly)-convex-(strongly)-concave problems.

Related papers

• On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms [17.227158587717934]
  We revisit the smooth convex-concave bilinearly-coupled saddle-point problem of the form $min_xmax_y f(x) + langle y,mathbfB xrangle - g(y)$. We develop the first lower complexity bounds and matching optimal linearly converging algorithms for this problem class.
  arXiv  Detail & Related papers  (2024-11-21T22:06:25Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Fixed-Time Convergence for a Class of Nonconvex-Nonconcave Min-Max Problems [5.787117733071416]
  We develop a fixed-time convergent saddle point dynamical system for solving min-max problems. The proposed method achieves fast compared to any other state method.
  arXiv  Detail & Related papers  (2022-07-26T12:25:05Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-max algorithms have been analyzed in the Euclidean setting. We prove that the extraiteient (RCEG) method corrected lastrate convergence at a linear rate.
  arXiv  Detail & Related papers  (2022-06-04T18:53:44Z)
• Efficient Algorithms for High-Dimensional Convex Subspace Optimization via Strict Complementarity [19.24470467199451]
  We consider optimization problems in which the goal is find a $k$ subspace of $realsn$, $k$, which minimizes a convex smooth loss. While this problem is highly in high-dimensional regimes, it is difficult to find a global optimal solution. In this paper we present a natural. determinate optimal dimension relaxation for which convergence to the. global is straightforward.
  arXiv  Detail & Related papers  (2022-02-08T17:36:43Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization [25.73397307080647]
  We present a new model of a general convex or non objective machine machine objectives. We propose an algorithm that solves a constraint with gradually relaxed point levels of each subproblem. We demonstrate the effectiveness of our new numerical scale problems.
  arXiv  Detail & Related papers  (2020-10-23T05:24:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.