Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
The authors design single-loop, purely subgradient-based algorithms for nonsmooth stochastic convex-concave saddle-point problems using linear minimization oracles instead of Euclidean projections. The framework achieves an anytime strong saddle gap convergence rate of $O(\epsilon^{-2})$ with bounded-variance stochastic subgradients, accompanied by matching minimax lower bounds. This establishes that trading expensive domain projections for linear minimization oracles incurs zero penalty in iteration complexity or statistical efficiency, even in nonsmooth minimax settings without smoothing.
Costly Euclidean projections in nonsmooth stochastic minimax optimization can be swapped for cheap linear minimization oracles with zero penalty to the minimax-optimal $O(\epsilon^{-2})$ convergence rate.
We study nonsmooth convex-concave saddle-point problems over compact convex sets, assuming access to stochastic subgradients of the payoff function. We develop single-loop projection-free algorithms that use linear minimization oracles over the primal and dual domains. Unlike prior projection-free approaches that rely on smoothing, our methods are purely subgradient-based and handle nonsmoothness directly. This design makes the framework modular: when a linear minimization oracle is not used over a specific domain, the corresponding update can be replaced by a standard projection oracle without changing the single-loop structure. Thus, our framework covers both fully projection-free and hybrid oracle configurations. We prove anytime strong saddle gap guarantees under standard unbiased stochastic oracle assumptions with bounded variance. Our algorithms achieve an $O(ε^{-2})$ iteration complexity, matching projected stochastic subgradient methods. We also provide matching lower bounds for the corresponding oracle models, establishing minimax optimality. Our results show that, for nonsmooth stochastic minimax problems, the computational advantages of linear minimization oracles need not come at the expense of statistical or oracle efficiency.