instruction:
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.
question:
We consider the design of online learning algorithms in a general learning setting, with the goal of obtaining computationally efficient no-regret algorithms, when given access to an oracle for the offline optimization version of the problem. We present an algorithm that we call Generalized Follow-thePerturbed-Leader (Generalized FTPL) and provide conditions under which it achieves vanishing regret and is efficiently implementable with an oracle. Our second main contribution is the introduction of a new online adversarial auction-design framework for revenue maximization and an application of our oracle-efficient learning results to the adaptive optimization of auctions. Our learning algorithm is a generalization of the classic FTPL algorithm of Kalai and Vempala [27], playing at every iteration the historically best-performing action after adding some perturbation to the performance of each of its actions. The crux of our design is adding perturbations in a manner that leads to oracle-efficiency. We reduce this to designing a translation matrix, which translates a low dimensional vector with independent noise components into a high dimensional vector of perturbations on the learner's action space. Our approach generalizes prior work on oracle-efficient online learning [11, 22, 27, 35], ranging from online combinatorial optimization, learning in simultaneous auctions, and contextual learning. Our auction-design framework considers an auctioneer learning an optimal auction rule in an online manner, every day observing an adversarially chosen vector of valuations. The auctioneer's goal is to achieve revenue that competes with the revenue of the optimal auction in hindsight among those in some target class. We give oracle-efficient learning results for: (1) VCG auctions with bidder-specific reserves in single-parameter settings with matroid constraints, (2) envy-free item pricing in multi-item auctions with unlimited supply, and (3) s-level auctions of Morgenstern and Roughgarden [28] for singleitem settings. The last result implies good regret against the optimal overall auction when valuations are coming from a fast mixing Markov chain, that is independent across bidders. We also extend our results to the case when the learner observes side information on the bidders before running the auction (contextual learning). We present additional extensions to contextual learning and learning with approximate oracles, implemented by FPTAS or Maximal-in-Range algorithms. We provide further applications in online welfare maximization in multi-unit auctions and in no-regret learning in simultaneous item auctions, answering an open question from prior work. Microsoft Research, New York, mdudik@microsoft.com Computer Science Department, Carnegie Mellon University, nhaghtal@cs.cmu.edu Microsoft Research, New York, haipeng@microsoft.com Microsoft Research, New York, schapire@microsoft.com Microsoft Research, New England, vasy@microsoft.com Microsoft Research, New York, jenn@microsoft.com ar X iv :1 61 1. 01 68 8v 1 [ cs .L G ] 5 N ov 2 01 6
answer:
Oracle-Efficient Learning and Auction Design

question:
We study online boosting, the task of converting any weak online learner into a strong online learner. Based on a novel and natural definition of weak online learnability, we develop two online boosting algorithms. The first algorithm is an online version of boost-by-majority. By proving a matching lower bound, we show that this algorithm is essentially optimal in terms of the number of weak learners and the sample complexity needed to achieve a specified accuracy. This optimal algorithm is not adaptive, however. Using tools from online loss minimization, we derive an adaptive online boosting algorithm that is also parameter-free, but not optimal. Both algorithms work with base learners that can handle example importance weights directly, as well as by rejection sampling examples with probability defined by the booster. Results are complemented with an experimental study.
answer:
Optimal and Adaptive Algorithms for Online Boosting

question:
Neural machine translation aims at building a single large neural network that can be trained to maximize translation performance. The encoder-decoder architecture with an attention mechanism achieves a translation performance comparable to the existing state-of-the-art phrase-based systems. However, the use of large vocabulary becomes the bottleneck in both training and improving the performance. In this paper, we propose a novel architecture which learns morphology by using two recurrent networks and a hierarchical decoder which translates at character level. This gives rise to a deep character-level model consisting of six recurrent networks. Such a deep model has two major advantages. It avoids the large vocabulary issue radically; at the same time, it is more efficient in training than word-based models. Our model obtains a higher BLEU score than the bpe-based model after training for one epoch on En-Fr and En-Cs translation tasks. Further analyses show that our model is able to learn morphology.
answer:
DEEP CHARACTER-LEVEL NEURAL MACHINE TRANSLATION BY LEARNING MORPHOLOGY