Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity
Many fundamental problems in machine learning can be formulated by the convex program where each is a convex, Lipschitz function supported on a subset of coordinates of . One common approach to this problem, exemplified by stochastic gradient descent, involves sampling one term at every iteration to make progress. This approach crucially relies on a notion of uniformity across the 's, formally captured by their condition number. In this work, we give an algorithm that minimizes the above convex formulation to -accuracy in 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 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 term at every iteration via a novel combination of cutting-plane and interior-point methods.