Follow the leader if you can, hedge if you must

Follow-the-Leader (FTL) is an intuitive sequential prediction strategy that guarantees constant regret in the stochastic setting, but has poor performance for worst-case data. Other hedging strategies have better worst-case guarantees but may perform much worse than FTL if the data are not maximally adversarial. We introduce the FlipFlop algorithm, which is the first method that provably combines the best of both worlds. As a stepping stone for our analysis, we develop AdaHedge, which is a new way of dynamically tuning the learning rate in Hedge without using the doubling trick. AdaHedge refines a method by Cesa-Bianchi, Mansour, and Stoltz (2007), yielding improved worst-case guarantees. By interleaving AdaHedge and FTL, FlipFlop achieves regret within a constant factor of the FTL regret, without sacrificing AdaHedge’s worst-case guarantees. AdaHedge and FlipFlop do not need to know the range of the losses in advance; moreover, unlike earlier methods, both have the intuitive property that the issued weights are invariant under rescaling and translation of the losses. The losses are also allowed to be negative, in which case they may be interpreted as gains.

Adaptive online gradient descent

We study the rates of growth of the regret in online convex optimization. First, we show that a simple extension of the algorithm of Hazan et al eliminates the need for a priori knowledge of the lower bound on the second derivatives of the observed functions. We then provide an algorithm, Adaptive Online Gradient Descent, which interpolates between the results of Zinkevich for linear functions and of Hazan et al for strongly convex functions, achieving intermediate rates between [square root T] and [log T]. Furthermore, we show strong optimality of the algorithm. Finally, we provide an extension of our results to general norms.

Learning the learning rate for prediction with expert advice

Most standard algorithms for prediction with expert advice depend on a parameter called the learning rate. This learning rate needs to be large enough to fit the data well, but small enough to prevent overfitting. For the exponential weights algorithm, a sequence of prior work has established theoretical guarantees for higher and higher data-dependent tunings of the learning rate, which allow for increasingly aggressive learning. But in practice such theoretical tunings often still perform worse (as measured by their regret) than ad hoc tuning with an even higher learning rate. To close the gap between theory and practice we introduce an approach to learn the learning rate. Up to a factor that is at most (poly)logarithmic in the number of experts and the inverse of the learning rate, our method performs as well as if we would know the empirically best learning rate from a large range that includes both conservative small values and values that are much higher than those for which formal guarantees were previously available. Our method employs a grid of learning rates, yet runs in linear time regardless of the size of the grid.

Open problem: Shifting experts on easy data

A number of online algorithms have been developed that have small additional loss (regret) compared to the best “shifting expert”. In this model, there is a set of experts and the comparator is the best partition of the trial sequence into a small number of segments, where the expert of smallest loss is chosen in each segment. The regret is typically defined for worst-case data / loss sequences. There has been a recent surge of interest in online algorithms that combine good worst-case guarantees with much improved performance on easy data. A practically relevant class of easy data is the case when the loss of each expert is iid and the best and second best experts have a gap between their mean loss. In the full information setting, the FlipFlop algorithm by De Rooij et al. (2014) combines the best of the iid optimal Follow-The-Leader (FL) and the worst-case-safe Hedge algorithms, whereas in the bandit information case SAO by Bubeck and Slivkins (2012) competes with the iid optimal UCB and the worst-case-safe EXP3. We ask the same question for the shifting expert problem. First, we ask what are the simple and efficient algorithms for the shifting experts problem when the loss sequence in each segment is iid with respect to a fixed but unknown distribution. Second, we ask how to efficiently unite the performance of such algorithms on easy data with worst-case robustness. A particular intriguing open problem is the case when the comparator shifts within a small subset of experts from a large set under the assumption that the losses in each segment are iid.

Using an extended theory of planned behavior to predict a change in the type of blood product donated

