PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Convexity: Stochastic Quasi-Convex Optimization

Elad Hazan, Kfir Y. Levy, Shai Shalev-Shwartz

arXiv:1507.02030v3cs.LGmath.OC

TL;DR

SGD is effective for convex Lipschitz objectives but can perform unsatisfactorily on non-convex problems with plateaus and sharp cliffs. The paper analyzes stochastic normalized gradient descent for locally quasi-convex and locally Lipschitz objectives, proving convergence guarantees and reporting supporting experiments.

  • Problem

    SGD can perform unsatisfactorily on non-convex objectives exhibiting very small gradients and exceedingly high gradients.

  • Method

    The paper analyzes stochastic normalized gradient descent (SNGD) for locally quasi-convex and locally Lipschitz objectives, using an SLQC-based framework.

  • Results

    SNGD obtains an ϵ-optimal minimum in O(1/ϵ2) iterations for locally quasi-convex functions, with a faster O(1/ϵ) rate when objectives are locally smooth.

  • Takeaways & Limitations

    The work presents a provable gradient-based algorithm for stochastic quasi-convex optimization and reports experiments supporting its theoretical guarantees.

  • Takeaways & Limitations

    A gap remains between the upper and lower bounds on the minibatch size sufficient for SNGD to provably converge.

Abstract

from arXiv · show

Stochastic convex optimization is a basic and well studied primitive in machine learning. It is well known that convex and Lipschitz functions can be minimized efficiently using Stochastic Gradient Descent (SGD). The Normalized Gradient Descent (NGD) algorithm, is an adaptation of Gradient Descent, which updates according to the direction of the gradients, rather than the gradients themselves. In this paper we analyze a stochastic version of NGD and prove its convergence to a global minimum for a wider class of functions: we require the functions to be quasi-convex and locally-Lipschitz. Quasi-convexity broadens the con- cept of unimodality to multidimensions and allows for certain types of saddle points, which are a known hurdle for first-order optimization methods such as gradient descent. Locally-Lipschitz functions are only required to be Lipschitz in a small region around the optimum. This assumption circumvents gradient explosion, which is another known hurdle for gradient descent variants. Interestingly, unlike the vanilla SGD algorithm, the stochastic normalized gradient descent algorithm provably requires a minimal minibatch size.

1 Introduction

The paper targets stochastic non-convex objectives with plateaus, cliffs, and potentially unbounded gradients by analyzing stochastic normalized gradient descent. It introduces locally-quasi-convex optimization, proves convergence guarantees, and identifies a necessary minibatch-size condition.

  • Motivation: SGD can perform poorly on non-convex objectives exhibiting both very small gradients on plateaus and exceedingly high gradients on cliffs.These phenomena are reported in certain non-convex optimization problems, including deep-network training.
  • Approach: SNGD applies normalized gradient updates to locally-quasi-convex and locally-Lipschitz objectives, targeting robustness to plateaus and gradient explosion.The paper defines the function family and proves SNGD is suitable for optimizing such objectives.
  • Guarantees: O(1/ϵ^2) iterations suffice for NGD to find an ϵ-optimal minimum under local-quasi-convexity, while local smoothness near the optimum yields O(1/ϵ).The local-Lipschitz condition need only hold in an Ω(ϵ)-region, and the faster rate assumes smoothness in an Ω(√ϵ)-region.
  • Applications: The stochastic setup captures GLM regression, for which SNGD converges within O(1/ϵ^2) iterations to an ϵ-optimal minimum.This establishes a stochastic optimization setting beyond the convex case described in the introduction.
  • Stochasticity: SNGD’s positive convergence result requires a minimally large minibatch, and an undersized minibatch can make the algorithm diverge.The paper also reports experiments supporting its theoretical guarantees and accelerated convergence.
  • Prior Work: The paper addresses a gap in prior work by providing theoretical results for stochastic NGD and locally-quasi-convex or locally-Lipschitz functions.Earlier approaches to plateaus and gradient explosion improved training in practice but did not provide better convergence guarantees.

2 Definitions and Notations

This section introduces the paper’s notation and local regularity assumptions, then characterizes quasi-convexity through gradient directions and convex sublevel sets. Local Lipschitzness and smoothness restrict these conditions to neighborhoods around a reference point.

  • Notation: The paper uses the Euclidean norm, d-dimensional Euclidean balls B_d(x,r), the unit ball B_d, and [N] for {1,...,N}.These symbols establish the geometric and indexing notation used throughout the paper.
  • Assumptions: The analysis assumes differentiability but does not generally impose a bound on gradient norms.This leaves room for objectives whose gradients may be unbounded away from the optimum.
  • Local Regularity: A function is locally-Lipschitz when its Lipschitz condition holds for every pair of points in a small ball around z.The corresponding local-smoothness condition is likewise imposed only within a ball around z.
  • Illustration: The illustrated quasi-convex locally-Lipschitz function contains plateaus and cliffs.These features motivate the paper’s local assumptions and normalized-gradient analysis.
  • Quasi-Convexity: Quasi-convexity requires the defining gradient-based inequality for any x,y with f(y)≤f(x), and equivalently requires every α-sublevel set to be convex.The paper notes that the opposite gradient gives a global descent direction.
  • Quasi-Convexity: Strict quasi-convexity additionally requires every non-minimizing point to have a nonzero gradient.Thus, gradients may vanish only at global minima under this stronger condition.

3 Local-Quasi-Convexity

The paper introduces local-quasi-convexity, a broader unimodality property that supports exploration or exploitation, and applies it to idealized and noisy GLM regression. These objectives can be SLQC even when they are not quasi-convex, enabling ε-optimal optimization with stochastic methods.

  • Local-Quasi-Convexity: Local-quasi-convexity extends quasi-convexity to capture unimodal functions that may include plateaus and saddle points.It is designed to support either exploration through a global descent direction or exploitation when the iterate is already approximately optimal.
  • Local-Quasi-Convexity: The SLQC condition requires either approximate optimality or a gradient direction satisfying an inequality toward a neighborhood of the optimum.The second case uses a nonzero gradient and constrains its inner product with points in B(z, ϵ/κ).
  • 3.1.1 The Idealized GLM: The idealized sigmoid GLM error is SLQC but not generally quasi-convex.This places the model within the paper’s broader function class despite failing ordinary quasi-convexity.
  • 3.1.2 The Noisy GLM: The noisy GLM model assumes a predictor w* whose conditional mean output follows an activation function, with expected error minimized at w*.Its empirical error becomes SLQC with high probability after a sample size scaling as 1/ϵ2, under the stated sigmoid and norm assumptions.
  • 3.1.2 The Noisy GLM: The fixed-point SLQC requirement yields a sample complexity independent of the dimension.Requiring the property for every point simultaneously would instead make the sample bound depend on d.

4 NGD for Locally-Quasi-Convex Optimization

The paper analyzes NGD for SLQC objectives and shows that normalizing gradients supports convergence when gradients may be very small or very large. It obtains O(1/ϵ2) convergence under local Lipschitzness and a faster local-smoothness rate.

  • 4 NGD for Locally-Quasi-Convex Optimization: NGD normalizes gradients before updating, using direction rather than gradient magnitude.This design targets plateaus with tiny gradients and cliffs with exploding gradients.
  • 4 NGD for Locally-Quasi-Convex Optimization: For an (ϵ, κ, x*)-SLQC objective, NGD returns an ϵ-optimal averaged iterate after T ≥ κ2∥x1 −x*∥2/ϵ2 iterations.The theorem uses learning rate η = ϵ/κ.
  • 4.1 Locally-Lipschitz/Smooth Quasi-Convex Optimization: Strict quasi-convexity combined with local Lipschitzness implies SLQC and gives O(1/ϵ2) NGD convergence.The guarantee requires Lipschitzness only in an ϵ/G-radius region around the optimum.
  • 4.1 Locally-Lipschitz/Smooth Quasi-Convex Optimization: With local smoothness, NGD achieves the faster rate O(1/ϵ).The stated iteration bound is T ≥ β∥x1 −x*∥2/2ϵ under local smoothness in the corresponding neighborhood.
  • 4.1 Locally-Lipschitz/Smooth Quasi-Convex Optimization: NGD remains guaranteed to reach an ϵ-optimal point even when gradients and second derivatives are arbitrarily large outside a small neighborhood of the optimum.The locally Lipschitz and locally smooth cases retain their respective iteration guarantees despite this behavior.

5 SNGD for Stochastic SLQC Optimization

SNGD normalizes stochastic gradients and, under stochastic SLQC and boundedness assumptions, obtains high-probability approximate optimization with polynomial query complexity. The guarantees extend to locally Lipschitz objectives, but require sufficiently large minibatches and leave a convergence-rate gap.

  • Algorithm and setting: The stochastic setup samples minibatches, queries their gradients, and assumes each minibatch average is SLQC with high probability and uniformly M-bounded.The SLQC condition must hold across all T iterations once the minibatch size exceeds b0(ϵ, δ, T).
  • Applications and assumptions: For noisy GLM regression, minibatches of size b ≥ Ω(log(T/δ)/ϵ2) make the average minibatch function SLQC at every iteration with probability at least 1−δ.This instantiates the stochastic SLQC assumption for a concrete noisy generalized linear model.
  • Applications and assumptions: Local-quasi-convexity plausibly covers expected sums of quasi-convex functions sharing common or nearby global minima, although such sums need not themselves be quasi-convex.In the general case, the number of local minima can grow exponentially with dimension d.
  • Algorithm and setting: SNGD normalizes minibatch gradients, using direction rather than magnitude to address plateaus and cliffs under the SLQC assumption.The update uses a normalized gradient with learning rate η.
  • Main guarantees: With T ≥ κ2∥x1−x∗∥2/(2ϵ2) and a sufficiently large minibatch, SNGD returns an average iterate satisfying f(x̄T)−f(x∗) ≤ 3ϵ with probability at least 1−2δ.The proof combines an SLQC progress lemma with concentration bounds relating minibatch objectives to the population objective.
  • Main guarantees: Arbitrarily large gradients outside a local region around the optimum are compatible with an ϵ-optimality guarantee, while the required minibatch size is Ω(1/ϵ2).The paper contrasts this with convex SGD, where minibatch size one suffices, and notes that the gap between O(1/ϵ2) and O(1/ϵ) remains open.

6 Experiments

The experiments evaluate SNGD on a one-hidden-layer ReLU network trained on MNIST, comparing it with minibatch SGD and stochastic Nesterov acceleration. SNGD performs comparably to Nesterov’s method and improves significantly with larger minibatches.

  • Experimental setup: The study trains a one-hidden-layer ReLU network with 100 units on MNIST using square loss.The experiment targets a hard non-convex optimization task.
  • Experimental setup: SNGD is compared with minibatch SGD and a stochastic variant of Nesterov’s accelerated gradient method.All methods use minibatches of size 100 in the scheme comparison.
  • Scheme comparison: SNGD performs comparably to Nesterov’s method, while MSGD converges relatively slowly.The comparison uses a constant step size for SNGD and decaying step sizes for the other methods.
  • Minibatch-size study: SNGD performance improves significantly as minibatch size increases.Figure 2(c) examines the objective for different minibatch sizes.

7 Discussion

The paper presents a provable gradient-based approach for stochastic quasi-convex optimization, extending stochastic convex optimization machinery to a tractable non-convex setting. Its discussion also identifies an unresolved gap in the minibatch-size bounds for SNGD.

  • SNGD is presented as the first provable gradient-based algorithm for stochastic quasi-convex optimization.
  • A remaining question is the gap between the upper and lower bounds on minibatch size sufficient for SNGD to provably converge.
  • The supplied proof establishes that the example function g is (ϵ, 1, x∗)-SLQC throughout [−10, 10]2 for ϵ ∈ (0, 1].

