Multitask learning with expert advice

We consider the problem of prediction with expert advice in the setting where a forecaster is presented with several online prediction tasks. Instead of competing against the best expert separately on each task, we assume the tasks are related, and thus we expect that a few experts will perform well on the entire set of tasks. That is, our forecaster would like, on each task, to compete against the best expert chosen from a small set of experts. While we describe the “ideal” algorithm and its performance bound, we show that the computation required for this algorithm is as hard as computation of a matrix permanent. We present an efficient algorithm based on mixing priors, and prove a bound that is nearly as good for the sequential task presentation case. We also consider a harder case where the task may change arbitrarily from round to round, and we develop an efficient approximate randomized algorithm based on Markov chain Monte Carlo techniques.

Multitask learning with expert advice

We consider the problem of prediction with expert advice in the setting where a forecaster is presented with several online prediction tasks. Instead of competing against the best expert separately on each task, we assume the tasks are related, and thus we expect that a few experts will perform well on the entire set of tasks. That is, our forecaster would like, on each task, to compete against the best expert chosen from a small set of experts. While we describe the "ideal" algorithm and its performance bound, we show that the computation required for this algorithm is as hard as computation of a matrix permanent. We present an efficient algorithm based on mixing priors, and prove a bound that is nearly as good for the sequential task presentation case. We also consider a harder case where the task may change arbitrarily from round to round, and we develop an efficient approximate randomized algorithm based on Markov chain Monte Carlo techniques.

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.

Second-order quantile methods for experts and combinatorial games

We aim to design strategies for sequential decision making that adjust to the difficulty of the learning problem. We study this question both in the setting of prediction with expert advice, and for more general combinatorial decision tasks. We are not satisfied with just guaranteeing minimax regret rates, but we want our algorithms to perform significantly better on easy data. Two popular ways to formalize such adaptivity are second-order regret bounds and quantile bounds. The underlying notions of 'easy data', which may be paraphrased as "the learning problem has small variance" and "multiple decisions are useful", are synergetic. But even though there are sophisticated algorithms that exploit one of the two, no existing algorithm is able to adapt to both. In this paper we outline a new method for obtaining such adaptive algorithms, based on a potential function that aggregates a range of learning rates (which are essential tuning parameters). By choosing the right prior we construct efficient algorithms and show that they reap both benefits by proving the first bounds that are both second-order and incorporate quantiles.

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.

Open problem : adversarial multiarmed bandits with limited advice

Adversarial multiarmed bandits with expert advice is one of the fundamental problems in studying the exploration-exploitation trade-o. It is known that if we observe the advice of all experts on every round we can achieve O(√KTlnN) regret, where K is the number of arms, T is the number of game rounds, and N is the number of experts. It is also known that if we observe the advice of just one expert on every round, we can achieve regret of order O(√NT). Our open problem is what can be achieved by asking M experts on every round, where 1 < M < N.

Perceptions of online learning in an Australian university : Malaysian students’ perspectives-usability of the online learning tools

This study set out to investigate the kinds of learning difficulties encountered by the Malaysian students and how they actually coped with online learning. The modified Online Learning Environment Survey (OLES) instrument was used to collect data from the sample of 40 Malaysian students at a university in Brisbane, Australia. A controlled group of 35 Australian students was also included for comparison purposes. Contrary to assumptions from previous researches, the findings revealed that there were only a few differences between the international Asian and Australian students with regards to their perceptions of online learning. Recommendations based on the findings of this research study were applicable for Australian universities which have Asian international students enrolled to study online.

Perceptions of online learning in an Australian university: an international students’ (Asian Region) perspective – enjoyment

