PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning with Average Top-k Loss

Yanbo Fan, Siwei Lyu, Yiming Ying, Bao-Gang Hu

arXiv:1705.08826v2stat.MLcs.LG

TL;DR

Aggregate-loss choices are limited, and the average and maximum losses have different drawbacks. The paper introduces ATk loss, the average of the k largest individual losses, and analyzes its optimization and theory. It reports that ATk can protect smaller groups of hard examples and adapt to different data distributions, with applicability demonstrated on classification and regression tasks.

  • Problem

    Aggregate-loss choices are limited, and the average and maximum losses have different drawbacks, while top-k loss is generally nonconvex in the individual losses.

    Source: §1 · pp. 1–2

  • Method

    The paper introduces ATk loss, averages the k largest individual losses, and studies MATk learning, including a reformulation for stochastic gradient-based optimization and ATk-SVM.

    Source: §1 · pp. 2–3

  • Results

    The paper reports that ATk can better protect small subsets of hard samples, especially in imbalanced problems, and demonstrates MATk learning for binary classification and regression on synthetic and real datasets.

    Source: §1 · p. 3, §6 · p. 8

  • Takeaways & Limitations

    ATk remains convex in the individual losses and can support convex optimization with conventional gradient-based methods.

    Source: §6 · p. 8

    The paper identifies applying ATk to deep learning and large-scale real-life datasets, and developing more efficient optimization methods, as open questions.

    Source: §6 · p. 8

Abstract

from arXiv · show

In this work, we introduce the {\em average top-$k$} (\atk) loss as a new aggregate loss for supervised learning, which is the average over the $k$ largest individual losses over a training dataset. We show that the \atk loss is a natural generalization of the two widely used aggregate losses, namely the average loss and the maximum loss, but can combine their advantages and mitigate their drawbacks to better adapt to different data distributions. Furthermore, it remains a convex function over all individual losses, which can lead to convex optimization problems that can be solved effectively with conventional gradient-based methods. We provide an intuitive interpretation of the \atk loss based on its equivalent effect on the continuous individual loss functions, suggesting that it can reduce the penalty on correctly classified data. We further give a learning theory analysis of \matk learning on the classification calibration of the \atk loss and the error bounds of \atk-SVM. We demonstrate the applicability of minimum average top-$k$ learning for binary classification and regression using synthetic and real datasets.

1 Introduction

The paper introduces average top-k (ATk) loss, averaging the k largest individual losses to balance the average and maximum losses while retaining convexity. On synthetic examples, ATk better protects smaller data sub-clusters from outliers and can yield classifiers closer to the Bayes classifier; the paper also studies its algorithms and theoretical properties.

1 Introduction

  • Aggregate-loss choices are limited: the average loss is widely used, while maximum loss can help with rare sub-populations but is sensitive to outliers, and top-k loss is generally nonconvex.Top-k loss generalizes maximum loss and can reduce its outlier sensitivity, but does not generally produce a convex objective.Source: §1 · p. 2
  • ATk loss averages the k largest individual losses, generalizes the average loss at k = n and the maximum loss at k = 1, and is convex in the individual losses.It is a tight upper bound of the top-k loss, which is generally not convex in the individual losses.Source: §1 · p. 2
  • With k = 10, ATk better protects smaller sub-clusters and yields classifiers closer to the optimal Bayes classifier than the average or maximum loss on the illustrated synthetic datasets.The maximum loss is affected by outliers, while the average loss can sacrifice smaller sub-clusters; minimum misclassification rates occur at k values other than 1 or n.Source: §1 · p. 2
  • The paper reformulates ATk loss to support stochastic gradient-based MATk learning and interprets it as reducing penalties on correctly classified data by shifting and truncating individual losses.With hinge loss, it defines ATk-SVM, studies classification calibration and error bounds, and derives a theoretical lower bound on k for reliable classification.Source: §1 · p. 3
  • The authors report experiments validating MATk learning and examine its use for binary classification and regression on synthetic and real datasets.The contribution list describes the experiments as extensive and aimed at validating MATk learning's effectiveness.Source: §1 · p. 3

2 Formulation and Interpretation

The ATk loss has an equivalent form that avoids sorting and transforms individual losses by shifting and truncating them at zero. This interpretation motivates convex optimization and explains how the transformation can reduce penalties on correctly classified examples.

