Stochastic Bias-Reduced Gradient Methods
Authors: Hilal Asi
Yair Carmon
Arun Jambulapati
Yujia Jin
Aaron Sidford
Venue: NeurIPS 2021 Poster (2021)
Keywords: convex optimization
algorithms
monte carlo
debiasing
accelerated gradient methods
privacy
optimal methods
complexity
theory

Abstract: We develop a new primitive for stochastic optimization: a low-bias, low-cost  estimator of the minimizer $x_\star$ of any Lipschitz strongly-convex function $f$. In particular, we use a multilevel Monte-Carlo approach due to Blanchet and Glynn to turn any optimal stochastic gradient method into an estimator of $x_\star$ with bias $\delta$, variance $O(\log(1/\delta))$, and an expected sampling cost of $O(\log(1/\delta))$ stochastic gradient evaluations. As an immediate consequence, we obtain cheap and nearly unbiased gradient estimators for the Moreau envelope of any Lipschitz convex function. We demonstrate the potential of our estimator through four applications. First, we develop a method for minimizing the maximum of $N$ functions, improving on recent results and matching a lower bound up to logarithmic factors. Second and third, we recover state-of-the-art rates for projection-efficient and gradient-efficient optimization using simple algorithms with a transparent analysis. Finally, we show that an improved version of our estimator would yield a nearly linear-time, optimal-utility, differentially-private non-smooth stochastic optimization method.

Stochastic Bias-Reduced Gradient Methods
Hilal Asi
Yair Carmon
Arun Jambulapati
Yujia Jin
Aaron Sidford
Abstract
We develop a new primitive for stochastic optimization: low-bias, low-cost estimator of the minimizer x. of any Lipschitz strongly-convex function. In particular, we use multilevel Monte-Care Carlo approach due to Blanchet and Glynn [8] to turn any optimal stochastic gradient method into an estimator of r. with bias 6, variance (llog(1/6)) and an expected sampling cost of O (log(()))))) (/))) stochastic gradient evaluations. As an immediate consequence, we obtain cheap and nearly unbiased gradient estimators for the Moreau- Yoshida envelope of any Lipschitz convex function, allowing us to perform dimension-frer randomized smoothing. We demonstrate the potential of our estimator through four applications. First, we develop a method for minimizing the maximum recent results and matching lower bound to logarithmic factors. Second and third, we recover state-of-the-ard rates for projection-efficien and gradient-efficient optimization using simple algorithms with transparent analysis. Finally, we show that an improved version of our estimator would yield nearly linear time, optimal-utilipp differentially private non non-smooth stochastic optimization method.
functions, improving on
Introduction
Consider the fundamental problem of minimizing a ju-strongly convex function access to a stochastic subb-ggradient estimator VF satisfying E F())) E OF(x) and E (<))11 < G for every E X. Is it possible to transform the unbiased estimator V into a (nearly) unbiased estimator of the minimizer v. argmin F(x)? In partieular, can improve upon the O(G/(uvT)) bias achieved by T' iterations of stochastic gradient descent (SGD)?
+ given
In this paper, we answer this question in the affirmative, proposing an optimum estimator ă., which (for any fixed > 0) has
G ( bias E2. x=Il = (6) and variance El Er. 112 o ( log (u))
G2
((o)))
obtain the same bias bound T iterations of SGD, but with expected cost of only Olog I') stochastic gradient evaluations (the worst-case cost is 7'). Further, the bias can be made arbitrarily small with only logarithmic increase the variance and the stochastic gradient evaluations of our estimator, and therefore therefore-parallelinee the term "nearly linear-time" [27]-we call â. nearly unbiased.
and, in expectation, costs Oloog( ( )) evaluations of F Setting 5 = G/(NVT),
Our estimator is instance of the multilevel Monte Carlo technique for de- de-biasing estimator sequences [25] and more specifically the method of Blanchet and Glynn [8]. Our key observation is that this method is readily applicable strongly-convex variants of SGD, indeed any stochastic optimization method with the same (optimal) rate convergence.
yujiajin, sidddssdsdddddddsdoooooooo Tel Aviv University, ycarmon@tauex Sau.ac.1.
Stanford University, jaaiijmmbppss juaasijjbbbpati..yjiiiaa....
When X' = (R(x)) C Rdd F(x) = E.e() (z;; i), and F' is the subgradient of a uniformly random
F(x; i) also get estimator with bias and expected cost Olog(ndd)). See Appendix A.1 for details.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Objective
Expensive operation
No
ENes
max (a) (Sec. 4)
fon(a))..... projx(2) VA(x)
((N)
Ō Ö(e-))
f(x) in domain X' (Sec. 3)
O O(VI/c) "
((x) + f(x) for L-smooth (Sec. 5)
Table 1. Summary of our applications of accelerated bias-reduced stochastic gradient methods. We use No and , to denote the number of expensive operations and subgradient estimations, respectively. The Ô notation hides polylogarithiic factors. See Section 1.2 for additional description.
1.1 Estimating proximal points and Yoshhua envelope gradients
Given convex function f and regularization level X, the proximal point of is Pyλ(v) = argmingea= (xr + 2 11 y|l²], Since computing Py,x amounts to solving a X-strongly- problem, our technique provides low-bias and cheap proximal point estimators. Proximal points are ubiquitous in optimization [43, 19, 52, 38] and estimating them efficiently with low bias opens up new algorithmic possibilities. One of these possibilities is estimating the gradient of the Moreau- Yoshida envelope fx(y) minger= f( + 2 I| yll²). which is a X-smooth, G2 ((2A)-accurate approxi- mation of any G-Lipschitz, (see, e.g., [43, 29] and Appendix B.3). Since V fyx(v) A(y - (y)) our optimum estimator provides a low-bias estimator for fy) with second moment and expected cost greater than those of f by only logarithmic factor. Thus, for any non-smooth f we can turn v into gradient estimator for the smooth surrogate fx. whose smoothness is independent of the problem dimension, allowing us to perform dimension-fee randomized smoothing [20].
1.2 Applications via accelerated bias-reduced methods
Our optimum estimator is a new primitive in stochastic convex optimization and we expect it to find multiple applications. We now describe three such applications: the first improves on previously known complexity bounds while the latter two recover existing bounds straightforwardly. For simplicity of presentation we assume (in the introduction only) E f < 1 and unit domain size.
In each application, we wish to minimize an objective function given access to cheap subgradient estimator V as well as an expensive application-specifee operation O (e.g., a projection to a complicated set). Direct use of the standard stochastic gradient method finds an e-accurate solution using ( ?) computations of both f and O, and our goal is to improve the O complexity without hurting the V complexity.
To that end, we design stochastic accelerated methods consisting of iterations, each one involving only constant number of O and proximal point computations, which approximate by averaging copies of our optimum estimator." Its low bias allows us to bound T < - as though our proximal points were exact, while maintaining an O(e-2) bound on the total expected number of V calls. Thus, save expensive operations without substantially increasing the gradient estimation cost. Table 1 summarizes each application, and we briefly describe them below.
Minimizing the maximal loss (Section 4). Given N convex, 1-Lipschitz functions fay..... f(N) we would like to find an c-approximate minimizer of their maximum fmax(2) (x) = [[N] (z)( This problem naturally arises when optimizing worst-case behavior, as in maximum margin classifi- cation and robust optimization [53, 15, 45, 6]. We measure complexity by the number of individual function and subgradient evaluations, so that the expensive operation of evaluating f(),..., .(N)) single point has complexity O(N) and the subgradient method solves this problem with com- plexity D(N--2) Carmon et al. [13] develop an algorithm for minimizing fmax with complexity Ō(Ne-22 2/3 + -8/3), improving on the subgradient method for sufficiently large N. Using our bias-reduced Moreau gradient envelope estimator in a Monteiro-Svaiier-type accelerated proximal point method [12, 1 11, 38], we obtain improved complexity - + 2 This matches (up to logarithmic factors) lower bound shown [13), settling the complexity of minimizing the maximum
'While averaging parallelizable, our optimum estimator itself sequential. Consequently, our approach does not yield improve parallelism; see Appendix A.2 for further discussion 'It is easy to turn expected complexity bounds into deterministic ones; Appendix A.3.

---

of N non-smooth functions. Our result reveals surprising fact: for N < (GR/c) 4/3 minimizing the maximum of N functions is no harder than minimizing their average.
Projection-efficient optimization via dimension-free randomized smoothing (Section 3). Con- sider the problem of minimizing a convex function f using an unbiased gradient estimator V. over convex set X' for which Euclidean projections are expensive compute (for example, the cone of PSD matrices). When f is L-smooth, a stochastic version of Nesterov's 's accelerated gradient descent (AGD) [16] performs only O(v projections, For non-smooth f we instead apply AGD to the Moreau envelope smoothing of f (with appropriate À = O(e-1) using our nearly-unbiased stochastic estimator for Vxx- This yields a solution in O(e- projections and (()-2) evaluations of f. Our algorithm provides a simple alternative to the recent work of Thekumparampil et al. [51] whose performance guarantees are identical up to a logarithmic factor.
Gradient-efficient composite optimization (Section 5), We would like to minimize v(x) A(x) + [()),, where A is convex and L-smooth but we can access it only via computing (ex- pensive) exact gradients, while f is non-smooth convex functions for which we have a (cheap) unbiased subgradient estimator f.. Problems of this type include inverse problems with sparsity constraints and regularized loss minimization in machine learning [34]. To save VA computa- tions, is possible to use composite AGD [41] which solves O(vL/e L/c) subproblems of the form minimize,, (( ((VA(v),=) + f(x) + 1 I| =² Lan [34] designed a specialized method, gradient sliding, for which the total subproblem solution cost is Oc-²)) evaluations of V. We show that a sim- ple alternative- eestmmatvee-siimatiing the subproblem solutions via our low-bias optimum estimator-
its guarantees up to logarithmic factors.
1.3 Non-smooth differentially private stochastic convex optimization
We now discuss a potential application of our technique that is conditional on the existence of an improved optimum estimator. In it, we minimize the population objective function f(x) = Es~pf(z; S) under the well-known constraint of differential privacy [22]. Given n i.i.d. samples S ~ P and assuming that each is I-Lipschitz, convex and sufficiently smooth, Feldman et al. [23] develop algorithms that obtain the optimal eтror and compute ((n) subgradients of f. The non- smooth case is more challenging and the best existing bound is (nn21/8 for the high-dimensional setting d = n [32, 3]. In Section 6 we show that our optimum estimator, combined with recent localization techniques [23], reduces the problem to private mean estimation. Unfortunately, estimator is heavy-tailed, leading to insufficient utility. Nevertheless, assuming a version of our estimator that has bounded outputs, we give an algorithm that queries Ö(n) subgradients for non- smooth functions, solving longstanding open problem in private optimization [14, 4]. This motivates the study of improved versions of our estimators that have constant sensitivity.
1.4 Related work
Multilevel Monte-Carle (MLMC) techniques originate from the literature on parametric integration for solving integral and differential equations [25]. Our approach is based on an MLMC variant put forth by Blanchet and Glynn [8] for estimating functionals of expectations. Among several applications, they propose [8, Section 5.2] an estimator for argmin, Es~pf(a: (x; S) where f(::s) is convex for all and assuming access to minimizers of empirical objectives of the form Eie(n] f(r; s;). The authors provide preliminary analysis of the estimator's 's variance (later elaborated in [9]) using an asymptotic Taylor expansion around the population minimizer. In comparison, we study the more general setting of stochastic gradient estimators and provide a complete algorithm based on SGD, along with a non-asymptotic analysis and concrete settings where our estimator beneficial.
number of works have used the Blanchet-Glynn estimator in the context of optimization and machine learning. These applications include estimating the ratio of expectations for semisupervised learning [7], estimating gradients of distributionally robust optimization objectives [35], and estimat- ing gradients in deep latent variable models [47]. Our estimator similar that of Levy et al. [35] in that we also have to pick a "critical" doubling probability for the (random) computational budget, which makes the expected cost and variance of our estimators depend logarithmically on the bias.
3

---

1.5 Limitations
Our paper demonstrates that our proposed optimum estimator is useful device: it allows to easily prove upper bounds on the complexity of structured optimization problems, and at least in one case (minimizing the maximum loss) improve over previously known bounds. However, our work does not investigate the practicality of our optimum estimator, as implementation and experiments are outside its scope.
Nevertheless, let us briefly discuss the practical prospects of the algorithms we propose. On the one hand, optimum estimator itself is fairly easy to implement, adding only few parameters top of a basic gradient method. On the other hand, in the settings of Sections 3 and 5, gradient-sliding based methods [34, 51] are roughly as simple to implement and enjoy slightly stronger convergence bounds (better by logarithmic factors) than our optimum estimator. Consequently, in these settings have reason to assume that algorithms
better in practice. In the setting of Section 4 (minimizing the maximum loss) our algorithm does enjoy a stronger guarantee than the previous best bound [13]. However, both our algorithm and [13] are based on an accelerated proximal point method that, in its current form, is not practical [13, Sec. 6.2J. Thus, evaluating the benefit of stochastic bias reduction in the context of minimizing the maximum loss would require to first develop a practical accelerated proximal point algorithm, which is an open question under active research [see, e.g., 50].
Another limitation of our optimum estimator is that, while it has bounded second moment, its higher moments are unbounded. While this does not matter for most of our results, the lack of higher moment bounds prevents from setting the complexity of non-smooth private stochastic convex optimization in Section 6. Finding an optimum estimator that bounded with high probability- proving that one does not cedist-remain
open question for future work.
Finally, our analyses are limited to convex objective functions. However, while outside the scope of the paper, we believe our results are possibly relevant for non-convex settings well. In particular, for smooth non-convex functions (and weakly-convex functions [17] more broadly) the problem of computing proximal points with sufficiently high regularization is strongly convex and estimator applies. Such non-convex proximal points play an important role in non-convex optimization [17] with applications in deep learning [see, e.g., 49]. Applying the optimum restmmt- technique in non-convex optimization is therefore a viable direction for future work.
1.6 Notation
We let BR(x) = fy E Rd: |yy x|| S. R} denote the ball of radius R around x, where ||-|| is the Euclidean norm throughout. We write Projs for the Euclidean projection S. We write 1[{ for the indicator of event A, i.c., 1(.4) = 1 when A holds and 0 otherwise. Throughout the paper, f denotes a (stochastic) subgradient estimator for the function f. and X' C Rd denotes the optimization domain, which we always assume closed and convex. We use p.. to denote the proximal operator (2) and fA to denote the Moreau envelope (3) associated with function and regularization parameter X. Finally, we use Ny and N to denote function and subgradient estimator evaluation complexity, respectively.
2 A multilevel Monte-Carlo optimum estimator
In this section, we construct a low-bias estimator for the minimizer of any strongly convex function F : X + R. This estimator is the key component of our algorithms in the subsequent sections, which use to approximate proximal points and Moreau envelope gradients. We assume that F is of the form F f + v. where the function v is "simple" and that f satisfies the following.
Assumption 1. The function f X + R is convex (with closed and convex domain X) and is accessible via an unbiased subgradient estimator Vf which satisfies E[(vf(=)) G²
@G2fffo for all x.
Our applications only use 1e of the form (/xx)) = ž || x' but our estimator applies more broadly to cases where argmin, { (v, + v((x) + 2, || y1l2| is easy to compute for all and y.
2.1 ODC algorithms
Our estimator can use, in a black-box fashion, any method for minimizing F with sufficiently fast convergence to x, argmin F(x). We highlight the required convergence property as follows.

---

Algorithm 1: OPTEST u. u, x))
Algorithm 2: MORGRADEST( f 2, 02,
b 6, are required bias and square error
o, are required bias and square error
b is the ODC algorithm constant
A is the regularization level
Tmax
4rG²2
y is the point at which to estimate V.x(y)
# ( +
15 (zr = 2 -0--yp1 y/1²
32cG² (ogg(Tmxx)]
N
n
c, = OPTEST V/ X, 4 X ;2 A)
for i
1, . do
return X(y - -t.
a. draw of the estimator (1)
return EiENN a
Definition 1. An citimalldistanee distance-convergence algorithm ODC takes as input f satisfying As- sumption 1, a simple function & and budget T 2 1. If = f + vp is p-strongly convex with minimizer 2., the algorithm's 's output ODC( f, vb, T) requires at most T evaluations of V to G compute and satisfies E|| x. S c L for some constant c > 0.
Standard lower bound constructions imply that the O G
T squared distance convergence rate is indeed optimal; see Appendix A.4 for additional discussion. Conversely, ODC algorithms are readily
available in the literature [44, 28] since any point x satisfying EF(x) - F(x.) = O G2 pT (the
optimal rate of convergence in strongly convex, Lipschitz optimization) also satisfies EE E| x, 1|? < O G² of a generalization of epoch SGD [28], which allows us to optimize over the composite objective F = + v instead of only f as in the prior study of epoch SGD.
(TT)) by due to the strong convexity of F. We provide concrete ODC algorithm consisting
Lemma 1. EPOCHSGD (Algorithm 8 in Appendix B.I) I) is ODC algorithm with constant c 32.
2.2
Constructing optimum estimator
To turn any ODC algorithm into low-bias, low-cost and near-constant variance optimum estimator, we use the multilevel Monte Carlo (MLMC) technique of Blanchet and Glynn [8]. Given a problem instance f vi, an algorithm ODC and a cutoff parameter Tmax E I, our estimator 2. is:
Draw J ~ Geom (t) E N and, writing x, = OD,(V,.))2)) compute
2 22 x3-1) 2 Tiaax
20 +
{0
otherwise.
We note that for certain ODC algorithms it is possible to extract T--1 from the intermediate steps of computing æ.,, so that we only need invoke ODC once. This particularly simple to do for EPOCHSGD, as we explain in Appendix B.I. The key properties of our estimator are as follows.
Proposition 1. Let f and & f satisfy Assumption 1, == + be μ-strooggyy convex with minimizer I. and T Tmax E N. For any ODC algorithm with constant c, the estimator (1) has bias |Eλ, - x. I uvTmax and variance El E& 112 16c 112 logo(Tmax), Moreover, the expected number of vf evaluations required compute á, is O(log Tmax)-
V2c- G
Proof.
Let jmax = max(i E N 2 < Timax]
[log2 T.mx)]. The expectation of d. is
Jmax
E.. Erg +
P(J = (Lxx - Ex = Ex j
1=1
where the second equality follows from PPJ j) = 2- and the sum telescoping. Noting that I Jmme ODC(CF, vi, T) for T 2mmax T Tmaxx/3 /2, we have that
G
|at -xxll= 5
BR 1 1212 S Vc
/ T
5

---

by Definition 1. To bound the variance we use ||a - bl12 v 2/|a|| + 2||b| and note that
E 2
Ei, 1 s Eljå. - 2211² 2 2B zoll² 2 + 2 20 1.11..
The ODC property implies that 20 x=112 11 S cG² /2² For the term E j.. - zol. we have
E i++ Smux
Janx
zoll =
P(J P(J=jj2²
Iz x3-111
2 zy - -z- 111.
and
==1
G
B| z-- - 2B| x. - x.112 1| + 2E Tj-1 - x.112 v 6c
2-
112
Substituting, get B| zol
G 1.z Jmax and El|a. | < 16c G the expected number of f evaluations is 1 Σ Jmn PPJ (2 2 (fmax).
6c
log, (T Finally,
The function OPTEST in Algorithm computes estimate of æ, with and desired bias ö and square error o² by averaging independent draws of the MLMC estimator (1). The following guarantees are immediate from Proposition 1; see Appendix B.2 for short proof.
Theorem 1. Let and V f satisfy Assumption I, f + ab be p-strongly convex with minimizer Is E X. and ó, a O. The function OPTEST(V f, v, pr, (2) outputs i, satisfying
E2, - x. 1 S and Ella. 2.11? s o²
using , stochastic gradient computations, where
EN =0 0
G log"
G (1min((807)
G
log
1:202
(
2.3 Estimating proximal points and Moreau envelope gradients
The proximal point of function f X + R with regularization level À at point is
P (y) argmin (f(x) + 1 -
=Ex
When satisfies Assumption 1, we may use OPTEST (with (xx) = 211 y and μ = A) to obtain reduced-bias proximal point estimator. The proximal point ( closely related to the Moreau envelope
(v) min (f(z) + =
zE
via the relationship Vv((v) = A(y (..(w))) (see Appendix B.3). Therefore, we can use our optimum estimator turn (1) calls to V into nearly unbiased estimator for fx. We formulate this as:
Corollary 2. Let f and &f satisfy Assumption I. let y E X and let X,0,8 >
0. The function MO 02, outputs Vfx(y) satisfying |EE f2())
ff((v) < ō and fx)V)(()) f2 I o² and has complexity ENe, =
G² log" (min(torr)) log min (b.a)
Projection-efficieet convex optimization
In this section. combine the bias-reduced Moreau envelope gradient estimator with standard accelerated gradient method to recover the result of Thekumparampil et al. [51]. We consider the problem of minimizing function f satisfying Assumption over the domain TB Bn((0) subject to the constraint x E X, where X' C (0) a complicated convex set that we can only access via (expensive) projections of the form Proj (x) argmin,ex* = We further assume that an initial point zo X' satisfies ||00 x_| < D.
Algorithm applies a variant of Nesterov's accelerated gradient descent method (related to [2, 1]) on the (A-smooth) Moreau envelope fx defined in eq. (3). Since computing the Moreau envelope

---

Algorithm 3: Stochastic accelerated gradient descent on the Moreau envelope
Input: A gradient estimator V f satisfying Assumption in [B)(()) projection oracle Projx and initial point Ty = V/u with || - x=1l I D.
Parameters Iteration budget T,, Moreau regularization X. approximation parameters d,, of
1 for k = T do
yk R+1 Tk E+I Kk-1
fk MORGRADEST(V/ ykkk-i òr o. Br(())
Zg Projx (yk-1 3x 9k.
Uk = ProjBn(0) (Uk-1 gK)
return 2T
does not involve projection to X, for sufficiently accurate approximation of V/> we require only T' = O( //D2/e) projections to X' for finding an O(e)-suboptimal point of fa constrained to X. For that point to be also e-suboptimal for itself, we must choose À of the order of GO /e, so that the number of projections is O(GD/e).
As noted in [51] computing ffx to accuracy O(e/R) is sufficient for the above guarantee to hold, but doing so using& a stochastic gradient method requires O(GGD/c) evaluations of f per iteration, and O((GD/e)*) evaluations in total. To improve this, employ Algorithm 2 compute nearly- unbiased estimates for V V and bound the error incurred by their variance. Our result matches the gradient sliding-based technique of Thekumparampil et al. [51] up to polylogarithmic factors while retaining the conceptual simplicity of directly applying AGD on the Moreau envelope. We formally state the guarantees of our method below, and provide self-container proof in Appendix C.
Theorem 3. Let f Bn( - IR and V f satisfy Assumption 1. Let X C Br((0) be a convex set admitting a projection oracle Projx- Let Di E X be an initial point with | - x= S D for some 2+A
x. E X. With A 2G² 8x = 8R oh =
and T = 1GD Algorithm 3 computes x E X with k+D
[f(] S f(x.)+ E with complexity ENG, O G² log" (GR) and O [GD) calls Projx-
4
Accelerated proximal methods and minimizing the maximal loss
In this section we apply our estimator in an accelerated proximal point method and use it to obtain an optimal rate for minimizing the maximum of N convex functions (up to logarithmic factors).
4.1 Accelerated proximal point method via Moreau gradient estimation
Algorithm an Monteiro- Monteiro-Svaiter-tyy Svaiter-type [38, 12] accelcrated proximal point method [36, 24] that leverages reduced-bias Moreau envelope gradient estimator. To explain the method, contrast with stochastic AGD on the Moreau envelope (A (Algorithm
3). First and foremost, Algorithm provides suboptimality bound the Moreau envelope fa (which for small À is far from f) while
Algorithm 4 minimizes f itself.
Second, while Algorithm 3 uses fixed regularization parameter X, Algorithm 4 handles an arbitrary sequence {Ax} given by a black-box function NEXTLAMBDA. To facilitate our application of the method to minimizing the maximal loss where gradient estimation is only tractable in small Euclidean balls around a reference point we include an optional parameter r such that the proximal point movement bound ||P A. (31,) yk || < holds for all k. However, most of our analysis of Algorithm 4 does not require this parameter (i.e., holding for r = oc), making it potentially applicable to other settings that accelerated proximal point methods [1 38, 50].
The third and final notable difference between Algorithms 3 and 4 the method of updating the x iteration sequence. While a projected stochastic gradient descent step suffices for Algorithm 3, here we require a more direct approximation of function value decrease attained by the exact proximal mapping P/ PI.x (see eq. (2)). For a given accuracy ip we define the ş-aaproximate proximal mapping
Pe (v) any x E X' such that EF(x) S F(P + + for F(2) f(2) + 111 v11. (4)
7

---

Algorithm 4: Stochastic accelerated proximal point method
Input: Gradient estimator V. f, function NEXTLAMBDA, initialization 20 vo and Ao 2 O. Parameters Approximation parameters {sPk: òk, ok), stopping parameters Amax and K maxx optional movement bound; >> 0.
for k = 0, ........... do
Ak+1 NEXTLAMBDA(2H: Uk A&) guaranteeing that || ( (26) well S
ax+1 = 2x4+1 VI 4A AR and Ak+1 = Au + aR+1 and X₂ = X' n (yR)
yk = Ar-1 + dn-l Un and 2x+1 = P
f.Ar (Vk) & defined in eq. (4)
Ac+1
gh++1 = MORGRADEST S, My,,, 1 5v, o Nx) and Uk411 = Projx (un 2 10++1)1+)
A 2 Amax or + Kmax then return T1++1
Note that Po (such as EPOCHSGD) using O /Xp)) evaluations f.
S.A = PyA and that for up > O we can compute P with an appropriate SGD variant
With the differences between the algorithms explained, we emphasize their key similarity: both algorithms update the Up sequence using our bias reduction method MORGRADEST (Algorithm 2), which holds the key to their efficiency. The following proposition shows that Algorithm 4 has the same bound on Kmax as an exact accelerated proximal point method [12), while requiring at most Ō R²c-) stochastic gradient evaluations; see proof in Appendix D.1.
Proposition Let f X R and ff satisfy Assumption 1, and let X S BB((F)). For target accuracy S GR let Pk+1 6074-10447' 5k+1 12OTe of "0au41'
é_ Ao R. and
> 2 Amin 2 Amay 01 RZ for all k S Kmax then lines and 5 of Algorithm Amax = 2R
have total complexity IEN', O (Kmax log GR G²R² log² GR
(RR. If addition [IP S.A (31--1
yk y 2 3r/4 whenever d 2 2Amin then for Kmax (( 2/3 log (GR) + Amin the
algorithm's 's output I satisfies f f(xx) - fxxx) I e with probability at least 2 3"
4.2 Minimizing the maximal loss
We now consider objectives of the form (x) max f())()) where each function f(i)
X + R is convex and G-Lipschitz. Our approach to minimizing Fmax largely follows Carmon et al.
[13]; the main difference is that approximate proximal steps via Algorithm 4 and reduced-bias bias estimator. The first step of the approach is to replace fmax with the "softmax" function, defined for given target accuracy
Ssmax (x) = log Σ (xx(((o(a)/ee) where log N
Since fsmax (x) fmax E [0. $) any 5 accuraaee solution of famax e-accurate for fmax-
The second step is to develop an efficient gradient estimator for famaxi this is non-trivial because fsmax is not finite sum expectation. In [13] this is addressed via "exponentiated softmax" trick; we develop an alternative, rejection sampling-base approach that fits Algorithm 4 more directly (see Algorithm 9). To produce unbiased estimate for V S.smax (2:) for in a ball of radius r, = c we require a single V (()(2) (x) evaluation (for some i), ((1) evaluations of f(a (x) in expectation, and evaluation of the N functions f(1y (1)( f(N) (g) for pre- pre-processing. Plugging this estimator into Algorithm with r = Te, the total pre-procsssing overhead of lines and 5 is O K Max
The final step is to find a function NEXTLAMBDA such that ||P fumaniees (BN) 3k |l S for all k (enabling gradient estimation). and ||P femae (Bk) y/ Te when d > 22 (allowing us to bound Kmax with Proposition 2). Here we use the bisection subroutine from [13] as is (see Algorithm 10). By judiciously choosing Amin amin-an improvement over the analysis in [13]-we we obtain the following complexity guarantee on Ni,,, and Nast. the total numbers of individual function and subgradient evaluations, respectively. (See proof Appendix D.2).
3

---

Theorem 4. Let f())....;fI) : 2 - R be convex and G-Lipschitz and let X' S BR(ZO). For any e < GR/ log N, Algorithm 4 (with Pe fauns:A implemented in Algorithm 8, Samax given by ouputs x E X that with probability at least is e-suboptimal for fmax (2) [ {(3) (2)) and has complexity
Algorithm 9 and NEXTLAMBDA given by Algorithm 10 with Amin = (re((re 4/3 R2/31)
Fo - - ([ N GRllgg N
2/3
(RR) log QR and ENaso O GR
log" GR
The rate given by Theorem 4 matches (up to logarithmic factors) the lower bound () (GR)e)²) shown [13] and is therefore near-optimal.
Gradient-efficien composite optimization
Consider the problem of finding a minimizer of the following convex composite optimization problem
minimize V (z) Axx) + (z) where A L-smooth and f satisfies Assumption 1, (5) #EX
given 20 such that ||00- .r, || < R for some I, E argmin x (x)). Lan [34] developed a method
called "gradient sliding" that finds c-accurate solution to (5) with complexity Av O(VLR?)
evaluations of V (1x) and NY = O((GR/c)²) evaluations of V (x)), which are optimal even for each component separately.
In this section, provide alternative algorithm that matches the complexity of gradient up to logarithmic factors and is conceptually simple. Our approach, Algorithm 5, is essentially composite AGD [41], where at the kth iteration we compute a proximal point (2) with respect to a partial lincarization of / around yk- In particular, letting (v) == A(ya) (VA(gk), v yk) and 8y = T we approximate Pa+s,s (Vk-1). Similar Algorithm 4, Algorithm computes two types of
24
approximations: one is an ea-approximate proximal point Pru. f. (Uk-1) per its definition (4), while the other is our bias-reduced optimum estimator from Algorithm 1. We note, however, that unlike Algorithm 4 which approximates the 2& update, here we approximate Up. the "mirror descent" update.
Below we state the formal guarantees for Algorithm 5; we defer its proof to Appendix E.
Algorithm 5: Stochastic composite accelerated gradient descent
Input: A problem of the form (5) with A. VA, Vj. Parameters :Step size parameters 3x = and % = E+1 iteration number N, approximation parameters (ex, 62, o and .i vn satisfying ||z0 x=1l R.
2
for k 1, 2, ................................ N do
y/ (1 7k x + N4 Projx
3 Uk = Phr, fu+f f.8, (Uk-1) for As A(yk) + (VA(8k), v 8k)
4 Uk = OPTEST(TN V /1 Wh. Br, 8c, og BR(vO) 22) for vh((z) = Ag 11= 11-1 11 +=)(=)
T& = (1 - 7 xx + Up
return NN
Theorem 5. Given problem (5) with solution x., a point Fo such that ||:00 - J- S R and target
accuracy > O, Algorithm 5 with ex LR/2KN, åz R//6N,, of R² /4N, and N
@(VIRE/)) finds an approximate solution satisfying EV(x) (x) S (xx) + e and has complexity
NF = 0
( ( LRe and EN = (GR) log2
((
LI2 log GR
Efficient non-smooth private convex optimization
We conclude the paper with a potential application of our optimum estimator for differentially private stochastic convex optimization (DP-SCO). In this problem we given n i.i.d. sample
'The gradient sliding result holds under relaxed Lipschitz assumption [see 34, eq. (1.2)). It straightforward extend EPOCHSGD, and hence all of our results, to that assumption as well.

---

8; P taking values in a set 8, and out objective is to privately minimize the population average f(x) = Es- (ar; 8)), where f A' x S - R. is convex in the first argument and X' C IR4 is convex set, and S is a population data points. That is, We wish to find a E & with small excess loss f(t) mingex f(z) while preserving differential privacy.
Definition 2 ([22)). A randomized algorithu A is (a, difffereett private ((a,, D)D) if. for all datasets S, S' E S" that differ in single data element and for every event O in the output space of A, we have P[A(S) E O] S PIA(S') E 0] B.
DP-SCO has received increased attention over the past few years. Bassily et al. [5] developed (inefficient) algorithms that attain the optimal excess loss 1 + v /dlog(1/3)/na: When each function is O(vr) smooth, Feldman et al. [23] gave algorithms with optimal excess loss and (()) gradient query complexity. In the non-smooth setting, however, their algorithms require (n subgradients. Subsequently, Asi et al. [3] and Kulkarni et al. [32] developed more efficient algorithms for non-smooth functions which need (mmin(n² /d, ////4//// n// /d subgradients which is ((n ) for the high- -ighnninenional setting d = n. Whether a linear gradient complexity is achievable for DP-SCO in the non- non-smooth setting is still open.
In this section, we develop an efficient algorithm for non-smooth DP-SCO that queries Ö(n) subgra- dients conditional on the existence of an optimum estimator with the following properties.
Definition 3. Let F = -f f+ t be p-strongly convex with minimizer x, and f is G-Lipschitz. For 5 > O, we say that Og is efficient bounded low-bias estimator if returns it, = Os(F) such that [|E[e. 2.1 S 82, 1 1.112 S C2 log(G/ (GG/pp)//² and the expected number of gradient queries is C2 log(G/ μб).
Comparing to MLMC estimator (1) and Proposition 1, we note that the only place our current estimator falls short of satisfying Definition 3 is the probability bound on || 2.1 which for (1) holds only in expectation. Indeed, for our estimator, || x=|l can be large (GG((1)) meaning that it is heavy-tailed.
It is not clear whether EBBOE as defined above exists. Nevertheless, assuming access to such esti- mator, Algorithm 6 solves the DP-SCO problem with a near-linear amount of gradient computations. The algorithm builds the recent localization-bass optimization methods in [23] which iteratively solve regularized minimization problems.
Algorithm 6: ceifferentially-priveee stochastic convex optimization via optimum estimation
Input: (S1,..., 8n) E S", domain X' C BR(2)). EBBOE O (satisfying Definition 3). Set k- llog n B 20 + + C2 log" n), ń N.r n = R min
Vn
B log / /dlog(
for i 1,2, ,k do
Let 1)s 2 4nn f(()) 1 th -)=+ fxx sy), vx(x) || (1/m))
Let v; 1
n -²= 0₂ (F.) with F. fo + 4h 83 G2
Set x; 2; + Ci where S ~ N(O, of (a) with 0; (BBVC1 logn + /log(2/)
6 return 2%
We average multiple draws of the (hypothetical) bounded optimum estimator to solve the regularized problems, and apply private mean estimation procedures to preserve privacy. We defer the proof of the following results Appendix F.
Theorem (conditional). Given an efficient bounded low-hias estimator Os satisfying Definition 3 for any > O, then for a S 1og(1/3), X E BR(zo), convex and G-Lipschitz f(z; s), Algorithm is (a, 3)DD, queries Ö(n) subgradients and has (hiding logarithmic factors in n) Elf(xu) (1/8)
minzex f(x)] S Ō
Theorem 6 provides a strong motivation for constructing bounded optimum estimators that satisfy Def- inition 3. In Appendix F.3, we discuss the challenges in making our MLMC estimator bounded, as well as some directions to overcome them.
10

---

Acknowledgments
HA was supported by ONR YIP N00014-19-2288 and the Stanford DAWN Consortium. YC was supported in part by Len Blavatnik and the Blavatnik Family foundation, and the Yandex Machine Learning Initiative for Machine Learning. YJ was supported by a Stanford Graduate Fellowship. AS was supported in part by Microsoft Research Faculty Fellowship, NSF CAREER Award CCF-1844855, NSF Grant CCF-1955039, a PayPal research award, and Sloan Research Fellowship.
References
[1] Z. Allen-Zhu. Katyusha: the first direct acceleration of stochastic gradient methods. In Proceedings of the Forty-Ninth Annual ACM Symposium on the Theory of Computing, 2017.
[2] Z. Allen-Zhu and L. Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. In Proceedings of the 8th Innovations in Theoretical Computer Science, ITCS '17 2017.
[3] H. Asi, V. Feldman, T. Koren, and K. Talwar. Private stochastic convex optimization: Optimal rates in & geometry. In Proceedings of the 38th International Conference Machine Leurning, 2021.
[4] R. Bassily, A. Smith, and A. Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 55th Annual Symposium on Foundations of Computer Science, pages 463,473,5 2014.
[5] R. Bassily, V. Feldman, K. Talwar, and A. Thakurta. Private stochastic convex optimization with optimal rates. In Advances Neural Information Processing Systems, volume 32, pages 1 11282-1 1291, 2019.
[6] A. Ben-Tal Tal, L. E. Ghaoui, and A. Nemirovski. Robust Optimization. Princeton University Press, 2009.
[7] J. Blanchet and Y. Kang. Semi-supervised learning based on distributionally robust optimization. In Stochastic Modeling Techniques and Data Analysis International Conference, 2018
[8] J. H. Blanchet and W. Glynn. Unbiased Monte Carlo for optimization and functions of expectations via multi-level randomization. In 2015 Winter Simulation Conference (WSC), pages 3656-3667, 2015.
[9] J. H. Blanchet, P. W. Glynn, and Y. Pei. Unbiased multilevel Monte Carlo: Stochastic optimiza- tion, steady-state simulation, quantiles, and other applications. arXiv:/9044 19044099499 [math.ST], 2019.
[10] S. Bubeck. Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn., 8 (3-4):231-357,22)) 2015.
[11] S. Bubeck, Jiang, Y. T. Lee, Y. Li, and A. Sidford. Complexity of highly parallel non-h convex optimization. arXiv: 10655 [math. OCJ, 2019.
[12] Y. Carmon, A. Jambulapati, Q. Jiang, Y. Jin, Y. T. Lee, A. Sidford, and K. Tian, Acceleration with ball optimization oracle. In Advances in Neural Information Processing Systems, 2020.
[13] Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford. Thinking inside the ball: Near-optimal minimization of the maximal loss. In Conference on Learning Theory, 2021.
[14] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk mini- mization. Journal of Machine Learning Research, 12:1069-1109, 2011.
[15] K. L. Clarkson, E. Hazan, and D. P. Woodruff. Sublinear optimization for machine learning. the Journal the ACM (JACM), 59(5):1-49, 2012.
[16] M. Cohen, J. Diakonikolas, and I.. Orecchia. On acceleration with noise-corrupted gradients. In International Conference Machine Learning, pages 1019-1028. PMLR, 2018.
11

---

[17] D. Davis and D. Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1)2007-339 2019.
[18] J. Diakonikolas and C. Guzmán. Lower bounds for parallel and randomized convex optimization. In Proceedings of the Thirty Second Annual Conference on Computational Learning Theory, pages 1132-1157, 2019.
[19] D. Drusvyatskiy. The proximal point method revisited. SIAG/OPT Views and News, 26(1), 2018.
[20] J. C. Duchi, P. L. Bartlett, and M. J. Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012.
[21] C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3 & 4):211-407, 2014.
[22] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Theory of Cryptography Conference, pages 263-284, 2006.
[23] V. Feldman, Koren, and K. Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM the Theory of Computing, pages 439-449, 2020.
[24] R. Frostig, R. Ge, S. Kakade, and A. Sidford. Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization. In International Conference on Machine Learning, 2015.
[25] M. B. Giles.
Multilevel Monte Carlo methods. Acta Numerica, 24:259-326, 2015.
[26] G. Grimmett and D. Stirzaker. Probability and random processes. Oxford university press, 2020.
[27] Y. Gurevich and S. Shelah. Nearly linear time. International Symposium on Logical Foundations of Computer Science, pages 108-18 118, 1989.
[28] E. Hazan and S. Kale, Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-conver optimization. Journal of Machine Learning Research, (5(1):2499-2512 2014.
[29] J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms Il: Advanced Theory and Bundle Methods. Springer, 1993.
[30] H. Jiang, T. Lee, Z. Song, and S. C. Wong. An improved cutting plane method for convex optimization, convex-concave games, and its applications. In Proceedings of the Fifty-Second Annual ACM Symposium on the Theory of Computing, pages 944-953. ACM, 2020.
[31] L. G. Khachiyan. A polynomial algorithm in linear programming. Doklady Akademii Nauk, 244(5):1093-1095 1979.
[32] J. Kulkarni, Y. T. Lee, and D. Liu. Private non-smooth empirical risk minimization and stochastic convex optimization subquadratic steps. arXiv:2103.15355 [cs.LG], 2021.
[33] G. Lan. Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization. Mathematical Programming, 149(1):1-45, 2015.
[34] G. Lan. Gradient sliding for composite optimization. Mathematical Programming, 159(1): 201-235, 2016.
[35] D. Levy, Y. Carmon, J. C. Duchi, and A. Sidford. Large-scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems, 2020.
[36] H. Lin, Mairal, and Z.. Harchaoui. A universal catalyst for first-order optimization. In Advances in Neural Information Processing Systems, 2015.
12

---

[37] M. Mitzenmacher and E. Upfal. Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press, 2005.
[38] R. D. C. Monteiro and B. Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM J. Optim., 23(2): 1092-1125, 2013.
[39] A. Nemirovski. On parallel complexity of nonsmooth convex optimization. Journal of Com- plexity, 10(4):451 463,,, 1994.
[40] A. Nemirovski and D. Yudin. Problem complexity and method efficiency in optimization. Wilcy-Intersciennce, 1983.
[41] Y. Nesterov. Gradient methods for minimizing composite functions. Mathematical Program- ming, 140(1))125-161, 2013.
[42] Y. Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
[43] N. Parikh and S. Boyd. Proximal algorithms. Foundations and Trends in Optimization, 1()): 123 201-231,22 2013.
[44] A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In International Coference on International Conference on Machine Learning, pages 1571-1578, 2012.
[45] S. Shalev-Shwartz and Y. Wexler. Minimizing the maximal loss: How and why? In Proceedings of the 33rd International Conference on Machine Learning, 2016.
[46] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Stochastic convex optimization. In Proceedings of the Twenty Second Annual Conference on Computational Learning Theory,
2009.
[47] Y. Shi and R. Cornish. On multilevel Monte Carlo unbiased gradient estimation for deep latent variable models. In International Conference on Artificial Intelligence and Statistics, pages 3925-3933. PMLR, 2021.
[48] N. Z. Shor. Cut-off method with space extension in convex programming problems. Cybernetics, 13(1):94 96, 1977.
[49] A. Sinha, H. Namkoong, J. Duchi. Certifying some distributional robustness with principled adversarial training. International Conference on Learning Representations, 2018.
[50] C. Song, Y. Jiang, and Y. Ma. Unified acceleration of high-order algorithms under Hölder continuity and uniform convexity. SIAM Journal Optimization, 2021.
[51] K. K. Thekumparampil, P. Jain, P. Netrapalli, and S. Oh. Projection efficient subgradient method and optimal nonsmooth frank-wolfe method. In Advances in Neural Information Processing Systems, 2020.
[52] Tseng. On accelerated proximal gradient methods for convex-concave optimization. 2008
[53] V. N. Vapnik. overview of statistical learning theory. IEEE transactions on neural networks, 10(5):988-995 999, 1999.
[54] B. Woodworth and N. Srebro. Tight complexity bounds for optimizing composite objectives. In Advances in Neural Information Processing Systems 29, 2016.
[55] D. B. Yudin and A. S. Nemirovski. Evaluation of the information complexity of mathematical programming problems. Ekonomika Matematicheskie Metody, 12:128-144 142, 1976.
13


Reviews:
[{"review_id": "ws3g2j0XXrw", "reviewer": "Reviewer_x1ay", "summary": "This paper proposes a procedure that converts any optimal stochastic gradient method into an estimator of the optimum $x^*$ using the multilevel Monte-Carlo approach. The estimator has a smaller expected cost of stochastic gradient computation compared with the original stochastic gradient method. The authors demonstrate that the proposed estimator can be combined with existing methods to improve the computation complexity and provide alternative algorithms to other methods in different applications. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper has a strong theoretical impact on stochastic optimization due to the introduction of the simple optimum estimator, which has potentially lots of applications in the field. However, some necessary empirical evidence is needed to demonstrate the efficiency and the advantage of the proposed estimator versus existing alternatives. \n\nCan you provide an example where you have to call ODC multiple times to get the estimator in (1)? In addition, there are many theoretical results in the main paper that are not followed by any discussion on the optimality and the comparison with existing methods. For example, for Theorem 4, it is as least interesting to the readers in what scenarios the proposed Algorithm 5 will have advantage over the method in [32]. Even if your goal is not to beat their algorithm, it is still helpful to convey the proper message to readers how the results stated here are positioned in the literature.\n\nIt is a little bit concerning to claim Theorem 5 as a theorem since it is not completely proved. The conclusion in Theorem 5 depends on Conjecture 1, which is not proved but shown to be hard to prove at the end of this paper. \n\nIt is nice to see the theoretical improvement of the proposed estimator. However, since its biggest advantage is to reduce the sampling cost of stochastic gradient estimators in computation, there should be at least some simulation study on the applications discussed in this paper to compare the empirical performance of the estimator with other alternatives.   \n\nTypos:\nL10: “up logarithmic factors”\nL74: “we instead instead apply ...”\n\n---post rebuttal---\nI have read the authors’ responses. I will keep my score as “accept” as long as the authors made the promised revision about discussions of theoretical results and conjecture.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The major limitation of this paper is the lack of empirical comparison with existing methods, while its main contribution is to develop efficient and nearly unbiased gradient estimators, which are claimed to achieve optimal bias to the optimum point with much fewer stochastic gradient evaluations. \n\nI do not see any potential negative societal impact directly related to this work\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "v7xlB41QZBo", "reviewer": "Reviewer_p9S5", "summary": "The paper develops a new primitive for stochastic optimization – a low-biased and low-cost estimator the minimizer x* for any Lipschitz strongly-convex function. Specially, the author(s) use a multi-level Monte-Carlo method to turn any optimal stochastic gradient method into an estimator x*. The paper also shows the potential of the estimator through four applications. ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results could be interesting. However, the authors should explain why the contributions of the paper are important. I am still questionable about the contributions.\n\n1) Can you please explain what is “nearly unbiased gradient estimators” and “nearly linear-time”? Through the paper, I am still confused what these terms are. \n\n2) It is not clear what set X could be. Does it require to be bounded, closed, or convex? Or it could be for any set? \n\n3) For the strongly convex function in R^d, there is a unique optimal solution x*. In order to determine the set X containing the optimal solution x*, the computational cost may be high. If x* is not in X, then the problem of finding argmin_{x in X} F ( x ) may not be interesting since the solution could be on the boundary of X. \n\n4) Assumption 1 should be correct if set X is bounded. However, as discussed in [Nguyen et al, “SGD and Hogwild! Convergence Without the Bounded Gradients Assumption”, ICML 2018], if X = R^d, then the \\mu-strongly convex function f cannot be bounded gradients E || \\hat{\\nabla} F ( x ) ||^2 <= G^2 for all x in R^d. \n\n5) There are four applications listed in the paper, some numerical experiments to verify theory could be useful. I wonder if the author(s) could provide some interesting experiments to support the results. \n\n6) Proposition 2 and Theorem 3 require \\epsilon to be smaller than some fixed number. Therefore, the results in Proposition 2 and Theorem 3 cannot be considered as complexity result since it should hold for any \\espilon > 0. \n\n7) It seems that this paper can apply only for convex case. I am not sure how to generalize it to the non-convex case since it would have more applications. \n\nI am happy to raise the scores if my concerns have been addressed properly. \n\n---------------------\n\nAfter rebuttal: \n\nThank the authors for the response. I am still not convinced with the bounded assumption in the strongly convex case. Moreover, the lack of experiments is the true weakness of this paper. I have decide to keep my score unchanged. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "mME_HuR1X7", "reviewer": "Reviewer_DN81", "summary": "The paper proposes a constructive way to obtain an estimator of the minimizer of a Lipschitz strongly convex function $f$. Assuming that we have an access to a stochastic subgradient of $f$, we can run a variant of SGD that guarantees good complexity. Furthermore, the authors demonstrate on several examples how this estimator leads to new algorithms with a better complexity.\n\n\nI think it is a good paper.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n1. Although for optimization tasks (projection-efficient or gradient-efficient methods) different algorithms with the same complexity were known, I would say the proposed idea is more natural and easier to remember. The chapter with a non-smooth private convex optimization was not that interesting, especially taking into account the need to consider conjecture as an assumption.\n\n2. Comparing the proposed approach with [32] or [46], the authors state that the former is a \"simple alternative\". I understand it as previous approaches are more complicated. However, from the algorithmic point of view I don't see it, perhaps even the opposite.\n\n3. Corollary 2.1: I am not sure I understand the final complexity. In order to apply previous result, we have to use $\\sigma:=\\frac{\\sigma}{\\lambda}$ and $\\delta := \\frac{\\delta}{\\lambda}$, but this will give us a slightly different fractions in $O(\\cdot)$.\n\n4. I only checked mathematics for main results relating to the stochastic estimator, and they seem correct. The rest is a rather tedious calculation of various complexity bounds. Although it is possible that the authors have made a mistake, there is nothing contradictory in their statements and I am inclined to trust their results.\n\n\n\n__Minor__:\n1. line 74: two instead.\n2. line 84: subproblems.\n3. line 124: what is $X$?\n4. line 173: Why do we ignore $\\sigma$ as a constant in $\\tilde O(1)$?\n5. line 263: Why is $O(L^2R^2/\\epsilon^2)$ optimal? Subgradient method needs $O(LR/\\epsilon^2)$.\n6. The authors call their stochastic estimator as low-bias and low-cost. To me it sounds a big vague. First, these two notions are dependent: the smaller the bias, the larger the cost. Second, in general why $O(1/\\sigma^2)$ is considered to be as a low cost?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "0", "review_text": "", "extra_scores": {"ethical_concerns": "0", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "0"}, "extra_text": {}}, {"review_id": "dR5ghoeiQ6x", "reviewer": "Reviewer_zGn6", "summary": "The paper uses a multilevel Monte Carlo technique to produce a minimizer with a reduced cost and bias of a Lipschitz strongly convex function $f$ . The paper then applies this technique to obtain a cheap and nearly unbiased estimator for gradient of the Moreau envelope of Lipschitz convex functions, and presents different applications of this technique.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The current paper uses the Multilevel Monte Carlo method to find an estimator $\\hat x_*$ of the minimizer $x_*$ of a function $F$ that satisfies certain assumptions (see Definition 2.1). The bias of $\\hat x_*$ is $O(\\delta)$, the variance is $O(\\log(1/\\delta))$ and the expected number of gradient evaluations required by the estimator is  $O(\\log(1/\\delta))$ (see Proposition 1). This result is interesting and is new to me. Averaging $m$ independent draws of this estimator yields an estimator with bias $O(\\delta)$ and variance $O(\\log(1/\\delta)/m)$, which implies Theorem 1 for a suitable choice of $m$. \n\nUsing the fact that the gradient of the Moreau envelope of a Lipschitz convex function can be calculated easily from the proximal operator, the paper shows that their technique can be applied to obtain a cheap and nearly unbiased estimator for the gradient of the Moreau envelope (see Corollary 2.1). \n\nThe paper uses this gradient estimator and an accelerated gradient descent algorithm to design a projection-efficient convex optimization algorithm (Theorem 2). The authors note that their algorithm matches, up to polylogarithmic factors, the performance of a previous algorithm by Thekumparampil et al [39]. \n\nThe authors also use their technique to minimize the maximum of $N$ Lipshitz convex functions with $\\tilde O(N\\epsilon^{-2/3}+\\epsilon^{-2})$ complexity, improving upon a previous result by Carmon et al [14] (Theorem 3). \n\nFinally, the authors use their technique to provide a gradient-efficient composite acceleration algorithm that matches a previous algorithm by Lan [29] up to logarithmic factors (Theorem 4).\n\nThe paper also discusses potential applications to private convex optimization.\n\nThe results in this paper, especially those that improve upon previous results, seem interesting to me. On the negative side, the paper contains no numerical experiments, and I find it hard to read. Some suggestions:\n\n--It is probably better to present the applications in Section 1.2 in the same order as in later sections.\n\n--It is probably better to clarify the assumptions made on $\\psi$, rather than putting them in a footnote (page 4).\n \n--Line 138: the reference [26] shows how to optimize the function $f$, rather than the function $F$. This point needs to be clarified.\n\n--In (1), is it assumed that $J\\ge1$?  \n\n--It may be better to put Algorithm 9 in the main paper, rather than the appendix.\n\n------after feedback----- The authors address my comments well, so I increased my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I am not aware of limitations of the paper, except that it is not clear whether the algorithms in the paper are efficient in practice. ", "review_text": "", "extra_scores": {"ethical_concerns": "I am not aware of ethical issues regarding this paper", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Although there was no consensus here, I think the paper should be accepted based on the the new theoretical results and the novelty of the algorithm.

One issue that was discussed quite a bit was the lack of empirical evaluation, which is strange for a NeurIPS paper proposing a new algorithm (as opposed to COLT, for example). Most NeurIPS readers will ask "does this algorithm actually work in practice", and without an answer to this the paper seems incomplete. Indeed, without this information it is likely that several poor graduate students will spend time implementing and trying out the method. The authors could save these people by doing it once, particularly if the algorithm does not work well in practice. Further, there might be some hidden assumption/disadvantage that makes the algorithm work much-worse in practice than the theory indicates (a classic example is the finite-termination of conjugate gradient which never actually happens empirically). Because of this, I am recommending acceptance but do not think the paper should be considered for a spotlight or oral or awards.

Finally, the camera-ready version should *at least* include a qualitative discussion of how the algorithm works empirically. Some examples:
- "Despite its theoretical properties, we found that the algorithm did not perform well empirically. More research is needed on this topic."
- "Although theoretically-faster in the worst case, the algorithm performed similarly to competing methods when we implemented it."
- "The algorithm outperformed method YYY in a preliminary implementation on the standard problem of ZZZ, although we did not explore extensive numerical experiments."
- "The algorithm converged very-quickly in practice, although more work needs to be done on decreasing the iteration cost."
- "The algorithm does not appear practical at all, but we hope our work will inspire others to develop practical variants with similar complexity bounds."
Decision: Accept (Poster)