The recursive teaching dimension (RTD) of a concept class C {0,1}n, introduced by Zilles et al. [ZLHZ11], is a complexity parameter measured by the worst-case number of labeled examples needed to learn any target concept of C in the recursive teaching model. In this paper, we study the quantitative relation between RTD and the well-known learning complexity measure VC dimension (VCD), and improve the best known upper and (worst-case) lower bounds on the recursive teaching dimension with respect to the VC dimension. Given a concept class C {0,1}n with VCD(C) = d, we first show that RTD(C) is at most d 2d+1. This is the first upper bound for RTD(C)that depends only on VCD(C), independent of the size of the concept class |C| and its domain size n. Before our work, the best known upper bound for RTD(C) is O(d2d loglog|C|), obtained by Moran et al. [MSWY15].

Neural Information Processing Systems http://nips.cc/

AIDE: Fastand Communication Efficient Distributed Optimization.arXive-prints,

Pd i=1(1 li) (see (8)), whereli = x>i (X>X) 1xi isthei-thleveragescoreofX. Here, weshow(3).

We propose the first reduction-based approach to obtaining long-term memory guarantees for online learning in the sense of Bousquet and Warmuth[8], by reducing the problem to achieving typical switching regret.

We will add more discussion on this in the next version of our paper, as suggested by the reviewer. For the full16 information setting, as far as we know there is no existing lower bound. Weare not aware of any25 existing results for tracking asmall set ofexperts with stochastic losses.

Associatedwitheach segment is a hypothesis from some hypothesis class. We give algorithms that are designed to exploit the scenario where there are many such segments but significantly fewer associated hypotheses.

We introduce a novel online multitask setting.