Efficient Large-Scale Learning of Minimax Risk Classifiers

• URL: http://arxiv.org/abs/2511.17626v1
• Date: Tue, 18 Nov 2025 22:36:47 GMT
• Title: Efficient Large-Scale Learning of Minimax Risk Classifiers
• Authors: Kartheek Bondugula, Santiago Mazuelas, Aritz Pérez,
• Abstract summary: We present a learning algorithm based on the combination of constraint and column generation.<n> Experiments on multiple benchmark datasets show that the proposed algorithm provides upto a 10x speedup for general large-scale data and around a 100x speedup with a sizeable number of classes.
• Score: 10.648049177775684
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Supervised learning with large-scale data usually leads to complex optimization problems, especially for classification tasks with multiple classes. Stochastic subgradient methods can enable efficient learning with a large number of samples for classification techniques that minimize the average loss over the training samples. However, recent techniques, such as minimax risk classifiers (MRCs), minimize the maximum expected loss and are not amenable to stochastic subgradient methods. In this paper, we present a learning algorithm based on the combination of constraint and column generation that enables efficient learning of MRCs with large-scale data for classification tasks with multiple classes. Experiments on multiple benchmark datasets show that the proposed algorithm provides upto a 10x speedup for general large-scale data and around a 100x speedup with a sizeable number of classes.

Related papers

• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  The MIDX-Sampler is a novel adaptive sampling strategy based on an inverted multi-index approach.<n>Our method is backed by rigorous theoretical analysis, addressing key concerns such as sampling bias, gradient bias, convergence rates, and generalization error bounds.
  arXiv  Detail & Related papers  (2025-01-15T04:09:21Z)
• Smooth Ranking SVM via Cutting-Plane Method [6.946903076677842]
  We develop a prototype learning approach that relies on cutting-plane method, similar to Ranking SVM, to maximize AUC. Our algorithm learns simpler models by iteratively introducing cutting planes, thus overfitting is prevented in an unconventional way. Based on the experiments conducted on 73 binary classification datasets, our method yields the best test AUC in 25 datasets among its relevant competitors.
  arXiv  Detail & Related papers  (2024-01-25T18:47:23Z)
• Large-scale Fully-Unsupervised Re-Identification [78.47108158030213]
  We propose two strategies to learn from large-scale unlabeled data. The first strategy performs a local neighborhood sampling to reduce the dataset size in each without violating neighborhood relationships. A second strategy leverages a novel Re-Ranking technique, which has a lower time upper bound complexity and reduces the memory complexity from O(n2) to O(kn) with k n.
  arXiv  Detail & Related papers  (2023-07-26T16:19:19Z)
• Efficient Learning of Minimax Risk Classifiers in High Dimensions [3.093890460224435]
  High-dimensional data is common in multiple areas, such as health care and genomics, where the number of features can be tens of thousands. In this paper, we leverage such methods to obtain an efficient learning algorithm for the recently proposed minimax risk classifiers. Experiments on multiple high-dimensional datasets show that the proposed algorithm is efficient in high-dimensional scenarios.
  arXiv  Detail & Related papers  (2023-06-11T11:08:20Z)
• Scalable Clustering: Large Scale Unsupervised Learning of Gaussian Mixture Models with Outliers [5.478764356647437]
  This paper introduces a provably robust clustering algorithm based on loss minimization. It provides theoretical guarantees that the algorithm obtains high accuracy with high probability. Experiments on real-world large-scale datasets demonstrate the effectiveness of the algorithm.
  arXiv  Detail & Related papers  (2023-02-28T14:39:18Z)
• Compound Batch Normalization for Long-tailed Image Classification [77.42829178064807]
  We propose a compound batch normalization method based on a Gaussian mixture. It can model the feature space more comprehensively and reduce the dominance of head classes. The proposed method outperforms existing methods on long-tailed image classification.
  arXiv  Detail & Related papers  (2022-12-02T07:31:39Z)
• Continual Learning For On-Device Environmental Sound Classification [63.81276321857279]
  We propose a simple and efficient continual learning method for on-device environmental sound classification. Our method selects the historical data for the training by measuring the per-sample classification uncertainty.
  arXiv  Detail & Related papers  (2022-07-15T12:13:04Z)
• CvS: Classification via Segmentation For Small Datasets [52.821178654631254]
  This paper presents CvS, a cost-effective classifier for small datasets that derives the classification labels from predicting the segmentation maps. We evaluate the effectiveness of our framework on diverse problems showing that CvS is able to achieve much higher classification results compared to previous methods when given only a handful of examples.
  arXiv  Detail & Related papers  (2021-10-29T18:41:15Z)
• Hyperspherical embedding for novel class classification [1.5952956981784217]
  We present a constraint-based approach applied to representations in the latent space under the normalized softmax loss. We experimentally validate the proposed approach for the classification of unseen classes on different datasets using both metric learning and the normalized softmax loss. Our results show that not only our proposed strategy can be efficiently trained on larger set of classes, as it does not require pairwise learning, but also present better classification results than the metric learning strategies.
  arXiv  Detail & Related papers  (2021-02-05T15:42:13Z)
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View [82.80085730891126]
  We provide the first modernally precise analysis of linear multiclass classification. Our analysis reveals that the classification accuracy is highly distribution-dependent. The insights gained may pave the way for a precise understanding of other classification algorithms.
  arXiv  Detail & Related papers  (2020-11-16T05:17:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.