Projected subgradient method with finite budget

Finite sums of vectors in ${\mathbb{R}}^n$ use the additive finite-list sum of Linear combination of a finite list, and the span $\mathrm{span}(S)$ as the smallest linear subspace containing $S$; sums of real coefficients use Finite sums and finite products, by recursion.

Let $n\ge 1$, let $C\subseteq {\mathbb{R}}^n$ be nonempty, closed, and convex, and let $f:C\to \mathbb{R}$ be convex. The finite-budget projected subgradient procedure takes $x_0\in C$, an integer budget $N\ge 1$, and positive stepsizes ${\alpha }_0,\dots ,{\alpha }_{N-1}$. At iteration $k$, an oracle returns either failure or a pair $(f(x_k),g_k)$ with $g_k\in \mathrm{\partial }f(x_k)$, where subgradient has the meaning in Subgradients and the subdifferential of a convex function. On a valid response set $x_{k+1}=P_C(x_k-{\alpha }_k{g}_k),$ where $P_C(u)$ is the unique nearest point in $C$ to $u$. On an oracle failure at iteration $k$, return status oracle-failure, the feasible current iterate, the completed update count, and the least-index best among values observed so far if any (otherwise report none); a full-horizon average is not returned. If all $N$ calls succeed, return status budget-exhausted, the final iterate, the weighted average ${\bar{x}}_N=({\sum }_{k<N}{\alpha }_k{x}_k)\mathrm{/}({\sum }_{k<N}{\alpha }_k)$, and a least-index minimizer of observed values among $x_0,\dots ,x_{N-1}$. Report status and completed update count. This finite procedure makes no convergence claim.