We study the best arm identification problem in combinatorial semi-bandits in the fixed confidence setting. We present Perturbed Frank-Wolfe Sampling (P-FWS), an algorithm that (i) runs in polynomial time, (ii) achieves the instance-specific minimal sample complexity in the high confidence regime, and (iii) enjoys polynomial sample complexity guarantees in the moderate confidence regime. To our best knowledge, existing algorithms cannot achieve (ii) and (iii) simultaneously in vanilla bandits. With P-FWS, we close the computational-statistical gap in best arm identification in combinatorial semi-bandits. The design of P-FWS starts from the optimization problem that defines the information-theoretical and instance-specific sample complexity lower bound. P-FWS solves this problem in an online manner using, in each round, a single iteration of the Frank-Wolfe algorithm. Structural properties of the problem are leveraged to make the P-FWS successive updates computationally efficient. In turn, P-FWS only relies on a simple linear maximization oracle.

Computing the top eigenvectors of a matrix is a problem of fundamental interest to various fields. While the majority of the literature has focused on analyzing the reconstruction error of low-rank matrices associated with the retrieved eigenvectors, in many applications one is interested in finding one vector with high Rayleigh quotient. In this paper we study the problem of approximating the top-eigenvector. Given a symmetric matrix $\mathbf{A}$ with largest eigenvalue $\lambda_1$, our goal is to find a vector $\hat{\mathbf{u}}$ that approximates the leading eigenvector $\mathbf{u}_1$ with high accuracy, as measured by the ratio $R(\hat{\mathbf{u}})=\lambda_1^{-1}{\hat{\mathbf{u}}^T\mathbf{A}\hat{\mathbf{u}}}/{\hat{\mathbf{u}}^T\hat{\mathbf{u}}}$. We present a novel analysis of the randomized SVD algorithm of \citet{halko2011finding} and derive tight bounds in many cases of interest. Notably, this is the first work that provides non-trivial bounds of $R(\hat{\mathbf{u}})$ for randomized SVD with any number of iterations. Our theoretical analysis is complemented with a thorough experimental study that confirms the efficiency and accuracy of the method.

The problem of branching experts is an extension of the experts problem where the set of experts may grow over time. We compare this problem in different learning settings along several axes: adversarial versus stochastic losses; a fixed versus a growing set of experts (branching experts); and single-task versus lifelong learning with expert advice. First, for the branching experts problem, we achieve tight regret bounds in both adversarial and stochastic setting with a single algorithm. While it was known that the adversarial branching experts problem is strictly harder than the non-branching one, the stochastic branching experts problem is in fact no harder. Next, we study the extension to the lifelong learning with expert advice in which one has to make online predictions with a sequence of tasks. For this problem, we provide a single algorithm which works for both adversarial and stochastic setting, and our bounds when specialized to the case without branching recover the regret bounds previously achieved separately via different algorithms. Furthermore, we prove a regret lower bound which shows that in the lifelong learning scenario, the case with branching experts now becomes strictly harder than the non-branching case in the stochastic setting.

In this work, we study a problem arising from two lines of works: online optimization and lifelong learning. In the problem, there is a sequence of tasks arriving sequentially, and within each task, we have to make decisions one after one and then suffer corresponding losses. The tasks are related as they share some common representation, but they are different as each requires a different predictor on top of the representation. As learning a representation is usually costly in lifelong learning scenarios, the goal is to learn it continuously through time across different tasks, making the learning of later tasks easier than previous ones. We provide such learning algorithms with good regret bounds which can be seen as natural generalization of prior works on online optimization.

We study the problem of online linear optimization with sparsity constraints in the semi-bandit setting. It can be seen as a marriage between two well-known problems: the online linear optimization problem and the combinatorial bandit problem. For this problem, we provide an algorithm which is efficient and achieves a sublinear regret bound. Moreover, we extend our results to two generalized settings, one with delayed feedbacks and one with costs for receiving feedbacks. Finally, we conduct experiments which show the effectiveness of our methods in practice.

Chih-Te Lai, Yi-Te Hong, Hong-You Chen, Chi-Jen Lu, Shou-De Lin. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

