Source-linked AI summary
Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models
Mor Shpigel Nacson, Suriya Gunasekar, Jason D. Lee, Nathan Srebro, Daniel Soudry
TL;DR
The paper addresses how regularization and gradient descent relate to margin-maximizing solutions, extending prior path analysis beyond positive-homogeneous predictors. It studies constrained and margin paths and characterizes their solutions, including lexicographic max-margin behavior for homogeneous models and shallow-submodel discarding in ensembles.
Problem
Earlier path-to-margin results were limited to positive-homogeneous predictors, leaving models such as biased networks and different-depth ensembles outside that connection.
Source: §1 · p. 2Method
The paper studies diverging-norm constrained and margin paths, and relates them to unconstrained optimization for homogeneous and non-homogeneous models.
Source: §1 · p. 2, Contributions · p. 3, §2 · p. 3Results
The constrained path converges to lexicographic max-margin solutions for homogeneous models, while non-homogeneous sums of different-order homogeneous functions have characterized asymptotic solutions.
Source: §1 · p. 2, Contributions · p. 3Takeaways & Limitations
In homogeneous-network ensembles, the asymptotic solution discards the shallowest network when it is unnecessary.
Source: Contributions · p. 3Margin convergence of the constrained path does not guarantee convergence in parameter space to the margin path; the optimization-path results require a C2 smoothness assumption.
Source: §3.1 · p. 4, §4.1 · p. 7
Abstract
from arXiv · showhide
With an eye toward understanding complexity control in deep learning, we study how infinitesimal regularization or gradient descent optimization lead to margin maximizing solutions in both homogeneous and non-homogeneous models, extending previous work that focused on infinitesimal regularization only in homogeneous models. To this end we study the limit of loss minimization with a diverging norm constraint (the "constrained path"), relate it to the limit of a "margin path" and characterize the resulting solution. For non-homogeneous ensemble models, which output is a sum of homogeneous sub-models, we show that this solution discards the shallowest sub-models if they are unnecessary. For homogeneous models, we show convergence to a "lexicographic max-margin solution", and provide conditions under which max-margin solutions are also attained as the limit of unconstrained gradient descent.
1. Introduction
The paper asks how training-time inductive bias selects among solutions in overparameterized models, extending path-to-margin analysis beyond positive-homogeneous predictors. It characterizes constrained-path solutions and studies when unconstrained gradient descent approaches margin-maximizing solutions.
1. Introduction
- Overparameterized networks can fit training data perfectly, yet minimizing training loss alone does not guarantee good generalization.The learning process's inductive bias affects which global minimizer is chosen.Source: §1 · p. 1
- Prior path-to-margin results were limited to positive-homogeneous predictors, excluding models with biases, different-depth ensembles, ResNets, and other skip connections.This work extends the connection beyond positive-homogeneous predictors.Source: §1 · p. 2
Contributions
- The constrained path converges to lexicographic max-margin classifiers, refining ordinary margin maximization when multiple solutions exist.The refinement successively maximizes distance to the closest data point, then the second closest, and so on.Source: §1 · p. 2
- When attainable margin is unbounded, constrained-path margins converge to max-margin; under additional conditions, the constrained path converges to the margin path in parameter space.The paper also gives conditions under which the optimization path converges to stationary points of the margin or constrained paths.Source: Contributions · pp. 2–3
- For models that sum homogeneous functions of different orders, the paper characterizes asymptotic constrained-path and margin-path solutions.In ensembles of homogeneous neural networks, the solution discards the shallowest network if unnecessary.Source: Contributions · p. 3
- The models also represent hard-margin SVM problems with unregularized bias, and the paper identifies conditions linking unconstrained optimization to margin maximization.For general continuous homogeneous models, the constrained path converges to lexicographic max-margin classifiers.Source: §1 · p. 2, Contributions · p. 3
2. Preliminaries and Basic Results
The preliminaries set up exponential-tailed loss minimization and define three paths: optimization, constrained, and margin. They state assumptions and a boundary property for constrained-path minimizers.
2. Preliminaries and Basic Results
- The paper studies exponential-tailed loss for continuous real-valued prediction functions on N samples.For any norm, it also defines the unit-norm ball in parameter space.Source: §2 · p. 3
2.1. The Optimization Path
- The optimization path is given by the direction of gradient-descent iterates in the Euclidean norm.It depends on the initialization and learning rates.Source: §2.1 · p. 3
2.2. The Constrained Path
- The constrained path minimizes loss at a fixed norm; under the stated monotonicity assumption, its minimizers lie on the unit-ball boundary for sufficiently large scaling.The assumption is that the constrained minimum decreases strictly toward zero beyond a threshold.Source: §2.2 · p. 3
2.3. The Margin Path
- The margin path maximizes margin at each scaling, assuming the maximum margin increases strictly without bound beyond a threshold.The text notes that sums of positive-homogeneous prediction functions satisfy this assumption.Source: §2.3 · p. 4
3. Non-Homogeneous Models
The section relates diverging-norm constrained paths to margin paths, showing when their margins or parameter sets converge and how the asymptotic solution behaves for sums of differently homogeneous functions. It also identifies examples where parameter convergence does and does not hold.
3.1. Margin of Constrained Path Converges to Maximum Margin
- When the attainable margin is unbounded, the constrained path’s margin converges to the maximum margin, though this does not guarantee convergence of its parameter set to the margin path.The section gives examples of both convergence and non-convergence in parameter space.Source: §3.1 · p. 4
Example 1: homogeneous models
- For homogeneous predictors, the margin path is constant across scales, but constrained-path convergence to it can depend on the predictor: it fails for the log predictor and holds for the (1+ε)-log example.For homogeneous models and any norm, the section connects the constrained path to the margin path and further refines the limit to a lexicographic max-margin subset.Source: Example 1: homogeneous models · pp. 4–5
3.2. Sum of Positively Homogeneous Functions
- The section characterizes the margin path for sums of positively homogeneous functions and relates its asymptotic form to the constrained path.The results in this subsection are specific to the Euclidean (L2) norm.Source: §3.2 · pp. 5–6
- For sums of positively homogeneous functions with increasing degrees, the asymptotic solution minimizes the lowest-degree component’s norm first, then the successive components’ norms.In an ensemble, this implies discarding the shallowest network when it is unnecessary to satisfy the constraints; discarding further unnecessary shallow networks is conjectured.Source: §3.2 · pp. 5–6
- Theorem 1 is used to represent hard-margin SVM problems with an unregularized bias, a setting prior results described here did not cover.The construction yields an asymptotic solution satisfying the stated margin constraint.Source: §3.2 · pp. 6–7
4. Homogeneous Models
For homogeneous predictors, the paper relates the optimization path to the margin and constrained paths, then refines constrained-path limits as lexicographic max-margin solutions. Under stated regularity and constraint-qualification assumptions, gradient descent’s limiting direction is first-order optimal for the diverging-norm constrained problem.
4. Homogeneous Models
- The homogeneous-model analysis links the optimization path to the limit of the margin path and to the diverging-norm constrained path.For general homogeneous predictors, the margin-path problem may be non-convex, so the analysis also considers first-order stationary points.Source: §4 · p. 7, §4.1 · pp. 7–8
4.1. Optimization Path Converges to Stationary Points of the Margin Path and Constrained Path
- LICQ makes the first-order optimality conditions necessary; in linear SVM, linearly independent support vectors ensure LICQ, while degenerate data may violate it.The paper notes that the global optimum need not satisfy those conditions without a constraint qualification.Source: §4.1 · p. 7
- Under Assumptions 1, 3, 4, and LICQ at the limiting direction, gradient descent’s normalized iterates are first-order optimal as the norm constraint diverges.The section assumes C2 prediction functions, convergence of the loss to zero, and asymptotic formulas for losses and parameters.Source: §4.1 · pp. 7–8
4.2. Lexicographic Max-Margin
- The constrained-path limit for α-positive homogeneous predictors is contained in the lexicographic maximum-margin set.This refines ordinary max-margin selection by successively considering the smallest margins when solutions are not unique.Source: §4.2 · p. 8
5. Summary
The paper characterizes links among constrained, margin, and optimization paths across model classes. It reports that ensemble models can discard unnecessary shallow sub-models, while homogeneous-model optimization paths converge to stationary points of the margin and constrained paths.
5. Summary
- For ensembles that are finite sums of positively homogeneous functions, the asymptotic constrained-path and margin-path solutions imply that unnecessary shallow networks are discarded.The paper identifies sums with shared variables, such as ResNets, as future work.Source: §5 · p. 8
- For general non-homogeneous models, the constrained-path solution’s margin converges to the maximum margin, and for some models the constrained path converges in parameters to the margin path.Source: §5 · p. 8
- For homogeneous models, the optimization path converges to stationary points of the constrained and margin paths, and the constrained-path limit receives a more refined characterization.The authors leave extending the optimization-path result to non-homogeneous models and determining whether data-point weighting affects asymptotic solution selection for future work.Source: §5 · pp. 8–9
A. Proof of Lemma 1
The proof establishes that the two optimization formulations have the same solution set by showing feasibility and ruling out additional solutions.
A. Proof of Lemma 1
- A solution of eq. 2 must satisfy the norm constraint at equality, so it also solves eq. 3; any supposed extra solution of eq. 3 would violate its feasibility condition.The proof uses strict monotonic decrease of φ(ρ) to rule out reducing ρ without changing the solution.Source: A. Proof of Lemma 1 · p. 11
B. Proof of Claim 1
The proof shows that solutions of eq. 14 approach the solution set W by contradicting the possibility of staying a fixed distance away.
B. Proof of Claim 1
- If a solution remained outside an ε-neighborhood of W, it would incur a fixed excess in the relevant norm, contradicting its optimality for sufficiently large γ′.Feasibility for both formulations and a bounded comparison solution provide the contradiction.Source: B. Proof of Claim 1 · p. 11
C. Proof of Lemma 5
The proof assumes the claimed form fails, then derives a contradiction from a norm gap, establishing convergence to the specified set and form.
C. Proof of Lemma 5
- A fixed positive distance from the set would force a positive norm gap, contradicting the asymptotic bound.The contradiction yields convergence into W and the representation in equations 12 and 13.Source: C. Proof of Lemma 5 · pp. 11–12
D. Examples Section: Auxiliary Results
The auxiliary arguments connect margin convergence to parameter-space convergence and derive an asymptotic relation for the specified loss function.
D.1. Showing that margin convergence implies convergence in the parameter space for homogeneous models
- For homogeneous models, margin convergence implies that the constrained parameter set converges to the margin-optimal set.The proof uses a contradiction and compactness to rule out parameters remaining a fixed positive distance from that set.Source: §D.1 · p. 12
D.2. Auxiliary results for fn (ρ, θ) = log1+ǫ ρθ⊤zn
- The gap γ*(ρ) − γ(ρ, θc(ρ)) equals (1 + ε) log^ε(ρ) times log(eγ*) − log(eγ(θc(ρ))), plus o(log^ε(ρ)).Source: §D.2 · p. 13
- When the log-margin difference tends to zero, the constrained parameter set converges to the margin-path set, using the homogeneous-case proof.The passage states that the remaining proof is identical to the argument in Appendix D.1.Source: §D.2 · p. 13
E.1. Proof of Theorem 2
These proof sections establish first-order margin optimality for Theorem 2 and use related loss comparisons and induction arguments in the proofs of Theorems 3 and 4.
E.1. Proof of Theorem 2
- Theorem 2’s proof shows that the limiting parameter satisfies the first-order optimality conditions of the margin problem.The argument identifies active indices S at the optimal margin; coefficients a_n vanish for n outside S.Source: §E.1 · pp. 13–14
E.2. Proof of Theorem 3
- Theorem 3’s proof follows the same approach as Theorem 2, reusing its cited equations and proof steps.The supplied passage characterizes the proof as similar, without specifying further theorem conclusions.Source: §E.2 · p. 15
E.3. Proof of Theorem 4
- Theorem 4’s proof compares constrained-path losses using upper and lower bounds, then proceeds by induction over successive sets.The induction begins with the unit sphere as the base set; the proof also invokes a lower bound for losses along a convergent constrained-path sequence.Source: §E.3 · pp. 15–16
F.1. The Regularization Path
The regularization-path arguments establish existence and norm divergence under stated conditions, then relate regularized solutions to constrained-path solutions.
F.1. The Regularization Path
- For every c > 0, the regularization path is nonempty because the regularized objective attains a minimum.The proof uses coercivity of the objective and continuity over a nonempty closed set.Source: §F.1 · p. 17
- If the optimal loss on spheres is strictly decreasing beyond a threshold, regularized minimizers’ norms diverge as c increases.The stated condition is strict monotonic decrease of L*(ρ) for ρ ≥ ρ0.Source: §F.1 · p. 17
F.2. Connections between regularization and constrained paths
- Each regularized solution belongs to a constrained path at some radius; under strict loss decrease, the constrained solutions at its norm are also regularized minimizers.The connection is stated for every c > 0 and each θr in Θr(c).Source: §F.2 · p. 18