اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRobust bounds and optimization at the large deviations scale for queueing models via Renyi divergence
75
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
This paper develops tools to obtain robust probabilistic estimates for queueing models at the large deviations (LD) scale. These tools are based on the recently introduced robust Renyi bounds, which provide LD estimates (and more generally risk-sensitive (RS) cost estimates) that hold uniformly over an uncertainty class of models, provided that the class is defined in terms of Renyi divergence with respect to a reference model and that estimates are available for the reference model. One very attractive quality of the approach is that the class to which the estimates apply may consist of hard models, such as highly non-Markovian models and ones for which the LD principle is not available. Our treatment provides exact expressions as well as bounds on the Renyi divergence rate on families of marked point processes, including as a special case renewal processes. Another contribution is a general result that translates robust RS control problems, where robustness is formulated via Renyi divergence, to finite dimensional convex optimization problems, when the control set is a finite dimensional convex set. The implications to queueing are vast, as they apply in great generality. This is demonstrated on two non-Markovian queueing models. One is the multiclass single-server queue considered as a RS control problem, with scheduling as the control process and exponential weighted queue length as cost. The second is the many-server queue with reneging, with the probability of atypically large reneging count as performance criterion. As far as LD analysis is concerned, no robust estimates or non-Markovian treatment were previously available for either of these models.
قيم البحث
اقرأ أيضاً
We formulate the large deviations for a class of two scale chemical kinetic processes motivated from biological applications. The result is successfully applied to treat a genetic switching model with positive feedbacks. The corresponding Hamiltonian
is convex with respect to the momentum variable as a by-product of the large deviation theory. This property ensures its superiority in the rare event simulations compared with the result obtained by formal WKB asymptotics. The result is of general interest to understand the large deviations for multiscale problems.
We propose and analyze algorithms for distributionally robust optimization of convex losses with conditional value at risk (CVaR) and $chi^2$ divergence uncertainty sets. We prove that our algorithms require a number of gradient evaluations independe
nt of training set size and number of parameters, making them suitable for large-scale applications. For $chi^2$ uncertainty sets these are the first such guarantees in the literature, and for CVaR our guarantees scale linearly in the uncertainty level rather than quadratically as in previous work. We also provide lower bounds proving the worst-case optimality of our algorithms for CVaR and a penalized version of the $chi^2$ problem. Our primary technical contributions are novel bounds on the bias of batch robust risk estimation and the variance of a multilevel Monte Carlo gradient estimator due to [Blanchet & Glynn, 2015]. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
We study two one-parameter families of point processes connected to random matrices: the Sine_beta and Sch_tau processes. The first one is the bulk point process limit for the Gaussian beta-ensemble. For beta=1, 2 and 4 it gives the limit of the GOE,
GUE and GSE models of random matrix theory. In particular, for beta=2 it is a determinantal point process conjectured to have similar behavior to the critical zeros of the Riemann zeta-function. The second process can be obtained as the bulk scaling limit of the spectrum of certain discrete one-dimensional random Schrodinger operators. Both processes have asymptotically constant average density, in our normalization one expects close to lambda/(2pi) points in a large interval of length lambda. Our main results are large deviation principles for the average densities of the processes, essentially we compute the asymptotic probability of seeing an unusual average density in a large interval. Our approach is based on the representation of the counting functions of these processes using stochastic differential equations. We also prove path level large deviation principles for the arising diffusions. Our techniques work for the full range of parameter values. The results are novel even in the classical beta=1, 2 and 4 cases for the Sine_beta process. They are consistent with the existing rigorous results on large gap probabilities and confirm the physical predictions made using log-gas arguments.
Risk control and optimal diversification constitute a major focus in the finance and insurance industries as well as, more or less consciously, in our everyday life. We present a discussion of the characterization of risks and of the optimization of
portfolios that starts from a simple illustrative model and ends by a general functional integral formulation. A major theme is that risk, usually thought one-dimensional in the conventional mean-variance approach, has to be addressed by the full distribution of losses. Furthermore, the time-horizon of the investment is shown to play a major role. We show the importance of accounting for large fluctuations and use the theory of Cramer for large deviations in this context. We first treat a simple model with a single risky asset that examplifies the distinction between the average return and the typical return, the role of large deviations in multiplicative processes, and the different optimal strategies for the investors depending on their size. We then analyze the case of assets whose price variations are distributed according to exponential laws, a situation that is found to describe reasonably well daily price variations. Several portfolio optimization strategies are presented that aim at controlling large risks. We end by extending the standard mean-variance portfolio optimization theory, first within the quasi-Gaussian approximation and then using a general formulation for non-Gaussian correlated assets in terms of the formalism of functional integrals developed in the field theory of critical phenomena.
Renyi divergence is related to Renyi entropy much like Kullback-Leibler divergence is related to Shannons entropy, and comes up in many settings. It was introduced by Renyi as a measure of information that satisfies almost the same axioms as Kullback
-Leibler divergence, and depends on a parameter that is called its order. In particular, the Renyi divergence of order 1 equals the Kullback-Leibler divergence. We review and extend the most important properties of Renyi divergence and Kullback-Leibler divergence, including convexity, continuity, limits of $sigma$-algebras and the relation of the special order 0 to the Gaussian dichotomy and contiguity. We also show how to generalize the Pythagorean inequality to orders different from 1, and we extend the known equivalence between channel capacity and minimax redundancy to continuous channel inputs (for all orders) and present several other minimax results.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