C Proof of Lemma 3.1

The proof shows that the idealized sigmoid GLM error is SLQC despite not generally being quasi-convex, using monotonicity and Lipschitz properties of the sigmoid.

  • The sigmoid GLM error is shown to be (ϵ, e^W, w∗)-SLQC for all ϵ > 0 and w ∈ B^d(0, W).
  • The argument bounds the activation change using the distance between v and w∗ and the constraint ∥w∥, ∥w∗∥ ≤ W.
  • The proof uses that the sigmoid activation is monotonically increasing and 1/4-Lipschitz.
  • The error function is generally not quasi-convex: two points have error at most 0.018, while their midpoint has error at least 0.019.

D Proof of Lemma 3.2

The proof extends the SLQC property from the idealized GLM setting to noisy empirical error through concentration, while local Lipschitzness supplies a low-error neighborhood around the optimum.

  • For noisy data, the empirical error analysis represents deviations as independent, zero-mean, bounded random variables.
  • The concentration argument requires m ≥ 8e^2W(W+1)^2ϵ^-2 log(1/δ) samples.
  • Local-Lipschitzness implies that when f(x) exceeds f(z) by more than ϵ, the ball B(z, ϵ/G) lies within the sublevel set of x.
  • Combining this neighborhood property with strict quasi-convexity establishes the SLQC conditions, including a nonzero gradient.
  • If f(x) − f(x∗) ≥ ϵ, every y in B(x∗, ϵ/G) satisfies f(x) − f(y) ≥ 0.

F Proof of Theorem 4.2

The proof of the faster smooth-function result follows the earlier theorem’s structure, replacing its neighborhood argument with a locally smoothness-based lemma.

  • A key lemma is introduced to obtain faster rates for smooth functions.
  • The lemma assumes a global minimum x∗ and local smoothness with parameters β and 2ϵ/β.
  • Under these assumptions, points whose objective gap exceeds ϵ are related to a neighborhood around x∗ through local smoothness.
  • Theorem 4.2 uses the same proof structure as Theorem 4.1, substituting the local-smoothness lemma when f(x_t) − f(x∗) ≥ ϵ.
  • The proof details are omitted after this description of the substitution.

G Proof of Lemma 5.3

The proof models absorption probabilities through stationary Markov-chain recurrences, then solves them with an exponential ansatz to identify their decay parameter.

  • The Markov property yields recursive equations relating each absorption probability to neighboring states.The recurrence applies for i > 1, with a separate boundary equation at i = 1.
  • Assuming α_i = c_0ρ^i converts the recurrence into an equation for the decay parameter ρ.
  • The only nontrivial solution is ρ = p/(1−p), and the boundary condition gives c_0 = 1.

H A Broader Notion of Local-Quasi-Convexity

The paper broadens local-quasi-convexity by allowing direction oracles, extending the NGD/SNGD guarantees to settings such as the γ-margin Perceptron.

  • Scope and motivation: Definition 3.1 covers a rich function family but excludes piecewise-constant quasi-convex objectives such as zero-one loss and the Perceptron problem.
  • Direction-oracle formulation: A direction oracle supplies a global ascent or descent direction when direct gradients are unavailable or ineffective.The paper presents this oracle as a proxy for the gradient.
  • Direction-oracle formulation: SLQC permits a nonzero oracle direction whose inner product with every point near the reference minimizer is nonpositive.
  • Direction-oracle formulation: Definition 3.1 is a special case of the direction-oracle formulation, and NGD/SNGD guarantees extend to SLQC functions with such oracles.
  • γ-margin Perceptron: Because the Perceptron error is SLQC with respect to the oracle, Algorithm 1 finds an ϵ-optimal minimum within poly(1/ϵ) iterations.
  • γ-margin Perceptron: In the γ-margin Perceptron setting, the error function is SLQC with respect to the specified direction oracle at every w.The result holds with parameters (ϵ, 2/γ, w*) for ϵ ∈ (0, 1).
Loading 1507.02030v3…