On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms

Dmitry Kovalev, Ekaterina Borodich

We revisit the smooth convex-concave bilinearly-coupled saddle-point problem of the form ${\min }_x{\max }_{y}f(x)+⟨y,\mathbf{B}x⟩-g(y)$. In the highly specific case whe…