PaperlayerView exact revision on arXiv

Source-linked AI summary

Logistic Regression: The Importance of Being Improper

Dylan J. Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, Karthik Sridharan

arXiv:1803.09349v2cs.LGstat.ML

TL;DR

Prior work showed that fast rates for logistic regression with linear predictors have poor dependence on predictor norm, and a lower bound ruled out improving that dependence in the proper setting. This paper uses mixability to build an improper online algorithm, then obtains improved rates for batch learning and broader classes. Its results also yield algorithms for bandit multiclass learning and boosting, while the boosting method remains suboptimal in its number of weak learners.

  • Problem

    Existing fast rates for logistic regression depend exponentially on predictor norm, and Hazan et al. (2014) showed this dependence cannot be improved for proper learning.

    Source: §1 · p. 2

  • Method

    The paper exploits 1-mixability of logistic loss with Vovk’s Aggregating Algorithm, using improper predictions that need not be linear in the instances.

    Source: §1 · p. 2

  • Results

    The improper online algorithm attains regret O(dlog(Bn)), with a doubly-exponential improvement in predictor-scale dependence, and the approach also yields a high-probability batch guarantee and improved general-class log-loss rates.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The improved norm dependence supports an Õ(√n) relative-mistake bound for online bandit multiclass learning and an adaptive online multiclass boosting algorithm with optimal sample complexity.

    Source: §1 · p. 2

    The adaptive boosting algorithm is suboptimal in the number of weak learners it uses, though no worse in this respect than previous adaptive algorithms.

    Source: §1 · p. 2

Abstract

from arXiv · show

Learning linear predictors with the logistic loss---both in stochastic and online settings---is a fundamental task in machine learning and statistics, with direct connections to classification and boosting. Existing "fast rates" for this setting exhibit exponential dependence on the predictor norm, and Hazan et al. (2014) showed that this is unfortunately unimprovable. Starting with the simple observation that the logistic loss is $1$-mixable, we design a new efficient improper learning algorithm for online logistic regression that circumvents the aforementioned lower bound with a regret bound exhibiting a doubly-exponential improvement in dependence on the predictor norm. This provides a positive resolution to a variant of the COLT 2012 open problem of McMahan and Streeter (2012) when improper learning is allowed. This improvement is obtained both in the online setting and, with some extra work, in the batch statistical setting with high probability. We also show that the improved dependence on predictor norm is near-optimal. Leveraging this improved dependency on the predictor norm yields the following applications: (a) we give algorithms for online bandit multiclass learning with the logistic loss with an $\tilde{O}(\sqrt{n})$ relative mistake bound across essentially all parameter ranges, thus providing a solution to the COLT 2009 open problem of Abernethy and Rakhlin (2009), and (b) we give an adaptive algorithm for online multiclass boosting with optimal sample complexity, thus partially resolving an open problem of Beygelzimer et al. (2015) and Jung et al. (2017). Finally, we give information-theoretic bounds on the optimal rates for improper logistic regression with general function classes, thereby characterizing the extent to which our improvement for linear classes extends to other parametric and even nonparametric settings.

1 Introduction

The paper uses logistic-loss mixability to obtain fast online rates through improper predictions, addressing the norm dependence that prior work showed could not be improved for proper learning. It also extends the approach to batch learning and other learning problems.

1 Introduction

  • The logistic loss is 1-mixable, enabling Vovk’s Aggregating Algorithm to obtain fast regret through predictions that need not be linear in the instances.MCMC methods can implement the algorithm in polynomial time in relevant parameters.Source: §1 · p. 2
  • Improper online logistic regression achieves regret O(dlog(Bn)), a doubly-exponential improvement in dependence on predictor scale B over the lower-bound-limited proper setting.This resolves a variant of McMahan and Streeter’s open problem when improper predictions are allowed.Source: §1 · p. 2
  • The approach also yields an online bandit multiclass algorithm with an Õ(√n) relative mistake bound and an adaptive multiclass boosting algorithm with optimal sample complexity.The bandit result applies across essentially all parameter ranges and addresses an open problem of Abernethy and Rakhlin (2009); the boosting result partially resolves open problems of Beygelzimer et al. (2015) and Jung et al. (2017).Source: §1 · p. 2
  • Converting the online algorithm gives a high-probability batch excess-risk guarantee of O(dlog(Bn)/n).The guarantee uses a modified “boosting the confidence” scheme; a lower bound shows the logarithmic dependence on B cannot be improved.Source: §1 · p. 2
  • For general function classes, the extent of improvement in predictor-range dependence is determined by sequential metric entropy, and the paper also obtains uniformly improved minimax log-loss rates.The general-class result uses sequential symmetrization and chaining arguments.Source: §1 · p. 2

