Combinatorial linear semi-bandits (CLS) are widely applicable frameworks of sequential decision-making, in which a learner chooses a subset of arms from a given set of arms associated with feature vectors. Existing algorithms work poorly for the clustered case, in which the feature vectors form several large clusters. This shortcoming is critical in practice because it can be found in many applications, including recommender systems. In this paper, we clarify why such a shortcoming occurs, and we introduce a key technique of arm-wise randomization to overcome it. We propose two algorithms with this technique: the perturbed C${}^2$UCB (PC${}^2$UCB) and the Thompson sampling (TS). Our empirical evaluation with artificial and real-world datasets demonstrates that the proposed algorithms with the arm-wise randomization technique outperform the existing algorithms without this technique, especially for the clustered case. Our contributions also include theoretical analyses that provide high probability asymptotic regret bounds for our algorithms.

We address the problem of combining sequence models of symbolic music with user defined constraints. For typical models this is nontrivial as only the conditional distribu - tion of each symbol given the earlier symbols is available, while the constraints correspond to arbitrary times. Previ - ously this has been addressed by assuming a discrete time model of fixed rhythm. We generalise to continuous time and arbitrary rhythm by introducing a simple, novel, and efficie nt particle filter scheme, applicable to general continuous ti me point processes. Extensive experimental evaluations demo n-strate that in comparison with a more traditional beam searc h baseline, the particle filter exhibits superior statistica l properties and yields more agreeable results in an extensive human listening test experiment.

The inverse Potts problem to infer the Boltzmann distribution for homologous protein sequences from their single-site and pairwise frequencies recently attracts a great deal of attention due to its capacity to accurately predict residue-residue contacts in a 3D protein complex. A Boltzmann machine for the accurate estimation of the field and coupling interactions, which is required for other studies in protein evolution and folding, is studied about learning methods, regularization models and a tuning method of regularization parameters in order to infer the interactions with reasonable characteristics. Using $L_2$ regularization for fields, group $L_1$ for couplings is shown to be very effective for parse couplings in comparison with $L_2$ and with $L_1$. Two regularization parameters for fields and couplings are tuned to yield equal values for both the sample average and the ensemble average of evolutionary energies of natural proteins. Both the averages along a learning process smoothly change and converge, but their profiles are very different between the learning methods. Most per-parameter adaptive learning methods invented for machine learning cannot learn reasonable parameters for sparse-interaction systems. A modified Adam (ModAdam) method is invented to make step-size proportional to the partial derivative for sparse couplings and to use a soft thresholding function for group $L_1$. It is shown by first inferring interactions from protein sequences and then from Monte Carlo samples that the fields and couplings can be well recovered by the group $L_1$ and the ModAdam method. However, the distribution of evolutionary energies over natural proteins is shifted towards lower energies from that of Monte Carlo samples, indicating that there may be higher-order interactions to favor natural sequences.

Forums play an important role in providing a platform for community interaction. The introduction of irrelevant content or spam by individuals for commercial and social gains tends to degrade the professional experience presented to the forum users. Automated moderation of the relevancy of posted content is desired. Machine learning is used for text classification and finds applications in spam email detection, fraudulent transaction detection etc. The balance of classes in training data is essential in the case of classification algorithms to make the learning efficient and accurate. However, in the case of forums, the spam content is sparse compared to the relevant content giving rise to a bias towards the latter while training. A model trained on such biased data will fail to classify a spam sample. An approach based on Synthetic Minority Over-sampling Technique(SMOTE) is presented in this paper to tackle imbalanced training data. It involves synthetically creating new minority class samples from the existing ones until balance in data is achieved. The enhanced data is then passed through various classifiers for which the performance is recorded. The results were analyzed on the data of forums of Spoken Tutorial, IIT Bombay over standard performance metrics and revealed that models trained after Synthetic Minority oversampling outperform the ones trained on imbalanced data by substantial margins. An empirical comparison of the results obtained by both SMOTE and without SMOTE for various supervised classification algorithms have been presented in this paper. Synthetic oversampling proves to be a critical technique for achieving uniform class distribution which in turn yields commendable results in text classification. The presented approach can be further extended to content categorization on educational websites thus helping to improve the overall digital learning experience.

