  This paper revisits a class of convex Finite-Sum Coupled Compositional
Stochastic Optimization (cFCCO) problems with many applications, including
group distributionally robust optimization (GDRO), learning with imbalanced
data, reinforcement learning, and learning to rank. To better solve these
problems, we introduce an efficient single-loop primal-dual block-coordinate
proximal algorithm, dubbed ALEXR. This algorithm leverages block-coordinate
stochastic mirror ascent updates for the dual variable and stochastic proximal
gradient descent updates for the primal variable. We establish the convergence
rates of ALEXR in both convex and strongly convex cases under smoothness and
non-smoothness conditions of involved functions, which not only improve the
best rates in previous works on smooth cFCCO problems but also expand the realm
of cFCCO for solving more challenging non-smooth problems such as the dual form
of GDRO. Finally, we present lower complexity bounds to demonstrate that the
convergence rates of ALEXR are optimal among first-order block-coordinate
stochastic algorithms for the considered class of cFCCO problems.
