Descent with Misaligned Gradients and Applications to Hidden Convexity
Authors: Aditya Bhaskara
Ashok Cutkosky
Ravi Kumar
Manish Purohit
Venue: ICLR 2025 Poster (2025)
Keywords: optimization
gradient descent
hidden convexity
Primary area: optimization

Abstract: We consider the problem of minimizing a convex objective given access to an oracle that outputs "misaligned" stochastic gradients, where the expected value of the output is guaranteed to be correlated with, but not necessarily equal to the true gradient of the objective.  In the case where the misalignment (or bias) of the oracle changes slowly, we obtain an optimization algorithm that achieves the optimum iteration complexity of $\tilde O(\epsilon^{-2})$; for the more general case where the changes need not be slow, we obtain an algorithm with $\tilde O(\epsilon^{-3})$ iteration complexity.  As an application of our framework, we consider optimization problems with a "hidden convexity" property, and obtain an algorithm with $O(\epsilon^{-3})$ iteration complexity.

Published as a conference paper at ICLR 2025
DESCENT WITH MISALIGNED GRADIENTS AND APPLICATIONS TO HIDDEN CONVEXITY
Aditya Bhaskara University of Utah
Ashok Cutkosky
Ravi Kumar Google Research
Manish Purohit
Boston University
Google Research
Salt Lake City, UT
Boston, MA
Mountain View, CA
Mountain View, CA
b yaegmo coom
ashok@outkoskky.coom
ravi. k538gmma 1.1. 1.com
mpurohit Bggoogle.com
ABSTRACT
We consider the problem of minimizing a convex objective given access to an oracle that produces "misaligned" stochastic gradients, where the expected value of the output is guaranteed to be only correlated, but not necessarily equal to the true gradient of the objective. In the case where the misalignment (or bias) of the oracle changes slowly, we obtain an optimization algorithm that identifies an e-suboptimal point with the optimal iteration complexity of Ö( "); for the more general case where the changes need not be slow, we obtain an algorithm with (E=5) iteration complexity. As an application of our framework, we consider optimization problems with "hidden convexity" property, and obtain an algorithm with (c-3)) iteration complexity.
INTRODUCTION
The stochastic gradient descent (SGD) algorithm has been the workhorse of modern machine learning applications due to its efficiency and effectiveness in optimizing complex models. Unlike vanilla gradient descent, SGD operates by iteratively updating model parameters but using only a subset of the data in each iteration. In addition to significantly saving computational cost and enabling it to scale to larger models, the stochastic aspect of SGD helps escape local minima. The convergence of SGD is guaranteed by the fact that the gradient estimate, obtained in each iteration, is unbiased.
However, many applications lack casily accessible unbiased or low-variance gradient estimators, particularly when considering quantization effects, approximate preconditioning matrices, or explicit noise addition to achieve differential privacy (Abadi et al.] 2016). Unbiased gradient estimators can also be computationally expensive and there is often a trade-off between computational costs, bias, and the variance of the gradient estimators. The topic of biased gradients and understanding the trade offs have been extensively studied in the literature; see, e.g., Hu et al. (2023); Ajallooiaa and Stich (2020); Chen and Luss (011)) 8); Sahu et al. (2021): Condat al. [2022] Hu al. (2021) Bottou ct al. (2018): Beznosikov et al. (2023): Hu et al. (2019; 2020a b 20 Stich and Karimireddy (2020g Karimi al. (2019); /hhag al. (2024) y; Hallak and Levy (2024). See also the recent survey of Demidovich et al. 2023). which unifies many of the existing works, and the references therein.
Several of the existing models for biased or noisy gradients assume an "additive" form of noise, i.e., the gradients are additively perturbed; these additive errors naturally accumulate in the resulting bounds and do not vanish the number of iterations grows. In this work, we depart from this additive noise model and instead study the setting when the obtained gradient is misaligned because it is weakly correlated with the true gradient. An interesting aspect of our results that we can obtain convergence guarantees even when the gradients have a significant bias at the optimal point, which is not possible in many previous analyses (Ajalloeian and Stich 2020; Beznosikov et al. 2023). While our results are closer to some of the parameter settings in Demidovich et al. (2023). to the best of our knowledge, their bounds are either the general non-convex setting (where the guarantees are weak), or they make much stronger assumptions, such the PL condition strong convexity. Our study is also related to the recent body of work on online optimization with hints, where a weakly correlated hint vector 2020; 202T); however, in those settings, the algorithm sees the unbiased gradient after each step and can thus "correct itself", which is not possible in our setting.
sufficient obtain logarithmic regret (Dekel et al. 2017 Bhaskara et al.)

---

Published as a conference paper at ICLR 2025
Contributions and Applications. We present a high level overview of our results here and defer the formal statements to the respective sections. All of our results consider an objective function f: IR + R for which we are given a "misaligned" gradient oracle il such that E [z)())] may not be equal to V (xr), but (E[](z)), (x))) 2 O, for input x. That is, E(h(z)) points in roughly the "same direction" the true gradient V but it may be misaligned.
Optimization algorithms with misaligned gradients are broadly applicable. Below, we list three applications, each of which requires different algorithmic treatment, which we present in this paper.
Preconditioning involves transforming the gradient by multiplying with a matrix, and has become of increasing interest in stochastic optimiza- tion (see, e.g., Shampoo (Gupta et al.) (0018) and variants (Wang et al. 2024] Vyas et al.) 2025). AdaHessian Yao et af. 2021) or Sophia (Liu et al. 2024)). In these works, the gradient multiplied by preconditioning matrix, which one hopes is related to principled preconditioner such as the inverse Hessian or gradient covariance, but in general will only be an estimate. We can formally write E[h(x)] = A(x)- fxxx for some SPD preconditioning matrix A(z). Since A(x) is SPD, it is clear that h(z) is correlated with fz(z). Morcover, we might even hope for additional structure in the matrix (ar): since the target ideal preconditioner changes slowly with in many settings, might hope that Axx) also changes slowly. In this case, we prove that a variant of projected SGD) with momentum converges at the optimal rate of ((N-1/2) for any slowly-varying preconditioning scheme (Section B). where N is the number of gradient evaluations. Notably, typical analyses of stochastic preconditioning methods do not employ momentum despite its use in practice, and require disparate analysis techniques for different preconditioners. Our analysis in contrast critically uses momentum to take advantage of any slowly-varying preconditioning scheme. Note that the O(N -1/2) rate is unprovable even for error-free gradient oracles (Nesterov et al. 2018).
(I) SGD WITH APPROXIMATE PRECONDITIONINGS
(II) COMPRESSION SCHEMES IN DISTRIBUTED OPTIMIZATION: In a distributed setting, gradients are often compressed to reduce expensive communication. Common compression schemes such as top-k(-) lead to biased gradients (Sun et al. 2017). For example, consider a simple compression scheme that extracts and returns the fighest-magniid not unbiased, but it will be correlated. This application is similar to a setup previously studied by Beznosikov et al. (0023 Definition 2); our assumptions in Section 4 essentially identical, but our setting does not require the noise to go to zero when the true gradient goes to zero. Our work
entry of the gradient. Clearly, this scheme is
also improves previous analyses (e.g.. (Beznosikov al., 2023; Demidovich et al. (023) ) either by
relaxing strong convexity requirements or by providing better convergence guarantees.
(II) HIDDEN CONVEXITY: Suppose f Rd + R is a function that is non-convex, but there exists an invertible, potentially non-linear, coordinate transformation function P P:R. Rd Rd such that f(x)= = C()(z) for a convex function C: Rd + R. This notion of hidden convexity was recently studied by Fatkhullin et al. (2023) and captures many applications in different areas such as reinforcement learning (Sun and Fazel (02T), T), revenue management (Chen et al. 2024), and training neural networks (Ergen and Pilanci| 2021 Wang et al. 20022; Sakos et al. (2224) among others. In this case, the minimizer of f is also the minimizer of C, but we do not have direct access to C, so we cannot perform gradient descent. However, fxx) can be seen to be (C(())))))) where [ar) is the Jacobian of the transformation P at x. Thus, having access to a stochastic oracle for f is equivalent having one for C, where the gradient is transformed by Jacobian matrix in expectation. The challenge in this case is that we cannot evaluate C' at arbitrary points and instead must access it only through C(P(x)) without even knowing the value of P(x). In Section 5 we develop new algorithm and analysis. yielding a convergence rate of N 1/3, Prior work either assumes different smoothness conditions, access to the raw Jacobian (z). or achieves worse convergence rates.
Organization. In Section 3 we assume that the expected gradient obtained by multiplying the true gradient with an (unobserved) SPD matrix; further, these matrices do not change much over time. In Section 4 we consider a more general setup, where the expected gradient is simply assumed to be correlated with the true gradient. In Section 5, we consider the setting of hidden convexity, where we wish to minimize a (non-convex) function f of the form f(x) = C(P(z)), where is convex and
Giien a point x. h outputs random vector h(z);; see Section 3 for details on the setup.
whee is convex, we let fz(z) indicate an arbitrary subgradient x
2