We study the task of conditional image generation and provide a general framework for combining autoencoders (AEs) with generative adversarial networks (GANs). Our framework provides a principled way to avoid well-known problems such as mode collapse and training instability. We use two AEs, a big parent-AE and a small child-AE, to play different roles. Our parent-AE is trained to minimize only one single objective: the reconstruction loss, which makes its training process stable and efficient. It is then fixed and used for several purposes, including initializing the generator and providing powerful features for a simple discriminator of GAN. It also plays the role of reducing the initial harder task of image generation to a simpler one: sampling from its latent distribution, which is given to child-AE to accomplish. Child-AE can be trained very efficiently due to its small size, and we only need to modify it if necessary for different applications, which makes our framework very flexible. Our experiments show that our model is capable of generating high quality novel images with controllable attributes.

Spiking Neural Networks (SNN) are mathematical models in neuroscience to describe the dynamics among a set of neurons that interact with each other by firing instantaneous signals, a.k.a., spikes. Interestingly, a recent advance in neuroscience [Barrett-Denève-Machens, NIPS 2013] showed that the neurons' firing rate, i.e., the average number of spikes fired per unit of time, can be characterized by the optimal solution of a quadratic program defined by the parameters of the dynamics. This indicated that SNN potentially has the computational power to solve non-trivial quadratic programs. However, the results were justified empirically without rigorous analysis. We put this into the context of natural algorithms and aim to investigate the algorithmic power of SNN. Especially, we emphasize on giving rigorous asymptotic analysis on the performance of SNN in solving optimization problems. To enforce a theoretical study, we first identify a simplified SNN model that is tractable for analysis. Next, we confirm the empirical observation in the work of Barrett et al. by giving an upper bound on the convergence rate of SNN in solving the quadratic program. Further, we observe that in the case where there are infinitely many optimal solutions, SNN tends to converge to the one with smaller l1 norm. We give an affirmative answer to our finding by showing that SNN can solve the l1 minimization problem under some regular conditions. Our main technical insight is a dual view of the SNN dynamics, under which SNN can be viewed as a new natural primal-dual algorithm for the l1 minimization problem. We believe that the dual view is of independent interest and may potentially find interesting interpretation in neuroscience.

Many scenarios in our daily life require us to infer some ranking over items or people based on limited information. In this paper, we consider two such scenarios, one for ranking student papers in massive online open courses and one for identifying the best player (or team) in sports tournaments. For the peer grading problem, we design a mechanism with a new way of matching graders to papers. This allows us to aggregate partial rankings from graders into a global one, with an accuracy rate matching the best in previous works, but with a much simpler analysis. For the winner selection problem in sports tournaments, we cast it as the well-known dueling bandit problem and identify a new measure to minimize: the number of parallel rounds, as one normally would not like a large tournament to last too long. We provide mechanisms which can determine the optimal or an almost optimal player in a small number of parallel rounds and at the same time using a small number of competitions.

Tensor decomposition is an important problem with many applications across several disciplines, and a popular approach for this problem is the tensor power method. However, previous works with theoretical guarantee based on this approach can only find the top eigenvectors one after one, unlike the case for matrices. In this paper, we show how to find the eigenvectors simultaneously with the help of a new initialization procedure. This allows us to achieve a better running time in the batch setting, as well as a lower sample complexity in the streaming setting.

We study online reinforcement learning in average-reward stochastic games (SGs). An SG models a two-player zero-sum game in a Markov environment, where state transitions and one-step payoffs are determined simultaneously by a learner and an adversary. We propose the \textsc{UCSG} algorithm that achieves a sublinear regret compared to the game value when competing with an arbitrary opponent. This result improves previous ones under the same setting. The regret bound has a dependency on the \textit{diameter}, which is an intrinsic value related to the mixing property of SGs. Slightly extended, \textsc{UCSG} finds an $\varepsilon$-maximin stationary policy with a sample complexity of $\tilde{\mathcal{O}}\left(\text{poly}(1/\varepsilon)\right)$, where $\varepsilon$ is the error parameter. To the best of our knowledge, this extended result is the first in the average-reward setting. In the analysis, we develop Markov chain's perturbation bounds for mean first passage times and techniques to deal with non-stationary opponents, which may be of interest in their own right.

