A simple modification improves GAN performance by discarding bad samples.
problem Improving GAN performance with minimal computational cost.
method Top-k update procedure: zero out gradient contributions from least realistic elements.
result Significant improvement in FID score for conditional generation on CIFAR-10.
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…
A new energy-efficient pruning method for federated learning.
problem Energy inefficiency in gradient sparsification for federated learning.
method Formalized energy-constrained projection problem and proposed Cost-Weighted Magnitude Pruning (CWMP).
result CWMP optimally balances performance and energy efficiency in federated learning.
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.
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…
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.
Paper tackles ranking items with a semi-random comparison graph and a monotone adversary.
problem Ranking items based on pairwise comparisons from a semi-random comparison graph with a monotone adversary.
method Developed a weighted maximum likelihood estimator (MLE) and an SDP-based approach to reweight the semi-random graph.
result Achieves near-optimal sample complexity, up to a log^2(n) factor, for identifying the top-K preferred items.
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…
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…
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.
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.
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…
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.
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.
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.
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…
CPATTA uses conformal prediction for efficient test-time adaptation.
problem Low data selection efficiency in existing ATTA methods.
method Conformal Prediction, online weight-update algorithm, domain-shift detector, staged update scheme.
result CPATTA consistently outperforms state-of-the-art methods by 5% in accuracy.
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.
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…
Analyze SGD with biased gradients, improving convergence rates and accuracy.
problem Analyzing the convergence of SGD with biased gradients.
method Derive convergence results for smooth non-convex functions and quantify the impact of bias magnitude.
result Improved rates under the Polyak-Lojasiewicz condition and insights into how bias magnitude affects accuracy and convergence.
New method makes CNN interpretations robust to adversarial attacks.
problem Adversarial attacks on CNN interpretation maps.
method Renyi Differential Privacy (RDP) for robust interpretation.
result Certifiable top-k robustness and improved experimental robustness. 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. 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.
Optimizes communication in federated learning using rate-distortion theory.
problem Reduces communication cost in federated learning while maintaining model accuracy.
method Applies rate-distortion theory to model updates, proposing distortion as a proxy for accuracy.
result Near-optimal communication reduction, outperforming other methods on a FL benchmark.
We study the top-K ranking problem where the goal is to recover the set of top-K ranked items out of a large collection of items based on partially revealed preferences. We consider an adversarial crowdsourced setting where there are two population sets, and pairwise comparison samples drawn from one of the populat…
Optimizes ranking of top-k players from partial comparison data.
problem Identifying the top-k players from incomplete pairwise comparisons.
method Maximum Likelihood Estimator (MLE) and Spectral Method.
result MLE achieves optimal partial and exact recovery, while Spectral Method is sub-optimal.
Optimizes identifying top-k items from comparisons with minimal comparisons.
problem Finding the top-k items from pairwise comparisons with a fixed error rate.
method Developed an asymptotically optimal algorithm using primal-dual procedure and adaptive comparison allocation.
result Proves the algorithm is asymptotically optimal for top-k identification.
Distributed stochastic gradient descent (SGD) algorithms are widely deployed in training large-scale deep learning models, while the communication overhead among workers becomes the new system bottleneck. Recently proposed gradient sparsification techniques, especially Top-k sparsification with error compensation (To…
FedSel uses local differential privacy to protect data privacy in federated SGD.
problem Privacy leakage from gradients in federated SGD.
method Two-stage framework with top-k dimension selection and gradient accumulation.
result FedSel reduces privacy leakage by privately selecting important dimensions.
The paper addresses calibration in label ranking, a structured prediction task.
problem Calibration in label ranking is not well understood and often poorly calibrated.
method Formalized calibration for label ranking, developed a hierarchy of notions, and empirically evaluated models.
result Popular label ranking models are often poorly calibrated, with differences between sub-ranking and top-k metrics.
We explore the top-K rank aggregation problem. Suppose a collection of items is compared in pairs repeatedly, and we aim to recover a consistent ordering that focuses on the top-K ranked items based on partially revealed preference information. We investigate the Bradley-Terry-Luce model in which one ranks items ac…
RAMPART ranks top-k features more accurately than existing methods.
problem Accurate ranking of important features in machine learning.
method Adaptive sequential halving strategy combined with ensembling techniques.
result RAMPART achieves the correct top-k ranking with high probability.
Proposes a method to infer ranking properties and top-K rankings with uncertainty quantification.
problem General uncertainty quantification in ranking problems.
method Combinatorial inference framework for the Bradley-Terry-Luce model, generalized to multiple testing.
result Minimax optimal method for inferring top-K rankings with FDR control.
As traditional neural network consumes a significant amount of computing resources during back propagation, \citet{Sun2017mePropSB} propose a simple yet effective technique to alleviate this problem. In this technique, only a small subset of the full gradients are computed to update the model parameters. In this paper …
We propose a simple yet effective technique to simplify the training and the resulting model of neural networks. In back propagation, only a small subset of the full gradient is computed to update the model parameters. The gradient vectors are sparsified in such a way that only the top-k elements (in terms of magnitude…
We study the active learning problem of top-k ranking from multi-wise comparisons under the popular multinomial logit model. Our goal is to identify the top-k items with high probability by adaptively querying sets for comparisons and observing the noisy output of the most preferred item from each comparison. To ac…
This paper explores the adaptive (active) PAC (probably approximately correct) top-k ranking (i.e., top-k item selection) and total ranking problems from l-wise (l≥2) comparisons under the multinomial logit (MNL) model. By adaptively choosing sets to query and observing the noisy output of the most favored …
Efficiently addresses federated learning challenges with reduced communication and sample complexity.
problem Heterogeneity in data volumes and distributions at different clients compromises model generalization ability.
method Introduces algorithms for communication-efficient Federated Group Distributionally Robust Optimization (FGDRO).
result Communication complexity reduced to O(1/ε4) for FGDRO-CVaR and O(1/ε3) for FGDRO-KL. Top-k Combinatorial Bandits generalize multi-armed bandits, where at each round any subset of k out of n arms may be chosen and the sum of the rewards is gained. We address the full-bandit feedback, in which the agent observes only the sum of rewards, in contrast to the semi-bandit feedback, in which the agent obse…