PaperlayerView exact revision on arXiv

Source-linked AI summary

Block stochastic gradient iteration for convex and nonconvex optimization

Yangyang Xu, Wotao Yin

arXiv:1408.2597v3math.OCcs.LGcs.NAmath.NAstat.ML

TL;DR

Large-data optimization makes full-data updates costly. The paper studies BSG’s block updates and analyzes their convergence for convex and nonconvex problems, reporting different guarantees for the two cases.

  • Problem

    Using all data for every update can be expensive, and accurately evaluating an objective or gradient expectation may be impossible or costly.

    Source: §1 · p. 2, §1.1 · p. 3

  • Method

    BSG uses Gauss-Seidel block updates, whose later blocks depend on earlier updates and can produce a biased stochastic partial gradient.

    Source: §2 · pp. 9–10

  • Results

    For convex problems, BSG has the same-order sublinear convergence as SG; for nonconvex problems, convergence is expressed through expected first-order optimality violation.

    Source: §2 · p. 12

  • Takeaways & Limitations

    The paper establishes convergence results for BSG in both convex and nonconvex settings, using a different convergence measure for each.

    Source: §1 · p. 2, §4 · p. 32

    The stated formulation assumes Eξf(x;ξ) is continuously differentiable, though regularizers may be nonsmooth.

    Source: §1 · p. 2

Abstract

from arXiv · show

The stochastic gradient (SG) method can minimize an objective function composed of a large number of differentiable functions, or solve a stochastic optimization problem, to a moderate accuracy. The block coordinate descent/update (BCD) method, on the other hand, handles problems with multiple blocks of variables by updating them one at a time; when the blocks of variables are easier to update individually than together, BCD has a lower per-iteration cost. This paper introduces a method that combines the features of SG and BCD for problems with many components in the objective and with multiple (blocks of) variables. Specifically, a block stochastic gradient (BSG) method is proposed for solving both convex and nonconvex programs. At each iteration, BSG approximates the gradient of the differentiable part of the objective by randomly sampling a small set of data or sampling a few functions from the sum term in the objective, and then, using those samples, it updates all the blocks of variables in either a deterministic or a randomly shuffled order. Its convergence for both convex and nonconvex cases are established in different senses. In the convex case, the proposed method has the same order of convergence rate as the SG method. In the nonconvex case, its convergence is established in terms of the expected violation of a first-order optimality condition. The proposed method was numerically tested on problems including stochastic least squares and logistic regression, which are convex, as well as low-rank tensor recovery and bilinear logistic regression, which are nonconvex.

1 Introduction

Large-data optimization makes full-data updates costly, while many problems also have variables that divide naturally into blocks. The paper introduces BSG to combine stochastic sampling with block updates and analyzes its behavior across convex and nonconvex problems.

1 Introduction

  • Large-data stochastic programs make full-data updates costly; the formulation partitions variables into blocks and allows possibly nonsmooth block regularizers.Source: §1 · p. 2

1.1 Motivation

  • SAA builds an empirical-risk problem from samples, SG updates from stochastic gradients, and BCD updates one block at a time to reduce per-iteration cost.Source: §1.1 · p. 3

1.3 Related work

  • SG and BCD are special cases of BSG, which updates all blocks rather than randomly selecting one as SBMD does; BSG’s analysis requires boundedness in expectation.Source: §1.3 · pp. 5, 7

1.2 Our algorithm

  • BSG uses sampled component gradients and updates all variable blocks sequentially, with a fixed or reshuffled order; later updates depend on earlier block values.Source: §1.3 · p. 5, §1.2 · p. 5

1.4 Contributions

  • For convex problems, BSG has SG’s convergence-rate order; for nonconvex problems, convergence is established in terms of expected first-order optimality violation.Experiments on two convex and two nonconvex problems report BSG as at least comparable to, and often significantly better than, SG and SBMD on convex problems, and significantly better than BCD on nonconvex problems.Source: §1.4 · pp. 7–8

