PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic AUC Maximization with Deep Neural Networks

Mingrui Liu, Zhuoning Yuan, Yiming Ying, Tianbao Yang

arXiv:1908.10831v5cs.LGmath.OCstat.ML

TL;DR

Stochastic AUC maximization is suited to imbalanced classification, but existing stochastic methods considered linear predictors. This paper uses a PL-based saddle-point approach to develop stochastic algorithms for deep neural networks; it reports an O(1/ϵ) rate for PPD-SG versus slower comparison rates and faster convergence than other baselines on benchmark datasets.

  • Problem

    Existing stochastic AUC maximization methods considered linear predictors, while AUC is described as more suitable than misclassification rate and its surrogate for imbalanced data.

    Source: §1 · p. 1

  • Method

    The paper uses a squared-surrogate saddle-point formulation for deep neural networks and develops stochastic primal-dual algorithms under the PL condition.

    Source: §1 · p. 2

  • Results

    O(1/ϵ) for PPD-SG, versus O(1/ϵ^3) and O(n/ϵ) for the cited comparison under the PL condition; the algorithms also converge faster than other baselines on several benchmark datasets.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The work reports state-of-the-art iteration complexity for non-convex concave min-max problems while extending stochastic AUC maximization to deep neural networks.

    Source: §1 · p. 2, §6 · p. 9

    The analysis assumes a PL condition on the objective; establishing that condition for neural networks is not the paper’s main focus, though an example is provided for a one-hidden-layer network.

    Source: §3 · pp. 4–5

Abstract

from arXiv · show

Stochastic AUC maximization has garnered an increasing interest due to better fit to imbalanced data classification. However, existing works are limited to stochastic AUC maximization with a linear predictive model, which restricts its predictive power when dealing with extremely complex data. In this paper, we consider stochastic AUC maximization problem with a deep neural network as the predictive model. Building on the saddle point reformulation of a surrogated loss of AUC, the problem can be cast into a {\it non-convex concave} min-max problem. The main contribution made in this paper is to make stochastic AUC maximization more practical for deep neural networks and big data with theoretical insights as well. In particular, we propose to explore Polyak-\L{}ojasiewicz (PL) condition that has been proved and observed in deep learning, which enables us to develop new stochastic algorithms with even faster convergence rate and more practical step size scheme. An AdaGrad-style algorithm is also analyzed under the PL condition with adaptive convergence rate. Our experimental results demonstrate the effectiveness of the proposed algorithms.

1 INTRODUCTION

The introduction motivates stochastic AUC maximization for imbalanced data and asks how to give it provable guarantees with deep neural networks. It proposes PL-based stochastic primal-dual methods, reports faster complexity and benchmark performance, and identifies the work as the first to apply the PL condition to this setting.

1 INTRODUCTION

  • Existing stochastic AUC methods considered linear predictive models, motivating the question of provable stochastic algorithms with deep neural networks.The introduction notes that AUC is more suitable than misclassification rate and its surrogate for imbalanced data, where majority-class data can dominate the usual formulation.Source: §1 · pp. 1–2
  • The authors cast squared-surrogate AUC maximization with a deep neural network as a non-convex concave min-max stochastic optimization problem.They build on the saddle-point reformulation and the inexact proximal point framework.Source: §1 · p. 2
  • The paper leverages the PL condition, which has been proved for some neural-network settings and observed in practice, to develop faster stochastic algorithms.The authors identify adapting this condition from minimization to the AUC min-max problem as a non-trivial theoretical challenge.Source: §1 · p. 2
  • PPD-SG achieves O(1/ϵ), faster than O(1/ϵ^3) and O(n/ϵ) from applying Rafique et al. (2018) under the PL condition.The paper also describes its results as state-of-the-art in iteration complexity for non-convex concave min-max problems.Source: §1 · p. 2
  • PPD-Adagrad has better adaptive complexity when cumulative stochastic-gradient growth is slow.The paper presents it as the first stochastic AdaGrad-style algorithm with adaptive convergence established for non-convex concave min-max problems.Source: §1 · p. 2
  • Experiments on several large-scale benchmark datasets show that the proposed algorithms outperform other baselines.The paper describes the results as demonstrating the algorithms’ effectiveness.Source: §1 · p. 2