Several researchers have reported that cultural and language differences can affect online interactions and communications between students from different cultural backgrounds. Other researchers have asserted that online learning is a tool that can improve teaching and learning skills, but its effectiveness depends on how the tool is used. To delve into these aspects further, this study set out to investigate the kinds of learning difficulties encountered by the international students and how they actually coped with online learning. The modified Online Learning Environment Survey (OLES) instrument was used to collect data from the sample of 109 international students at a university in Brisbane. A smaller group of 35 domestic students was also included for comparison purposes. Contrary to assumptions from previous research, the findings revealed that there were only few differences between the international Asian and Australian students with regards to their perceptions of online learning. Recommendations based on the findings of this research study were made for Australian universities where Asian international students study online. Specifically the recommendations highlighted the importance of upskilling of lecturers’ ability to structure their teaching online and to apply strong theoretical underpinnings when designing learning activities such as discussion forums, and for the university to establish a degree of consistency with regards to how content is located and displayed in a learning management system like Blackboard.

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.

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.

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.

No borders : virtual communities in online learning

It can be argued that technological advances and increasing familiarity with technology in the general population has created a huge potential for expansion of online learning (OL) across the educational spectrum. The growth of OL at the university level over the last few years has brought with it an increasing need to understand the learning processes and social processes involved in the ‘cyber’ or ‘virtual’ lecture hall and seminar room by asking questions such as: What are ‘virtual universities’? How – or more critically whether – virtual learning environments are different from face-to-face (F2F) ones? In other words, there is a critical need to explore how students relate to each other and their lecturer(s) in a literal ‘school without walls’? This paper explores the development of a virtual community within a wholly online MA in Applied Linguistics program within the framework of online community development proposed by Haythornthwaite et al (2000).

A pilot test on the differences between domestic and international students’ perceptions towards online learning in a Malaysian institution (Part I)

Teaching to an international audience online can be significantly different as compared to a traditional classroom setting. In a traditional classroom setting, the students are usually removed from their own cultural context and required to operate in the lecturer’s context. International students coming to Malaysia to study are implicitly expected to, and often do, become familiar with the Malaysian culture and style of education. The use of educational technologies as a blended strategy in higher education programs offers challenges and opportunities for all students but this may be different for international students who come from varied backgrounds. With an increasingly competitive global demand for higher education, Malaysian institutions strive to be the hub of educational excellence and a preferred option for international students in coping with the challenges of studying abroad in a different culture. This research will evaluate how undergraduate students perceive their online learning experiences in a Malaysian university. The OLES (Online Learning Environment Survey) will be used to explore the international and domestic students’ perception on e-learning and the findings of the first six OLES scales varying from (Computer Usage, Teacher Support, Student Interaction & Collaboration, Personal Relevance, Authentic Learning, and Student Autonomy) will be reported in this research. An in-depth study will be conducted to compare and contrast the challenges of international students with domestic students. Major difficulties encountered and how these students actually cope with e-learning, as well as the strategies and tools used to overcome the challenges will be investigated.

A pilot test on the differences between domestic and international students' perceptions towards online learning in a Malaysian institution (part II)

Teaching to an international audience online can be significantly different as compared to a traditional classroom setting. In a traditional classroom setting, the students are usually removed from their own cultural context and required to operate in the lecturer’s context. International students coming to Malaysia to study are implicitly expected to, and often do, become familiar with the Malaysian culture and style of education. The use of educational technologies as a blended strategy in higher education programs offers challenges and opportunities for all students but this may be different for international students who come from varied backgrounds. With an increasingly competitive global demand for higher education, Malaysian institutions strive to be the hub of educational excellence and a preferred option for international students in coping with the challenges of studying abroad in a different culture. This research will evaluate how undergraduate students perceive their online learning experiences in a Malaysian institute. The OLES (Online Learning Environment Survey) will be used to explore the international and domestic students’ perception on e-learning and the findings of the last six OLES scales varying from (Equity, Enjoyment, Asychronocity, Evaluation & Assessments, Online Learning Tools, and Interface Design) will be reported in this research. An in-depth study will be conducted to compare and contrast the challenges of international students with domestic students. Major difficulties encountered and how these students actually cope with e-learning, as well as the strategies and tools used to overcome the challenges will be investigated.