PaperlayerView exact revision on arXiv

Source-linked AI summary

On Stochastic Gradient and Subgradient Methods with Adaptive Steplength Sequences

Farzad Yousefian, Angelia Nedić, Uday V. Shanbhag

arXiv:1105.4549v1math.OCeess.SY

TL;DR

The paper addresses limited guidance for choosing stochastic-approximation stepsizes and the difficulty of applying such methods to nonsmooth stochastic problems. It develops adaptive stepsize rules and local smoothing, showing that smoothing yields Lipschitz gradients with a bound growing as √n and that a recursive rule minimizes the error over a prescribed choice set.

  • Problem

    Standard stochastic approximation offers limited guidance for choosing stepsize sequences, while nonsmooth random integrands hinder direct application of known methods.

  • Method

    The paper develops two adaptive stepsize rules and a local smoothing technique producing a globally differentiable approximation with Lipschitz-continuous gradients.

  • Results

    The smoothed gradient Lipschitz constant grows at the rate of √n, and the recursive scheme minimizes the error over the prescribed choice set.

  • Takeaways & Limitations

    Local smoothing supports stochastic approximation for nonsmooth objectives, while the recursive rule provides an error-minimizing adaptive stepsize sequence.

Abstract

from arXiv · show

The performance of standard stochastic approximation implementations can vary significantly based on the choice of the steplength sequence, and in general, little guidance is provided about good choices. Motivated by this gap, in the first part of the paper, we present two adaptive steplength schemes for strongly convex differentiable stochastic optimization problems, equipped with convergence theory. The first scheme, referred to as a recursive steplength stochastic approximation scheme, optimizes the error bounds to derive a rule that expresses the steplength at a given iteration as a simple function of the steplength at the previous iteration and certain problem parameters. This rule is seen to lead to the optimal steplength sequence over a prescribed set of choices. The second scheme, termed as a cascading steplength stochastic approximation scheme, maintains the steplength sequence as a piecewise-constant decreasing function with the reduction in the steplength occurring when a suitable error threshold is met. In the second part of the paper, we allow for nondifferentiable objective and we propose a local smoothing technique that leads to a differentiable approximation of the function. Assuming a uniform distribution on the local randomness, we establish a Lipschitzian property for the gradient of the approximation and prove that the obtained Lipschitz bound grows at a modest rate with problem size. This facilitates the development of an adaptive steplength stochastic approximation framework, which now requires sampling in the product space of the original measure and the artificially introduced distribution. The resulting adaptive steplength schemes are applied to three stochastic optimization problems. We observe that both schemes perform well in practice and display markedly less reliance on user-defined parameters.

I. INTRODUCTION

The paper develops adaptive stochastic gradient and subgradient methods to reduce reliance on user-chosen stepsize sequences. It proposes two adaptive rules for differentiable problems and local smoothing for nondifferentiable objectives.

  • Adaptive stepsize rules: The paper develops and analyzes two adaptive stepsize rules for strongly convex stochastic optimization with differentiable random integrands and Lipschitz gradients.The two rules are introduced under assumptions that include differentiability and a Lipschitzian gradient condition.
  • Motivation: The paper addresses limited guidance on choosing stochastic-approximation stepsize sequences by proposing rules that use problem information.The motivation is to construct convergent schemes whose stepsizes better reflect the problem setting.
  • Recursive stepsize rule: The recursive rule selects each stepsize from the previous stepsize and problem parameters while providing global convergence and rate estimates.Its construction minimizes a bound on expected error per iteration.
  • Cascading stepsize rule: The cascading rule keeps the stepsize constant between updates, then lowers it when iterates reach an appropriate error threshold, with convergence support.The resulting sequence is piecewise constant with drops at particular epochs.
  • Local smoothing: For nondifferentiable objectives, local smoothing produces a globally differentiable approximation with Lipschitz-continuous gradients.The resulting gradient Lipschitz constant grows at the rate of √n with problem dimension n and supports a stochastic approximation framework.
  • Numerical evaluation: The paper reports numerical results from applying the proposed stepsize rules and smoothing technique to three test problems.The experiments are described as applications of the framework developed in the paper.

A. Problem Formulation