Background Demand for essential plasma-derived products is increasing. Purpose This prospective study aims to identify predictors of voluntary non-remunerated whole blood (WB) donors becoming plasmapheresis donors. Methods Surveys were sent to WB donors who had recently (recent n = 1,957) and not recently donated (distant n = 1,012). Theory of Planned Behavior (TPB) constructs (attitude, subjective norm, self-efficacy) were extended with moral norm, anticipatory regret, and donor identity. Intentions and objective plasmapheresis donation for 527 recent and 166 distant participants were assessed. Results Multi-group analysis revealed that the model was a good fit. Moral norm and self-efficacy were positively associated while role identity (suppressed by moral norm) was negatively associated with plasmapheresis intentions. Conclusions The extended TPB was useful in identifying factors that facilitate conversion from WB to plasmapheresis donation. A superordinate donor identity may be synonymous with WB donation and, for donors with a strong moral norm for plasmapheresis, may inhibit conversion.

Erratum: Multicentric carpotarsal osteolysis is caused by mutations clustering in the amino-terminal transcriptional activation domain of MAFB

(The American Journal of Human Genetics, 90, 494–501; March 9, 2012) In the published version of this article, the amino acid alteration caused by c.161C>T should have been notated as p.Ser54Leu and not p.Pro54Leu. The wild-type amino acid is incorrectly notated in the main text, in Table 2, and in Figure 4. The authors regret this error. Additionally, The Journal regrets that this erratum, originally requested in 2012, was not published in a timely fashion.

One practical algorithm for both stochastic and adversarial bandits

We present an algorithm for multiarmed bandits that achieves almost optimal performance in both stochastic and adversarial regimes without prior knowledge about the nature of the environment. Our algorithm is based on augmentation of the EXP3 algorithm with a new control lever in the form of exploration parameters that are tailored individually for each arm. The algorithm simultaneously applies the “old” control lever, the learning rate, to control the regret in the adversarial regime and the new control lever to detect and exploit gaps between the arm losses. This secures problem-dependent “logarithmic” regret when gaps are present without compromising on the worst-case performance guarantee in the adversarial regime. We show that the algorithm can exploit both the usual expected gaps between the arm losses in the stochastic regime and deterministic gaps between the arm losses in the adversarial regime. The algorithm retains “logarithmic” regret guarantee in the stochastic regime even when some observations are contaminated by an adversary, as long as on average the contamination does not reduce the gap by more than a half. Our results for the stochastic regime are supported by experimental validation.

Tracking adversarial targets

We study linear control problems with quadratic losses and adversarially chosen tracking targets. We present an efficient algorithm for this problem and show that, under standard conditions on the linear system, its regret with respect to an optimal linear policy grows as O(log^2 T), where T is the number of rounds of the game. We also study a problem with adversarially chosen transition dynamics; we present an exponentiallyweighted average algorithm for this problem, and we give regret bounds that grow as O(sqtr p T).

A randomized controlled trial protocol testing a decision support intervention for older patients with advanced kidney disease

Aim To assess the effectiveness of a decision support intervention using a pragmatic single blind Randomized Controlled Trial. Background Worldwide the proportion of older people (aged 65 years and over) is rising. This population is known to have a higher prevalence of chronic diseases including chronic kidney disease. The resultant effect of the changing health landscape is seen in the increase in older patients (aged ≥65 years) commencing on dialysis. Emerging evidence suggests that for some older patients dialysis may provide minimal benefit. In a majority of renal units non-dialysis management is offered as an alternative to undertaking dialysis. Research regarding decision-making support that is required to assist this population in choosing between dialysis or non-dialysis management is limited. Design. A multisite single blinded pragmatic randomized controlled trial is proposed. Methods Patients will be recruited from four Queensland public hospitals and randomizd into either the control or intervention group. The decision support intervention is multimodal and includes counselling provided by a trained nurse. The comparator is standard decision-making support. The primary outcomes are decisional regret and decisional conflict. Secondary outcomes are improved knowledge and quality of life. Ethics approval obtained November 2014. Conclusion This is one of the first randomized controlled trials assessing a decision support intervention in older people with advance chronic kidney disease. The results may provide guidance for clinicians in future approaches to assist this population in decision-making to ensure reduced decisional regret and decisional conflict.