Notation

  • Notation uses x_<i for blocks before i, ∇_{x_i}F for a partial gradient, and I_1/I_2 to distinguish update types.Source: Notation · p. 8

2 Convergence analysis

The section analyzes convergence of BSG for convex and nonconvex problems, giving rate conditions for the convex case and expected first-order optimality results for the nonconvex case.

2 Convergence analysis

  • Sequential Gauss–Seidel block updates make the stochastic partial-gradient error depend on the current sample through earlier block updates, so it is generally biased.The analysis notes that the usual conditional zero-mean error property does not hold for this algorithm.Source: §2 · pp. 9–10

2.1 Convex case

  • For convex F and r_i, Algorithm 1 achieves a sublinear convergence rate of the same order as stochastic gradient; when Φ is strongly convex with modulus μ > 0, its rate is O(1/k).Source: §2 · p. 12, §2.1 · p. 16
  • When σ_k decreases fast, BSG can achieve almost linear convergence if either each constraint set is unconstrained or every regularizer is zero.The result assumes strong convexity and convex modified regularizers; in the deterministic case σ_k ≡ 0, the stated recurrence implies linear convergence, and increasing batch size can reduce σ_k.Source: §2.1 · pp. 17–19
  • In the convex case, mk=O(k) yields the Theorem 4 convergence rate, while linearly decreasing σk yields linear convergence.The supplied passages do not show the expression for the Theorem 4 rate.Source: §2.1 · p. 20

2.2 Nonconvex case

  • For smooth unconstrained nonconvex problems, Theorem 5 analyzes Algorithm 1 under Assumptions 1–3 when σk is bounded.The theorem’s precise convergence bound is not visible in the supplied passages.Source: §2.2 · p. 21
  • For nonsmooth nonconvex problems, the optimality condition holds asymptotically in expectation along a subsequence under Assumptions 1–4 and the stated constraint and sampling conditions.If σk decreases sufficiently fast, the subsequence can be the full sequence.Source: §2.2 · pp. 23, 25
  • Choosing mk=⌈k^(1+ε)⌉ for any ε>0 guarantees the required finite sampling-error sum under the stated bounded-variance condition.This supplies a sufficient sample-size growth condition for the nonconvex result.Source: §2.2 · p. 26

3 Numerical experiments

The experiments evaluate BSG on convex stochastic least-squares and logistic-regression problems and nonconvex tensor-recovery and bilinear-logistic-regression problems. Across these tests, BSG often performs well against the compared methods, with results depending on the problem and setting.

3 Numerical experiments

  • The tested problems included stochastic least squares and logistic regression as convex cases, and low-rank tensor recovery and bilinear logistic regression as nonconvex cases.All compared algorithms used the same randomly generated starting point.Source: §3 · p. 26, §3.1 · p. 27

3.1 Parameter settings

  • For nonconvex tests, factor matrices were treated as blocks, with three blocks for tensor recovery and two for bilinear logistic regression; tensor tests varied sampling and regularization settings.For smooth nonconvex cases, sample size stayed fixed; for the nonsmooth tensor case it increased asymptotically.Source: §3.1 · pp. 26–27, §3.4 · p. 30

3.2 Stochastic least squares

  • In stochastic least squares, BSG was better than SG except at N = 4000, while SBMD performed consistently better as it updated more coordinates.SBMD updated only partial coordinates and took less computing time.Source: §3.2 · p. 27, Table 2 · p. 28

3.3 Logistic regression

  • On synthetic logistic regression, BSG reached a much lower objective than SG and SBMD within the same epochs or running time, especially with large θ.When θ was small, SBMD performed better as it updated more coordinates; SBMD-1 also had higher partial-gradient cost than BSG.Source: §3.3 · p. 28, Figure 1 · p. 29

