PaperlayerView exact revision on arXiv

Source-linked AI summary

A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization

Saeed Ghadimi, Andrzej Ruszczyński, Mengdi Wang

arXiv:1812.01094v2math.OC

TL;DR

The paper addresses constrained smooth composition optimization when function values and derivatives are available only through stochastic estimates. It proposes NASA, a single-timescale method, and shows that O(1/ε^2) observations suffice for an approximate stationary point, improving on the cited O(1/ε^2.25) bound for nested nonconvex optimization.

  • Problem

    The paper studies constrained, potentially nonconvex smooth composition optimization when values and derivatives of the component functions cannot be observed directly and must be estimated stochastically.

    Source: §1 · p. 2

  • Method

    NASA lifts the problem into a higher-dimensional space to estimate the composite gradient and inner-function value, using one stepsize sequence and a tailored Lyapunov function.

    Source: §1 · p. 4

  • Results

    O(1/ε^2) observations suffice for NASA to find an approximate stationary point, improving on the cited O(1/ε^2.25) complexity bound for smooth nested nonconvex stochastic optimization.

    Source: §1 · pp. 4–5

  • Takeaways & Limitations

    The convergence analysis is the same for constrained and unconstrained problems and requires no batch samples per iteration; the simplified single-level variant retains the same complexity bound.

    Source: §5 · p. 24

    The simplified single-level variant is scoped to problems with g(x) ≡ x and noisy information only about f.

    Source: §4 · p. 19

Abstract

from arXiv · show

We study constrained nested stochastic optimization problems in which the objective function is a composition of two smooth functions whose exact values and derivatives are not available. We propose a single time-scale stochastic approximation algorithm, which we call the Nested Averaged Stochastic Approximation (NASA), to find an approximate stationary point of the problem. The algorithm has two auxiliary averaged sequences (filters) which estimate the gradient of the composite objective function and the inner function value. By using a special Lyapunov function, we show that NASA achieves the sample complexity of ${\cal O}(1/\epsilon^{2})$ for finding an $\epsilon$-approximate stationary point, thus outperforming all extant methods for nested stochastic approximation. Our method and its analysis are the same for both unconstrained and constrained problems, without any need of batch samples for constrained nonconvex stochastic optimization. We also present a simplified variant of the NASA method for solving constrained single level stochastic optimization problems, and we prove the same complexity result for both unconstrained and constrained problems.

1 Introduction

The paper studies smooth nested composition optimization under stochastic-oracle access, including nonconvex constrained settings. It introduces NASA, a single-timescale method with an O(1/ε^2) sample-complexity guarantee for approximate stationarity.

1 Introduction

  • The setting permits smooth, potentially nonconvex f and g when only stochastic estimates of g(x), its Jacobian, and the gradient of f are available.The feasible set is convex and closed.Source: §1 · p. 2
  • For sequential low-rank matrix estimation, the authors formulate a nonconvex problem to which their method can be applied online to find a stationary solution.The example concerns approximating an unknown matrix from samples and has applications including image analysis and recommendation systems.Source: §1 · p. 3
  • Earlier approaches use multiple timescales, requiring the outer method to run infinitely slower; the introduction identifies no existing single-timescale method for general smooth f and g without minibatches or complexity guarantees for constrained stationarity.These requirements can decrease convergence rates and create practical difficulties.Source: §1 · p. 4
  • NASA lifts the problem to track the decision variable, composite-gradient estimate, and inner-function-value estimate using one stepsize sequence and a tailored Lyapunov function.This gives a single-timescale stochastic approximation algorithm for the composition problem.Source: §1 · p. 4
  • O(1/ε^2) observations suffice for NASA to find an approximate stationary point, improving on the prior O(1/ε^2.25) bound for smooth nested nonconvex stochastic optimization [27].The bound is also of the same order as that for stochastic gradient methods in general smooth one-level nonconvex stochastic optimization.Source: §1 · pp. 4–5
  • NASA's analysis gives the same O(1/ε^2) complexity for constrained and unconstrained problems without minibatches, a property the authors connect to online learning with one-at-a-time samples.The paper also presents a simplified single-level variant with the same order of complexity for constrained and unconstrained problems.Source: §1 · p. 5

2 The Method

NASA maintains iterates for the decision variable and running estimates of the composite gradient and inner-function value. Its optimality measure connects the estimated gradient to constrained stationarity.