Essays in Philosophical Moral Psychology

The dissertation consists of four essays and a comprehensive introduction that discusses the topics, methods, and most prominent theories of philosophical moral psychology. I distinguish three main questions: What are the essential features of moral thinking? What are the psychological conditions of moral responsibility? And finally, what are the consequences of empirical facts about human nature to normative ethics? Each of the three last articles focuses on one of these issues. The first essay and part of the introduction are dedicated to methodological questions, in particular the relationship between empirical (social) psychology and philosophy. I reject recent attempts to understand the nature of morality on the basis of empirical research. One characteristic feature of moral thinking is its practical clout: if we regard an action as morally wrong, we either refrain from doing it even against our desires and interests, or else feel shame or guilt. Moral views seem to have a conceptual connection to motivation and emotions – roughly speaking, we can’t conceive of someone genuinely disapproving an action, but nonetheless doing it without any inner motivational conflict or regret. This conceptual thesis in moral psychology is called (judgment) internalism. It implies, among other things, that psychopaths cannot make moral judgments to the extent that they are incapable of corresponding motivation and emotion, even if they might say largely the words we would expect. Is internalism true? Recently, there has been an explosion of interest in so-called experimental philosophy, which is a methodological view according to which claims about conceptual truths that appeal to our intuitions should be tested by way of surveys presented to ordinary language users. One experimental result is that the majority of people are willing to grant that psychopaths make moral judgments, which challenges internalism. In the first article, ‘The Rise and Fall of Experimental Philosophy’, I argue that these results pose no real threat to internalism, since experimental philosophy is based on a too simple conception of the relationship between language use and concepts. Only the reactions of competent users in pragmatically neutral and otherwise conducive circumstances yield evidence about conceptual truths, and such robust intuitions remain inaccessible to surveys for reasons of principle. The epistemology of folk concepts must still be based on Socratic dialogue and critical reflection, whose character and authority I discuss at the end of the paper. The internal connection between moral judgment and motivation led many metaethicists in the past century to believe along Humean lines that judgment itself consists in a pro-attitude rather than a belief. This expressivist view, as it is called these days, has far-reaching consequences in metaethics. In the second essay I argue that perhaps the most sophisticated form of contemporary expressivism, Allan Gibbard’s norm-expressivism, according to which moral judgments are decisions or contingency plans, is implausible from the perspective of the theory of action. In certain circumstances it is possible to think that something is morally required of one without deciding to do so. Morality is not a matter of the will. Instead, I sketch on the basis of Robert Brandom’s inferentialist semantics a weak form of judgment internalism, according to which the content of moral judgment is determined by a commitment to a particular kind of practical reasoning. The last two essays in the dissertation emphasize the role of mutual recognition in the development and maintenance of responsible and autonomous moral agency. I defend a compatibilist view of autonomy, according to which agents who are unable to recognize right and wrong or act accordingly are not responsible for their actions – it is not fair to praise or blame them, since they lacked the relevant capacity to do otherwise. Conversely, autonomy demands an ability to recognize reasons and act on them. But as a long tradition in German moral philosophy whose best-known contemporary representative is Axel Honneth has it, both being aware of reasons and acting on them requires also the right sort of higher-order attitudes toward the self. Without self-respect and self-confidence we remain at the mercy of external pressures, even if we have the necessary normative competence. These attitudes toward the self, in turn, are formed through mutual recognition – we value ourselves when those who we value value us. Thus, standing in the right sort of relations of recognition is indirectly necessary for autonomy and moral responsibility. Recognition and valuing are concretely manifest in actions and institutions, whose practices make possible participation on an equal footing. Seeing this opens the way for a kind of normative social criticism that is grounded in the value of freedom and automomy, but is not limited to defending negative rights. It thus offers a new way to bridge the gap between liberalism and communitarianism.

