Non-asymptotic confidence bounds for the optimal value of a stochastic program

We discuss a general approach to building non-asymptotic confidence bounds for stochastic optimization problems. Our principal contribution is the observation that a Sample Average Approximation of a problem supplies upper and lower bounds for the optimal value of the problem which are essentially better than the quality of the corresponding optimal solutions. At the same time, such bounds are more reliable than “standard” confidence bounds obtained through the asymptotic approach. We also discuss bounding the optimal value of MinMax Stochastic Optimization and stochastically constrained problems. We conclude with a small simulation study illustrating the numerical behavior of the proposed bounds.

Lower bound to the mass of a relativistic three-boson system in the lightcone

The lower bound masses of the ground-state relativistic three-boson system in 1 + 1, 2 + 1 and 3 + 1 spacetime dimensions are obtained. We have considered a reduction of the ladder Bethe-Salpeter equation to the lightfront in a model with renormalized two-body contact interaction. The lower bounds are deduced with the constraint of reality of the two-boson subsystem mass. It is verified that, in some cases, the lower bound approaches the ground-state binding energy. The corresponding non-relativistic limits are also verified.

Mutual Information Rate and Bounds for It

The amount of information exchanged per unit of time between two nodes in a dynamical network or between two data sets is a powerful concept for analysing complex systems. This quantity, known as the mutual information rate (MIR), is calculated from the mutual information, which is rigorously defined only for random systems. Moreover, the definition of mutual information is based on probabilities of significant events. This work offers a simple alternative way to calculate the MIR in dynamical (deterministic) networks or between two time series (not fully deterministic), and to calculate its upper and lower bounds without having to calculate probabilities, but rather in terms of well known and well defined quantities in dynamical systems. As possible applications of our bounds, we study the relationship between synchronisation and the exchange of information in a system of two coupled maps and in experimental networks of coupled oscillators.

Bounds on the density of sources of ultra-high energy cosmic rays from the Pierre Auger Observatory

We derive lower bounds on the density of sources of ultra-high energy cosmic rays from the lack of significant clustering in the arrival directions of the highest energy events detected at the Pierre Auger Observatory. The density of uniformly distributed sources of equal intrinsic intensity was found to be larger than ~(0.06 - 5) × '10 POT. -4' 'Mpc POT. -3' at 95% CL, depending on the magnitude of the magnetic deflections. Similar bounds, in the range (0.2 - 7) × '10 POT. -4' 'Mpc POT. -3', were obtained for sources following the local matter distribution.

User-definable resource bounds analysis for logic programs

We present a static analysis that infers both upper and lower bounds on the usage that a logic program makes of a set of user-definable resources. The inferred bounds will in general be functions of input data sizes. A resource in our approach is a quite general, user-defined notion which associates a basic cost function with elementary operations. The analysis then derives the related (upper- and lower-bound) resource usage functions for all predicates in the program. We also present an assertion language which is used to define both such resources and resourcerelated properties that the system can then check based on the results of the analysis. We have performed some preliminary experiments with some concrete resources such as execution steps, bytes sent or received by an application, number of files left open, number of accesses to a datábase, number of calis to a procedure, number of asserts/retracts, etc. Applications of our analysis include resource consumption verification and debugging (including for mobile code), resource control in parallel/distributed computing, and resource-oriented specialization.

Lower bound cost estimation for logic programs

It is generally recognized that information about the runtime cost of computations can be useful for a variety of applications, including program transformation, granularity control during parallel execution, and query optimization in deductive databases. Most of the work to date on compile-time cost estimation of logic programs has focused on the estimation of upper bounds on costs. However, in many applications, such as parallel implementations on distributed-memory machines, one would prefer to work with lower bounds instead. The problem with estimating lower bounds is that in general, it is necessary to account for the possibility of failure of head unification, leading to a trivial lower bound of 0. In this paper, we show how, given type and mode information about procedures in a logic program, it is possible to (semi-automatically) derive nontrivial lower bounds on their computational costs. We also discuss the cost analysis for the special and frequent case of divide-and-conquer programs and show how —as a pragmatic short-term solution —it may be possible to obtain useful results simply by identifying and treating divide-and-conquer programs specially.

Resource bounds analysis.

