PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimizing the Maximal Loss: How and Why?

Shai Shalev-Shwartz, Yonatan Wexler

arXiv:1602.01690v2cs.LG

TL;DR

Average-loss minimization is convenient for online learning, while maximal loss can drive higher training accuracy, but its relevance to unseen examples and sensitivity to outliers are concerns. The paper converts online learners into maximal-loss minimizers and studies rare-example guarantees. It reports that, under stated conditions, minimizing even a few rare examples can secure good performance on unseen rare examples.

  • Problem

    Average loss supports online updates from a few examples, while the value of greater training accuracy for unseen-example performance is uncertain and maximal loss is vulnerable to outliers.

    Source: §1 · p. 1

  • Method

    The paper develops a meta-algorithm that converts any online learner into a maximal-loss minimizer and proposes robust versions using outlier-handling techniques.

    Source: §1 · p. 2, §4.2 · p. 7

  • Results

    Under stated conditions, minimizing even a few rare examples can guarantee good performance on unseen examples from the rare scenario.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The authors conclude that minimizing maximal loss is preferable to average loss in some situations.

    Source: §1 · p. 2

    Convexity of φ_y alone does not ensure that the loss is convex in w; this also requires h_w(x) to be affine in w.

    Source: §2.2 · p. 3

Abstract

from arXiv · show

A commonly used learning rule is to approximately minimize the \emph{average} loss over the training set. Other learning algorithms, such as AdaBoost and hard-SVM, aim at minimizing the \emph{maximal} loss over the training set. The average loss is more popular, particularly in deep learning, due to three main reasons. First, it can be conveniently minimized using online algorithms, that process few examples at each iteration. Second, it is often argued that there is no sense to minimize the loss on the training set too much, as it will not be reflected in the generalization loss. Last, the maximal loss is not robust to outliers. In this paper we describe and analyze an algorithm that can convert any online algorithm to a minimizer of the maximal loss. We prove that in some situations better accuracy on the training set is crucial to obtain good performance on unseen examples. Last, we propose robust versions of the approach that can handle outliers.

1. Introduction

Average loss is convenient for online learning, but minimizing maximal loss can improve training accuracy; the paper develops an online conversion, studies when that accuracy helps on rare examples, and addresses outliers.

1. Introduction

  • Average loss supports online updates from a few examples because a randomly sampled example's gradient is an unbiased estimate, unlike maximal loss.Source: §1 · p. 1
  • The authors identify uncertainty about whether greater training accuracy from minimizing maximal loss improves performance on unseen examples.Source: §1 · p. 1
  • Maximal loss is not robust to outliers: even one outlier can make its minimizer meaningless.Source: §1 · p. 2
  • The authors describe a meta-algorithm that converts any online learner into a minimizer of maximal training loss.Source: §1 · p. 2
  • When training data include typical and rare scenarios, conditions can make minimizing even a few rare examples sufficient for good performance on unseen rare examples.The authors argue that high accuracy on both typical and rare examples is often desirable.Source: §1 · p. 2
  • The paper reviews standard techniques for extending its results from realizable cases to settings with outliers.Source: §1 · p. 2
  • The paper reports empirical evidence that its algorithm is effective on real-world learning problems.Source: §1 · p. 2

2. How

FOL frames maximal-loss minimization as a game between an online learner and an example-selecting player, then returns an ensemble or predictor with bounded loss on every training example. The section gives classification and convex-loss guarantees, implementation details, and comparisons with related methods.

2. How

  • FOL frames maximal-loss minimization as a zero-sum game: a player selects examples to maximize loss while an online learner chooses predictors to minimize it.The example player uses EXP3-style sampling with a half-uniform mixture; the tree-based update takes O(log(m)) time per iteration.Source: §2 · pp. 2–3
  • Under Theorem 1's conditions, FOL finds an ensemble of O(log(m)/ϵ) predictors whose ensemble loss is below ϵ on every example.The theorem gives a probability-at-least-1−δ guarantee and conditions on T, k, and the online learner's mistake bound.Source: §2 · p. 3

2.1. Classification

  • With zero-one loss, FOL's majority classifier is consistent on the entire training set with probability at least 1−δ.For the Perceptron example, the stated runtime is ˜O(m + C), compared with order m C iterations for SGD.Source: §2.1 · p. 3

2.2. Convex Losses

  • For losses φ_y(h_w(x)) with convex φ_y, the average predictor has loss at most ϵ on every training example; an affine predictor permits the corresponding averaged parameters.Convexity of φ_y alone does not ensure that the loss is convex in w; affinity of h_w(x) is additionally required for that property.Source: §2.2 · p. 3