We study the problem of recovering the subspace spanned by the first k principal components of d-dimensional data under the streaming setting, with a memory bound of O(kd). Two families of algorithms are known for this problem. The first family is based on the framework of stochastic gradient descent. Nevertheless, the convergence rate of the family can be seriously affected by the learning rate of the descent steps and deserves more serious study. The second family is based on the power method over blocks of data, but setting the block size for its existing algorithms is not an easy task. In this paper, we analyze the convergence rate of a representative algorithm with decayed learning rate (Oja and Karhunen, 1985) in the first family for the general k>1 case. Moreover, we propose a novel algorithm for the second family that sets the block sizes automatically and dynamically with faster convergence rate. We then conduct empirical studies that fairly compare the two families on real-world data. The studies reveal the advantages and disadvantages of these two families.

We study the dynamic regret of multi-armed bandit and experts problem in non-stationary stochastic environments. We introduce a new parameter $\W$, which measures the total statistical variance of the loss distributions over $T$ rounds of the process, and study how this amount affects the regret. We investigate the interaction between $\W$ and $\Gamma$, which counts the number of times the distributions change, as well as $\W$ and $V$, which measures how far the distributions deviates over time. One striking result we find is that even when $\Gamma$, $V$, and $\Lambda$ are all restricted to constant, the regret lower bound in the bandit setting still grows with $T$. The other highlight is that in the full-information setting, a constant regret becomes achievable with constant $\Gamma$ and $\Lambda$, as it can be made independent of $T$, while with constant $V$ and $\Lambda$, the regret still has a $T^{1/3}$ dependency. We not only propose algorithms with upper bound guarantee, but prove their matching lower bounds as well.

We consider the problem of online multiclass prediction in the bandit setting. Compared with the full-information setting, in which the learner can receive the true label as feedback after making each prediction, the bandit setting assumes that the learner can only know the correctness of the predicted label. Because the bandit setting is more restricted, it is difficult to design good bandit learners and currently there are not many bandit learners. In this paper, we propose an approach that systematically converts existing online binary classifiers to promising bandit learners with strong theoretical guarantee. The approach matches the idea of boosting, which has been shown to be powerful for batch learning as well as online learning. In particular, we establish the weak-learning condition on the online binary classifiers, and show that the condition allows automatically constructing a bandit learner with arbitrary strength by combining several of those classifiers. Experimental results on several real-world data sets demonstrate the effectiveness of the proposed approach.

Consider the online convex optimization problem, in which a player has to choose actions iteratively and suffers corresponding losses according to some convex loss functions, and the goal is to minimize the regret. In the full-information setting, the player after choosing her action can observe the whole loss function in that round, while in the bandit setting, the only information the player can observe is the loss value of that action. Designing such bandit algorithms appears challenging, as the best regret currently achieved for general convex loss functions is much higher than that in the full-information setting, while for strongly convex loss functions, there is even a regret lower bound which is exponentially higher than that achieved in the full-information setting. To aim for smaller regrets, we adopt a relaxed two-point bandit setting in which the player can play two actions in each round and observe the loss values of those two actions. Moreover, we consider loss functions parameterized by their deviation D, which measures how fast they evolve, and we study how regrets depend on D. We show that two-point bandit algorithms can in fact achieve regrets matching those in the full-information setting in terms of D. More precisely, for convex loss functions, we achieve a regret of O(\sqrtD), while for strongly convex loss functions, we achieve a regret of O(\ln D), which is much smaller than the Ω(\sqrtD) lower bound in the traditional bandit setting.

We consider the problem of constructing hitting set generators for sparse multivariate polynomials over any finite fields. Hitting set generators, just as pseudorandom generators, play a fundamental role in the study of derandomization. Pseudorandom generators with a logarithmic seed length are only known for polynomials of a constant degree \cite{Lov09, Vio09}. On the other hand, hitting set generators with a logarithmic seed length are known for polynomials of larger degrees, but only over fields which are much larger than the degrees \cite{KS01, Bog05}. Our main result is the construction of a hitting set generator with a seed length of O(\log s), which works for s-term polynomials of any degrees over any finite fields of constant size. This gives the first optimal hitting set generator which allows the fields to be smaller than the degrees of polynomials. For larger fields, of non-constant size, we provide another hitting set generator with a seed length of O(\log (sd)), which works for s-term polynomials of any degree d, as long as d is slightly smaller than the field size.

We study the task of deterministically extracting randomness from sources containing computational entropy. The sources we consider have the form of a conditional distribution (f(X)|X), for some functionfand some distributionX, and we say that such a source has computational min-entropykif any circuit of size 2kcan only predictf(x) correctly with probability at most 2-kgiven inputxsampled fromX. We first show that it is impossible to have a seedless extractor to extract from one single source of this kind. Then we show that it becomes possible if we are allowed a seed which is weakly random (instead of perfectly random) but contains some statistical min-entropy, or even a seed which is not random at all but contains some computational min-entropy. This can be seen as a step toward extending the study of multisource extractors from the traditional, statistical setting to a computational setting. We reduce the task of constructing such extractors to a problem in computational learning theory: learning linear functions under arbitrary distribution with adversarial noise, and we provide a learning algorithm for this problem. In fact, this problem is a well-recognized one in computational learning theory and variants of this problem have been studied intensively before. Thus, in addition to its application to extractors, our learning algorithm also has independent interest of its own, and it can be considered as the main technical contribution of this paper.

The online learning problem requires a player to iteratively choose an action in an unknown and changing environment. In the standard setting of this problem, the player has to choose an action in each round before knowing anything about the corresponding loss. However, there are situations in which it seems possible for the player to spend efforts or resources to collect some prior information before her actions. This motivates us to study a variant of the online learning problem, in which the player is allowed to query B bits from the loss vector in each round before choosing her action. Suppose each loss value is represented by K bits and distinct loss values differ by at least some amount δ, and suppose there are N actions to choose and T rounds to play. We provide an algorithm for this problem which achieves a regret of the following form. Before B approaching B1 = NK/2, the regret stays at , and after B exceeding B1 but before approaching B2 = NK/2 + 3K/2–1, the regret drops slightly to , while after B exceeding B2, the regret takes a dramatic drop to (N ln N)/δ. Our algorithm is in fact close to optimal as we also provide regret lower bounds which almost match the regret upper bounds achieved by our algorithm.

In this paper, we consider the task of deterministically extracting randomness from sources consisting of a sequence ofnindependent symbols from {0,1}d. The only randomness guarantee on such a source is that the whole source has min-entropyk. We give an explicit deterministic extractor which extract Ω(logk-loglog(1/ ε)) bits with error ε , for anyn,d,k∈ \BBN and ε ∈ (0,1). For sources with a larger min-entropy, we can extract even more randomness. Whenk≥n1/2+γ, for any constant γ ∈ (0,1/2), we can extractm=k-O(dlog(1/ ε)) bits with any error ε ≥ 2-Ω(nγ). Whenk≥ logcn, for some constantc> 0, we can extractm=k-(1/ ε)O(1) bits with any error ε ≥k-Ω(1). Our results generalize those of Kamp and Zuckerman and Gabizon which only work for bit-fixing sources (withd=1 and each bit of the source being either fixed or perfectly random). Moreover, we show the existence of a nonexplicit deterministic extractor which can extractm=k-O(log(1/ ε)) bits wheneverk=ω(d+log(n/ ε)) . Finally, we show that even to extract from bit-fixing sources, any extractor, seeded or not, must suffer an entropy lossk-m=Ω(log(1/ ε)). This generalizes a lower bound of Radhakrishnan and Ta-Shma on extracting from general sources.

