PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Frank-Wolfe Methods for Nonconvex Optimization

Sashank J. Reddi, Suvrit Sra, Barnabas Poczos, Alex Smola

arXiv:1607.08254v2math.OCcs.LGstat.ML

TL;DR

Nonconvex Frank-Wolfe methods lack sufficient convergence understanding, especially when projections are costly and classical finite-sum Frank-Wolfe is expensive. The paper develops stochastic and variance-reduced Frank-Wolfe algorithms, proving faster finite-sum rates and improved stochastic rates. These results establish projection-free methods with improved theoretical efficiency in the studied settings.

  • Problem

    Nonconvex Frank-Wolfe methods have limited convergence analysis, while classical finite-sum Frank-Wolfe can be prohibitively expensive for large n.

  • Method

    The paper analyzes stochastic Frank-Wolfe and develops variance-reduced finite-sum and stochastic variants using variance-reduction ideas.

  • Results

    Svfw and SagaFw are provably faster than deterministic Fw by factors of n1/3 and n2/3, respectively, while stochastic variance-reduced variants improve Sfw’s convergence rate.

  • Takeaways & Limitations

    The results provide theoretically improved projection-free methods for nonconvex stochastic and finite-sum optimization under the paper’s assumptions.

  • Takeaways & Limitations

    The tightness of the reported convergence rates remains an open problem, and the step-size rules may require estimates of parameters such as L, D, and F(x0)−F(x∗).

Abstract

from arXiv · show

We study Frank-Wolfe methods for nonconvex stochastic and finite-sum optimization problems. Frank-Wolfe methods (in the convex case) have gained tremendous recent interest in machine learning and optimization communities due to their projection-free property and their ability to exploit structured constraints. However, our understanding of these algorithms in the nonconvex setting is fairly limited. In this paper, we propose nonconvex stochastic Frank-Wolfe methods and analyze their convergence properties. For objective functions that decompose into a finite-sum, we leverage ideas from variance reduction techniques for convex optimization to obtain new variance reduced nonconvex Frank-Wolfe methods that have provably faster convergence than the classical Frank-Wolfe method. Finally, we show that the faster convergence rates of our variance reduced methods also translate into improved convergence rates for the stochastic setting.

1 Introduction

The paper addresses the limited understanding of nonconvex Frank-Wolfe methods by developing stochastic and variance-reduced algorithms for constrained optimization. Its methods target projection-free optimization where classical approaches are costly or unavailable.

  • Frank-Wolfe avoids potentially expensive projections by using a linear oracle, making it attractive for structured constraints.Projection-based methods can be impractical for domains such as trace-norm balls and base polytopes.
  • Nonconvex Frank-Wolfe applicability and non-asymptotic convergence were largely unstudied despite Frank-Wolfe’s success in convex optimization.
  • The paper proposes Sfw for nonconvex stochastic problems and Svfw and SagaFw as variance-reduced methods for nonconvex finite-sum problems.The finite-sum methods are based on Svrg and Saga ideas.
  • Svfw and SagaFw are proved faster than deterministic Fw by factors of n1/3 and n2/3, respectively.
  • The proposed stochastic variants provide a theoretical improvement over existing stochastic nonconvex Frank-Wolfe methods.The authors describe this as the first theoretical improvement for stochastic variants in nonconvex optimization.

2 Preliminaries

The paper formulates stochastic and finite-sum oracle models, defines the Frank-Wolfe gap as its nonconvex stationarity criterion, and motivates faster methods by the cost of classical Frank-Wolfe. Classical Fw requires O(n/ϵ2) IFO calls in finite sums, which is expensive when n is large.

  • The paper studies stochastic objectives and finite-sum objectives, with n denoting the number of component functions in the finite-sum case.
  • The analysis assumes differentiability, smoothness, and a convex compact domain; stochastic functions additionally have bounded gradients.
  • The Frank-Wolfe gap is used because it characterizes stationarity for nonconvex constrained problems and upper-bounds suboptimality for convex functions.
  • SFO, IFO, and LO complexity count oracle calls needed to obtain an ϵ-accurate solution measured by E[G(x)] ≤ ϵ.
  • Classical Fw computes the full gradient and moves toward a minimizer of a linearized objective at each iteration.
  • O(n/ϵ2) IFO complexity makes classical Fw prohibitively expensive for large n, motivating faster stochastic and variance-reduced methods.