1.1 Preliminaries

  • Mixability means that a mixed prediction can match or improve the exponential-loss performance of a distribution over predictions, supporting constant-in-round-count regret for finite classes.The paper uses the continuous version of this strategy for the logistic loss.Source: §1.1 · p. 4

2 Improved Rates for Online Logistic Regression

The section establishes that multiclass logistic loss is mixable and uses an Aggregating Algorithm to learn linear comparators with improper predictions. Its regret has logarithmic dependence on predictor scale, and that dependence is shown to be unimprovable for most values of the scale.

2 Improved Rates for Online Logistic Regression

  • The unweighted multiclass logistic loss is 1-mixable, which supplies the key condition for applying an Aggregating Algorithm to linear predictors.For weighted outcomes with total weight at most L, the loss is 1/L-mixable.Source: §2 · p. 4
  • The algorithm’s multiclass logistic regret is logarithmic in predictor scale B, circumventing the lower bound for proper learning and resolving a variant of McMahan and Streeter’s open problem.The bound is stated for the unweighted multiclass case and depends on the linear-algebraic dimension of the parameter set.Source: §2 · p. 5
  • The algorithm can be approximately implemented in time polynomial in d, n, B, R, K, and L, although the paper says this is not a practical algorithm.The predictions are bounded by log(K/µ), and smoothing provides this bound for applications while degrading performance as µ increases.Source: §2 · p. 5
  • A lower bound shows the log(B) factor in the regret guarantee cannot be improved for most values of B.The argument reduces to learning halfspaces with a margin in a Perceptron-type setting.Source: §2 · p. 5

3 Application: Bandit Multiclass Learning

This section applies the paper’s techniques to bandit multiclass learning, where efficient algorithms seek low regret against linear predictors with bandit feedback. OBAMA achieves a ˜O(√n) relative mistake bound for the multiclass logistic loss.

3 Application: Bandit Multiclass Learning

  • The task uses bandit feedback: after predicting a class, the learner receives only whether that prediction was correct.The goal is to minimize regret against linear predictors using a surrogate for 0-1 loss.Source: §3 · p. 6
  • ˜O(√n) relative mistake bound for the multiclass logistic loss makes OBAMA another solution to Abernethy and Rakhlin’s (2009) open problem.The problem called for an efficient algorithm with O(√n) regret.Source: §3 · p. 6
  • OBAMA improves on Newtron’s bound under the same setting and surrogate loss, while its relative mistake bound applies across a larger range of parameter values.The bounds for OBAMA and SOBA are incomparable because they measure comparator loss using different loss functions.Source: §3 · p. 6

4 Application: Online Multiclass Boosting

The paper applies improper logistic learning to adaptive online multiclass boosting. AdaBoost.OLM++ achieves optimal sample complexity, with improved dependence on the number of classes, while its weak-learner count remains a trade-off.

4 Application: Online Multiclass Boosting

  • The broader contribution is an adaptive online multiclass boosting algorithm with optimal sample complexity, extending improvements over AdaBoost.OL by Beygelzimer et al. (2015) and AdaBoost.OLM by Jung et al. (2017).The results also apply to the binary setting of Beygelzimer et al. (2015).Source: §4 · p. 7, §4.1 · p. 9

4.1 AdaBoost.OLM++

  • The method learns weights for a combination of weak learners by applying improper logistic learning, replacing the proper gradient-descent approach used in earlier work.The resulting improvement in regret leads to optimal sample complexity.Source: §4.1 · pp. 7–8
  • Using a multiclass-suited logistic loss yields an exponential improvement in the number of classes K for the number of weak learners required.The comparison is with the loss used by Jung et al. (2017).Source: §4.1 · p. 7
  • The algorithm combines weighted weak-learner scores, uses Hedge over the resulting experts, and supplies weak learners with cost matrices related to the loss gradient.The algorithm is called AdaBoost.OLM++; the weights are learned improperly for each weak learner.Source: §4.1 · p. 8
  • AdaBoost.OLM++ has a high-probability mistake bound that is adaptive to empirical weak-learner edges and holds even without the weak learning condition.The paper also relates empirical edges to the edge in the stated weak learning condition.Source: §4.1 · p. 8
  • The sample complexity improves dependence on K from linear to log(K) for OnlineMBBM and improves dependence on ε and γ for AdaBoost.OL, reaching the stated optimal bound.The comparison is to Jung et al. (2017) and their lower bound; the weak-learner count is weaker than for non-adaptive OnlineMBBM.Source: §4.1 · p. 9

