DOS Seminar

Event Details
  • Date/Time:
    • Wednesday April 16, 2014 - Thursday April 17, 2014
      4:00 pm - 4:59 pm
  • Location: Advisory Board Room 402 Groseclose
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: DOS Seminar

Full Summary: No summary paragraph submitted.

TITLE:  Lower Complexity Bounds for Large-Scale Smooth Convex Optimization

SPEAKER:  Cristobal Guzman


We prove lower bounds on the black-box oracle complexity of large-scale
smooth convex minimization problems. These lower bounds work for unit balls
of normed spaces under a technical smoothing condition, and arbitrary
smoothness parameter of the objective with respect to this norm. As a
consequence, we show a unified framework for the complexity of convex
optimization on \ell^p-balls, for 2<=p<=\infty. In particular, we prove
that the T-step Conditional Gradient algorithm as applied to minimizing
smooth convex functions over the n-dimensional box with T<=n is nearly

On the other hand, we prove lower bounds for the complexity of convex
optimization over \ell^p-balls, for 1<=p<2, by combining a random subspace
method with the p=\infty lower bounds. In particular, we establish the
complexity of problem classes that contain the sparse recovery problem.

This is joint work with Arkadi Nemirovski

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
Undergraduate students, Faculty/Staff, Graduate students
No keywords were submitted.
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Apr 14, 2014 - 5:19am
  • Last Updated: Apr 13, 2017 - 5:22pm