PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Particle Gradient Descent for Infinite Ensembles

Atsushi Nitanda, Taiji Suzuki

arXiv:1712.05438v1stat.MLcs.LGmath.OC

TL;DR

Existing infinite-ensemble methods often rely on L1 regularization, which can require early stopping or approximate optimization. This paper proposes SPGD, which learns probability measures over base classifiers using transport maps. It reports a finite-dimensional nonconvex stochastic-optimization convergence rate and an interior optimality property under stated conditions.

  • Problem

    Many infinite-model ensemble methods use L1 regularization with a nonnegative constraint, but handling that regularization is difficult and often requires early stopping or inexact approximation.

    Source: §1 · p. 2

  • Method

    SPGD optimizes a probability measure over parameterized base classifiers through transport-map updates, forming an ensemble by expectation.

    Source: §1 · p. 2

  • Results

    SPGD’s convergence rate is as fast as that of stochastic optimization for finite-dimensional nonconvex problems, and an interior local optimum is optimal in its support under appropriate assumptions.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The finite-particle transport-map approximation forms a residual-type network, while the no-resampling variant is regarded as well-initialized SGD for nonweighted voting classification.

    Source: §1 · p. 3

    The stated algorithm is impractical when it requires the exact value of hμk; the paper estimates it using a sample average.

    Source: §4 · p. 12

Abstract

from arXiv · show

The superior performance of ensemble methods with infinite models are well known. Most of these methods are based on optimization problems in infinite-dimensional spaces with some regularization, for instance, boosting methods and convex neural networks use $L^1$-regularization with the non-negative constraint. However, due to the difficulty of handling $L^1$-regularization, these problems require early stopping or a rough approximation to solve it inexactly. In this paper, we propose a new ensemble learning method that performs in a space of probability measures, that is, our method can handle the $L^1$-constraint and the non-negative constraint in a rigorous way. Such an optimization is realized by proposing a general purpose stochastic optimization method for learning probability measures via parameterization using transport maps on base models. As a result of running the method, a transport map to output an infinite ensemble is obtained, which forms a residual-type network. From the perspective of functional gradient methods, we give a convergence rate as fast as that of a stochastic optimization method for finite dimensional nonconvex problems. Moreover, we show an interior optimality property of a local optimality condition used in our analysis.

1 Introduction

The introduction motivates infinite ensembles as a way to build powerful classifiers while avoiding the regularization and early-stopping difficulties of existing methods. It presents SPGD as probability-measure optimization, alongside generalization bounds, convergence analysis, and practical variants.

1 Introduction

  • Existing ensemble methods optimize linear combinations even though the cited generalization bounds concern convex combinations, so they use regularization such as early stopping to control L1-norm growth.The paper notes that early stopping can interrupt obtaining a sufficiently complex classifier for difficult tasks.Source: §1 · p. 2
  • SPGD learns a probability measure over continuously parameterized base classifiers and forms an ensemble by taking their expectation, potentially yielding infinitely many classifiers.The method is presented as avoiding penalization and early-stopping adjustment while allowing a complex ensemble to be found quickly.Source: §1 · p. 2
  • The paper extends generalization bounds to infinite ensembles, whose probability-measure combinations can reduce the empirical margin-distribution term more than traditional ensembles.The bounds also contain complexity terms.Source: §1 · p. 2

Contributions

  • SPGD updates probability measures by transport maps, and its convergence rate is as fast as that of stochastic optimization for finite-dimensional nonconvex problems.A counter-part of Taylor’s formula supports the local optimality condition and convergence analysis; an interior local optimum is optimal in its support under appropriate assumptions.Source: §1 · pp. 2–3
  • The paper gives a finite-particle transport-map approximation that forms a residual-type network and a no-resampling variant regarded as well-initialized SGD for nonweighted voting classification.The latter is described as extending vanilla SGD to optimization of a general probability measure.Source: §1 · p. 3

Related Work

  • Related methods include L1-regularized boosting and convex neural networks, while SVGD is specialized to KL-divergence minimization and SPGD does not require a special loss structure.The paper says the method therefore applies to a wider class of problems, although its study focuses on ensemble learning.Source: Related Work · pp. 3–4

2 Infinite Ensembles and Generalization Bounds

The section defines infinite ensembles as expectations of parameterized base classifiers under probability measures, then extends margin bounds to this setting. Under a covering-number growth assumption, small empirical margins support bounds on expected classification error.

2 Infinite Ensembles and Generalization Bounds

  • An infinite ensemble averages parameterized base classifiers under a probability measure and predicts by the sign of that expectation.The section considers Borel-measurable base classifiers parameterized over Θ.Source: §2 · p. 5

2.1 Generalization Bounds

  • The section extends existing margin bounds to infinite ensembles under an assumption on the growth of their covering numbers.The stated bounds apply with probability at least 1 − δ over the training sample.Source: §2.1 · p. 5
  • The improved margin bound is also extended to infinite ensembles, with compactness of X required by its stated assumptions.The section says small empirical margin distributions yield good expected classification error for sufficiently large datasets.Source: §2.1 · pp. 5–6
  • The authors argue that optimizing infinite ensembles can reduce empirical margin distributions more than using base classifiers alone.They cite the representation ability of infinite ensembles as the basis for this observation.Source: §2.1 · p. 6

3 Optimization Problem

The paper formulates infinite-ensemble learning as optimization over probability measures and updates those measures through transport maps. Composing the maps gives a final distribution that can be represented by transformed samples from an initial distribution.

3 Optimization Problem

  • The optimization problem seeks a probability measure minimizing the empirical loss for an infinite ensemble.The loss is a function of the ensemble induced by the measure.Source: §3 · p. 6
  • At each step, the current measure is pushed forward by a transport map of the form id + ξ_k in a direction that reduces the objective.Repeated updates compose into a transport map from the initial measure.Source: §3 · pp. 6–7
  • In practice, the final measure is approximated by transforming samples drawn from the initial measure through the composed transport map.The transformed samples are described as samples from the resulting measure.Source: §3 · p. 7

3.1 Optimization Domain and Topological Property

  • The optimization domain P2 consists of probability measures on Θ with finite second moment, and transport maps preserve membership in P2.The paper describes these maps as L2(µ) maps used to push forward measures.Source: §3.1 · p. 7

Integral Probability Metric on P

The section uses an integral probability metric to describe convergence and continuity over probability measures, then develops necessary and sufficient local optimality conditions. It also gives an interior optimality property under assumptions on the measure and its support.

Integral Probability Metric on P

  • The metric d_F compares probability measures through bounded, Lipschitz test functions and defines uniform convergence of their integrals over that function class.The paper identifies its topology with that of the Dudley metric.Source: Integral Probability Metric on P · pp. 7–8
  • Under Assumption 2, the ensemble prediction, empirical loss, and local-optimality quantity are continuous in the measure under the defined metric.A sufficient condition given for Assumption 2 includes differentiability and uniform Lipschitz continuity of the base classifiers and their gradients.Source: Integral Probability Metric on P · p. 8

3.2 Local Optimality Condition

  • A local minimum must satisfy the necessary condition in Theorem 4; with convex loss and the stated positive-curvature condition, the condition is sufficient for a local minimum.The sufficient result is stated on L∞(µ), under Assumption 3.Source: §3.2 · p. 9

3.3 Interior Optimality Property

  • The local and global optimality conditions can differ, but the interior property connects a local optimum to optimality within its support under the theorem’s assumptions.The paper states that the global condition can express this interior property.Source: §3.3 · p. 10
  • For a continuous-density measure with compact smooth-manifold support satisfying the local condition, no better continuous-density measure exists on that support or any measure exists with support inside its interior.The theorem requires the stated smoothness and convexity assumptions.Source: §3.3 · p. 10

4 Stochastic Particle Gradient Descent

SPGD optimizes a probability measure by updating its transport map using stochastic functional-gradient steps. Particle approximations yield a residual-type network, while a no-resampling variant connects the method to vanilla SGD.

4 Stochastic Particle Gradient Descent

  • SPGD updates a measure by pushing it forward and updates its corresponding map by composing with the same displacement.The method uses a stochastic gradient direction to choose the displacement.Source: §4 · pp. 10–11
  • For sufficiently small learning rates, a stochastic transport-map update reduces expected objective value when the measure fails the local optimality condition.The paper presents Algorithm 1 as the ideal SPGD method based on this analysis.Source: §4 · p. 12
  • Exact computation of the ensemble prediction needed for the ideal algorithm is impractical, so the practical method estimates it with a particle sample average.The transport-map update is then approximated using finite particles.Source: §4 · p. 12
  • The finite-particle approximation iteratively stacks residual-type layers to form a residual network that outputs an infinite ensemble.The paper also describes a more practical variant that avoids resampling particles.Source: §4 · p. 12

4.1 Extension of Vanilla Stochastic Gradient Descent

  • With a Dirac initial measure, the practical variant matches vanilla SGD for nonweighted voting, and the general-measure method extends vanilla SGD.The paper also describes a multiclass extension using class-confidence outputs.Source: §4.1 · pp. 13–14

5 Numerical Experiments

The synthetic example shows particles moving to locations whose predicted labels classify the data well. On real binary and multiclass datasets, SPGD generally improves over base models, though not over logistic regression on some datasets.

5.1 Synthetic Data

  • With 20 particles, the final particle locations produced predicted labels that classified the synthetic data well.The figure contrasts initial and final particle weights and predicted labels.Source: §5.1 · p. 14

5.2 Real Data

  • SPGD showed overall improvements over base models on the real-data settings, but did not improve logistic regression on some datasets.The experiments covered binary and multiclass classification tasks.Source: §5.2 · p. 15

6 Conclusion

The conclusion presents infinite-ensemble generalization bounds and an optimality condition, alongside a stochastic optimization method with convergence analysis for empirical risk minimization.

6 Conclusion

  • The paper extends generalization-error bounds from convex combinations to infinite ensembles.Source: §6 · p. 15
  • The paper explores an optimality condition for infinite-ensemble learning.Source: §6 · p. 15
  • For infinite-ensemble empirical risk minimization, the paper proposes a stochastic optimization method and analyzes its convergence.Source: §6 · p. 16

A Generalization Bounds

The appendix develops generalization bounds for majority-vote classifiers by relating infinite ensembles to convex combinations and using Rademacher complexity and covering-number results.

A Generalization Bounds

  • Averaging classifiers with a probability measure does not increase Rademacher complexity.Source: A Generalization Bounds · p. 20
  • For compact feature spaces, the covering numbers of infinite ensembles are bounded by those of convex combinations, using approximation in L2(m).Source: A Generalization Bounds · p. 21
  • The infinite-ensemble class inherits the O(ε^-2V/(V +2)) entropy bound, allowing the improved generalization bound from to be applied.Source: A Generalization Bounds · p. 21

B Topological Properties and Optimality Conditions

The appendix establishes continuity and transport-map properties used in the optimality analysis, then gives necessary and sufficient local optimality conditions under stated assumptions.

B Topological Properties and Optimality Conditions

C Interior Optimality Property

The section establishes an interior optimality property by smoothing probability measures and analyzing a Neumann problem. Its result rules out a lower-objective measure supported inside the support of a measure satisfying the stated local optimality condition.

C Interior Optimality Property

  • Smoothing approximates probability measures by smooth densities, with convergence in Lp for measures having an Lp density and weak convergence under compact-support conditions.For compactly supported μ, the smoothed measures are tight and converge uniformly on the function class F.Source: C Interior Optimality Property · pp. 25–26
  • For sufficiently small ε, the closed ε-neighborhood of a compact smooth submanifold has a compact smooth-manifold-with-boundary structure.This supports applying the bounded-domain analysis to the neighborhoods used in the smoothing argument.Source: C Interior Optimality Property · p. 26
  • The proof uses the weak Neumann problem, whose solution exists uniquely in V(U) and has a norm bounded by the dual norm of its linear functional.The Poincaré-Wirtinger inequality makes V(U) a Hilbert space; the Lax-Milgram theorem gives the stated solution bound.Source: C Interior Optimality Property · p. 27
  • If a measure μ′ supported inside supp(μ*) has lower LS than μ*, then μ* cannot satisfy local optimality condition (6).The proof assumes such a μ′ exists and derives that the expected score is not identically zero on supp(μ*).Source: C Interior Optimality Property · pp. 28–29

D Convergence Analysis

The convergence analysis gives an expected-accuracy guarantee for the method, while the accompanying perspectives interpret SPGD through probability-measure curves and transport maps. The updates are connected to a discretized gradient flow and, with a fixed initial measure, to functional gradient descent.

D Convergence Analysis

  • After up to t iterations, the method finds an ε-accurate solution with respect to the expectation.The guarantee follows by summing the expected objective decrease across updates.Source: D Convergence Analysis · p. 29

E Other Perspectives of SPGD

  • SPGD can be viewed both as a functional gradient method in L2(μ0) and as discretization of a gradient flow in probability-measure space.The section presents these as complementary perspectives on the method.Source: E Other Perspectives of SPGD · p. 29

Continuity Equation and its Discretization

  • The continuity equation describes probability-measure curves through a velocity field, and transport-map updates realize their discretization without explicitly restricting the update to tangent vectors.The update takes the form μ+ ← (id+ξ)♯μ, with ξ chosen from L2(μ).Source: Continuity Equation and its… · pp. 30–32

Discretization of Gradient Flow

  • Algorithm 1 is a stochastic approximation to discretizing the probability-measure gradient flow that reduces the objective.The flow combines particle velocity with the opposite-direction Fréchet differential of the objective.Source: Discretization of Gradient Flow · p. 32

E. 2 Functional Gradient Descent Perspective

With a fixed initial distribution, SPGD can be expressed as optimization over transport maps in L2 of that distribution. Its update is the stochastic functional gradient update, although the measure-space formulation remains important for understanding the problem.

E. 2 Functional Gradient Descent Perspective

  • With fixed initial measure μ0, Algorithm 1's transport maps lie in L2(μ0), so the objective can be written as LS(φ)=LS(φ♯μ0).The text notes that this translation generally does not make sense when the initial distribution varies across trials.Source: E. 2 Functional Gradient Descent… · p. 32
  • The functional differential is ES[sμ(φ(θ), x, y)], making sμ(φ(θ), x, y) the stochastic gradient for minimizing LS(φ) in L2(μ0).The objective is Fréchet differentiable with respect to φ.Source: E. 2 Functional Gradient Descent… · pp. 32–33
  • For a fixed initial distribution, SPGD is equivalent to stochastic functional gradient descent, while the probability-measure formulation remains important for understanding the problem.The text identifies the updates as equivalent and emphasizes the value of considering optimization directly over probability measures.Source: E. 2 Functional Gradient Descent… · p. 33

Related papers

Loading 1712.05438v1…