---

Published as a conference paper at ICLR 2025
P is non-linear coordinate transform. Here, obtain unbiased estimate of the gradient of f; however, due to the transformation, this can be viewed as a misaligned gradient for C.
2 NOTATION AND PRELIMINARIES
Throughout, we deal with functions Rd + R. where d is the dimension, and denote by J. the minimizer, i.c., I. E argmin f. We assume ||x,1 I R for some scalar R. We write [T] (1....,7) for any integer T 1. Unless otherwise specified, || = |æ||| for any vector x E R denotes the usual Euclidean norm. For any symmetric positive definite (SPD) matrix M, we define the matris-induaed norm ||
MM. The operator norm of matrix M is defined as |Mop = infx(]] Mx I c||2r]|, Vol; when clear from context, we also use [| to denote the operator norm of M.
Projections. For D) 2 0 and x E R. let 1D [x] = gr || - y/l denote the standard (2-projection of x onto a Euclidean ball of radius D. We also perform projections using the matrix norm: for an SPD M, D 2 and x E Rd, let 11 [x] argmin y:1ly S
yllM-
Function properties. We say that function f is H-Lipschitz if for all x. y, we have -f f(y)l= H || - yll; note that this is equivalent to the condition that |/ [x)) I H for all æ. We also use the following standard definition of smoothness of a function:
said to L-smooth for some parameter if for all I, y, we have f(y) & f(x) + (Vf(z). - x) + 4 |y =1|
Parameter tuning. All of our algorithms assume knowledge of various problem parameters (e.g. H, L, or R) that are used to specify optimized learning rates and other hyperparameters. In practice, the learning would need to be adjusted using standard hyperparameter tuning techniques.
MATRIX-TRANSFORNE GRADIENTS
In this section, we assume that the misaligned stochastic gradients are obtained by a smooth matrix- based transformation. We start by formally stating the assumptions necessary in this section.
(A1) Oracle & Assumptions. Let ʃ be H-Lipschitz and convex. We assume that the algorithm has access to an oracle that generates stochastic gradients as follows: given æ, the oracle returns a random vector f(z)) with [[(())) s H with probability 1 and [[h(z)] = A(x) V fz() where A(x) e dxd denotes an SPD matrix that perturbs the stochastic gradients. As outlined earlier, such transformation 0. We assume that [|A(())- 1 Allop pl| vlla for any y Rdd and assume that the eigenvalues of A(x) lie in [Amiu Amax] for all Rd
ensures the condition (E [.)]. V f(r)
We design an algorithm that, after N queries to the misaligned gradient oracle, outputs a point x such that f(x) f(x.) < O Our algorithm can be viewed as projected gradient descent using the misaligned gradients, along with iterate-averinn averaigaver,ging;
Algorithm for details.
Algorithm
Optimization with Matrix- Transformed Gradients.
Require: Time horizon N, projection radius D, learning rate 17. Initialize:
I1 t 0, 0 2: for t= to N do
3: Generate misaligned gradient estimate: hg + h(xx)
4: Zt+1 f- [I 1yhss]
5: # variables Gr. are needed for connection with momentum (not used in analysis)
6: de f (2+ /211
7: me t 8.m (1 9r)g, with 8, = 2/(t
-+1
8: Te+1 1I 21 Ft 177
Connection to Momentum. In Algorithm T, we provide two equivalent forms of our update; the equivalence is demonstrated in Appendix A. for completeness. The intermediate variables in lines
3

---

Published as a conference paper at ICLR 2025
6-7 are not used in our analysis, but they provide valuable context for our method. If we were to ignore the projection step in line 4 (which in practice one expects to only rarely be active) then Ir h4/ 2 and the definition of m, in line 7 and the second form of the update in line 8 is exactly the same form as standard SGD with momentum. Thus, our analysis in fact shows that the addition of momentum helps correct for gradient misalignment. This is significant because standard theoretical analyses of preconditioned algorithms like Shampoo frequently do not employ momentum, even though the methods used in practice do; our results are step towards filling this gap.
Overview of Techniques. Our analysis is based on several known ideas in stochastic convex optimization such as itcrate-averaging and projections. but we need apply these in a carefully crafted manner to obtain our result. First, our iterate-averagin scheme is not the vanilla Polyak averaging- we query gradients at the running average rather than only averaging once the end. This gives our iterates natural "stability" property: ||x++1 xell = (1/tt) which is critical in our analysis. Secondly, the projection steps are not used to ensure feasibility (as often the case in constrained optimization), but indeed to control technical issue in which the iterates move too far from the optimum point. Although not recognized by many analyses, this last challenge is usually not present with unbiased gradient oracles they never cause the SGD iterates to stray far from the optimal point (Carmon and Hinder 2022).
Finally, since algorithm updates the iterates using misaligned stochastic gradients such that E[h,] = Agg. where A, = A(x²) and 9: = (x+), is convenient for the analysis to work in the matrix-induced norm || ll.. Unfortunately, the algorithm does not know the matrix A,, so we
cannot perform the projection step in Algorithm [| using the matrix- norm. The key idea is to show that by appropriately setting the projection radius D, the f2-projection performed in Algorithm iss equivalent to projecting via the matrix-inducee norm into different domain that nevertheless still contains the optimum T..
Lemma 3.1. Suppose A E Rdxd is an SPD matrix with all eigenvalues in [Amins Amax] Let > 0 and let Rv Amm.. Let x. E Rdd be an arbitrary vector. Then there exists a K such that [1][z] = A [x] and for all x, with ||z.|l2 S R, it holds that ||*,|l S K.
The proof relies on showing that our definition of TT (a)) is always some scalar multiple of x. The condition number guarantees then imply the lemma.
Theorem 3.2. Assume (AI). Let ;1,..., UN be the iterates produced by Algorithm 7 when we set
the projection radius D = RV/ Amax and step size n
R2, /2)mm + y y (Ry Denasa >mmn)
where
Amin
H +1 Daaia VN
H.N O(log N) is the Nth harmonic number. Then the final iterate EN satisfies:
4pR
Amaa Amin
3/2
HN
(Xmax + X
(v
ZAmmn
log N
[[f(eN) - f(x))] 2RH
o
N
Proof. We first note that since we use iverate-averaging, the iterates are stable. We have,
||
E 2 Ei
|
-
Σ
t-1
((-
24
24
1 | zell -
2D (1)
where the inequality follows since both Tz-1 and 2, have norm at most D.
Let Q: V f(r.)) (unknown to the algorithm). Then using anytime online-to-batch conver- sion (Cutkosky 2019 Theorem 1), we have the following
N
[[f(xn) f(z,((
E
Σ
(gt,
x.m
(2)
To bound the RHS above, we start by analyzing the distance between the 2, 's and By Lemma
3.1 there exists some K, E g+ such that 2t-1 = -| - mphl] = 11 [Ra - nhh). and
For completeness, we include self-contained proof in Appendix A.3
4

---

Published as a conference paper at ICLR 2025
| Kt. (Notice that we are working with the norm induced by A, Since assumed
that Ag is an SPD matrix with eigenvalues in Dminn Amax,, A, is also symmetric positive and has eigenvalues in [Amixx Amnl- Hence, we have:
|| | xx S 1| - 1//1 Ix 0= 1|2,-
= 1| - J. 2.122,- - 20/(1e, (2 - xx)) + / A-
(3)
Let = h1 - B[he] = he - Aigh Then we have E[rl] = and Bi |ree || - hellhell? 1 H². By
substituting h, Agg: + T2. we can simplify the two terms in (3) as:
|| = (Aist + rt)) (A.ge + mz) gi Agge + r T A, + 2
-1eell1,, + 11re 1| A + rz),
Ar A, xx)) (Aigr + rr. Ar (2+ x.)) (ge, 2t z.) + (r,, A (2+ xx)).
(4)
Substituting back in 3 and taking expectations (and using E[[r]] = 0) yields:
Bll|a++1 Fx || < B[[l= 1054-2-4, ==.1),,11 21/(1e ā x.) n/=lllgel 11 + 1/ |
(5)
Rearranging and summing:
N
2| 2= 21112,-
||
(es 5t ram)
S
21
21
N
2|
x2113
1|
I. 11
N
+
A7-1
17
Σ
[1se11., + 11
2m
2
1=
(6)
To simplify, let us consider the following expression:
|| x. 11,,, ||
2.
11
A,
|| r= راا A,7- ; -2+
I,, (A,
A x.))
< || - r. 12 ||4,*
A-1 llop || - x, 1|2 = || - 1.112 ||A, -A
P. 1121-1111 - S p- (2D)² 2 2D SpD3
-
t t
where the three inequalities follow from Kauchy-Schwarr the assumed bound on the operator norm, and respectively. We can then substitute back into (6) and replace Σ 1 S Hyy where HNN = (log N) is the Nith harmonic number. We also note that [19.113, S 11 ||llA and S ||r |1 1 Resuming,
| 2 A,
||
x. 112 1|A-1
8pD2HHN +
Σ (gt, 24 x.,)
S IE
Σ
-1rellaa1))
2n1
241
||
x.A
A
8pDDHN
+
17
N Σ
119 13,, + +1rel12,,
2n
2n
2
t=1
||2| - xx
xx,11
8pD3HN
+ n H2 (max ||Aeelop + ||A=5|lop
2n
2n
R²
Spxaie R&HN
Amax +
2
2/2
Amain
To balance out the terms, set the learning rate 77
1 V R2 1P/22min 4pHLN N (R Amaxx Amin) )3
H 1/Xmin V N
and get the following, which along with 2 completes the proof:
3/2
E
Σ 9r, 2 xx)
< 2RH
N
1
+ 4pH
Amax
H.N
(Amase +
1
2Amin
Amin
Amai
5

---

Published as a conference paper at ICLR 2025
4 GENERAL MISALIGNED GRADIENTS
In the previous section, we assume that at time t, the gradient oracle returns a vector he such that R|/a] Aige and further assume that the matrices A, (xxx) change slowly time. We now consider a more general settin in which E[hh]] is merely positively correlated with the gradient Jt. which is a weaker assumption. particular, this allows [h/]]] o even when 9r O. We formally
specify the gradient oracle and our assumptions below.
(A2) Oracle & Assumptions. Let Rd + R be H-Lipschitz convex function. Let x., argmin f satisfy ||=,,|| S R some known parameter R. Let the misaligned stochastic gradient oracle for f. We assume that the oracle h satisfies the following correlation conditions: for any input x, h(x) outputs a random vector such that:
[h(=))l < H with probability I, The expected output {(x) == E[h(x)] satisfies the condition (Vf(z).E(x)) 2
Il for some parameter a, and
|[(x)]] 2 [(>)]l for some (possibly unknown) parameter 3.
We assume that outputs for different calls h(r) on the same input x independent. It turns that our arguments hold more generally, but we would need the assumptions above to hold conditioned on the "query history". To simplify the presentation, we will assume independent outputs.
We now present our result for optimizing smooth convex functions, given access to a stochastic oracle that outputs a misaligned gradient, subject the correlation conditions defined above. addition to the assumptions above, we assume that / is L-smooth (see Section 2b.
The main result-stated formally in Theorem 4.4 shows that after N queries to the misaligned gradient oracle, the algorithm obtains a point such that f(x) f(x.) ONN11/3) Our algorithm can viewed as SGD with mini-batches, but with two key modifications: (i) we move along the normalized gradient estimate using carefully designed step size schedule, and (ii) we add novel correction step that prevents the iterates from being too far from the optimum. Algorithm 2 presents the full details. In the following, let [2]_ denote min(2, 0).
Before the analysis, 1et us briefly compare this result to those in Demidovich et al. (2023), which considered broadly similar setup. Their results for the convex case either require p-strong convexity and achieve convergence rate of ((1/(p2
achieve O(1/N1/4) without strong convexity. Our result does not require strong convexity and achieves ((1/N1/3), Note that, unlike in standard unbiased optimization, we cannot simply regularize non-strongly convex objective to become strongly convex because this can destroy the correlation structure in the gradient estimates.
Algorithm 2 Smooth Convex Optimization with Misaligned Gradients.
Require: Time horizon T, norm bound D, sequence BI...., By of minibatch sizes, sequence ......, .T of learning rates.
1: Initialize:
F1 f-
2: for = to do
3: Generate a misaligned gradient estimate using minibatch of size B, by calling on
same point B, times and taking the average, i.e., by < B, EB= h(x²)
4: T hi and #e+1 It 7/,
[..]
5:
if | > D then
[Te
6:
E++1 +- It - mhh + 1/t
7: else
8:
I+41 + 8141
First, we show a few technical statements. The first shows that the norm bound remains bounded throughout. This is a subtle consequence of the extra -1j² T term inn our update for large iterates. Roughly speaking, this extra regularization is "just enough" to keep the norm from growing matter

---

Published as a conference paper at ICLR 2025
what the noisy gradient h4 is. It is possible that standard projection step would also suffice, but this explicit update is more amenable to our analysis. Lemma 4.1. Suppose tte S D/2. Then for all ||zell S D.
Proof. We proceed by induction. Suppose || < D. Now, if || & D, then F++1 1 so there is nothing to prove. So let us assume that | > D. In this case, note that we also have | 2
[++1| Th 2 D/2. Thus, /t/
| <
Next, define u, h4 [ th, |
By definition, we have (ue, m2) 2 and also ||u/ S 1, since
Uy is either 7ú itself or the projection of ht orthogonal to the direction of xt. Therefore:
| 1 -
||
1/2
+ n
|| 21/ +
1/6
+ m1 ||u, 11
|
|
Wi
lare|l
1
n/²
-1
112 D.
1
|are|
Next, we need the following simple geometric lemma. Lemma 4.2. Suppose that g and satisfy the conditions (g. ft) 2 |||||||b|l and || 2 Bllg for some parameters 3 > 0 and a E [0, 1]. Then for any 6, we have
h + 5
2a
9
4|
9:
1 + 511
3
B
The next lemma gives us the key technical property required for our final analysis. It also shows the dependence on size the minibatch, B..
Lemma 4.3. Let t be any step of the algorithm, and suppose that ne D/2 and D 2 12R/a. Then (lV F141 xx)] < woll H())l
S.
3
BVB.
Proof.
Throughout this proof, write 9. (x))) First, define ò, h4 E[he], and for
convenience, write & = B[/... Recall the correlation conditions satisfied by &.. Since we make B queries to the oracle using the same Tt and since |/tel| S H, we have B[] [1 4/12/ and thus
E|][6e||] < 2H/ /B. We now consider two cases:
Case 1: |لt+1 < D. Since T++1 It nhh by applying Lemma 4.2 with & taking the role of by in the lemma statement, we obtain
(gt, F+41 xz) < 2
4nel10al
3
B
Case |1 > D. Since Nt < D/2, we must have |!rlll 2 D/2. this case, x4+1 It niti + m (sha -x ||
m
21 and thus
[Te, [1), (9c, xx)
(ge: zzd ni
(10, IZ) = no Tho) + m7
(8)
||22|
|| 11
In this case, we first note that if (ge, nx) 2 O, there nothing to prove, because the last two terms on the RHS above will be non-pont non-positive (since [2] < O for any 2).
Thus, let us assume that (g) O. In this case, we note that because (gt, - xx) (which
holds by convexity), we have
(gt,
11 ||
a |lgell
||xe|l
||æeel
||
In the last step, we used the fact that ||aeel 2 D/2 > 6lt by choice, and || || s R. Thus, plugging this into 8) we have
a [T,, x xx)] Il
2 a | +
Te+1 - xz) < -nc Fee)
6 [
6 |
7

---

Published as a conference paper at ICLR 2025
S Th
- (rt, he)
a
lIgell
+
ni
gt a
6 x
In the second step, we used [z]- -|2|, together with Cauchy-Schyee Applying Lemma 4.2 as before, along with the fact that 7h - 1/2 < | we have
21+1 - xx) - 2ma gel
417 |oell
a
1
a
lI
4m ||
1
+
17
+
3
3
6
6
3
8
Thus in both the cases, we have
(gt, Ze+1 21) S maal
4n |6-1
- nhall
8n, H
Bl ge)
Bv B.
We can now prove the main convergence guarantee. Theorem 4.4. Assume (A2). Let = 12R/ a, and set
12 B. (1+1+ m
6D
k
a(t +
+++
At the end Tf iterations of Algorithm the total number of gradient evaluations is N = O((T) and
5200
RH 02
LR
E[f(xT) fxx))1
N1/3 log T
a²
Proof. As before, write 9r fxz) We start by bounding | k 2 12 the property ne I is always satisfied.
22ll- Note that since
|| S D, then we have || - xell = Th. Otherwise,
Fr (Tte, (1)) 30
X4 |1=
Ze41 3z S n7
| ?1
As we saw in the proof of Lemma 4.1 the term in the parentheses is the projection he orthogonal Fı. and thus it has norm 1. Likewise, because ||ar=|| D/2 /2 7/. in this case, the last term also has a norm bounded by nh. This implies that || - xzll - 2m.
The analysis is based on analyzing the potential function 4, (I (x)))))) ((x))). By definition,
Φ 4; = (t + ()(f(==1 - f(x))) + (f(x)) - f(x))).
By then using smoothness and applying Lemma 4.3 we have
L ([((()))) fxx)) < E (0, 2x) |00+11 2z 12 mha malllal
8m H
2T
B/B.
Also, convexity implies that f(x;) f(x.) < (gt, x.) S 2D || Now from our choice of the parameters, 7) will satisfy the condition 2D (++1+k)ma Plugging these in, we have
88 H BVB.
E - D S (++1+k)
2
Plugging in the value of Br, 1/. and D. we have
8m, H
48 DH a:((1
72 LD
E E
Tel (t 1++
+ +2Ln]
B(L+ 1 k))
a2(+++
2592
R.H.
LR²
(t (++1+h)
a23 A
Summing this over we get
T k k+1
RH
LFº a
E [
S $ + 2592 log
2
8

---

Published as a conference paper at ICLR 2025
Since start at the origin, we have du < kR [V
I kRH, so this term can be ignored by
slightly increasing the constant in the second term. Thus, by the definition of the potential,
2600
RH LR
(IT())) - [(x+))] S
T log T
o2B + α
Now, observe that the total number of queries to the oracle is
N Σ B ST. BT = T
87
assuming T> k. Thus, T 2 11/3 /2, and plugging this in, we obtain
5200
RH
LR
B[((xT) f(x.)) f
log T
a²B +
N1/3
a
5 HIDDEN CONVEXITY
In this section, we consider the optimization of (non-convex) functions that admit a convex reformu- lation. We start by recalling the notion of hidden convexity defined earlier: f Rd -> IR is function that can be expressed as f(z) 1 (=)())) Vx, where C : RR + R a convex, H H-Lisschitz function, and P: Fd - IR is an invertible, possibly non-linear, coordinate transform function. Let J (zz) be the Jacobian (total derivative) of P at æ. Since P is invertible, we also have that (xx is invertible for all (indeed, this only requires local invertibility for P).
In contrast to some previous work on this problem (Fatkhullin et al. 2023), we do not assume that the convex function C is smooth-instent the composition f will therefore not be smooth in general. This allows us to more accurately model applications with non-smooth losses (e.g., neural networks with ReLU layer). Previous studies involving similar non-smooth setups generally achieve weaker results. Sakos et al. (2024) develop algorithms assuming that we have access (z), which we forbid, and Chen al. (2024) provide
will assume that the transformation P is smooth. Note that
method that fits exactly our setting to obtain convergence rate of O(1/N1/1) whereas we obtain convergence rate of O11/N1/3).
(A3) Oracle & Assumptions. We assume that there exist constants a. 8. > 0 such that for all y Rdd we have (=)]lop S 1/a and (x))oo S 1/B, and J())))
-l| y|l- For technical reasons, we also assume knowledge of parameters D,, D2 such that for all |||||| Di and ||y|| D2. f(y) 2 f(x). We have access stochastic gradient oracle for f that we call For any input x, h(()) outputs a random vector satisfying (i) [[(x)]] < H with probability 1, and (ii) [[]())] = (xx). As we discussed earlier, f((x)
(er))(C(((r))) thus the oracle provides VC at the point P(x),, with transformation matrix applied.
We first show a couple of technical lemmas on hidden convexity. The first lemma upper and lower bounds the distortion of the distance between any two points due to the coordinate transformation.
Lemma 5.1. For all x, y E Rd, B|Ix yl < P(x) P(y)]
< ||a-v]
Next, let B(x, 6) = {y - S 8} denote a ball of radius ô centered at æ. The following lemma shows that if the function value does not drop significantly anywhere in a small ball of radius around a point x, then x is close (in function value) to being a global minima of f. (Thus, hidden convexity implies a guarantee very similar to convexity.)
Lemma 5.2. Let x be arbitrary point and D O be such that ||ж||| S D and ||x.-| || & D. Let B = (xx,00 8) be a ball of radius ò < D centered at x. Suppose that sup=eB( [z)] S for
some 0. Then,
((c)- < (1
3D
a,35
Algorithm Outline. At each outer iteration (corresponding to k), the algorithm performs an opti- mization in a ball around x k. of an appropriate radius. If the ball contains x., the algorithm can terminate. If not, can guarantee (using Lemma 5.2 that 2 k+1,1 is closer z,, Thus with growing k. the centers of the balls are guaranteed get closer and closer to T..
The key technical lemma is the following:

---

Published as a conference paper at ICLR 2025
Algorithm 3 Optimization of Hidden Convex Functions.
Initialize:
Ii + 0, k +-
2: I1 2D
3: for k = 1 to K do
4:
Tx x- 2
5:
dR & PVTa
6:
+ HVT.
7:
if k o then 1 +-
200 ag5
8:
for i= to L do
9:
Xh: -- for ||æ: - 2=/"'l || S 8x
10:
for 1 to Ti do
h h(a R.d)
k.i - xt 1 n, $1 E++1
12:
Choose zb uniformly random from {a) ..... TT.
k.d
14:
if 1
D2 then
15:
k 11
D
16:
else
ki++1 k.
17:
I1
k+1,1 f- 11
kTTx+1
18:
Return è <- +11
19:
Lemma 5.3. Algorithm 3 ensures for all ls 2 2:
((((()))((xA)))) 20 HD2
aB3/2k
The proof is quite involved (see Appendix C.1 With this, the main result is the following.
Theorem 5.4. Assume (A3). Let N = En IxTr be the total number of gradient evaluations by Algorithm 3 Bnnd &t be the final iterate. Then we have
1//3Hp H/3
(ff())-((x.)))
(a.3)/331133
6 CONCLUSION
We have developed algorithms to minimize convex function given access to misaligned stochastic gradients, Misalignments can be specified using linear transformation and may or may not vary smoothly with the input point. We obtain different convergent rates for these two cases. We then use these insights to develop an algorithm for minimizing non-convex functions that have a "hidden convexity" property, i.e., there is coordinate transformation that make the function convex.
Our work raises natural open questions about the optimality of the results: can the - iteration complexity in two of our results be improved? In the hidden convex case, improving to c is conceptually very interesting, as it would match the convex case. Another "structural" question is we can obtain one meta-algorithm from which different algorithmic results can be derived. We currently require different projection steps and additional tricks to deal with non- non-PSD transformations. Yet another question would be weaken some of assumptions (e.g., bounded gradients).
REFERENCES
Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In CCS, pages 308-318, 2016.
10

---

Published as a conference paper at ICLR 2025
Ahmad Ajalloeian and Sebastian U Stich. On the convergence of SGD with biased gradients. arXiv:2008. 00051, 2020.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. JMLR, 24,276):1-50, 2023.
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online learning with imperfect hints. In ICML, pages 822-831, 2020.
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Logarithmic regret from sublinear hints. In NeurIPS, pages 28222-28232, 2021.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223 311,, 2018.
Yair Carmon and Oliver Hinder. Making SGD parameter-free. In COLT, pages 2360-2389, 2022.
Jie Chen and Ronny Luss. Stochastic gradient descent with biased but consistent gradient estimators. 1rXiv:180.111880 2018.
Xin Chen, Niao He, Yifan Hu, and Zikun Ye. Efficient algorithms for minimizing compositions of convex functions and random functions and its applications in network revenue management. Operations Research, 2024.
Laurent Condat, Kai Yi, and Peter Richtárik. EF-BV: A unified theory of error feedback and variance reduction mechanisms for biased and unbiased compression in distributed optimization. In NeurlPS, 2022.
Ashok Cutkosky. Anytime online-to-batch, optimism and acceleration. In ICML, pages 1446-1454 2019.
Aaron Defazio. Momentum via primal averaging: Theoretical insights and learning schedules for non-convex optimization. arXiv:2010.00406 2020.
Ofer Dekel, Arthur Flajolet, Nika Haghtalab, and Patrick Jaillet. Online learning with hint. In NIPS, pages 5299-5308, 2017.
Yury Demidovich, Grigory Malinovsky, Igor Sokolov, and Peter Richtárik. A guide through the zoo of biased SGD. In NeurIPS, 2023.
Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep ReLU networks via convex programs. ICML, pages 2993-3003, 2021.
Ilyas Fatkhullin, Niao He, and Yifan Hu. Stochastic optimization under hidden convexity. In OPT 2023 (NeurIPS 2023 Workshop). 2023.
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimiza- tion. In ICMI., 2018
Nadav Hallak and Kfir Yehuda Levy. A study of first-order methods with deterministic relative-error gradient oracle. In ICML, 2024.
Bin Hu, Peter Seiler, and Laurent Lessard. Analysis of biased stochastic gradient descent using sequential semidefinite programs. Mathematical Programming, pages 1-26, 2020a.
Xiaowei Hu, I. A Prashanth, András György, and Csaba Szepesvári. (Bandit) convex optimization with biased noisy gradient oracles. In AISTATS, pages 819-828, 2016.
Yifan Hu, Siqi Zhang, Xin Chen, and Niao He. Biased stochastic first-order methods for conditional stochastic optimization and its applications in meta learning. In NeurIPS, 2019.
Yifan Hu, Xin Chen, and Niao He. Sample complexity of sample average approximation for conditional stochastic optimization. SIAM J. Optimization, 2020b.
11

---

Published as a conference paper at ICLR 2025
Yifan Hu, Xin Chen, and Niao He. On the bias-variance-cost tradeoff of biased stochastic optimization. In NeurlPS, 2021.
Yifan Hu, Jie Wang, Yao Xie, Andreas Krause, and Daniel Kuhn. Contextual stochastic bilevel optimization. In NeurlPS, 2023.
Belhal Karimi, Blazej Miasojedow, Eric Moulines, and Hoi-To Wai. Non-asymptotic analysis of biased stochastic approximation scheme. In COLT, pages 1944-1974, 2019.
Hong Liu, Zhiyuan Li, David Hall, Percy Liang, and Tengyu Ma. Sophia: A scalable stochastic second-order optimizer for language model pre-training. In ICLR, 2024.
Yurii Nesterov et al. Lectures convex optimization, volume 137. Springer, 2018.
Atal Sahu, Aritra Dutta, Ahmed M Abdelmoniem, Trambak Banerjee, Marco Canini, and Panos Kalnis. Rethinking gradient sparsification total error minimization. In NeurlPS, pages 8133- 8146, 2021.
losif Sakos, Emmanouil- Vasileios Vlatakis- GaaaakiiGGar Panayotis Mertikopoulos, and Georgios Piliouras. Exploiting hidden structures in non-convex games for convergence to Nash equilibrium. In NeurlPS, 2024.
Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed updates. JMLR, 21(1):9113-9648 2020.
Xu Sun, Xuancheng Ren, Shuming Ma, and Houfeng Wang. meprop: Sparsified back propagation for accelerated deep learning with reduced overfitting. In ICML, pages 3299-3308, 2017.
Yue Sun and Maryam Fazel. Learning optimal controllers by policy gradient: Global optimality via convex parameterization. In CDC, pages 4576 4581, 2021.
Nikhil Vyas, Depen Morwani, Rosie Zhao, Itai Shapira. David Brandfonbrener, Lucas Janson, and
Sham Kakade. SOAP: Improving and stabilizing Shampoo using Adam. In ICLR, 2025.
Sike Wang. Jia Li, Pan Zhou, and Hua Huang. 4-bit Shampoo for memory-efficient network training. In NeurlPS, 2024.
Yifei Wang, Jonathan Lacotte, and Mert Pilanci. The hidden convex optimization landscape of two-layer ReLU neural networks: an exact characterization of the optimal solutions. In ICLR, 2022.
Zhewei Yao, Amir Gholami, Sheng Shen, Mustafa Mustafa, Kurt Keutzer, and Michael Mahoney. Adahessian: An adaptive second order optimizer for machine learning. In AAAI, pages 10665- 10673, 2021.
Siqi Zhang, Yifan Hu, Liang Zhang, and Niao He. Generalization bounds of (onconvexx(strongly) concave stochastic minimax optimization. In AISTATS, 2024.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML, pages 928-936, 2003.
A MISSING PROOFS IN SECTION 3
A.1 EQUIVALENCE UPDATE FORMS IN ALGORITIMM
Our analysis of Algorithm I makes use of the "anytime online-to-batch" conversion result of Cutkosky (2019). However, this approach (under the alternative name "primal averaging")) was shown to be equivalent to SGD with momentum (Defazio 2020). Here we reproduce the necessary calculations:
Proposition A.1. For any sequence 21,...; 2r of vectors and any scalar n, let me and define
t = 21. Then consider the sequences:
2t 2
(1
2
2ğ.
g.
m+
m + + I'
#141 2, 1p74
Z41
2n
t+1
t 1
Then is xz for all l.
12

---

Published as a conference paper at ICLR 2025
Proof. First, note that
to (t - 1) 21
() -ze).
We proceed by induction. From direct calculation, mi (21 22)/n1 that 22 x1 32 21 =1--22 T2. Next, let x; i for some all Then clearly rmm, = 2i+1 xy for all < t. Now,
T++1 = 2t + 2++1 3t.
t 1
(21+1
21) + (zt - x1)
2t +
t+1 1
219h
Tt Zt
4t
t + 1
t 1
2n9
(t - 1) 1) x(-1)
8t
t+1 1
t+1
21
11(1 1)m4-1
5t
t +
t+1
2
21/er
$t
1
1114-1
t+ 1
8+1
A.2 PROOF OF LEMMA 3.1
Proof. First, consider the case ||0||e < D. this case, IIp [x] = æ, and so we can set oc to achieve IT [x]
IT [ar]. Furthermore, ||æ= K for all F.-
Next, consider the case ||>||e > D. We have II [x] = Dæ ||=||
Let be the projection, that argmin bIlASk ||I x13.. Therefore by Lagrange multipliers:
2A(v - r) AAe.
Therefore is the point that satisfies for some a:
|ulla = VoT Au = K and
aAv = A(x v)-
For K = D||=| and a 1 - D/||z/12 2 0 and we can verify that:
D
[x]]=>] =
||0||| K,
||= 2
A(x - 1T [x]) = A(x Da/1|=//1)2 A(1 - D/11=/12)x = ax..
So. this shows that [p [z]. It remains to show that lla S K for all w, such that
|| & R. To this end, we compute:
wT Aw
|| < xr. 12.1l2
V sup
$ / Amax
||r.112 I /maxx R
w T Aw
| K,
= DDDAAmin D.
"vin I
inf
S D
|
where we used the fact that symmetric.
A.3 GRADIENT DESCENT WITH (TERATE-AVERAGING
For the sake of completeness, we now give a short proof of Theorem 1 from Cutkosky (019 on iterate-averaged online gradient descent that used in Section 3
13

---

Published as a conference paper at ICLR 2025
Theorem A.2. Suppose 21 Ei=1 24. Then for any convex F and point u, for all T:
F(ET) - F(u) (V --
T
Proof. Define 9t (x))) Then:
F F(u)= $ Σ gr, u) Σ
ge. 3t -2))
(gt, 21 u)
1=1
Observe that 24 21 (t () -xt):
T
Σ (1,, + (gts 2t -w)
T < (1 (1- (1 F(x)) +
T
Σ
Σ (ge, 2t u).
The last step also follows by convexity. Rearranging and telescoping completes the proof.
B MISSING PROOF IN SECTION 4
Proof of Lemma 4.2 We consider cases:
Case 1: ||ō|| 2
|hll Here, 4|15
M||
2 2 |[g|l. Thus the RHS of ( is < -1iggl and the inequality
2
B
#
trivially holds by Cauchy-Schward
Case 2: || < 2
||A|] Here, we have
3 |ill
| 2
8 >
> 11/
811
2
Now, by the triangle inequality and the hypothesis, note that (g. h Plugging in the above inequality, we get
5) 2
|[ll] [b]] - ||ll| ||]]]
(g. h - 5) 1/ + 811
|
|gll|
2a ||
2 ||
||8||
|99ll
8
C MISSING PROOFS IN SECTION 5
Proof of Lemma 3.7 We show that (P(x)-((y))) < lr-v/| The other claim follows symmetrically since J-1 is the derivative of p-1 at P(x) and ir = P- (Pxx).
Define h((t) fl x²). Then have:
d P(h(tt) P(M()) [P(h(t)) - P(h(0))) ((
P((()) - P(h(O)) P(O)))
dt
11 1
< ((((()))) = - [((((t))]
where the second inequality uses the bound on the operator norm of J. Therefore, we have
|| xl1 dt
11 xll
PP()) P(x) P(M(1) P(M(O)
LI
a
Proof of Lemma 5.2 Let B (P(v) E B(x, 5)}. Consider the line segment connecting P(x) and P(x.) and let be the intersection of this line segment with the boundary of B. Then we must
have |P- (q) x 6, and by Lemma 5.1 4 P(x) 2 $5.
14

---

Published as a conference paper at ICLR 2025
Next, ||=||| < D. ||=11 D. and (g) =|| =. By the triangle inequality we have (P-1(g)
J. - ( x | x. s 5 2D S 3D. By Lemma 5.1 we have ||g P(x.)) Il - 3.2
Finally, since q is on the line segment connecting P(x) and P(x.). holds that
- P - (P(x) q).
- P(x.)
Therefore, we have
f(x) [(x+) C(P(x)) ((P(=)))C(((x.)))
C(P(=)) C()) -
$ c(((())) + ((1)+ +VVC())) P(x.))
(1--((ss)]]
s cC(((=)) C(2) + [P(x) gll (VC(g), g)
(1+ [ - all
(q--P(a))]
$ (C(P(z)) - C(a))
[I+ 3D
s (C(P(x)) - C(a))
a:30
3D
3D
= -(P=))((P
1+ ag3
S c
1+
a,3
where the first and third inequalities follow from the convexity of C and the last inequality uses that p-1 (q) E (xx,
Proof of Theorem 5.4 Notice that I S 4D2p. Since 8 < 1/p and since D2 2 aB/p. it holds that
1. I D0 for all k 1. Therefore, the total number of iterations is at most:
0366g
40D2p aB
K Σ
80D2p 23K/2
N
I = 8D2p
23h/2 < 8D2p aB
k=1
k=
Next, by Lemma 5.3
have:
HDz
D4/S H
E[(( fxx+)(
20
S0
a.3v2K+1
(a:3)/3N1133
C.1 PROOF LEMMA 5.3
Proof of Lemma 5.3
We proceed by induction. For the base case, consider A = 2. From unrolling
Lemma
we have:
Bf 21 f(x.) = E[f(x] 1.T: +1]] f(x.)
[[ f(xx)) - In PHH., 4pHó? (1+ 4D2
}
S max
a,d; )
since f is hidden convex and D2 2 R, we have that / (x11')) ((xx) S HD2. Also 1 = 2D2p = D2/(p6f) and so the first term above is at most O. So, we have:
4D2
S <4pH69
1+
cx35
recalling that D2 2 as/p and 81 S 11/ps so that 1 < D2/(a,81):
MH o D28 20 HD2
< 20 aB
2
Next, for the induction step. suppose E[((x> [(x+)] < 20-
HD2
20 for some k.
a3v2"
a3
Then unrolling the result Lemma C yields:
[a (1))) ((x))
(. f(x+)
15

---

Published as a conference paper at ICLR 2025
4D2
I max [[f(x)")) - Ix pH1 4pHlo7
1+
0,36x
4D2
= max
-1 1 pH6 4pHo
1
0,36
using D2 aB/p and òR 11pp
Elf (f 1 -HH 20 PH D2
I max
a.
Eif(x 4x pH 20
HD2
S max
a.v22
notice that Ls 2 20D2 and use the induction hypothesis: a.69
HD2
20
aBv2k
This completes the induction.
Lemma C.1. Let and b be arbitrary points Rd. Then, we have
IP((a) P(b) J(b)(a b)ll pll - all
2
Proof. Let denote an arbitrary unit vector. We define the function s : R
R by s(A)
(v, P(ad + b(1- - A))). Then s'()) = J(ad b(1 - A))(a - b)). Therefore:
P(a) P(b) s(1) s(0) S' ((A) da
=0((0) + / (s s'00) di
(bv, - -b)) + ( (d(()) - 5(0)) dx.
P(a) P(b) (00((- b))1 1/' (J + b(1 - -)) -J(b)(aa b))1 da
< plla b112 ( Ad pla-bbl²
2
Since this holds for all we have that IIP(a)-P()) P(b) (b) b)]l = sup |+|== (w, P(a) P(b)
((b((a b))l S pllb=el?
Lemma C.2. Algorithm ensures:
(I ) - f(x.)= S max [[f((++1) 100-ff(az f(xx) - ,Ho 4pHo (1 1+
ag36x )
4D2
Proof. To simplify notation, let v, = x7 = t X' kh., T Tk, and 8 = Sz. We also define Jr J(zz) and 9r VC()) where y/ P(zz). Then have B[he] = J gt.
Notice that by assumption Di and D2. [(a S (xx) So, it suffices show that:
4D2
}
[[((T)] - (xxx max B[[(x)))- f(xx) pH0² 4pH62
(1+ a:38
Then, for all u E X' we have:
T
T
Σ ((xx) - f(u) Σ
16

---

Published as a conference paper at ICLR 2025
T
(C((P)))), - P(u))
(VC(P(2))) P(xt) - P(u) - Je( - -u) + Σ Ji( u)).
By Lemma C.1 and recalling
|C(P(=))] < // and || w/l S 20:
20TH0 JC( u))
2pTH6²
(J. (C)((P))) u)
t=1
T
2pT'08 +
Σ (h4, Te u} + Σ [BB]he] h4s 2t - u)-
Note that the points } are chosen via projected online gradient descent where the domain has radius 8. Hence the linearized regret is upper bounded by ΣT (he, It u) ÖHvT (see, e.g., Zinkevich 2003
T
= = + SH.T +
Σ
[1/1)] - 1e, 32. - 11)
1=1
E Σ (ax) ( [(u)
< 20TH SHVT 3pHoTT,
where the last equality uses
PVT. Next, notice that by definition,
T
B]((a)] = E T 1=1
(xx)
Therefore, we have that for all u E X::
- e(f(z)-
s 3pH8
Now, consider two cases.
Case 1: f(x)) - fu) 2 4pH for some u E X. Here, we have:
[[f(() - f(x:)) = Eif(z) f(u) + f(u) f(x1)) < 3 = -H
[[S(T) - [(x+)) - + B[f(z) [(x1)) S ([((x))] - [(xx) -pH62
Case 2: f(x1) f(u) < 4p for all X. Then since have || S D2, ||xx|| S D2, by
Lemma 5.2 we have:
4D₂
f(x))= f(x1) + f(x)) f(x.) s 4pH12
1+
a,3
Thus, in both cases, we have;
B[((z)] f(x.) S max B[f(x1)] f(x.) pH82 4pH62 (1
4D2
1 a,30
17


Reviews:
[{"review_id": "qLUhTDttf2", "reviewer": "Reviewer_SpNX", "summary": "This paper focuses on the case where the stochastic oracle produces feedback which is not necessarily unbiased. More precisely, it introduces the notion of misaligned stochastic gradients in order to capture the lack unbiasedness in several practical scenarios. To that end, the authors test their theoretical machinery for the optimization problems with hidden convexity (also studied in Sakos 2024 and references therein) and provide an algorithmic method which exhibit $\\mathcal{O}(\\varepsilon^{-3})$ iteration complexity.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is very well written and easy to follow. Moreover, the mathematical analysis is sound and clear as far I have checked. The idea of misaligned stochastic vectors is quite intuitive and as far as my knowledge goes it paves the way for dealing with a useful practical methodology for structured biased stochastic gradients.", "weaknesses": "Concerning this paper I have two main concerns/questions:\n\n1. The almost sure boundedness of the biased gradients seems to be a quite restrictive statistical assumption. As far as my knowledge this type of assumption is usually used in methods which are run with adagrad-type step-sizes (see for example Levy 2017). Thus, my question is two-fold: Does this statistical assumption hold in practice and secondly do the authors believe that it is an artefact of the analysis or the method in order to overcome it ?\n\n2. The paper lacks a numerical comparison with other methods which consider biased gradients like the Stich 2020 paper. My question concerns the fact that the compression scheme presented in the said paper seems to cover the case of an \"relative bias\" (an analogy to Polyak's relative noise) in the sense that the bias vanishes when we approach a solution. To that end, some simple calculations may show that under this condition the second assumption in oracle & assumptions may be recovered. So, I think that a more thorough discussion is needed.", "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": "", "extra_scores": {}}, {"review_id": "UFmUNo3Hhx", "reviewer": "Reviewer_hxRG", "summary": "The paper studies oracle-based optimization in three settings. First, when the oracle returns gradients that are misaligned with the true gradients in a specific manner: the expectation of the returned gradient is positively correlated with the true gradient (in terms of the inner product). Second, for more specific applications, they strengthen this assumption, and require that the lower bound not just be nonzero, but that it is at least the square of the true gradient. Third, for their setting of hidden convexity, they use the standard unbiased estimator assumption. \n\nThe paper provides improved rates of convergence under all three settings.", "questions": "1. Does the analysis in Section 3 have any connection with the analysis seen when using self-concordant barriers? The assumption that two matrices $A_t$ and $A_{t+1}$ do not change much is quite similar to saying that two successive Hessians do not (which is essentially what self-concordance captures). If the authors believe there could be a connection to this, it would be useful to add that to the paper and add pointers to the literature on interior-point methods, where this notion is used; if not, then it would still help to clarify why it differs. \n\n2. The assumption in Section 4 that the inner product of the true gradient and expected gradient (from the oracle) is lower bounded by the square of the true gradient norm is identical to that in Beznosikov et al (as the authors themselves note). Can the authors explain what exactly they do differently to improve the $\\epsilon^{-4}$ rate to $\\epsilon^{-3}$? Could they point to a specific step in their proof where they use this inner product assumption in a better manner?\n\n3. There was a recent paper https://arxiv.org/abs/2304.08596 by Shu, Ramachandran, and Wang, which also talks about hidden convexity. I think it would be useful to cite the paper if the way the phrase \"hidden convexity\" is used is the same. If not, it would be helpful to clarify the differences.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "I think it's a well-motivated paper with a coherent set of results. I like that the analysis in Section 3, though, simple, is complete and step-by-step. The authors are also quite honest about differences with prior work, though they could do a better job explaining why they do better than existing work in similar assumptions (see Questions).", "weaknesses": "My only complaint is that the paper's introduction suggests that the only assumption made is that the inner product of the true gradient with the expected gradient provided by the oracle is positive: however, this seems to hold only in Section 3. In Section 4, this is strengthened to say that the lower bound is the squared norm of the true gradient (an assumption same as Beznosikov et al), and in Section 5, it's further strengthened to be simply an unbiased estimator. Is my understanding accurate? If so, the \"misaligned\" description used throughout the introduction applies only to Section 3, and for the other results, there already exists standard terminology for those assumptions, so assigning them a new name wouldn't be the right thing to do. \n\nMy recommendation to the authors is to please clarify all the assumptions (for each of the different settings studied) in the introduction, so as to avoid any confusion. \n\nFurther, it would be useful to have a better understanding of what specific difference in the analyses in Section 4 lead to the improved rates as compared to existing work under this assumption (see Questions).", "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": "", "extra_scores": {}}, {"review_id": "9sI0YQzy9N", "reviewer": "Reviewer_7H59", "summary": "The paper studies stochastic convex optimization where the stochastic gradient oracle is biased but correlated with the true gradient. The proposed algorithms achieve the following performances: for Lipschitz, convex objectives and slowly varying bias, the rate is O(N^{-1/2}); for Lipschitz, smooth convex objectives and general correlated stochastic gradient oracle, the rate is O(N^{-1/3}). The results are applied to problems with hidden convexity, which achieves a rate O(N^{-1/3}).", "questions": "-- All the convergence results are presented in expectation. I’m wondering how hard it is to obtain ``with high probability’’ performance guarantee? \n\n-- In line 113, ``note that this is equivalent to the condition that …”, this seems to require that f is differentiable. Otherwise, the gradient of f may not exist, and instead the bound holds for all subgradients.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is overall well written, with clearly presented setups, algorithms, and performance. In addition, the correlated stochastic oracle studied, as pointed out on page 2, might have broad applications.", "weaknesses": "-- The paper is closely related to the stochastic optimization literature. Although the authors have cited many relevant works, the exact known results are missing in this paper. It might help the readers better appreciate the significance of the results by providing more details and/or comparisons with existing setups and known upper/lower bounds on the convergence rate.\n\n-- The assumptions of each theorem are stated at the beginning of each corresponding section (informally). It might be better to present them more formally, either as Asssumption 1/2/3, or stated directly in the theorems. \n\n-- In terms of significance, it is unclear how tight the bounds are. Would it be possible to derive some lower bounds from known results for other related problems? This would greatly help the readers appreciate the significance of the results. In addition, it seems that the analysis is relatively standard. Could the authors provide more comparisons with existing proofs for stochastic convex optimization, or related problems/setups?", "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": "", "extra_scores": {}}, {"review_id": "OoLyGV0Evo", "reviewer": "Reviewer_HMLj", "summary": "The paper considers the problem of first-order stochastic optimization where the learner can only access a stochastic gradient whose expectation is only guaranteed to be correlated with (but not equal to) the true gradient at the queried point.  The authors consider three different settings commonly encountered in machine learning problems where the learner can only access biased gradients. For each of the three settings, they propose a new algorithm and provide its analysis.", "questions": "1. Can the authors explain the intuition behind the update in line 6 in algorithm 2? It seems like you just want to consider the update in the orthogonal direction but I can't quite understand why? Is it simply to reduce the norm of the update (and not considering the update along $x\\_t$ helps) or is there something fundamental that is going on there?\n\n2. Does strong-convexity help for algorithm 2 and 3? In other words, if we are given the additional information of strong convexity, how much does that help improve the error? Particularly for alg 2, if it does not help then what exactly from the analysis in Demidovich et al, 2023 does not work out in this case?\n\n3. I am not sure if this will work, but might be worth a try: If I understand correctly, the term $f(x_t) - f(x^{\\star})$ in line 413 cancels out with the term $-\\frac{\\eta\\_t \\alpha \\| g\\_t \\| }{3}$ in line 416. I think with an appropriate change of constants, we can retain a fraction of the negative term in line 416 and carry forward it to the equation in line 421. Now, if $\\|g\\_t\\| \\leq \\frac{C}{\\sqrt{t}}$ for some $C > 0$, then we are at a point with small gradient. Otherwise, it will cancel out the $\\frac{1}{\\sqrt{B_t}}$ term in the equation in line 421 with $B_t = t + 1 + k$. This might help you achieve optimal error rate. Of course this needs to be checked but it might be helpful to address the sub-optimality gap.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I like the paper overall. It uses simple but interesting additions to existing strategies for optimization to design the algorithm with biased gradient estimates which often yield optimal performance. I think the results are sufficiently novel and interesting and improve upon the best known results so far.", "weaknesses": "I don't see any glaring weakness in the paper but I have some questions listed in the next section.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)