The paper formulates constrained stochastic optimization with convex expected objectives and stochastic gradient errors, then motivates adaptive steplength methods for differentiable and nonsmooth settings.

  • A. Problem Formulation: The problem minimizes an expected stochastic objective over a nonempty feasible set X contained in an open domain D.
  • A. Problem Formulation: The feasible set is convex and closed, each sample function is convex, and the expected objective is finite throughout D.
  • A. Problem Formulation: For differentiable objectives, the stochastic gradient error is the sampled gradient minus its expectation and has conditional mean zero.
  • A. Problem Formulation: The analysis assumes positive stepsizes and almost-surely bounded stochastic gradient errors, using Robbins–Siegmund-type results for convergence.
  • A. Problem Formulation: The paper focuses on strongly convex objectives with Lipschitz gradients when developing adaptive steplength schemes.
  • B. Adaptive Stochastic Approximation Schemes: Prior stochastic approximation work leaves the choice of steplength sequence challenging, despite established sequences such as a/k and adaptive data-based variants.
  • B. Adaptive Stochastic Approximation Schemes: The proposed adaptive schemes use algorithm and problem parameters rather than sample points to construct steplengths.
  • C. Smoothing Techniques: For nonsmooth objectives, the paper adopts local averaging through mollifiers to obtain smoothed approximations and pursue an alternative to sequentially solving smoothed problems.

III. A RECURSIVE STEPLENGTH STOCHASTIC APPROXIMATION SCHEME

The recursive stochastic approximation framework addresses diminishing-steplength implementation by deriving a recursive rule from expected-error bounds for strongly convex smooth problems.

  • III. A RECURSIVE STEPLENGTH STOCHASTIC APPROXIMATION SCHEME: The RSA scheme makes each steplength a function of the previous steplength and problem parameters.
  • III. A RECURSIVE STEPLENGTH STOCHASTIC APPROXIMATION SCHEME: Standard diminishing-steplength methods require summability conditions, while the choice of a constant such as θ in γk = θ/k can strongly affect performance.
  • III. A RECURSIVE STEPLENGTH STOCHASTIC APPROXIMATION SCHEME: The convergence analysis relies on conditional zero-mean gradient errors, projection properties, co-coercivity, and strong convexity.
  • III. A RECURSIVE STEPLENGTH STOCHASTIC APPROXIMATION SCHEME: Under convexity and Lipschitz-gradient assumptions, the stochastic iterates converge almost surely to an optimal solution or an optimal-set point.
  • III. A RECURSIVE STEPLENGTH STOCHASTIC APPROXIMATION SCHEME: For strongly convex objectives with Lipschitz gradients, the method converges almost surely to the unique optimal solution under an admissible stepsize bound.

B. A recursive steplength scheme

The recursive steplength scheme minimizes a recursively defined error bound by updating each steplength from the preceding one and problem parameters.

  • B. A recursive steplength scheme: Choosing an effective diminishing steplength is framed as minimizing the recursively defined error bound at each iteration.
  • B. A recursive steplength scheme: The scheme adaptively optimizes steplengths from iteration to iteration through the recursively updated error model.
  • B. A recursive steplength scheme: The next steplength can minimize the next-iteration error as a function of only the most recent steplength.
  • B. A recursive steplength scheme: The error recursion uses the strong-convexity parameter η and an upper bound ν^2 for second moments of the error norms.
  • B. A recursive steplength scheme: The resulting sequence minimizes the error over the prescribed set Gk of admissible steplength vectors.
  • B. A recursive steplength scheme: The minimizing sequence is also a stationary point of the error function over the admissible set.

C. Convergence theory

The convergence theory establishes that the recursive scheme produces valid diminishing steplengths and converges almost surely under smooth and nonsmooth convexity conditions.

  • C. Convergence theory: The proposed RSA approximation scheme yields a positive nonincreasing steplength sequence whose limit is zero and whose required sums are finite.
  • C. Convergence theory: The recursive steplength sequence generated by the scheme satisfies the assumptions needed for global convergence.
  • C. Convergence theory: The convergence result also applies to a self-adaptive stepsize sequence and yields almost-sure convergence to a random point in the optimal set.
  • C. Convergence theory: Under differentiability, Lipschitz gradients, strong convexity, and the stated initialization, RSA converges almost surely to the unique optimal solution.
  • C. Convergence theory: For nonsmooth objectives, convergence is established under compactness, strong convexity, and a bounded subgradient-moment condition.

IV. A CASCADING STEPLENGTH STOCHASTIC APPROXIMATION SCHEME