For$\delta \in (0,1)$and$k,n\in \BBN $, we study the task of transforming a hard function$f: \{0,1\}^{n}\to \{0,1\} $, with which any small circuit disagrees on$(1-\delta )/2$fraction of the input, into a harder function$f^{\prime}$, with which any small circuit disagrees on$(1-\delta ^{k})/2$fraction of the input. First, we show that such hardness amplification, when carried out in some black-box way, must require a high complexity. In particular, it cannot be realized by a circuit of depth$d$and size$2^{o(k^{1/d})}$or by a nondeterministic circuit of size$o(k/\log k)$(and arbitrary depth) for any$\delta \in (0,1)$. This extends the result of Viola, which only works when$(1-\delta )/2$is small enough. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently nonuniform in the following sense. To guarantee the hardness of the resulting function$f^{\prime}$, even against uniform machines, one has to start with a function$f$, which is hard against nonuniform algorithms with$\Omega (k\log (1/\delta ))$bits of advice. This extends the result of Trevisan and Vadhan, which only addresses the case with$(1-\delta )/2=2^{-n}$. Finally, we derive similar lower bounds for any black-box construction of a pseudorandom generator (PRG) from a hard function. To prove our results, we link the task of hardness amplifications and PRG constructions, respectively, to some type of error-reduction codes, and then we establish lower bounds for such codes, which we hope could find interest in both coding theory and complexity theory.

In this paper, we propose a number of adaptive prototype learning (APL) algorithms. They employ the same algorithmic scheme to determine the number and location of prototypes, but differ in the use of samples or the weighted averages of samples as prototypes, and also in the assumption of distance measures. To understand these algorithms from a theoretical viewpoint, we address their convergence properties, as well as their consistency under certain conditions. We also present a soft version of APL, in which a non-zero training error is allowed in order to enhance the generalization power of the resultant classifier. Applying the proposed algorithms to twelve UCI benchmark data sets, we demonstrate that they outperform many instance-based learning algorithms, the k-nearest neighbor rule, and support vector machines in terms of average test accuracy.

