1
$\begingroup$

Due to the rise of machine learning, in many stochastic convex optimization papers the first-order methods now mainly focus on the finite-sum objective function setting. This ends up significantly narrowing the scope of the original/standard stochastic first-order oracle model (e.g., the one described in Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization by A. Agarwal, P. L. Bartlett, P. Ravikumar, and M. J. Wainwright [2012]). This oracle model answers to any query $x$ with a noisy version of $\nabla f (x)$, $\widehat{\nabla f(x)}$, with $E[\widehat{\nabla f(x)}] = \nabla f (x)$ and typically a bounded variance of $\widehat{\nabla f(x)}$ assumption. Note that this oracle is more general than the one considered in the finite sum setting (but includes it).

I was wondering if someone could clarify me towards possible applications of the latter (standard oracle), specially in contexts where the consultation of the oracle itself is the limiting factor (e.g. if the oracle consultation is extremely expensive).

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Sorry, but I don't get what you ask. In the finite sum example one has $f(x) = \tfrac1n\sum_{i=1}^n f_i(x)$ and then $\nabla f_i(x)$ is a "noisy version" of $\nabla f(x)$, it is even an unbiased estimator in the sense that the expected value of $\nabla f_i(x)$ (if you choose i uniformly) is $\nabla f(x)$. Is this related to your question? $\endgroup$
    – Dirk
    Commented Apr 26, 2021 at 11:02
  • $\begingroup$ @Dirk, I edited the question and hope that it is clearer now. I want to know the applications of a more general setting but that includes the finite-sum setting. Thank you for your feedback $\endgroup$
    – Manuel Madeira
    Commented Apr 26, 2021 at 14:19
  • 1
    $\begingroup$ Do you mean something like arxiv.org/abs/1412.4845 ? In the linked file on adaptive importance sampling, the authors apply stochastic optimization to an expectation that is not a finite-sum. $\endgroup$
    – Nawaf Bou-Rabee
    Commented Apr 26, 2021 at 14:23
  • 1
    $\begingroup$ Also, variational inference arxiv.org/abs/2009.00666 en.wikipedia.org/wiki/Variational_Bayesian_methods $\endgroup$
    – Nawaf Bou-Rabee
    Commented Apr 26, 2021 at 14:40
  • $\begingroup$ Crossposted at MSE: math.stackexchange.com/questions/4117100/… $\endgroup$
    – Noah Schweber
    Commented Apr 26, 2021 at 14:41

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .