Publication

On the Complexity of a Simple Primal-dual Coordinate Method

2025

Abstract

We prove new complexity bounds for the primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD), which has been shown to obtain promising practical performance for solving convex-concave min-max problems with bilinear coupling and dual separability. Such problems arise in many machine learning contexts, including empirical risk minimization, matrix games, and image processing. Our results either match or improve the best-known complexities of first-order algorithms for dense and sparse (strongly)-convex-(strongly)-concave problems with bilinear coupling.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2025

Abstract

Official source

Related concepts (31)

Convex optimization

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

Convex function

In mathematics, a real-valued function is called convex if the line segment between any two distinct points on the graph of the function lies above the graph between the two points. Equivalently, a function is convex if its epigraph (the set of points on or above the graph of the function) is a convex set. A twice-differentiable function of a single variable is convex if and only if its second derivative is nonnegative on its entire domain.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Related publications (32)

On the Complexity of a Simple Primal-dual Coordinate Method

Chat with Graph Search

Learning in Pinns: Phase Transition, Diffusion Equilibrium, and Generalization

Thinking of Neural Networks like a Physicist: the Statistical Physics of Machine Learning

Faster Homomorphic Operations and Beyond: Expediting Homomorphic Computation via Boolean Circuit Optimization