Hyveiden harjoittaminen : edellytykset ja esteet

In the first half of the 20th century, most moral philosophers took the concept of virtue to be secondary to moral principles or emotions, though in various and mutually conflicting ways. In the early 1960s interest in the virtues was restored by the analytic philosophers Elizabeth Anscombe and Georg Henrik von Wright, the younger colleagues and friends of the late Wittgenstein. Later, Alasdair MacIntyre became a leading virtue ethicist. In 1981, MacIntyre introduced in After Virtue the concept of practices, which he based on the Aristotelian distinction between praxis and poiesis. This dissertation examines MacIntyre s characterization of the interconnectedness between practices and virtues, especially in relation to skills, education, and certain emotions. The primary position of the virtues is defended against the tendency in modern moral philosophy to overemphasize the role either of principles and rules or of emotions. The view according to which rational action and acting according to the virtues is best conceptualized as following rules or principles is criticized by arguments that are grounded by some Wittgensteinian observations, and that can be characterized as transcendental. Even if the virtues cannot be defined by, and are not based entirely on, emotions, the role of certain emotions on the learning and education of skills and virtues are studied more carefully than by MacIntyre. In the cases of resentment, indignation, and shame, the analysis of Peter Strawson is utilized, and in the case of regret, the analysis of Bernard Williams. Williams analysis of regret and moral conflict concludes in a kind of antirealism, which this study criticizes. Where education of practices and skills and the related reactive emotions are examined as conditions of learning and practicing the virtues, institutions and ideologies are examined as obstacles and threats to the virtues. This theme is studied through Karl Marx s conception of alienation and Karl Polanyi s historical and sociological research concerning the great transformation . The study includes six Finnish-published articles carrying the titles Our negative attitudes towards other persons , Authority and upbringing , Moral conflicts, regret and ethical realism , Practices and institutions , Doing justice as condition to communal action: a transcendental argument for justice as virtue , and Alienation from practices in capitalist society: Alasdair MacIntyre s Marxist Aristotelianism . The introductory essay sums up the themes of the articles and presents some central issues of virtue ethics by relating the classical Socratic questions to Aristotelian practical philosophy, as well as to current controversies in metaethics and moral psychology.

A non-cooperative game-theoretic approach to channel assignment in multi-channel multi-radio wireless networks

Channel assignment in multi-channel multi-radio wireless networks poses a significant challenge due to scarcity of number of channels available in the wireless spectrum. Further, additional care has to be taken to consider the interference characteristics of the nodes in the network especially when nodes are in different collision domains. This work views the problem of channel assignment in multi-channel multi-radio networks with multiple collision domains as a non-cooperative game where the objective of the players is to maximize their individual utility by minimizing its interference. Necessary and sufficient conditions are derived for the channel assignment to be a Nash Equilibrium (NE) and efficiency of the NE is analyzed by deriving the lower bound of the price of anarchy of this game. A new fairness measure in multiple collision domain context is proposed and necessary and sufficient conditions for NE outcomes to be fair are derived. The equilibrium conditions are then applied to solve the channel assignment problem by proposing three algorithms, based on perfect/imperfect information, which rely on explicit communication between the players for arriving at an NE. A no-regret learning algorithm known as Freund and Schapire Informed algorithm, which has an additional advantage of low overhead in terms of information exchange, is proposed and its convergence to the stabilizing outcomes is studied. New performance metrics are proposed and extensive simulations are done using Matlab to obtain a thorough understanding of the performance of these algorithms on various topologies with respect to these metrics. It was observed that the algorithms proposed were able to achieve good convergence to NE resulting in efficient channel assignment strategies.

Receiver-only optimized Vector Quantization for fading channels

