PhD Thesis Defense - Cristobal Guzman

Event Details
  • Date/Time:
    • Monday March 30, 2015
      9:00 am
  • Location: Groseclose 226A
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: PhD Thesis Defense - Cristobal Guzman

Full Summary: No summary paragraph submitted.

TITLE: Information, Complexity and Structure in Convex Optimization

ABSTRACT:

This thesis is focused on the limits of performance of large-scale convex optimization algorithms. Classical theory of oracle complexity, first proposed by Nemirovski and Yudin in 1983, successfully established the worst-case behavior of methods based on local oracles (a generalization of first-order oracle for smooth functions) for nonsmooth convex minimization, both in the large-scale and low-scale regimes; and the complexity of approximately solving linear systems of equations (equivalent to convex quadratic minimization) over Euclidean balls, under a matrix-vector multiplication oracle.

Our work extends the applicability of lower bounds in two directions:

Worst-Case Complexity of Large-Scale Smooth Convex Optimization: We generalize lower bounds on the complexity of first-order methods for convex optimization, considering classes of convex functions with Holder continuous gradients. Our technique relies on the existence of a smoothing kernel, which defines a smooth approximation for any convex function via infimal convolution. As a consequence, we derive lower bounds for ell_p/ell_q-setups, where 1 <= p,q <= \infty, and extend to its matrix analogue: Smooth (w.r.t. Schatten q-norm) convex minimization over matrices with bounded Schatten p-norm.

The major consequences of this result are the near-optimality of the Conditional Gradient method over box-type domains (p=q=\infty), and the near-optimality of Nesterov's accelerated method over the cross-polytope (p=q=1).

The thesis is available for public inspection in the School of
Mathematics lounge (Skiles 236), the ARC lounge (Klaus 2222), the ISyE
PhD student lounge, and at the URL

        http://www.aco.gatech.edu/dissert/guzman.html

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
Other/Miscellaneous
Keywords
No keywords were submitted.
Status
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Mar 24, 2015 - 11:22am
  • Last Updated: Apr 13, 2017 - 5:19pm