2 RELATED WORK

Prior stochastic AUC methods use linear predictors, while related non-convex min-max work addresses different assumptions or algorithmic settings. The paper positions its contribution at the intersection of stochastic AUC maximization with deep networks and the PL condition.

Stochastic AUC Maximization

  • Prior stochastic AUC primal-dual methods use a saddle-point reformulation, but the cited methods consider only linear models and therefore convex objectives.Earlier approaches include buffer-based sampling, maintained data statistics, and primal-dual stochastic algorithms.Source: §2 · p. 3

Non-Convex Min-max Optimization

  • The paper differs from related non-convex min-max work by using the PL condition for the outer minimization and designing stochastic rather than deterministic algorithms.The comparison is with work applying PL to the inner maximization problem and deterministic gradient descent-ascent.Source: §2 · p. 3

Leveraging PL Condition for Minimization

  • PL-based stochastic optimization methods for minimization do not directly apply to the AUC min-max formulation; the cited AUC method using quadratic growth relies on convexity.The paper notes that this convexity does not hold for AUC maximization with a deep neural network.Source: §2 · p. 3
  • Prior deep-learning work proves or implies PL-like conditions in specified neural-network settings, including sufficiently wide two-layer and overparameterized deep ReLU networks.The cited examples concern a global optimum in a ball around initialization or a global minimum around a random initial solution.Source: §2 · pp. 3–4

3 PRELIMINARIES AND NOTATIONS

This section formulates AUC maximization using a squared surrogate and a nonlinear predictor, then relates its saddle-point form to assumptions and convergence analysis. It also describes the stochastic formulation’s sampling advantage and a warmup method whose PL-based rate motivates faster algorithms.

3 PRELIMINARIES AND NOTATIONS

  • AUC is the probability that a positive example scores at least as high as a negative one; the formulation uses squared loss as a surrogate and permits nonlinear predictors such as neural networks.Earlier AUC work assumed a linear predictor, whereas this section allows a general model parameterized by w.Source: §3 · p. 4
  • Proposition 1 converts the original optimization problem into an equivalent saddle-point problem.The stated formulation expresses the objective as an expectation of F over the data distribution.Source: §3 · p. 4
  • The min-max formulation supports updates from one example or a mini-batch without carefully sampling both positive and negative examples; it applies to batch and online learning.In batch learning, p is the ratio of positive training examples and the expectation becomes an average over the n individual functions.Source: §3 · p. 4
  • The analysis assumes a PL condition on φ, smoothness, bounded conditional score variances, scores in [0, 1], and a bounded initial objective gap.The authors relate the PL condition on φ to a PL condition on P(w); they note that proving the latter for a neural network is not the paper’s main focus and provide a one-hidden-layer example in the appendix.Source: §3 · pp. 4–5
  • The warmup applies Rafique et al. (2018) to the online setting and adds bounded primal and dual domains, which should not affect the solution when their radii are sufficiently large.The cited analysis requires bounded domains for both variables.Source: §3 · p. 5
  • Under the PL condition, the warmup’s smooth-objective guarantee gives complexity eO(1/(µ^3ϵ^3)) for objective error at most ϵ, prompting the open question of reaching O(1/ϵ).The discussion says exact inner maximization over α is non-trivial, so simply maximizing first and then applying SGD is not viable.Source: §3 · p. 5

4 ALGORITHMS AND THEORETICAL ANALYSIS

This section presents two primal-dual algorithms in a proximal-point framework with theoretical convergence results. PPD-SG has better iteration complexity than Algorithm 1 under the stated comparison.

4.1 PROXIMAL PRIMAL-DUAL STOCHASTIC GRADIENT

  • PPD-SG uses nested loops: stochastic primal-dual updates approximately solve regularized min-max problems, while outer loops update the reference point and learning rate.It uses geometrically decaying step sizes and estimates the optimal dual variable using a small number of samples.Source: §4.1 · p. 6
  • eO(1/(µ²ϵ)) improves on Algorithm 1’s eO(1/(µ³ϵ³)) complexity, improving dependence on both ϵ and µ.The comparison is stated up to logarithmic factors.Source: §4.1 · p. 7