This paper considers the design and analysis of a filter at the receiver of a source coding system to mitigate the excess distortion caused due to channel errors. The index output by the source encoder is sent over a fading discrete binary symmetric channel and the possibly incorrect received index is mapped to the corresponding codeword by a Vector Quantization (VQ) decoder at the receiver. The output of the VQ decoder is then processed by a receive filter to obtain an estimate of the source instantiation. The distortion performance is analyzed for weighted mean square error (WMSE) and the optimum receive filter that minimizes the expected distortion is derived for two different cases of fading. It is shown that the performance of the system with the receive filter is strictly better than that of a conventional VQ and the difference becomes more significant as the number of bits transmitted increases. Theoretical expressions for an upper and lower bound on the WMSE performance of the system with the receive filter and a Rayleigh flat fading channel are derived. The design of a receive filter in the presence of channel mismatch is also studied and it is shown that a minimax solution is the one obtained by designing the receive filter for the worst possible channel. Simulation results are presented to validate the theoretical expressions and illustrate the benefits of receive filtering.

Multi-Armed Bandit Mechanisms for Multi-Slot Sponsored Searth Auctions

In pay-per click sponsored search auctions which are currently extensively used by search engines, the auction for a keyword involves a certain number of advertisers (say k) competing for available slots (say m) to display their ads. This auction is typically conducted for a number of rounds (say T). There are click probabilities mu_ij associated with agent-slot pairs. The search engine's goal is to maximize social welfare, for example, the sum of values of the advertisers. The search engine does not know the true value of an advertiser for a click to her ad and also does not know the click probabilities mu_ij s. A key problem for the search engine therefore is to learn these during the T rounds of the auction and also to ensure that the auction mechanism is truthful. Mechanisms for addressing such learning and incentives issues have recently been introduced and would be referred to as multi-armed-bandit (MAB) mechanisms. When m = 1,characterizations for truthful MAB mechanisms are available in the literature and it has been shown that the regret for such mechanisms will be O(T^{2/3}). In this paper, we seek to derive a characterization in the realistic but nontrivial general case when m > 1 and obtain several interesting results.

Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions

In pay-per-click sponsored search auctions which are currently extensively used by search engines, the auction for a keyword involves a certain number of advertisers (say k) competing for available slots (say m) to display their advertisements (ads for short). A sponsored search auction for a keyword is typically conducted for a number of rounds (say T). There are click probabilities mu(ij) associated with each agent slot pair (agent i and slot j). The search engine would like to maximize the social welfare of the advertisers, that is, the sum of values of the advertisers for the keyword. However, the search engine does not know the true values advertisers have for a click to their respective advertisements and also does not know the click probabilities. A key problem for the search engine therefore is to learn these click probabilities during the initial rounds of the auction and also to ensure that the auction mechanism is truthful. Mechanisms for addressing such learning and incentives issues have recently been introduced. These mechanisms, due to their connection to the multi-armed bandit problem, are aptly referred to as multi-armed bandit (MAB) mechanisms. When m = 1, exact characterizations for truthful MAB mechanisms are available in the literature. Recent work has focused on the more realistic but non-trivial general case when m > 1 and a few promising results have started appearing. In this article, we consider this general case when m > 1 and prove several interesting results. Our contributions include: (1) When, mu(ij)s are unconstrained, we prove that any truthful mechanism must satisfy strong pointwise monotonicity and show that the regret will be Theta T7) for such mechanisms. (2) When the clicks on the ads follow a certain click precedence property, we show that weak pointwise monotonicity is necessary for MAB mechanisms to be truthful. (3) If the search engine has a certain coarse pre-estimate of mu(ij) values and wishes to update them during the course of the T rounds, we show that weak pointwise monotonicity and type-I separatedness are necessary while weak pointwise monotonicity and type-II separatedness are sufficient conditions for the MAB mechanisms to be truthful. (4) If the click probabilities are separable into agent-specific and slot-specific terms, we provide a characterization of MAB mechanisms that are truthful in expectation.