Fast gradient algorithms for structured sparsity

  • Author / Creator
    Yu, Yaoliang
  • Many machine learning problems can be formulated under the composite minimization framework which usually involves a smooth loss function and a nonsmooth regularizer. A lot of algorithms have thus been proposed and the main focus has been on first order gradient methods, due to their applicability in very large scale application domains. A common requirement of many of these popular gradient algorithms is the access to the proximal map of the regularizer, which unfortunately may not be easily computable in scenarios such as structured sparsity. In this thesis we first identify conditions under which the proximal map of a sum of functions is simply the composition of the proximal map of each individual summand, unifying known and uncover novel results. Next, motivated by the observation that many structured sparse regularizers are merely the sum of simple functions, we consider a linear approximation of the proximal map, resulting in the so-called proximal average. Surprisingly, combining this approximation with fast gradient schemes yields strictly better convergence rates than the usual smoothing strategy, without incurring any overhead. Finally, we propose a generalization of the conditional gradient algorithm which completely abandons the proximal map but requires instead the polar---a significantly cheaper operation in certain matrix applications. We establish its convergence rate and demonstrate its superiority on some matrix problems, including matrix completion, multi-class and multi-task learning, and dictionary learning.

  • Subjects / Keywords
  • Graduation date
  • Type of Item
  • Degree
    Doctor of Philosophy
  • DOI
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
  • Language
  • Institution
    University of Alberta
  • Degree level
  • Department
    • Department of Computing Science
  • Specialization
    • Statistical machine learning
  • Supervisor / co-supervisor and their department(s)
    • Schuurmans, Dale (Computing Science)
    • Szepesvari, Csaba (Computing Science)
  • Examining committee members and their departments
    • Gyorgy, Andras (Computing Science)
    • Bach, Francis (Computer Science Laboratory, Ecole Normale Superieure)
    • Sacchi, Mauricio (Physics)
    • Salavatipour, Mohammad (Computing Science)