4.2 PROXIMAL PRIMAL-DUAL ADAGRAD

  • PPD-Adagrad changes the inner-loop updates to AdaGrad-style adaptive updates and has adaptive iteration complexity when cumulative stochastic-gradient growth is slow.When α < 1/2, its iteration count is below the bound in Theorem 2.Source: §4.2 · p. 7

4.3 EXTENSIONS

  • For online learning with unknown positive-class ratio p, unbiased estimates of p and p(1 − p) replace those quantities in the objective and stochastic gradients.The estimates are updated during optimization.Source: §4.3 · p. 8
  • The binary-class formulation extends to c classes using c normalized scoring functions, with deep networks able to share lower layers and use class-specific final connections.The algorithms can be modified for multiple class pairs, with an additional sampling level over pairs.Source: §4.3 · p. 8

5 EXPERIMENTAL RESULTS

The experiments compare the proposed algorithms with primal-dual and cross-entropy baselines on four image datasets. AUC-based methods are mostly more advantageous than SGD in imbalanced settings.

5 EXPERIMENTAL RESULTS

  • PPD-SG and PPD-AdaGrad are compared with PGA, OAUC, and cross-entropy SGD using a 20-layer ResNet.PGA and OAUC address the same min-max formulation; SGD provides a comparison with cross-entropy minimization.Source: §5 · p. 8
  • The proposed methods use stagewise step sizes and a batch size of 128, reduced to 32 for STL10.The initial step size and stage length are tuned separately for each algorithm.Source: §5 · p. 8
  • The comparisons use Cat&Dog, CIFAR10, CIFAR100, and STL10, with multiple binary classification tasks at varying negative-to-positive ratios.Cat&Dog uses an 80:20 training/testing split; training/validation splits are also reported for all four datasets.Source: §5 · p. 9
  • In imbalanced settings, AUC-maximization methods are more advantageous than SGD in most cases, and PPD-SG and PPD-AdaGrad are mostly better than the other baselines.PPD-AdaGrad is faster than PPD-SG in some cases; SGD performs better in balanced settings on Cat&Dog and CIFAR10.Source: §5 · p. 9, Figure 1 · p. 9

6 CONCLUSION

The paper studies stochastic AUC maximization with a deep neural network and proposes algorithms analyzed using the PL condition. Experiments on benchmark datasets indicate faster convergence than other baselines.

6 CONCLUSION

  • The paper considers stochastic AUC maximization with a deep neural network as the predictive model.It builds on a saddle-point reformulation and the PL condition to propose two algorithms with state-of-the-art complexities.Source: §6 · p. 9
  • Experiments on several benchmark datasets indicate that the proposed algorithms converge faster than other baselines.Source: §6 · p. 9
  • The paper suggests extending its analysis techniques to other problems with min-max formulations.Source: §6 · p. 9

A.1 PROOF OF PROPOSITION 1

The proof excerpt reduces its claim to a displayed expression and states optimal values for three auxiliary variables.