5 High-Probability Online-to-Batch Conversion

The paper addresses high-probability batch excess-risk guarantees for logistic regression, where prior proper-learning lower bounds also apply. It adapts the online improper algorithm and obtains an O(dlog(Bn)/n) excess-risk bound.

5 High-Probability Online-to-Batch Conversion

  • The batch logistic-regression predictor achieves high-probability excess risk O(dlog(Bn)/n).The guarantee is for linear classes and uses n samples.Source: §5 · p. 9
  • A modified “boosting the confidence” scheme is needed for the high-probability guarantee, because deviations must scale at most as O(log(B)).The ordinary online-to-batch conversion gives the stated excess-risk bound in expectation; obtaining it with high probability is less straightforward.Source: §5 · p. 9
  • The conversion theorem turns an online log-loss algorithm predicting distributions into a batch predictor whose high-probability excess bound is essentially its average regret.The logistic-regression result follows from this more general conversion.Source: §5 · p. 9

6 Beyond Linear Classes

The section characterizes minimax regret for unweighted multiclass logistic loss over general predictor classes, using sequential covering numbers. Its bounds extend beyond linear predictors but are information-theoretic rather than algorithmic.

6 Beyond Linear Classes

  • Sequential-cover-based bounds characterize minimax regret for unweighted multiclass logistic loss over general predictor classes.The setting uses predictors f: X → R^K and an abstract instance space.Source: §6 · p. 10
  • Combining 1-mixability with the loss’s 2-Lipschitz property lets the analysis use both aggregation and sequential complexity measures.A pointwise-cover approach can fail when the pointwise covering number is infinite, so the section replaces it with sequential covering numbers.Source: §6 · pp. 10–11
  • The section’s general-function-class bounds overcome prior approaches that either ignore curvature and miss fast rates or pay e^B through exp-concavity.The bounds require boundedness to apply the minimax theorem, though boundedness does not explicitly enter the quantitative bounds.Source: §6 · p. 11
  • The logistic-loss rate avoids prior bounds’ O(B√n) or O(e^B) scaling on the sparse-linear example, obtaining O(log(B)) scaling instead.The section also notes that the minimax rate depends on scale through the capacity of the class, not explicitly on B.Source: §6 · p. 11
  • The general-function-class bounds can be lifted to high-probability guarantees for the i.i.d. batch setting, but remain information-theoretic rather than algorithmic.The paper describes this lift as generic.Source: §6 · pp. 10, 12

7 General Function Class Bounds for Log Loss

General-class log-loss rates are difficult to characterize, and existing bounds can be vacuous or loose for some classes. The paper derives a minimax bound that uniformly improves on the cited general-class rate, while presenting results only for the binary case.

7 General Function Class Bounds for Log Loss

  • Earlier general-class log-loss rates were limited by pointwise-cover bounds that can be vacuous and sequential-cover bounds known not to be tight for some classes.The paper identifies its new rates as a uniform improvement over Rakhlin and Sridharan (2015a).Source: §7 · p. 12
  • Mapping between logistic loss and log loss gives coarse rates that improve on the cited bound in low-complexity regimes but are worse for high-complexity classes.The mapping applies Theorem 6 to σ+ ○ F for log-loss prediction.Source: §7 · p. 12
  • The paper provides a minimax log-loss bound that uniformly improves on the rate of Rakhlin and Sridharan (2015a) for binary outcomes and extends in general to K > 2.Results are presented only for the binary case.Source: §7 · p. 12
  • The proof combines the style of Theorem 6 with technical observations from Rakhlin and Sridharan (2015a), and the stated bound uses L∞ covering numbers.The theorem is stated for F ⊆ [0,1]^X and δ ∈ (0, 1/2].Source: §7 · p. 12

8 Discussion

The discussion highlights improper learning based on Vovk’s Aggregating Algorithm as a route to improvements across applications. The core algorithm is polynomial-time implementable, but not practical.

8 Discussion

  • The authors identify the logistic loss’s 1-mixability as the observation behind improvements from improper learning based on Vovk’s Aggregating Algorithm.The discussion frames a truly efficient implementation as an open research question.Source: §8 · p. 13
  • The core algorithm is polynomial-time implementable but not practical; a practical version would need a modest polynomial dependence on dimension.The paper points to the Online Newton Step algorithm as precedent for a practically efficient alternative to an Aggregating Algorithm instance.Source: §8 · p. 13

A.1 Proofs from Section 2

These proofs establish the generalized multiclass logistic loss properties used in the regret analysis, then derive an online regret bound and a lower-bound construction. They also identify the regime in which that lower bound applies.

A.1 Proofs from Section 2

  • The generalized multiclass logistic loss is 2L-Lipschitz with respect to the ℓ∞ norm.The proof bounds the gradient’s ℓ1 norm by 2L and applies duality.Source: §A.1 · p. 15
  • The generalized multiclass log loss is 1/L-mixable, yielding an inequality for predictions averaged over distributions on the simplex and their softmax preimages.The proof uses exp-concavity and transfers the averaged prediction through the softmax mapping.Source: §A.1 · p. 16
  • Theorem 1’s proof bounds regret by integrating over a contracted neighborhood of the best comparator and choosing the contraction parameter to control the integral.The contraction contributes a Jacobian-volume term, while Lipschitzness bounds the loss change.Source: §A.1 · pp. 17–18
  • Choosing θ so that 1−θ = min{D_W/(B∑_{t=1}^n∥x_t∥⋆),1} yields a final bound containing log(1 ∨ B∑_{t=1}^n∥x_t∥⋆/D_W); for µ > 0, Lemma 3 handles the general case.Source: §A.1 · p. 18
  • The lower-bound construction builds margin-shattered trees by extending a one-dimensional threshold instance across coordinates; its stated scope is restricted to γ² ≥ d.The construction gives a margin of at least δ²/4 before rescaling, and the stated regime does not contradict the dimension-independent Perceptron bound.Source: §A.1 · pp. 19–21

A.2 OBAMA Algorithm and Proof of Theorem 3

This appendix section gives the OBAMA procedure and proves its multiclass bandit guarantee. The proof uses importance-weighted feedback and selects a smoothing level to bound expected mistakes.

A.2 OBAMA Algorithm and Proof of Theorem 3

  • OBAMA plays a label sampled from the smoothed softmax prediction and feeds the corresponding importance-weighted feedback to the logistic learner.The pseudocode initializes the learner with the decision set and smoothing parameter, then repeats prediction and feedback each round.Source: §A.2 · p. 21
  • Importance-weighted feedback has conditional expectation equal to the true-label indicator, so the expected logistic losses match the true-label losses.The feedback vector also has expected ℓ1 norm 1.Source: §A.2 · p. 21
  • The proof chooses between smoothing settings to bound expected mistakes, using that log loss upper-bounds the probability of a mistake.The supplied bound expressions include a term 2µn and an O(dK² exp(2BR) log(BRn dK + e)) expression for µ = 0.Source: §A.2 · p. 21

A.3 Pseudocode and Proofs from Section 4

This section gives the AdaBoost.OLM++ procedure and analyzes its logistic learners and boosting guarantee. The proof uses a concentration bound tailored to preserve the improvement from improper logistic regression.

A.3 Pseudocode and Proofs from Section 4

  • AdaBoost.OLM++ initializes weak learners alongside logistic learners with a specified decision set and smoothing parameter.The logistic learners use µ = 1/n.Source: §A.3 · p. 22
  • Freedman’s inequality supplies a high-probability concentration step in the boosting analysis, avoiding the extra √n term that a Hoeffding bound could introduce.The text says that term could spoil the improvement from improper logistic regression in this analysis.Source: §A.3 · p. 22
  • The proof bounds the regret of each logistic-regression instance and combines those bounds across the experts in its boosting analysis.The supplied intermediate bounds include O(N log(nlog(nK))) terms and a high-probability conclusion.Source: §A.3 · pp. 23–24
  • The analysis relates the weak-learning condition to the aggregate mistake bound through cost matrices and the losses of successive experts.The proof uses a lemma bounding changes in multiclass logistic loss when one logit is shifted.Source: §A.3 · pp. 24–25

A.4 Proof from Section 5

The section converts an online multiclass log-loss guarantee into an improper batch predictor with a high-probability excess-risk guarantee. Its construction combines independently trained predictors using an online convex optimization procedure.