The cascading steplength stochastic approximation scheme reduces steplengths at error-based epochs while keeping them constant between reductions. Under stated smoothness, convexity, and compactness conditions, the scheme is well defined and targets progressively smaller persistent errors.

  • Scheme structure: The cascading scheme uses a diminishing steplength framework with constant-steplength regimes separated by reductions at selected epochs.Regime durations form an increasing sequence, and each reduction starts a new regime.
  • Algorithm: Each regime duration Kt is defined by the largest iteration count for which the transient error remains above the persistent error.This threshold rule determines when the next cascading step occurs.
  • Error control: Reducing the steplength decreases the persistent error, while the transient error contracts during each fixed-steplength regime.The persistent error increases with γ, whereas the transient term is reduced through the contraction factor q(γ).
  • Algorithm: The CSA scheme initializes a steplength and then repeatedly reduces it by a factor θ after the transient error reaches the persistent-error threshold.Within regime t, γk remains equal to γt, and the next regime uses γt+1 = γtθ.
  • Properties: The resulting steplength sequence is piecewise constant and decreasing, with persistent-error jumps occurring whenever the steplength is reduced.The scheme is well defined because Kt is finite for every t under the stated assumptions.

B. Global convergence theory

The convergence analysis establishes that the CSA scheme satisfies the required summability condition under its geometric steplength reductions. Consequently, its iterates converge almost surely to the unique optimal solution under the stated assumptions.

  • Global convergence: The paper proves that the cascading steplength scheme converges to the optimal solution under the stated strongly convex, Lipschitz-gradient, and compactness assumptions.The formal result assumes L > η and a geometrically reduced steplength sequence.
  • Global convergence: The iterates converge almost surely to the unique optimal solution of problem (1).This conclusion follows after verifying the stochastic approximation summability requirement.
  • Proof strategy: The proof uses γt = θ^tγ0 and bounds the regime durations Kt so that the cumulative squared steplengths are finite.The geometric reduction factor satisfies θ ∈ (0, 1).

V. ADDRESSING NONDIFFERENTIABILITY THROUGH LOCAL RANDOMIZED SMOOTHING

The paper addresses nondifferentiable stochastic objectives by locally smoothing the objective with random perturbations. It then studies the gradient regularity of the resulting differentiable approximation and its use in stochastic approximation.

  • Local smoothing: A local smoothing approach approximates a nondifferentiable objective using random perturbations.The approximation is denoted by f̂ and is formed through local randomness.
  • Gradient regularity: The analysis derives Lipschitz constants for the approximation’s gradients when the perturbations follow a uniform distribution.The convergence theory is then examined for the modified stochastic approximation framework.

A. Differentiable Approximation

The local randomized smoothing method produces a convex differentiable approximation by averaging perturbed function values. With uniform perturbations, its gradient is Lipschitz, while the bound grows at a rate proportional to √n but avoids the global-domain requirement of normal smoothing.

  • Differentiable approximation: The smoothed objective is defined as the expected value of f(x + z) over local perturbations z supported in an ε-ball.The domain is enlarged to Xε so that every perturbed point remains in the function’s domain.
  • Differentiable approximation: Under bounded subgradients, the approximation is convex and differentiable, with gradient given by the expected perturbed subgradient.Its gradient norm is also bounded by the subgradient bound C.
  • Uniform smoothing: Uniform perturbations yield a Lipschitz gradient for f̂ with a dimension-dependent bound involving κ n!!/(n−1)!! and ε.The result applies to perturbations uniformly distributed over an n-dimensional ball.
  • Dimension dependence: The Lipschitz bound grows at rate √n with problem size, which is worse than the ln(n + 1) rate reported for global normal smoothing.The local method nevertheless removes the requirement that f be defined over the entire space.

C. Convergence analysis of the algorithm with local smoothing

Local smoothing replaces a convex nondifferentiable objective with a differentiable approximation whose optimal value is close to the original. Under the stated assumptions, stochastic approximation converges almost surely to an optimal solution of the smoothed problem.

  • Deterministic nondifferentiable optimization: The local-smoothing method applies stochastic approximation to a differentiable approximation of the convex nondifferentiable objective.The approximation is formed before minimizing over the feasible set.
  • Deterministic nondifferentiable optimization: The smoothed objective approximates the original optimal value within ϵC, where C bounds subgradient norms.The relation f* ≤ ˆf* ≤ f* + ϵC makes ϵC an upper bound on the overestimation.
  • Convergence analysis: Under the stated assumptions, the iterates generated by method (41) converge almost surely to a random optimal solution.The assumptions include convexity, a suitable smoothing radius, and existence of a solution.
  • Convergence analysis: The convergence proof verifies boundedness and regularity conditions for the smoothed objective and its stochastic gradients.The argument uses convexity, finiteness, bounded subgradients, and bounded gradients of the approximation.
  • Convergence analysis: The smoothed objective is differentiable with Lipschitz gradients over the feasible set, so the convergence conditions apply.This establishes the regularity needed by the stochastic approximation result.

2) Stochastic nondifferentiable optimization:

For stochastic nondifferentiable objectives, local smoothing introduces uniform random perturbations and yields a differentiable stochastic approximation. The resulting method has controlled approximation error, Lipschitz gradients, and almost-sure convergence.

  • Stochastic nondifferentiable optimization: Local smoothing transforms the stochastic nondifferentiable problem into an approximation whose randomness combines the original variable ξ with an independent smoothing variable z.The smoothed objective is represented through nested expectations over ξ and z.
  • Convergence analysis: Under the lemma’s bounded-subdifferential assumptions, method (44) converges almost surely to an optimal solution of the approximate problem.The proof establishes the required Lipschitz-gradient and bounded-noise conditions.
  • Stochastic nondifferentiable optimization: For every ξ, the smoothed integrand is convex and differentiable, approximates F(x,ξ) within ϵC, and has a Lipschitz gradient.The Lipschitz bound depends on dimension through the stated double-factorial expression.
  • Stochastic nondifferentiable optimization: The expected smoothed objective ˆf is convex and differentiable, while its optimal value overestimates the original value by at most ϵC.This motivates solving the approximate stochastic problem.
  • Convergence analysis: The stochastic approximation framework samples in the product space of the original randomness and the artificial smoothing randomness.The smoothed stochastic functions satisfy the regularity assumptions needed for the convergence proposition.

VI. NUMERICAL RESULTS

The numerical study compares RSA and CSA with harmonic stochastic approximation across stochastic utility, bilinear matrix game, and network utility problems. Across the tests, adaptive schemes generally perform well and show limited sensitivity to problem parameters.

  • Experimental design: The experiments compare RSA and CSA with harmonic stochastic approximation across three stochastic optimization problem classes.The study evaluates nine problems of varying size and parameters and includes theoretical and empirical error comparisons.
  • Experimental design: The simulations use repeated trajectories and report means with 90% confidence intervals under varying n, N, and η.The reference setting is n = 20, N = 4000, ϵ = 0.5, and η = 0.5 for the parametric analysis.
  • Stochastic utility problem: Confidence intervals for RSA and CSA are relatively invariant to problem dimension, while RSA is slightly tighter than CSA in the stochastic utility study.Increasing N improves the intervals, whereas larger η gives tighter bounds but less accurate solutions relative to the unregularized problem.
  • Bilinear matrix game problem: In the bilinear matrix game, CSA finds solutions faster than RSA in at least three test problems: P(i): 3, 5 and 7.The true optimal solution is obtained within N gradient steps for most test problems.

3) A stochastic network utility problem:

The network utility experiments compare adaptive steplength schemes with harmonic stochastic approximation and examine theoretical bounds, empirical errors, and parameter sensitivity. RSA and CSA remain robust as problem size changes, with CSA often yielding tighter empirical confidence intervals.

  • Problem formulation: The network utility problem models user flow rates, uncertain user parameters, link capacities, and congestion costs over a spatial network.The objective combines user-specific utilities with a congestion cost based on aggregate link flow.
  • Numerical results: Both RSA and CSA perform favorably compared with HSA, and neither deteriorates in confidence-interval terms as problem size grows.CSA has slightly tighter empirical confidence intervals in the reported tests.
  • Theoretical and empirical trajectories: RSA has uniformly better theoretical bounds than CSA for the stochastic utility and network utility problems, while their final empirical errors are similar.CSA’s theoretical-bound jumps correspond to reductions in its steplength.
  • Theoretical and empirical trajectories: CSA performs significantly better than RSA for a subset of bilinear-game problems.This contrasts with the similar final empirical behavior observed for the utility and network utility problems.
  • Parameter sensitivity: HSA termination error varies by nearly a factor of 10 across tested problems, whereas RSA is relatively insensitive to its initial stepsize and CSA is relatively insensitive to θ.Smaller θ slightly improves theoretical bounds, but empirical differences are muted.
  • Concluding remarks: Locally smoothed RSA and CSA perform well on nonsmooth stochastic optimization problems and are relatively insensitive to problem parameters.The paper reports this conclusion for two classes of nonsmooth stochastic optimization problems.
Loading 1105.4549v1…