Variance-based regularization with convex objectives

1 Introduction

• The proposed robust empirical risk uses empirical-likelihood and distributionally robust ideas to approximate variance-regularized risk while remaining convex when the loss and parameter space are convex.The variance-penalized empirical-risk formulation can be non-convex even for convex losses, motivating the tractable surrogate.Source: §1 · pp. 2–3
• O(1/n) is the robust risk’s approximation to population risk, compared with O(1/√n) for empirical risk.For bounded losses, the robust risk also approximates the variance-regularized quantity; its finite-sample convergence guarantees are often tighter than ERM’s.Source: §1 · pp. 2–3
• O(ρ/n) excess risk is attainable when parameters with small risk and variance exist; the procedure also provides high-probability optimality certificates without requiring a Bernstein-type condition.An explicit example gives O(log n/n) convergence for the robust procedure versus O(1/√n) for ERM.Source: §1 · p. 3
• Under suitable growth conditions, robust estimation retains near-optimal fast rates, while classical correctly specified problems can incur inefficiency; the asymptotic analysis identifies a bias despite optimal variance.The paper studies finite-sample properties for general stochastic optimization and asymptotic normality in classical problems.Source: §1 · pp. 3–4
• Across three experiments, robust solutions outperform ERM on harder, higher-variance instances and improve rare-class performance at minor cost on common classes.The reported classification tradeoff reflects ERM’s tendency to sacrifice rare-class performance to improve common cases.Source: §1 · p. 4

Related Work

• Maurer and Pontil [33] directly penalize empirical variance but yield a generally non-convex problem; this approach addresses that tractability obstacle for general stochastic optimization.The introduction also distinguishes the method’s risk-variance tradeoff from prior fast-rate approaches that often require noise or curvature conditions.Source: §1 · p. 3, Related Work · pp. 4–5

2 Variance Expansion

• The robust formulation is convex for convex losses, even though loss variance can be non-convex, as illustrated by the absolute-loss example.The example’s variance function has multiple local minima and inflection points and does not grow as θ → ±∞.Source: §2 · p. 5, Figure 1 · p. 6

2.1 Variance expansion for a single variable

• For bounded losses, robustly regularized risk is a convex surrogate for empirical risk plus loss standard deviation and approximates exact variance regularization.The exact expansion applies when the loss has enough variance; the section uses it to develop guarantees for stochastic risk minimization.Source: §2.1 · pp. 6–7

2.2 Uniform variance expansions

• The variance expansion holds uniformly for bounded functions with sufficient variance under a Rademacher-complexity condition.The section also notes that an asymptotic analogue for heavier-tailed random variables is possible [20].Source: §2.2 · pp. 7–8

2.2.1 Linear and margin-based losses

• In margin-based classification, the section applies variance-expansion guarantees to Euclidean and high-dimensional ℓ1-constrained settings.For the high-dimensional setting, the exact expansion holds with high probability uniformly over predictors meeting a variance threshold.Source: §2.2.1 · pp. 8–9

2.2.2 Covering number guarantees

• Covering-number bounds also yield high-probability exact variance expansions above a variance threshold, while Rademacher-complexity arguments can be tighter.The section motivates these guarantees with covering numbers for function classes and Lipschitz losses over parametric sets.Source: §2.2.2 · pp. 9–10

3 Optimization by Minimizing the Robust Loss

• The robust objective overestimates population risk by at most O(1/n), versus the empirical risk’s O(1/√n) approximation, yielding favorable finite-sample properties.The guarantees are not always comparable to those for empirical risk minimization.Source: §3 · p. 10

3.1.1 Covering bounds: corollaries

• For finite-VC classes, the corollaries extend to standard loss-composition ERM settings and give high-probability guarantees with failure probability at most 2 exp(c1 d log n − c2ρ).Here c1 and c2 are universal constants, with c2 ≥ 1/9.Source: §3.1.1 · pp. 11–12

3.1 Covering arguments

• The covering-number results bound robust risk and excess risk, with the latter controlled relative to the best variance-corrected risk at O(log n/n).The section also gives an example where the robust solution has a tighter excess-risk bound than ERM under a straightforward localized Rademacher-complexity argument.Source: §3 · p. 10, §3.1.2 · p. 12

3.1.2 Examples and heuristic discussion

• In well-specified LAD regression, the robust bound’s leading term depends on noise level B², while the ERM counterpart also depends on parameter-space diameter D and covariate bound L.For typical d-dimensional classes, the passage says the ERM bound is worse; the robust comparison is against an optimistic naive ERM bound.Source: §3.1.2 · p. 13
• In the hard median example, ERM has excess risk 2δB with constant probability, whereas the robust estimator’s excess risk is at most δB with high probability.The robust choice is more conservative, favoring parameters for which large losses are less frequent.Source: §3.1.2 · p. 13
• Robust minimization attains faster rates when variance at the optimum is small; for bounded realizable losses, it retains O(log n/n) rates under the stated conditions.The passage notes that Var(ℓ(θ⋆; X)) = 0 can hold even when another parameter has lower loss with positive probability.Source: §3.1.2 · pp. 13–14

3.2 Localized Rademacher Complexity

• The refined guarantee replaces global covering arguments with localized Rademacher complexity, whose additional terms are negligible when variance dominates the first moment.Theorem 4 gives a high-probability bound for the robust empirical minimizer under its stated sub-root complexity and radius conditions.Source: §3.2 · pp. 14–15
• For RKHS LAD regression, localization yields guarantees when covering numbers are too large, with rates tied to kernel eigenvalue decay and no noise-smoothness assumption.The examples consider exponentially or polynomially decaying eigenvalues; the stated convergence guarantee does not require smoothness of the noise distribution.Source: §3.2 · pp. 15–16

3.3 Beating empirical risk minimization

• For a loss centered at θ⋆, robust risk is at most R(θ⋆) + O(1/n) with high probability; gains are expected when piecewise-linear losses make ERM noise-sensitive.In the constructed example, ERM may have substantially higher risk when too many observations equal 1 or −1.Source: §3.3 · p. 17
• In a constructed one-dimensional example estimating the median of a discrete distribution supported on X = {−1, 0, 1}, the robustly regularized estimator converges at log n/n, while empirical risk minimization is at best 1/√n.Source: §3.3 · pp. 17–18

3.4 Invariance properties

• For unconstrained Θ = R^d, robust regularization is shift invariant for symmetric convex location losses and invariant to invertible linear transformations in generalized linear models.The section notes that these results require unbounded θ; localization approaches can address this limitation.Source: §3.4 · p. 18

4 Robust regularization cannot be too bad

• Robust regularization cannot generally dominate ERM; in correctly specified Gaussian linear regression, least squares is essentially optimal and the robust estimator is asymptotically efficient.The robust estimator’s bias is zero in this special case by symmetry of the error distribution.Source: §4 · p. 18, §4.2 · pp. 21–22

4.1 Fast Rates

• Under local risk growth and convex Lipschitz loss, robust approximate minimizers achieve ERM-comparable fast rates; when γ=2, roughly strong convexity, they attain the familiar rate, unless ρ is too large.The growth condition is R(θ) ≥ λ dist(θ,S⋆)^γ near the optimal set.Source: §4.1 · pp. 19–20

4.2 Asymptotics

• The robust estimator retains the generally unimprovable asymptotic variance, but its efficiency loss lies in a bias of order 1/√n scaled by confidence ρ, adding an asymptotic-risk penalty of order 1/n.Source: §4 · p. 19, §4.2 · p. 21
• When loss variance is stable near θ⋆, robust regularization has asymptotically little effect; a large gradient of loss variance instead yields substantial bias.Source: §4.2 · p. 21

5.1 Minimizing the robust objective

• The robust objective is minimized by gradient descent, using an efficiently solvable convex dual problem to compute the worst-case distribution and backtracking line search for step sizes.The dual procedure computes an ε-accurate solution in O(n log n + log(1/ε) log n) time.Source: §5.1 · p. 22

5.2 Simulation experiment

• In the simulation, robust solutions always achieved lower true risk than ERM, with the risk gap significant at p < .01 and substantially smaller robust-solution variance.The experiment used 1,200 independent replications per sample size and B; observed robust coverage was 100%, exceeding the stated high-probability guarantee’s conservative bound.Source: Figure 2 · p. 23, §5.2 · p. 23, Table 2 · p. 24

5.4 Document classification in the Reuters corpus

• As ρ rose from 0 (ERM) to 105, Economics recall improved substantially from ERM’s .69 test recall without significant precision degradation; at 106, robustness degraded classification performance.Precision increased from .93 ± .005 to .94 ± .005. These classification improvements occurred despite an increase in average binary logistic risk.Source: Figure 5 · p. 29, §5.4 · p. 29

Summary

• Across applications, robustification improved performance on harder, higher-variance instances, with ρ providing a tuning parameter to trade variance against absolute performance.The paper identifies relatively rare classification classes as an example of subsets that induce higher variance.Source: Summary · p. 30

Discussion

• The authors develop theoretical results for robust regularization in general stochastic optimization and learning, and expect it to perform well when the optimal loss variance is small.They also report empirical observations that it can improve performance on hard instances without sacrificing performance on easier ones, but say rigorous explanations and comparisons with related estimators remain open.Source: §6 · p. 30
• Robust estimates achieve faster convergence under growth conditions analogous to uniform convexity, but connecting these guarantees to Theorems 3 and 4 remains unclear.ERM fast rates typically require the risk gap to control excess-loss variance [32, 3, 10, 4]; the robust analysis involves the variance of the loss difference, which need not equal the variance of the loss.Source: §6 · pp. 30–31
• Theorem 4’s complexity guarantee uses self-normalized function classes, and the authors suggest studying this normalization could yield insights.They connect the robust objective to an empirical-likelihood upper confidence bound on optimal population risk and note that empirical-likelihood bounds are self-normalizing and yield pivotal statistics.Source: §6 · p. 31
• The discussion contrasts this analysis with Bartlett et al.’s [3, Theorem 3.3] ERM result, which considers a different class of functions involving E[f^2].The robust proof instead considers complexity of self-normalized classes; investigating this distinction is proposed as a direction for future work.Source: §6 · p. 31

A Proof of Theorem 1

• When the sample variance or σ² is zero, the theorem is immediate; otherwise, the proof uses maximization problem (8) and solution criterion (9).Source: A Proof of Theorem 1 · p. 32
• Theorem 1’s proof combines two-sided variance bounds with a high-probability exact expansion, which follows when the sample variance is sufficiently large.The proof establishes that the condition for the exact expansion holds with high probability by lower-bounding the sample variance.Source: A Proof of Theorem 1 · pp. 32–33

A.1 Proof of Lemma A.1

• Lemma A.1 obtains a high-probability lower bound on sample variance using convex-function concentration and estimates of the expectation of standard deviations.The proof invokes concentration inequalities for convex functions to show that the event ensuring the exact expansion has high probability.Source: A Proof of Theorem 1 · pp. 32–33, §A.1 · p. 33

A.2 Proof of Lemma A.3

• Lemma A.3 proves bounds (31a) and (31b) for finite-fourth-moment variables under a pairwise covariance condition on their squares.The proof uses Cauchy–Schwarz to establish (31a), then derives the sharper bound (31b).Source: §A.1 · p. 33, §A.2 · pp. 34–35

A.3 Proof of Lemma A.4

• Lemma A.4 applies Lemma A.3 to centered i.i.d. variables with finite fourth moment to obtain bounds (33a) and (33b).When the variables are bounded within an interval of width C, the proof specializes the final inequality using fourth-moment and variance bounds.Source: §A.1 · p. 33, §A.3 · pp. 35–36

B Proof of Theorem 2

• A uniform high-probability lower bound on sample variances yields Theorem 2 by combining bounds on the two terms in the variance decomposition.The proof writes the sample variance as an empirical second moment around the population mean minus the squared empirical mean around that mean.Source: B Proof of Theorem 2 · pp. 36–37
• Lemma B.1 provides a high-probability bound for every function in a bounded class, supporting the lower bound on the empirical second-moment term.The proof follows Srebro et al. and Bousquet [13, Thm. 6.1], using Rademacher-complexity bounds and a contraction step for the squared function.Source: B Proof of Theorem 2 · pp. 36–37
• Lemma B.2 applies a Talagrand inequality due to Bousquet to bound squared empirical-mean deviations when each function has variance at most r.The same statement also holds with the supremum of the empirical-mean deviations over the function class.Source: B Proof of Theorem 2 · p. 37

• Lemma C.1 provides uniform Bernstein-like bounds for F using empirical ℓ∞-covering numbers (Maurer and Pontil [33], Theorem 6).Source: C Proof of Theorem 3 · p. 37
• The proof establishes Theorem 3’s first bound (15) from Theorem 1’s uniform bounds under ρ ≥ 9t.Source: C Proof of Theorem 3 · p. 38
• For bound (16), the estimator’s minimizing property reduces the proof to bounding its worst-case expected loss over the divergence-constrained distributions.Source: C Proof of Theorem 3 · p. 38
• Bernstein’s inequality and Lemma A.1 give fixed-function bounds with probability at least 1 − 2e^−t; using ρ ≥ t in the earlier bound yields result (16).Source: C Proof of Theorem 3 · pp. 38–39

D.1 Proof of Lemma D.1

• Peeling with Talagrand concentration yields a uniform Bernstein inequality for bounded functions with variance at most r, in terms of Rademacher complexity [3].The lemma also gives the statement with population and empirical expectations reversed.Source: D Proof of Theorem 4 · p. 39

D.2 Proof of Lemma D.2

• Lemma D.2 replaces expected Rademacher complexity with a local fixed-point quantity, applying Lemma D.1 to a self-normalized class to bound robustly regularized risk.Following techniques of Bartlett et al. [3, Thm. 3.3], it uses f/√E[f²] rather than variance-normalizing scaling.Source: D Proof of Theorem 4 · p. 39
• The localized bound also holds with the roles of population and empirical expectations reversed.Source: D Proof of Theorem 4 · p. 39, §D.2 · p. 43

D.3 Proof of Lemma D.3

• Lemma D.3 establishes an analogous high-probability bound for squared functions under the localization condition, with a tunable η.Source: D Proof of Theorem 4 · p. 39

D Proof of Theorem 4

• The proof obtains Theorem 4’s first bound (22) with probability at least 1−2e−t and derives its second bound (23) via Bernstein and standard-deviation concentration.For the second bound, it chooses f to minimize the right-hand side of the preceding expression.Source: D Proof of Theorem 4 · p. 41

D.3 Proof of Lemma D.3

• The proof truncates a self-normalized squared-function class, uses the Rademacher contraction principle [28, Thm. 4.12], and also handles reversed expectation roles.Source: §D.3 · pp. 43–44

E Proof of Theorem 5

• The proof defines a Euclidean projection onto the closed convex optimal set and a localized empirical deviation comparing each point with its projection.The deviation is the difference between expected and empirical loss differences for the point and its projection.Source: E Proof of Theorem 5 · p. 44
• Bounded differences and symmetrization control the supremum of the localized deviation, using [11, Theorem 6.5].Source: E Proof of Theorem 5 · p. 45
• Convexity reduces the claim to the localized-set boundary while preserving the projection and bounding empirical risk by projected risk plus ε.The proof then applies Theorem 1's upper bound (10) to obtain the claim.Source: E Proof of Theorem 5 · pp. 45–46

F Proof of Theorem 6

• The exact variance expansion requires sufficient variability in the losses, and the proof handles the added difficulty that losses may be unbounded above or below.The argument makes the heuristic rigorous by first proving a uniform expansion in a neighborhood of θ⋆.Source: F Proof of Theorem 6 · p. 46
• The proof of Theorem 6 first establishes a uniform expansion near θ⋆, then uses Taylor and local asymptotic normality arguments for finite-dimensional estimator asymptotics.It follows standard asymptotic techniques, including those of van der Vaart and Wellner and Lehmann and Casella.Source: F Proof of Theorem 6 · p. 46

F.1 The uniform variance expansion

• Owen’s Lemma 3 is used with the strong law to establish that the conditions for the uniform expansion eventually hold almost surely.Source: §F.1 · p. 48
• Under Assumption A and the stated conditions, the exact variance expansion holds uniformly near θ⋆ eventually with probability one.The argument uses finite second moments for Z(θ⋆) and the random Lipschitz function L(X), together with the strong law of large numbers.Source: §F.1 · pp. 47–48

F.2 Asymptotics and Taylor expansions

• The asymptotic expansion identifies its final term as bias, while its first term converges in distribution to N(0, Σ).The proof obtains the expansion by differentiating the objective near θ⋆ and applying a Taylor expansion.Source: §F.2 · pp. 48–49

G.1 Proof of Inequality (24)

• The proof of inequality (24) bounds Gaussian complexity using Sudakov-Fernique comparison [17] and a classical RKHS bound of Mendelson [34].It also uses the standard bound of Gaussian complexity on Rademacher complexity.Source: §G.1 · pp. 49–50

G.2 Proof of Lemma 3.1

• The empirical risk minimizer is 1 when N1 > N0 + N−1, −1 when N−1 > N0 + N1, and otherwise lies in [−1, 1].The counts satisfy N1 + N−1 + N0 = n.Source: §G.2 · p. 51
• The proof bounds the probability of the disjoint count-dominance events by reducing one event to the binomial tail P(N1 > n/2); the final probability is 0 for odd n and bounded for even n.N1 is marginally distributed as Bin(n, 1−δ/2).Source: §G.2 · p. 51

G.3 Proof of Lemma F.4

• For every ε > 0, the robust empirical minimizer eventually lies within ε of θ⋆, because the objective is eventually larger outside that neighborhood.The proof uses uniform convergence and strong convexity near θ⋆, then extends the objective comparison to all points outside the neighborhood by convexity.Source: §G.3 · p. 52

H Efficient solutions to computing the robust expectation

• The supremum problem is reformulated as minimization over p, then partially dualized in λ; Slater’s condition ensures strong duality.The procedure maximizes the resulting dual problem to find the optimizing p.Source: H Efficient solutions to computing the… · p. 52
• Sorting z and applying simplex projection, with binary searches over the shift and λ, computes the robust expectation in O(n log n + log(1/ε) log n) time.The total includes sorting z; for each λ, the shift index is found by binary search and the derivative is computable in O(1) time.Source: H Efficient solutions to computing the… · p. 53
• For each λ, the infimum is equivalent to projecting v(λ) onto the probability simplex, giving p_i(λ) = (v_i − η)+ with η chosen so the entries sum to 1.The vector z may be sorted and centered without changing the original optimization problem.Source: H Efficient solutions to computing the… · p. 53