2022

最新文章

• Mixed-Integer Convex Representability AI翻译
  作者：Lubin, Miles; Vielma, Juan Pablo; Zadik, Ilias
  作者单位：Alphabet Inc.; Google Incorporated; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); New York University
  摘要：Motivated by recent advances in solution methods for mixed-integer convex optimization (MICP), we study the fundamental and open question of which sets can be represented exactly as feasible regions of MICP problems. We establish several results in this direction, including the first complete characterization for the mixed-binary case and a simple necessary condition for the general case. We use the latter to derive the first nonrepresentability results for various nonconvex sets, such as the ...
• Bounding Residence Times for Atomic Dynamic Routings AI翻译
  作者：Cao, Zhigang; Chen, Bo; Chen, Xujin; Wang, Changjun
  作者单位：Beijing Jiaotong University; University of Warwick; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS
  摘要：In this paper, we are concerned with bounding agents' residence times in the network for a broad class of atomic dynamic routings. We explore novel token techniques to circumvent direct analysis on complicated chain effects of dynamic routing choices. Even though agents may enter the network over time for an infinite number of periods, we prove that under a mild condition, the residence time of every agent is upper bounded (by a network-dependent constant plus the total number of agents inside...
• Distributionally Robust Inventory Control When Demand Is a Martingale AI翻译
  作者：Xin, Linwei; Goldberg, David Alan
  作者单位：University of Chicago; Cornell University
  摘要：Demand forecasting plays an important role in many inventory control problems. To mitigate the potential harms of model misspecification in this context, various forms of distributionally robust optimization have been applied. Although many of these methodologies suffer from the problem of time inconsistency, the work of Kiabjan et al. established a general time-consistent framework for such problems by connecting to the literature on robust Markov decision processes. Motivated by the fact tha...
• A Variable Sample-Size Stochastic Quasi-Newton Method for Smooth and Nonsmooth Stochastic Convex Optimization AI翻译
  作者：Jalilzadeh, Afrooz; Nedic, Angelia; Shanbhag, Uday, V; Yousefian, Farzad
  作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Arizona State University; Arizona State University-Tempe; Oklahoma State University System; Oklahoma State University - Stillwater
  摘要：Classical theory for quasi-Newton schemes has focused on smooth, deterministic, unconstrained optimization, whereas recent forays into stochastic convex optimization have largely resided in smooth, unconstrained, and strongly convex regimes. Naturally, there is a compelling need to address nonsmoothness, the lack of strong convexity, and the presence of constraints. Accordingly, this paper presents a quasi-Newton framework that can process merely convex and possibly nonsmooth (but smoothable) ...
• Geometrically Convergent Simulation of the Extrema of Levy Processes AI翻译
  作者：Gonzalez Cazares, Jorge Ignacio; Mijatovic, Aleksandar; Uribe Bravo, Geronimo
  作者单位：Alan Turing Institute; University of Warwick; Universidad Nacional Autonoma de Mexico
  摘要：We develop a novel approximate simulation algorithm for the joint law of the position, the running supremum, and the time of the supremum of a general Levy process at an arbitrary finite time. We identify the law of the error in simple terms. We prove that the error decays geometrically in L-p (for any p >= 1) as a function of the computational cost, in contrast with the polynomial decay for the approximations available in the literature. We establish a central limit theorem and construct nona...
• Strong Embeddings for Transitory Queueing Models AI翻译
  作者：Chakraborty, Prakash; Honnappa, Harsha
  作者单位：Purdue University System; Purdue University; Purdue University System; Purdue University
  摘要：In this paper, we establish strong embedding theorems, in the sense of the Komlos-Major-Tusnady framework, for the performance metrics of a general class of transitory queueing models of nonstationary queueing systems. The nonstationary and non-Markovian nature of these models makes the computation of performance metrics hard. The strong embeddings yield error bounds on sample path approximations by diffusion processes in the formof functional strong approximation theorems.
• Variational Analysis of Composite Models with Applications to Continuous Optimization AI翻译
  作者：Mohammadi, Ashkan; Mordukhovich, Boris S.; Sarabi, M. Ebrahim
  作者单位：Wayne State University; University System of Ohio; Miami University
  摘要：The paper is devoted to a comprehensive study of composite models in variational analysis and optimization the importance of which for numerous theoretical, algorithmic, and applied issues of operations research is difficult to overstate. The underlying theme of our study is a systematical replacement of conventional metric regularity and related requirements by much weaker metric subregulatity ones that lead us to significantly stronger and completely new results of first-order and second-ord...
• Graphical Convergence of Subgradients in Nonconvex Optimization and Learning AI翻译
  作者：Davis, Damek; Drusvyatskiy, Dmitriy
  作者单位：Cornell University; University of Washington; University of Washington Seattle
  摘要：We investigate the stochastic optimization problem of minimizing population risk, where the loss defining the risk is assumed to be weakly convex. Compositions of Lipschitz convex functions with smooth maps are the primary examples of such losses. We analyze the estimation quality of such nonsmooth and nonconvex problems by their sample average approximations. Our main results establish dimension-dependent rates on subgradient estimation in full generality and dimension-independent rates when ...
• Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model AI翻译
  作者：Fei, Yingjie; Chen, Yudong
  作者单位：Cornell University; University of Wisconsin System; University of Wisconsin Madison
  摘要：We consider the problem of estimating the discrete clustering structures under the sub-Gaussian mixture model. Our main results establish a hidden integrality property of a semidefinite programming (SDP) relaxation for this problem: while the optimal solution to the SDP is not integer-valued in general, its estimation error can be upper bounded by that of an idealized integer program. The error of the integer program, and hence that of the SDP, are further shown to decay exponentially in the s...
• Suboptimal Local Minima Exist for Wide Neural Networks with Smooth Activations AI翻译
  作者：Ding, Tian; Li, Dawei; Sun, Ruoyu
  作者单位：Chinese University of Hong Kong; University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign
  摘要：Does a large width eliminate all suboptimal local minima for neural nets? An affirmative answer was given by a classic result published in 1995 for one-hidden-layer wide neural nets with a sigmoid activation function, but this result has not been extended to the multilayer case. Recently, it was shown that, with piecewise linear activations, suboptimal local minima exist even for wide nets. Given the classic positive result on smooth activation and the negative result on nonsmooth activations,...