Online discovery of similarity mappings

We consider the problem of choosing, sequentially, a map which assigns elements of a set A to a few elements of a set B. On each round, the algorithm suffers some cost associated with the chosen assignment, and the goal is to minimize the cumulative loss of these choices relative to the best map on the entire sequence. Even though the offline problem of finding the best map is provably hard, we show that there is an equivalent online approximation algorithm, Randomized Map Prediction (RMP), that is efficient and performs nearly as well. While drawing upon results from the "Online Prediction with Expert Advice" setting, we show how RMP can be utilized as an online approach to several standard batch problems. We apply RMP to online clustering as well as online feature selection and, surprisingly, RMP often outperforms the standard batch algorithms on these problems.

Implicit online learning

Online learning algorithms have recently risen to prominence due to their strong theoretical guarantees and an increasing number of practical applications for large-scale data analysis problems. In this paper, we analyze a class of online learning algorithms based on fixed potentials and nonlinearized losses, which yields algorithms with implicit update rules. We show how to efficiently compute these updates, and we prove regret bounds for the algorithms. We apply our formulation to several special cases where our approach has benefits over existing online learning methods. In particular, we provide improved algorithms and bounds for the online metric learning problem, and show improved robustness for online linear prediction problems. Results over a variety of data sets demonstrate the advantages of our framework.

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.

Matrix regularization techniques for online multitask learning

In this paper we examine the problem of prediction with expert advice in a setup where the learner is presented with a sequence of examples coming from different tasks. In order for the learner to be able to benefit from performing multiple tasks simultaneously, we make assumptions of task relatedness by constraining the comparator to use a lesser number of best experts than the number of tasks. We show how this corresponds naturally to learning under spectral or structural matrix constraints, and propose regularization techniques to enforce the constraints. The regularization techniques proposed here are interesting in their own right and multitask learning is just one application for the ideas. A theoretical analysis of one such regularizer is performed, and a regret bound that shows benefits of this setup is reported.

Closing the gap between bandit and full-information online optimization : high-probability regret bound

We demonstrate a modification of the algorithm of Dani et al for the online linear optimization problem in the bandit setting, which allows us to achieve an O( \sqrt{T ln T} ) regret bound in high probability against an adaptive adversary, as opposed to the in expectation result against an oblivious adversary of Dani et al. We obtain the same dependence on the dimension as that exhibited by Dani et al. The results of this paper rest firmly on those of Dani et al and the remarkable technique of Auer et al for obtaining high-probability bounds via optimistic estimates. This paper answers an open question: it eliminates the gap between the high-probability bounds obtained in the full-information vs bandit settings.

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.

Health professionals' recognition of co-occurring alcohol and depressive disorders in youth: a survey of Australian general practitioners, psychiatrists, psychologists and mental health nurses using case vignettes

Objective: To examine whether health professionals who commonly deal with mental disorder are able to identify co occurring alcohol misuse in young people presenting with depression. Method: Between September 2006 and January 2007, a survey examining beliefs regarding appropriate interventions for mental disorder in youth was sent to 1710 psychiatrists, 2000 general practitioners (GPs), 1628 mental health nurses, and 2000 psychologists in Australia. Participants within each professional group were randomly given one of four vignettes describing a young person with a DSM-IV mental disorder. Herein is reported data from the depression and depression with alcohol misuse vignettes. Results: A total of 305 psychiatrists, 258 GPs, 292 mental health nurses and 375 psychologists completed one of the depression vignettes. A diagnosis of mood disorder was identified by at least 83.8% of professionals, with no significant differences noted between professional groups. Rates of reported co-occurring substance use disorders were substantially lower, particularly among older professionals and psychologists. Conclusions: GPs, psychologists and mental health professionals do not readily identify co-occurring alcohol misuse in young people with depression. Given the substantially negative impact of co-occurring disorders, it is imperative that health-care professionals are appropriately trained to detect such disorders promptly, to ensure young people have access to effective, early intervention.

Helping someone with problem drinking: Mental health first aid guidelines - a Delphi expert consensus study

Background Alcohol is a leading risk factor for avoidable disease burden. Research suggests that a drinker's social network can play an integral role in addressing hazardous (i.e., high-risk) or problem drinking. Often however, social networks do not have adequate mental health literacy (i.e., knowledge about mental health problems, like problem drinking, or how to treat them). This is a concern as the response that a drinker receives from their social network can have a substantial impact on their willingness to seek help. This paper describes the development of mental health first aid guidelines that inform community members on how to help someone who may have, or may be developing, a drinking problem (i.e., alcohol abuse or dependence). Methods A systematic review of the research and lay literature was conducted to develop a 285-item survey containing strategies on how to help someone who may have, or may be developing, a drinking problem. Two panels of experts (consumers/carers and clinicians) individually rated survey items, using a Delphi process. Surveys were completed online or via postal mail. Participants were 99 consumers, carers and clinicians with experience or expertise in problem drinking from Australia, Canada, Ireland, New Zealand, the United Kingdom, and the United States. Items that reached consensus on importance were retained and written into guidelines. Results The overall response rate across all three rounds was 68.7% (67.6% consumers/carers, 69.2% clinicians), with 184 first aid strategies rated as essential or important by ≥80% of panel members. The endorsed guidelines provide guidance on how to: recognize problem drinking; approach someone if there is concern about their drinking; support the person to change their drinking; respond if they are unwilling to change their drinking; facilitate professional help seeking and respond if professional help is refused; and manage an alcohol-related medical emergency. Conclusion The guidelines provide a consensus-based resource for community members seeking to help someone with a drinking problem. Improving community awareness and understanding of how to identify and support someone with a drinking problem may lead to earlier recognition of problem drinking and greater facilitation of professional help seeking.