A.1 PROOF OF PROPOSITION 1

  • The proof states that it suffices to establish the displayed expression.Source: §A.1 · p. 12
  • The displayed expression includes the squared difference between the positive- and negative-class expected scores.Source: §A.1 · p. 12
  • The stated optimal values are a* = E[h(w; x)|y = 1], b = E[h(w; x')|y' = −1], and α* = E[h(w; x')|y' = −1] − E[h(w; x)|y = 1].Source: §A.1 · p. 13

A.2 PROOF OF LEMMA 2

The proof excerpt defines an auxiliary maximizer and presents an inequality involving the primal-dual objective. It also bounds terms involving the auxiliary variable and iterate changes.

A.2 PROOF OF LEMMA 2

  • The proof defines α*,k as a maximizer of f(v̄k, α) and groups v and α into the vector u.Source: §A.2 · p. 13
  • An inequality compares the min-max objective with its value at sk and ᾱk, including a proximal term scaled by 1/(2γ).The excerpt attributes part of its justification to the standard analysis of the primal-dual stochastic gradient method.Source: §A.2 · p. 13
  • The proof bounds the squared error of ᾱk−1 using a variance-related term and the squared change between consecutive v̄ iterates.The bound also uses Lipschitz continuity of the difference between negative- and positive-class expected scores.Source: §A.2 · p. 14

A.3 PROOF OF THEOREM 2

The proof uses smoothness and the PL property to derive the theorem’s iteration and sample-complexity bounds.

A.3 PROOF OF THEOREM 2

  • The proof uses smoothness of the proximal objective and a strongly convex proximal subproblem.It sets the subproblem smoothness to L̂ = L + γ⁻¹ and defines its minimizer s_k.Source: §A.3 · pp. 14–15
  • The proof invokes the PL property to bound the objective gap using the gradient norm.It defines the gap as Δ_k = φ( v̄_k ) − φ(v*).Source: §A.3 · p. 15
  • The argument sets the inner iteration count T_k using a bound involving L̃.The stated choice is T_k = max(2, 16L̃²).Source: §A.3 · p. 16
  • The proof concludes by specifying total iteration complexity and a required sample count.The supplied passages introduce these quantities without giving their expressions.Source: §A.3 · p. 16

A.4 PROOF OF LEMMA 3

The proof combines conditional-expectation arguments with variance and stopping-time bounds.

A.4 PROOF OF LEMMA 3

  • The proof takes conditional expectations over the filtration generated up to v̄_{k−1} and uses the tower property.It applies this step to the bound obtained from equation (17).Source: §A.4 · p. 18
  • The proof treats T_k as an almost surely bounded stopping time.It then invokes a stopping-time argument.Source: §A.4 · p. 19
  • The argument uses that stochastic-gradient variance is no greater than its second moment.The passage says this supports a similar bound for term I.Source: §A.4 · p. 19

A.5 PROOF OF THEOREM 3

The appendix proves convergence results under the PL condition, gives a neural-network example, and reports additional dataset and pretraining experiments.

A.5 PROOF OF THEOREM 3

  • The proof combines smoothness, strong convexity of a proximal objective, and the PL property to derive iteration and sample complexities.The supplied proof passages introduce the total iteration complexity and required sample count but do not expose their full expressions.Source: §A.5 · pp. 19–21

A.6 PROOF OF LEMMA 1

  • Strong convexity in (a, b), with modulus 2 min(p, 1 − p), is used to establish the PL condition.The proof then relates the objective gap to the gradient norm.Source: §A.6 · pp. 21–22

A.7 AN EXAMPLE THAT SATISFIES PL CONDITION

  • The example analyzes a one-hidden-layer Leaky ReLU network under zero conditional class means; a zero-mean Gaussian input with nondegenerate covariance gives μ > 0.The theorem passage states the activation and conditional-mean condition; the remark gives the Gaussian case.Source: §A.7 · p. 22

A.8 DATASET PREPARATION

  • For CIFAR10 and STL10, the first five classes are negative and the last five positive; CIFAR100 uses the first 50 versus the last 50.Removing 90%, 80%, or 60% of negative training samples yields 91/9, 83/17, or 71/29 ratios, respectively; test data remain unchanged.Source: §A.8 · p. 23

A.9 MORE EXPERIMENTS

  • Pretraining followed by PPD-SG improves convergence and achieves better AUC in most cases.The model is first trained with SGD for up to 2,000 iterations at initial step size 0.1; Figure 2 compares testing AUC on four datasets.Source: §A.9 · p. 23, Figure 2 · p. 24

A.10 ADDITIONAL EXPERIMENTS WITH DIFFERENT LABELING ORDER

  • With randomly assigned positive and negative classes and 20:1 or 10:1 training imbalance, PPD-Adagrad and PPD-SG converge faster than other baselines.Figure 3 compares testing AUC across Cat&Dog, CIFAR10, CIFAR100, and STL10.Source: §A.10 · p. 23, Figure 3 · p. 24

Related papers

Loading 1908.10831v5…