2.3. Pseudo-code

  • The pseudocode uses a tree to sample and update the example player's probabilities, adding O(log(m)) time per iteration to the online learner's step.Source: §2.3 · p. 4

2.4. Related Work

  • Against Clarkson et al. [the cited work], the Perceptron-based runtime can be better or worse; for sparse instances, its dimension factor can use the sparsity bound.The stated bounds are ˜O((m + d) · C) for Clarkson et al. and ˜O((m + C) · d) for this method; the authors also describe the method as an online version of AdaBoost.Source: §2.4 · p. 4

3. Why

The section argues that worst-case bounds can obscure cases where minimizing maximal loss is preferable, and examines when training-set accuracy matters for unseen examples. It shows that a small number of rare examples can support good performance on both typical and rare distributions, under data-dependent conditions.

3. Why

  • The section challenges reliance on worst-case bounds, presenting a problem where SGD and ERM have a large sample-complexity gap and the proposed algorithm runs faster than SGD.The supplied lemmas quantify the ERM and SGD outcomes for the example.Source: §3 · p. 5, §3.1 · p. 5

3.1. A Simple Example of a Gap

  • With sufficient sample size, every ERM hypothesis has zero generalization error, while hinge-loss SGD may need Ω(1/(αε)) iterations to find error below ε.The ERM guarantee holds with probability at least 1−δ when m ≥ 2 log(4/δ)/ε; the SGD result holds with probability 1−O(ε) for fewer iterations.Source: §3.1 · p. 5

3.2. Typical vs. Rare Distributions

  • A hypothesis with average loss at most ε may still err on most rare examples when their mixture weight is below ε, motivating maximal-loss minimization for accuracy on both distributions.The analysis bounds the required rare examples using the reduced class of hypotheses already accurate on the typical distribution and a separation condition on their rare-distribution errors.Source: §3.2 · pp. 5–6
  • A small number of rare examples can strongly affect performance on the rare distribution, but benefiting from them requires consistency on most such examples.Figure 1 illustrates typical face and non-face examples alongside rare negative examples.Source: §3.2 · p. 6, Figure 1 · p. 6

4. Robustness

The section adapts two known outlier-handling strategies to maximal-loss minimization. Repeated subsampling can reduce outlier exposure while retaining rare examples, and slack variables allow up to K examples to be treated as outliers.

4. Robustness

  • The robustness setting assumes the number of outliers k is smaller than the number of rare examples m2.The paper motivates this boundary by noting that more outliers than rare examples preclude benefiting from the rare examples.Source: §4 · pp. 6–7

4.1. Sub-sampling with repetitions

  • Subsampling n examples independently with replacement from the original sample can avoid outliers while retaining enough rare examples when n is suitably chosen.For n = m/(100k) and m2 ≥ 1000 log(100) k, the stated bad-event probability is at most 0.03.Source: §4.1 · p. 7
  • With m ≥ 10k, the bad-event probability for the new sample is at most 0.01 + 0.99kn/m + e^-0.1nm2/m.The bad event is that the sample contains outliers or fewer than m2/2 rare examples.Source: §4.1 · p. 7

4.2. Slack variables

  • The ideal slack-variable formulation minimizes maximal loss over at least m−K examples, permitting up to K examples to be designated outliers.Relaxing binary slacks to [0,1] and using additive slack can yield a convex loss when the original loss is convex; projection constraints provide an efficient implementation.Source: §4.2 · p. 7

5. Experiments

The face-detection experiments compare FOL with SGD and AdaBoost, finding faster training convergence for FOL and lower test error than SGD. They also examine how FOL’s training and prediction behavior compares with AdaBoost.

Experimental setup

  • FOL uses SGD with Nesterov momentum as its online learner, applied to a LeNet-variant CNN with 710,642 weights and logistic loss.The experiments use batch size 64, ℓ2 regularization 0.0005, momentum 0.9, and a decaying learning rate.Source: §5 · pp. 7–8
  • The face-detection dataset uses 28,000 positive and 246,000 negative examples, filtered for correct labels by an initial vanilla-SGD network and split 9:1.The examples came from 30,000 tagged photos; face crops were scaled to 28×28 pixels.Source: §5 · pp. 7–8