A.4 Proof from Section 5

  • Theorem 9 states that an online multiclass algorithm with regret R(n) yields an improper predictor with an excess-risk bound holding with probability at least 1−δ.The displayed bound itself is not present in the supplied passage.Source: §A.4 · p. 26
  • The proof uses online-to-batch conversion and an excess-risk bound for each predictor, then combines these with smoothing and probability bounds.The text gives EWOO regret O(M log(n)) and a smoothed log-loss range bounded by log(K/µ).Source: §A.4 · pp. 26–27
  • The construction trains M predictors on disjoint sample sets, smooths their predictions, then combines them using EWOO over distributions on the predictors.The combination loss is the negative log of the mixture probability assigned to the observed label.Source: §A.4 · pp. 26–27

A.5 Details from Section 6

This section develops cover-based regret analysis for bounded or clipped predictors under log loss, using finite-class aggregation and tree covers. It also introduces a sequential covering number and combines regret terms into a bound with freely chosen δ and γ.

A.5 Details from Section 6

  • The finite-class logistic Aggregating Algorithm has a regret guarantee and predictions bounded by ∥z_hat_t∥∞ ≤ log(Kn).The supplied passage states the guarantee but omits its formula.Source: §A.5 · p. 28
  • Theorem 6’s proof conditions on a feature tree x and constructs centered classes Fv whose L2 covering complexity remains comparable to that of F while their radius is at most γ.The proof starts from a minimal γ-sequential cover of ℓ○F on x.Source: §A.5 · pp. 29–30
  • A cover of F on x yields a cover of each centered class Fv with size at most n times the original cover size.The construction uses a modified cover for each possible transition time in the path representation.Source: §A.5 · pp. 33–34
  • For any uniformly bounded collection of RK-valued K-ary trees, Lemma 11 supplies a deterministic competing strategy whose predictions satisfy ∥z_hat_t∥∞ ≤ log(Kn).The passage states that the strategy guarantees an inequality for every sequence, but omits the inequality’s formula.Source: §A.5 · p. 34

A.6 Details from Section 7

  • Section 7 defines N∞(α,F,x) as the smallest cover size for F by [0,1]-valued binary trees on a fixed X-valued binary tree x, and takes its supremum over x for N∞(α,F).Source: §A.6 · p. 36
  • Clipping predictors and learner outputs to [δ, 1 −δ] bounds the loss, and clipping does not increase the L∞ covering number.The proof introduces clipping to handle the log loss’s non-Lipschitzness.Source: §A.6 · p. 36
  • The constructed tree classes have covering number bounded by that of Fδ and L∞ radius at most γ, while providing a cover for each path and predictor.The construction uses a tree that agrees with the predictor along a covered path and with its cover tree elsewhere.Source: §A.6 · pp. 37–38
  • The proof controls the two terms with the Aggregating Algorithm over benchmark trees and a deterministic minimax strategy for each tree class.The strategies’ predictions are restricted to [δ, 1 −δ].Source: §A.6 · pp. 38–39
  • Theorem 7’s final log-loss minimax bound combines two terms, takes the supremum over x, and applies the clipping-cover result; δ and γ may be chosen freely.The supplied passages do not include the bound’s formula.Source: §A.6 · pp. 36, 38

B Efficient Implementation

The section gives a randomized polynomial-time implementation based on sampling the algorithm’s log-concave distribution. With high probability, the approximation adds at most O(1) loss over n rounds.

B Efficient Implementation

  • MCMC samples matrices from the algorithm’s log-concave distribution, and their predictions approximate the mixed prediction used by the algorithm.The approximation averages sampled sigmoid predictions and applies smoothing.Source: B Efficient Implementation · pp. 39–40
  • The implementation assumes access to a polynomial-query sampler for the log-concave density, but the resulting running-time bounds are too loose for practical use.The authors leave improving those bounds for future work.Source: B Efficient Implementation · pp. 39–40
  • With high probability, the sampled prediction adds at most 1/n loss per round, or O(1) additional loss over n rounds.The sampling parameter m is chosen to be polynomial in the problem parameters.Source: B Efficient Implementation · p. 40
  • Chernoff–Hoeffding bounds and a union bound give an approximation error of at most ε when m = ˜Ω(1/ε^2), with high probability.The coordinate-wise bound combines with the triangle inequality to bound the distance from the target distribution.Source: B Efficient Implementation · p. 40

Related papers

Loading 1803.09349v2…