A bounded empirical duality gap does not guarantee that the primal variables obtained after running the alternating primal-dual algorithm REF  and solving the saddle point problem approximately are near optimal or approximately feasible. Although stronger primal recovery guarantees can be obtained by randomizing the learning algorithm [1]}, it requires storing model parameters \(\theta \)  at each iteration, and there is empirical evidence [1]}, [3]}, [4]}, [5]}, [6]}, [7]} that good solutions can still be obtained without randomization.
