View in EDS

Distributed Online Optimization With Long-Term Constraints.

Saved in:
Bibliographic Details
Title: Distributed Online Optimization With Long-Term Constraints.
Authors: Yuan, Deming1 dmyuan1012@gmail.com, Proutiere, Alexandre2 alepro@kth.se, Shi, Guodong3 guodong.shi@sydney.edu.au
Source: IEEE Transactions on Automatic Control. Mar2022, Vol. 67 Issue 3, p1089-1104. 16p.
Subjects: Convex functions, Vector valued functions, Time perspective, Distributed algorithms
Abstract: In this article, we consider distributed online convex optimization problems, where the distributed system consists of various computing units connected through a time-varying communication graph. In each time step, each computing unit selects a constrained vector, experiences a loss equal to an arbitrary convex function evaluated at this vector, and may communicate to its neighbors in the graph. The objective is to minimize the system-wide loss accumulated over time. We propose a decentralized algorithm with regret and cumulative constraint violation in ${\mathcal O}(T^{\max \lbrace c,1-c\rbrace })$ and ${\mathcal O}(T^{1-c/2})$ , respectively, for any $c\in (0,1)$ , where $T$ is the time horizon. When the loss functions are strongly convex, we establish improved regret and constraint violation upper bounds in ${\mathcal O}(\log (T))$ and ${\mathcal O}(\sqrt{T\log (T)})$. These regret scalings match those obtained by state-of-the-art algorithms and fundamental limits in the corresponding centralized online optimization problem (for both convex and strongly convex loss functions). In the case of bandit feedback, the proposed algorithms achieve a regret and constraint violation in ${\mathcal O}(T^{\max \lbrace c,1-c/3 \rbrace })$ and ${\mathcal O}(T^{1-c/2})$ for any $c\in (0,1)$. We numerically illustrate the performance of our algorithms for the particular case of distributed online regularized linear regression problems on synthetic and real data. [ABSTRACT FROM AUTHOR]
Copyright of IEEE Transactions on Automatic Control is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 155494954
AccessLevel: 6
PubType: Periodical
PubTypeId: serialPeriodical
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Distributed Online Optimization With Long-Term Constraints.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Yuan%2C+Deming%22">Yuan, Deming</searchLink><relatesTo>1</relatesTo><i> dmyuan1012@gmail.com</i><br /><searchLink fieldCode="AR" term="%22Proutiere%2C+Alexandre%22">Proutiere, Alexandre</searchLink><relatesTo>2</relatesTo><i> alepro@kth.se</i><br /><searchLink fieldCode="AR" term="%22Shi%2C+Guodong%22">Shi, Guodong</searchLink><relatesTo>3</relatesTo><i> guodong.shi@sydney.edu.au</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Automatic+Control%22">IEEE Transactions on Automatic Control</searchLink>. Mar2022, Vol. 67 Issue 3, p1089-1104. 16p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Convex+functions%22">Convex functions</searchLink><br /><searchLink fieldCode="DE" term="%22Vector+valued+functions%22">Vector valued functions</searchLink><br /><searchLink fieldCode="DE" term="%22Time+perspective%22">Time perspective</searchLink><br /><searchLink fieldCode="DE" term="%22Distributed+algorithms%22">Distributed algorithms</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: In this article, we consider distributed online convex optimization problems, where the distributed system consists of various computing units connected through a time-varying communication graph. In each time step, each computing unit selects a constrained vector, experiences a loss equal to an arbitrary convex function evaluated at this vector, and may communicate to its neighbors in the graph. The objective is to minimize the system-wide loss accumulated over time. We propose a decentralized algorithm with regret and cumulative constraint violation in ${\mathcal O}(T^{\max \lbrace c,1-c\rbrace })$ and ${\mathcal O}(T^{1-c/2})$ , respectively, for any $c\in (0,1)$ , where $T$ is the time horizon. When the loss functions are strongly convex, we establish improved regret and constraint violation upper bounds in ${\mathcal O}(\log (T))$ and ${\mathcal O}(\sqrt{T\log (T)})$. These regret scalings match those obtained by state-of-the-art algorithms and fundamental limits in the corresponding centralized online optimization problem (for both convex and strongly convex loss functions). In the case of bandit feedback, the proposed algorithms achieve a regret and constraint violation in ${\mathcal O}(T^{\max \lbrace c,1-c/3 \rbrace })$ and ${\mathcal O}(T^{1-c/2})$ for any $c\in (0,1)$. We numerically illustrate the performance of our algorithms for the particular case of distributed online regularized linear regression problems on synthetic and real data. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of IEEE Transactions on Automatic Control is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=155494954
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1109/TAC.2021.3057601
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 16
        StartPage: 1089
    Subjects:
      – SubjectFull: Convex functions
        Type: general
      – SubjectFull: Vector valued functions
        Type: general
      – SubjectFull: Time perspective
        Type: general
      – SubjectFull: Distributed algorithms
        Type: general
    Titles:
      – TitleFull: Distributed Online Optimization With Long-Term Constraints.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Yuan, Deming
      – PersonEntity:
          Name:
            NameFull: Proutiere, Alexandre
      – PersonEntity:
          Name:
            NameFull: Shi, Guodong
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 03
              Text: Mar2022
              Type: published
              Y: 2022
          Identifiers:
            – Type: issn-print
              Value: 00189286
          Numbering:
            – Type: volume
              Value: 67
            – Type: issue
              Value: 3
          Titles:
            – TitleFull: IEEE Transactions on Automatic Control
              Type: main
ResultId 1