Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity

Many fundamental problems in machine learning can be formulated by the convex program [ minθ∈ Rd sumi=1nfi(θ), ] where each fi is a convex, Lipschitz function supported on a subset of di coordinates of θ. One common approach to this problem, exemplified by stochastic gradient descent, involves sampling one fi term at every iteration to make progress. This approach crucially relies on a notion of uniformity across the fi's, formally captured by their condition number. In this work, we give an algorithm that minimizes the above convex formulation to ε-accuracy in widetildeO(sumi=1n di log (1 /ε)) gradient computations, with no assumptions on the condition number. The previous best algorithm independent of the condition number is the standard cutting plane method, which requires O(nd log (1/ε)) gradient computations. As a corollary, we improve upon the evaluation oracle complexity for decomposable submodular minimization by Axiotis et al. (ICML 2021). Our main technical contribution is an adaptive procedure to select an fi term at every iteration via a novel combination of cutting-plane and interior-point methods.