2026

最新文章

• 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...
• Optimized Dimensionality Reduction for Moment-Based Distributionally Robust Optimization AI翻译
  作者：Jiang, Shiyi; Cheng, Jianqiang; Pan, Kai; Shen, Zuo-Jun Max
  作者单位：Hong Kong Polytechnic University; University of Arizona; University of California System; University of California Berkeley; University of Hong Kong; University of Hong Kong
  摘要：Moment-based distributionally robust optimization (DRO) provides an optimization framework to integrate statistical information with traditional optimization approaches. Under this framework, one assumes that the underlying joint distribution of random parameters runs in a distributional ambiguity set constructed by moment information and makes decisions against the worst-case distribution within the set. Although most moment-based DRO problems can be reformulated as semidefinite programming (...
• Exponential Concentration in Stochastic Approximation AI翻译
  作者：Law, Kody . T. H.; Walton, Neil; Yang, Shangda
  作者单位：University of Manchester; Durham University
  摘要：We analyze the behavior of stochastic approximation algorithms where iterates, in expectation, progress toward an objective at each step. When progress is proportional to the step size of the algorithm, we prove exponential concentration bounds. These tailbounds contrast asymptotic normality results, which are more frequently associated with stochastic approximation. The methods that we develop rely on a proof of geometric ergodicity. The extends results on the exponential ergodicity of Markov...
• The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model AI翻译
  作者：Shi, Laixi; Li, Gen; Wei, Yuting; Chen, Yuxin; Geist, Matthieu; Chi, Yuejie
  作者单位：Johns Hopkins University; Chinese University of Hong Kong; University of Pennsylvania; Yale University
  摘要：This paper investigates model robustness in reinforcement learning (RL) to reduce the sim-to-real gap in practice. We adopt the framework of distributionally robust Markov decision processes (RMDPs), aimed at learning a policy that optimizes the worst-case performance when the deployed environment falls within a prescribed uncertainty set around the nominal Markov decision process (MDP). Despite recent efforts, the sample complexity of RMDPs remained mostly unsettled regardless of the uncertai...
• 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). ...
• Integrated Conditional Estimation-Optimization AI翻译
  作者：Qi, Meng; Grigas, Paul; Shen, Zuo-Jun (max)
  作者单位：Cornell University; University of California System; University of California Berkeley; University of Hong Kong; University of Hong Kong
  摘要：Many real-world optimization problems involve uncertain parameters with probability distributions that can be estimated using contextual feature information. In contrast to the standard approach of first estimating the distribution of uncertain parameters and then optimizing the objective based on the estimation, we propose an integrated conditional estimation-optimization (ICEO) framework that estimates the underlying conditional distribution of the random parameter while considering the stru...
• LEGO: Optimal Online Learning Under Sequential Price Competition AI翻译
  作者：Li, Shukai; Shi, Cong; Mehrotra, Sanjay
  作者单位：New York University; NYU Shanghai; University of Miami; Northwestern University
  摘要：We consider price competition among multiple sellers over a selling horizon of T periods. In each period, sellers simultaneously set prices and subsequently observe their own demand realizations, which are unobservable to competitors. The realized demand of each seller depends on the prices of all sellers and follows a private, unknown linear model. We propose a least-squares estimation and then gradient optimization (LEGO) policy, which does not require sellers to share demand information or ...
• Optimal Inventory Allocation for Indifferent Goods Under Dynamic Substitution AI翻译
  作者：Zhou, Ziyan; Wang, Tong; Zhang, Tingwei
  作者单位：Shanghai Jiao Tong University; City University of Hong Kong; The Chinese University of Hong Kong, Shenzhen
  摘要：Stockout-based substitution creates complex stochastic dynamics in inventory systems even in highly symmetric settings. We study a joint assortment and inventory allocation problem in which a firm allocates a fixed total inventory of m units across n perfectly substitutable product types (e.g., colors or designs). Customers are indifferent among available types and arrive sequentially, each purchasing one unit chosen uniformly at random from the nonempty types. The sales process terminates whe...
• On the Convergence of Modified Policy Iteration in Risk-Sensitive Exponential Cost Markov Decision Processes AI翻译
  作者：Murthy, Yashaswini; Moharrami, Mehrdad; Srikant, Rayadurgam
  作者单位：California Institute of Technology; University of Iowa; University of Illinois System; University of Illinois Urbana-Champaign
  摘要：Modified policy iteration (MPI) is a dynamic programming algorithm that combines elements of policy iteration and value iteration. The convergence of MPI is wellstudied in the context of discounted and average-cost Markov decision processes (MDPs). In this work, we consider the exponential cost risk-sensitive MDP formulation, which is known to provide some robustness to model parameters. Although policy iteration and value iteration are well-studied in the context of risk-sensitive MDPs, MPI i...