We present a generic analysis that infers both upper and lower bounds on the usage that a program makes of a set of user-definable resources. The inferred bounds will in general be functions of input data sizes. A resource in our approach is a quite general, user-defined notion which associates a basic cost function with elementary operations. The analysis then derives the related (upper- and lower- bound) cost functions for all procedures in the program. We also present an assertion language which is used to define both such resources and resource-related properties that the system can then check based on the results of the analysis. We have performed some experiments with some concrete resource-related properties such as execution steps, bits sent or received by an application, number of arithmetic operations performed, number of calls to a procedure, number of transactions, etc. presenting the resource usage functions inferred and the times taken to perform the analysis. Applications of our analysis include resource consumption verification and debugging (including for mobile code), resource control in parallel/distributed computing, and resource-oriented specialization.

Aplicação da metodologia numérica “fast bounds crack” para uma estimativa eficiente da evolução do tamanho de trinca

A significant part of the life of a mechanical component occurs, the crack propagation stage in fatigue. Currently, it is had several mathematical models to describe the crack growth behavior. These models are classified into two categories in terms of stress range amplitude: constant and variable. In general, these propagation models are formulated as an initial value problem, and from this, the evolution curve of the crack is obtained by applying a numerical method. This dissertation presented the application of the methodology "Fast Bounds Crack" for the establishment of upper and lower bounds functions for model evolution of crack size. The performance of this methodology was evaluated by the relative deviation and computational times, in relation to approximate numerical solutions obtained by the Runge-Kutta method of 4th explicit order (RK4). Has been reached a maximum relative deviation of 5.92% and the computational time was, for examples solved, 130,000 times more higher than achieved by the method RK4. Was performed yet an Engineering application in order to obtain an approximate numerical solution, from the arithmetic mean of the upper and lower bounds obtained in the methodology applied in this work, when you don’t know the law of evolution. The maximum relative error found in this application was 2.08% which proves the efficiency of the methodology "Fast Bounds Crack".

A Stochastic View of Optimal Regret through Minimax Duality

We study the regret of optimal strategies for online convex optimization games. Using von Neumann's minimax theorem, we show that the optimal regret in this adversarial setting is closely related to the behavior of the empirical minimization algorithm in a stochastic process setting: it is equal to the maximum, over joint distributions of the adversary's action sequence, of the difference between a sum of minimal expected losses and the minimal empirical loss. We show that the optimal regret has a natural geometric interpretation, since it can be viewed as the gap in Jensen's inequality for a concave functional--the minimizer over the player's actions of expected loss--defined on a set of probability distributions. We use this expression to obtain upper and lower bounds on the regret of an optimal strategy for a variety of online learning problems. Our method provides upper bounds without the need to construct a learning algorithm; the lower bounds provide explicit optimal strategies for the adversary. Peter L. Bartlett, Alexander Rakhlin

Measuring mechanical properties of tendon in vivo

Introduction: Understanding the mechanical properties of tendon is an important step to guiding the process of improving athletic performance, predicting injury and treating tendinopathies. The speed of sound in a medium is governed by the bulk modulus and density for fluids and isotropic materials. However, for tendon,which is a structural composite of fluid and collagen, there is some anisotropy requiring an adjustment for Poisson’s ratio. In this paper, these relationships are explored and modelled using data collected, in vivo, on human Achilles tendon. Estimates for elastic modulus and hysteresis based on speed of sound data are then compared against published values from in vitro mechanical tests. Methods: Measurements using clinical ultrasound imaging, inverse dynamics and acoustic transmission techniques were used to determine dimensions, loading conditions and longitudinal speed of sound for the Achilles tendon during a series of isometric plantar flexion exercises against body weight. Upper and lower bounds for speed of sound versus tensile stress in the tendon were then modelled and estimates derived for elastic modulus and hysteresis. Results: Axial speed of sound varied between 1850 to 2090 m.s−1 with a non-linear, asymptotic dependency on the level of tensile stress in the tendon 5–35 MPa. Estimates derived for the elastic modulus ranged between 1–2 GPa. Hysteresis derived from models of the stress-strain relationship, ranged from 3–11%. These values agree closely with those previously reported from direct measurements obtained via in vitro mechanical tensile tests on major weight bearing tendons. Discussion: There is sufficiently good agreement between these indirect (speed of sound derived) and direct (mechanical tensile test derived) measures of tendon mechanical properties to validate the use of this non-invasive acoustic transmission technique. This non-invasive method is suitable for monitoring changes in tendon properties as predictors of athletic performance, injury or therapeutic progression.

Ergodic capacity and outage performance of amplify-and-forward protocols

