Sharper bounds for uniformly stable algorithms

Olivier Bousquet; Yegor Klochkov; Nikita Zhivotovskiy

Source-linked AI summary

Sharper bounds for uniformly stable algorithms

Olivier Bousquet, Yegor Klochkov, Nikita Zhivotovskiy

arXiv:1910.07833v2Oct 17, 2019cs.LGmath.PRstat.ML

TL;DR

The paper asks whether generalization bounds for uniformly stable algorithms can be sharpened and matched by high-probability lower bounds. It develops a moment-based concentration approach, removes an unnecessary logarithmic term, and proves near-tight lower bounds subject to additional structure.

Problem
Existing high-probability upper bounds for uniformly stable algorithms were known to be sub-optimal in some regimes, motivating sharper bounds and corresponding lower bounds.
Method
The paper develops a moment bound from a concentration inequality for weakly correlated random variables, using a simpler sample-splitting-inspired analysis and standard moment inequalities.
Results
The resulting bound removes the unnecessary nγ(log n)^2 term, implies the earlier sub-gaussian bound, and strengthens both recent results while matching lower bounds up to a logarithmic factor.
Takeaways & Limitations
The moment bound is sharp up to logarithmic factors unless additional properties of the corresponding random variables are exploited.
Takeaways & Limitations
The lower bounds do not completely establish optimality for uniformly stable algorithms, and tightness can depend on additional properties beyond the theorem’s stated parameters.

Abstract

from arXiv · show

Deriving generalization bounds for stable algorithms is a classical question in learning theory taking its roots in the early works by Vapnik and Chervonenkis (1974) and Rogers and Wagner (1978). In a series of recent breakthrough papers by Feldman and Vondrak (2018, 2019), it was shown that the best known high probability upper bounds for uniformly stable learning algorithms due to Bousquet and Elisseef (2002) are sub-optimal in some natural regimes. To do so, they proved two generalization bounds that significantly outperform the simple generalization bound of Bousquet and Elisseef (2002). Feldman and Vondrak also asked if it is possible to provide sharper bounds and prove corresponding high probability lower bounds. This paper is devoted to these questions: firstly, inspired by the original arguments of Feldman and Vondrak (2019), we provide a short proof of the moment bound that implies the generalization bound stronger than both recent results (Feldman and Vondrak, 2018, 2019). Secondly, we prove general lower bounds, showing that our moment bound is sharp (up to a logarithmic factor) unless some additional properties of the corresponding random variables are used. Our main probabilistic result is a general concentration inequality for weakly correlated random variables, which may be of independent interest.

1. Introduction

The paper studies high-probability generalization bounds for uniformly stable learning algorithms, motivated by estimating risk from training data without additional data. It strengthens recent bounds and establishes near-matching lower-bound evidence.

1. Introduction: Accurate risk estimation from no or limited additional data remains a fundamental statistical learning question.Empirical risk is the natural estimator when no test set is available.
1. Introduction: Uniform stability bounds the error between true risk R(A_S) and empirical risk R_emp(A_S) using sensitivity to changes in the training sample.The framework includes algorithms whose outputs change little when one sample point is replaced.
1. Introduction: The classical Bousquet–Elisseef bound can fail to guarantee convergence outside the regime γ ≲ 1/n.Its tightness and convergence behavior are limited when the stability parameter is larger.
1. Introduction: Feldman and Vondrak’s later bound captures both sub-gaussian and sub-exponential regimes, including optimal-rate convergence when γ ∼ 1/n up to logarithmic factors.The bound contains two distinct types of terms and improves on the earlier result in relevant regimes.
1. Introduction: The paper’s Theorem 4 removes the unnecessary nγ(log n)^2 term, implies the earlier sub-gaussian bound, and is supported by lower bounds that are tight up to logarithmic factors.The lower-bound result applies unless additional properties of the corresponding random variables are used.

2. Preliminaries

The preliminaries recast mixed tail bounds through moment norms and collect concentration inequalities for independent random variables. These tools motivate the paper’s use of moment bounds as a tractable route to generalization and lower-bound results.