2 Formulation and Interpretation

  • The equivalent ATk formulation minimizes an average of individual losses shifted and truncated at zero by a parameter λ.This form avoids the sorting procedure in the original definition.Source: §2 · p. 3
  • For continuous convex surrogates, correctly classified examples can still incur penalties and may be sacrificed when minimizing average loss.Applying the hinge transformation reduces these penalties; sufficiently distant correctly classified examples can receive zero penalty.Source: §2 · p. 3
  • When the individual loss is convex in the model parameters, the reformulated objective is jointly convex in the parameters and λ, enabling stochastic projected gradient descent.The described update samples a training example at each iteration.Source: §2 · p. 4
  • ATk-SVM combines the ATk loss with hinge loss in an RKHS and generalizes C-SVM at k = n and ν-SVM when C = 1, K(x_i, x_i) ≤ 1, and ν = k/n.Its dual form yields a convex quadratic program.Source: §2 · p. 4
  • The choice of k can be tuned on validation data, while the calibration analysis supplies a theoretical lower bound and outlier information can narrow the search.Because k is an integer, the paper describes a simple grid search.Source: §2 · p. 4

3 Statistical Analysis

The statistical analysis studies classification calibration for ATk loss and excess misclassification error for ATk-SVM. It gives conditions on the top-k fraction and a high-probability error guarantee under stated assumptions.

3.1 Classification Calibration under ATk Loss

  • For convex individual losses differentiable at zero with negative derivative, ATk calibration is characterized by conditions on ν; in particular, ν > E*ℓ gives calibration and k > nE*ℓ is a sufficient lower bound.For hinge loss, E*ℓ = 2R*; if there is no mass at η(x) = 1/2, the paper also relates the maximum-loss case to the Bayes error.Source: §3.1 · p. 5
  • When the set with η(x) = 1/2 has zero probability, calibration of maximum loss requires ν to be at least approximately 1/n and the Bayes error to become arbitrarily small as n grows.The paper identifies this condition with maximum loss sensitivity to outliers and non-separable data.Source: §3.1 · p. 5

3.2 Error bounds of ATk-SVM

  • For ATk-SVM, Theorem 2 bounds excess misclassification error when k = ⌈n(E_h(f_H) + μ)⌉, for ε ∈ (0, 1] and μ ∈ (0, 1 − E_h(f_H)).The bound assumes the RKHS setup and the stated conditions on ε and μ.Source: §3.2 · p. 6
  • With a universal kernel and C/n → 0, the ATk-SVM misclassification risk can be arbitrarily close to Bayes error with high probability for sufficiently large n.This conclusion follows under the theorem’s stated choice of k and conditions.Source: §3.2 · p. 6

4 Experiments

The experiments compare average top-k learning with average- and maximum-loss objectives in binary classification and regression. Across classification datasets, ATk can improve on both extremes, with an interior range of k outperforming them on four representative datasets.

4 Experiments

  • Classification experiments combine logistic or hinge individual losses with aggregate losses on eight UCI and KEEL benchmark datasets.The average-loss variants correspond to logistic regression and C-SVM, respectively.Source: §4 · p. 6
  • ATk improves classification performance beyond the average-loss baseline, which consistently outperforms maximum loss; gains are especially conspicuous on Monk and Australian.Table 1 reports average misclassification rates over eight datasets; the passage provides no cell values.Source: Table 1 · p. 7, §4 · p. 7
  • On four representative datasets, a range of intermediate k values beats both extremes; increasing k can first reduce noise and outlier effects, then hurt performance.The comparison fixes C at 10^2; declines at larger k are attributed to including more well-classified samples with non-zero loss.Source: §4 · p. 7, Figure 3 · p. 7
  • In regression, ATk usually improves RMSE over average- or maximum-loss objectives on one synthetic and three real datasets.The experiments use square and absolute individual losses and normalize target outputs to [0, 1].Source: §4 · p. 7

5 Related Works

Related work considers aggregate losses that emphasize different portions of the training examples, as well as top-k objectives for individual losses. The paper distinguishes ATk by its convexity with respect to individual losses and notes that it can complement top-k individual-loss methods.

5 Related Works

  • Self-paced learning uses the average of the k smallest individual losses per pass, termed average bottom-k, unlike ATk’s focus on the largest losses.Curriculum and self-paced methods organize training in passes, gradually including samples from easy to hard [9].Source: §5 · pp. 7–8
  • The top-k loss [20] uses the k-th largest individual loss and is advocated as a remedy to average- and maximum-loss drawbacks, but is generally not convex in individual losses.The average bottom-k loss is also generally nonconvex in individual losses.Source: §5 · p. 8
  • Top-k individual losses for ranking and multiclass classification [12] [13] can be combined with ATk as complementary approaches.The multiclass form penalizes a prediction when the correct label is absent from the top k confident predictions.Source: §5 · p. 8