3.4 Low-rank tensor recovery

  • On 60 × 60 × 60 tensor recovery, BSG achieved about 1.93% relative error; on 32 × 32 × 32 tests, it beat BCGD early, but BCGD ended slightly lower with nonsmooth regularization.BCGD became trapped at a local solution in the smooth case.Source: §3.4 · pp. 29–30, Figure 4 · p. 31

3.5 Bilinear logistic regression

  • On BCI EEG data, BSG outperformed BCGD within 50 epochs, while BSG bilinear logistic regression gave consistently higher prediction accuracy than linear logistic regression.BCGD later reached a similar objective and prediction quality, but required more time.Source: §3.5 · p. 32

4 Conclusions

The conclusion reports that BSG's convex-programming convergence rate is similar to SG's. Figure 5 presents objective-value and prediction-accuracy comparisons on BCI EEG data.

4 Conclusions

  • For convex programming, BSG has a convergence rate similar to that of SG.The conclusion also states that the paper analyzed convergence for both convex and nonconvex problems.Source: §4 · p. 32
  • Figure 5 compares BSG and BCGD objective values on BCI EEG data within 50 epochs and prediction accuracies across 20 runs within 30 epochs, alongside LIBLINEAR.The caption identifies lower objective and higher accuracy as preferable.Source: Figure 5 · p. 33

A Proof of some lemmas

This appendix section provides proofs for some lemmas used in the paper.

A Proof of some lemmas

  • The appendix supplies proofs for some of the paper's lemmas.The section does not identify which lemmas in this passage.Source: A Proof of some lemmas · p. 33

A.1 Proof of Lemma 1

The proof of Lemma 1 invokes conditional independence and Jensen's inequality.

A.1 Proof of Lemma 1

  • The proof uses conditional independence between u_k and δ_k for an equality, then Jensen's inequality for the final bound.These are the stated justifications for the respective steps in the proof.Source: §A.1 · p. 34

A.2 Proof of Lemma 2

The proof of Lemma 2 treats the index sets I1 and I2 separately, applying prior bounds and standard inequalities in each case.

A.2 Proof of Lemma 2

  • Lemma 6 defines the subgradient norm as the supremum of the norms of elements of ∂ψ(z), assigning +∞ when ∂ψ(z) is empty.Source: §A.2 · p. 34
  • For i in I1, the proof combines Lemma 6 and Remark 3, using Cauchy–Schwarz in the second inequality.Source: §A.2 · p. 34
  • For i in I2, the proof uses projection nonexpansiveness in the first inequality.Source: §A.2 · p. 34

A.3 Proof of Lemma 3

The proof establishes the stated bound on A by induction, handling a ≤ 1 and a > 1 separately.

A.3 Proof of Lemma 3

  • For a ≤ 1, induction establishes A_k ≤ c/(k + 1).Source: §A.3 · p. 35
  • For a > 1, the proof starts at k = ⌊a⌋ + 1 and bounds A_⌊a⌋ + b(⌊a⌋)^2 by 2b(⌊a⌋ + 1)(a − 1).Source: §A.3 · p. 35
  • The a > 1 case then yields A_k ≤ c/(k + 1), completing the induction argument.Source: §A.3 · p. 35

A.4 Proof of Lemma 4

Assuming a_k+1/a_k tends to ν, the proof establishes that e_k+1/e_k tends to η across the cases ν < η, ν = η, and ν > η.

A.4 Proof of Lemma 4

  • When ν < η, the proof uses the limiting ratio to show that a_k ≤ η^k eventually, so e_k = η^k from that point onward.Source: §A.4 · p. 35
  • The proof states that the ν > η case follows similarly to ν < η and concludes that e_k+1/e_k tends to η.Source: §A.4 · pp. 35–36
  • When ν = η, the proof treats sequences that stay on one side of η^k directly and handles crossings by considering the intervals between successive indices n_ℓ.Source: §A.4 · pp. 35–36

Related papers

Loading 1408.2597v3…