Optimal strategies and minimax lower bounds for online convex games

A number of learning problems can be cast as an Online Convex Game: on each round, a learner makes a prediction x from a convex set, the environment plays a loss function f, and the learner’s long-term goal is to minimize regret. Algorithms have been proposed by Zinkevich, when f is assumed to be convex, and Hazan et al., when f is assumed to be strongly convex, that have provably low regret. We consider these two settings and analyze such games from a minimax perspective, proving minimax strategies and lower bounds in each case. These results prove that the existing algorithms are essentially optimal.

Entropic bounds for multi-scale and multi-physics coupling in earth sciences

The ability to understand and predict how thermal, hydrological,mechanical and chemical (THMC) processes interact is fundamental to many research initiatives and industrial applications. We present (1) a new Thermal– Hydrological–Mechanical–Chemical (THMC) coupling formulation, based on non-equilibrium thermodynamics; (2) show how THMC feedback is incorporated in the thermodynamic approach; (3) suggest a unifying thermodynamic framework for multi-scaling; and (4) formulate a new rationale for assessing upper and lower bounds of dissipation for THMC processes. The technique is based on deducing time and length scales suitable for separating processes using a macroscopic finite time thermodynamic approach. We show that if the time and length scales are suitably chosen, the calculation of entropic bounds can be used to describe three different types of material and process uncertainties: geometric uncertainties,stemming from the microstructure; process uncertainty, stemming from the correct derivation of the constitutive behavior; and uncertainties in time evolution, stemming from the path dependence of the time integration of the irreversible entropy production. Although the approach is specifically formulated here for THMC coupling we suggest that it has a much broader applicability. In a general sense it consists of finding the entropic bounds of the dissipation defined by the product of thermodynamic force times thermodynamic flux which in material sciences corresponds to generalized stress and generalized strain rates, respectively.

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.

Combining initial segments of lists

We propose a new way to build a combined list from K base lists, each containing N items. A combined list consists of top segments of various sizes from each base list so that the total size of all top segments equals N. A sequence of item requests is processed and the goal is to minimize the total number of misses. That is, we seek to build a combined list that contains all the frequently requested items. We first consider the special case of disjoint base lists. There, we design an efficient algorithm that computes the best combined list for a given sequence of requests. In addition, we develop a randomized online algorithm whose expected number of misses is close to that of the best combined list chosen in hindsight. We prove lower bounds that show that the expected number of misses of our randomized algorithm is close to the optimum. In the presence of duplicate items, we show that computing the best combined list is NP-hard. We show that our algorithms still apply to a linearized notion of loss in this case. We expect that this new way of aggregating lists will find many ranking applications.

A new type of high-order elements based on the mesh-free interpolations

We propose a new type of high-order elements that incorporates the mesh-free Galerkin formulations into the framework of finite element method. Traditional polynomial interpolation is replaced by mesh-free interpolations in the present high-order elements, and the strain smoothing technique is used for integration of the governing equations based on smoothing cells. The properties of high-order elements, which are influenced by the basis function of mesh-free interpolations and boundary nodes, are discussed through numerical examples. It can be found that the basis function has significant influence on the computational accuracy and upper-lower bounds of energy norm, when the strain smoothing technique retains the softening phenomenon. This new type of high-order elements shows good performance when quadratic basis functions are used in the mesh-free interpolations and present elements prove advantageous in adaptive mesh and nodes refinement schemes. Furthermore, it shows less sensitive to the quality of element because it uses the mesh-free interpolations and obeys the Weakened Weak (W2) formulation as introduced in [3, 5].

Correcting for bias when estimating the cost of hospital-acquired infection : an analysis of lower respiratory tract infections in non-surgical patients

Hospital acquired infections (HAI) are costly but many are avoidable. Evaluating prevention programmes requires data on their costs and benefits. Estimating the actual costs of HAI (a measure of the cost savings due to prevention) is difficult as HAI changes cost by extending patient length of stay, yet, length of stay is a major risk factor for HAI. This endogeneity bias can confound attempts to measure accurately the cost of HAI. We propose a two-stage instrumental variables estimation strategy that explicitly controls for the endogeneity between risk of HAI and length of stay. We find that a 10% reduction in ex ante risk of HAI results in an expected savings of £693 ($US 984).