4期

最新文章

• Convergence and Inference of Stream Stochastic Gradient Descent, with Applications to Queueing Systems and Inventory Control AI翻译
  作者：Li, Xiang; Liang, Jiadong; Chen, Xinyun; Zhang, Zhihua
  作者单位：Peking University; The Chinese University of Hong Kong, Shenzhen
  摘要：Stream stochastic gradient descent (SGD) is a simple and efficient method for solving online optimization problems in operations research (OR), where data are generated by parameter-dependent Markov chains. Unlike traditional approaches which require increasing batch sizes during iterations, stream SGD uses a single sample per iteration, significantly improving sample efficiency. This paper establishes a systematic framework for analyzing stream SGD, leveraging the Poisson equation solution to...
• Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives AI翻译
  作者：Behdin, Kayhan; Chen, Wenyu; Mazumder, Rahul
  作者单位：Massachusetts Institute of Technology (MIT)
  摘要：We consider the problem of learning a sparse graph underlying an undirected Gaussian graphical model, which is a key problem in statistical machine learning. Given n samples from a multivariate Gaussian distribution with p variables, the goal is to estimate the p x p inverse covariance matrix (aka precision matrix), assuming it is sparse (i.e., has a few nonzero entries). We propose GraphL0BnB, a new estimator based on an & euro;0-penalized version of the pseudo-likelihood function; most earli...
• On the Complexity of Finding Locally Optimal Solutions in Bilevel Linear Optimization AI翻译
  作者：Prokopyev, Oleg A.; Ralphs, Ted K.
  作者单位：University of Zurich; Lehigh University
  摘要：We consider the computational complexity of finding locally optimal solutions to bilevel linear optimization problems (BLPs), from the leader's perspective. We show that, for any constant c > 0, the problem of finding a leader's solution that is within Euclidean distance c(n) of any locally optimal leader's solution, where n is the total number of variables, is NP-hard. Our derivations exploit techniques similar to those used for the analogous result for quadratic optimization problems (QPs). ...
• Stochastic Gradient Descent with Adaptive Data AI翻译
  作者：Che, Ethan; Dong, Jing; Tong, Xin T.
  作者单位：Columbia University; National University of Singapore
  摘要：Stochastic gradient descent (SGD) is a powerful optimization technique that is particularly useful in online learning scenarios. Its convergence analysis is relatively well understood under the assumption that the data samples are independent and identically distributed (iid). However, applying SGD to policy optimization problems in operations research involves a distinct challenge: the policy changes the environment and thereby affects the data used to update the policy. The adaptively genera...
• Online Learning and Optimization for Queues with Unknown Arrival Rate and Service Distribution AI翻译
  作者：Chen, Xinyun; Hong, Guiyu; Liu, Yunan
  作者单位：The Chinese University of Hong Kong, Shenzhen; Shanghai University of Finance & Economics; Amazon.com; North Carolina State University
  摘要：We investigate an optimization problem in a queueing system where the service provider selects the optimal service fee p and service capacity & micro; to maximize the cumulative expected profit (the service revenue minus the capacity cost and delay penalty). The conventional predict-then-optimize (PTO) approach takes two steps: First, it estimates the model parameters (e.g., arrival rate and service-time distribution) from data; second, it optimizes a model taking these parameters as input. A ...
• Risk Minimization as a Framework for Online Allocation in Display Advertising AI翻译
  作者：Shamsi, Davood; Luenberger, Robert; Ye, Yinyu
  作者单位：Shanghai Jiao Tong University; Shanghai Institute for Mathematics & Interdisciplinary Sciences
  摘要：This research note revisits the framework proposed in our earlier work and explores its conceptual and algorithmic connection to recent advances in dual-based online resource allocation-particularly the dual mirror descent method introduced previously. Both approaches address the challenge of making real-time sequential allocation decisions under dynamically revealed constraints. Although the dual mirror descent method relies on Bregman divergence to guide dual updates, our framework derives n...
• The Pandora's Box Problem with Sequential Inspections AI翻译
  作者：Aouad, Ali; Ji, Jingwei; Shaposhnik, Yaron
  作者单位：Massachusetts Institute of Technology (MIT); Stanford University; University of Rochester
  摘要：The Pandora's box problem is a core model in economic theory that captures an agent's (Pandora's) search for the best alternative (box). We study an important generalization of the problem in which the agent can either fully open boxes for a certain fee to reveal their exact values or partially open them at a reduced cost. This introduces a new trade-off between information acquisition and cost efficiency. We establish a hardness result and employ an array of techniques in stochastic optimizat...
• A Note on Piecewise Affine Decision Rules for Robust, Stochastic, and Data-Driven Optimization AI翻译
  作者：Thomae, Simon; Schiffer, Maximilian; Wiesemann, Wolfram
  作者单位：RWTH Aachen University; Technical University of Munich; Technical University of Munich; Imperial College London
  摘要：Multistage decision making under uncertainty, where decisions are taken under sequentially revealing uncertain problem parameters, is often essential to faithfully model managerial problems. Given the significant computational challenges involved, these problems are typically solved approximately. This short note introduces an algorithmic framework that revisits a popular approximation scheme for multistage stochastic programs and improves on it to deliver superior policies in the stochastic s...
• Tail Optimality and Performance Analysis of the Nudge*(M) Scheduling Algorithm AI翻译
  作者：Charlet, Nils; Van Houdt, Benny
  作者单位：University of Antwerp
  摘要：Recently it was shown that the response time of first-come-first-served (FCFS) scheduling can be stochastically and asymptotically improved upon by the Nudge scheduling algorithm in case of light-tailed job size distributions. Such improvements are feasible even when the jobs are partitioned into two types, and the scheduler only has information about the type of incoming jobs (but not their size). In this paper, we introduce Nudge*(M) scheduling, where basically any incoming type 1 job is all...
• Dual Sourcing in an Assembly System: A Simple and Effective Critical-Set Base-Surge Policy AI翻译
  作者：Deng, Tianhu; Shao, Feiyu; Song, Jing-Sheng Jeannette; Yu, Yi
  作者单位：Soochow University - China; Tsinghua University; Duke University; Shanghai University of Finance & Economics
  摘要：To enhance supply chain resilience, assembly manufacturers increasingly adopt dual-sourcing strategies, utilizing both regular and faster but costlier express sources for each key component. Although research has focused on single-item systems, coordinating dual-sourced orders across multiple components in an assembly system remains underexplored. To address this gap, we introduce a novel Critical-Set Base-Surge (CSBS) policy, which combines a constant order policy for regular sources to meet ...