PhD Thesis Defense - Cristobal Guzman

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

Summary Sentence: PhD Thesis Defense - Cristobal Guzman

Full Summary: No summary paragraph submitted.

TITLE: Information, Complexity and Structure in Convex Optimization


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

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: Mar 24, 2015 - 11:22am
  • Last Updated: Apr 13, 2017 - 5:19pm