This thesis analyses the performance bounds of amplify-and-forward relay channels which are becoming increasingly popular in wireless communication applications. The statistics of cascaded Nakagami-m fading model which is a major obstacle in evaluating the outage of wireless networks is analysed using Mellin transform. Furthermore, the upper and the lower bounds for the ergodic capacity of the slotted amplify-and-forward relay channel, for finite and infinite number of relays are derived using random matrix theory. The results obtained will enable wireless network designers to optimize the network resources, benefiting the consumers.

Non-invasive clinical measurement of the viscoelastic properties of tendon using acoustic wave transmission

Background. In isotropic materials, the speed of acoustic wave propagation is governed by the bulk modulus and density. For tendon, which is a structural composite of fluid and collagen, however, there is some anisotropy requiring an adjustment for Poisson's ratio. This paper explores these relationships using data collected, in vivo, on human Achilles tendon and then compares estimates of elastic modulus and hysteresis against published values from in vitro mechanical tests. Methods. Measurements using conventional B-model ultrasound imaging, inverse dynamics and acoustic transmission techniques were used to determine dimensions, loading conditions and longitudinal speed of sound in the Achilles tendon during a series of isometric plantar flexion exercises against body weight. Upper and lower bounds for speed of sound versus tensile stress in the tendon were then modelled and estimates of the elastic modulus and hysteresis of the Achilles tendon derived. Results. Axial speed of sound varied between 1850 and 2090 ms-1 with a non-linear, asymptotic dependency on the level of tensile stress (5-35 MPa) in the tendon. Estimates derived for the elastic modulus of the Achilles tendon ranged between 1-2 GPa. Hysteresis derived from models of the stress-strain relationship, ranged from 3-11%. Discussion. Estimates of elastic modulus agree closely with those previously reported from direct measurements obtained via mechanical tensile tests on major weight bearing tendons in vitro [1,2]. Hysteresis derived from models of the stress-strain relationship is consistent with direct measures from various mamalian tendon (7-10%) but is lower than previous estimates in human tendon (17-26%) [3]. This non-invasive method would appear suitable for monitoring changes in tendon properties during dynamic sporting activities.

Prediction with limited advice and multiarmed bandits with paid observations

We study two problems of online learning under restricted information access. In the first problem, prediction with limited advice, we consider a game of prediction with expert advice, where on each round of the game we query the advice of a subset of M out of N experts. We present an algorithm that achieves O(√(N/M)TlnN ) regret on T rounds of this game. The second problem, the multiarmed bandit with paid observations, is a variant of the adversarial N-armed bandit game, where on round t of the game we can observe the reward of any number of arms, but each observation has a cost c. We present an algorithm that achieves O((cNlnN) 1/3 T2/3+√TlnN ) regret on T rounds of this game in the worst case. Furthermore, we present a number of refinements that treat arm- and time-dependent observation costs and achieve lower regret under benign conditions. We present lower bounds that show that, apart from the logarithmic factors, the worst-case regret bounds cannot be improved.

Finite-SNR diversity-multiplexing trade-off of inter-vehicular cooperative diversity protocols

The finite-signal-to-noise ratio (SNR) diversity-multiplexing trade-off (DMT) of cooperative diversity protocols are investigated in vehicular networks based on cascaded Rayleigh fading. Lower bounds of DMT at finite SNR for orthogonal and non-orthogonal protocols are derived. The results showcase the first look into the achievable DMT trade-off of cooperative diversity in volatile vehicular environments. It is shown that the diversity gains are significantly suboptimal at realistic SNRs.

Development of a flexible design approach for the deflection zone behind road safety barriers

Flexible design practices broadly permit that design values outside the normal range can be accepted as appropriate for a site-specific context providing that the risk is evaluated and is tolerable. Execution of flexible design demands some evaluation of risk. In restoration projects, it may be the case that an immovable object exists within the zone of the expected deflection of a road safety barrier system. Only by design exception can the situation be determined to be acceptable. However, the notion of using flexible design for road safety barrier design is not well developed. The existence of a diminishing return relationship between safety benefits and provision of increased clear zone has been established previously. This paper proposes that a similar rationale might reasonably apply for the deflection zone behind road safety barriers and describes how the risk associated with road safety barriers might be quantified in order that defensible road safety barrier design can exist below the lower bounds of normal design standards. As such, the methodology described in this paper may provide some basis to enable road authorities to make informed design decisions, particularly for restoration, or “Brownfield”, projects.