6 Discussion

The discussion presents ATk as a convex aggregate loss that balances average and maximum loss while reducing penalties on correctly classified data. It also identifies open directions, including deep learning, large-scale applications, and broader error-bound analysis.

6 Discussion

  • ATk averages the k largest training losses, generalizes average and maximum loss, and remains convex over individual losses.Its continuous-loss interpretation suggests reduced penalties on correctly classified samples; the paper also studies calibration and ATk-SVM error bounds.Source: §6 · p. 8
  • The paper leaves efficient special-case optimization, unsupervised learning, deep-learning and large-scale applications, and general-loss error bounds for future work.The current optimization uses conventional gradient-based algorithms.Source: §6 · p. 8

Proof of Lemma 1

The appendix expresses a top-k sum through a linear program and its dual, then uses a hinge-based representation and conditions on the individual loss to establish calibration results.

Proof of Lemma 1

  • The proof formulates the top-k sum as a linear program and derives its dual; it also uses λ = x[k] as an optimal solution to establish convexity.The LP constrains p to sum to k with each component between zero and one.Source: Proof of Lemma 1 · p. 10

Proof of Lemma 2

A.2 Proof of Theorem 1

  • Under the stated loss conditions, the proof derives a shifted loss φ(t) = (ℓ(t) − λ*)+ and shows calibration when ν > E*ℓ.The argument uses ℓ(0) = 1 and λ* < ℓ(0) to establish φ’s differentiability at zero and negative derivative.Source: §A.2 · pp. 10–11

A.3 Proof of Theorem 2

The proof establishes error bounds for MATk learning without requiring a universal kernel, using concentration and Rademacher-average arguments.

A.3 Proof of Theorem 2

  • The stated result holds without the universal-kernel assumption required by the contrasted ν-SVM result.The proof invokes the relationship between excess misclassification error and generalization error.Source: §A.3 · pp. 11, 13
  • The proof combines Rademacher-average symmetrization and contraction with concentration inequalities to bound the relevant empirical errors.It uses Hoeffding’s and McDiarmid’s inequalities in the derivation.Source: §A.3 · pp. 11–12
  • A lower bound for ρ_z is established as an intermediate step in proving the main theorem.The argument conditions k on the expected hinge error and a positive margin parameter μ.Source: §A.3 · p. 12

B Examples of ATk loss coupled with different individual losses

With hinge loss, ATk-SVM reduces to ν-SVM under stated conditions, while absolute-loss MATk in an RKHS becomes ν-SVR. These links also yield interpretations of k and an efficient convex optimization formulation.

B Examples of ATk loss coupled with different individual losses

C Toy examples for effects of different aggregate losses

Synthetic binary-classification examples show how ATk can fit varied distributions by choosing k, whereas maximum and average losses can be affected by outliers or multimodality. The useful k ranges depend on the distribution and individual loss.

C Toy examples for effects of different aggregate losses

  • When data are linearly separable without outliers, all tested aggregate losses achieve perfect classification, and ATk has zero misclassification for every k.The examples use six synthetic distributions with 200 samples each.Source: C Toy examples for effects of… · p. 15, Figure 4 · p. 17
  • With one outlier, maximum loss is strongly affected, while ATk is more robust and classifies better for k ≥ 3.The figure compares logistic-loss classifiers on the left with hinge-loss classifiers on the right; ATk misclassification is plotted against k.Source: C Toy examples for effects of… · pp. 15–16, Figure 4 · p. 17
  • For separable data with a rare positive mode, average loss sacrifices rare-mode samples, while ATk fits better for k ∈ [1, 18] with logistic loss and k ∈ [1, 50] with hinge loss.The paper attributes the average-loss behavior to nonzero penalties on some correctly classified samples.Source: C Toy examples for effects of… · p. 16
  • With both multimodality and an outlier, ATk performs better over k ∈ [4, 24] for logistic loss and k ∈ [3, 62] for hinge loss; its k = 10 boundary is closer to the optimal Bayes linear classifier.Neither maximum nor average loss fits this distribution well.Source: C Toy examples for effects of… · p. 16, Figure 4 · p. 17
  • In imbalanced data, ATk achieves better classification for k ∈ [1, 25] with logistic loss and k ∈ [1, 135] with hinge loss, and for an imbalanced case with an outlier, the better ranges are [2, 12] and [3, 59], respectively.In the latter case, maximum-loss performance decreases due to the outlier, and average hinge-loss performance also decreases.Source: C Toy examples for effects of… · p. 16

Related papers

Loading 1705.08826v2…