DOS Seminar

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

Summary Sentence: DOS Seminar

Full Summary: No summary paragraph submitted.

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

SPEAKER:  Cristobal Guzman

ABSTRACT:

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
optimal.

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
No
Groups

H. Milton Stewart School of Industrial and Systems Engineering (ISYE)

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