Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Efficient Online Clustering with Moving Costs
 
conference paper not in proceedings

Efficient Online Clustering with Moving Costs

Christou, Dimitris
•
Skoulakis, Efstratios Panteleimon  
•
Cevher, Volkan  orcid-logo
2023
37th Conference on Neural Information Processing Systems (NeurIPS 2023)

In this work we consider an online learning problem, called Online k-Clustering with Moving Costs, at which a learner maintains a set of k facilities over T rounds so as to minimize the connection cost of an adversarially selected sequence of clients. The learner is informed on the positions of the clients at each round t only after its facility-selection and can use this information to update its decision in the next round. However, updating the facility positions comes with an additional moving cost based on the moving distance of the facilities. We present the first O(log n)-regret polynomial-time online learning algorithm guaranteeing that the overall cost (connection + moving) is at most O(log n) times the time-averaged connection cost of the best fixed solution. Our work improves on the recent result of Fotakis et al. [31] establishing O(k)-regret guarantees only on the connection cost.

  • Files
  • Details
  • Metrics
Type
conference paper not in proceedings
Author(s)
Christou, Dimitris
Skoulakis, Efstratios Panteleimon  
Cevher, Volkan  orcid-logo
Date Issued

2023

Subjects

ML-AI

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LIONS  
Event nameEvent placeEvent date
37th Conference on Neural Information Processing Systems (NeurIPS 2023)

New Orlean, USA

December 10-16. 2023

Available on Infoscience
July 2, 2024
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/208965
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés