Variance-based regularization with convex objectives

John Duchi; Hongseok Namkoong

Source-linked AI summary

Variance-based regularization with convex objectives

John Duchi, Hongseok Namkoong

arXiv:1610.02581v3Oct 8, 2016stat.MLmath.ST

TL;DR

The paper addresses how to trade approximation error against estimation error while retaining computational tractability. It constructs a convex variance surrogate from distributionally robust optimization and empirical likelihood, then proves finite-sample and asymptotic guarantees. The robust estimator can achieve faster rates than ERM in some scenarios and improves performance on harder classification instances, although it may be inefficient in correctly specified models.

Problem
Variance-regularized risk can balance approximation and estimation error, but its non-convexity limits computationally tractable use even for convex losses.
Method
The paper replaces variance regularization with a distributionally robust empirical-likelihood formulation that is convex whenever the loss is convex.
Results
The robust estimator provides high-probability guarantees and can converge at O(log n/n), compared with O(1/√n) for ERM in an explicit example.
Takeaways & Limitations
Robust regularization provides a practical tuning parameter ρ for trading variance or uniform performance against absolute performance, especially on harder instances.
Takeaways & Limitations
The robust procedure cannot uniformly dominate ERM and may be inefficient in correctly specified classical estimation problems.

Abstract

from arXiv · show

We develop an approach to risk minimization and stochastic optimization that provides a convex surrogate for variance, allowing near-optimal and computationally efficient trading between approximation and estimation error. Our approach builds off of techniques for distributionally robust optimization and Owen's empirical likelihood, and we provide a number of finite-sample and asymptotic results characterizing the theoretical performance of the estimator. In particular, we show that our procedure comes with certificates of optimality, achieving (in some scenarios) faster rates of convergence than empirical risk minimization by virtue of automatically balancing bias and variance. We give corroborating empirical evidence showing that in practice, the estimator indeed trades between variance and absolute performance on a training sample, improving out-of-sample (test) performance over standard empirical risk minimization for a number of classification problems.

1 Introduction

The paper introduces a convex distributionally robust surrogate for variance-regularized risk minimization, designed to trade approximation error against estimation error. It establishes theoretical guarantees, including faster convergence in some settings, and reports empirical improvements over ERM.

Motivation and approach: Variance-corrected empirical risk can balance approximation and estimation error, but is generally non-convex and computationally difficult.The proposed approach uses distributionally robust optimization and Owen’s empirical likelihood to obtain a tractable surrogate.
Motivation and approach: The robust empirical risk is convex in θ whenever the loss is convex, regardless of the robustness radius ρ.This follows because the robust risk is the supremum of convex functions.
Theoretical guarantees: For bounded losses, the robust risk approximates the variance-regularized quantity, with an error term ε_n(θ) that is nonpositive and O_P(1/n) uniformly in θ.When the loss has sufficiently large variance, ε_n is zero with high probability.
Theoretical guarantees: Under suitable conditions, the robust estimator has excess risk essentially O(ρ/n), without requiring the Bernstein-type variance condition often used for ERM.An explicit example obtains O(log n/n) convergence versus O(1/√n) for ERM.
Limitations and empirical evidence: The method does not uniformly dominate ERM: it can be inefficient in correctly specified classical models, and excessive variance penalization can slow convergence.Its asymptotic analysis characterizes an efficiency loss relative to empirical expectation minimization.

2 Variance Expansion

The paper shows that robust regularization approximates empirical risk plus a variance-related penalty while preserving convexity for convex losses. It develops expansion and complexity results supporting this approximation across single-variable and function-class settings.

Convex surrogate: The robust formulation is convex whenever the loss is convex because it is the supremum of a family of convex functions.This makes the robust objective a computationally tractable surrogate for variance regularization.
Motivation: Variance regularization can be non-convex even when the loss is convex, producing multiple local minima and poor behavior at extreme parameter values.The absolute-loss example illustrates this obstruction directly.
Conditions: The results rely on boundedness or sufficient-variance assumptions, with later arguments relaxing boundedness through the exact expansion characterization.The paper also states a high-probability uniform expansion under a variance lower bound.
Variance expansion: For bounded losses, the robustly regularized risk approximates empirical risk plus a standard-deviation term and provides a convex approximation to exact variance regularization.The paper uses this variance expansion to derive guarantees for stochastic risk minimization.
Uniform results: The variance expansion extends uniformly from a single variable to function classes under sufficient-variance conditions, using complexity measures such as Rademacher averages and covering numbers.Theorem 2 gives a uniform result for bounded functions, while later examples apply the framework to classification classes.
Classification examples: For margin-based classification, norm constraints and loss complexity determine conditions under which the exact variance expansion holds uniformly over parameters.The examples cover Euclidean and high-dimensional ℓ1-constrained settings.

3 Optimization by Minimizing the Robust Loss

The robustly regularized objective is a tighter, convex approximation to population risk that automatically trades approximation and estimation error. Its guarantees can improve on ERM in variance-sensitive settings, while preserving useful invariance properties.

Main guarantees: The robust objective overestimates population risk by at most O(1/n), compared with the empirical risk's O(1/√n) approximation.This tighter approximation underpins favorable finite-sample properties, though they are not always comparable to ERM.
Main guarantees: Theorem 3 gives high-probability guarantees linking the population expectation to the robust empirical objective and the empirical minimizer to the best variance-corrected risk.The first gap is O(1/n), while the second is O(log n/n).
Examples and comparisons: In realizable or low-variance settings, robust regularization can achieve faster convergence and tighter excess-risk bounds than ERM.The paper reports an O(log n/n) robust excess-risk bound and cases where the robust leading term depends only on noise level B^2, unlike ERM's dependence on global information.
Localized analyses: Localized complexity analyses provide tighter bounds in some settings, including RKHS classes with rapidly decaying kernel eigenvalues and polynomial-eigenvalue regimes.The reported rate in one example holds without assumptions on the smoothness of the noise distribution.
Examples and comparisons: A constructed LAD regression example exhibits a gap of nearly n^2 in order of convergence between robust regularization and ERM.The example is specially constructed, and the paper characterizes the robust method as more conservative in related comparisons.
Invariance properties: The robust solution has invariance properties absent from standard parameter-centered regularizers, including shift invariance for symmetric location losses and invariance to invertible linear transformations in generalized linear models.These properties preserve behavior under corresponding transformations of the data or parameterization.

4 Robust regularization cannot be too bad

The robust estimator can achieve fast convergence rates comparable to empirical risk minimization under curvature or growth conditions, while its asymptotic efficiency loss appears in a bias term. Its behavior relative to empirical risk minimization depends on the setting and on how the loss variance changes near the optimum.

Comparison with ERM: The estimator does not dominate empirical risk minimization, which remains essentially optimal in some correctly specified classical problems.The paper explicitly identifies correctly specified Gaussian linear regression as a setting where least-squares empirical risk minimization is essentially optimal.
Finite-sample rates: The robust estimator enjoys near-optimal fast convergence rates when the population risk has suitable curvature or growth conditions.Under these conditions, its rates can match those of empirical risk minimization, including approximate rates associated with strong convexity.
Conditions: The finite-sample guarantees rely on assumptions including convexity, local Lipschitz behavior, and a population-risk growth condition around the optimal solution set.The paper states that the Lipschitz condition need only hold locally near the relevant solution set.
Asymptotic behavior: Asymptotically, the robust estimator generally retains the classical variance while incurring efficiency loss through an additional bias term.The additional penalty appears at rate 1/n in asymptotic risk, while the asymptotic variance is generally unimprovable.
Asymptotic behavior: The asymptotic bias is small when loss variance is stable near the optimum but can become substantial when the variance changes sharply with the parameter.The relevant quantity is the gradient of the loss variance at the optimal parameter.
Special case: In correctly specified Gaussian linear regression, symmetry makes the bias term zero, so the robustly regularized estimator is asymptotically efficient.This conclusion follows from Cov(εX, ε^2)=0 under the stated Gaussian error model.

5 Experiments

The experiments compare robust variance regularization with ERM and standard regularizers in simulation and classification. Robust solutions reduce variance and improve performance on rare or difficult classes, while tuning ρ controls the trade-off.

Experimental setup: Three experiments compare the robust solution with ERM: a simulation and two real-data classification problems.The implementation uses gradient descent and an efficiently solvable convex subproblem for the worst-case distribution.
Simulation: 100% coverage was obtained in the simulation, exceeding the nominal high-probability guarantee because the bound was conservative.The experiment used δ = .05 and selected ρ to obtain coverage at least 1 − δ.
Simulation: The simulation reports substantially smaller robust-solution variance than ERM, often by several orders of magnitude for large n.The procedure outperforms standard alternatives in this setting.
Protease cleavage: In HIV-1 cleavage classification, increasing ρ improves error on the uncommon class while causing only a small, insignificant degradation on the common class.The robust estimator therefore improves overall classification performance, although the authors note that classification gains can occur despite increased logistic risk.
Reuters corpus: For Reuters, precision rises from .93 ± .005 to .94 ± .005 as ρ increases, while Economics recall improves substantially from ERM’s .69 test recall as ρ increases to 10^5.The improvement occurs without significant precision degradation, whereas very large ρ = 10^6 worsens classification performance.
Overall findings: Across examples, robustification favors hard or high-variance instances and provides a principled ρ knob for trading variance against absolute performance.The paper identifies rare classes with few training examples as a representative setting where this behavior is useful.

6 Discussion

The discussion positions robust regularization as a convex variance-regularization approach with theoretical support across stochastic optimization and learning. It highlights empirical benefits on hard instances while identifying unresolved links to existing fast-rate theory.

Contributions: The paper develops theoretical results for robust regularization that apply to general stochastic optimization and learning problems.The discussion connects these results to the robust solution studied empirically.
Interpretation: Robust regularization is presented as a convex surrogate for variance regularization that can improve performance on hard, higher-variance instances.Examples include classes with relatively few training examples.
Open questions: The relationship between robust-estimator performance and that of ERM, related estimators, and variance-regularized estimates remains a challenge.The authors leave identifying the separation between these procedures for future work.
Rates: The robust estimator has faster convergence rates under growth conditions analogous to uniform convexity of the population risk.The discussion states that the connection to the paper’s other variance-related guarantees remains unclear.
Interpretation: The robust objective is an empirical-likelihood upper confidence bound on optimal population risk and has a self-normalizing, pivotal-statistic interpretation.The discussion suggests that self-normalization may yield fruitful complexity guarantees.

A Proof of Theorem 1

The proof establishes variance-related properties of the robust objective through concentration and moment bounds. It combines sufficient conditions for exact expansions with auxiliary lemmas controlling empirical variance.

Proof structure: The proof begins from the robust-risk maximization problem and its solution criterion.These characterize the maximizing distribution used in the robust objective.
Variance bounds: Under the theorem’s conditions, bounded observations and sufficient sample variance yield two-sided variance bounds for the robust objective.The exact expansion holds when the sample variance is large enough.
Concentration: A high-probability lower bound on sample variance is obtained using concentration for convex functions and estimates of expected standard deviations.The resulting event supplies the sufficient condition needed for the theorem.
Auxiliary lemmas: The auxiliary lemmas control fourth moments, covariances, and empirical variances for bounded or finite-fourth-moment random variables.These controls are combined to prove the variance inequalities and exact expansion.
Bounded case: The bounded-variable case uses the range condition to relate fourth central moments and variance, completing the final inequality.The proof invokes the bound E[(Z − E[Z])^4] ≤ C^2 Var(Z) for variables supported on an interval of width at most C.

B Proof of Theorem 2

The proof of Theorem 2 derives uniform control of empirical variances and empirical-process deviations for bounded function classes. It combines Rademacher-complexity and concentration tools to obtain the theorem’s result.

Proof strategy: The proof reduces Theorem 2 to a uniform lower bound on sample variances that holds with sufficiently high probability.The empirical variance is decomposed into a second-moment term and a squared empirical-mean term.
Second-moment control: Lemma B.1 provides a high-probability lower bound for empirical second moments over a bounded function class.Its proof uses a sub-root upper bound on worst-case Rademacher complexity.
Conclusion: Combining the auxiliary bounds yields the desired uniform result with probability at least 1 − e^−t.The final step explicitly combines the preceding lemmas.
Deviation control: A Talagrand-type inequality bounds empirical-process deviations when every function in the class has variance at most r.The same statement applies to the reverse deviation involving empirical means.

C Proof of Theorem 3

The proof establishes Theorem 3 by combining uniform Bernstein-type bounds, fixed-function concentration, and the optimizer’s robust-risk characterization.

Uniform Bernstein-like bounds are obtained for the function class using empirical ℓ∞-covering numbers.
The robust estimator is characterized through bf ∈argminf∈F supP subject to Dφ(P|| bPn) ≤ρ/n.
For each fixed f ∈F, Bernstein’s inequality and Lemma A.1 yield simultaneous bounds with probability at least 1 −2e−t.
The proof uses assumptions such as ρ ≥t to substitute concentration bounds into the earlier risk inequality.
These bounds yield the theorem and its stated result.

D Proof of Theorem 4

The proof of Theorem 4 develops uniform variance and expectation bounds using localized Rademacher complexity, self-normalization, peeling, and concentration inequalities.

Uniform Bernstein inequalities are established using Rademacher complexities, peeling, and Talagrand’s concentration inequality.
Lemma D.1 provides a uniform bound for bounded functions with Var(f(X)) ≤r and probability at least 1 −e−t.
The argument extends global Rademacher complexity bounds to the local fixed point r⋆n of the sub-root function ψn.
Self-normalized scaling is used instead of variance-normalizing scaling to obtain bounds applicable to robustly regularized risk.
The resulting inequalities hold uniformly over f ∈F with probability at least 1 −2e−t and support results (22) and (23).

E Proof of Theorem 5

The proof of Theorem 5 controls localized empirical deviations around the projection onto the optimal set using convexity, bounded differences, and symmetrization.

The Euclidean projection π(θ) maps parameters onto the closed convex optimal set S⋆.
The localized deviation function compares population and empirical excess losses relative to π(θ).
The proof bounds the supremum of localized deviations using bounded differences and the standard symmetrization inequality.
Convexity of Rn allows points outside the localized set to be connected to its boundary while controlling empirical risk.
Applying Theorem 1’s upper bound completes the claim.

F Proof of Theorem 6

The proof of Theorem 6 derives asymptotic guarantees by establishing an eventual uniform expansion, then applying local asymptotic analysis and Gaussian-limit arguments.

A uniform expansion near θ⋆ is established before applying standard finite-dimensional estimator asymptotics.
The expansion requires suitable variability in observed losses and care because losses may be unbounded below and above.
The empirical variance of Z(θ) is identical to the empirical variance of ℓ(θ, X).
Under the stated moment and Lipschitz conditions, the exact variance expansion eventually holds with probability one.
The proof combines the exact expansion with asymptotic expansions of the variance-regularized objective and invertibility of the local Hessian.
The leading asymptotic term converges in distribution to a N(0, Σ) distribution, yielding the theorem’s claimed limit.

G.2 Proof of Lemma 3.1

The proof characterizes the empirical risk minimizer through counts of the three possible observations and bounds the probability of its two extreme-count events.

The empirical risk minimizer equals 1 when N1 > N0 + N−1, −1 when N−1 > N0 + N1, and lies in [−1, 1] otherwise.
Because N1 + N−1 + N0 = n, the event N1 > N0 + N−1 is equivalent to N1 > n/2.
The two events producing extreme minimizers are disjoint: N1 > N−1 + N0 or N−1 > N0 + N1.
Marginally, N1 follows a Binomial distribution with parameters n and 1−δ.
For odd n the final probability is 0, whereas for even n the proof derives a separate expression.

G.3 Proof of Lemma F.4

The proof establishes consistency of the robust estimator under local regularity and gives an efficient simplex-projection procedure for computing the optimizing probability vector.

Proof of Lemma F.4: Positive-definite local curvature and uniform convergence imply that the robust estimator eventually lies within every ε-neighborhood of θ⋆.
Proof of Lemma F.4: The relevant inequalities combine uniform convergence, strong convexity of R near θ⋆, and the separation condition ∥θ − θ⋆∥2 ≥ ε.
Efficient computation: The inner optimization is reformulated using a partial dual with λ ≥ 0, and strong duality applies because the Slater condition is satisfied.
Efficient computation: For fixed λ, the infimum is computed by projecting v(λ) onto the probability simplex, yielding p_i(λ) = (v_i − η)+.
Efficient computation: The threshold η is selected so the projected coordinates sum to one, with positive entries before the active index and nonpositive entries afterward.
Efficient computation: After sorting z, binary searches over the active index and λ compute the solution in O(log 1/ε log n) time, following O(n log n) sorting.