**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Publication# Efficient Online Clustering with Moving Costs

Abstract

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.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (16)

Related MOOCs (2)

Related publications (39)

Cost

In production, research, retail, and accounting, a cost is the value of money that has been used up to produce something or deliver a service, and hence is not available for use anymore. In business, the cost may be one of acquisition, in which case the amount of money expended to acquire it is counted as cost. In this case, money is the input that is gone in order to acquire the thing. This acquisition cost may be the sum of the cost of production as incurred by the original producer, and further costs of transaction as incurred by the acquirer over and above the price paid to the producer.

Connection form

In mathematics, and specifically differential geometry, a connection form is a manner of organizing the data of a connection using the language of moving frames and differential forms. Historically, connection forms were introduced by Élie Cartan in the first half of the 20th century as part of, and one of the principal motivations for, his method of moving frames. The connection form generally depends on a choice of a coordinate frame, and so is not a tensorial object.

Connection (mathematics)

In geometry, the notion of a connection makes precise the idea of transporting local geometric objects, such as tangent vectors or tensors in the tangent space, along a curve or family of curves in a parallel and consistent manner. There are various kinds of connections in modern geometry, depending on what sort of data one wants to transport. For instance, an affine connection, the most elementary type of connection, gives a means for parallel transport of tangent vectors on a manifold from one point to another along a curve.

Introduction to optimization on smooth manifolds: first order methods

Learn to optimize on smooth, nonlinear spaces: Join us to build your foundations (starting at "what is a manifold?") and confidently implement your first algorithm (Riemannian gradient descent).

Introduction to Programming in C++

Ce cours initie à la programmation en utilisant le langage C++. Il ne présuppose pas de connaissance préalable. Les aspects plus avancés (programmation orientée objet) sont donnés dans un cours suivan

Anastasia Ailamaki, Viktor Sanca, Eleni Zapridou, Stefan Igescu

K-means is one of the fundamental unsupervised data clustering and machine learning methods. It has been well studied over the years: parallelized, approximated, and optimized for different cases and applications. With increasingly higher parallelism leadi ...

2023Robert West, Maxime Jean Julien Peyrard, Marija Sakota

Generative language models (LMs) have become omnipresent across data science. For a wide variety of tasks, inputs can be phrased as natural language prompts for an LM, from whose output the solution can then be extracted. LM performance has consistently be ...

A strategic roadmap for noncarbonized fuels is a global priority, and the reduction of carbon dioxide emissions is a key focus of the Paris Agreement to mitigate the effects of rising temperatures. In this context, hydrogen is a promising noncarbonized fue ...