Multiple local steps are key to communication-efficient federated learning. However, theoretical guarantees for such algorithms, without data heterogeneity-bounding assumptions, have been lacking in general non-smooth convex problems. Leveraging projection-efficient optimization methods, we propose FedMLS, a federated learning algorithm with provable improvements from multiple local steps. FedMLS attains an ϵ-suboptimal solution in O(1/ϵ) communication rounds, requiring a total of O(1/ϵ2) stochastic subgradient oracle calls.