We study the task of transforming a hard function f, with which any small circuit disagrees on (1 - /spl delta/)/2 fraction of the input, into a harder function f', with which any small circuit disagrees on (1 - /spl delta//sup k/)/2 fraction of the input, for /spl delta/ /spl isin/ (0,1) and k /spl isin/ /spl Nopf/. We show that this process cannot be carried out in a black-box way by a circuit of depth d and size 2/sup o(k2/d)/ or by a nondeterministic circuit of size o(k/log k) (and arbitrary depth). In particular, for k = 2/sup /spl Omega/(n)/, such hardness amplification cannot be done in ATIME(O(1), 2/sup o(n)/. Therefore, hardness amplification in general requires a high complexity. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently non-uniform in the following sense. Given as an oracle any algorithm which agrees with f' on (1 - /spl delta//sup k/)/2 fraction of the input, we still need an additional advice of length /spl Omega/(k log(1//spl delta/)) in order to compute f correctly on (1 - /spl delta/)/2 fraction of the input. Therefore, to guarantee the hardness, even against uniform machines, of the function f', one has to start with a function f which is hard against non-uniform circuits. Finally, we derive similar lower bounds for any black-box construction of pseudorandom generators from hard functions.

We study the problem of deterministically extracting almost perfect random bits from multiple weakly random sources that are mutually independent. With two independent sources, we have an explicit extractor which can extract a number of random bits that matches the best construction currently known, via the generalized leftover hash lemma. We also extend our construction to extract randomness from more independent sources. One nice feature is that the extractor still works even with all but one source exposed. Finally, we apply our extractor for a cryptographic task in which a group of parties wants to agree on a secret key for group communication over an insecure channel, without using ideal local randomness.

Given a hypergraph and a set of colors, we want to find a vertex coloring to minimize the size of any monochromatic set in an edge. We give a deterministic polynomial time approximation algorithm with performance close to the best bound guaranteed by an existential argument. This can be applied to support divide and conquer approaches to various problems. We give two examples. For deterministic DNF approximate counting, this helps us explore the importance of a previously ignored parameter, the maximum number of appearances of any variable, and we construct algorithms that are particularly good when this parameter is small. For partially ordered sets, we are able to constructivize the dimension bound given by Füredi and Kahn [Order, 3 (1986), pp. 15--20].

This paper provides the first explicit construction of extractors which are simultaneously optimal up to constant factors in both seed length and output length. More precisely, for every n,k, our extractor uses a random seed of length O(log n) to transform any random source on n bits with (min-)entropy k, into a distribution on (1-α)k bits that is e-close to uniform. Here α and e can be taken to be any positive constants. (In fact, e can be almost polynomially small.Our improvements are obtained via three new techniques, each of which may be of independent interest. The first is a general construction of mergers [22] from locally decodable error-correcting codes. The second introduces new condensers that have constant seed length (and retain a constant fraction of the min-entropy in the random source). The third is a way to augment the win-win repeated condensing paradigm of [17] with error reduction techniques like [15] so that the our constant seed-length condensers can be used without error accumulation.

The Lovász local lemma (LLL) is a powerful tool that is increasingly playing a valuable role in computer science. The original lemma was nonconstructive; a breakthrough of Beck and its generalizations (due to Alon and Molloy and Reed) have led to constructive versions. However, these methods do not capture some classes of applications of the LLL. We make progress on this by providing algorithmic approaches to two families of applications of the LLL. The first provides constructive versions of certain applications of an extension of the LLL (modeling, e.g., hypergraph-partitioning and low-congestion routing problems); the second provides new algorithmic results on constructing disjoint paths in graphs. Our results can also be seen as constructive upper bounds on the integrality gap of certain packing problems. One common theme of our work is a "gradual rounding" approach.

In this note we consider the number of distinct $\alpha$-ary codes produced by repeatedly applying the Gray code mapping of Sharma and Khanna [ Inform. Sci., 15 (1978), pp. 31--43]. This number was derived before by Lichtner [SIAM J. Discrete Math., 11 (1998), pp. 381--386], and we give an alternative proof here. Our key observation is a simple connection between this number and the period of binomial coefficients modulo $\alpha$. Then the result follows immediately from a known periodic property of binomial coefficients modulo $\alpha$ [ Fibonacci Quart., 27 (1989), pp. 64--79; SIAM J. Discrete Math., 9 (1996), pp. 55--62; Ann. Univ. Mariae Curie-Sklodowska Sect. A, 10 (1956), pp. 37--47].

In this paper we show several results about monotone planar circuits. We show that monotone planar circuits of bounded width, with access to negated input variables, compute exactly the functions in non-uniform AC/sup 0/. This provides a striking contrast to the non-planar case, where exactly NC/sup 1/ is computed. We show that the circuit value problem for monotone planar circuits, with inputs on the outerface only, can be solved in LOGDCFL/spl sube/SC, improving a LOGCFL upper bound due to Dymond and Cook. We show that for monotone planar circuits, with inputs on the outerface only, excessive depth compared to width is useless; any function computed by a monotone planar circuit of width w with inputs on the outerface can be computed by a monotone planar circuit of width O(w) and depth w/sup O(1)/. Finally, we show that monotone planar read-once circuits, with inputs on the outerface only, can be efficiently learned using membership queries.

We show that searching a width k maze is complete for Pi_k, i.e., for the k'th level of the AC0 hierarchy. Equivalently, st-connectivity for width k grid graphs is complete for Pi_k. As an application, we show that there is a data structure solving dynamic st-connectivity for constant width grid graphs with time bound O(log log n) per operation on a random access machine. The dynamic algorithm is derived from the parallel one in an indirect way using algebraic tools.

The algebraic path problem is a general description of a class of problems, including some important graph problems such as transitive closure, all pairs shortest paths, minimum spanning tree, etc. In this work, the algebraic path problem is solved on a processor array with a reconfigurable bus system. The proposed algorithms are based on repeated matrix multiplications. The multiplication of two n*n matrices takes O(log n) time in the worst case, but, for some special cases, O(1) time is possible. It is shown that three instances of the algebraic path problem, transitive closure, all pairs shortest paths, and minimum spanning tree, can be solved in O(log n) time, which is as fast as on the CRCW PRAM.>