Optimization Online


Solving large scale polynomial convex problems on \ell_1/nuclear norm balls by randomized first-order algorithms

Aharon Ben-Tal (abental***at***ie.technion.ac.il)
Arkadi Nemirovski (nemirovs***at***isye.gatech.edu)

Abstract: One of the most attractive recent approaches to processing well-structured large-scale convex optimization problems is based on smooth convex-concave saddle point reformulation of the problem of interest and solving the resulting problem by a fast First Order saddle point method utilizing smoothness of the saddle point cost function. In this paper, we demonstrate that when the saddle point cost function is polynomial, the precise gradients of the cost function required by deterministic First Order saddle point algorithms and becoming prohibitively computationally expensive in the extremely large-scale case, can be replaced with incomparably cheaper computationally unbiased random estimates of the gradients. We show that for large-scale problems with favourable geometry, this randomization accelerates, progressively as the sizes of the problem grow, the solution process. This extends significantly previous results on acceleration by randomization, which, to the best of our knowledge, dealt solely with bilinear saddle point problems. We illustrate our theoretical findings by instructive and encouraging numerical experiments.

Keywords: convex-concave saddle point problems, large-scale convex programming, first order optimization algorithms, acceleration by randomization

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 10/24/2012
Entry Accepted: 10/24/2012
Entry Last Modified: 03/24/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society