The empirical risk minimization (ERM) problem with relative entropy regularization (ERM-RER) is investigated under the assumption that the reference measure is a σ-finite measure, and not necessarily a probability measure. Under this assumption, which leads to a generalization of the ERM-RER problem allowing a larger degree of flexibility for incorporating prior knowledge, numerous relevant properties are stated. Among these properties, the solution to this problem, if it exists, is shown to be a unique probability measure, mutually absolutely continuous with the reference measure. Such a solution exhibits a probably-approximately-correct guarantee for the ERM problem independently of whether the latter possesses a solution. For a fixed dataset and under a specific condition, the empirical risk is shown to be a sub-Gaussian random variable when the models are sampled from the solution to the ERM-RER problem. The generalization capabilities of the solution to the ERM-RER problem (the Gibbs algorithm) are studied via the sensitivity of the expected empirical risk to deviations from such a solution towards alternative probability measures. Finally, an interesting connection between sensitivity, generalization error, and lautum information is established.

In this paper, 2×2 zero-sum games are studied under the following assumptions: (1) One of the players (the leader) commits to choose its actions by sampling a given probability measure (strategy); (2) The leader announces its action, which is observed by its opponent (the follower) through a binary channel; and (3) the follower chooses its strategy based on the knowledge of the leader’s strategy and the noisy observation of the leader’s action. Under these conditions, the equilibrium is shown to always exist. Interestingly, even subject to noise, observing the actions of the leader is shown to be either beneficial or immaterial for the follower. More specifically, the payoff at the equilibrium of this game is upper bounded by the payoff at the Stackelberg equilibrium (SE) in pure strategies; and lower bounded by the payoff at the Nash equilibrium, which is equivalent to the SE in mixed strategies. Finally, necessary and sufficient conditions for observing the payoff at equilibrium to be equal to its lower bound are presented. Sufficient conditions for the payoff at equilibrium to be equal to its upper bound are also presented.

The optimality and sensitivity of the empirical risk minimization problem with relative entropy regularization (ERM-RER) are investigated for the case in which the reference is a σ-finite measure instead of a probability measure. This generalization allows for a larger degree of flexibility in the incorporation of prior knowledge over the set of models. In this setting, the interplay of the regularization parameter, the reference measure, the risk function, and the empirical risk induced by the solution of the ERM-RER problem is characterized. This characterization yields necessary and sufficient conditions for the existence of regularization parameters that achieve arbitrarily small empirical risk with arbitrarily high probability. Additionally, the sensitivity of the expected empirical risk to deviations from the solution of the ERM-RER problem is studied. Dataset-dependent and dataset-independent upper bounds on the absolute value of the sensitivity are presented. In a special case, it is shown that the expectation (with respect to the datasets) of the absolute value of the sensitivity is upper bounded, up to a constant factor, by the square root of the lautum information between the models and the datasets.

Prefetching control is a vital operation for the On-demand interactive systems where the instantaneous response is the crucial factor for the system success. The controller in such type of interactive system operates in an uncertain environment and makes sequences of decisions with long and short term stochastic effects. The difficulty, then, is to determine at every system state which contents to prefect into the cache. We address the prefetching control problem in which the controller seeks to reach a Zero-Cost system state as quickly as possible while minimizing costs along the way (i.e. taking the shortest path). We model this control problem as a Negative Stochastic Dynamic Programming problem in which we minimize the undiscounted total expected cost. Our first contribution is formulating the prefetching problem as a control problem using the Markov Decision Process formalism. Our control model, PREF-CT, integrates the main models necessary for an adequate prefetching control operation, the prediction model, the access model, the network resource model, and the performance model. Our second contribution is the detection of a special structure of the optimal prefetching policy. Exploiting this special structure permits to develop two strategically different algorithms, ONE-PASS and TREE-DEC, which improve the complexity of computing the optimal prefetching policy.

We consider a single-server queue in discrete time, in which customers must be served before some limit sojourn time of geometrical distribution. A customer who is not served before this limit leaves the system: it is impatient. The service of customers, the loss due to impatience and the holding of customers in the queue induce costs. The purpose is to decide when to serve the customers so as to minimize them. We use a Markov decision process with infinite horizon and discounted cost. We establish the structural properties of the stochastic dynamic programming operator and we deduce that the optimal policy is of threshold type. In addition, we are able to compute explicitly the optimal value of this threshold in terms of the parameters of problem.

The paper deals with the study of the optimisation of the distribution of the download time from a particular video on demand system. This VOD system is based on grid delivery network which is an hybrid architecture based on P2P and grid computing concepts. In this system, the data are shrunk into fixed size blocks which must be replicated on hosts to decrease the total download time. We propose an optimal replication factor to optimise the average download time. We showed that the allocation methods are directly correlated with the variance of response waiting time. We analyse different heuristics to solve these two problems in practice, and validate them through simulation. With our methods, we can guarantee a pre-established waiting response time with an error of approximately 10%.

In this paper, we examine the data replication problem in a particular grid delivery network (GDN). In this system, the data are divided into fixed size blocks which must be replicated on hosts to decrease the total download time. We propose a probabilistic model to optimize the average download time of requests based on the hosts availability and the document size distribution. The objective function induced by this model is a nonlinear integer problem. It can be solved in real values by Lagrangian optimization. We prove that in a particular case, this problem can be reduced to a knapsack problem. We propose approximation algorithms and validate them using simulations with varying characteristics.

