4
$\begingroup$

The Wikipedia page for SGD describes optimizing a function $f = \sum f_i(\theta;x_i)$ by successively approximating gradients from random subsets of the data, while most literature poses the problem as optimizing $f = \text{E}[F(\theta,\zeta)]$ for some random variable $\zeta$. I can see how these are asymptotically equivalent when $\zeta$ is a sample from all available observations and $F(\theta; \zeta) = \sum_{x_i\in \zeta}f_i(\theta;x_i)$, and intuitively, it seems that the later formulation is more descriptive of the actual optimization task. However, it isn't apparent to me that these problems necessarily have the same solution. Under what conditions are the solutions equal (convexity, etc.)? Are there any theoretical guarantees that a stationary point of the stochastic approximation be in some $\epsilon$-neighborhood of a stationary point of the deterministic function when these assumptions are not met?

EDIT: Wikipedia says the method converges to a global optima for convex and pseudo convex functions. I'm curious if there is any established error analysis between a deterministic solution and it's stochastic approximation, or are these algorithms used because they make solutions for normally intractable problems possible, and so error analysis is generally impossible/unimportant? I'm trying to decide if an SGD, or one of several online L-BFGS methods, is a flexible enough framework for a tool where I expect a large range of dataset sizes (from 10 to 10s of thousands) and dimensions, but is still generally too many dimensions for most second order methods, without losing accuracy or significant speed when the problem is small enough for other deterministic methods.

$\endgroup$
  • $\begingroup$ Sometimes two different things end up with the same name, if the people working on them do not interact. I suspect that's what is happening here -- stochastic methods for large-scale deterministic problems are a completely different field to stochastic programming or robust optimization. $\endgroup$ – Christian Clason Feb 11 '17 at 22:41
  • $\begingroup$ I'm still curious about the overlap, since the same method SGD, if being applied to the different problems. And, as I point out, they can be made synonymous. They are different, but one seems to be informed by the other. I'm mostly confused/curious, if I have a determistic problem and use a stochastic technique like online L-BFGS, how well does the result approximate the fully determined solution? I'm reading papers where the same stochastic algorthms are applied to both stochastic problems as well as (approximations?) determined problems like maximum likelihood of a CRF. $\endgroup$ – deasmhumnha Feb 11 '17 at 22:56
  • $\begingroup$ My point was that your assumption that one is informed by the other might be unfounded. There may be a connection (and you point one out), but I wouldn't assume that there must be one. Regarding stability of solutions with respect to approximations, I'd suggest looking at Bonnans and Shapiro's book Perturbation Analysis of Optimization Problems or, coming from the other direction, Shapiro, Dentcheva, and Ruszczynski, Lectures on Stochastic Programming. $\endgroup$ – Christian Clason Feb 11 '17 at 23:13
  • 2
    $\begingroup$ I think your definition differs from Wikipedia a little. If you define $f_1(\theta) = N^{-1}\sum_i f(\theta, x_i)$, and $f_2(\theta) = \mathbb{E}[f(\theta, \xi)]$, then they are exactly the same thing (not just asymptotically), provided $\xi$ is an r.v. uniformly distributed on the set of $x_i$'s. With your definition, there is an extra index in $f_i(\theta, x_i)$ that does break this equivalence. In Wikipedia's notation, I think $f_i(\theta)$ is being used instead of $f(\theta, x_i)$, but it should be the same thing. $\endgroup$ – Kirill Feb 12 '17 at 0:47
  • $\begingroup$ I've found that the expectation problem is just one out of many formulations in stochastic optimization, and the process $\theta_{n+1} = \theta_n+\gamma_n[\nabla f(\theta_n)+b_n+D_{n+1}]$ might be a more applicable model. For decreasing $\gamma_n$, bounded $b_n$ and $\text{E}[D_{n+1}]=0$, this process converges to a small neighborhood of a solution of the asymptotic dynamic system, but I haven't found a upper bound on the size of that neighborhood, nor am I certain in general that the stochastic gradient error has mean 0. I suspect the answer is yes, but only for certain functions. $\endgroup$ – deasmhumnha Feb 12 '17 at 1:35

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.