2023

最新文章

• Technical Note-The Elliptical Potential Lemma for General Distributions with an Application to Linear Thompson Sampling AI翻译
  作者：Hamidi, Nima; Bayati, Mohsen
  作者单位：Stanford University; Stanford University
  摘要：In this note, we introduce a general version of the well-known elliptical potential lemma that is a widely used technique in the analysis of algorithms in sequential learning and decision-making problems. We consider a stochastic linear bandit setting where decision makers sequentially choose among a set of given actions, observe their noisy rewards, and aim to maximize their cumulative expected reward over a decision-making horizon. The elliptical potential lemma is a key tool for quantifying...
• Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality AI翻译
  作者：Gao, Rui
  作者单位：University of Texas System; University of Texas Austin
  摘要：Wasserstein distributionally robust optimization (DRO) aims to find robust and generalizable solutions by hedging against data perturbations in Wasserstein distance. Despite its recent empirical success in operations research and machine learning, existing performance guarantees for generic loss functions are either overly conservative because of the curse of dimensionality or plausible only in large sample asymptotics. In this paper, we develop a nonasymptotic framework for analyzing the out-...
• The Anchor-Robust Project Scheduling Problem AI翻译
  作者：Bendotti, Pascale; Chretienne, Philippe; Fouilhoux, Pierre; Pass-Lanneau, Adele
  作者单位：Electricite de France (EDF); Sorbonne Universite; Centre National de la Recherche Scientifique (CNRS)
  摘要：In project scheduling with uncertain processing times, the decision maker often needs to compute a baseline schedule in advance while guaranteeing that some jobs will not be rescheduled later. Standard robust approaches either produce a schedule with a very large makespan or offer no guarantee on starting times of the jobs. The concept of anchor-robustness is introduced as a middle ground between these approaches. A subset of jobs is said to be anchored if the starting times of its jobs in the...
• A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers AI翻译
  作者：Srivastava, Prateek R.; Sarkar, Purnamrita; Hanasusanto, Grani A.
  作者单位：University of Texas System; University of Texas Austin; University of Texas System; University of Texas Austin; University of Texas System; University of Texas Austin
  摘要：We consider the problem of clustering data sets in the presence of arbitrary outliers. Traditional clustering algorithms such as k-means and spectral clustering are known to perform poorly for data sets contaminated with even a small number of outliers. In this paper, we develop a provably robust spectral clustering algorithm that applies a simple rounding scheme to denoise a Gaussian kernel matrix built from the data points and uses vanilla spectral clustering to recover the cluster labels of...
• Managing Queues with Different Resource Requirements AI翻译
  作者：Zychlinski, Noa; Chan, Carri W.; Dong, Jing
  作者单位：Technion Israel Institute of Technology; Columbia University
  摘要：Queueing models that are used to capture various service settings typically assume that customers require a single unit of resource (server) to be processed. However, there are many service settings where such an assumption may fail to capture the heterogeneity in resource requirements of different customers. We propose a multiserver queueing model with multiple customer classes in which customers from different classes may require different amounts of resources to be served. We study the opti...
• Maximum Entropy Distributions with Applications to Graph Simulation AI翻译
  作者：Glasserman, Paul; de Larrea, Enrique Lelo
  作者单位：Columbia University; Columbia University
  摘要：We study the problem of sampling uniformly from discrete or continuous product sets subject to linear constraints. This family of problems includes sampling weighted bipartite, directed, and undirected graphs with given degree sequences. We analyze two candidate distributions for sampling from the target set. The first one maximizes entropy subject to satisfying the constraints in expectation. The second one is the distribution from an exponential family that maximizes the minimum probability ...
• Efficient Resource Allocation Contracts to Reduce Adverse Events AI翻译
  作者：Liang, Yong; Sun, Peng; Tang, Runyu; Zhang, Chong
  作者单位：Tsinghua University; Duke University; Xi'an Jiaotong University; Tilburg University
  摘要：Motivated by the allocation of online visits to product, service, and content suppliers in the platform economy, we consider a dynamic contract design problem in which a principal constantly determines the allocation of a resource (online visits) to multiple agents. Although agents are capable of running the business, they introduce adverse events, the frequency of which depends on each agent???s effort level. We study continuous-time dynamic contracts that utilize resource allocation and mone...
• Stability and Sample-Based Approximations of Composite Stochastic Optimization Problems AI翻译
  作者：Dentcheva, Darinka; Lin, Yang; Penev, Spiridon
  作者单位：Stevens Institute of Technology; University of New South Wales Sydney; University of New South Wales Sydney
  摘要：Optimization under uncertainty and risk is indispensable in many practical situations. Our paper addresses stability of optimization problems using composite risk functionals that are subjected to multiple measure perturbations. Our main focus is the asymptotic behavior of data-driven formulations with empirical or smoothing estimators such as kernels or wavelets applied to some or to all functions of the compositions. We analyze the properties of the new estimators and we establish strong law...
• Every Choice Function Is Pro-Con Rationalizable AI翻译
  作者：Dogan, Serhat; Yildiz, Kemal
  作者单位：Ihsan Dogramaci Bilkent University
  摘要：We consider an agent who is endowed with two sets of orderings: pro-and con orderings. For each choice set, if an alternative is the top-ranked by a pro-ordering (con-ordering), then this is a pro (con) for choosing that alternative. The alternative with more pros than cons is chosen from each choice set. Each ordering may have a weight reflecting its salience. In this case, the probability that an alternative is chosen equals the difference between the total weights of its pros and cons. We s...
• Early Reservation for Follow-up Appointments in a Slotted-Service Queue AI翻译
  作者：Ding, Yichuan; Gupta, Diwakar; Tang, Xiaoxu
  作者单位：McGill University; University of Texas System; University of Texas Austin; Wells Fargo Company
  摘要：We study an appointment-based slotted-service queue with the goal of maximizing service volume. Returning customers prefer to be served by the same service agent as in their previous visit. This model captures aspects of a whole host of settings, including medical clinics, law firms, and tutoring services. We consider a simple strategy that a service provider may use to reduce balking among returning customers-designate some returning customers as high-priority customers. These customers are p...