Federated learning (FL) trains machine learning models over heterogeneous and decentralized datasets. Communication between client and server can be a major bottleneck for FL, especially in cases of large models. Moreover, real-world FL problems often involve data heterogeneity issues such as class imbalance. We propose an approach to address these issues of class balance and communication efficiency in Federated Learning. Our strategy is based on two key elements: 1. a novel adaptive voting-based federated dropout on client models addressing communication bottlenecks and data heterogeneity, and 2. a heterogeneous quantization method that can adjust to clients' bandwidth requirements. We conduct experiments across several datasets and models demonstrating that these two components work together to balance the trade-off between communication costs and model performance with clients having heterogeneous communication bandwidth. Importantly, our approach improves performance on imbalanced datasets like CIFAR-10-LT and CIFAR-100-LT, which is critical for addressing class imbalance in federated learning. On CIFAR-10 We get approximately a seven-factor reduction in communication cost without degrading the quality of the model.

Neural networks are often pre-trained on a large source dataset and then fine-tuned on a smaller target dataset. Although pre-training on large-scale datasets is very useful, it has a few disadvantages, such as (1) high training cost and (2) domain mismatch where pre-training on a less-related source might lead to poor results in a target model. Examples of this are areas like underwater imaging, medical imaging, microscopic imaging, etc. Many datasets in these domains also have class imbalance which makes transfer learning less effective. In this paper, we propose an efficient method for selective pre-training, i.e. selecting relevant subsets from a pre-training dataset. Fine-tuning with our method gives better accuracy while increasing training efficiency. We validate our technique with selective pre-training on ImageNet21k and ImageNet1k datasets, and fine-tuning on tasks like image classification and image segmentation. We conduct experiments on several imbalanced datasets and compare our performance with full pre-training as well as other state-of-the-art methods to handle class imbalance. On imbalanced CIFAR-10 we get an accuracy of 77% with pre-training on 500k images of ImageNet1k compared to 74% for full pre-training on ImageNet.

Lloyd k-means is a widely used clustering algorithm. The Hamerly and Annulus algorithms are faster versions of the Lloyd k-means, employing the triangle inequality to skip unnecessary distance computations. In this paper, we propose new probabilistic k-means clustering algorithms - Beta k-means and Beta Hamerly k-means, which converge faster than the Lloyd, Hamerly, and Annulus algorithms for a high number of clusters and dimensions. We compute the probability of a center being closest to the point, and if the probability is lower than the threshold, the distance calculation can be skipped. To the best of our knowledge, this is the first algorithm that uses Beta distribution to accelerate k-means. Experiments were conducted to demonstrate the advantages of the proposed algorithm in practice.

The k-means algorithm calculates the distances be-tween all points and centers at every iteration, which results in a significant amount of wasted work and slows down the algorithm. Many algorithms have been proposed to increase the convergence speed by skipping unnecessary distance computations, often using distance bounds that are cheaply adjusted with the triangle inequality. This paper proposes an annealing technique that can further accelerate these algorithms by tightening the bounds. As a result, we skip even more distance computations and only calculate the distances when the chance of changing an assignment is high. The function that tightens the bound is adaptive and depends on the number of points that change the assignment in the last iteration. The annealing technique can speed up both Hamerly's and Elkan's accelerated algorithms without lowering the output quality. Experimental results showed a time improvement of up to 15 percent, representing a significant performance boost over the Hamerly algorithm.

The k-means algorithm is popular for data clustering applications. Most implementations use Lloyd's algorithm, which does many unnecessary distance calculations. Several accelerated algorithms (Elkan's, Hamerly's, heap, etc.) have recently been developed which produce exactly the same answer as Lloyd's, only faster. They avoid redundant work using the triangle inequality paired with a set of lower and upper bounds on point-centroid distances. In this paper we propose several novel methods that allow those accelerated algorithms to perform even better, giving up to eight times further speedup. Our methods give tighter lower bound updates, efficiently skip centroids that cannot possibly be close to a set of points, keep extra information about upper bounds to help the heap algorithm avoid more distance computations, and decrease the number of distance calculations that are done in the first iteration.

The k-means algorithm is widely used for clustering, compressing, and summarizing vector data. In this paper, we propose a new acceleration for exact k-means that gives the same answer, but is much faster in practice. Like Elkan’s accelerated algorithm [8], our algorithm avoids distance computations using distance bounds and the triangle inequality. Our algorithm uses one novel lower bound for point-center distances, which allows it to eliminate the innermost k-means loop 80% of the time or more in our experiments. On datasets of low and medium dimension (e.g. up to 50 dimensions), our algorithm is much faster than other methods, including methods based on low-dimensional indexes, such as k-d trees. Other advantages are that it is very simple to implement and it has a very small memory overhead, much smaller than other accelerated algorithms.

We investigate here the behavior of the standard k-means clustering algorithm and several alternatives to it: the k-harmonic means algorithm due to Zhang and colleagues, fuzzy k-means, Gaussian expectation-maximization, and two new variants of k-harmonic means. Our aim is to find which aspects of these algorithms contribute to finding good clusterings, as opposed to converging to a low-quality local optimum. We describe each algorithm in a unified framework that introduces separate cluster membership and data weight functions. We then show that the algorithms do behave very differently from each other on simple low-dimensional synthetic datasets and image segmentation tasks, and that the k-harmonic means method is superior. Having a soft membership function is essential for finding high-quality clusterings, but having a non-constant data weight function is useful also.