Experiment 1: Convergence speed

  • FOL reaches zero training error after 30 epochs, while SGD remains at 0.1313% after 14,000 epochs.Both models were initialized with the same randomly selected weights.Source: §5 · p. 8, Figure 2 · p. 8
  • At 0.13% error, only 1 in 769 examples is informative; FOL focuses on the 984 informative examples in the 246,000-example training set.With batch size 64, SGD picks a useful sample only once every fifteen iterations, whereas FOL expects an average of 32 useful samples per iteration.Source: §5 · p. 8
  • 0.14% test error after 27 epochs for FOL, versus 0.35% for SGD after 14,000 epochs.Figure 2 compares train and test error as a function of iterations.Source: §5 · p. 8, Figure 2 · p. 8

Experiment 2: Comparison to AdaBoost

  • AdaBoost finds a consistent hypothesis after 20 epochs, while FOL takes 27 epochs; AdaBoost’s predictor is 10 times slower at prediction.FOL’s last hypothesis has zero training error; Figure 3 compares train error over epochs.Source: §5 · p. 8, Figure 3 · p. 8

A.1. Background

The background appendix introduces conditions and terminology for martingale concentration, then describes the EG algorithm and states an assumption for a bound.

A.1. Background

  • A Markovian sequence has each variable independent of earlier variables given its predecessor; a martingale difference sequence has conditional expectation zero.The stated conditional expectation is given B1 through Bt.Source: §A.1 · p. 10
  • The EG algorithm generates a sequence of vectors from z1 through zT, beginning with an all-ones vector and normalizing into the simplex.The passage attributes the algorithm name to Kivinen & Warmuth (1997).Source: §A.1 · p. 10
  • Lemma 5 assumes ηzt,i ≥ −1 for every t and i, and states a bound for every u in the simplex.Source: §A.1 · p. 10

A.2. Proof

The proof section establishes shorthand notation for per-example losses and distribution weights.

A.2. Proof

  • The proof writes ℓi(wt) for the loss of wt on training example i and omits the time index when context makes it clear.It likewise uses qi as shorthand for qt,i.Source: §A.2 · p. 10

A.2.1. THE w PLAYER

The proof appendix gives a condition for the w player, describes the p player’s EG-based update, and applies concentration bounds.

A.2.1. THE w PLAYER

  • Under the assumption C/T ≤ ϵ/8, the proof derives a statement for every sequence i1 through iT.Source: §A.2.1 · p. 10

A.2.2. THE p PLAYER

  • The p player maintains q in the simplex and mixes it half-and-half with the uniform distribution; its update uses EG on z.The passage states that this exploration mix affects convergence by a constant factor and permits an O(log(m)) update step.Source: §A.2.2 · p. 10

A.2.3. MEASURE CONCENTRATION

  • For measure concentration, the proof bounds martingale differences and applies Bernstein’s inequality, with k = Ω(log(m/δ)/ϵ).The stated condition on the sequence length is T ≥ 6m log(m/δ)/(ϵ/8)^2.Source: §A.2.3 · p. 11

B. Proofs of Lemmas in Section 3.1

The proofs bound ERM’s generalization error and analyze how the Perceptron’s updates depend on seeing typical and rare examples. They derive sample-size requirements for the rare-example setting and a mistake bound for the Perceptron.

C. Proof of Theorem 2

The proof constructs ERM by splitting the sample between two distributions and selecting a hypothesis consistent with both parts. It combines sample-count and VC-bound claims to establish the theorem’s error guarantee on both distributions.

  • The proof samples indices to divide the examples between D1 and D2, finds hypotheses consistent with the D1 sample, then selects one also consistent with the D2 sample.Source: C. Proof of Theorem 2 · p. 12
  • With probability at least 1−δ/3, both sample counts are at least half their expected counts, λ1m/2 and λ2m/2.Source: C. Proof of Theorem 2 · p. 12
  • A union bound over the three claims gives probability at least 1−δ that the ERM has error at most ε on both D1 and D2, under the theorem’s assumption.The proof uses Chernoff’s bound for sample counts and standard VC bounds for the other claims.Source: C. Proof of Theorem 2 · pp. 12–13

D. Proof of Theorem 3

The proof bounds the chance that the new sample contains an outlier and the chance that it contains too few rare examples. It combines these bounds with a union bound.

  • The chance that the sample contains an outlier is bounded by analyzing the probability that at least one outlier enters the sample.Source: D. Proof of Theorem 3 · p. 13
  • The chance that fewer than half the rare examples appear in the sample is at most exp(−0.1 nm2/m), by Chernoff’s bound.The expected number of rare examples in the sample is nm2/m.Source: D. Proof of Theorem 3 · p. 13
Loading 1602.01690v2…