Recent neural network and language models have begun to rely on softmax distributions with an extremely large number of categories. In this context calculating the softmax normalizing constant is prohibitively expensive. This has spurred a growing literature of efficiently computable but biased estimates of the softmax. In this paper we present the first two unbiased algorithms for maximizing the softmax likelihood whose work per iteration is independent of the number of classes and datapoints (and does not require extra work at the end of each epoch). We compare our unbiased methods' empirical performance to the state-of-the-art on seven real world datasets, where they comprehensively outperform all competitors. Under the softmax model 1 the probability that a random variable y takes on the label ∈ {1, ..., K}, is given by p(y = |x; W ) = e where x ∈ R D is the covariate, w k ∈ R D is the vector of parameters for the k-th class, and W = [w 1 , w 2 , ..., w K ] ∈ R D×K is the parameter matrix. Given a dataset of N label-covariate pairs D = {(y i , x i )} N i=1 , the ridge-regularized maximum log-likelihood problem is given by DISPLAYFORM0 where W 2 denotes the Frobenius norm.This paper focusses on how to maximize (2) when N, K, D are all large. Having large N, K, D is increasingly common in modern applications such as natural language processing and recommendation systems, where N, K, D can each be on the order of millions or billions BID15 BID6 BID4 .A natural approach to maximizing L(W ) with large N, K, D is to use Stochastic Gradient Descent (SGD), sampling a mini-batch of datapoints each iteration. However if K, D are large then the O(KD) cost of calculating the normalizing sum K k=1 e x i w k in the stochastic gradients can still be prohibitively expensive. Several approximations that avoid calculating the normalizing sum have been proposed to address this difficulty. These include tree-structured methods BID2 BID7 BID9 , sampling methods BID1 BID14 BID10 and self-normalization BID0 . Alternative models such as the spherical family of losses that do not require normalization have been proposed to sidestep the issue entirely BID13 . BID11 avoid calculating the sum using a maximization-majorization approach based on lower-bounding the eigenvalues of the Hessian matrix. All 2 of these approximations are computationally tractable for large N, K, D, but are unsatisfactory in that they are biased and do not converge to the optimal W * = argmax L(W ).Recently BID16 managed to recast (2) as a double-sum over N and K. This formulation is amenable to SGD that samples both a datapoint and class each iteration, reducing the per iteration cost to O(D). The problem is that vanilla SGD when applied to this formulation is unstable, in that the gradients suffer from high variance and are susceptible to computational overflow. BID16 deal with this instability by occasionally calculating the normalizing sum for all datapoints at a cost of O(N KD). Although this achieves stability , its high cost nullifies the benefit of the cheap O(D) per iteration cost.The goal of this paper is to develop robust SGD algorithms for optimizing double-sum formulations of the softmax likelihood. We develop two such algorithms. The first is a new SGD method called U-max, which is guaranteed to have bounded gradients and converge to the optimal solution of (2) for all sufficiently small learning rates. The second is an implementation of Implicit SGD, a stochastic gradient method that is known to be more stable than vanilla SGD and yet has similar convergence properties BID18 . We show that the Implicit SGD updates for the doublesum formulation can be efficiently computed and has a bounded step size, guaranteeing its stability.We compare the performance of U-max and Implicit SGD to the (biased) state-of-the-art methods for maximizing the softmax likelihood which cost O(D) per iteration. Both U-max and Implicit SGD outperform all other methods. Implicit SGD has the best performance with an average log-loss 4.29 times lower than the previous state-of-the-art.In summary, our contributions in this paper are that we:1. Provide a simple derivation of the softmax double-sum formulation and identify why vanilla SGD is unstable when applied to this formulation (Section 2). 2. Propose the U-max algorithm to stabilize the SGD updates and prove its convergence (Section 3.1). 3. Derive an efficient Implicit SGD implementation, analyze its runtime and bound its step size (Section 3.2). 4. Conduct experiments showing that both U-max and Implicit SGD outperform the previous state-of-the-art, with Implicit SGD having the best performance (Section 4). In this paper we have presented the U-max and Implicit SGD algorithms for optimizing the softmax likelihood. These are the first algorithms that require only O(D) computation per iteration (without extra work at the end of each epoch) that converge to the optimal softmax MLE. Implicit SGD can be efficiently implemented and clearly out-performs the previous state-of-the-art on seven real world datasets. The result is a new method that enables optimizing the softmax for extremely large number of samples and classes.So far Implicit SGD has only been applied to the simple softmax, but could also be applied to any neural network where the final layer is the softmax. Applying Implicit SGD to word2vec type models, which can be viewed as softmaxes where both x and w are parameters to be fit, might be particularly fruitful. 10 The learning rates η = 10 3,4 are not displayed in the FIG2 for visualization purposes. It had similar behavior as η = 10 2 .
Propose first methods for exactly optimizing the softmax distribution using stochastic gradient with runtime independent on the number of classes or datapoints.
{"src": "scitldr-AIC_train", "paper_id": "H1bhRHeA-"}