TASK DEFINITION: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
PROBLEM: We first consider the problem of learning k-parities in the on-line mistake-bound model: given a hidden vector x ∈ {0, 1} with |x| = k and a sequence of “questions” a1, a2, · · · ∈ {0, 1} , where the algorithm must reply to each question with 〈ai, x〉 (mod 2), what is the best tradeoff between the number of mistakes made by the algorithm and its time complexity? We improve the previous best result of Buhrman et. al. [BGM10] by an exp(k) factor in the time complexity. Second, we consider the problem of learning k-parities in the presence of classification noise of rate η ∈ (0, 1/2). A polynomial time algorithm for this problem (when η > 0 and k = ω(1)) is a longstanding challenge in learning theory. Grigorescu et al. [GRV11] showed an algorithm running in time ( n k/2 )1+4η+o(1) . Note that this algorithm inherently requires time ( n k/2 ) even when the noise rate η is polynomially small. We observe that for sufficiently small noise rate, it is possible to break the ( n k/2 ) barrier. In particular, if for some function f(n) = ω(1) and α ∈ [1/2, 1), k = n/f(n) and η = o(f(n)/ log n), then there is an algorithm for the problem with running time poly(n) · ( n k )1−α · e.

SOLUTION: On learning k-parities with and without noise

PROBLEM: <lb>Recent price-of-anarchy analyses of games of complete information suggest that coarse correlated<lb>equilibria, which characterize outcomes resulting from no-regret learning dynamics, have near-optimal<lb>welfare. This work provides two main technical results that lift this conclusion to games of incomplete<lb>information, a.k.a., Bayesian games. First, near-optimal welfare in Bayesian games follows directly from<lb>the smoothness-based proof of near-optimal welfare in the same game when the private information<lb>is public. Second, no-regret learning dynamics converge to Bayesian coarse correlated equilibrium in<lb>these incomplete information games. These results are enabled by interpretation of a Bayesian game<lb>as a stochastic game of complete information.

SOLUTION: No-Regret Learning in Repeated Bayesian Games

PROBLEM: Inspired by the hierarchical hidden Markov models (HHMM), we present the hierarchical semi-Markov conditional random field (HSCRF), a generalisation of embedded undirected Markov chains to model complex hierarchical, nested Markov processes. It is parameterised in a discriminative framework and has polynomial time algorithms for learning and inference. Importantly, we consider partiallysupervised learning and propose algorithms for generalised partially-supervised learning and constrained inference. We demonstrate the HSCRF in two applications: (i) recognising human activities of daily living (ADLs) from indoor surveillance cameras, and (ii) noun-phrase chunking. We show that the HSCRF is capable of learning rich hierarchical models with reasonable accuracy in both fully and partially observed data cases.

SOLUTION:
Hierarchical Semi-Markov Conditional Random Fields for Recursive Sequential Data