Online Learning of Facility Locations

• URL: http://arxiv.org/abs/2007.02801v1
• Date: Mon, 6 Jul 2020 15:04:53 GMT
• Title: Online Learning of Facility Locations
• Authors: Stephen Pasteris, Ting He, Fabio Vitale, Shiqiang Wang, Mark Herbster
• Abstract summary: We provide a rigorous theoretical investigation of an online learning version of the Facility Location problem. In our formulation, we are given a set of sites and an online sequence of user requests. At each trial, the learner selects a subset of sites and then incurs a cost for each selected site and an additional cost which is the price of the user's connection to the nearest site in the selected subset.
• Score: 21.451413948517228
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we provide a rigorous theoretical investigation of an online learning version of the Facility Location problem which is motivated by emerging problems in real-world applications. In our formulation, we are given a set of sites and an online sequence of user requests. At each trial, the learner selects a subset of sites and then incurs a cost for each selected site and an additional cost which is the price of the user's connection to the nearest site in the selected subset. The problem may be solved by an application of the well-known Hedge algorithm. This would, however, require time and space exponential in the number of the given sites, which motivates our design of a novel quasi-linear time algorithm for this problem, with good theoretical guarantees on its performance.

Related papers

• No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! [56.80767500991973]
  We focus on two canonical settings: $(i)$ online resource allocation where rewards and costs are observed before action selection, and $(ii)$ online learning with resource constraints where they are observed after action selection, under full feedback or bandit feedback.<n>It is well known that achieving sublinear regret in these settings is impossible when reward and cost distributions may change arbitrarily over time.<n>We design general (primal-)dual methods that achieve sublinear regret with respect to baselines that follow the spending plan. Crucially, the performance of our algorithms improves when the spending plan ensures a well-balanced distribution of the budget
  arXiv  Detail & Related papers  (2025-06-16T08:42:31Z)
• Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices [13.68761797358598]
  We study the dynamic pricing problem with knapsack, addressing the challenge of balancing exploration and exploitation under resource constraints. We introduce three algorithms tailored to different informational settings: a Boundary Attracted Re-solve Method for full information, an online learning algorithm for scenarios with no prior information, and an estimate-then-select re-solve algorithm that leverages machine-learned informed prices with known upper bound of estimation errors.
  arXiv  Detail & Related papers  (2025-01-24T00:46:52Z)
• Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints [11.029788598491077]
  We introduce and study a new online problem motivated by emerging challenges in sustainability and energy. In $mathsfSOAD, an online player completes a workload by allocating and scheduling it on the of a metric space $(, d) per point. At each time step, a service cost function is revealed that represents the cost of the workload at each point, and the player must irrevocably decide the current allocation of work to points.
  arXiv  Detail & Related papers  (2024-08-14T22:08:06Z)
• Contractual Reinforcement Learning: Pulling Arms with Invisible Hands [68.77645200579181]
  We propose a theoretical framework for aligning economic interests of different stakeholders in the online learning problems through contract design. For the planning problem, we design an efficient dynamic programming algorithm to determine the optimal contracts against the far-sighted agent. For the learning problem, we introduce a generic design of no-regret learning algorithms to untangle the challenges from robust design of contracts to the balance of exploration and exploitation.
  arXiv  Detail & Related papers  (2024-07-01T16:53:00Z)
• Exponentially Weighted Algorithm for Online Network Resource Allocation with Long-Term Constraints [0.6466206145151128]
  This paper studies an online optimal resource reservation problem in communication networks with job transfers. We propose a novel algorithm based on a randomized exponentially weighted method that encompasses long-term constraints.
  arXiv  Detail & Related papers  (2024-05-03T10:12:40Z)
• Stop Relying on No-Choice and Do not Repeat the Moves: Optimal, Efficient and Practical Algorithms for Assortment Optimization [38.57171985309975]
  We develop efficient algorithms for the problem of regret in assortment selection with emphPlackett Luce (PL) based user choices. Our methods are practical, provably optimal, and devoid of the aforementioned limitations of the existing methods.
  arXiv  Detail & Related papers  (2024-02-29T07:17:04Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  We present efficient methods for optimizing dynamic regret and adaptive regret, which reduce the number of projections per round from $mathcalO(log T)$ to $1$. Our technique hinges on the reduction mechanism developed in parameter-free online learning and requires non-trivial twists on non-stationary online methods.
  arXiv  Detail & Related papers  (2023-09-16T07:30:12Z)
• Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making [73.48977854003697]
  This work introduces a new notion of complexity, the generalized bracketing numbers, which marries constraints on the adversary to the size of the space. We then instantiate our bounds in several problems of interest, including online prediction and planning of piecewise continuous functions.
  arXiv  Detail & Related papers  (2023-02-10T18:45:52Z)
• Online Resource Allocation: Bandits feedback and Advice on Time-varying Demands [12.081877372552606]
  We consider a general online resource allocation model with bandit feedback and time-varying demands. Motivated by the recent Online Algorithms with Advice framework, we explore how online advice can inform policy design. Our proposed algorithm is shown to have both theoretical performance and promising numerical results compared with other algorithms in literature.
  arXiv  Detail & Related papers  (2023-02-08T16:40:43Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  Existing primal-dual algorithms for constrained online learning problems rely on two fundamental assumptions. We show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers. We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions.
  arXiv  Detail & Related papers  (2023-02-02T16:30:33Z)
• Online Allocation with Two-sided Resource Constraints [44.5635910908944]
  We consider an online allocation problem subject to lower and upper resource constraints, where the requests arrive sequentially. We propose a new algorithm that obtains $1-O(fracepsilonalpha-epsilon)$ -competitive ratio for the offline problems that know the entire requests ahead of time.
  arXiv  Detail & Related papers  (2021-12-28T02:21:06Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• Decentralized Personalized Federated Learning for Min-Max Problems [79.61785798152529]
  This paper is the first to study PFL for saddle point problems encompassing a broader range of optimization problems. We propose new algorithms to address this problem and provide a theoretical analysis of the smooth (strongly) convex-(strongly) concave saddle point problems. Numerical experiments for bilinear problems and neural networks with adversarial noise demonstrate the effectiveness of the proposed methods.
  arXiv  Detail & Related papers  (2021-06-14T10:36:25Z)
• Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
  We consider a general online optimization problem with multiple budget constraints over a horizon of finite time periods. The objective of the decision maker is to maximize the cumulative reward subject to the budget constraints. This formulation captures a wide range of applications including online linear programming and network revenue management.
  arXiv  Detail & Related papers  (2020-12-13T04:47:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.