Mengdi Wang, Princeton University


Duality Gap For Large Separable Saddle Point Problems


We consider the saddle point problem involving the sum of a large number of component functions. Although the component functions are not necessarily convex-concave, we can show that their large sum is approximately convex-concave. We derive a duality gap estimate for this saddle point problem, which suggests that solving the maximin problem provides a fairly good approximation for the minimax problem.

« Back