Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

Greedy Methods, Randomization Approaches, and Multiarm Bandit Algorithms for Efficient Sparsity-Constrained Optimization

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
  • معلومة اضافية
    • Contributors:
      Equipe Apprentissage (DocApp - LITIS); Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS); Université Le Havre Normandie (ULH); Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN); Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie); Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH); Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA); éQuipe AppRentissage et MultimediA Marseille (QARMA); Laboratoire d'informatique Fondamentale de Marseille (LIF); Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS); éQuipe d'AppRentissage de MArseille (QARMA); Laboratoire d'Informatique et des Systèmes (LIS) (Marseille, Toulon) (LIS); Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS); Institut universitaire de France (IUF); Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.)
    • بيانات النشر:
      HAL CCSD
      IEEE
    • الموضوع:
      2017
    • Collection:
      Université de Toulon: HAL
    • نبذة مختصرة :
      International audience ; Several sparsity-constrained algorithms such as Orthogonal Matching Pursuit or the Frank-Wolfe algorithm with sparsity constraints work by iteratively selecting a novel atom to add to the current non-zero set of variables. This selection step is usually performed by computing the gradient and then by looking for the gradient component with maximal absolute entry. This step can be computationally expensive especially for large-scale and high-dimensional data. In this work, we aim at accelerating these sparsity-constrained optimization algorithms by exploiting the key observation that, for these algorithms to work, one only needs the coordinate of the gradient's top entry. Hence, we introduce algorithms based on greedy methods and randomization approaches that aim at cheaply estimating the gradient and its top entry. Another of our contribution is to cast the problem of finding the best gradient entry as a best arm identification in a multi-armed bandit problem. Owing to this novel insight, we are able to provide a bandit-based algorithm that directly estimates the top entry in a very efficient way. Theoretical observations stating that the resulting inexact Frank-Wolfe or Orthogonal Matching Pursuit algorithms act, with high probability, similarly to their exact versions are also given. We have carried out several experiments showing that the greedy deterministic and the bandit approaches we propose can achieve an acceleration of an order of magnitude while being as efficient as the exact gradient when used in algorithms such as OMP, Frank-Wolfe or CoSaMP.
    • Relation:
      hal-01774838; https://hal.science/hal-01774838; https://hal.science/hal-01774838/document; https://hal.science/hal-01774838/file/inexact.pdf
    • الرقم المعرف:
      10.1109/TNNLS.2016.2600243
    • الدخول الالكتروني :
      https://hal.science/hal-01774838
      https://hal.science/hal-01774838/document
      https://hal.science/hal-01774838/file/inexact.pdf
      https://doi.org/10.1109/TNNLS.2016.2600243
    • Rights:
      info:eu-repo/semantics/OpenAccess
    • الرقم المعرف:
      edsbas.D1D7017A