We show how the fat-shattering dimension can be used to obtain lower bounds for a generic class of convex optimization problems under the local access model. This in turn implies that the sample complexity for learning is upper bounded by the optimization runtime (with only local black-box accesses) of the corresponding empirical optimization problem.

Joint work with Karthik Sridharan