We consider the stochastic approximation problem where a convex function has to be minimized, given only the knowledge of unbiased estimates of its gradients at certain points, a framework which includes machine learning methods based on the minimization of the empirical risk. We focus on problems without strong convexity, for which all previously known algorithms achieve a convergence rate for function values of O(1/n^{1/2}). We consider and analyze two algorithms that achieve a rate of O(1/n) for classical supervised learning problems. For least-squares regression, we show that averaged stochastic gradient descent with constant step-size achieves the desired rate. For logistic regression, this is achieved by a simple novel stochastic gradient algorithm that (a) constructs successive local quadratic approximations of the loss functions, while (b) preserving the same running time complexity as stochastic gradient descent. For these algorithms, we provide a non-asymptotic analysis of the generalization error (in expectation, and also in high probability for least-squares), and run extensive experiments on standard machine learning benchmarks showing that they often outperform existing approaches.

Online learning with delayed feedback has received increasing attention recently due to its several applications in distributed, web-based learning problems. In this paper we provide a systematic study of the topic, and analyze the effect of delay on the regret of online learning algorithms. Somewhat surprisingly, it turns out that delay increases the regret in a multiplicative way in adversarial problems, and in an additive way in stochastic problems. We give meta-algorithms that transform, in a black-box fashion, algorithms developed for the non-delayed case into ones that can handle the presence of delays in the feedback loop. Modifications of the well-known UCB algorithm are also developed for the bandit problem with delayed feedback, with the advantage over the meta-algorithms that they can be implemented with lower complexity.

We study the power of different types of adaptive (nonoblivious) adversaries in the setting of prediction with expert advice, under both full-information and bandit feedback. We measure the player's performance using a new notion of regret, also known as policy regret, which better captures the adversary's adaptiveness to the player's behavior. In a setting where losses are allowed to drift, we characterize ---in a nearly complete manner--- the power of adaptive adversaries with bounded memories and switching costs. In particular, we show that with switching costs, the attainable rate with bandit feedback is $\widetilde{\Theta}(T^{2/3})$. Interestingly, this rate is significantly worse than the $\Theta(\sqrt{T})$ rate attainable with switching costs in the full-information case. Via a novel reduction from experts to bandits, we also show that a bounded memory adversary can force $\widetilde{\Theta}(T^{2/3})$ regret even in the full information case, proving that switching costs are easier to control than bounded memory adversaries. Our lower bounds rely on a new stochastic adversary strategy that generates loss processes with strong dependencies.

We introduce online learning algorithms which are independent of feature scales, proving regret bounds dependent on the ratio of scales existent in the data rather than the absolute scale. This has several useful effects: there is no need to pre-normalize data, the test-time and test-space complexity are reduced, and the algorithms are more robust.

Educators who wish to engage their students in multi-agent experimentation and learning need an inexpensive multi-robot system that leverages existing equipment and open-source software. This paper proposes Overwatch as an inexpensive educational tool for teaching and experimenting in multi-robot systems. The interaction of multiple agents within a single environment is an important area of study. It is vital that agents within the environment perceive other agents as intelligent, acting within the environment as cooperative teammates or as competitive members of another team. To do so, the system must meet three goals: first, to allow multiple robots to communicate and coordinate; second, to localize within a shared global coordinate system; third, to recognize their teammates and other teams. The cost and scale of such experimental platforms places them outside the reach of many educational institutions or limits the number of agents that are interacting within the system \cite{Liu201160}. The goal of Overwatch is to create an experimental platform for multi-agent systems that is comprised of much smaller, albeit less capable, robots, many of which are prevalent in academic institutions already. Making use of available open-source libraries and utilizing lower cost robots, such as Scribblers, allows for experiments with many agents. This enables Overwatch to fit into the budget limitations of an academic setting. The Overwatch platform provides the Scribblers with global localization capabilities. This paper presents the system in detail and includes experiments to show its ability to localize, interact with other agents, and coordinate behaviors with these other agents. Additionally, the details to setup this system are also included.

This study expands upon an existing model of students’ reading comprehension ability within an intelligent tutoring system. The current system evaluates students’ natural language input using a local student model. We examine the potential to expand this model by assessing the linguistic features of self-explanations aggregated across entire passages. We assessed the relationship between 126 students’ reading comprehension ability and the cohesion of their aggregated self-explanations with three linguistic features. Results indicated that the three cohesion indices accounted for variance in reading ability over and above the features used in the current algorithm. These results demonstrate that broadening the window of NLP analyses can strengthen student models within ITSs.

In student modeling, the concept of "mastery learning" i.e. that a student continues to learn a skill till mastery is attained is important. Usually, mastery is defined in terms of most recent student performance. This is also the case with models such as Knowledge Tracing which estimate knowledge solely based on patterns of questions a student gets correct and the task usually is to predict immediate next action of the student. In retrospect however, it is not clear if this is a good definition of mastery since it is perhaps more useful to focus more on student retention over a longer period of time. This paper improves a recently introduced model by Wang and Beck that predicts long term student performance by clustering the students and generating multiple predictions by using a recently developed ensemble technique. Another contribution is that we introduce a novel clustering algorithm we call "Regularity Clustering" and show that it is superior in the task of predicting student retention over more popular techniques such as k-means and Spectral Clustering.

Research on individual differences indicates that students vary in how they interact with and perform while using intelligent tutoring systems (ITSs). However, less research has investigated how individual differences affect students’ interactions with game-based features. This study examines how learning outcomes and interactions with specific game-based features (off-task personalization vs. on-task mini games) within a game-based ITS, iSTART-ME, vary as a function of students’ performance orientation. The current study (n=40) is part of a larger study (n=126) conducted with high school students. The analyses in this study focus on those students assigned to iSTART-ME. Results indicate that students with higher levels of performance orientation perform better during training, progress further within the system, and interact less frequently with off-task game-based features. These results provide further evidence that individual differences play an important role in influencing students’ interactions and achievement within learning environments.

Many intelligent tutoring system (ITS) researchers are looking at ways to detect and to respond to student emotional states (for instance animated pedagogical agents that mirror student emotion). Such interventions are complicated to build, and do not take advantage of the potential for teachers to be part of the process. We present two studies that intervene when a student is having trouble by presenting the student with a YouTube video that is recorded by their own teacher and that delivers a motivational message to help them to persist with the learning session. We experimentally compared two different motivational interventions, which are both grounded in the literature on student affect and motivation. We also had a control condition that had no video. We found that when looking at students’ self-reports on the value of mathematics, we found a main effect of condition for the value-video. In Study 2 we examined whether these 60-second videos could impact homework completion rates and found that in fact homework completion rates were higher for students in the value-video condition. The present research is suggestive of a somewhat novel use of teacher-generated content that could easily be incorporated into other ITSs.

Introduction to the papers presented at the 2013 FLAIRS Conference Special Track on Intelligent Tutoring Systems