2. Preliminaries: The preliminaries define conditional Lp norms and emphasize that an almost-sure conditional bound is stronger than its unconditional counterpart.These conditional norms are applied to functions of independent variables and independent copies of coordinates.
2. Preliminaries: Mixed sub-gaussian and sub-exponential tail bounds are equivalent, up to constants, to moment bounds of the form √pa + pb.This equivalence makes moment norms a convenient alternative for studying deviations.
2. Preliminaries: Moment inequalities are useful because they are often easier to manipulate than deviation inequalities, especially for proving lower bounds.The paper uses this perspective as a basis for its subsequent probabilistic arguments.
2. Preliminaries: McDiarmid’s bounded-differences inequality yields a moment bound for functions of independent variables, including the moment form of Hoeffding’s inequality for bounded centered sums.The resulting tools control deviations through coordinate-wise sensitivity.
2. Preliminaries: The Marcinkiewicz–Zygmund inequality provides a complementary moment bound for sums of independent centered random variables with finite p-th moments.It is introduced as one of the main tools used in the paper.

3. Upper Bounds

The paper develops a moment inequality for sums of weakly correlated functions of independent variables and applies it to uniformly stable algorithms. This yields a sharper generalization bound while avoiding logarithmic losses in earlier analyses.

3.1. A Moment Bound for Sums: A general moment inequality for sums of functions of independent variables is the section’s main probabilistic result.The theorem assumes boundedness and bounded differences away from each function’s distinguished variable.
3.1. A Moment Bound for Sums: The proof uses nested binary partitions, telescopic sums, conditional bounded differences, and the Marcinkiewicz–Zygmund inequality.This replaces the recursive structure, truncation, and union-bound steps used in related analyses.
3.1. A Moment Bound for Sums: Theorem 4 supports a version where E[gi|Zi] is sub-Gaussian, although the paper focuses on a simplified bounded form.The stated result is presented for the simplified setting for clarity.
3.2. Consequences for Uniformly Stable Algorithms: Under uniform stability and loss bounded by L, Corollary 8 gives a high-probability generalization bound for any δ ∈(0, 1).The construction uses functions gi bounded by L and with bounded differences parameter β = 2γ away from the i-th variable.
3.2. Consequences for Uniformly Stable Algorithms: The resulting bound improves Feldman and Vondrák’s upper bound by removing the unnecessary nγ log^2 n term.The paper also states that Theorem 4 almost recovers the sub-gaussian bound.

4. Lower Bounds

The paper constructs lower bounds showing that Theorem 4 is tight up to a logarithmic factor in several regimes, while leaving full optimality for uniformly stable algorithms unresolved.

Lower-bound tightness: The bound of Theorem 4 is tight with respect to M, β, n, and log 1/δ up to a logarithmic factor in some regimes.The authors state that this establishes the strongest conclusion available when the upper bound uses only these parameters.
Remaining gap: These lower bounds do not fully establish the optimality of the uniformly stable learning risk bound because Theorem 4 does not use the condition |gi| ≤ L.The authors leave open whether stronger lower bounds can be obtained for uniformly stable algorithms themselves.
Lower-bound tightness: The lower bound matches Theorem 4 up to the logarithmic factor when p ≤ n, forcing sub-exponential behavior unless additional properties of the functions gi are used.The corresponding moment lower bounds also imply deviation lower bounds for δ in a specified range.
Lower-bound tightness: For p > n, the example gi = LZi shows that the nL term in the moment bound is best possible.Here Zi are i.i.d. Rademacher signs, corresponding to an algorithm that always outputs the same classifier.

5. Discussions

The discussion explains that weak correlation yields sharper moment bounds, nearly recovers a sub-Gaussian result, and identifies remaining limitations and extensions to interpolation algorithms.

A Better Second Moment Bound: Weak correlation among the gi functions enables a tight upper bound on the second moment.The authors contrast this with earlier analyses that did not exploit the small correlations between different gi.
A Better Second Moment Bound: The second moment bound improves on the earlier result by using M instead of L.The discussion identifies this as a direct improvement in the bound’s parameter dependence.
Recovering the sub-Gaussian bound: Theorem 4 is strong enough to almost recover Feldman and Vondrak’s sub-Gaussian bound without discarding its relevance because of additional log n factors.The authors emphasize the sub-Gaussian form and note that the bound depends only on δ tails in the comparison.
Interpolation Algorithms: For interpolation algorithms, the empirical risk is zero, so the paper proposes a leave-one-out risk estimator but notes that realistic stability extensions require more work.The modified analysis would also exclude cases where the test point belongs to the training set and may require hypothesis stability.

6. Open Questions

