New insights into the top-K sparse softmax gating function for deep learning.
problem Understanding the theoretical effects of the top-K sparse softmax gating function on density and parameter estimations.
method Using a Gaussian mixture of experts, novel loss functions, and theoretical analysis.
result The convergence rates of density and parameter estimations are parametric under certain conditions, but slow under over-specified models.
Computations for the softmax function are significantly expensive when the number of output classes is large. In this paper, we present a novel softmax inference speedup method, Doubly Sparse Softmax (DS-Softmax), that leverages sparse mixture of sparse experts to efficiently retrieve top-k classes. Different from most…
In order to push the performance on realistic computer vision tasks, the number of classes in modern benchmark datasets has significantly increased in recent years. This increase in the number of classes comes along with increased ambiguity between the class labels, raising the question if top-1 error is the right perf…
Proposes differentiable and sparse top-k operators for neural networks.
problem Discontinuity of top-k operator makes it unsuitable for end-to-end training with backpropagation.
method Formulates top-k as a linear program over permutahedron, introduces p-norm regularization, and uses isotonic optimization.
result Successfully applied to neural network pruning, fine-tuning, and routing.
Top-k error is currently a popular performance measure on large scale image classification benchmarks such as ImageNet and Places. Despite its wide acceptance, our understanding of this metric is limited as most of the previous research is focused on its special case, the top-1 error. In this work, we explore two direc…
Despite being the standard loss function to train multi-class neural networks, the log-softmax has two potential limitations. First, it involves computations that scale linearly with the number of output classes, which can restrict the size of problems we are able to tackle with current hardware. Second, it remains unc…
Introduces top-k regularization for better feature selection in machine learning.
problem Limited ability of existing feature selection methods to reconcile feature representativeness and inter-correlations.
method Top-k regularization, which induces a sub-architecture on the model's architecture to select informative features and model complex relationships. result Uniform approximation error bound for top-k regularization approximating high-dimensional sparse functions. Evidential Softmax preserves multimodality in sparse probability distributions for generative models.
problem Sparse probability distributions in deep generative models make exact marginalization computationally intractable.
method Introduce ev-softmax, a sparse normalization function that preserves multimodality and can be trained with probabilistic loss functions.
result ev-softmax outperforms existing techniques in distributional accuracy and dimensionality reduction.
New sparsity operator reduces variance reduction methods' computational cost.
problem Reduce computational cost of variance reduction methods.
method Introduce random-top-k operator to estimate gradient sparsity and reduce operations per update.
result Our algorithm consistently outperforms SpiderBoost in various tasks.
Neural language models have been widely used in various NLP tasks, including machine translation, next word prediction and conversational agents. However, it is challenging to deploy these models on mobile devices due to their slow prediction speed, where the bottleneck is to compute top candidates in the softmax layer…
Paper extends sparse alternatives to softmax for continuous domains, enabling efficient attention mechanisms.
problem Efficiently assigning zero probability to irrelevant categories in continuous domains.
method Extend alpha-entmax to continuous domains, introducing continuous-domain attention mechanisms.
result Continuous attention allows attending to time intervals and compact regions, improving text classification, machine translation, and visual question answering.
Attention mechanisms have become ubiquitous in NLP. Recent architectures, notably the Transformer, learn powerful context-aware word representations through layered, multi-headed attention. The multiple heads learn diverse types of word relationships. However, with standard softmax attention, all attention heads are de…
This note considers softmax parameter estimation when little/no labeled training data is available, but a priori information about the relative geometry of class label log-odds boundaries is available. It is shown that `data-free' softmax model synthesis corresponds to solving a linear system of parameter equations, wh…
Proposes a sparse classifier for discriminative Gaussian Mixture Models.
problem Softmax-based discriminative models assume unimodality, leading to parameter redundancy.
method Sparse Bayesian learning for GMM-based discriminative model, reducing parameters and complexity.
result The SDGM outperforms existing softmax-based discriminative models.
New method uses temperature to control sparse MoE convergence rates.
problem Sparse MoE convergence rates are slow due to temperature interactions.
method Proposes a novel activation gate to improve convergence rates.
result Improved convergence rates to polynomial rates via novel gate.
Low-rank framework for task-specific LLM ranking from sparse comparisons.
problem Challenges in reliable task-specific ranking of LLMs under sparse, imbalanced comparisons.
method Low-rank modeling of task-by-model ability matrix, max-norm accurate estimator, task-wise top-K recovery guarantees, uncertainty quantification framework.
result Improves sample efficiency and produces tighter, better-calibrated ranking certificates.
We propose sparsemax, a new activation function similar to the traditional softmax, but able to output sparse probabilities. After deriving its properties, we show how its Jacobian can be efficiently computed, enabling its use in a network trained with backpropagation. Then, we propose a new smooth and convex loss func…
DSelect-k improves MoE models for multi-task learning with better performance and smoother training.
problem Smoothness and convergence issues in sparse gate selection for MoE models.
method Developed DSelect-k, a differentiable and sparse gate for MoE models.
result DSelect-k achieves statistically significant improvements in prediction and expert selection over Top-k.
Paper analyzes trade-offs in top-k classification accuracies and proposes a new loss function.
problem CE loss does not always optimize top-k prediction, especially with complex data.
method Introduces a novel top-k transition loss to improve top-k accuracy.
result Our loss function improves top-k accuracy, especially for k > 10.
Class ambiguity is typical in image classification problems with a large number of classes. When classes are difficult to discriminate, it makes sense to allow k guesses and evaluate classifiers based on the top-k error instead of the standard zero-one loss. We propose top-k multiclass SVM as a direct method to optimiz…
The top-k error is often employed to evaluate performance for challenging classification tasks in computer vision as it is designed to compensate for ambiguity in ground truth labels. This practical success motivates our theoretical analysis of consistent top-k classification. Surprisingly, it is not rigorously und…
Converting an n-dimensional vector to a probability distribution over n objects is a commonly used component in many machine learning tasks like multiclass classification, multilabel classification, attention mechanisms etc. For this, several probability mapping functions have been proposed and employed in literature s…
The paper analyzes convergence rates of softmax gating in MoE models.
problem The effectiveness and scalability of machine learning models using MoE.
method Convergence analysis of parameter and expert estimation under MoE with softmax gating and its variants.
result Theoretical results show polynomially many data points are needed for strong identifiability conditions, while exponential points are required for linear experts.
Paper introduces a new loss function for deep imbalanced classification.
problem Class ambiguity and imbalance in large datasets.
method Stochastic top-K hinge loss based on smoothed top-K operator.
result Our loss function significantly outperforms other baseline loss functions in imbalanced datasets.
Smoothed top-k operator improves model training efficiency.
problem Discontinuous top-k operation makes models untrainable end-to-end.
method SOFT top-k operator approximates top-k as EOT solution.
result Improved performance in k-nearest neighbors and beam search.
Paper introduces efficient top-k selection with differential privacy.
problem Efficiently selecting top-k elements with differential privacy.
method Oneshot Laplace mechanism, generalizing Report Noisy Max.
result Noise level of O(sqrt(k)/eps) for approximate differential privacy.
Spark Transformer achieves high sparsity in FFN and attention without sacrificing model quality.
problem Inactivity of most neurons in FFN of Transformers, leading to inefficiency.
method Top-k masking, statistical top-k algorithm, and predictor for activated entries.
result Only 8% of FFN neurons are activated, achieving up to 2.5x wall-time speedup.
Motivated by applications in recommender systems, web search, social choice and crowdsourcing, we consider the problem of identifying the set of top K items from noisy pairwise comparisons. In our setting, we are non-actively given r pairwise comparisons between each pair of n items, where each comparison has noi…
Unified model for prediction and deferral selects top-k entities efficiently.
problem Efficiently selecting top-k entities for deferral in machine learning.
method One-stage Top-k Learning-to-Defer framework with a convex surrogate. result Unified model achieves superior accuracy-cost trade-offs.
Paper characterizes minimax regret rates for online ranking with top-k feedback.
problem Analyzing online ranking with partial feedback.
method Developed techniques from partial monitoring to characterize minimax regret rates.
result Full characterization of minimax regret rates for Precision@n.
Paper introduces MPES for top-k ranking BO with preferential observations.
problem Handling top-k ranking and tie/indifference observations in Bayesian optimization.
method Designs a surrogate model and introduces MPES acquisition function.
result MPES outperforms existing acquisition functions in handling preferential observations.
We present online boosting algorithms for multilabel ranking with top-k feedback, where the learner only receives information about the top k items from the ranking it provides. We propose a novel surrogate loss function and unbiased estimator, allowing weak learners to update themselves with limited information. Using…
Study improves top-k set prediction with low cardinality.
problem Improving top-k set prediction accuracy with low cardinality.
method Introduces new target loss function and surrogate losses.
result Demonstrates effectiveness of cardinality-aware algorithms.
Paper extends top-k Mallows model for better user preference analysis.
problem Capturing real-world user preferences focusing on a limited set of items.
method Generalized top-k Mallows model, novel sampling scheme, efficient algorithm, active learning.
result New tools for analysis and prediction in decision-making scenarios.
Top-k sparsification reduces deep learning communication costs.
problem Reducing communication overhead in distributed deep learning.
method Extensive experiments and theoretical analysis of Top-k sparsification.
result A tighter bound for Top-k operator derived, improving scaling efficiency.
Transformers with linear space and time complexity for accurate attention estimation.
problem Efficiently estimating attention in large-scale tasks without relying on priors.
method Performers use Fast Attention Via positive Orthogonal Random features (FAVOR+) for linear approximation of softmax attention.
result Performers achieve competitive results on various tasks, demonstrating the effectiveness of their attention-learning approach.
Sparse attention model reduces long-context inference time with exponential accuracy guarantees.
problem Efficiently processing long-context queries in large language models.
method Formalizes attention as a projection onto key vectors, analyzes entropic relaxation, and introduces Vashista Sparse Attention.
result Sparse attention concentrates on a constant-size active face, leading to exponential decay of inactive tokens' mass and linear scaling of active face error.
SAE-FiRE extracts key financial info from long documents, improving earnings surprise predictions.
problem Predicting earnings surprises from long, redundant financial documents.
method Sparse Autoencoder feature selection to filter out noise and identify key dimensions.
result SAE-FiRE significantly outperforms baseline approaches in financial datasets.
Work on making classifiers robust against adversarial attacks for top-k predictions.
problem Vulnerability of classifiers to adversarial perturbations, especially for top-k predictions.
method Randomized smoothing to turn any classifier into a robust one, using Gaussian noise.
result Derives a tight robustness in ℓ2 norm for top-k predictions, achieving 62.8% certified top-5 accuracy on ImageNet.
This paper compares average-K and top-K classification methods under ambiguity.
problem Choosing a single label in ambiguous cases leads to low precision.
method Formally characterizes ambiguity profiles and compares average-K and top-K classification methods.
result Average-K can achieve lower error rates than top-K in some ambiguous cases.
Study on top-k classification with new loss functions and algorithms.
problem Improving multi-class classification accuracy and cardinality trade-off.
method Introducing cardinality-aware loss functions and deriving their consistency bounds.
result New cardinality-aware algorithms for top-k classification. This paper explores the preference-based top-K rank aggregation problem. Suppose that a collection of items is repeatedly compared in pairs, and one wishes to recover a consistent ordering that emphasizes the top-K ranked items, based on partially revealed preferences. We focus on the Bradley-Terry-Luce (BTL) model…
The paper proposes methods to identify and sample from mixtures of Mallows models for top-k rankings.
problem Identifying and sampling from mixtures of Mallows models for top-k rankings in a heterogeneous population.
method Efficient sampling algorithms and identifiability proofs for both components of the mixture.
result The identifiability and learnability of the Mallows components' parameters in the mixture.
Recent literature on unsupervised learning focused on designing structural priors with the aim of learning meaningful features, but without considering the description length of the representations. In this thesis, first we introduce the φ metric that evaluates unsupervised models based on their reconstruction …
This paper develops sparse alternatives to continuous distributions, including new types of Gaussians and attention mechanisms.
problem Creating flexible continuous distributions with varying support for machine learning applications.
method Defining Ω-regularized prediction maps and Fenchel-Young losses for arbitrary domains, and deriving new types of Gaussians and attention mechanisms. result Sparse alternatives to continuous distributions, including deformed exponential families and β-Gaussians, are introduced. Unified framework for deferring queries to top-k experts, improving accuracy-cost trade-offs.
problem Limitation of existing L2D frameworks to single-expert deferral.
method Top-k Learning-to-Defer framework, including adaptive Top-k(x) variant. result Superior accuracy-cost trade-offs with multi-expert deferral.
We propose the Limited Multi-Label (LML) projection layer as a new primitive operation for end-to-end learning systems. The LML layer provides a probabilistic way of modeling multi-label predictions limited to having exactly k labels. We derive efficient forward and backward passes for this layer and show how the layer…
Previous literature on unsupervised learning focused on designing structural priors with the aim of learning meaningful features. However, this was done without considering the description length of the learned representations which is a direct and unbiased measure of the model complexity. In this paper, first we intro…