Timezone: »

 
Poster
Local Minimax Complexity of Stochastic Convex Optimization
sabyasachi chatterjee · John Duchi · John Lafferty · Yuancheng Zhu

Wed Dec 07 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #21
in Wednesday Posters »

We extend the traditional worst-case, minimax analysis of stochastic convex optimization by introducing a localized form of minimax complexity for individual functions. Our main result gives function-specific lower and upper bounds on the number of stochastic subgradient evaluations needed to optimize either the function or its ``hardest local alternative'' to a given numerical precision. The bounds are expressed in terms of a localized and computational analogue of the modulus of continuity that is central to statistical minimax analysis. We show how the computational modulus of continuity can be explicitly calculated in concrete cases, and relates to the curvature of the function at the optimum. We also prove a superefficiency result that demonstrates it is a meaningful benchmark, acting as a computational analogue of the Fisher information in statistical estimation. The nature and practical implications of the results are demonstrated in simulations.

Keywords: Information Theory · (Other) Statistics · Convex Optimization · (Other) Optimization · Stochastic Methods · Active Learning
[ PDF] 

Author Information

sabyasachi chatterjee (University of Chicago)
John Duchi (Stanford)
John Lafferty (Yale University)
Yuancheng Zhu (University of Chicago)

More from the Same Authors