3 Algorithms

The paper develops stochastic and variance-reduced Frank-Wolfe methods for nonconvex optimization, analyzing their convergence in stochastic and finite-sum settings. The stochastic method attains stated SFO and LO complexity bounds, while variance reduction improves finite-sum convergence rates.

  • Stochastic setting: Sfw adapts Frank-Wolfe to the nonconvex stochastic setting by replacing the unavailable full gradient with a Robbins-Monro gradient approximation.The algorithm uses independently sampled data to obtain an unbiased gradient estimate and randomly selects an iterate as output.
  • Stochastic setting: Under the stated theorem assumptions and parameter choices, Sfw has SFO complexity O(1/ϵ4) and LO complexity O(1/ϵ2).The result applies when f is G-Lipschitz and F is L-smooth.
  • Stochastic setting: The Sfw analysis requires O(1/ϵ2) minibatch size per iteration and O(1/ϵ2) iterations to obtain an ϵ-accurate solution.The paper also notes that decreasing step sizes and increasing minibatch sizes can yield an essentially similar result.
  • Finite-sum setting: The stochastic convergence result also applies to the finite-sum setting, but variance reduction can significantly improve its convergence rates.The finite-sum methods build on variance-reduced gradient approximations.
  • Finite-sum setting: Svfw and SagaFw are variance-reduced nonconvex Frank-Wolfe algorithms based on Svrg and Saga, respectively.Their parameters can be selected to obtain faster convergence rates than deterministic Frank-Wolfe.

Svfw Algorithm

Svfw is an epoch-based variance-reduced Frank-Wolfe method that periodically computes a full gradient and uses it to control inner-loop stochastic-gradient variance. With m = ⌈n1/3⌉, its stated IFO complexity is O(n + n2/3/ϵ2), while its LO complexity is O(1/ϵ2).

  • Svfw method: Svfw computes a full gradient at each epoch and uses it to control stochastic-gradient variance during the inner loop.When the epoch size m equals 1, Svfw reduces to classical Frank-Wolfe.
  • Algorithm: Svfw samples minibatches within each inner iteration and updates the iterate using a Frank-Wolfe direction based on the variance-reduced gradient.The algorithm outputs an iterate selected uniformly at random from the inner-loop iterates.
  • Svfw method: The variance-reduced gradient-error term has lower variance than the corresponding stochastic Frank-Wolfe term, leading to faster convergence rates.The analysis compares ∇F(xt) − ˜∇t with the higher-variance stochastic term ∇F(xt) − ∇t.
  • Convergence analysis: The method analyzes iterates across epochs and inner iterations, using a Lyapunov function and telescoping bounds to establish convergence.The theorem assumes the total number of inner iterations is a multiple of the epoch size.
  • Complexity: With m = ⌈n1/3⌉, Svfw achieves IFO complexity O(n + n2/3/ϵ2) and LO complexity O(1/ϵ2).The epoch cost balances full-gradient computation against minibatch costs, with amortized per-iteration IFO complexity O(n2/3).

SagaFw Algorithm

SagaFw is a purely incremental variance-reduced Frank-Wolfe method that avoids full-gradient calculations by updating an average gradient vector. Its finite-sum complexity depends on minibatch and iteration choices, with improved bounds over classical Frank-Wolfe.

  • SagaFw Algorithm: SagaFw is a purely incremental method based on the SAGA algorithm and avoids calculating full gradients.It updates the average gradient vector at each iteration.
  • SagaFw Algorithm: SagaFw maintains additional vectors α_i, incurring worst-case storage cost O(nd), reducible to O(n) in several practical cases.The storage trade-off supports incremental updates without full-gradient computation.
  • SagaFw Algorithm: For T ≥ n and b = ⌈n^1/3⌉, SagaFw has IFO complexity O(n + n^1/3/ϵ^2) and LO complexity O(1/ϵ^2).These bounds follow from the stated parameter setting and θ(b,n,T) bound.
  • SagaFw Algorithm: With T ≥ n^3/2 and b = 1, SagaFw has IFO complexity O(n^3/2 + 1/ϵ^2).The stated condition yields θ(b,n,T) ≤ 5/2.

4 Variance Reduction in Stochastic Setting

The paper applies variance reduction to stochastic Frank-Wolfe by forming a finite-sum problem from sampled data and then running Svfw or SagaFw. The resulting stochastic variants improve SFO complexity over Sfw while retaining O(1/ϵ^2) LO complexity.

  • 4 Variance Reduction in Stochastic Setting: Svfw-S and SagaFw-S construct a finite-sum problem from sampled data and apply Svfw or SagaFw to it.Figure 2 presents the two stochastic variants.
  • 4 Variance Reduction in Stochastic Setting: Svfw-S and SagaFw-S have SFO complexities O(1/ϵ^10/3) and O(1/ϵ^8/3), respectively.The result is stated under the assumptions of Theorem 5.
  • 4 Variance Reduction in Stochastic Setting: Both Svfw-S and SagaFw-S have LO complexity O(1/ϵ^2).The linear-oracle complexity is the same for both stochastic variance-reduced methods.
  • 4 Variance Reduction in Stochastic Setting: Svfw-S and SagaFw-S have better SFO complexity than Sfw.The comparison follows from Corollary 4 and Corollary 1.

5 Discussion

The discussion compares the methods’ complexity rates and identifies limitations in interpreting them across convergence criteria and analyses. It also notes that step-size parameter knowledge can be removed at the cost of slightly worse constants.

  • 5 Discussion: Sfw has SFO complexity O(1/ϵ^4) and LO complexity O(1/ϵ^2) under the paper’s convergence criterion.The criterion differs from the one used in the cited nonconvex SGD analysis.
  • 5 Discussion: The tightness of the stochastic convergence rates remains an open problem, and their precise relationship to another convergence criterion is unresolved.The paper also compares the rates with online and convex stochastic Frank-Wolfe results.
  • 5 Discussion: Svfw and SagaFw have IFO and LO dependence O(1/ϵ^2), while improving dependence on n over classical Frank-Wolfe by factors n^1/3 and n^2/3, respectively.The gap between the two variance-reduced rates remains open.
  • 5 Discussion: Choosing β = 2(F(x0) − F(x∗)) removes step-size dependence on parameters such as L, D, and F(x) − F(x∗).This choice incurs only slightly worse constants in the convergence rate.

Appendix

The appendix supplies smoothness, variance, and independence lemmas used to analyze the stochastic and finite-sum Frank-Wolfe methods. It then bounds the variance of the gradient estimates and updates underlying Svfw and SagaFw.

  • Appendix: For an L-smooth function, the appendix invokes the classical smoothness bound used in the convergence analysis.This establishes the basic inequality needed for later estimates.
  • Appendix: A stochastic-gradient lemma bounds the variance of an empirical gradient estimate under bounded component gradients.The setting assumes F(x) = E_z[f(x,z)] and an upper bound G on component gradient norms.
  • Appendix: Additional lemmas bound the variance of the gradient estimates used by Svfw and SagaFw.The SagaFw bound differs because its variance term involves α_i.
  • Appendix: The appendix uses a mean-zero independent-variable lemma and Jensen’s inequality to control variance terms.These tools recur in the proofs of the stochastic gradient and variance-reduction bounds.
Loading 1607.08254v2…