Return to Question

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." A. Agarwal, P. L. Bartlett, P. Ravikumar, and M. J. Wainwright. [2012] - https://arxiv.org/pdf/1009.0571.pdf). 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).

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).

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." 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 onde 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).

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." A. Agarwal, P. L. Bartlett, P. Ravikumar, and M. J. Wainwright. [2012] - https://arxiv.org/pdf/1009.0571.pdf). 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).

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." A. Agarwal, P. L. Bartlett, P. Ravikumar, and M. J. Wainwright. [2012], where it answers to any query $x$ with a noisy version of $\nabla f (x)$).

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).

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." 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 onde 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).