The paper identifies open questions about tightening its upper and lower bounds for uniformly stable algorithms and extending the analysis to additional settings.

6. Open Questions: Removing the logarithmic factor from the upper bound for p > 2 remains an open question.The second moment already avoids this factor, motivating the possibility of removing it more generally.
6. Open Questions: A matching high-probability lower bound for uniformly bounded functions |g_i| ≤ L remains to be found.The paper notes that its example can have L much larger than M, leaving the bounded-function case unresolved.
6. Open Questions: The paper’s upper and lower bounds are almost matching, but their exact tightness is not fully settled.The authors describe the current results as progress toward narrowing the exact behavior of the true–empirical risk difference.
6. Open Questions: Extensions to unbounded losses and improved stability bounds for learning algorithms are suggested as directions for future work.Known unbounded-case extensions may support generalization bounds for unbounded losses, while newer stability results may benefit from the presented techniques.

Appendix A. Proof of Lemma 1

This appendix derives a moment bound for a shifted positive-tail random variable and converts it into the required probability bound using Markov’s inequality.

Appendix A. Proof of Lemma 1: The random variable (|Y| − a − b)+ satisfies the cited concentration theorem’s requirements, yielding moment bounds for every integer p ≥ 1.The construction isolates the positive tail beyond a + b before applying the theorem.
Appendix A. Proof of Lemma 1: The full Lp norm is bounded by the tail term’s L2p norm plus a + b.This follows from the triangle inequality for the decomposition into the shifted tail and the threshold terms.
Appendix A. Proof of Lemma 1: Markov’s inequality converts the moment estimate into a high-probability bound for any δ ∈ (0, 1).The proof then selects the relevant exponent so that the unwanted exponent disappears.

Appendix B. Proof of Proposition 9

The proof of Proposition 9 combines moment facts for weighted Rademacher sums with conditional properties of the constructed variables and association inequalities.

Appendix B. Proof of Proposition 9: Hitczenko’s lemma characterizes weighted Rademacher-sum moments up to a multiplicative constant.The lemma applies to non-increasing non-negative weights and independent Rademacher signs.
Appendix B. Proof of Proposition 9: Chebyshev’s association inequality compares expectations of products of non-decreasing functions of the same random variable.The proof invokes it for powers of x and M + βx/2 on the non-negative half-line.
Appendix B. Proof of Proposition 9: The proof combines these estimates through the triangle inequality and a decomposition involving M S+ and β S2/2.The decomposition supplies a lower bound on the corresponding Lp norm.
Appendix B. Proof of Proposition 9: Symmetry and the weighted Rademacher moment lemma provide the needed control for the relevant moment range.The argument applies the symmetry of S together with Lemma 10 for p ≤ n.
Appendix B. Proof of Proposition 9: The construction yields a lower bound after establishing the conditional means and bounded-difference properties of each g_i.Conditioning gives E[g_i | Z[n]\{i}] = 0 and E[g_i | Z_i] = M, while g_i is β-bounded in the other variables.

Appendix C. Proof of the Lower Tail (14)

The lower-tail proof uses Paley–Zygmund and Rademacher-chaos moment bounds to establish a probability lower bound over a specified range of p and δ.

Appendix C. Proof of the Lower Tail (14): The lower bound implies the desired tail estimate after applying Paley–Zygmund to the relevant polynomial quantity.The argument defines the function f and derives the lower-tail probability from its moments.
Appendix C. Proof of the Lower Tail (14): Latała’s Rademacher-chaos bound provides a matching upper bound without the logarithmic factor for κ ≤ p ≤ n.A moment version of Hanson–Wright is offered as an alternative when only the upper bound is needed.
Appendix C. Proof of the Lower Tail (14): The proof controls the chaos terms using a symmetric zero-diagonal matrix and the non-decreasing rearrangement of associated coefficients.The matrix-based estimate is applied to the quantities introduced in the preceding steps.
Appendix C. Proof of the Lower Tail (14): For κ ≤ p ≤ n/2, the proof obtains ∥f∥p ≥ c∥f∥2p for an absolute constant c ≤ 1.This moment comparison is then used in the probability calculation.
Appendix C. Proof of the Lower Tail (14): Choosing p = κ ∨ pδ links the moment order to δ, under the condition δ ≥ e^{−(log 2c−2)−1n}.The choice ensures pδ ≤ n and sets the relevant power of c2/2 equal to δ.