2 The Method

  • The algorithm generates decision iterates x_k, average-gradient estimates z_k, and average inner-value estimates u_k.At each iteration it calls the stochastic oracle for the relevant estimates and updates the running averages.Source: §2 · p. 6
  • The averaged gradient estimate can remain biased, but its bias terms are controlled through the averaging updates; the averaged inner-value estimate's error is also driven asymptotically to zero.The convergence depends on the stepsize and regularization sequences and parameters specified later in the paper.Source: §2 · pp. 6–7
  • For constrained problems, V(x,z) measures violation of the optimality condition using the primal-dual pair; in the unconstrained case it equals ||z||^2 + ||z − ∇F(x)||^2.The paper relates this measure to the subproblem used by the method.Source: §2 · p. 7
  • The computed z_k is an online estimate of ∇F(x), whereas the comparison vectors discussed for other optimality criteria are not computable in the stochastic setting.This makes the averaged estimate available at each iteration.Source: §2 · p. 9

3 Convergence Analysis

Under the paper’s assumptions, the convergence analysis establishes an O(1/ε^2) sample complexity for constrained and unconstrained problems. It also addresses asymptotic convergence and the accuracy of the method’s auxiliary estimates.

3 Convergence Analysis

  • The analysis uses a tailored merit function and assumes Lipschitz continuity of the functions and their derivatives.The paper notes that bounded derivatives implied by Assumption 1 allow relaxing the Lipschitz assumption on the functions themselves.Source: §3 · pp. 9, 10, 17
  • Theorem 2 bounds expected optimality at a randomly selected iterate under its parameter and deterministic-stepsize conditions.The selection law for the random iterate is specified in the theorem.Source: §3 · p. 14
  • O(1/ε^2) stochastic-gradient iterations suffice for an approximate stationary point in both constrained and unconstrained problems, using one sample per iteration in the constrained case.The paper states that this matches the single-level smooth nonconvex stochastic-gradient complexity.Source: §3 · p. 17
  • The method’s second running average also provides squared-error bounds for estimating the inner value g(xR), alongside accuracy bounds for the approximate stationary point.The paper also describes the method as providing reliable gradient estimates.Source: §3 · p. 17
  • For the stochastic variational inequality example, the method attains O(ε^-2) oracle complexity without assuming monotonicity.The paper attributes the approach to a one-level method for a merit function involving the lifted gap function and a projection mapping.Source: §3 · p. 18
  • With the stated stepsize condition, every accumulation point almost surely satisfies the theorem’s conditions; convergent subsequences recover a stationary point, its composite gradient, and the inner-function value.The sequence’s gradient and inner-value estimation errors converge to zero almost surely.Source: §3 · p. 18

4 Dual averaging with constraints

For single-level stochastic optimization, the paper simplifies NASA to an averaged stochastic approximation method. The analysis gives convergence guarantees for constrained and unconstrained problems and describes a trade-off under a relaxed oracle assumption.

4 Dual averaging with constraints

  • The simplified method retains O(1/ε^2) complexity for constrained and unconstrained problems without forming mini-batches, and its stepsize policy does not depend on problem parameters.The paper also allows random, history-dependent stepsizes in this parameter-free setting.Source: §4 · pp. 19, 21
  • With g(x) ≡ x, Algorithm 2 replaces the stochastic Jacobian estimate with the identity and removes the averaged inner-value sequence.It updates a running average of stochastic gradients.Source: §4 · p. 19
  • Algorithm 2 outputs an estimate zR of ∇f(xR) without extra samples, and max(1,βk)∥yk − xk∥ can serve as an online solution-quality certificate.The paper states this is relevant to both constrained and unconstrained problems.Source: §4 · p. 21
  • The same-order convergence rate holds under a relaxed bounded-variance oracle assumption, but βk then depends on problem parameters.The paper contrasts this with the parameter-free result under the earlier oracle assumption.Source: §4 · pp. 23–24
  • Under the stated stepsize conditions, every accumulation point of Algorithm 2 almost surely satisfies the theorem’s conditions.This asymptotic result is stated separately from the finite-iteration complexity guarantees.Source: §4 · p. 24

5 Concluding Remarks

The conclusion reports that the method matches the order of the best-known single-level stochastic-gradient sample-complexity bound. Its analysis applies to constrained and unconstrained problems without batches, and a simplified single-level variant retains the same complexity bound.

  • The method’s sample-complexity bound for approximate stationarity is in the same order as the best-known stochastic-gradient bound for single-level stochastic optimization.Source: §5 · p. 24
  • The convergence analysis is the same for constrained and unconstrained problems and does not require batches of samples per iteration.Source: §5 · p. 24
  • A simplified parameter-free NASA variant for single-level problems has the same complexity bound whether or not constraints are present.Source: §5 · p. 24
Loading 1812.01094v2…