Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
I&C Journal 2019 Journal Article
We study the { 0, 1 } -loss version of adaptive adversarial multi-armed bandit problems with α ( ≥ 1 ) lossless arms. For the problem, we show a tight bound K − α − Θ ( 1 / T ) on the minimax expected number of mistakes (1-losses), where K is the number of arms and T is the number of rounds.
ICML Conference 2018 Conference Paper
We analyze algorithms for approximating a function $f(x) = \Phi x$ mapping $\Re^d$ to $\Re^d$ using deep linear neural networks, i. e. that learn a function $h$ parameterized by matrices $\Theta_1, .. ., \Theta_L$ and defined by $h(x) = \Theta_L \Theta_{L-1}. .. \Theta_1 x$. We focus on algorithms that learn through gradient descent on the population quadratic loss in the case that the distribution over the inputs is isotropic. We provide polynomial bounds on the number of iterations for gradient descent to approximate the least squares matrix $\Phi$, in the case where the initial hypothesis $\Theta_1 =. .. = \Theta_L = I$ has excess loss bounded by a small enough constant. On the other hand, we show that gradient descent fails to converge for $\Phi$ whose distance from the identity is a larger constant, and we show that some forms of regularization toward the identity in each layer do not help. If $\Phi$ is symmetric positive definite, we show that an algorithm that initializes $\Theta_i = I$ learns an $\epsilon$-approximation of $f$ using a number of updates polynomial in $L$, the condition number of $\Phi$, and $\log(d/\epsilon)$. In contrast, we show that if the least squares matrix $\Phi$ is symmetric and has a negative eigenvalue, then all members of a class of algorithms that perform gradient descent with identity initialization, and optionally regularize toward the identity in each layer, fail to converge. We analyze an algorithm for the case that $\Phi$ satisfies $u^{\top} \Phi u > 0$ for all $u$, but may not be symmetric. This algorithm uses two regularizers: one that maintains the invariant $u^{\top} \Theta_L \Theta_{L-1}. .. \Theta_1 u > 0$ for all $u$, and another that "balances" $\Theta_1, .. ., \Theta_L$ so that they have the same singular values.
JMLR Journal 2018 Journal Article
We analyze dropout in deep networks with rectified linear units and the quadratic loss. Our results expose surprising differences between the behavior of dropout and more traditional regularizers like weight decay. For example, on some simple data sets dropout training produces negative weights even though the output is the sum of the inputs. This provides a counterpoint to the suggestion that dropout discourages co-adaptation of weights. We also show that the dropout penalty can grow exponentially in the depth of the network while the weight-decay penalty remains essentially linear, and that dropout is insensitive to various re-scalings of the input features, outputs, and network weights. This last insensitivity implies that there are no isolated local minima of the dropout training criterion. Our work uncovers new properties of dropout, extends our understanding of why dropout succeeds, and lays the foundation for further progress. [abs] [ pdf ][ bib ] © JMLR 2018. ( edit, beta )
JMLR Journal 2015 Journal Article
Dropout is a simple but effective technique for learning in neural networks and other settings. A sound theoretical understanding of dropout is needed to determine when dropout should be applied and how to use it most effectively. In this paper we continue the exploration of dropout as a regularizer pioneered by Wager et al. We focus on linear classification where a convex proxy to the misclassification loss (i.e. the logistic loss used in logistic regression) is minimized. We show: when the dropout-regularized criterion has a unique minimizer, when the dropout- regularization penalty goes to infinity with the weights, and when it remains bounded, that the dropout regularization can be non- monotonic as individual weights increase from 0, and that the dropout regularization penalty may not be convex. This last point is particularly surprising because the combination of dropout regularization with any convex loss proxy is always a convex function. In order to contrast dropout regularization with $L_2$ regularization, we formalize the notion of when different random sources of data are more compatible with different regularizers. We then exhibit distributions that are provably more compatible with dropout regularization than $L_2$ regularization, and vice versa. These sources provide additional insight into how the inductive biases of dropout and $L_2$ regularization differ. We provide some similar results for $L_1$ regularization. [abs] [ pdf ][ bib ] © JMLR 2015. ( edit, beta )
TCS Journal 2014 Journal Article
We propose a new way to build a combined list from K base lists, each containing N items. A combined list consists of top segments of various sizes from each base list so that the total size of all top segments equals N. A sequence of item requests is processed and the goal is to minimize the total number of misses. That is, we seek to build a combined list that contains all the frequently requested items. We first consider the special case of disjoint base lists. There, we design an efficient algorithm that computes the best combined list for a given sequence of requests. In addition, we develop a randomized online algorithm whose expected number of misses is close to that of the best combined list chosen in hindsight. We prove lower bounds that show that the expected number of misses of our randomized algorithm is close to the optimum. In the presence of duplicate items, we show that computing the best combined list is NP-hard. We show that our algorithms still apply to a linearized notion of loss in this case. We expect that this new way of aggregating lists will find many ranking applications.
JMLR Journal 2012 Journal Article
This work explores the effects of relevant and irrelevant boolean variables on the accuracy of classifiers. The analysis uses the assumption that the variables are conditionally independent given the class, and focuses on a natural family of learning algorithms for such sources when the relevant variables have a small advantage over random guessing. The main result is that algorithms relying predominately on irrelevant variables have error probabilities that quickly go to 0 in situations where algorithms that limit the use of irrelevant variables have errors bounded below by a positive constant. We also show that accurate learning is possible even when there are so few examples that one cannot determine with high confidence whether or not any individual variable is relevant. [abs] [ pdf ][ bib ] © JMLR 2012. ( edit, beta )
ICML Conference 2011 Conference Paper
JMLR Journal 2009 Journal Article
We give an algorithm for the on-line learning of permutations. The algorithm maintains its uncertainty about the target permutation as a doubly stochastic weight matrix, and makes predictions using an efficient method for decomposing the weight matrix into a convex combination of permutations. The weight matrix is updated by multiplying the current matrix entries by exponential factors, and an iterative procedure is needed to restore double stochasticity. Even though the result of this procedure does not have a closed form, a new analysis approach allows us to prove an optimal (up to small constant factors) bound on the regret of our algorithm. This regret bound is significantly better than that of either Kalai and Vempala's more efficient Follow the Perturbed Leader algorithm or the computationally expensive method of explicitly representing each permutation as an expert. [abs] [ pdf ][ bib ] © JMLR 2009. ( edit, beta )
I&C Journal 2001 Journal Article
This paper presents a general information-theoretic approach for obtaining lower bounds on the number of examples required for Probably Approximately Correct (PAC) learning in the presence of noise. This approach deals directly with the fundamental information quantities, avoiding a Bayesian analysis. The technique is applied to several different models, illustrating its generality and power. The resulting bounds add logarithmic factors to (or improve the constants in) previously known lower bounds.
I&C Journal 2000 Journal Article
In the standard on-line model the learning algorithm tries to minimizethe total number of mistakes made in a series of trials. On each trial the learner sees an instance, makes a prediction of its classification, then finds out the correct classification. We define a natural variant of this model (“apple tasting”) where u • the classes are interpreted as the good and bad instances, • the prediction is interpreted as accepting or rejecting the instance, and • the learner gets feedback only when the instance is accepted. We use two transformations to relate the apple tasting model to an enhanced standard model where false acceptances are counted separately from false rejections. We apply our results to obtain a good general-purpose apple tasting algorithm as well as nearly optimal apple tasting algorithms for a variety of standard classes, such as conjunctions and disjunctions of n boolean variables. We also present and analyze a simpler transformation useful when the instances are drawn at random rather than selected by an adversary.
I&C Journal 2000 Journal Article
We consider a generalization of the mistake-bound model (for learning {0, 1}-valued functions) in which the learner must satisfy a general constraint on the number M + of incorrect 1 predictions and the number M − of incorrect 0 predictions. We describe a general-purpose optimal algorithm for our formulation of this problem. We describe several applications of our general results, involving situations in which the learner wishes to satisfy linear inequalities in M + and M −.
ICML Conference 1996 Conference Paper
STOC Conference 1993 Conference Paper
FOCS Conference 1992 Conference Paper
In the standard on-line model the learning algorithm tries to minimize the total number of mistakes made in a series of trials. On each trial the learner sees an instance, either accepts or rejects that instance, and then is told the appropriate response. The authors define a natural variant of this model ('apple tasting') where the learner gets feedback only when the instance is accepted. They use two transformations to relate the apple tasting model to an enhanced standard model where false acceptances are counted separately from false rejections. They present a strategy for trading between false acceptances and false rejections in the standard model. From one perspective this strategy is exactly optimal, including constants. They apply the results to obtain a good general purpose apple tasting algorithm as well as nearly optimal apple tasting algorithms for a variety of standard classes, such as conjunctions and disjunctions of n boolean variables. They also present and analyze a simpler transformation useful when the instances are drawn at random rather than selected by an adversary. >