Our work focuses on an adaptive approach to RED, namely ARED (adaptive RED) that performs a constant tuning of RED parameters according to the traffic load. ARED requires no hypothesis on the type of traffic, which diminishes its dependency on the scenario parameters such as the bandwidth, the round-trip time and the number of active connections. Our goal is to find a simple extension to ARED in order to improve the predictability of performance measures like queueing delay and delay jitter without sacrificing the loss rate. To achieve this goal, we propose a new algorithm that sets the RED parameters and evaluate it by extensive simulations. Our results show that compared to the original ARED, our algorithm can stabilize the queue size, keep it away from buffer overflow and underflow, and achieves a more predictable average queue size without substantially increasing the loss rate.

We consider a system of uniform recurrence equations of dimension 1 and we show how its computation can be carried out using minimal memory size with several synchronous processors. This result is then applied to register minimization for digital circuits and parallel computation of task graphs.

Schemes based on the tagging of packets have been proposed as a low-cost way to augment the single class best effort service model of the current Internet by including some kind of service discrimination. Such schemes have a number of attractive features, however, it is not clear exactly what kind of service they would provide to applications. Yet quantifying such service is very important to understand the benefits and drawbacks of the different tagging schemes and of the mechanisms in each scheme (for example how much RED with input and output (RIO) contributes in the assured scheme), and to tackle key performance and economic issues (e.g. the difference in tariff between different service classes would presumably depend on the difference in performance between the classes). The goal in this paper is to obtain a quantitative description of the service provided by tagging schemes. Specifically, we describe and solve simple analytic models of two previously proposed schemes, namely the assured service scheme and the premium service scheme. We obtain expressions for performance measures that characterize the service provided to tagged packets, the service provided to non-tagged packets, and the fraction of tagged packets that do not get the better service they were supposed to. We use these expressions, as well as simulations and experiments from actual implementations, to illustrate the benefits and shortcomings of the schemes.

The purpose of this paper is to obtain the distribution of the number of lost packets within a sequence of n consecutive packet arrivals into a finite buffer M/M/1 queue. We obtain explicit expressions for the multidimensional generating function of these probabilities based on a recursive scheme introduced by Cidon et al. (1993). We then analyze the loss probabilities of a whole message, and analyze the effect of adding redundant packets. We show that in both heavy traffic as well as in light traffic conditions, adding redundant packets results in decreasing the message loss probabilities.

We show how the analysis of Markov modulated rate processes can be used to address the problem of computing the distribution of W, the stationary workload in the MMPP/GI/1 queue. Using the results of papers by Anick et al. (1982); Mitra (1988); and Elwalid et al. (1991), we present the decomposition properties of the Laplace transform of W and efficient computational algorithms for computing its distribution. The techniques are also applied to compute the bounds on the distribution of W developed by Liu et al. (see JACM, vol.44, no.2, p.366-94, 1997). Numerical results illustrating the usefulness of the methods are given for the case of the superposition of independent, nonidentical sources.

We analyze the distribution of the delay of messages in an infinite capacity M/M/1 queue. A message is composed of n packets, and the arrival of the packets to the queue is Poisson. Our calculations are based on recursive schemes. We obtain explicit expressions for the Laplace-Stieltjes transform (LST) of the delays, which enables to obtain exact expressions for the moments of the delay in a complexity smaller than the one obtained by using recursive schemes. We repeat the above calculations for the case that messages are dispersed, i.e. packets from several sources arrive to an M/M/1 queue and are served according to the FIFO discipline. Hence, several packets of other messages may arrive between consecutive packets of a given message.

The purpose in the paper is to obtain the distribution of the number of lost packets within a sequence of n consecutive packet arrivals into a finite buffer M/M/1 queue. The authors obtain explicit expressions for the multi-dimensional generating function of these probabilities based on a recursive scheme introduced by Cidon et al. (1993)They then analyze the loss probabilities of a whole message, and analyze the effect of adding redundant packets. They show that in both heavy traffic as well as in light traffic conditions, adding redundant packets results in decreasing the message loss probabilities.>

article Free AccessParallel queues with resequencing Authors: Alain Jean-Marie INRIA, Valbonne, France INRIA, Valbonne, FranceView Profile , Levent Gün IBM, Research Triangle Park, NC IBM, Research Triangle Park, NCView Profile Authors Info & Claims Journal of the ACMVolume 40Issue 5Nov. 1993 pp 1188–1208https://doi.org/10.1145/174147.169748Published:01 November 1993Publication History 42citation575DownloadsMetricsTotal Citations42Total Downloads575Last 12 Months10Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Messages arrive randomly at one end of a slotted communication channel. They are assigned to (packed in) packets of fixed duration which queue up for transmission in first-in-first-out order; the packets are sent one per time slot. In a stochastic setting, where message durations are also random, we analyze a model which yields statistics on message delays and the number of waiting messages, assuming that the assignment protocol is the well-known next-fit rule of one-dimensional bin packing. A stability condition is obtained as a function of general discrete message-length distributions. As a by-product, we contribute a new result to the literature on the probabilistic analysis of the static next-fit bin-packing rule, viz. the limiting expected bin occupancy for general discrete distributions. Specializations of the results to constant message lengths and to uniform message-length distributions are worked out in detail.>