We shed new insights on the two commonly used updates for the online $k$-PCA problem, namely, Krasulina's and Oja's updates. We show that Krasulina's update corresponds to a projected gradient descent step on the Stiefel manifold of the orthonormal $k$-frames, while Oja's update amounts to a gradient descent step using the unprojected gradient. Following these observations, we derive a more \emph{implicit} form of Krasulina's $k$-PCA update, i.e. a version that uses the information of the future gradient as much as possible. Most interestingly, our implicit Krasulina update avoids the costly QR-decomposition step by bypassing the orthonormality constraint. We show that the new update in fact corresponds to an online EM step applied to a probabilistic $k$-PCA model. The probabilistic view of the updates allows us to combine multiple models in a distributed setting. We show experimentally that the implicit Krasulina update yields superior convergence while being significantly faster. We also give strong evidence that the new update can benefit from parallelism and is more stable w.r.t. tuning of the learning rate.

We revisit the local Stochastic Gradient Descent (local SGD) method and prove new convergence rates. We close the gap in the theory by showing that it works under unbounded gradients and extend its convergence to weakly convex functions. Furthermore, by changing the assumptions, we manage to get new bounds that explain in what regimes local SGD is faster that its non-local version. For instance, if the objective is strongly convex, we show that, up to constants, it is sufficient to synchronize $M$ times in total, where $M$ is the number of nodes. This improves upon the known requirement of Stich (2018) of $\sqrt{TM}$ synchronization times in total, where $T$ is the total number of iterations, which helps to explain the empirical success of local SGD.

We propose and analyze a new type of stochastic first order method: gradient descent with compressed iterates (GDCI). GDCI in each iteration first compresses the current iterate using a lossy randomized compression technique, and subsequently takes a gradient step. This method is a distillation of a key ingredient in the current practice of federated learning, where a model needs to be compressed by a mobile device before it is sent back to a server for aggregation. Our analysis provides a step towards closing the gap between the theory and practice of federated learning, and opens the possibility for many extensions.

We provide the first convergence analysis of local gradient descent for minimizing the average of smooth and convex but otherwise arbitrary functions. Problems of this form and local gradient descent as a solution method are of importance in federated learning, where each function is based on private data stored by a user on a mobile device, and the data of different users can be arbitrarily heterogeneous. We show that in a low accuracy regime, the method has the same communication complexity as gradient descent.

Among different types of networks, Residual Network (ResNet, He et al. (2016a)) is undoubted a milestone. ResNet is equipped with shortcut connections, which skip layers in the forward step of an input. Similar idea also appears in the Highway Networks (Srivastava et al., 2015), and further inspires densely connected convolutional networks (Huang et al., 2017). ResNet owes its great success to a surprisingly efficient training compared to the widely used feedforward Convolutional Neural Networks (CNN, Krizhevsky et al. (2012)). Feedforward CNNs are seldomly used with more than 30 layers in the existing literature. There are experimental results suggest that very deep feedforward CNNs are significantly slow to train, and yield worse performance than their shallow counterparts (He et al., 2016a). However, simple first order algorithms such as stochastic gradient descent and its variants are able to train ResNet with hundreds T. Liu, M. Chen, E. Zhou, and T. Zhao are affiliated with School of Industrial and Systems Engineering at Georgia Tech; M. Zhou is now affiliated with CS Department of Duke University; S. S. Du is now affiliated with Institute for Advanced Study; This work is done while M. Zhou is at Peking University and S. S. Du is a Ph.D. student at CMU. T. Liu and M. Chen contribute equally; T uo Zhao is the corresponding author; Email: tourzhao@gatech.edu. 1 arXiv:1909.04653v2

--Automated brain tumor segmentation plays an important role in the diagnosis and prognosis of the patient. The main focus of this paper is to segment tumor from BRA TS 2018 benchmark dataset and use age, shape and volumetric features to predict overall survival of patients. The random forest classifier achieves overall survival accuracy of 59% on the test dataset and 67% on the dataset with resection status as gross total resection. The proposed approach uses fewer features but achieves better accuracy than state-of- the-art methods. Medical fraternity considers brain tumor amongst the most fatal type of cancer [1]. Brain tumors are divided into two categories based on origin and malignancy. Former is further classified as primary and secondary.