Stochastic Gradients under Nuisances
Authors: Facheng Yu
Ronak Mehta
Alex Luedtke
Zaid Harchaoui
Venue: NeurIPS 2025 poster ()
Keywords: Stochastic gradient
orthogonal statistical learning
nonparametric statistics
Primary area: optimization

Abstract: Stochastic gradient optimization is the dominant learning paradigm for a variety of scenarios, from classical supervised learning to modern self-supervised learning. We consider stochastic gradient algorithms for learning problems whose objectives rely on unknown nuisance parameters, and establish non-asymptotic convergence guarantees. Our results show that, while the presence of a nuisance can alter the optimum and upset the optimization trajectory, the classical stochastic gradient algorithm may still converge under appropriate conditions, such as Neyman orthogonality. Moreover, even when Neyman orthogonality is not satisfied, we also show that an algorithm variant with approximately orthogonalized updates (with an approximately orthogonalized gradient oracle) may achieve similar convergence rates. Examples from orthogonal statistical learning/double machine learning and causal inference are discussed.

Stochastic Gradients under Nuisances
Facheng Yu"
Ronak Mehta
Alex Luedtke
Zaid Harchaoui
University of Washington
Abstract
Stochastic gradient optimization is the dominant learning paradigm for a variety scenarios, from classical supervised learning modern self-supervised learning. We consider stochastic gradient algorithms for learning problems whose objec- tives rely unknown nuisance parameters, and establish non-asymptotic con- vergence guarantees. Our results show that, while the presence of nuisance can alter the optimum and upset the optimization trajectory, the classical stochas- tic gradient algorithm may still converge under appropriate conditions, such as Neyman orthogonality. Moreover, even when Neyman orthogonality is not isfied, we show that an algorithm variant with approximately orthogonalized up- dates (with an approximately orthogonalized gradient oracle) may achieve similar convergence rates. Examples from orthogonal statistical learning/double machine learning and causal inference are discussed.
Introduction
Machine learning, statistics, and causal inference rely on risk minimization problems of the form
min PEB
[o(0) := Ez-z [o:; Z)]].
(1)
where C Rdd a parameter space, Z is Z-valued random variable, and & θ 2 + is loss function. The quantity (o; describes the performance of model parametrized by 0 E θ on a test example 2 E Z. Given only an oracle that provides a stochastic gradient estimate of the objective (1), practitioners able to train models ranging from linear functions tabular data to billion-paramne parameter neural networks on vision and language data.
The success of stochastic gradient descent (SGD) algorithms [Amari, 1993, Bottou and Le Cun, 2005, Bottou and Bousquet, 2007, Ward al., 2020] has motivated an abundance of work on their theoretical properties under various algorithmic and risk conditions, such as class separabil- ity [Soudry et al., 2018), random reshuffling (Gürbüzbalaban al., 2021], decomposable objectives [Schmidt et al., 2017, Vaswani et al., 2019], quantization noise [Gorbunov et al., 2020], and noise dominance [Sclocchi and Wyart, 2024]. This success been fueled by machine learning and Al software libraries such as JAX, PyTorch, TensorFlow, and others, which offer wide range of SGD variants, as long as a loss function can be clearly specified. The gradient is then evaluated automatically mini-batch of datapoints and used for stochastic updates.
Though powerful, this recipe takes one thing for granted: that the learner can always compute the risk (or an unbiased estimate thereof). Indeed, many complex learning problems rely on risk function that only partially specified up to a class
== (T( ; : E
where G is a possibly parameter 0 E θ and an unknown nuisance parameter g E G.
set and L 0 0 G + RR is function of both the target
email: fachengy@u..ccm edu.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

This framework originates from semiparametric estimation and inference [Levit, 1979, Linnik, 2008, Bickel et al.. 1993, Van der Vaart, 2000], where the risk a Kullback- g provides information about the true data-generating distribution IP, but is not of primary scientific interest. However, the partially specified loss formulation from (2) is not limited to semiparametric estimation and inference problems. This framework connects to many areas of interest, including profile likelihood based learning [Murphy and and, 2000, Pavlichin et al., 2019, Hao and Orlitsky, 2019] and distributionally robust learning [Shapiro, 2017, Levy et al., 2020, Mehta et al., 2024].
(KL) divergence and
For instance, profile likelihood based learning reduces (2) by applying a pointwise minimum over g E G to then construct problem that can be solved in 0 E e. Another example arises in applica- tions with distribution shifts, for which represents an unknown test data distribution that may differ from the one from which the training data were drawn. Distributionally robust learning reduces (2) by instead taking a pointwise maximum over 9 and solving the resulting problem. Although the pointwise minimum and maximum are natural reductions, it is often the case that there is a "true" Do E 9 and the loss class is reduced by first estimating Do with auxiliary data to produce some ğ. which we refer to as double/debiased machine learning, or DML, following Chemozhukov et al. [2018a]. The problem (1) is then thought to be derived via Lo = L(0, go) in this case (see examples in Sec. 2). This is the focus of this paper.
Despite the prominence of SGD and DML individually, the convergence guarantees of SGD to re- cover the risk minimizer with misspecified nuisance parameter remain unknown. Indeed, after producing 9. the user typically solves (full batch) empirical risk minimization problem, i.c. mini- mizing a sample average approximation of L(,,9). In this paper, we aim to fill this gap by proving convergence guarantees on the sequence (0(*)) )n21 generated by updates of the form
g(n) g(n-1) 1)S(((n-1), .g: Zn),
where 17 > is learning rate, D,, (Z,) is stream of independent data drawn from P, 9 is nuisance parameter estimate, and S θ x 9 x Z E is stochastic gradient oracle satisfying of Ez=z[S(0, g; 2)] = VoL(O,g) g) for all (0, g) E θ x G. In particular, when G lies within a Banach space equipped with norm Il.l|g. we wish to compare ((n) to
0. arg min L(,.go). deB
(4)
given conditions on the degree of misspecification ||@ - golle and (approximate) Neyman orthogo- nality of the risk L [Neyman, 1959].
Intuitively, Neyman orthogonal classes of objectives are instances of (2) whose curvature with re- spect to B is insensitive to the choice of (see Sec. 2 for the formal description). When Neyman orthogonality is satisfied, the double machine learning framework is also known as orthogonal sta- ristical learning (OSL) [Zadik et al., 2018, Liu et al., 2022, Foster and Syrgkanis, 2023]. In addition to the obvious computational considerations, we argue that the SGD perspective in this paper also sheds light on the methodological opportunities in DML/OSL. Indeed, while loss functions are typ- ically specified by the chosen architecture, Neyman orthogonality is often achieved by specialized analytic calculations
the part of the user. Although this property is generally seen second- order property of the loss, it can also be viewed as a first-order property of the gradient oracle S. As we detail in Sec. 3, it may be casier and more aligned with the spirit of modern machine learning, to craft Neyman orthogonal gradient oracles instead of losses.
Contributions. We prove the first theoretical convergence guarantees for SGD under an unknown nuisance model. We find that ((n) converges linearly to a neighborhood of the optimum in the well-specified wase-with a radius that has fourth-power (resp. squared) dependence on -ools when Neyman orthogonality is (resp. is not) satisfied. Our analysis can also apply to two-stream settings in which the nuisance parameter is learned online alongside the target. We further analyze a new algorithm, called orthogonalized SGD (OSGD), wherein the gradient oracle of a possibly non-orthogonal loss can be iteratively made orthogonal using an "approximately orthogonalized" gradient oracle, which is based on separate estimation procedure. This algorithm enjoys a con- vergence guarantee that interpolates between the |ا - goll' (nuisance insensitive) and ||ğ - goll (nuisance sensitive) regimes depending on the quality of the orthogonalizing operator.
2

---

We provide an introduction to the OSL/DML setting in Sec. 2. The SGD and OSGD algorithms are described and analyzed in Sec. 3. We discuss related work in Sec. additional discussion can be found in Appx. F. All proofs and numerical illustrations can be found in the Appendix.
2 Orthogonal Statistical Learning
We first introduce various examples of risk functions in the form of (2), then formally introduce Neyman orthogonality and its implications. As is common in learning settings, the risk will be in the form of expectation,
L( g) Ez-e [e(0, g: Z)],
where e θ x x R is an instance-level loss function. Various assumptions used in the analysis in Sec. 3 (e.g. convexity) may be placed on either the loss or the risk L. In each example, we provide the structure of the data point Z, the set G, and the loss L, and the true Jo E 9 to fully specify the problem. Here, we interpret "true" to mean that Do a parameter of the tett-generating distribution (e.g. a propensity score in causal inference). or that 9n satisfies cost-min minimiziig or criterion (as in the profile likelihood distributional robustness examples from
Sec. 1).
Example
g(0.g:=)
PLM
fiv (w) (x()))
( W] Er [X W])
CATE
(x))))) - (xr) + (e te tatt x)))
(Re 1. XX 0, B3 X))
CRR
[ng (o (x) log(1 (o()
( Y W 1, XX 0, R X])
Table 1 Examples of Neyman Orthogonal Losses.
Example 1 (Partially Linear Model), Let Z (X P. where X is -d-valued input, is a real-valued outcome, and W a W-valued control or confounder. The space G is nonparametric class containing functions of the form
g (gy, 9x) W IR Rd.
Following the construction of Robinson [1988], this is supplied to the loss
(0 g:
2 gr (w) - (0, x - 9x(w)))?
To ensure 0, can be interpreted via the projection of EF Y X, W] onto partially linear addi- tive functions, the true nuisance is given by go (go.x, Jo.y where
( = E, Y W w] and gu.x (w) Ep X W w)
The next example concerns a quantity widely studied in causal inference [Kennedy, 2023].
Example 2 (Conditional Average Treatment Effect). We observe = (X,Y,W) ~ P. where W is binary treatment assignment. The functions in are the form
g = (g (0)
prup) Rd +
x (0, 1),
and evaluated (see der Laan and Luedtke [2014, Thm. 1]) the loss
1
w - poop (x)
fCATE(0, (0)
2 g (x) - (x) +
(x) grop (x:) (y gim) - (0, (0))
For go
(g) (0) (1)
90 go p) nuisance functions (0) and /o represent the outcome regressions
96 (0) (x: [Y W 1, X = 2r| and n0 (अ) lY W 0, X 2x).
3

---

Ep [W]] X -| denotes the propensity score. The minimizer 0, in- dexes projection of the conditional average treatment effect g¹ 9o onto linear functions.
whereas goth (z)
Finally, we maintain the data structure from the previous example, but consider a loss corresponding to different target parameter according to van der Laan et al. [2024].
Example 3 (Conditional Relative Risk). We retain all components of the previous exam- ple, changing only the loss and assuming that the outcome Y is binary/non-negative. First, consider the "label" function
1 1 =) ( (z) (x) (x) (1 s) (x)) (y (1)))
where I (.) denotes the indicator function, and the logit-linear predictor po(#) el0.2) /(1 +1+ (( ). To obtain a linear approximation of the log-relative risk log(g)) (1) /90"), we employ the cross entropy-type loss function
ECRR (0, (0 - [u[² (z) (o()) + (=) log(1 po(x)))
While the choices of the loss function in Examples and might look opaque to readers outside of causal inference and statistics, they are carefully designed to be Neyman orthogonal. To motivate its definition, notice that, invariably, 9o is unknown to the user. In DML., the user may produce or access some 9 G. which an estimate of go based on independent training data other than the stream (Z,) used to produce g(m), It is of clear interest how stochastic optimization algorithms (and their resulting minimizers) behave in light of the misspecification of gu. and what precise theoretical conditions govern this behavior. Morcover, be used to analyze procedures for which the user may access additional data to progressively improve the estimate and learn 0, simultaneously. We now formally introduce Neyman orthogonality, and by extension, the orthogonal statistical learning (OSL) variant of DML.
demonstrate in Sec. 3, these same conditions can
Neyman Orthogonality. For a definition that accounts for a possibly infiniteddimensional function class G, we introduce the directional derivative, equivalently, the derivative operator.
Definition (Derivative Operator). For a functional F mapping from vector space F I, we define the (directional) derivative operator 1) as [F) == 4F th) 1t=0 for any h E F. For a vector-valued generalized by taking derivatives coordinate-wise. We define the second-order derivative as DFF(() ht] := ((DE())) for h, h' E F and higher-order derivatives simi- the subscript notation
FF > TRd. this derivative operator can be
larly. For functionals of multiple variables F F x G + R. DfF(f.)(( to indicate the directional derivative of - F(f.g) with g E G fixed.
We denote by So Vol(O, g; 2) the gradient of the loss function w.r.t. the target parameter
E O. Borrowing terminology from statistics, we call this the score, whether i based on a likeli- hood or not.² This constitutes one particular example of a stochastic gradient oracle S used in (3). Overloading notation, the population gradient oracle defined as So g) = Ez-p Vol gi Z)
Definition 2 (Neyman Orthogonality). The population gradient oracle Sa is Neyman orthog-
onal at (0: over G' C if
(00,, go)l9 go] 0 for all g g'.
(5)
For O' C O, the population loss L is Neyman orthogonal at (f., go) over O' x g' (0..L((..go)1 0., - gol = 0 for all (0,g) E e' x g'.
2This notion of (Fisher) score differs from the "score" used in score-based generative modeling [Song et al., 2021]. If f is based likelihodood then So is the gradient w.e.t. the parameter 0 θ not the input 2 Z.

---

Non-OOthogonal Risk
Orthogonalized Risk
Cross Sections for Fixed g
L(O,
92
L(0,g0)
90
L(0,91)
91
Minimizers are inscnsitive to the muisance value.
02 0x 01
02 0x 01
Figure 1: Illustration of Neyman Orthogonalization. The first two panels are contour plots of the risk function L(O,g) g). where 0 varies on the r-axis and g varies on the y-axis. For the orthogonalized risk (center) the contours are approximately axis-aligned. The right plot shows the cross sections of the non-orthogonal risk when fixing g = go, 91 9 Due to non-orthogonality, the minimizers 0 and 02 shown in the first and third plots may drift significantly from 0,. In contrast, the minimizers the center plot are less sensitive the choice of g.
In Definition 2, we allow O' g' C 9 to be a proper subset, which not only provides weaker condition, but also accounts for localization-stlle arguments. Moreover, since DoL(O., (o) (00[000)))))) (Sa (0., 9o), 0.), if the population risk L satisfies (5), then (6) holds for any target parameter class O' S Rd. As mentioned above, the risk functions in Examples 1-3 are all Neyman orthogonal at their respective value of 90). In the next section, we will discuss a procedure to make non-orthogonal gradient oracle "approximately" orthogonal. We illustrate the intended outcome intuitively in Fig. by comparing generic loss and its orthogonalized counterpart.
3 Stochastic Gradient Optimization
In this section, we propose two stochastic gradient algorithms, which rely on different choices of the stochastic gradient oracle used (3). The first the familiar stochastic gradient oracle that provides sample estimate of the gradient V ( 9) for fixed estimate ÿ. The second employs approximately orthogonalized gradient oracle, or OSGD oracle, to achieve notion of approximate Neyman orthogonality (in manner make precise in this section). We analyze the first algorithm under both non-orthogonal and orthogonal settings, achieving an illustrative breakdown of "nuiisance sensitive" and "nuisance insensitive" regimes regarding the theoretical convergence guarantee. For the OSGD algorithm, we prove a convergence guarantee that interpolates between the two regimes, depending the accuracy of the oracle.
Notation and Assumptions. For readers' convenience, a table of all the notation we introduce throughout the paper is collected Appx. A. maintain the prototypical bias/variance conditions on the stochastic gradient oracle S, that is, an unbiasedness condition and acond-moment growth condition (see Asm. 3()). To dispel confusion, note that by "unbiased", we mean specifically that Ez-z (6, g: Z]] V [.,, g) for all (0, g). opposed to the "bias" of replacing á with Io- terminology sometimes used DML/OSL. Our analysis will rely partly on the initial distance r of the nuisance estimate go in G. which defines the ball
Gr (go) = {g E g ||g - gollg <r)
Various assumptions on the risk will be required to hold only locally, that is, within G, (go) as op- posed to the entire linear space G. Thus, the assumptions become weaker the estimate ý improves.
Assumption 3. The following conditions hold:
(a) Differentiability: For any (z,g) E 9. + ((0ggz) twice continuously dif-
ferentiable. For any (0.g). E θ G. (i) D'DeE(0, T. z] 0,,g
gol exists and is continuous, (ū) DoL(0,0)0 0.) and D L g)gg - gol exist,

---

and (iii) E& Doe 9: 2) 0.]] = DeL(0,9)1 - 0.). Ee [D g: Z)(9 9ul] (AL(0,g)le go].
(b) First-order optimality: The pair (0., go) satisfies Sg 90) 0.
(c) Smoothness and strong convexity: There exist constants M 2 μ 0 such that for all
E Gr (go), the population risk L(; g) is M-smooth and p-strongly convex for E O.
(d) Second-moment growth: There exist constants K1, K1 2 0 such that
Ez-plI|So(AA. Z) 5o(0.9)15 & K1 + K1 ||@ 0.112
40 E E E gr (go).
(e) Second-order smoothness: There exists a constant
01 2 0 such that
[D, (0.. 3) [ 0..g goll - a 1|e 12112 l1g gاllو 40 E G, E
g, (9o).
Asm. 3 does not require Neyman orthogonality at go). Instead, Asm. 3(a) is a standard differ- entiability condition. Asm. 3(b) and (c) implies that 6. is unique global minimizer. Asm. 3(d) generalizes the uniformly bounded second moment condition in stochastic optimization (e.g. Cutler al. (2023]) by adding a quadratic form in which allows us to consider an unbounded feasible set @ and more loss classes. Finally, Asm. 3(d) and (e) can be satisfied when the Hessian of the population risk a bounded operator. Usually, K1, K1, and an would depend on the initial nui- sance estimation distance We provide in Appx. B estimates of the constants in Asm. 3 for each motivating example. We proceed to the main results regarding the convergence of SGD and OSGD.
Stochastic Gradient Algorithm. Here, we use the standard single-sample stochastic gradient esti- mate S = Sn in (3), This leads to the update
g(m) = ((=-1) () ( ,9; Zn,, e E O.
(8)
While the SGD procedure can be easily extended to using batch of unbiased gradient estimates, we keep our single-observation construction to highlight the most important aspects the analysis. In order to achieve quantitative guarantees in the Neyman orthogonal setting, which essentially removes certain second-order terms that include 0 and g. we will consider the following higher- order condition in some cases.
Assumption 4 (Higher-Order Smoothness). The risk L satisfies Definition 2 at (0.,90), and there exists some constant 31 > 0 such that
DDL (0., Ø) 10 0.,g g gull < 31 110 - 02112 1 v E G,g.g 9 E (90)
When satisfied, Asm. 4 results in the nuisance insensitivity alluded to at the beginning of this section. Notice that Neyman orthogonality is not necessary to construct stochastic optimizer, and it is still possible to obtain a nuisance sensitive rate under only Asm. We demonstrate this in Thm. 1.
Theorem Define Dn (Zi,...; Za), sampled from the product measure P Suppose that Asm. holds, ğ E Gr (go) is estimated independently of D',, and g()) ......))) E almost surely. The iterates of (8) satisfy:
1. Nuisance sensitive: If S 44/2(M + k1), then
ED,,<P= (110(m) 0.133 < (1- 11000) 0-113 1.
20
l 2ull + 4K17 112
2. Nuisance insensitive: If Asm. 4 also holds, then, for 1j 2 H/2(MM + K2).
ED.~Pa [1]0()) 0.13. <
1 2
(1000)
0.12 +
82
ll@ - go + 4K17
2n
Note that the assumption that the iterates remain in θ is satisfied in common cases. It is satisfied trivially for the first two examples in Sec. 2 because θ = RRd Another case when the loss decomposes into the sum of G-Lipschitz continuous component and the &3 no-m regularizer, i.c.

---

1(0.9: 2) 2) + 11112- Then, the iterates and the optimum remain in {0 |0]12 S G/u} (see, e.g., Mehta et al. [2023, Appx. CD). so Definition 2 can be restricted this compact set.
Thm. states that SGD converges linearly to a ball around 0. with a radius that depends on the bias (due to the replacement of 90 with 9) and the variance due to gradient noise. Moreover, the variance component decays proportionally to the learning rate Under Asm. 4, the bias component can have a significantly more favorable scaling with the error in the nuisance estimate - 1ol-oollo- specifically, ll - golli gollğ instead of |ا gollă. A similar breakdown into two regimes of the bias scaling occurs in the works of both Foster and Syrgkanis [2023] and Liu al. [2022] under Asm. (called "slow rate" and "fast rate" there). Importantly, their bounds are based on an exact, offline empirical risk minimization procedure for fixed training set, i.e. they provide excess risk bounds on the quantity L(On,, 9o) I(f.,, 9o). where
0, arg min 0g
Σ ((0,9:
In contrast, Thm. I accounts for both the expected distance to optimum and the interplay between bias incurred by 9 and the progress achieved at each step. In particular, even when using a constant learning rate, the bias does not accrue on each iterate and is in fact constant in n. When 6n is designed to be doubly robust, using SGD can achieve double robustness; see Appx. F.5 for an example.
Orthogonalized Stochastic Gradient Algorithm. Given the marked improvement in the rate of decay of the bias term when an orthogonal loss is used, is clearly beneficial to do so when possible. We now describe how we can induce orthogonality by adjusting the stochastic gradient oracle using the solution of an auxiliary problem.
The construction of Neyman orthogonal losses has historically been motivated in semiparametric theory and statistical learning as means to build efficient minimum asymptotic variance fuul batch statistical estimators [TTsiatis, 2006, Van der Vaart, 2000, Foster and Syrgkanis, 2023, Cher- nozhukov et al., 2018b]. The approach nozhukov et al. [201 8a, Section 2.2]: see also Luedtke [2024]. We also give an intuitive explanation based on least-squares estimation, instead of the usual differential/information geometry one.
follow is inspired by the construction reviewed in Cher-
While our construction holds in general spaces, let us first consider the illustrative case when G = R* At the true parameters (0+, go). consider the problem of finding the best predictor of the Rd. valued target variable (0,,., go: Z) = V vel(O.. go; Z) given the RR* -aluul predictor V ,00 90: 2) variable in the space L(G, +) containing all continuous and linear operators from G to O
ro = arg min Er [1]oo(f,,00) 9o: Z) - TV,((0... 9o: 2) reL(g,))
(9)
In the special case where (00gg:2) 2) log (2) for density po.g on Z that governs the random variable Z, the projection direction solving (9) can be shown to satisfy To H H-1 Hag V,,Sp(0.,90) E kexd is the transposed Jacobian and Hgg = (OL(,.,90) E I Rgkk is the Hessian. The prediction Vo ,(E (0x,.09; 9o; Z) accounts for the covariance between Vol(O., 9o; Z) (the gradient w.t. 8) and V ((0. go: Z) (the gradient w.r.t. g). It stands reason that as 0 0., the random vector
gg where
e(. go: 2) = So 90: Z) S(0, go: 2) == So gu: 2) - V.
Ho ((, 9o: 2) (10)
would be less sensitive to perturbations of go. as the component of Se 9o: Z) that is predictable through changes 9o is subtracted out. Furthermore, if we are aware that the expectation of S is made zero at 0_, then a stochastic gradient scheme based on (10) could conceivably achieve a nuisance insensitive rate guarantee in lieu of Thm. From a variance reduction viewpoint, the correction term in (10) subtracts the regression of the 0 gradient of the loss on the "gradient" of the loss. By the law of total variance, the variance the gradient reduces and improves the trajectory of stochastic optimization; see Appx. F.4 for more details. This variational description (10) hints at how such an operator can be computed algorithmically. instead of the historical approach of deriving the operator via calculation by hand on case by case basis.
7

---

Supported by this illustration, we define a generalization that will provide a modified stochastic gra- dient oracle use for optimization purposes. Without assuming that é negative log- lig-likelhoodd we generalize the formulas for V y g; =) E R., Hag E R and Hgs E T & for when = (9, ( :)g) is an infnite-dimeesionall Hilbert space. Under regularity conditions on the direc- tional derivatives of L, we have that v,L(o, g;;) E G for all E 2, Hag = (H
Hōg) E g", and Hgg و + G is bounded and self-adjoint operator. The formal details of their construction are contained in Appx. D. Just as in (10), we may consider the operator To G - R defined element- wise by [Tgl;
9) gi where the invertibility of Hyg is satisfied by assumptions preceding Thm. 3. As shown (9), the orthogonalizing To defined by both the true nuisance Do and the target 0.. where go can usually be learned as some conditional expectation and 0. can be learned by our proposed methods. We then construct the central object of the upcoming Thm. 3: the Neyman orthogonalized (NO) gradient oracle
gg og
Sn (0,0,,;
So(0, To g0,
(11)
Lemma 2. Suppose that Asm. 3(a) holds and (2,L 9- G G + R is bounded and symmetric bilinear form. Then the NO gradient oracle (0, y: is Neyman orthogonal at (9o.9o).
We refer readers to Lem. 15 for the proof. In this context, we refer to the operator To as the "or- thogonalizing operator". As a natural sanity check, we note that for risk function that is already Neyman orthogonal at (0), the NO score Spo is exactly equal to score function Sa itself since Io O. To construct Sa for the non-orthogonal loss, we provide the following example in partially linear model where the corresponding derivations of To and Sn are included in Appx. B.1.2.
Example 4 (Partially Linear Model). In addition to Example 1, suppose that Z (X, Y, W) P satisfies
Y -0,, X} + (W) t
where 0, E Rdd is the true parameter, go : W + is the true nuisance function, and Eg [c X, W] 0. The space (IP) with inner product (01,92c, Eplgi (W))=WW)
for any 91, I2 E G is a nonparametric class containing functions of the form
g
R.
Consider the following non-orthogonal squared loss function:
1
(0, g) =) = - g(w) - (0, .x)
The orthogonalizing operator for this non-orthogonal loss is
To g + [E|[E]X]] W]g(W)),
and the NO gradient oracle is obtained as
(0 2) - g(w) 20x2))(z Ex[X W = =w].
Motivated by the advantage a Neyman orthogonal score, we now construct our OSGD algorithm using an estimated the NO score Sno. While To (like gn) is unknown to the user in general, using an arbitrary estimate I', we can define the estimated NO score Sno oracle via
Sn (0,0 2) (0, g: iv ((0,g)))))
(12)
Usually, can obtain such an estimate I using the same data stream of 9: discuss possible strategies in Appx. F.3. Finally, using S.o the stochastic gradient oracle S in (3), derive the OSGD update
g(n) 1(n S (0( (8(n 11) .g: Zn), ( e.
(13)
8

---

To measure the quality of I in our analysis, we use the Frobenius norm || = - where P 9 + R2, p g + [Ty]s and lop denotes the usual operator norm for linear function- als. As an example, by the uniqueness of Riesz representations, ||Tollãro Σラ= H 9g 1
Using this modified oracle (12) requires similar assumptions to those used in Thm. 1. For ease of presentation, defer the formal assumption statement to Appx. E, but note that the result depends on the constants (Pao: Mao: 02 32, K2), which are exactly analogous to (n, M, 01 31, K1) from Asm. 3.
Theorem 3. Consider the setting of Thm. 1, with the addition of Asm. 6. When | TollEro Huo/ (4x)) and
Mno 4a 1| Toll Fro
"
12M 3/t/0/ 1 + (Kr + N2 I
the iterates of (13) satisfy:
ED, ~P [1(0(n]
0111 < (1 Mmn'l) " 110(0)
0011
4(K1 + K2|lT||Peo
Mmo
3
+ p
(811 g
90ll + 40 وا
90 lg
-.IIII - To Toll
(14)
Compared with Thm. 1, Thm. 3 shows that OSGD outperform the nuisance sensitive rate through
the correction term || g | To ll and can align with the nuisance insensitive rate when || - RollRvo is of the order O - gollg). With slightly different assumptions, Thm. can further simplified Appx. E for details.
Interleaving Target and Nuisance Estimation. The results seen thus far have considered for sim- plicity the estimate be fixed element of G, and included terms that depend on the discrepancy llø gollg- Part of the convenience of these results is that if g((m) is the result of learning procedure with m independent data points, then statistical bounds on [m)(m) gu llg (either in expec- tation or high probability, depending on the situation) can be plugged in to quantify the bias. While the results naturally account for full batch learning procedures, they also amenable to analyzing staggered procedures in which two data sources are queried to estimate 0g and go, respectively. To knowledge, this is the first theoretical analysis of such orthogonal stochastic learning method.
To be precise, suppose that we update the nuisance estimator for m times, leading to the sequence g(1), g(.,,.... .................... (g(m) on stream of W-valued data Wi...., Wm. sampled i.i.d. from a probability mea- sure Q We define (10,n) ((0) E O, and for the update of g(0 for 1 < i < m, define g(a.0) 1(i- and produce the sequence
gli.n) using steps of the SGD update (8) initialized at (ft.0), Consider, for example, the case in which G is reproducing kernel Hilbert space (RKHS) with kernel k(.,). With the assumption that the eigenvalues (Az)ı21 of covariance opera- tor Eg (AW,,) & k(W, -]] decay polynomially at order j-a the nonparametric stochastic gradient algorithm of Dieuleveut and Bach [2016] satisfies Eq [[]](m) 20l O(m ((2a (2a-11/(20)) This leads to the following nuisance sensitive rate for a non-Neyman orthogonal loss, by Prop. 22:
g(.11)
((1 Em []]@(m..)) - 0- 1 = O (11 pm/2) + m + n + 7)
20-1
As another example, suppose that, in addition, we can estimate f (im using the nonparamet- ric stochastic gradient algorithm of Dieuleveut and Bach [2016] and using the same data stream
(W,..., W..) If there are high probability bounds for (] goll and []f(m) - To Toll of
the same order as (201122)))) and []@(m.n) 1 decays described in Thm. 3, then have in Prop. 23 that []@(m..) 0.113 Op ((1-fm) /m/2) 2) mm + -2a-
n 17) where the Om (2a nuisance bias term decays quadratically faster than the one for non-Neyman orthogonal loss. We refer the reader to Appx. F.3 for further details of this analysis.

---

4 Related Work
We summarize in this section our discussion of the related work. Additional discussions, as well as calculations supporting them, can be found in Appx. F. Possible extensions to SGD variants such as SGD with momentum, averaged SGD, and Adam, are explored in Appx. H.
From an optimization perspective, it is helpful to know how our convergence bounds perform in the idealized case of a known nuisance, which is equivalent (I). In this case, Thm. gives the convergence rate ED [[]((m) 0. O(11 wn/2)" "m + 17), which aligns with the non- asymptotic SGD convergence rates, in mean-square error [Bach and Moulines, 2011] and in high- probability [Cutler et al., 2023]. Our result requires a smaller learning rate 1i < (M/2(Mp: + 2x1) when compared to the requirement to our bounded moment assumption (see Asm. 3(d)), which contrasts with uniform boundedness assumption over all θ x Gr (90). In addition, when the uniform moment bound holds true, becomes zero, and our learning rate requirement becomes 1/ 1/(2M..
< 1/(2M) from Cutler et al. [2023]. This is entirely due
The comparison with unbiased SGD, and biased SGD, respectively, also valuable. In the biased SGD literature, the "bias" refers to the fact that Σz-æ [S(0, 9: Z)] VoL go) in general. The convergence radius then depends on the average value of |Ez= [((("), 9; 2) VoL(O()) go) Results along this line result in a radius that may not scale with vj; see Demidovich et al. [2023, Thm. 3]. Although this form of bias may be related to و|ا gulle under Lipschitzness conditions the oracle, it unclear how to effectively incorporate Neyman orthogonality into these general-purpose purpose approaches. Our approach naturally leverages Neyman orthogonality whenever it holds.
In the general case of an unknown nuisance, Foster and Syrgkanis [2023], Chernozhukov et al. [2018b] consider full batch learning methods based on analytically crafted Neyman orthogonal risk functions various scenarios. For regression functionals, the procedure from Chernozhukov et al. [2022] using random forests neural networks can ensure that the bias term |ا go ll is asymp- totically negligible for large samples, in the sense that classical statistical confidence sets for 0. are asymptotically valid. These papers are focused on algorithm-independdee statistical properties.
Our work fills this gap. by providing non-asymptotic convergence guarantees for stochastic gradient algorithms under unknown nuisances. Moreover, the modified stochastic gradient oracle moreover offers flexible solution deal with general risk functions. deriving an orthogonalized risk by hand is difficult or impossible, then the strategy we propose can be applied, and Thm. 3 demonstrates that, when the learning rate 1) set appropriately, the convergence rate using the modified stochastic gradient oracle can be improved to
(
Moo?? 2
90 3lll + 11 g -|- - Tollfro +7).
11 +
improvement over || 90 18
When we have the true orthogonalizing To, the improved rate recovers the nuisance insensitive one from Thm. 1. Besides, when å converges but || Toll = (1), the improved rate resembles the nuisance sensitive rate of Thm. 1, plus O(1)) bias term. Thus, the quality of the estimated orthogonalizing operator governs how the optimization interpolates between these two rates.
Having understood the performance of SGD when using an estimated orthogonalizing operator, one question is how to compute or approximate such an operator. Luedtke [2024] recently demonstrated that orthogonalizing operator can be derived using algorithmic/revese mode functional differen- tiation in many interesting cases. This can also be effective in our stochastic setting. In Sec. 3, using least-squares
Sersss regression an illustration, we developed control variate [Johnstone and Velleman, 1985] interpretation of the variance reduction. This viewpoint offers another venue to develop ap- proximate orthogonalizing operators.
Conclusion. We established non-asymptotic convergence guarantees for SGD algorithms under nuisances. We showed how the Neyman orthogonality of the loss function can mitigate the sensi- tivity of SGD algorithms to the effect of nuisances, and obtained results that align with recent ones from the DML/OSL literature in the batch setting. We also presented an iteratively orthogonalized SGD algorithm. whose convergence rate aligns with the rate in the nuisance insensitive regime. Extensions hypothesis testing and reinforcement learning are interesting venues for future work.
10

---

Acknowledgments. The authors would like to thank L. Liu, V. Roulet, and J. Wellner for valu- able comments and suggestions. This work was supported by NSF DMS-2023166, DMS-2134012, DMS-2210216, DMS-2502281, CCF-2019844, NIH, and IARPA 2022-22072200003. Part of this work was performed while R. Mehta and Z. Harchaoui were visiting the Simons Institute for the Theory of Computing, and A. Luedtke was visiting the Institute of Statistical Mathematics, and with the University of Washington.
Broader Impact. This work lies at the intersection of machine learning, mathematical optimiza- tion, learning theory, and mathematical statistics. While there are many applications stochastic gradient optimization for practitioners, this particular work is of theoretical nature and does not have any immediate positive or negative societal impact.
References
Amari. Backpropagation and Stochastic Gradient Descent Method. Neurocomputing, 1993.
F. Bach and E. Moulines. Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning. In NeurIPS, 2011.
Bickel, C. A. Klaassen, J. Bickel, Ritov, J. Klaassen, A. Wellner, and Ritov. Efficient and Adaptive Estimation for Semiparumetric Models. Johns Hopkins University Press Baltimore, 1993.
M. Bonvini and E. H. Kennedy. Fast Convergence Rates for Dose-Response Estimation, 2022.
L. Bottou and O. Bousquet. The Tradeoffs of Large Scale Learning. In NeurlPS, 2007.
L. Bottou and Y. Le Cun. On-Line Learning for Very Large Data Sets. Applied Stochastic Models in Business and Industry, 2005.
S. P. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
M. Carone, A. R. Luedtke, and M. J. van Der Laan. Toward Computerized Efficient Estimation in Infinite-iimessional Models. Journal of the American Statistical Association, 2019.
V. Chernozhukov, D. Chetverikov, M. Demirer, E. Duflo, C. Hansen, W. Newey, and J. Robins. Double/Debiased Machine Learning for Treatment and Structural Parameters. The Econometrics Journal, 2018a.
V. Chernozhukov, D. N. Nekipelov, V. Semenova, and V. Syrgkanis. Plug-In Regularized Estima- tion of Hiigh-Dimensionll Parameters Nonlinear Semiparametric Models. Technical report, Cemmap Working Paper, 2018b.
V. Chernozhukov, W. K. Newey, and R. Singh. Automatic Debiased Machine Learning of Causal and Structural Effects. Econometrica, 2022.
V. Cheroozuukov, W. K. Newey, V. Quintas-Martinez, and V. Syrgkamis. Automatic Debiased Ma- chine Learning via Riesz. Regression, 2024.
J. Clore, K. Cios, J. DeShazo, and B. Strack. Diabetes 130-US Hospitals for Years 1999-2008. UCI Machine Learning Repository, 2014.
Cutler, D. Drusvyatskiy, and Z. Harchaoui. Stochastic Optimization under Distributional Drift. Journal of Machine Learning Research, 2023.
A. Défossez and F. Bach. Averaged Seaas--MannSaoan Squares: Bias- Variance Trade-Off's and Optimal Sampling Distributions. In AISTATS, 2015.
A. Défossez, L. Bottou, F. Bach, and N. Usunier. A Simple Convergence Proof of Adam and Adagrad. Simple Convergence Proof of Adam and Adagrad, 2022.
Y. Demidovich, G. Malinovsky, Sokolov, and Richtárik. A Guide Through the Zoo of Biased SGD. In NeurlPS, 2023.

---

A. Dieuleveut and F. Bach. Nonparametrie Stochastic Approximation with Large Step-Sizes. The Annals of Statistics, 2016.
S. Ferguson. Mathematical Statistics; Decision Theoretic Approach. Academic press, 2014.
D. J. Foster and V. Syrgkanis. Orthogonal Statistical Learning. The Annals of Statistics, 2023.
E. Gorbunov, F. Hanzely, and P. Richtarik. A Unified Theory of SGD: Variance Reduction, Sam- pling, Quantization and Coordinate Descent. In AISTATS, 2020.
R. M. Gower, M. Schmidt, F. Bach, and P. Richtárik. Variance-Reduced Methods for Machine Learning. Proceedings of the IEEE, 2020.
C. Graham and D. Talay. Stochastic Simulation and Monte Carlo Methods. Springer Berlin, Hei- delberg, 2013.
M. Gürbiizalaaaan, Ozdaglar, and P. A. Parrilo. Why Random Reshufiling Beats Stochastic Gradient Descent. Mathematical Programming, 2021.
Y. Hao and A. Orlitsky. The Broad Optimality of Profile Maximum Likelihood. In NeurlPS, 2019.
H. Ichimura and W. K. Newey. The Influence Function of Semiparametric Estimators. Quantitative Economics, 2022.
M. Johnstone and F. Velleman. Efficient Scores, Variance Decompositions, and Monte Carlo Swindles. Journal of the American Statistical Association, 1985.
M. Jordan, Y. Wang, and A. Zhou. Empirical Gateaux Derivatives for Causal Inference. In NeurlPS, 2022.
E. H. Kennedy. Towards Optimal Doubly Robust Estimation of Heterogeneous Causal Effects. Electronic Jourmal of Statisties, 2023.
M. J. Laan and J. M. Robins. Unified Methods for Censored Longitudinal Data and Causality- Springer, 2003.
B. Y. Levit. Infinite-Dimensionn Dimensional Informational Inequalities. Theory of Probability & Its Applica- tions, 1979.
D. Levy, Y. Carmon, J. Duchi, and A. Sidford. Large-Scale Scale Methods for Distributionally Robust Optimization. In NeurlPS, 2020.
X. Li, M. Liu, and F. Orabona. On the Last Iterate Convergence of Momentum Methods. In ALT, 2022.
J. Linnik. Statistical Problems with Nuisance Parameters. American Mathematical Society, 2008
L. Liu, C. Cinelli, and Z. Harchaoui. Orthogonal Statistical Learning with Self-Concordant Loss. In COLT, 2022.
A. Luedtke. Simplifying Debiased Inference via Automatic Differentiation and Probabilistic Pro- gramming, 2024.
A. Luedtke and I. Chung. One-Step Estimation of Differentiable Hilbert-Valued Parameters. The Annals of Statisties, 2024.
R. Mchta, V. Roulet, Pillutla, L. Liu, and Z. Harchaoui. Stochastic Optimization for Spectral Risk Measures, In AISTATS, 2023.
R. Mehta, V. Roulet, K. Pillutla, and Z. Harchaoui. Distributionally Robust Optimization with Bias and Variance Reduction. ICLR, 2024.
Murphy and W. V. D. and. On Profile Likelihood. Journal of the American Statistical Association, 2000.
W. K. Newey. The Asymptotic Variance of Semiparametric Estimators. Econometrica, 1994.
12

---

J. Neyman. Optimal Asymptotic Tests for Composite Hypotheses. Probability and Statistics, 1959.
J. Neyman. (a) Tests and Their Use. Sankhyā: The Indian Journal of Statistics, Series A, 1979.
X. Nie and S, Wager. Quasi-Oracle Estimation of Heterogeneous Treatment Effects. Biometrika, 2021.
D. S. Pavlichin, J. Jiao, and T. Weissman. Approximate Profile Maximum Likelihood. Journal of Machine Learning Research, 2019.
J. Pfanzagl. Asymptotic Expansions for General Statistical Models. Springer-Verlag Berlin Heidel- berg, 1985.
A. Rahimi and Recht. Random Features for Large-Scale Kernel Machines. In NeurIPS, 2007.
J. Robins, L. Li, E. Tchetgen, A. van der Vaart, et al. Higher Order Influence Functions and Minimax Estimation of Nonlinear Functionals. In Probability and Statistics: Essays in Honor of David A. Freedman. Institute of Mathematical Statistics, 2008.
J. M. Robins and A. Rotnitzky. Semiparametric Efficiency in Multivariate Regression Models with Missing Data. Journal of the American Statistical Association, 1995.
J. M. Robins, A. Rotnitzky, and I.. P. Zhao. Estimation of Regression Coefficients When Some Regressors Are Not Always Observed. Journal of the American Statistical Association, 1994.
M. Robinson, Root-N-Consistent Semiparametric Regression. Econometrica, 1988.
A. Rotnitzky, E. Smucler, and M. Robins. Characterization of Parameters with a Mixed Bias Property. Biometrika, 2021.
D. Rubin. Estimating Causal Effects Treatments in Randomized and Nonrandomized Studies. Journal of Educational Psychology, 1974.
M. Schmidt, N. Le Roux, and F. Bach. Minimizing Finite Sums with the Stochastic Average Gradi- ent. Mathematical Programming, 2017.
A. Sclocchi and M. Wyart. On the Different Regimes of Stochastic Gradient Descent. PNAS, 2024.
A. Shapiro. Distributionally Robust Stochastic Programming. SIAM Journal Optimization, 2017.
C. Shi, D. Blei, and V. Veitch. Adapting Neural Networks for the Estimation of Treatment Effects. In NewrlPS, 2019.
Y. Song. J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole. Score-Based Gener- ative Modeling through Stochastic Differential Equations. ICLR, 2021.
D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The Implicit Bias of Gradient Descent Separable Data. Journal of Machine Learning Research, 2018.
A. A. Tsiatis. Semiparametric Theory and Missing Data. Springer, 2006.
L. van der Laan, M. Carone, and A. Luedtke. Combining T-learning and DR-Leaming: A Frame- work for Ofacle-Efficient Estimation of Causal Contrasts, 2024.
L. van der Laan, A. Bibaut, N. Kallus, and A. Luedtke, Automatic Debiased Machine Learning for Smooth Functionals of Nonparametric M M-Estimands, 2025.
M. J. van der Laan and A. R. Luedtke. Targeted Learning of an Optimal Dynamic Treatment, and Statistical Inference for Its Mean Outcome, U.C. Berkeley Division of Biostatistics Working Paper Series, 2014.
M. J. van der Laan, S. Rose, et al. Targeted Learning: Causal Inference for Observational and Experimental Data. Springer, 2011.
A. W. Van der Vaart. Asymptotic Statistics. Cambridge University Press, 2000.
13

---

S. Vaswani, A. Mishkin, I. Laradji, M. Schmidt, G. Gidel, and S. Lacoste-Julien. Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates. In NeurIPS, 2019.
R. Ward, X. Wu, and L. Bottou. Adagrad Stepsizes: Sharp Convergence over Nonconvex Land- scapes. Journal of Machine Leurning Research, 2020.
J. M. Wooldridge. Specification Testing and Quas-Maxiium-LLkelihddd Estimation. Journal of Econometrics, 1991.
1. 7adik, L.. Mackey, and V. Syrgkanis. Orthogonal Machine Learning: Power and Limitations. In ICML, 2018
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our claims are theoretical convergence guarantees for various optimization algorithms. The results are included in Sec. 3 and the proofs are written in the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: A detailed discussion including limitations, relationships to other work, and future work is contained Sec. 4.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech- speech-to-text system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
15

---

Answer:
[Yes]
Justification: Assumptions are given before the statement of each result and proof' are contained in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided not)?
Answer: [Yes]
Justification: While this work is primarily theoretical, we provide code that reproduces our numerical illustrations.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
16

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code is provided github.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https: : /rl:://nnnn /nnisnis.... publ c / gu des SCumemuomm i s.s onPol cy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //niss. cc ppublic. c/ gu idie///// /CodeSubrr
plyycy for more details. The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Ys]]
Justification: Experiments are included in Appx. G.
Guidelines:
The answer means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer:
[NA]
Justification:
Experiments of this nature are not included in our paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our numerical illustration is not computationally prohibitive, and can run on instance of Google Colab.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https:/ /twuurius.p../// httppbllc//thccccieeeellllll
Answer:
[Yes]
Justification: There ethical violations, the authors' knowledge.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
A "Broader Impact" statement is included before the references.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
18

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not provide any models or datasets in this paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not use any third party data/models that may incur licensing issues.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswi thoode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
19

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Question:
Answer:
[Yes]
Justification:
Our code is documented in notebook format.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Experiments of this nature are not included in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Experiments of this nature not included in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
20

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
No substantive part of this research involved the use of large language models.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer
LLM policy (https: / //eurrurr/////// ps wttccc///cooo /cc/onferreness//// 2025/LMM) for what should or should not be described.
21

---

Appendix
Table of Contents
A Notation
23
B Detailed Examples
24
Partially Linear Model
24
B.2 Conditional Averaged Treatment Effect
................................
27
B.3 Conditional Relative Risk
28
B.4 Proofs
29
Convergence Proofs for Stochastic Gradient
47
C.I Overview
47
Technical Lemma
................................
47
C.3 Proof of Theorem
50
D Orthogonalization with respect to Nuisance
52
D.1 Orthogonalization via Riesz Representation..................
52
D.2 Technical Lemma
53
E Convergence Proofs for Orthogonalized Stochastic Gradient
Overview
54
E.2 Technical Lemma
55
E.3 Proof of Theorem 3
57
F
Detailed Discussion
60
F1
Comparison to Biased SGD
60
F2
Discussion of Full-sample Orthogonal Statistical Learning and Related Methods
61
F3
Discussion of Interleaving Target Nuisance Estimation
F4
Interpretation as Control Variate for Variance Reduction
64
F5
Discussion of Double Robustness
65
R6
Proof of Proposition 22
67
F7
Proof of Proposition 23
69
G Numerical Experiments
71
Numerical Illustration
71
G.2 Simulations
72
G.3 Real Data Analysis
77
H Extension to SGD Variants
81
H.l SGD with Momentum and Averaged SGD
81
H.2 Adam
84
22

---

A Notation
Symbol
Description
θ C Rd
Finite-dimensional parameter class.
(G, lG)
Possibly infinit-ddimensional nuisance space.
(9, (g)
The nuisance space as a Hilbert space.
IP
The unknown distribution of interest.
E 2
The random variable under P.
0.
The target of interest. The true nuisance parameter.
90
g;0,
The prespecified loss function.
L(0,g)
The population loss Ez-F [e[0, gi Z)].
(0,gg);)
The score function (g
(6
The population score Ez-r Vo g: 2)].
(0,
The Neyman orthogonalized score.
(0,
The population Neyman orthogonalized score Ez-p SSmo (0, gi 2)}.
(Vo, o. Vg)
The gradient w.r.f. 8 and g
(Do; Dg)
The derivative operator w.r.f. 0 and g. The transposed Jacobian defined by V ,0 (0., 90) E gd The nuisance Hessian operator defined by V L 0.. 9o) L
Hog
Hgg
To
Linear operator defined by [Togl] = ( H s9 9) g¹
The strong convexity constant L..
M
The smoothness constant of L. Constants to bound the second moment of Sg(0, g; Z).
(K1, k1)
(a1,a2)
The second order smoothness constant of L.
81
The higher order smoothness constant of a Neyman orthogonal L.
Pno
The strong convexity constant (0.,
Mao
The smoothness constant of VoS (f,, 90)
(K2, K2))
Constants to bound the second moment of Smo (f, g; Z).
B32
The higher order smoothness constant of Spo-
1]
The learning rate of stochastic optimization.
n
The iteration of stochastic gradient.
m
The iteration of nuisance estimation.
Table 2: Notation used throughout the paper.
23

---

B Detailed Examples
In this section, we describe in detail how the three examples in Sec. from the main text satisfy Asm. 3 and Asm. 4. We first talk about the partially linear model (PLM) in Appx. B.I, and then introduce the conditional averaged treatment effect (CATE) based on the potential outcomes frame- work in Appx. B.I. Under the same framework, finally we talk about the conditional relative risk (CRR) in Appx. B.3. In addition, we also study a non-orthogonal loss usually used for PLM in Appx. B.1.2 and an unrestricted loss function for CATE in Appx. B.2.1. 1. The constants for all exam- ples are concluded in Tab. 3 and proofs of lemmas in this section are provided in Appx. B.4.
B.1 Partially Linear Model
B.1.1 Orthogonal Loss
We revisit Example from the main text where we consider the target of interest as a solution of partially linear model. Let Z (X, W), where X is -v-uuue input, Y is real- valued outcome, and W is a W-valued control or confounder. The space G a nonparametric class containing functions of the form
g [or,gx) W R x Rd.
Following the construction of Robinson [1988], this g is supplied the loss
E(0, g: 2) = 2 grrrr))) (w) (0, [x()))
(15)
To ensure 0, can be interpreted via the projection of (X W] onto partially linear additive functions, the true nuisance is given by 9u (90,x, I0,y), where
(o,y(w) = F Y
W w] and 90.x (w) = Ep XX W w).
We define the residual at 90) as
6 = Jo.Y (W) - (0x, X 90.x (W))-
Lemma 4. Let Y = (w)) and X X 90.x (w). We assume the following conditions:
(a) Amin (Ex [XX N for some constant Ao > 0. (b) [& la S Cx a.s. and Ex [e_] S a for some constants Cx, > O.
Then Asm. and Asm, 4 are satisfied. The target 0, the minimizer of the squared loss:
0, = arg min Eel(( - XT00
BEad
The proof Lem. 4 provided in Appx. B.4.1.
B.1.2 Non-orthogonal Loss
Suppose that the outcome Y is generated under the partially linear model:
Y (0o, X) + So) +
(16)
where Og E Rdd is the parameter, 9o W R is the true nuisance function and E3 [c X, W) 0. The space & a nonparametric class containing functions of the form
g g:W
We can also consider the following not-orthogonal squared loss function:
((0.g:z) = マ g(w) (0,x)) 2)
(17)
24

---

CxO1 + 1ix +G,)
20 +11.,lla)
den Cxx
4ng CCx(1
2(1+ [1e. la)rr
20x + 3)r
2Cx (65 +1r
Cx
O(r)
60 + 6(8 2 + 4ep' (+)) O(P)
270 0(12)
20
30%
Table 3: Constants All Examples.
120 + 40xil lle + +
2403 2 deg CB) +
(o +
1803 + 0(22)
30 2/a)
K,
03 1,2) 1,2)
++))+
63 +
M
C3
Ag
Ag
An
Au
(2) Non- Orthogonal PLM
(1) Orthogonal PLM
(3) Unrestricted CATE
(4) Restricted CATE
Example
CRR
25

---

We define the residual at (0., go) as
L=Y-9o(N - -10,, X).
Lemma 5. We assume the following conditions:
(a) Amin (E [XXT]) 2 do for some constant Xo > 0.
(b) |x I Cx a.s. and Ep [<]] S o² for some constants Cx, > 0.
Then Asm. satisfied and the target 02 is the true parameter, i.e., 0, = Og.
The proof Lem. 5 provided in Appx. B.4.2.
Orthogonalization. We can perform our orthogonalization method to obtain the Neyman orthogo- nal gradient oracle for this non-orthogonal loss. For any h1 h2 E G. define the inner product of G as
(01 h2)g = Ep (W)22)
(18)
x G By Definition the derivative of con-orthogonal loss (17) along the For any (0, g.). E e
direction of hi is given by
d dt
9: g:
(
(g th1)(w) (0.x))²) = (y (y-w (6, (6,)))/((w).
(19)
Do derivative on Dy 9: [h1] along the direction of h2 and we have
d
D2 9: 2) h2] = dt (~ (g + (w) (0. x)) (w)) h (w))2(w),
(20)
which implies
gh) = Ep [ (0.. 90: hel] = Ee [h1 (W))
By the definition (84), we have Hgg = the identity operator. In addition, do derivative on the score along the direction of G and have
d
D S0 gi [b] = dt
(- - (g th) - (0, (0)z))x) = h(w)æ,
which implies that
(6 = Eg [Se(0. g: [h]] Ep [h(W) [X W]].
By the definition in (83), we have Heg Ep [X W]. Thus, by (85) we have
To g [Eg X W g) Ep Ep X W (W)]
(21)
Thus, the Neyman orthogonalized gradient oracle defined in (86) is given by Smo (0, gi
So D,L(0, Er [X W = w|] -y g(w) (0,z)) Ep |X W w)).
(22)
Lemma 6. Consider the bounded linear operator 1 : G + dd such that [[ = (6()), .) Vg e g
for some 4(6) e G.j l....dd Let Y (w) and X -o. (w). We assume the following conditions:
(a) Amin (E~(XX for some constant Ao > 0.
(b) | S Cx a.s. and Ex [69] S a for some constants Cx, a > 0.
Then Asm. 6 is satisfied.
The proof of Lem. 6 is provided in Appx. B.4.3.
26

---

B.2 Conditional Averaged Treatment Effect
We now introduce examples in causal inference which are established based on the potential out- comes framework. The potential outcomes framework [Rubin, 1974] has been widely used in causal inference. Let Z = (W. X, Y) E {0, 1 x I& x I under some distribution P. We posit the existence of potential outcomes (1), (0) E The conditional averaged treatment effect (CATE) is then defined as
(σ -(()) X = z|.
To identify r0(2)) and the following causal assumptions are required:
Assumption 5. The following conditions hold:
(a) (consistency) Y Y(W).
(b) (unconfoundednesss) Y (w) 1 W X for all 10,
(c) (positive overlap) co S P (W- = x) < - co a.s. for some co > 0.
Under Asm. 5, can be identified by observed data since
(x(x) [1) (0) X = x] [Y W 1,
Bp ( W 0, =
Ep[Y W = 1,X =x] x]- EY W 0, X = x].
B.2.1 Unrestricted Nuisance
We observe Z = (X, Y, W). where W is binary treatment assignment. The functions in G are of the form
(g poop) Rd R x R,
and are evaluated (see Nie and Wager [2021, Eq. (2)l) at the loss
8 (0, g: 2)
(y gmd (w (x)) x))²
(23)
For 90 (g out prop propensity score, respectively:
90
nuisance functions 9hth and oo represent the outcome regression and the
go 0tt (x)
| X 2| and (x) Br(W[] X x].
We define the residual under the true model as
= g0 pat (X) - (W groo (X)) xx(
Lemma 7, We assume Asm. 5 and the following conditions hold:
(a) Amin (Ep [x 2 No some constant Ào >> 0.
(b) |X|| & Cx and (To(X) s Cr a.s. and Ez (c4] S a for some constants Cx, Cr, a > 0.
Then Asm. 3 and Asm. 4 are satisfied. The target 0, is the minimizer of the squared loss:
0, arg min Ez [[W - "0
-0 (x)) (To( - T0
BERd
The proof of Lem. 7 is provided in Appx. B.4.4.
27

---

B.2.2 Restricted Nuisance
We observe Z (X,Y, W),, where W is binary treatment assignment. Here we restrict the propensity model as grop I + (0, 1). The functions in G are of the form
g (g gd gDmp) R R R (0, 1),
and are evaluated (see van der Laan and Luedtke [2014, Thm. 1J) at the loss
gmmP(()
2 (x))) -0,,
((0.:: g: = (z)
(x) geup (z) grup (x))
(24)
This loss also appears in Foster and Syrgkanis [2023, Eq. (23)]. For 90 = (90 (0) (1) prop nuisance functions 9o and 9o represent the outcome regressions
1,00'000 90
10 (z) = Ep W =
=1, 1, x| and (x)) FF W = 0, -0,x=00 x]-
We define the residual as
W
9o
prop (X)
(Y - 9o
-9 (X)).
(W)
90
poop
(X)(1
To prop (X))
Lemma 8. We assume Asm. 5 and the following conditions hold:
(a) Amin (Ep [xx]]] 2 No for some constant Ao > O.
Ep 22 S 2 |X||a Cx, and Y - S Cr, 0, a.s. for some constants
Cy
Then Asm. 3 and Asm. 4 are satisfied. The target 02 is the minimizer of the squared loss:
0, = arg min Ep -
8E3d
The proof of Lem. 8 is provided in Appx. B.4.5.
B.3 Conditional Relative Risk
We retain all components of the previous example, changing only the loss and assuming that the First, consider the "label" function
outcome is
1 1(w = s)
p gx* sgpiop (x) (1 =1 (x)) (x)),
where (-)) denotes the indicator function, and the log-linear predictor (xx = el0 /11 + e el ).
Following Example 2 in van der Laan al. [2024], then employ the cross entropy-type loss function
e(0, gi z) = T (=) log + (z) ((log())((x))]]
(25)
Lemma 9. We assume the following conditions:
(a) Amin (Ep [xx]] 2 do for some constant Ag >> 0.
(b) X E Cx and (ww) 90 "00 Cy, w = 0, a.s. for some constants Cx, Cy > 0.
(c) 8 < 90 00 (X) + 90 (1 (X) < 8-1 a.s. for some constant ö > 0.
Then Asm. 3 and Asm, 4 are satisfied. The target 0,, is the minimizer of the weighted cross entropy loss:
0. arg min - -E (X) log (o + go (o) HERd
The proof of Lem. 9 is provided in Appx. B.4.6.
28

---

B.4 Proofs
B.4.1 Proof Lemma
Proof. We consider the following loss:
1 - gr 10, (x())))
e(0, =)
with the corresponding risk function defined
1 Be [(Y gr (W) - -xx
L(O, g)
2
Let V Y (w) and X X - (w)) By definition, the target O, is the minimizer of the squared loss:
arg min Ep [ir xT = Ep X 8ER*
Ep
YX)
(26)
Differentiating E(0, gi 2) with respect to 0, we obtain the gradient and Hessian w.r.t. 0 as
(0, 2; - - gy (w) (0, - (x (xpll===xx())) 9x(w)), Hee (0, 2) = (x exxx((e (w)) - (x()))
The expected gradient and expected Hessian are then obtained as
So(0,g) Er [(Y gr ( (0, gx (xx)))(XXxxx))))
(0, = Er [(x 9x (W) - 9x (
We consider the nuisance neighborhood such that for E Gr (go).
|gg golle max Ep [Wl -o.. Ep [(r (wW) Sr. (27)
We now verify that the loss function e satisfies Asm. 3.
(a) We assume that 9x(w) W Idd and gr(w) W R are continuous functions, thus
Asm. 3(a) is satisfied.
(b) By (26), it follows from KKT conditions that
So go) = -Ep [(8- - (0., x)) = 0.
(28)
(c) Since Ex[X W] and Ep Y
W O, we have
Hao (0,()
EE [
[(xx 9o.x (0.x(WW)(xx(1)) - (w)) (w) '].
For any g Gy, when Amii (Bpp (XXXXX] > Ao and ||X1|2 < Cx a.s. we have
A Hoe (f,g) & (C² + 2 p Ao and M C + r
(29)
(d) Consider the Taylor expansion around 0,, we have
Sg gi Z) Sa g) = Sp(0..g; 2) - Sp + (Hoo(0., 10.00.. g: 2) - Hoo g)) - 0.).
Let V (0+: X). Note that X gx (W) X (gx 90.x (W) and
Y - gr (W) - (0., (x)) = - (gr (W) + (0., (9x 90.x (WW). (30)
29

---

Since Ep |e| W] = 0. Ep[x | W] = 0 by definition and Ee(eX] = 0 by (28), then for any g E 9, (90),
[0. 0](l2 |Er 1lor (ox 90,x)
(f+, (ex (W)) 20,x (W)xl < Bp [(or ) By ||[ex ( 1/2 + +E 11(ex -0)x) 110.12
$ <r + I10.11).
Similarly, we have
[S0(0..) 2)122 - (c - (gr - 90,y (W) + (0., (ox - g0.xx (W))) 1| (gx - 90.x (W)
5 (e² + ((gr - 90.y (W)) + 1lex 90. (W) [B) (Cx + 11xx - 30V))()))l2)
< 16(( (e2 + ((gr 20.r (0.r) (W))² + 11ex 90,x s0,x)( (3) (C) + ||ax -
which implies that for g E Gr (90). when Eplc*] s ot.
Ex (0 gi 2]
I I6C3 (Er [c2] + Ep [((9> - 90,y ( + Es [ex - g0.x ( (10.11)
+ 61Ep [e]1((x x0.x) [13] - 61E> [[99
- 90.xx (W))
+ -E?> [][(xx (W)) 110.12
I 60% (0² + + 12, (2) + 6r 11. + 6 (Ee [e-] Ep [ll(x - -0,x) 1/2
+ 6 (Ep [(99 yo.y 20.r (W)) Ep [[((x- - xo,x [la]) 1/2
S 660 0² + 66 + 0% (1+ 1 {)} 6 110. 13))
Thus, for any g E Gr (go),
Eell g: 7) - (f.. M) < 2F, [1)50 g; 2) + +211So(0...))1
I <12020² + {120² + 2(1 + 10. + 120 (1 + 10.
1B)] |1.
+ -12(1 + 12)
120 + (r²2)
On the other hand, since
(H g: 2) = 11(8- (gxx - 90.x) (W)) - -9x -9xx-90xx -90x)(W)) 112
$ 1 (gx x0.x) (W)
< 2118112 + 211(xx 20,x (WV 3 2203 - -211(xx (0.x))()))
by (29) we have
|HHoo(.. -
S (00 2))2 + |1H (0..
$ 30 + 72 + 211(xx - 90.x xW.))
which implies that
EFo] (O,, 2) Hoo (0., (0.,
(00.)))0000))11 -0-000--)13 $ Bp (30x + + 21l - -0..) ( ||0
0.)1
0.112
= -90 + 0(+2))100 -0.12.
Thus,
Ep [1S5 9: Z)- - So((.
<2E, [| - So(O.. [|]] g: Z) Hoo (0., ()) 0.)1 + 2Ep (0.
<21C + 0 (18C* + 0 0-
30

---

which implies
K1 o2 + O(r)) and K1 = 180 + O(r2).
(31)
(e) For any 0 E O and 9.9 9r (gn). by (30) have
D₂ Dg 9) 0. yo]
= Ep [( 11- (gy go.r (W) + (0., (ex 90. [ 0.. (øx 90.x (W)))
+ EP 11-(11 (ōr 90. (W)) + (0., (øx (W)))) Or, (ox 90, (0,x) [W]]]
Since y E Gr (90),
[Ep |[- (gy - 90.r) +
- -x.xx 0.. (ōx - 90.x 90xx(
$ Ep ||(gr g0.y ( (1xx (0) 0.112
+ =100112EPp [1l(x 90.x (W) - (00x 110 0+112
- Ex ||((x - -ooxx) 1/2 Ep ((gr - (or) 1/2 110 0.112
+ |00. 112Ep [ll@x - 90.x) ( 1/2
Ep [l[(x 90.x) 1/2
|00 0.112
S (1 + 110+12))|11 - -90lll/1000011001 0+1/2.
Similarly,
EE (ğx 90,y (W) (0., (ōx (W)) 0., (gx -0,x)
I (1 + |0_1|2)r|1g - 901lo110 0,112.
Thus,
Dg. () - 0.. goll
$ |Bp (gy 9o.y (W) (0., (gx 9o.)) 0., 0., go.x)(W)))
+ EE [[ (ōx 90. (W) (0., (ōx 90.x (0)))) - 0., (ax (0.x)
s 2 + |10. 122)r1ll - 9olle|10 0.112-
which implies
a1 2(1 + 110.1122) 112)r.
(32)
In addition, the risk Neyman orthogonal at (0+, 90) since
DyDoL((A.go)) go 0..g gol
(33)
Note that
L 0,,9 90.9 g0]
2Bp 1(-(gy 90.y (W) + (0., (gx 90,x (o,x) 0,, (gx g0.x -0o.x) (W))
By identical proof of (32), we have that I satisfies Asm. since
( g) 0.,g 90. g gol s 2(1 + |10. 122 - 90ll3110 0. 1|2.
which implies
B1 = 2(1 110.
(34)
B.4.2
Proof Lemma
Proof. We consider the following loss:
{(0, =
2 (y ((w)= (8, x2)
31

---

with the corresponding risk function defined as
g) Er (08-9(1) [V-- - x))]
Under the true nuisance, the target the minimizer of the following squared loss:
0+ = arg min DER
3 Ep [(Y - gw( - (0, x))
2
Since e Y go() (0u. X) satisfies Ep |e X, W] under the true model, by bias- decomposition, we have
1
0. arg min Ep [((0,. X) (8,x)) 0g. BER2
(35)
2
Differentiating E(0, 9i 2) with respect to 0, we obtain the gradient and Hessian w.s.t 0 as
S0 gi z) -y gww) (z, 0)) and Hev g: xz.
The expected gradient and expected Hessian are then obtained as S, Ep [(Y g(W) (X, 0)) and Hoo = Ep [Xx]]
We consider the nuisance neighborhood such that for Gr (90).
|gg واllو Ee [(o(W) 9o (W)) 1/2
(36)
We now verify that the loss function satisfies Asm. 3.
(a) We assume that W - IR is continuous, thus Asm. 3(a) is satisfied.
(b) Since 0, do by (35), we have
So -E [cX] 0.
(37)
(c) When Amin (Ep [xx]] Ao > and |X||2 S Cx a.s. L(O,g) is An-strongly convex and smooth since
AoI & (0) ~ C = μ= Ao and M = CC
(38)
(d) Consider the Taylor expansion around 0., have
So Z) (e g) = So(O., Z) - So (f., + (H., g: Z) - (oo - 0.).
Since So(O..g;2) 2) ((g - (w) - x) and ||x||2 1 S Cx a.s. we have
[[ g: Z) So(O.. g) 11((g - (W) c) Ep [((g- - gu) (W))
- Cx (1(g -0) + Ep [1 (W)) [c))
On the other hand,
Hoo gi 7) Hoo g) x [
[XX]] * 2
which implies that
|| Ho (0..: 7) (0o ()) - -0.)1l2 S 2 110 0.112-
32

---

For E G. (9o), when Ep [<]] I o² we have
Ep [1) g: Z) So 2 [1 9: 2) So(O.. 9)1
+ 2Ep [1. 9: Z) - Hoo (f. 9) 9) - 0.)1
$20 Ee [I[o - (W) + Es [(g - (0) + +<])*]
+ + 110 - -0.12
<603 (2Br [([o g0) (W))) + Ep [c2] + 20 110 -0.12
<607 (2r² + +o0) + +C 110 0.112.
which implies that
K1 = 6C (2r² + 0²) and 11 = =20
(39)
(c) For any A E θ and 9.9 E Gr (90). we have
DD g) 0.. g goll
Ep [[g (w) 0.)1
S Ex [1( (W) (X,, -0.)1
- Cx 110 1. [((g - (w)))))
which implies that
a1 Cx.
(40)
B.4.3
Proof of Lemma 6
Proof. We consider the following loss:
((0,g; 2) = -V- )(w) - (0, x))
2
with the corresponding risk function defined as
1
L(O.g) g) _e [(Y- - gg()) - x))]
First by the same proof as Appx. B.4.2, we have 0. = 0g. Define the inner product (1 as (18) and define the norm Il-llg such that || = (g. g)g Vg E G. Consider a uniformly bounded neighborhood Gr (90) such that
(go) fg e g lo(W) gu (W) S r almost surely).
(41)
The NO gradient oracle for this non not-orthogonal loss is derived as (22) such that
Se g; 2) = (v (ww) (0, (x) E X W w])-
We now verify that Asm. 6 is satisfied.
(a) Since Y (o(W) (fo, X) satisfies EE [e X, W) first have
O under the true model, by (22) we
(0.,
Ep [Sno (O,, go; Z)] -Ep [e(x- - E [X| WI)
-Ep [Bg X, W] (X E [[X W])] 0.
(42)
Let (00)
Hhg 1 for j I....,d. d. By (85), we have [Tggh (166) (96%..).. Vgg E G. Thus, by
(
(82) have
[ - (o)
g [(,, ), = (4:) - -0) L(I 900) = D.I( 12(0) - (5))
33

---

which, by (19), implies that
= -E cef - [oll
= Ep Ep le w] - rol( = 0. (43)
Thus, Asm. 6(a) holds true due to (42) and (43).
(b) By (22), for any (0,g) E x
Vo Ep [X Ep [X W]
-Ep [Xx]] Ep Ep |X B |X w]"
Ep [XXT]
(44)
which implies that
Amin VoSnn Vo
2mpp [XX 2 2A0.
Thus, Asm. 6(b) holds true for u Ao-
(c) For any (0,g.9) x Gr (go). by (19),
Ep [DgT(0,0 [) - Dg ((..0)())))
Er [Dg ())))
[Y- ((-((w) x)) (o(W))
Ep
(o) - (0 0., x))² (o(W))) Ep (E - (g (g-)))
3Ep (o(W)) |²] 3Eg (g (o)) ((()))) + 3Ep -
0,, x)² ( (o(W))²]
Assume that Ep [e2 W| - 0² and | 1 Cx a.s. By (41) we have
Ep (0, 9; [g] D,L(0,9))1) < 3(0² + + + 1 0.113)19113
(45)
Thus, Asm. 6(c) holds true for K2 3(0² + p²) and A2 = 3C
(d) For any (0.g. 91, 92) E e 9. (go) x x G, by (20).
|D 02]
= EEp [و] (W) )g2 (W)]l
< Ex [(0 (W) ) 1/2 Ee (1)) = =199lllllleelss
(46)
In addition, for any (0.0.g) x x by (19) we have
DDD,, g0) 0.]l = DşEp [(Y - 90(W) - (0, (0,x)) 10 0..l
[ (0 0., (W")))1
Ep (0 0,, x)] 1/2
Ep ((o(W)))211/2
Cx ||0 0111211116--
(47)
Thus, Asm. 6(d) holds true for a2 = 1 due to (46) and a
Cx due to (47).
(e) Note that
Su (0, 2) = -y g(w) - xx Ep W = w)).
which implies that for any 91, E G,
D2 Sm (0, gi 2) 291 =
(48)
Thus, Asm. 6(e) holds true for 3, 0.
34

---

B.4.4
Proof of Lemma? 7
Proof. We consider the following loss:
{(0.g:2) = (y gm) (w g (0, x
with the corresponding risk function defined as
L(0,g) g) = Ep (Y (X) - (W- - gmmp ()) (0, x1)
2
Note that E = Y 900 (X) - (W- 10 (X)) (x)). Under Asm. 5, we have Ex [e | W| = 0. which implies that
- L(,, go) = BBp (e+ + (W - 96 (x)) -x0 x
Ep [W ob (x)) (To (0, x3) + = [e9]
Thus, the target is the minimizer of the following squared loss:
0, arg min Ee (W -(tT(()) (To(X) - (0, SER
(49)
Differentiating E(0. gi 2) with respect to 8, we obtain the gradient and Hessian w.r.t. as
(o =) = (y - gr' (w - (x)) (0, x)) (w - ))))(()) x, Hea (0, (w ( (x))) xz T.
The expected gradient and expected Hessian are then obtained as Sp g) = -Ep (Y - g nutl (X) - (W - gp (x)) (0, x)) (W- - (x))
Hoo (0 = Er (0 (1 g0od ) + ((g - ) (x)))) xx
We consider the nuisance neighborhood such that for E Gr (g0),
llg gollg max I8p [(1 (X) - g6 (x))4} Ee (X) goth (x)){}} s..
We now verify that the loss function f satisfies Asm. 3.
(a) We assume that nTt Rd R and goopp Rd IR are continuous, thus Asm. 3(a) is satisfied.
(b) Since 0, is global minimizer of (49), we have
Sp = 0.
(50)
(c) We assume that co S go prop < cc a.s. for some co > When Amin (Ep [XXT]] 2 do > and |||||2 < Cx a.s. we have
ca & (0, & (1 + = μ cgdo and M M= ( +1+
(51)
(d) Consider the Taylor expansion around 0., we have
(g g; Z) Sa(O, g) = Sp(O.. 2) - Se g) + (O.e 2) - Heo 9)) - 0.).
Note that
So (0... 2) (Y (X) - (W- g (x)) X)) (W- -X)) X
(c (g 90 (X) + mrp 9o prop ) (X)ro(() (W gpoop())) x
+ (W nuuu (x)) (10.. x) - To (X))x.
35

---

We assume that To R² + I is continuous. Then when || - Cx a.s. |To(X)) - C+ for some
C+ O. It follows that
[|So(0.. 9: 2)1l2 ICx 1(c (g - 90th 00th)(( (X) + (0 -0 ) (X)ro( (W- - ( (X))
+ Cx (W- - (x)) 1(0, X) - -o((X)
xxx (1el + |( - 90 out [X)] + CT - - -)nh (X)l) W - g
+ +xx(Cx110 1001x110011-0000 C+) (W g)
Since Ep [W - gm (X))² x = gn prop (1 - p (X) + ((g (X))2 and (W-
gropp x)) s 2+ + 2( 90 (x)) we have
(m)p(x))
prop)
Ep [|So(O., 9: [)] <40 Bp [e (1 + ((g go (
+ -40 [((g 96 (x))² (1 +++1 ((g - -0g - )
LOR00, [((g - 90 m (x)) (1+ + ((g gb (X))))]
+ (Cx 110-112 + 2pp [++ 4((g ) (X))}]
When Ep [<t] S o by Hölder inequality,
Ep [| g: |) (4xxx=++( + + CG)r² + +4 C2 + 4(x 10.112 + )r,
-
Similarly, use the fact that Ep |c| W, X 0 and by the stationary condition of (49), we have
g)
Up [[(gg'M
0M 90 =l (X) ppp 90 00mDP) (X)) (g - )) (X)x]
Ep [([W- 96 prop (X))² + ((gpuup 90 (X)))² ((0,,) X) - [X]
Er ((gg
90 (X) - (gg - - - (X)) (g - 0 (X)x]
+ Ep ((p 50 (x)) - (x()))
which implics
|So((..))113 + +C)))r
On the other hand,
Hoo 9: Z)- - Ho) $ (W- - nmpp (X)) Xx + (1 +1+ C3
x Cx + 12 + 2( - o)
which implies that
EE [[o. 2)- -oo (o. ().,9) - 00) s <990 + ( 0. 112.
Thus,
Ep [1)5o(0,9; - 00.00))113 <3Ex [1 (0.) g; 2)13 3 | (o 9)
+ 315p (H.. 2) Hee 0. 0.)
which implies
K2 = 120 (0² + 4(Cx((111)) + +C))) and x1 = 27C + 0(+2)
(52)
(e) For any 8 E θ and 9.9 E Gr (9u). we have
(0.. - 0..9 9 - go]
= -Ep [(g 90 (g prop 5e (x) - (g - 90 out (g
96
prop ) (X)) (x, 0.)]
+ 2Ep [To(X)(
90 prop (g go (X) - 0.)]
+ 2Ep Pop - go0 (g go (X) - (x) 0.)
36

---

Thus,
DyD - 0. - g0ll
- -Cx10-0.11bbb (
90 (g Fo pmm (X) + (9 - 90 ) (g pm)) (X)
+ 22Cx + -x116.11a1100-B.1
( 96 prop ) g0 p(x))( (x)
& Cx(1+ (Cx (2) 1.112119 - 90lls.
which implies
œ1 = =x ( 10.x110 Ct))r.
(53)
In addition, L( is Neyman orthogonal at (f., (o) since
DoDoL((+ (0 0,, gol = O.
Since for any 8 E θ and 9.9 9, (9o).
(2., - 0..g- - 90. 9 - gol
EEp ((g 90 (g prop 96 (XX) = (0 - out (g - ) (X, 8 -0,)
+ 2Ep [xo(
90
mrpp
(X)) -0.)
2Ep [((g 90 (X)) (10., X) (x -0)]
Similarly, show that
D 0,, -
90.9 sool
Cx(1 Cx(1+4((x|100112 + 0. 121111 gu 90113.
which implies that
81 +==xx1144CCx/// 1 +C)).
(54)
B.4.5
Proof of Lemma 8
Proof. Let
w - g (x) + (x) (z)) (y (x))
bgg 2) = (x))
We consider the following loss:
{(0, gi 2) (6(g))) x),
with the corresponding risk function defined as
L(0.g) = 2 Ep -(0,))))
2
We define the residual as
W
9ū
prop (X)
yo (X)) (Y 96"
(W) (X)).
pap (X)(1
96
Under Asm. 5, we have Ep [c
W, X = Since To(x) = 90 (1) (z))
go (0) (x), we have
L(0,
BBp (E + To(X) - (0, x))
= Ep (TT((X) - (0, x)) + Ep [c]]
37

---

Thus, the target is the minimizer of the following squared loss:
0_ = arg min Ex [(To(X) - (0, [)]])
(55)
BER
Differentiating 8(0, gi 2) with respect to 0, we obtain the gradient and Hessian w.z., 0 as
5:(0,9;2) = - (o(g: 2) (8, x>) x, H0 (0) = .
The expected gradient and expected Hessian are then obtained as
S, EE [(p(g: 2) (0, X)) X].
Hoo = Ep [Xx]].
We consider the nuisance neighborhood such that for g E Gr (00).
177
(
(1)) (X))
(
(g
90
prop (X) gotop) (X)
||g - gollg == max
Ep
18p
ST.
g
We now verify that the loss function satisfies Asm. 3.
(a) We assume that g(w)
R + R. 0, 1, and grop Rd + (0, continuous, thus Asm. 3(a)
satisfied.
(b) Since 0, is global minimizer of (55), we have
So(O.. = O.
(56)
(c) When Amin (Ep [XT]) 2 do > 0 and |X|| S Cx a.s. we have
AoI Hoo (0, $ C μ do and M C
(57)
(d) Consider the Taylor expansion around 0., we have
Sg (0 Z) (0, g) = So(O.,g; Z) - So g) + (Hoo gi Z) Hoo g)) 0.).
Let -0( (0) and
1
(1 <(gg;))
(oooa ( (x)
prop (1
prop (x)
doni 96 audd (
(x)
(mab) + 50
prpp (x)
Aood (1
[] ool
(al) dooadd
(2))
Under Asm. 5, we have
) (X)
W6: X)] < 2002
ppopp) ()
( (x)
We can decompose So. g; Z) as
So(O., gi 2) + 1g + + 17
97 57
87
197 +
38

---

where
1 = - ((T - TX) + TX(X) - (0-, x7) X,
12 (g: X) 9h 0 (X)) ( 90 " (X)),
13 <' XWW 96 (X) 90 (W) (X)X,
44 <' (o -5 (X) - 90 (W) (X))X,
J5 (9; (g(g9T S 90 prop (g (W) 96 (X)x;
(W- 90 (X) (Y 90
(W) (X))
I6
X -ex,
9
prop (1 90 prop
(X)
(W- go T (X)) (g (W) 90
(W)
(X)
17
X,
9o ddl (1 96 (ono (X)
_0 (X) (Y 90
(W)
(x))
1g
X,
90 pro (1 90 (oo (X)
90 ) (W) ())
(g)
(W) (x)
90
1g
X.
96 Prop (1 yo prop) (X)
For 11, when ||1||2 S Cx a.s. we have Tx(( (0,: 1 C for some > 0 and
|4 S (1(T (x)( +C),
which implies
Ep [|4 S 2C C*))
For 12, when y 96 (x) s Cr a.s. we have
0g 00 (X) gorop - -ggpp))( (X)
12ll2 S 40p CxCx
which implies
Ep [1 [2] - 160 (Cxxx
For Is.
[alla & 2x
(gpopp - 90 p1op) (X)
(m(0) -
-56 (1)) (x0
gpopp1 -pppp) (xx)
which implies
Ep 11 < 16cg + C22
For 14, since 1g
ddop
< 2,
(0g 000 )
||4||2 < 4cp20 Cx
gprop(1 - gprop)
which implies
Ep [14 < 160 (e0='"(xxxx)) (Cxxx))22
For Is.
(gpoop - 90 prop (X)
||a/|22 < 4c52
(g(4) - (0 ((0)
gpeop(1 (1 -g (X)
39

---

which implies
Ep [14: S 160 4 (Cxxxx)3
For 1o-
Holla S lel.
When Ep [c²] S 0², we have
Ep [1] S O2
For 17.
1 S 20 Ox (c) -)
which implies
Ep [|111|]] I C3r2
For Is.
Msll S c0 CxCr - 50 (X))
which implies
Ex || (Cx
For To.
||ll|2 S 10 2x prp ) (x)] (g( -6 (x)
which implies
Ex [144]]]] S Co r2
By Cauchy-Schwarz inequality, Ep [[]So gi Z) [ < 900 + 0
inequaally it follows that
+
Similarly, we have
|Sa < 90 (2C + + 0(72).
Since Heo 2) He0 (0..g) $ I we have
|I(Hoo (0. 7)- (oo(O..g))C - 0.)13 S 1 - 12-
Thus,
Ep [1Sa 2)- 9) <3E. [1 2| + (3))
+ 3Ep (H (0.,g: 7) (0. (0 0.)
-270 o202 + +0 110 0- 112
which implies
K1 = 22C + + 06r2) and K1 =30+-
(58)
40

---

(e) Since Y = (1 - -Y aue g (X) = can be written as
- + (X), Φ(9; Z)
W(W- - -
(.y.i - (X)()) - -To(T))))
1 + (g: 2) = To (o(x)
(X) (ooae -ood MM
-arppe Aoloolo (X))
W W
+
Semuia - 11lae Bauud b
(X)) (x)
- (0(0)
10
(.96 (X) + " - Llmmee ( (xx) (Y(1) - ( - to()))
(X)) + +
(X) Yiaaoo
= (X(o) +
(X) Aouue -
( M
W.
- ganng g)mpp()) (x) (0)0 - 96 (X)
W gproo (X)
+ gomp (X) gron (0( (x)) + g (V(1) (()) - (x)))
Under Asm. 5, we have
g
gh gotop
prop
g
poop grrop (0)0) -0 (X).
Ep [6(0; Z) X] = (X)
و n)
90 (X)
Thus, for r = g - g0 and for any 0 E θ and 9 E Gr (go) such that = tg + (1 t)go for some E (0, we have
DyD,L ( 0.. 9 9ol
= =D (EE [Ø(g: 2) X] + (f., (X, 0- -0-)] - gol
-Er [(x, D,) (Ø(0: Z) X] [g goll
Io prop
gi prop
--Epp (x, 0.)
(gpopp) (g
96 2 (g gb p (X)
0)
96 000 (x))
grop
- -Eg (X,0- 0.)
In propy (groop go prop) (g
96
mop
90 Gooo
prop
(g (0) go 100
(x)
gorop )
Since (a + b)2 S Sa² + 8822 for a, b E IR we have
gra + daaud (Xm (x))
come (x)1
E
= E
groop (X)4
grop (X))
g (X) + (X))(
s 8IE.
< 8r 4 + 8.
(59)
group x))
Similarly, we have
(1 50 (X))
E
3 18 + 8.
group X))
It is easy to show that
prop
Ep (X, 0 10-0, 0.)
(gropyz (
90 (3) (g - D8 00000) (X)
< (8r 88)+100 0. llallg gollg.
and
Ep
(x, 0 - 0.)
gmmp
gn
prop
(g 1)) 96 (x)
$ 5xxrl10 - 10110-0.12211 0.11211g gollg.
grou
Thus,
L,D,L((e..))e 0.. g goll
< 2((8** + +88 + 1)Cxxr10--8 - -0,11211 - gاlle
< 2(2(r +1) + 1)xx 0.112 -gollg.
41

---

which implies
01 = 20x + 3)r.
(60)
In addition, L(0,g) is Neyman orthogonal at (0+, 90) since
(f.. 0,, 9 gol = 0.
We have the higher-order derivative such that for any 0 E O and g. 9 E G, (gn),
D 0) 0,, 9 90. 9
Dol
00000 (g
(g (X) - 966 (x)) (x,0 0.)
=
(gprop) )3
96 10 (gproo
9 propp
(g (g (X) 96 (x)) (X,0 - 04)
2Fp
(gmup))
(1 g6
go poopy
(g (X) - 90 (x)) (X,0 - -O,)
2Ep
33
(1
(apdop (aii io
go prup)
(g (X) - (0) (x)) (X,0 0 - 0.)
2Fp
goron)2
Note that gorop = igpp
t)go (1 +
for some t E 1) by Taylor's theorem. Then
(X)
O (X)
goop
(1 + x) Joorid
t)g0 " (X)
1
t (1 - 1) S 5.¹
(61)
(1 1+t
(66 / /gmp (X)
Thus,
Ep
go prop (g
(x) 96 n (x))
(X, 0 - -ai)
(gmopp) )3
(gpop)) (grrop (X) ( (X)) 1/2
500h (X) - 960d (X)
1/2
<
Ep
Ex
Cx 100 0,112
[groo))
(ghop)
gooop
S <66 Cxrl10 0.11ellg - goll3.
Similarly, we have
p (g
m (g (X) 06"0 10'(' (X)) (x,6 -4b]
Ex
(gmpp)2
(g
22
(g
se ) (g)=)) - go (
< Ep
(x)
Cx110 - 0,112 S <x=0xx100 - 0-11alls - 30...
(2
gruup
group
Then we can show that
L(.,,L(O..,)0 - 0..9 gu.9 y -uul S
+ (1 0. 12111- - 201l..
which implies that
31 = Cx +r).
(62)
B.4.6 Proof of Lemma 9
Proof. Define
1 1(w s)
(z) =x' +
sgpoop (xx) (1 s)(1 (010p(s)) (y (x)),
42

---

where 1() denotes the indicator function, and the log-linear predictor pe(x) = e/0,2) /11 + cll Under Asm. 5,
I( =
Ep lug" (Z) X] Ep (X) sgmmp(X) + (1 s)( ) (Y(s) - g() x
(x) sgo prop (X) + (1 - 6) 00 (X)) (x) -x)
sgoop (X) (1 8)( - (o0oo(X))))))))
(2s () (X) 00 (X))
(X) sgRop (X) + (1 6) - yprco (X)) (g) (X) (x)) =: (g; (g: X). (63)
We consider the following loss:
((0,9: 2) = [ (z) log (x) + g log(1 - po(x))]
with the corresponding risk function defined as
L(0.g) Epp [mg (Z) log (x() v (Z) log(1 - po()))]
By (63), we have Ep Ep (2) X] 96¹ (X). Thus, the target is the minimizer of the following squared loss:
0, arg min -Ep |g - (X) po)) + 90 (X))log( -e(()))
(64)
EERU
Since Vopo(x) = po(o)))(
pa (x)) (x)) jr, we have
Vo (o))) = (xpo(x) = -(1 - pp(()))
pe(z)
Vo)o(x)
Ve Volo po(x)) = 1- (-pp(x) (2)
Differentiating E(0, gi 2) with respect to 8, we obtain the gradient and Hessian w.n. as
So(O,g; g: = - [46] (=) po(x)) 1 (=)po(=)=) H0 g: 2) (4g) (z))po po(x))
The expected gradient and expected Hessian are then obtained as
So(A. g) = - Ee (g: X1 Po(X))XX - from (g: X)po
Heo g) = Er (f X) + f (X) (x
We consider the nuisance neighborhood such that for E Gr (90).
(g(m)) (()m)))))))) g (w)
(wr) (x)
47
(g grop (X) grop
47 1
||g gollg max
Ep
- - (x))
EEe
ST.
grrup (X)
We assume that 8 $ 9o +g (1) (X) S 5-1 for O. In addition, we assume that for E Gr (go),
(g; + f()) (g: X) 2 a.s. Note that
gmmp (X) 0000 (X) (1 prop (X))
Ep (1 (): + n (y: X) <
Σ Ep
(x)(() 266 (x))
(0(111
< 8 + 2r
We now verify that the loss function satisfies Asm. 3.
(a) We assume that ((") Idd + R. 0, 1, and grop Ed + (0, 1) are continuous, thus Asm. 3(a)
is satisfied.
43

---

(b) Since 0, is global minimizer of (64), we have
So 90) = 0.
(65)
(c) We assume that O is bounded such that C S (x) 1 C a.s. for some C' 0. When
Amin (Ep [XxT]] 2 d > 0 and ||X||2 I Cx a.s., we have
CO & g)) < C + 28 20-22''20 1) = p C280 and M = C 20--21''0 1?). (66)
(d) Consider the Taylor expansion around f., have
So g: Z) Sa, g) = Sp(O.. Z) - So(O.. + (Hoo(O., g: Z) - ()) - 0.).
Note that
Ex [1.: 2) S5( S.(0+:94115 [1] S Ep [0.. 9; [)]
s C (1 (2) + 14g0 (2)
s 20 E (Z))² + (n) (2))
For 8 1, when ((1) (X) S Cy a.s. for Cr > 0, we have
96 (X)) + (X) W
W
(Y- (6- (6)( 27
Ep Er(ug] (1 (2) Ep
(pRon (X)
( - (X) (Xoop()
I 388-2 + 3Ep
(X) sLMl
(690) - -6)))
B3
g0 1 (x)
(cmp((X))
(g)p)()))2
((00)) 00
- (x) 27
< <38-2 2 + 12EF
+ 3 CG
(X)
3:0-2 + 12r² + 330 CC + +8)1/2 < 3000 + 4G +
Thus,
Ep [I(So(0..g:]] S4 94) S 4c,
Since
H,, - (1) < (2 +4)
we have
oHo (0.. 9: 7) (o $ (00 Similarly, we show that
Ep [Il( 2) (oo < (6
It follows that
K1 = 20 +c0 : and k = 61 +2) (67)
(e) For s 1. we have
p (X)
Dy: X)]g go]
(gropp x))² (X) (X) 96 pr0 (X))
(addde (X) 96 din (X) (X) 96 (x)).
gXro((X)
44

---

Similarly, for s = 0,
- 9o
prop (X)
Dg (1) gol
(X) 96 (X)) (x - (
(1 gropp x))3
gump(X) (X) - 50000
(g (X) - go (X)).
gerop (X)
For any 9.9 (90) such that tg (1 t) for some t E (0, 1), we have
(g 9)10 0..g- - gol
= - Ex (D (0: () ((o(X)) - - (0: X X)po [))[g - 90l (X, 0 0.)]
P po)
--E
(gmop)) (g 96 [g (g ) (X, 0 0.)
(1 90
prop
Rp
groop) ) (g(0)
gg (0) m - mim ) (X)(X,0 0+)
(gerop
00
(1 )
po)
Ey
(n (X) 0 -0.)
gorop
(g
go prop) pp
(0 - (X)) 0.)
+ Ep
grrop
Note that by (61),
Ep
0 (1
(gmmp) ) (g(h) - "6 > mr _00 (X) 0.)
pa)
gerop
(gre) 96 (x) (oroop
06 p
S Ep
Cx 10 0+112
gorop (X)
gorop(X)) (X)
grop((X)
S co Cxrl10 01112119 - -oolls
In addition.
(grop
90 pmp))
(1
po) (g 96 (x)( 0.)
Ep
grrop
< Ep
rgo
go
poup)
(g 96 (x) Cx110 0.112 - Cxr 0.112llg gollg.
gruu
Thus, is easy to show that
[DDDeL(0..9)0 0.0g
2(( -099- goll s 1)Cxr[10 1.112 go llg.
which implies
a = 2(c 1)Cxr.
(68)
In addition, L(0,9) is Neyman orthogonal at (0+,9o) since
( 0,, gol = 0.
Now we compute the the higher-order derivative. For 1, we have
20p (X)
(T; X1g 90.9 gu]
(x)) 66 (X)) (OP) - 2 (X)
grpp (X))²
(gpop(X))²
+ (g)mp(X))2
(g) - - (X))
prop (X) prop (X)).
45

---

Similarly, for s = 0,
1 - 90 prop (X)
1 (g: X) 90.99 900 -2 (1 gorop X
0000 (X) -666 (x)) (x (X) 16 (X))²
+ 2 1 - 90 (X)
getup (x))2 69 /00 (X) -6 (x)) "0 (X) 90nd (X)).
Then for any 0 θ and 9.9 E 9r (go) such that و tg + t)go for some t (0,1),
DOL 9) 0 0n.g 9 go. 9 gol
-Ep [ (5: X) (1 (x() - ( X ())o(())) - yo. 9 - gol (X, 0 0.)l
9 prop
(gerop/ X )3 (g 1 (X) - 960 (x)) Prop (X) (x)) 0.)
2Epp
2Ep prop (X)
grop (0 (X) 96 (1 - -i (X)) - 0.))
S (grop (X)) )}3 (X) 96 (g (X) 9.... (X)) (X, 0 0.))
2Ep
groop x))3 (X) 96 (X - 90 ". (X)) 0 - -0.1
S (X)
2Ep
By (61), we have
Ep
(grnop (X))3 (X) (X)) (X) (X)) - 0+)
90
prop (X)
(gprrop (X))2 2 got) (X) 2i
(y (
(odd Jaanie X) 90 (x)
Ep
Badd (X)
Cx Cx110 0-112
(X))²
grapp (X)
$ % Cxrll 0. 1112119 soll..
In addition,
poup (X)
Ep
96 (g)))p()))2
(g (X) - 96 (Xo))) - ( 0 -0.) --0)
(gprop/ x))2 (X) - 06¹d (X) dooad (X) - 0ro0 (X)
s E2
Cx110 -0.12
(X))
(X)
(X)
<. 2 Cx 110 0. |12l|1 90ll..
Together we have
D.D. 0..9 go.9 g gool s 4c0 2xx(1 + r)1 0- 0-12211 goll.:
which implies
== 2cx2 +r)
(69)
46

---

C Convergence Proofs for Stochastic Gradient
This section is dedicated to demonstrate the SGD convergence in Thm. from Sec. of the main text using Asm. and Asm. 4. We first give an overview of the problem settings and the expected results with the proof outline in Appx. C.I. We then provide all the technical lemmas needed for Thm. in Appx. C.2, and finally prove our first main result in Appx. C.3.
C.1 Overview
In this section, demonstrate the convergence of SGD for risk minimization problem with nui- sance:
0, arg min L(6,go). dee
where gu E G is the true nuisance, L(0, g) = Ez-p [e(0, g: Z)}, and is prespecified loss function. We consider the stochastic gradient method for learning 9, when go is unknown but estimate accessible. Define D, = (ZI..... Zn), sampled from the product measure P". Recall the SGD g(n) defined as
g(a) g(n-1) So (f(m-)1, Zn..
(70)
Throughout the section, take the following notations for simplicity:
g(m) ((()) Oz:
(71)
S(n) -S((((-1), gg: Zn),
(72)
((m) = =S(") (o ,g)
(73)
where So (0, gi 2) = VoL(O, g; 2) is the gradient and Sz g) Bz-F [Sn 9; 2)] is the population gradient. We are interested in the mean squared error using an estimated nuisance g. and our results show that for non-Neyman orthogonal loss L, the error g(m) satisfies
ED. [[1(()) S (1 -1-22
11:00 2 + llø - 90 + n.
(74)
where the nuisance estimator would lead to a bias of order Ol1 goll3) for the SGD conver- gence. If T, is Neyman orthogonal, this bias introduced by the nuisance estimation would be further removed, resulting in the following convergence
Epacer (1 | $ (1 (0-1"") " (1 112 و|ا
1 + n
(75)
Proof Outline. The proofs for both results (74) and (75) proceed through the following four steps:
1. Upper bound the excess risk T.(0(n), T( in terms of the SGD improvement.
2. Lower bound L(0()) .9) L(O., 9) using strong convexity and Neyman orthogonality.
3. Derive a recursive formula of Ep,,< [x) ) [[2] from these bounds.
4. Perform the recursion and obtain the final result.
Follow these steps above, we provide technical lemma in Appx. C.2, and then prove our first main result Thm. in Appx. C.3.
C.2 Technical Lemma
Lemma 10 (One-step improvement for SGD), Suppose that Asm. holds. If < 1/M, g(m) E O, and g E Gr it holds that
n7
2m (0(m) 9) - L(O., g)) s (1 - un) 18 118 22((e(())
(7(6(1))81n-11) + 1 Mn
47

---

1 Proof. We first define the "/' -strongly convex function fn as
fn (u) (5(m), u - g(n + 2n
1 l|ue
11
(76)
Note that
arg mig fn (u) = arg min||u 100(0((0))))) - - 213 wgRd
Rd
which implies that g(m) = f(n-1) - m)(((m) (m) is the global minimizer of (76) and Vofn(0(m) = 0. Then
In (0.) 2 Sa(((m) + (VoSn(0(<)), -o(1), +
1
18 1
21)
= = + 2n ||0(n)
1
(77)
Since L (..9) is p-strongly convex and fn (0.) = (5(m)) 18(x-1) + (27) -1 '110~'13 we have that
L(0..9)= 2 L(0(x-1), 1) .)) + (0(n-11)) 9), -6(n-1) + 2 (18(n11)
12
= -I(0(n-1), ,0) + (5(()) (n( + (oomm, (0m)),(mmm3 s((
+
|
pgin 1)
2
= =((0(=-1), + fm (0.) - (wfm), 8(m-1)) (0fm),(mm11)) + (5-
110
| 1)
12
2n/
Together with (77), it follows that
L(0(m-1),0) ,9) + fn (((n)) (I((r,)) - -(u(n) ,(n
+
((1)
1
||8tn
1
||8(n)
(78)
22
21j
Since L (+.9) is M-smooth and fn (D(m)) (S(()) Obm) - ((n-1)) + -1)0)=1((00)) have that
0(n-1) we
1|3
I((((), 9) x T((((-1).0) + (S(0(m-1) 1) ,)), 0(n) - 1(n-1)) + M (10(m) - -0(=--))))))- 111-11113
2
= L(((n-1),0) + (s(m), g(n) -((n-111 + M |1 g - (aru)) g(x) g(n-1))
2
= =((o .0) + (n(((()) +
[M
1
|10(m) - 01 - (m (pm)) _ 0)n-1))
2
2n
By (78), it follows that
L(O(m),)) .9) S (().,)) - (n 8(
2n - = (18mm11) 1) 112 2n
1
|| 8(m) 12
+
+(1))
(M 1
+
110m))
O0
11 - (m) 0(m) Oin- 1)
2
211
which implies that
L(B(") .9) L(0..9) 5
1110
1
|18(m) 113 -(0("), (0("))8() 80(--1))
21
2
2n
M
+
(10(m)
gin-1113 (olm), g(m)) - g(n-1)).
(79)
21
For any w > 0, by Cauchy-Schward inequality and Young's inequality, we have
-(olm), glm)) - g(n--1)- < w " (|o060) + [|0((x)) g(n 13 ||.
2
2w
48

---

Take this into (79) and we have
L(B(m)0) 9) [(0,,0)
-
1 1
|
1
110mn)13
(ulm), ,5tn-1),
27
2
2n
M
+
+
|10(m)
p(n-1)
1)
2
21
2w
When 17 $ 1/M, set z
1
+
0,
i...
set
1/(11
M). It follows that
2n
2n
I(O(m),0) .)) - I((+. S
1
118(-~1112
1
|1800011 - (00")) (5(n-1)
21
2
2m
+ 2(1 Mn)
π
|
We complete the proof by multiplying both sides of the inequality by 2ny.
Lemma 11. Suppose that Asm. 3 holds. If < 1/M, g(x) O and 9 Gr(g))) it holds that
|| 12 (1 - (u7) 118mn11) aiv وا goll + (o((), 5(a-1))) + 1/ 1 11
Mn
Proof. Under Asm. 3,
2) = (0.. + ((.. و gol
= =D,DoL(0,,0) .9 ]o] 2 -ai 11 llallo golle
(80)
Since L(: is p-strongly convex.
T(00)) 9) - I(O..)) 2 (S(0.. (), ((m))) + " - 11 1
= -DL 901(m)) + # ス
(m) 12
By (80), it follows that
L(g("), 9) L(0..0) -011166))12110 gulls + 11 11000012.
Together with Lemma 10, we have
2n a2 18 ||21 golls + " 118()113) 5(1 ((11m))(1 188 12
- 11 - w0 8( 80m-11) + 172110(m) 12
Mn
Rearranging it, we have
(1 + (m)] 1 <(1 - un)ll
golle - 27(o(()) 27(((())g(mn1)) + 172 721100000133 ||21ا|
(81)
Mn
By Young's 's inequality,
2na (116 1211 - galls s nan
L a1
11 + و 9n 12
#
Take this into (81) and we have
5ln 2,((6(),8(mm11)) + 17² 1100600 1|3
| 1| = (1 - (m)) 1(n + - - gull -
1 Mn
49

---

Corollary 12. Suppose that Asm. 3 holds. 1f < 1/M, 6(m) E and á E Gr((9)), it holds that
Ezan [108001]] s (11 (1- pm
K177²
aîn
K2n2
111 + 1 1-M1) 118(n=11
11 soll3 + 1 Mnj
Proof. Note that Ez,,> [(o(()) o((n))])] = 0. By Lem. 11, we have
Ez, ~P [10c))1]] 51 - (an)) (| 11 + ajn 1 goll
1/2 Mn
Ez ~p ||((m)
Under Asm. 3, BZ [||p6t))]]] S Ki + ki || and it follows that
Bz ~P [1080013] S <(1 (1- lm + 1 1--M)
n1
11
ain r 11 9oll3 + 1 1- Mnj
Knn²
Mn
+
Lemma 13. Suppose that Asm. 3 and Asm. 4 hold. If < 1/M, 0(m) e,, and à E Gr(go), it holds
that
fi 110 gull - (n(()()) 20(n11))5tn11) 17 (0) 11
|10(m0 1 (11)) (1) 12+
4u
Mn
Proof.
Under Asm. 3 and Asm. 4,
DoL(O..0))00w)) = (0.,(00,00)(0'41
Do (, (0.) 99-90)
+ DOL(0,
+ 1
9 9 9 - -9ul
1 - D2 10. (p(m) 9 - 9 9 - gol 2
31 || - -0ol3-
=
2
The rest of the proof is similar to Lem. 11.
Corollary 14. Suppose that Asm. 3 and Asm. 4 hold. If n < 1/M, g(m) O, and E (r
holds that
Eza~P [1861011]
<< <(1- pm
R17)²
1,
8y 4p
وا goll + 1- Mn
Knn2²
1 1-Mn)
Mn
Proof.
The proof is similar to Cor. 12 using Lem. 13.
C.3 Proof of Theorem
Proof. Let c(n) = 1 kin/(1 Mn). When 17 < pM ki), we have
(1- ---1- Mn n n= 10=1-((1)) <1
K177
um +
Mn
Under Asm. 3 and by Cor. 12, we have that
[18(m) 2
RRz ~P [1Sta]] [3]
E EDa_INP--1
23 lgg
Kin2
<(1 c(n))) E EDI-INAn-
[18
1 + 1- Mn
9oll
< (1 - <(n)n)) ED.-
110
ofn 11 9oll3 + (1 (1+((1(())m) Knn²
+ (1 + (1 - (1-c(m)))
P
Mn
50

---

By recursion. it follows that
ofn
[18t1011]
< ((1-(()))*
110(0)
1
+
1
soll
Σ ==0
(1 c())))
P
Kin2²
+
Σ
(1 (1-c(m)m)
Mn
i=0
at
Kin
51 c(n)n)) 11800) 1/2 pc(n)
|1 -9oll + c(n) - Mn)
nn S p/2(Mpp + k1), we have p/2 S d()) S μ. Thus,
ED [1 s 5 2) 11:0012 + 2a μr²
4K1n
||
9oll3 +
In addition, if Asm. 4 holds, then by Cor. 14 and using identical proof as above, it follows that for Neyman orthogonal risk L.
ED [1060013] $ (1-12) 18800 11 +
37
1 20llž + 4K17
2n
51

---

D
Orthogonalization with respect to Nuisance
In this section, we establish our orthogonalization method for the possibly infiniteddimensional nui- sance introduced in Sec. of the main text. We demonstrate how construct the orthogonalizing operator in Appx. D.1, and provide all the technical lemmas in Appx. D.2.
D.1 Orthogonalization via Riesz Representation
We consider G = (G ())) as possibly infiniteddimensional Hilbert space, Recall the derivative operator D defined as for any h E G.
Dge(0, 9: mM f00,9 + th; 2) I==0
at
This derivative operator is also known as the Gateaux derivative. We posit the usual assumption as Jordan et al. [2022] that the derivative operator DyE(0, gi 2) is linear and continuous G for any (0, 2) E θ x Gr (9o) x Z. We also assume regularity conditions such that D,D, g:2) is continuous and DoL(0, 9; =) DoD,e(0, z) at any (.)...
Since Dyf(0. g; 2) is linear and continuous, by the Riesz representation theorem, there uniquely exists some v,L(O, gi 2) E 9 such that for any g g.
Dge(0, 9i =)]g]
(V (V,e(0, ;),
(82)
Lem. 16 shows that the operator Dy (0 9o) is linear and continuous. By Riesz representation theorem, we can define Hog = (H)g) H Gd such that for all E G.
Sy ( (0.. 90) [g] (mag) 9) for any j I,...,
(83)
The Hessian operator gg 9 + G is defined as for any 91. E g,
DēL lo 92] 9g91, 92)g-
(84)
We will show in Lem. 17 that Hgg gg uniquely exists and is an self-adjoint and bounded linear operator when LO,, 90) is bounded and symmetric bilinear. Assuming that Hg is invertible, we define the orthogonalizing operator as
To : G Rd.
[Tog]; (Fr ( o)
(85)
We now construct the Neyman orthogonalized (NO) gradient oracle
Sno gi Sp(0, g: =) To (0
In addition, To V (5(0gg5)) can be written the derivative in the sense that for each j 1,...,, .d.
To v g ((,g)) = (H(6 H V 2))
=(H gg H () v.l(0.g: g: 2))
That is, the NO gradient oracle can be easily obtain by
Smo gi 2) = So g: 2) - ((, HHr Hog]-
(86)
The following Lemma shows that (m. g; 2) is Neyman orthogonal at (0.. Jo). Lemma 15. (e. gi 2) is Neyman orthogonal score at (fo.go).
Proof.
Since Sa (0. g3 2) = So(0, (0)0==))>((00000 (y
H 49 Hog) for any E G.
Ep [DySno (9o. gu: [)[h]]
(00, 90) hi - (0, go) [H yo Heg h]
(Hag) h)g (11 Hog h)
(oog h)g
(ogg h)g = 0,
52

---

which implies that (0, is Neyman orthogonal at (o).
D.2
Technical Lemma
Lemma 16. (050(0,g32) G Hd and D Dg + E2 are linear and continuous in G.
Proof. The continuity of D0 gi and Dj (0,900,9) follows from the continuity of
D, Dal(O, gi 2). It suffices to prove that Sa (0, g; 2) is linear. For all u E R h1, h2 E G.
(u, D, g; 2) + hel)
Dg (u, (0, g3 =) + h2] D,Doe(0,,) gi k) h2]
g0
(Va (D::((00;;:)]]++++))))
(Vo (D,,((0.g;;))))) g; =)]12) u)
Do01:((0.:::),,,,,++DDooooo/ g; g;=) =)2, u)
D,DDe(0,:::)(luh)+) ( h2,
(u, [,, ( 222)?>
which implies that
g; + h2]
Lemma 17. Suppose that D2 g0) G (+4G++ R is bounded and symmetric bilinear form. Then Hgg 9 + G uniquely exists and self-adjoint, bounded, and linear.
Proof. Given 01.92 G, since DT,, (9)0))9))111)))) is bounded linear map from G R. by Riesz representation theorem, for any 92 E G, there uniquely exists some Th1 E G such that
LO, 9o)l91. g2l = =(T9.. 92)
Thus, we define the operator T : 9 + G. Note that D2 is bilinear. For any a E R. and any 9r, P1.92 E G, we have
(T(ag1 d'g') d'gi),92)g D ga) a'g'
aD2 9) 99 921 a L0,, 9o) 9zl a(T (. 92)g + o' 92)) (aTT g1 + a
which implies T is linear operator. To show T bounded, suppose that the norm of the bilinear form (2.( 90) is bounded by B. Thus, for T91 + #0,
Tgi
[T (T'i,
ITi
(T91,92) I|salle=1
sup
sup
(0L((0..0))9n g2]l < Bllgille.
which implies T is bounded. Note that (O. ;o) is symmetric, we have T being self-adjoint since
(Tg1,92)g (0. 90),0, 92] (0, (0) 91] (T'2, g1) (g1, T992a. Finally, we show that T is unique. there exists some T G + 9 such that for any 9n g2 E G.
g2)g L0, go) 92] (T' gl 92)g.
which implies
( - 92) = Vgi, 92 E G. That is, T = T". We finish the proof by letting Hg9 T.
53

---

E Convergence Proofs for Orthogonalized Stochastic Gradient
This section is dedicated to demonstrate the OSGD convergence in Thm. of the main text. In Appx. E.I, we give an overview the OSGD settings, the additional assumptions, and the expected results with the proof outline. We then provide all the technical lemmas in Appx. E.2, and finally prove Thm. 3 in Appx. E.3.
E.1 Overview
Following the same problem settings in Appx. C, consider the orthogonalized SGD (OSGD) using the estimated NO score Sno oracle defined
Smo g: 2) = (o g; TV g((,gg;;)))
(87)
where I is an estimator for the orthogonalizing operator defined in (85). Specifically, we consider all continuous linear I 9 + Fd for estimating the orthogonalizing operator To. By Riesz repre- sentation theorem, there exists some 4(01 G for j I,..., d, such that
[ gg
()) g)g for all E.
For the orthogonalizing operator To, we define (1) = 9g 0g . = 1,..., d, such that
[ogli (70 (1) ,90g for all EG
We focus on the OSGD defined below:
((m) ((n-1) So g Z,), 0(0) E e.
(88)
Throughout the section, we take the following notations for simplicity:
s(m) = g(v) 0.:
(89)
na
((n) Sno(0(n 9j: 7nn)
(90)
u S(n) (B((11111) .9).
(91)
Let V ((0,9) EV 2)] and (0, g) = Ez.r((mm(0,,00 Z)). We need the following assumptiios establish the convergence result the OSGD.
Assumption 6. The following conditions hold:
(a) First-order optimality: Sno(O.. 0 and (f V 0.
(b) Smoothness and strong convexity: There exists some Mnos Mmo > such that for all 0 e θ and Gr (go), V g)l2) S Mno and
Amin Sm (0.g) VoSno(O,g) 2 2/
(c)
growth: There exist constants K2, K2 > 0 such that
Ez-z (DD 9: 2) g) D,,( 9) < (K₂ k2l10 - 1191))
for all 0 θ, G. (go), and G.
(d) Second-order smoothness: There exists a constant 0g > 0 such that
[2 g) 02l1 S 0z 02llgnllell9a vo DDD,L(0.,0 go) 0 0.]l < an |e 0lllallolle
O. g E Gr (go) (9,) E G,
vo, 0 E O. g.
(e) Higher-order smoothness: There exists constants B2 > O such that
||D (0.,))99 go. golll2 S 821lg - 9oll3 Vg. E G, (9o).
54

---

Asm. 6(a) is necessary for the convergence of the OSGD to 0.. When So is Neyman orthogonal
go). ( To is accessible and thus, S.. Sg. When Sg is non-orthogonal, Asm. 6(a) can be satisfied whenever (gI.(...00) = O, implying that (fx, 90) is local minimizer of T.00, g). Asm. 6(b) is related the Schur complement of the population Hessian. Thus, the hypothetical objective relating to Sno inherits its strong convexity from that of the population risk L w.t. (0,g) E x (gog) when G is finite-dimensional; see Boyd and Vandenberghe [2004]. Asm. 6(C) and (d) are exactly analogous to Asm. 3(d) and (e), while Asm. 6(e) is analogous Asm. 4.
With Asm. 6, aim to show that the error ole) satisfies
ED, ~
[11080
|اا
gol
l1 -ooll || rolliro + n. (92)
2
Proof Outline. The proof the (92) follows the following four steps:
1. Upper bound ||. 17 V Vo g)ll w.E.. the operator estimation error ||[ Toll
2. Upper bound || (0.. 9) ll2 using Neyman orthogonality and the first order optimality.
3. Derive a recursive formula of Ep,.< pm [1 [ from these bounds.
4. Perform the recursion and obtain the final result.
Follow these steps above, we provide technical lemma Appx. E.2, and then prove our second main result Thm. 3 in Appx. E.3.
Alternatively, the intuition of step 1 also suggests that we should focus on I that lies in the neigh- borhood of Io such that ||A- rollllo Fro < R for small R >>>>> 0. Then, instead of assuming Asm. 6(b), can directly assume that for all 0 E θ and g G. (go), I (0, 2 I Mn and
Amin (v (0,g) + V S (0, g) )) 2 2pno
With this assumption, one can still show the same OSGD convergence rate by the identical proof while the constraint of the learning rate 17 will be simplified.
E.2
Technical Lemma
Lemma 18. Given yj > O. For any w > 0 and u, u E Rd
||u mull s (1 + m10)l (172 + mo I|lll.
Proof. By definition, ||u + gell ||ul2 + 1/1111112 2n/24, u) S ||u12 + 1/11: 2n/ 2n||u||2||ve ||/2||1/|2-
By Young's inequality, for any O,
2||u||2||u112 S w||u|l + -|011.
Thus,
|/u + qull < (1 + mo)l + (17² + mw n ||l1||
Lemma 19. Suppose that Asm. 6 holds. For all E θ and g E Gr (gu).
|| ( (0, < 1 2n( ai || Fro)) 2n (M + 2a2 Tol ll.l2.0))
Proof. Note that
(I (T-IVO (0. (0,9))(T -1 "7VoSm((0.)))
I (V03m (0, + VoSn (0.)) (0) + + V VoS (0))
55

---

Since VoSno(O,g) = VoSno(0,0) - -o(f)))-ooo--o we have
(0 V (..
VoS + voS (8, - -
-
2( |V Vv
We now bound - [T((~_ToVV_(00000) For each j = -.....,,
d. for any 0 E Rd.
vo((f-rr)0,,400000 0.) (o(() ()) V,L(0, 0.1
70
(0, - 8.1 Sa 1001))0)~~00ll1 12112.
[D.D,
Thus,
IVo(( - -o)0, 0.)112 s Foll 0. 112
which implies that Vo -oo anl -ullero and
V VoSno 6,, + VoS, 2 2(1oo - -olloo))
Additionally, we have
|| (1
< |V (0,9)11
V.. (0, (TTT((())VV
$ 2M no + -2a
To lolloo
In conclusion, we have (T- T- V
(0,
2n(nuo an j Toll (M + 22a - -rollino)
Lemma 20. Suppose that Asm. holds. When 9 E Gr (go).
82 وg@ lol + 20 Toll |10 1
S| (f., (0.,0)13 <
2
Proof. Note that
S (0., .))1 = (1. -(-T))
s Sno (..,
9)
(0. +2 Σ
(V (O..,)))),50 7() - (331
20.50o(0...0) +2 Σ (D,L(O., -
- 1
Since (f., go) and Sno is Neyman orthogonal (0.. go). we have for some ğ E Gr (9v).
1 (n. Sno (0. go) + Smo go)lo gol 2 D2 (0., 9)(6 gol
1 D3 Sm. 16
ggll-
2
56

---

which implies
2 -10 90 l
Similarly, since (FG) - V 9n) = 0. we have for some g' E 9r (go),
(,L(0..0)(0)) 7601 D2L(0,,
- - ,3 -600
= =((6) [u) (0) (2 9311 -601
g3)1 -00
which implies
(0,,0000) - (1) ,9 - gol S s2214( - ~700
(5) lss Iø golle-
In conclusion,
82
(0.. S
2 واا --ool + 202llT - F.. ||9 - -
Lemma 21. Suppose that Asm. 3 and Asm. 6 holds. Then
|10/6 Ez,n?
[13] s 2(K1 + K2ll 2(x1 + K2 1111 '12.
Proof. Note that (n) (0(n-11 1), 99; Zn) (0(n-111), ,g)
Ez 1000''13 13] S 2IE ~P (1(0)) Zn) (g 9
+ 2EZznF 2n l1l'Vv(((nn11 Zn) iv g (((in-))) ,0)1
By Asm. 3,
EzanP (B(n ((:(n-1),;:2.) ((((m-1),0)133 s K, + 111
Since
E2, ~P |ITV (itvg((((-1)) !.) rv. gv 11)1
(Dge(0(n-1) 1) ,0; 20) DD Dg 10000))
Exan
<
K2 + 0- 0013)1150013 =(K² + +2210-1 - 0g [|]
j=1
In conclusion,
EN,n7
||0
S 2(K1 + (2 + 2(x1 + K2 |2 -1..
E.3
Proof of Theorem 3
Proof. Since ((x) ((n-1) 1) - 11500 by Taylor's theorem we have that for some F(n 1)
((n)
g(n) = 8(n-1) - (0(n-)) 9) (0. (0.. 9)) (0.. - 170
= (I - o (1 _0)))(=11) n7S (0,. .) - (7((1))
(0..
57

---

[n)] Uno
Note that En ~P
0.
Take the expectation of the squared norm of both sides w.t. Zn and
we have
Ez ~P
|10%0 |I(I (0 10) 17
11 ~P
|1
By Lem.
18, Lem. 19, and Lem. 20, for any 0.
[I(1 O0 (0)))((m03) 17 (0., 0)
$ (1 (1+ m1+mw)lle )l( v (0(n-1), ,)) 111 + (1) + mpw ) (0.. 9)1
$ (1 + nw) (1- (1-21( 2m -1 | - -ollfto + 21/² ( + 2a
ro ( |
12
+ (1)² + k
و goll 2a L'lll 10. واا -90ll)
Set Mao- For 7) S 2/Pmo: Pmo: have
(1 + mpw) (1 21)(100 01 || TollFvo) + 2 20 || Fool)
- (Nmo - 201 |1 rollmr))1) - 2(1200
M 01 r )
+ 2(1 + mymmm) ) (M 2 + 2a |1 1' )'
S (Mno 20, || [ollFro)
(oMe 2p:20 + 2 - + 12o Tolliro 1/²
b(n)),,
where
b(π) = Uao
20 - Tollero (6MM) - 2pt + 2/ / Tollero + 12a | To rullir..
By Lem. 21,
Ez,aB |1:000 ||
s 2 + K2 (2))) + 2(k1 + K2
follows that
Ex, P 1 < (1-ble (1-b(1)) + 2(k) + K2 12.0 )1 1
3n
[2
واا
goll 20 r - Toll |اا
go1l + 2(K + K₂ 11.
Pno
2
Thus, it is clear that when ||T - L'olrro I Mmo/ (4a1) and the learning rate satisfies
2
Mmu 4ag f Tall
17 S min
Unoo 12M2 3/ / + 4(x1 + Ne (
Mmn - 4cr || TollFr
(93)
12M2 3p + 4(11 + N2 1
we have Pnon/2 2 2 and
b(n)) 2(m + +2 )n² < 1 Muo
When 7) satisfies (93), it follows that
Ez, [1](((())))
< (1 |mo?)
2 |18(1-11
11
3n
2 |19
gull 11
2a f -
Toll 1lğ --oll: 2(K, =f2
Pno
58

---

Finally, perform the same recursion in Appx. C.3 and we have
[1 [1:1 - (1 Mno!! a
1 + 4(Ki K22l (P:.o) )
ED, PM
Uuo
3 (32 0 90 lg + 4a P - Tollero -l - 90 113
+
1000
59

---

F
Detailed Discussion
This section provides details comparisons and remarks following the statements of the main sults in the main text, and details on the discussions summarized in Sec. 4 from the main text. In Appx. F.I, compare with errors the stochastic gradients. In Appx. F.2. we discuss different orthogonalization method in orthogonal statistical learning. In Appx. F.3, we discuss how interleave the target and nuisance estimation. In Appx. F.4, we describe the connection between our orthogonalized gradient to vari- ance reduction method the Monte Carlo estimation literature. In Appx. F.5, discuss the double robustness of SGD for rose-ns estimation.
results generic state-of-the-arr results biased SGD, that is SGD
F.1 Comparison to Biased SGD
There several ways to think about the bias induced by using imperfect estimate opposed to the true nuisance 9u E g. For the sake of discussion, we will define L(::9)) and L(, g) as the "original objective" and "shifted objective", respectively. Accordingly, will call 0, the "original minimizer" and denote by
0, arg min L) dE
(94)
the "shifted minimizer". The bias can be measured in terms of (i) the error |10. - 0- -0. between the original and shifted minimizers, (ii) the uniform error supa [(, (o) L(0, g) between the original and shifted objectives, and (iii) some summary of the gradient bias
Bz,-P ((((t-1), 9
V (oT .9),
(95)
of the oracle S' (a vector-valued quantity) for step t = I,..., n of the algorithm. Whether one appeals (i) or (ii) depends on whether the convergence guarantees are stated in terms of iterate convergence or function value convergence; because we analyze convergence of iterates, our discus- sion will cover (i) and (iii).
On (i), one applies the decomposition
[10(m) 0.113 s 21(((m) - 0. + 12
and plugs an analysis of unbiased SGD from the current literature for the ||0(n) - 0.11 term. The purpose of this substitution is to check how our theoretical results align with the known results on unbiased SGD.
Bach and Moulines [2011, Thm. 1] show that for constant learning rate 77 OH//M²) the iterate g(n) satisfies
K1n -0
ED, pm [l])(n)
0. 11 <
exp
|1000)
+ 110 0.1
(96)
/
Cutler et al. [2023, Thm. 3] demonstrate that with the learning rate r O(1/M), the iterates would satisfy the following bound:
Ep. Ep.-e= [I]@(n) -0.1131 < (1
2
[|0(0) - -0.112
K17
|10. -0_1l3
(97)
In addition, Cutler et al. [2023, Thm. 6] provide the high probability bound of g(r) that for 1 (L/M)), with probability at least 1 - d,
Kin [| 0.12 S (1 2 """"" (1 - 0211
log (5) + 110 - 0.112
(98)
#
All of these bounds essentially agree, as we may apply (1 - (m/2) S exp(-uun 2)) In comparison to our Thm. 1, our bias term is stated directly in terms of the nuisance eтror || goll3- This
can be viewed as a refinement the less transparent bias measurement |0, 0 Moreover, although (96)-198) are of the same order results in Thm. 1 when the true nuisance go is
60

---

available, all of the three bounds above require = 0 in Asm. 3(d). In this case, provide (97) and (98) use a learning rate of the order (1/M) (whereas the learning rate of (96) encounters an additional condition number M/p). Our learning rate recovers O(1 ((1/M) when K1 = 0, and adapts via the setting 7 = Ouu/(Mp + k1)) when K1 > O. Finally, the high probability bound (98) requires stronger assumption in the sense that Sg 2) (0, g) is parameter / for all 0 e and g E G, (go).
with uniform
Returning to the bias in the stochastic gradient oracle (95), this case is handled quite generally in Demidovich et al. [2023]. Their "ABC assumption" considers constants A, C, 2 such that the inequalities
(L go), Ez-r [So(0. 9: 2))) 2 b) (O, (0)(()))) go)l +
(99)
EF Sa 9; 2)1 - 2A (L(0, 90) - (0)) +00 +C
(100)
A+ M +1 2b) < /
(101)
hold for all 0 Rd (where the expectations conditional any randomness in g).² The bias is really captured in the first of the three inequalities, whereas the third inequality places conditions on the parameters of the problem that are not in the hands of the algorithm user. By strong convexity, our Asm. 3(d) satisfies (100) with A = kI/M, B = O, C,C = K, The resulting convergence guarantee [Demidovich al., 2023, Thm. 5] gives
ED. -P [1]0(n) - 1 E (1
(10(0) 0-11+
K1 +
2
f
11a
for a learning rate set as
2 μ
2/K1/H + ML 26))
n S min
We would like check how our thcoretical results compare with the above application of generic results on biased SGD. In our setting, the condition (101) reads K1/μ + M (1 26) < 2//2. We assume neither this nor (99), and in our Thm. 1, replace the ع term with a bias term that depends directly on the nuisance error |اا gollă. either in the nuisance sensitive regime, or in the nuisance insensitive regime.
F.2 Discussion of Full-sample Orthogonal Statistical Learning and Related Methods
Comparison of Orthogonalizing Operators. Constructing orthogonal losses scores has been widely studied in semiparametric inference, hypothesis testing, and machine learning. In semipara- metric statisties, such constructions often rely the efficient influence function, which character- izes the asymptotic efficient estimation bound; see Bickel et al. [1993, Ch. 3], Tsiatis [2006, Ch. 4], Van der Vaart [2000, Ch. 25]. Luedtke and Chung [2024]. In hypothesis testing, orthogonal scores were used by Neyman [1959, 1979] and Ferguson [2014] to guarantee the local unbiasedness of specific tests based on the likelihood with fintt-ddieeniionll nuisance. In machine learning, the con- struction of orthogonal scores was latter extended to non-likee likelihood losses in Wooldridge [1991] 1] and Liu et al. [2022], which aligns with our construction limited to the finite- -inee-iimnsiionl nuisance case. Recent work of orthogonalization in machine learning with Siinite-dimension nuisance relies on the approach named concentrating-onn though all these constructions produce Neyman orthogonal losses or scores, none of them consider the stochastic design. Our work is complementary to these, providing non-asymptotic guarantees for stochastic optimization.
[Newey. 1994, Chernozhukov et al., 2018a), However, al-
Although these constructions might lead different orthogonal scores, they can be the same at both the target and the true nuisance. Specifically, when l is the negative log-likelihood and g = R* the concentrating-out approach and our NO gradient oracle S. both produce the efficient score in the semiparametric theory literature; see Newey [1994, Page 1359], Van der Vaart [2000, Ch. 25.4], and Tsiatis [2006, Def. 8). This identity can happen for infinite-dime difintt-dimmnsionall nuisances as well. As
'The third inequality is actually A + M (B + 1- 26) < but the constant (1/2) to make the resulting for the stronger inequality.
bound more comparable, in that their bound can only improve
61

---

an example, consider the partial linear model from Appx. B.1.2, where the non-orthogonal loss is defined as
( x0,
Chernozhukov al. [2018s, Sec. 2.2.2] showed that the concentrating-one approach would produce
an orthogonal score under the concentrated-our nuisance (o(() = Z + Ep - (0,x) X) W] as
(PO,:)P((0)): Z) = (X - Ep W))(Y - E3 Y W] - (0., X Ee [X W))).
On the other hand, it is easy verify that Hgg I. Heg EPp X W]. and To V g;)
Dy g: H) Hogl, which implies that orthogonal gradient oracle So in (11) has the same form under the target 0, and true nuisance 9n (W)) E, YY (6.. X) W]:
Sno 90; Z) = -(X - Er [X WY)(Y Ep Y W| - (0.. X Ep X WT)).
Comparison with Debiased Machine Learning. In machine learning, debiasing typically refers to reducing the impact of model selection error on the parameter or quantity of interest. In partic- ular, mitigating the bias introduced by nuisance estimation is known as debiased machine learning (DML), which has been recently studied by der Laan et al. [2011]. Shi et al. [2019], Cher- nozhukov et al. [2024], van der Laan et al. [2025]. Some of the calculations used by DML estimators have been shown to be amenable computerization, simplifying their construction [Carone al., 2019, Ichimura and Newey, 2022, Luedtke, 2024]. Statistical learning methods that use debiasing also called orthogonal statistical learning (OSL) and have been studied in Foster and Syrgkanis [2023], Liu et al. [2022]. Zadik et al. [2018]. While the earlier studies focus on the empirical risk minimization, our paper provide stochastic approximation method in DML/OSL and establish the convergence rate of the debiased estimation.
To strengthen the debiasing effect, one possible approach is to consider the higher-order Neyman orthogonality. the loss function satisfies the k-th order orthogonality at (0., go). Zadik et al. [2018, Cor. 4] show that only need the nuisance estimator to converge at rate Op 2(-11 to have the nuisance effect in the order of O,(n which aligns with the nuisance insensitive rate in Thm. 1, where A = 1 and the nuisance effect || lullă Op(nn when |ا gulle (n-1///4, Similar improvements in sensitivity to nuisance estimation rates have been developed previously using higher-orde order influence functions [Pfanzagl, 1985, Robins al., 2008].
For range of problems, debiasing methods often lead to cross-produe estimations consisting of two nuisance estimators [Rotnitzky et al., 2021]. Such remainders frequently result from orthogo- nalization procedures used in missing data problems and causal inference problems [Robins et al., 1994, Robins and Rotnitzky, 1995, Laan and Robins, 2003]. Chernozhukov et al. [2024] consider cases where = (W,Y), goW) = Ep YY W]. and the target can be written as the averaged moment of the form
0, = [m(: W)].
where E|m(g: W)] W + Rd is continuous linear functional of g W - R. By Riesz representation theorem, there uniquely exists a Riesz representer (RR) RR E g such that [p(m((; W)] = Ex & (W)) Then the debiased score for estimating 0, is defined
S(0, g: Z) = mmg; W) + 90 (W)(Y - g(W))
The debiasing effect on the nuisance turns out depending on the cross-product || - -g || 11g gollg- Specifically, Chernozhukov et al. [2024, Asm. 4] requires the cross product be in the order On 1/2) construct Op(n consistent target estimator. This aligns with the cross-product ||@ - gollg | - To Fro in Thm. 3 where the same requirement needs to be satisfied to obtain a On 1/2) consistent estimator. However, Thm. 3 also has a second, non-cross con-cross-poodut remainder llg soll3 that will only be small 9 approximates go. making it so that our consistency guarantee is robust to misspecification of f' but not to misspecification of g.
62

---

F3 Discussion of Interleaving Target and Nuisance Estimation
To propose the interleaving approach, we consider the case where we learn the nuisance from the W-valued data W (U, V) from a probability measure Q We assume that the true nuisance go satisfies 9o : u + R and is the minimizer of the mean squared error over G:
9o arg min Te [(a(U)- - -v
geg
Suppose that we observe another data stream Wi...., Wm sampled i.i.d. from Q, and that S.
[W,,... 3 is independent of the parameter stream Dz. We define the sigma algebra Hm
(SSm), m 2 1 as the nuisance filtration and the sigma algebra Fm. = oSSm U ((mm-1)a+tl t S the parameter filtration. We assume that there are two stochastic processes g(m²), 2 adapted to Hmm and ((m.)), 0 S t S n adapted to Fm,t. to which we refer as the nuisance estimator and the parameter estimator, respectively. Intuitively, this means that the nuisance estimator gim) can be updated now instead of being the fixed ÿ. and the parameter estimator ((m,t) can be updated n times between every two nuisance updates. Specifically, we use SGD as the parameter estimator. We define g(0,m) g(0) θ and g(+00) g(i-1,m) for - S m, and produce the sequence ((1.1) ,...., ((f.)) using n steps of the SGD update (8) initialized at ((6.0)
S
Under Non-orthogonality. Consider the case that G is a reproducing kernel Hilbert space (RKHS) with kernel .). To obtain a sequence of nuisance estimator g(m) on Hm, one possible approach is to adopt the non-parametrii stochastic approximation. With the assumption that the eigenvalues (2))521 of covariance operator (o("(W,,)) & k((,,) decay polynomially at order j_a Dieuleveut and Bach [2016, Cor. 3] suggests that the non-parametric stochastic approximation (fm) satisfies for some C 0,
Em := Esm.. mm [| ]ulll]
S
Cm
(102)
This leads to the following nuisance sensitive rate for non- non-Neyman orthogonal losses.
Proposition 22. Suppose that gmm) satisfies (102) and that ((T)) Gr (go) and g(m.t) e θ almost surely for all m 2 1 and 0 < t S Under the same conditions to Thm. 1, it holds that
ED US LP (l
0-1131
(1-2)
p077
[0(0) 0.11
2
+ exp
ummmm
+ (m
2
(mm) 1).
4
In addition, when
it holds that
ED Pmam []]((mm)) 0. 1131 x (1
110(0)
0.
20-1
+ + 17.
2
The proof is provided Appx. F.6. Prop. 22 demonstrates that interleaving the target and nuisance estimation allows 17 n since the nuisance update iterations guarantees the shrinking of the term (1 2n/2) mn in this case. This is an improvement to Thm. where 77 should satisfy (171) -1 = o(1)
to ensure 2m/2)" shrinking to zero.
Under Orthogonalized SGD. To establish similar probability bound for OSGD, we assume that the orthogonalizing operator To can be written the minimizer of the following program:
To = arg min Eg [1 (0., 9o: Z) rV ((.,, 90: 1)
rESt
where G. the dual space of g. When d fixed, we assume that To can be estimated (coordinate- wisely) from the data stream S,, using the stochastic approximation of Dieuleveut and Bach [2016), which leads to sequence of operator estimators f(m), 1. For any 0, define the
63

---

following events for i = o....... m,
As(s) |0 goll l = Css Cs 20-1
and (s) { - Tolliro I Sss
We assume that for some constant c the nuisance estimator g( satisfies
Es. ( -goll
(s C%i
(103)
Additionally, we assume that (+)) decays in the same rate such that
[IF roll ( Bi (s(//o) & SC' 3n
(20-1l
Es.
(104)
With all the assumptions above, is possible to provide a convergence bound of |10(m..) - 0-11 in probability. The following proposition shows that estimations from Sm using OSGD contribute to nuisance insensitive rate of Om _ compared the nuisance sensitive rate O(m 2u in Prop. 22 for non-Neyman orthogonal losses.
Proposition Suppose that (g(m), m 2 1} satisfies (103), and that (f(m), m 2 1} satisfies
(104). Assume that flm,,t) E almost surely for all m 2 1 and 0 S t S For any s 2 define 5(s) = (ms) as (109). Under the same conditions to Thm. 1, with probability at least 1 5(s), it holds that
[10(m,m) -0.12255 (1-
110(0) 0.12
+ (m exeppp parprer
2/ 2u1 (((())+++))
In addition, when
= =0n))1=0(1)) with probability at least 1 11-86 8(5). it holds that
[ -0.11 S 8 -1 (1
10 11000) - 0 + - (0--111-111 (8-2/om= 20-1
+n + +1))
n)
2
We refer the reader to Appx. F.7 for the proof.
E4 Interpretation Control Variate for Variance Reduction
The regression equation (9), which provides an alternate characterization of the orthogonalized stochastic gradient oracle in the case of negative log-likel likelihoooo losses, yields an interesting con- nection to the Monte Carlo estimation literature. Variance reduction techniques (or "swindles") are used problems such as estimating the mean or variance of a statistic via Monte Carlo simulation. Consider probability space ($2, F. IP) with expectation denoted by E and an unknown vector-valued target E Rd, We have Ω + Rd, where we interpret ê as a (not necessarily unbiased) sample estimate of v. Several variance reduction techniques fall into the category of control variates [Gra- ham and Talay, 2013]. where random variable à Ω + I& with known expectations = E[a] and a matrix E d are used in the variance-reduced estimator
i = 8 I(á u))
A mean squared error decomposition yields the identity
E ū v = EE|é - 011 2E [[ū u)) + BIIi w)
E 2112 20 [ - u)) l(([T))ap)
indicating that for sufficiently "small" T, provides an improved estimator if 0 v and u have high (multiple) correlation. While in the Monte Carlo literature, ú and can be chosen optimally provided knowledge of the underlying tata-generating mechanism, as I can be interpreted as the regression function of on á u.4 Outside of Monte Carlo simulation, this procedure can be applied more widely if user chooses and based on intuition or limiting arguments.
"In the Monte Carlo settings, it often holds that d = k and I = af for some constant E R. Then, E(0 v. 1'A (ū- u)) can be replaced by Tr(Cov(O, ū)) and of [1']lop) can be replaced by o(a).
64

---

In the stochastic optimization setting, v represents the true gradient of the objective at particular parameter, while represents stochastic gradient estimate from an oracle. Variance reduction techniques have previously been applied in incremental setting, in which fixed data set of size provided initialization, and the algorithm may only make multiple passes through this same data set [Gower et al., 2020]. Note that this differs from our fully stochastic setting, in which we receive fresh sample Z, on each iterate ...... n. For negative log-likelihood losses, our orthogonalized oracle can be viewed in similar light to control variate-based variance reduction methods (although an diminia-dimeniional setting), To summarize, we have from (9) that
Sp(O.. 90)
i = So(O.,
(by Asm. 6)
û V Vye(0., 2) So Poi Z)
(0.,g(00..000 Z),
using the idcalized parameters. Using the approximations for 0 o 0., have
So) Sy(O,g)
= 0
(for 0 = 0.)
V vv((0.g:2)
û = So 7) - , ((..0
In fact, using the derivative of the log likelihood control variate procedure has been explored in the simulation literature early Johnstone and Velleman [1985], the correlation between statistic and the score function has tight connections to the Cramér-Rao lower variance bound and exponential families. We emphasize, however, that our method does not require the loss to be of negative log-likeliiee likellodd form nor any specific distributional knowledge to be applied.
F5
Discussion of Double Robustness
We now study the double robustness of SGD for dose-response estimation as discussed in Bonvini and Kennedy [2022]. Consider estimating the effect of the continuous treatment A A C I on the outcome E y c IR, which is defined as (Y(a) (known as the dose-response function, DRF) under the potential outcomes framework. Under standard assumptions, the DRF takes the form
/ E|Y A = f, = xx))(x),
(t) E B A = t, x]] =
where X E & C Rd is the measured confounders. Let Z = AY ~ P with density We take the following notations:
d du
x(a,z) .l(a,))) E A a, X w), p(a) P(U =) x) p(x)
p(u)
T(a x))
We can rewrite (o(t) equivalently as
(o( = = Bl X)Y A= t].
We also take the notations P(g(Z)) f (g(2)) n -n ((,).. |191l,.
(Z))) to denote the (T)) norm, and || La(P) = (P( (2)) to denote the (TP) norm. We now establish the procedure to estimate (t) as Algorithm 1 in Bonvini and Kennedy [2022]
with slightly modification to apply SGD:
Observe i.i.d. samples (7)mm for the nuisance estimation and i..d samples {7.) for the parameter estimation.
2. Estimate μ, w, and maa) P)((a,)) using ( with f., wn and si((a) (x(((a,))) respectively.
65

---

3. Construct the pseudo-outcome
= =0),,,AA,,)) - MA, + M(A +m(A).
We also define the true nuisance as
po(Z) - ((A,)))P(O). (
4. Define the loss function via a parametric function class Fe = (50 A Rd)
as
e(0, pp = = (10((a -((())
(105)
Define the stochastic gradient oracle as
Se (fe(a) - ((e)))aal
5. Solve the optimization problem
0, arg min E [E(0, PP: Z)]
8eB
using SGD with the stochastic gradient Sb ;; 2) by
() = g(n-1) - 1)500((n 1) :; 7 ( E E
(106)
As demonstrated in Bonvini and Kennedy [2022]. this procedure would yield doubly robust ERM estimator. In the following proposition, we claim that double robustness would be preserved the SGD estimator is adopted instead.
Proposition 24. Assume that E Vofo. (A)11) I CA. Suppose that Asm. 3 holds and g(0) ..... g(m) O almost surely for g(m) in (106). If p/2(Mμ + k1), the iterates of (106) satisfy
BD.~P=11O - -0.121 2
+ 1
2
+ ||
L || Alea(P)) + max - P) (Ā(a, X)H|²
aEA
Prop. 24 follows directly from the following two lemmas, Lem. 25 and Lem. 26, and the nui- sance sensitive rate in Thm. Whenever the empirical estimation max.e.1 (Pp, - IP) {A(a, } shrinks, Prop. 24 suggests that the g(x) would converge to the the target parameter when either a or is correctly specified.
Lemma 25. Assume that E [eVe..e. 1/2 < CA. Then for the loss defined in (105), we have
(.D. ()., 0., voll < CAlle pollo 0 0x112,
where || - polls = B(EE(()) 2o(() 1/211/2 B[E[)(Z) | A] 0o (1/)
Proof. Let f(() = E [+( | A = 1] - (t). Note that
DoDDL 2010 - 0 - PP] -E [({(()) (o(( (A), O.Y1
=-E =-IE [ [ ()) A) - E (2) Al)(Volo, (A),0 - 0.1
( (A),0 --.)]
--E (4)
66

---

Thus, by the assumption that [[ fe. (A)
1/2 CA..
()) - 0., - poll v E [F(A) P]
1/2
E [I [A))
1/2 110
0.
S CAB [((())]]
1/2
110 0, 0.12
Lemma 26. For the norm defined in Lem. 25, have
1 - - I 11w0 - u||
La(r) Ma
1/2
1/2 + max (TP - P) ())-
aEA
Proof. Lemma of Bonvini and Kennedy [2022] demonstrates that IF(() = || - di f| || - Alle + [IP,. - P) (ū(t,x)):
(107)
where ( A = t). By (107). we have
|| - splls 2 ||| - ساا|ااق: - a [PP, PP)- (i(L, X)
S ||0 - u| 1/2 L.20,) || p + max P) (x),,
aEA
E.6 Proof of Proposition 22
Proof. For simplicity, we use the notation Em,, to replace SS Let gn (1
2m/2)", glm,n) = ((m,n) - 0,, and g(0) = 5(0,n), Thus, by Thm. 1,
2a7
4K17
E |||
/ S qn F. 1. (l])(m.0))
2
Sm
+
1
1
2
4K17
- 1,m (m)) 1m)
Sm +
12
p
This recursive formula gives complete bound for ((m,a) as
2a
4K1
E [1]mmm..)
< qtth 1|
+
Ln
E.
+
In g
/
By (96), we assume that Em S Cm
20-1 2a
for some
> 0. Note that
wm7 2
S exp
2
For the second term, when on E (0, 1) we have
m
[m/2]
m
4n
5:
In
m
Σ
On
m-ig
[m/2]
+1
|n/
C
On
m-
+ C
m
0 m-
2
Cm
m/2
C
m
2a
2
1 qn
2
Cm
wmmli
C
111
20 1
exp
2
4
In
2
67

---

The last term is easy to bound since for In E (0, 1),
1
4n -
qn
i=0
We claim that for some constant 0,
(1-
Lnl
2 emin {
On =1
(108)
2
2
With (108), we have
umM +1)
Sc-l
1 qn
which implies that
E m (l 0 -000"1100) exp
(- 1arprent
mm
2a +1)
(1=
+1
mm
When (mm)-1= (1),, the bound above reduces to
Em, ()
T (|0(0)
+
2a-1
+ n2 + 11)
We will finish the proof by showing (108). The key step is to show 1 e 2 emin(a, 1) for all > 0 and some constant >> O.
Let f(x) e x/2, for x (0, 1) we have
0 for x E (0, 2og
f(x)) = 2
0 for log 2,
for (log 2, 1).
Thus, f(x) 2 flog 2) (1 log 2)/2 > for æ E (0, 1), which implies that - E > x/2 for 1). Note that 1 - 2 e- for 2 1. Let min(2 e11). Then have 1 2 c min( 1).
It follows that
On = exp (nn log 1 (1mpm/2) )) cmin n 1 un/2 . 1
Since
> log for all x > 0, we have
log (1 22/2) < 1 un/2 = -
which implics that
2 pmm
n log
1 un/2
Thus, we complete the proof.
68

---

E.7
Proof of Proposition 23
Given O, we define A; (s(/ and B; (:(ss/c) for 0,..., ; m for simplicity. First, since e 2 1, by (103) and Markov inequality, for i = .,.... m,
Proof.
P [A: A Ao] = P [10()) 9o l 2 Cs 1//1 2a-1
AA-
1 - P [10(0) go 1 2 CO
La Ele
Ai- Ao
Es... [llg(t) goll A Ai]
C² (20 1)c
We assume that P [Ao] = P [Bo] 1, and we have
P PlAm A Ai
A1, Aul = P Am Am- A1l [A1 | AAo [Ao]
II 8) = =(1 11-8) sm
Similarly, we have
IP [ m: B
Bi] 2 (1 5)m
we consider the conditional mean squared error of ((m,,)) given (n A.) n ()) By similar proof Prop. 22, we can show that for some constant C1 0,
ED US, [110@mmm) 0.113 (n (n (nE
SC
( S C1 (1
mn 10(00 0.112
2
+ m exp
parper
+ (8 2/2
20-1
+ (n)(m))) + 1))
We define the event of interest
(()) = [10(mma) - 0,113 S Cis C1s fm
where fs(m, n) is defined as
fs(m, n) = =(1 pmn
|10(0) 0.11
2
wmmm
(s 2/cm m 20 (n)(mm))1 1).
+ m exp
4
By Markov inequality, we have
ED
usm [10(m,)) -0 (n n (n B.)
P (|Ea(s) (o) (0 B.) 21
f(--f((m,))
2-8.
Since
P [()(()) = Ep [lea()] (ng - Ep [I) (nnmodnnnn
< Ep [Lacenntogsss))mm...... + Ex (1
= P [E)(s) n (2 + (1
= P [E)(s) (n A.) n (n + (0
which implies that
P [8((s] 2 2(1 - s) - 1.
69

---

Define 6(s) as
8(s) = 8 + 2(1 (1 - x)**) = (ms))
(109)
Then, with probability at least - -()), we have
[|0(m,m) -0112 S 11 (1 w1
|10(0) - 0.12
+ s m exp
jarmrr
+ (8 2/c m
20_1 (m)(mm))++1)
4
When (mm) = (1), it follows that
10(mx))-011 S -1 (1
mn
11000] 0.112 + + (s 25-2/mm 20-1
+ 1 + n).
2
70

---

G Numerical Experiments
This section provides numerical experiments of the proposed stochastic methods in this paper. In Appx. G.I, we design numerical experiment illustrate our orthogonalization method. In Appx. G.2, we design simulations based on partially linear model. In Appx. G.3, we conduct real data analysis with synthetic outcome to evaluate the performance of our methods. Code for reproduction can be found at https: http:///ach.....//// github.ic.
G.1 Numerical Illustration
In this section, we design a numerical experiment illustrate how our orthogonalization method effects the target estimation as shown in Fig. from the main text.
Settings. Consider θ R and IR. Let L(0,g) be real-valued risk function defined
L(0,g) = L(u) = (u. Au) + Asinn((u, Bu)),
(110)
where a (0,9)T T IR, A 0.02 the regularization parameter, and
3 2
2 -1
and B
0.
1.5
easy to see that (0,0) 0) the global minimizer of T. since T(00, g) O. Let = (u, Bu). The gradient w.r.t u is
Vul(u)- = Au + ()sin(g(u)) cos(a(u))
(A sinq(n()())
Since A + 2λ sin(((((()) - 0.04B implying that (0, 0) the only minimizer of L. Furthermore, we can obtain the Hessian w.r.t. u as
it is clear that (0. 0) is the only stationary point,
(111) which implies that L(,g)) is not convex R given any g E Gr (9o). However, when is a small neighborhood around zero, it is still possible to have L(;g) strongly convex for in θ given any E Gr (go)-
L() = + (ag(n((((u))) B + 8A co) Bu(B))
To orthogonalize T., we first derive the orthogonal gradient oracle using (11), and then integral the oracle w.r.t. 0 to obtain the orthogonalized loss Lno-
Orthogonalization.
Let H be the Hessian at (0, 0). By (111), we know that Hl = A, implying Hag A1 and H Agg- Since the gradient w.r.t. satisfies
VoL(O,g) [1, (A
(A + 2A B))
(An + 2A ( + (A12 + 22sin(2 (12)))
and the gradient w.r.t. g satisfies
y L g) [0. 1](A + si))n(((uu))B)
= (A2 + 2X (fn((.gg)))) g)) B21 8 + (A22 + 2X sin sinsnin(((()) (2q(u) B2a) ).
follow the construction of (11) and we obtain the orthogonal gradient oracle
Sna O g) VoL(O, g) Hog H , (a + 2b (in + 2cA (in(2((6.g)))))
where a = An A12 Ag1. b = Bn A12 B21, and B12 - A12 Bzz. Finally, we integral Smo (0. w.r.t. 0 and recover the orthognalized loss Inn as
Imo (0.g) () = - Smo(S, g)ds.
71

---

Numerical Computation. Usually, Smo(s. g) contains form of integral, which needs to be nu- merically computed. For the example introduced above, we can simplify (0, g) stabilize the numerical computation. Note that Vo Vasin (g(0. g)) sin(2q (Bn + B12g). Then
2bd /
26d
S/ sin(2q(s.g)) + B12g)ds B1ng f sin(24(s g)
sin(2g(s.g))sds
B11
26A
sin (q Bi2g / sin sin(2g(s.
Bu
It follows that the orthogonalized loss Ino admits the following form
26A
B1 ) Ag I' sin(2g(s,, ())
B12,
Loo (0,
02
sin (a((,))) +
Bn
which implies that only the integral of sin (2q(s. w.r.t. needs to be computed.
G.2
Simulations
G.2.1 Data Generating Process
To demonstrate Thm. 1 and Thm. 3, we revisit the partially linear model and the corresponding orthogonal and non-orthogonal losses Appx. B.1. Specifically, (X, W,Y) ) R x Rd R satisfies the following partially linear model where the nonlinear function is determined by the distribution of (W, U) I x
Y (fo. X) + (o(W) +,, = ao ()) +
(112)
(113)
where 8, E Rdd is the true parameter, on W + R is the true nonlinear function, and
independent noises that satisfy E(e X, W] = and E[ W = O. clear that on E
W]. In our simulations, we choose d and 0n = [-0.5 0.5
To get samples for simulations, we first generate (X, W) under the Gaussian model
X W
[xx 1'
(1 + 8)L2 (1+6)1.)
XI2
= N
(114)
AI
where fxx [1 T]T, Mw
[2 T, I, R222 is the identity matrix, E [0, is used to control the correlation between X and W, and 5 5= 0.05 is used to prevent the degeneration of the covariance matrix. For simplicity, define the nonlinear function 0g
W1 + w2 + 0.5 sin
W1 + W2
(o(w) 0.5
(115)
2
where w = [w1 w2]l R We then generate Y and using independent Gaussian noises NO, 1) and ~ NO0 1) based on (112) and (113), respectively.
G.2.2 Stochastic Gradient Oracles
To estimate the true parameter O using stochastic gradients, we need to design correspond loss whose minimizer 0, is equal to 0g. Based Appx. B. there two types of loss, the orthogonal loss and the non-orthogonal loss, available for this goal. We will derive the stochastic gradient oracle for these two losses and further derive the orthogonalized gradient oracle for the non-orthogonal loss.
Orthogonal loss. Recall the orthogonal loss in Appx. B.1.1:
1 - -r-rww (0, (xw))
E(O, 2)
(116)
where g = (gy,gx): W - x Rdd and the norm ||. lla defined in (27). The true nuisance for this
loss is 9o = (90.x, ). where (o. Ep [Y W w| and go.x (w) == Ep [X W w]
72

---

In fact, the explicit expression for 9u can be easily obtained as
90.y (w) = (fo. 90.x (w)) + ow(w),
(117)
A
90.x (w) μx +
(w - pw))
(118)
1.05
From (112) and (117), it is clear that
Y go,y (W) (0o, X 9o, (W)) +
which implies that 0, 8, by Lem. 4. The stochastic gradient oracle for the orthogonal loss (116) then defined as
=0(0 - (w)
(0, - gx (w))) gx (w))
(119)
Non-orthogonal loss. We also provide the non-orthogonal loss in Appx. B.1.2 as
1 5 g(w) (0, x))
((0.g:2)
(120)
where g : W + and the norm - واا is now defined in (36). The true nuisance for this non- orthogonal loss satisfies
(v(w) = ao(w) = E |U W = w]
(121)
By Lem. 5, we have 0, = 0g. The stochastic gradient oracle for the orthogonal loss (120) is then defined as
So(0,9;2) = -y - g(w) - (0.x))a.
(122)
Orthogonalized gradient oracle. Since we perform orthogonalization on the non-orthogonal loss, we have 0- On being the same target parameter. By (22) in Appx. 1.1.2, the Neyman orthogonal- ized gradient oracle for this non-orthogonal loss (120) is given by
(0, gi (y g(w) (0, x))
[ W w)).
(123)
G.2.3 Estimation Methods
Throughout the experiments, we estimate the nuisances and the orthogonalizing operator using full- batch data and stream data, respectively.
Nuisance estimation. Note that the true nuisances for the orthogonal loss and the non-orthogonal loss conditional expectation given W. To conduct nonparametric regression, Fourier feature (RFF) [Rahimi and Recht, 2007] using the kernel w - exp (-7 (| to generate randomized feature map for W.
random
The nuisance estimation procedure for obtaining g(m) using full batch data can be summarized as
1. Fit RFF sampler with 20 components using i.i.d. samples from PwIA-
2. Fit Ridge regressions where the regularization parameter is set to be 0.01/m. Specifically,
For the orthogonal loss, fit two Ridge regressions using m i.i.d. samples from the joint distribution Px,w,yJa and the fitted RFF sampler coordinate-wised wiisll estimate ||X W]. With the same data, fit one Ridge regression using the fitted RFF sampler to estimate IELY W].
For the non-orthogonal loss, one Ridge regression using m i.i.d. samples from the joint distribution Px,w,yJx and the fitted RFF sampler to estimate B(U W].
To estimate nuisances using stream data, instead of fit Ridge regression each time, perform SGD for the Ridge regression loss. The procedure can be summarized as
1. Initialize RFF sampler with 20 components using no i.i.d. samples (W))2 from PWIA-
2. Perform SGD update once observing mini-batch of i.idd. samples from the joint distribu- tion Px,W.YJa with size ng. Specifically,
73

---

For the orthogonal loss, perform two SGD with the Ridge loss for m iterations to estimate E|X W| coordinate-wist wisely.. With the same data perform another SGD with the Ridge loss for iterations to estimate F W].
For the non-orthgonna loss, perform one SGD with the Ridge loss for m iterations to estimate EUU W].
Orthogonalizing operator estimation. To approximate the orthogonalizing operator Fo, it suffices estimate E [X] W] by (21). To that end, we use the same method the nuisance estimation. The orthogonalizing operator estimation procedure for obtaining (*()) can be summarized as
1. Fit RFF sampler with 20 components using kt i.i.d. samples (W)) from Pwra-
2. Fit two Ridge regressions with the regularization parameter being 0.01/k using the fitted RFF sampler and another l i.idd samples (X,, W to coordinate-wise estimate E[X] W].
Target estimation. After the estimation of nuisances and orthogonalizing operator, we perform stochastic gradient descent (SGD) estimate 0, using each of the three stochastic gradient oracles in (119), (122), and (123) on n i.idd samples drawn from the joint distribution Px,W,U.. The learning rates of all the three SGDs are fixed during the training.
G.2.4 Simulation Results
Setup. each nuisance estimation setting, we study three types of estimation methods for learning
8o established in this paper: (1) (orthogonal loss) obtain nuisance estimator g g(TT) = (gy Ix of
(m) (mm)
(117) and (118) and then perform SGD to obtain ((²) using the gradient oracle (1 19) after plugging
in g(mm); (2) (non-orthogonal loss) obtain the nuisance estimator gf(m) = (m) of (121) and then
perform SGD to obtain ((n) using the gradient oracle (122) after plugging in g(m); (3) (OSGD) obtain the nuisance estimator g(m²) of (121) and the orthogonalizing operator estimator (1) of (21), and then perform SGD to obtain g(n) using the gradient oracle (123) after plugging in g g(m)) and ((R) Each method is independently repeated 20 times. For nuisance estimated using stream data, allow the procedure repeated by plugging in updated nuisance estimators and updated operator estimator, where the nuisances get updated for 2000 iterations after every 2000 target SGD iterations.
Evaluation.
We evaluate the performance of nuisance estimators using the corresponding norms defined in (27) and (36). Specifically, for method (1), we evaluate the nuisance estimation by
||ox5T (m)) (W) 9a. (W) $ E [(oVT] (W) - 90.r go.r oo.) }) (124)
||g (m) - golls = max
For method (2) and (3), we evaluate the nuisance estimation by
(m) - golle
- an (W)
(125)
We evaluate (()) + E (W) (W) in method (3) using the Frobenius norm [|[(M] (oo))olllea which is defined
FoloFro
(R) Tollero = E [110x
( (W) 90.x (W)ll
(126)
Finally, we evaluate the target estimation using two kinds of criterion: (a) the relative error [0ol) and (b) the risk L(B(m)..g) .9) L(e.. 90) where L(A.g) E[ g: Z)). For method |ooll (I), EO, gi 2) is the orthogonal loss defined in (116) while for method (2) and (3), E(O, gi 2) is the non-orthogonal loss defined in (120).
Results using nuisances fitted on full-batch data. We first estimate the target using prefitted nuisances and operator. The estimation errors of nuisances and the operator fitted on full-batch data are shown in Fig. 2, where estimation converges when the sample size m increases and less samples are usually required to obtain the same error level when À increases.
74

---

Nuisance error for non-orthagonal loss
Nuisance error for orthogonal loss
Operator arror non-orthegonal loss
3.0
2.5
1.5
3-
0.0
10F
10P
-02
10"
107
10P
Figure 2: The Nuisance and Orthogonalizing Operator Fitted on Full-Batch Simulated Data. The y-axis measures the corresponding eπror defined in (124) (126) and the x-axis displays the sample size of data used to estimate the nuisance and operator.
À 0.0
0.5
A 1.0
10"
10P
1000
10-2
10
15000
5000
15000
20000
6000
10000
20000
1,000 sal 110, .00
100
10
10
10-5
10
10
5000
10000
15000
20000
5000
10000
15000
20000
5000
10000
15000
20.00
500
3
-00000
Figure 3: SGD for Orthogonal Loss with the Nuisance Fitted on Full-Batch Simulated Data. The x-axis represents the SGD iteration. Top: The y-axis measures the relative error. Bottom: The y-axis measures the risk.
The performances of SGDs using prefitted nuisances and stochastic gradient oracles (119), (122), and (123) are shown in Fig. 3, Fig. 4, and Fig. 5, respectively. These figures suggest that when increases, i.e., the correlation between and increases, usually more iterations are required to have SGD converged due to the difficulty of separating the effect of X from W. In addition, a well prefitted nuisance estimator would largely reduce the SGD estimation error, which aligns with Thm. 1. This improvement would be more obvious À increases. Fig. 5 also shows that either using a well estimated nuisance or well estimated orthogonalizing operator can improve the OSGD performance, and that OSGD using both well prefitted nuisance and operator would perform nearly the same as OSGD using the true nuisance and the true operator.
Results using nuisances fitted on stream data. We then study the interleaving the nuisance and target estimations discussed in Appx. F.3. Here, Both the nuisance and the operator are learned using the same data stream and the results are shown in Fig. 6. Compared with Fig. 2, nuisances estimated using stream data usually has larger error and need more iterations to converge due to mini-batch learning rate, and other tuning parameters.
The performances of SGDs by interleaving nuisance and target updates with stochastic gradient oracles (119), (122), and (123) are shown in Fig. 7, Fig. 8, and Fig. 9, respectively. For all the three stochastic gradients, when À increases, the relative errors of the target SGD always get larger and their convergence rates become slower. There are obvious errors for SGDs using gradient oracles (119) and (122) in Fig. 7 and Fig. 8 since nuisances are not well estimated. However, OSGD
75

---

À 0.0
0.5
A
10-1-
10
10
100
10-3
10m-
10-1
5000
10000
15000
20000
5000
10000
150000
2000
5000
100000
15000
200000
100. (60
10
10
107
10-1
10-4
10-9
10-1
5000
100.0
15000
5000
10000
15000
20000
5000
10000
15000
20000
Figure 4: SGD for Non-Orthogonal Loss with the Nuisance Fitted on Full-Batch Simulated Data. The x-axis represents the SGD iteration. Top: The y-axis measures the relative error. Bottom: The y-axis measures the risk.
À - 0.0
0.5
10-1--
10
1200--4
10-3
10
5000
10000
15000
20000
5000
10000
15000
20000
5000
10000
15000
20000
[00,51 .01
10"1
10
10-1
10:9.
3-
10-1
10000
15000
20000
8000
19000
20000
6000
10000
20000
gind, fiN0
gemu, firet
goma) 101
gomo Fohtl
Figure 5: OSGD with the Nuisance and Operator Fitted on Full-Batch Simulated Data. Here, = 500, m2 10000, k = 300, h = 10000. The x-axis represents the OSGD iteration. Top: The y-aiis measures the relative error. Bottom: The y-axis measures the risk.
Nuisance orthogonal less
Nuisance orthogonal loss
Operator for orthogonal
1.0
0.5
0.20
0.9
[fto] Tol.mn
0.8
0.15
0.7
0.3
0.6
0.6
0.2
0.1
10000
11000
10000
15000
5000
10000
16000
m
m
A= 0.0
Ub
1.U
Figure 6: Nuisance and Orthogonalizing Operator Fitted on Simulated Stream Data. The y- axis measures the corresponding error defined in (124) (126) and the x-axis displays the sample size of data used to estimate the nuisance and operator.
76

---

2 - 0.5
A 1.0
100
10P
9.b
140
10
0
5.00
10000
15000
20000
5000
10000
15000
20000
1000
10000
13000
20000
100. .23
10-2
10m1
10-1
10
3000
15000
20000
15000
20000
5000
10000
15000
SGD lterations
SCD Berations
5GD iteations
68 m
Figure 7: SGD for Orthogonal Loss with the Nuisance Fitted on Simulated Stream Data. The x-axis represents the SGD iteration. Top: The y-axis measures the relative error. Bottom: The y-axis measures the risk.
2 - 0.5
1.0
10-1
10-1
10-1
5000
1500K:
20000
10000)
15000
20000
50013
1:000
150000
20000
130 .00
100
10-2
10-1
2/ au)
10:5.
10
10
X000
10000
15000
20000
5000
10000
15000
20000
5000
10000
13000
20000
SGD iteratioms
SCD itrraioos
SGD iteration
(g/99 m 1}
Figure 8: SGD for Non-Orthogonal Loss with the Nuisance Fitted on Simulated Stream Data. The x-axis represents the SGD iteration. Top: The y-axis measures the relative error. Bottom: The y-axis measures the risk.
performs perfectly as shown in Fig. 9, which verifies the analysis Thm. 3 that using an estimated orthogonalizing operator would reduce the bias from nuisance estimation.
G.3 Real Data Analysis
We consider the Diabetes 130-Hospitals Dataset (Clore et al., 2014] as the real dataset example. We six of these features covariates, which are summarized in Tab. 4. We take the binary feature "change" as the input X E {0, 1} and take the rest five features as the control W/ E 1R.
G.3.1 Synthetic outcomes
To evaluate the performance of our proposed methods, we use the synthetic outcome instead of a real outcome examine the performance of proposed methods. Using the synthetic outcome is common in causal inference; see Nie and Wager [2021, Sec. 4.1]. this real data analysis, we generate outcome according the following partially linear model:
Y = 0, X + ān (W) 0.5 6,
(127)
U = ( 0.5 x E.
(128)
77

---

2 - 0.5
A 1.0
10
10P
194b
10ma
10-2
5000
10000
15000
20000
5000
10000
15000
20000
5000
1000
15000
20000
Ligisumt g0) 100
10-2-
10-2
10-1
10-9
10"0
10-0
3000
15000
20000
15000
20000
10000
15000
SGD lterations
SGD Berations
50D iteations
[1gint,fim (imil. y an 1)
Figure 9: OSGD with the Nuisance Fitted on Simulated Stream Data. The x-axis represents the SGD iteration. Top: The y-axis measures the relative error. Bottom: The y-axis measures the risk.
Feature
Description
change
Indicates was change diabetic medications.
time_in hospital
Integer number of days between admission discharge.
num nab_lab.jue www.laabpproddre..
Integer number of tests performed during encounter.
num pro.errcesures
Integer number procedures (other than lah tests) performed during the encnunter. Integer number distinct generic names administered during encounter. Integer number of diagnoses.
num_medications
diagnoses
Table 4: Features used for real data analysis.
where 6, -1, ~ Wo 1) and & (000 1) are independent noises, and åg R + R satisfies that for (wi..... Ws).
5
ao(w) = 0.5 x cos Σ Wi 0.5 x sin 5 5
wi
i=1
Similar to Appx. G.2.2, have 0, 0g in this case.
G.3.2 Real Data Results
Setup. We consider the same three stochastic gradient oracles as Appx. G.2.2 and the same two nuisance estimation methods Appx. G.2.3 except that we use logistic regression on full batch data and SGD of the logistic loss on stream data for estimating E[X W). The setup SGD using prefitted nuisances for this real data analysis is the same as Appx. G.2.4. For nuisance estimated using stream data, we update nuisances for 100 iterations after every 500 target SGD iterations.
Evaluation. Since the true nuisances E[X W] and E[Y W] are unknown, we evaluate the per- (m) (m)) for the orthogonal loss by the mean squared
formance of nuisance estimation ((m)) (o 9 error:
(m) (W) - Y)2 MSE, (g(m)) = max Ep (g("))
Ep
(
(m) (W) xy²}
(129)
We adopt the nuisance estimation error non-orthogonal loss due to the synthetic outcome, where now go ãg. For the operator estimation
(x golls defined in (125) as the nuisance evaluation for
78

---

Nuisance error for non-orthogonal loss
Nuisance MSE for orthogonal loss
Operator MSE for non-orthogonal loss
1.30
0.230
0.250
1.00
M
0.75
0.215
0.30
0.240
0.25
0.210
m
Figure 10: Nuisance and Orthogonalizing Operator Fitted on Full-Batch Real Data. The x- axis displays the sample size of data used to estimate the nuisance and operator. Left. The y-axis measure the nuisance error defined in (125). Middle. The y-axis measure the nuisance estimation MSE defined in (129). Right. The y-axis measure the operator estimation MSE defined in (130).
SGD for Orthogonal Loss
SGD for Non Orthogonal Loss
OSGD
.0--
10-2
10-2
10-3-
10
10
10.
10-5-
10000
Z/000 (a) E.0, 5b)
10
10-1-
10m-
10-5-
10-4
10-5
26000
5000
7600
10000
2500
6000
7500
1000
2500
5000
7500
1000
g(re)
glmal
kmmu glmal
30m6 MMa
gime) Poa
Figure 11: Stochastic Gradients with Nuisance Fitted on Full-Batch Real Data. Here, mi = 32, m2 64, my 128, m4 8, ms 128, kn 32 and la 128. The x-axis represents the SGD iteration using corresponding stochastic gradient. Top: The y-axis measures the relative error. Bottom: The y-axis measures the risk.
f(m)
g + E (W), evaluate its performance by the mean squared error:
MSE = Ep (OX (m) (W) -x)]
(130)
Results using nuisances fitted on full-batch data. We first estimate the target using prefitted nuisances and operator. The estimation erгоrs of nuisances and the operator using full-batch real data are shown Fig. 10, which suggests that the estimation of âg converges to zero due to our design while there exists obvious bias for estimating the nuisance (No,x, (9,y) and the orthogonalizing operator To possibly due to model misspecification.
The performances of SGDs using prefitted nuisances and stochastic gradient oracles (119), (122), and (123) are shown Fig. 11. Overall, the relative error and the risk are small when well estimated nuisances are used. In addition, both relative errors and risks become smaller when we use more samples to estimate nuisances for the orthogonal loss and the non-orthogonal loss.
Results using nuisances fitted on stream data. We then estimate the target by interleaving the nuisance and target updates. Here, Both the nuisance and the operator are learned using the same
79

---

N Nuisance error for non-orthogonal loss
Nuisance MSE orthagonal loss
Operator MSE for not-orthogonal loss
01,020
01:0000
1,50
0.5
0.21775
01.4
1,00
0.2125
0.2
0.50
0124400
2000
$000
40.00
1000
4000
5000
20000
3000
Estimation Errors of Nuisanee and Orthogonalizing Operator Fitted on Stream Data. The x-axis displays the sample size of data used to estimate the nuisance and operator. Left. The y-axis measure the nuisance error defined (125). Middle. The y-axis measure the nuisance estimation MSE defined in (129). Right. The y-axis measure the operator estimation MSE defined in (130).
Figure 12:
Orthogonal Loss
Non-Orthagonal
OSGD
10
10:9.
10
10-9
10
10-3
10-7
10-9
10-7
10
2000
10000
106 061
10-2
10
56)
10
10
10-7
7
2000
4000
6000
8000
10000
2000
8000
8000
8000
10000
2000
1000
10000
Beration
Itration
iteraiinn
16 (im))
13
No. (i)): m
Figure 13: Stochastic Gradients with Nuisance Fitted Real Stream Data. The x-axis repre- sents the SGD iteration. Top: The y-axis measures the relative error. Bottom: The y-axis measures the risk.
data stream and the results are shown in Fig. 12. Compared with Fig. 10, nuisances estimated using stream data converges similarly.
The performances of SGDs by interleaving nuisance and target updates with stochastic gradient oracles (119), (122), and (123) are shown in Fig. 13. The figure on the left in Fig. 13 shows that the target estimation has small relative error using the estimated nuisance sequence (g(m)) m 2 1)- The figure in the middle suggests that there still some bias for the target estimation while this bias negligible. The figure on the right shows the performance of OSGD, where the relative error of OSGD using the estimated nuisance sequence is similar to OSGD using the true nuisance, which aligns with Thm.
80

---

H Extension to SGD Variants
In this section, we discuss strategies for analyzing other variants of SGD under nuisances. In Appx. H.I, discuss the relationship between SGD with momentum and averaged SGD and pro- vide a convergence analysis example of the averaged SGD. Appx. H.2, we discuss Adam as generalization of SGD with momentum and the difficulties to analyze the convergence rate of Adam.
H.1 SGD with Momentum and Averaged SGD
For the gradient oracle sequence s(x), SGD with momentum following the description of Li et al. [2022] can be expressed as
m (n+1) B,m (n) + s(x) and ((n+1) = g( - m.)
(131)
where g(m) is the SGD estimation sequence, m(") is the momentum sequence, and (ax)n20 and (9n)n2u can be any positive sequence. The following example shows that the averaged SGD is special case of SGD with momentum.
Example 5 (Averaged SGD). Let 3n. 1/n and on 7)(1 Bn+t) for all 2 1. The momentum updates implied by this sequence are
mm (n) + s(t) and ((n+1) T(m) (1
(1
m (n+1)
m (n)
which implies that 0(++1) is the averaged SGD such that
Ø(++l)
(132)
+ t=
Example demonstrates that the convergence rate of SGD with momentum can be analyzed in the same way averaged SGD, While is not the focus of this paper, we provide a convergence result of the averaged SGD based on the analysis of Défossez and Bach [2015].
Proposition 27 (Convergence rate of averaged SGD). Consider the partially linear model and the non-orthogonal loss E(O, gi 2) in Appx. 1.1.2. Define D, (Zi...., Zn), sampled from the product measure Pa. Choose the gradient oracle g(n) be the score Se Zn) where 9 is estimated independently of DD,, Let ((n) be the averaged SGD defined in (132). Suppose the same assumptions as Lem. If0 < 17 <. Tmax then
Ee (10(m) 0.113 S
11 90ll3
where Tmax = sup(n > 0 or (A Ep[XX (IA) - nEp AXTAX) > 0, AA e S(R)) and S(R4) is the set of all d x d symmetric matrices.
Before we prove Prop. 27, recall the example of non-orthogonal loss for the partially linear model in Appx. 1.1.2, where Z = (X, W, Y) satisfies
Y = (fu. X) + (W) +e, Ep je X, W|
(133)
The target parameter 0, arg mingee Ep [6(0, g: 2)] where e the non-orthogonal loss defined as
E(0. g) 2) = g(w) (8, x3)
(134)
By Lem. 5, we have 0, 00. The stochastic gradient oracle for this non-orthogonal loss is
So(0,g:2) 2) = - g(w) (0, x)).
81

---

and the SGD iteration is defined by ((0) E θ and
g(m) g(n-1) (0, 9: Zn- g(n-1) n - ((Wn-1) (n-)x, (135)
where ÿ E Gr (go) is any nuisance estimator independent of {Zi] Note that (135) can be written
as
nn (Yn - 0 (W.)) 0. (60)_ 0. nX,x,,,,) 0(n-1)
= -I1 - (1-1)aax, x)xx (0(m-1) - 0,) + 1n (Yn 9 (Wn) - xx 0.)
(I -n,Xxxx,, (0(n-1) - 0.) + nnnnn n2nn (0 (Wn) 90 (W,)).
Let ((x) = -((n) - 0z I' = 0 (Wn) 90 (Wn), and
T (1 (1- (1- nxxx7) 1=++1
Ma..
II
E Rddd
By recursion, we have
g(m) - -) 3(m-1) nnnnn 7nNnTn
M Ma,nXKes 11 Σ MaT
Let 3(a) = Ø(n) - 0, = (n 1)
Σj=o B(8), we have
g(m)
1
n
Mo
3(0)
7
Σ
n
Mas
(Xx - rrk) + +EE [x
n +
n
j=0
k=1 j=k
77
Ma.
E [[
72 +
In the above formula, first two terms usually interpreted the bias term and the variance term under the true nuisance, respectively according to Défossez and Bach [2015], and the last term can be viewed the error term caused by the nuisance estimation.
To analyze the bias term and the variance term, we adopt the notations of Défossez and Bach [2015] for matrices and operators. First, Defin H = E3 X x Let H2 (resp. HR) be the matrix operator representing left multiplication (resp. right multiplication) by H, and T be the linear operator such that for any square matrix M E [ddd TM HM + M Hl 7/Ep [XX .M XXXXX
Let p max [| [| | |lap where the operator norm ||- llllop is defined as the largest singular value. Finally, let 7max be the same as Prop. 27. With definitions above, the asymptotic covariances of the bias and the variance follow directly from Theorems and 2 of Défossez and Bach [2015, Appx. 3].
Lemma 28 (Asymptotic covariance of the bias). Let E. = Epp 300) 3(0) T
IfO < < Tmax then
Ex B, = 1
H + R n!) (I~ +0 p" -
nン
where B, n+1 Ej= 310
Lemma 29 (Asymptotic covariance of the variance). Let Eo = Var(X, (ex - -ra) + E [(rrr,)).. If
0 17 Tmax then
Ep VVVTT
(HT + H - 1711 2-0
( + H nT) (I TTT)T +0 (p" (Bolle).
m
82

---

where Vn
2 n+1 Ek=1
(Ax (ex: - rk) + E [Xarr)))
In fact, the convergence rate of averaged SGD depends on (B, and tr (V,V,)). When p < 1, Lem. 28 demonstrate that tr (B,,,,) of order n ?, while Lem. 29 shows that tr (V, of order n which is reasonable due to the randomness of the noise C₁ Tk-
For the error term, we can analyze it in a similar way to the bias term. Let A = Ep [X,ra] and
T En
Maj
A.
n
+
k=
jonk
Note that by Jensen's 's inequality,
2
12
n
Ep
Em
12
Ep
17
Σ
MR.
A
n
k=1
jo
n
12
Ep
Σ
Masa
Σ
Mr
A
72
is clear see that the asymptotic covariance of De, = Ej= Mr. of the same form as the bias term in Lem. 28. Let Go = Ex [A and we have
Ep A
(H H n!) (T- + 0 ((n I Golle) 172
Thus, the trace of the covariance summation over I,.... 7 satisfies
n-
tr Ep AI)) = tr ((HE=* + H Go) +0
11dh
kp
Golll
71
(136)
Gathering the bias term, the variance term, and the error term, we now ready to proof Prop. 27.
Proof of Prop. 27. By Lemma of Défossez and Bach [2015], 0 < < 1 when 0 < 17 < 1mmax-
Suppose that || I Cx almost surely. By Jensen's 's inequality we have that
|Gooll |Ep [Xurx]12 S Ex C Esp [+]]] = Cx - 90.12.
Note that
n- p&
d
(1 1-
p - np" + (n - 1)p
Σ kp = p dp k=
= P dp
= 0(1.
1 -
(1 - (1=
k=
By Lem. 28, Lem. 29, and (136), we have
Ep
[p(n) 111
I Ee
B 1
+
Ep
[
+ Ep Em1
[,, (EE V. + n7 Σ (Ep A AT..)) 1)
tr (E2
n
16 11
83

---

H.2
Adam
The primary updates for Adam under nuisance estimate I are given by the following recursive equa- tions. Below, we let E {1..... d denote particular dimension of the finite-dimension parame- ter of interest. Following the description of Défossez et al. [2022], for the gradient oracle sequence
((x) the Adam generates the target estimator ((m) as below:
m (n) 8im; (n-1) 1) + s(
(137)
= 820 (n-1) + ((())) 2
(138)
m; (n)
0 = 8(n-1)
(139)
+ us (m)
where B2 E (0, 1], 31 E [0, 82] are the momentum and variance parameters, m( v(m) E Rd are the momentum and variance sequences, and 0 is numerical stability parameter. Adam differs from the SGD with momentum by adding variance sequence v(*), When e(()) is chosen to be constant, then (137) and (139) would reduce to the special case SGD with momentum where Bn. and an constant.
The analysis of Adam often done the case of smooth non-convex optimization, in which shown that the gradient of the objective tends to zero [Ward et al., 2020, Défossez et al., 2022]. Specifically, Défossez al. [2022] consider a momentum-free Adam (3) = () analyze the es- sential ingredients that differ from momentum: the variance pre-conditioning and element-wise up- dates, which suggests that under the true nuisance, i.e., S(n) Sg(O(m), :o:: Z,,) for an i..d sample {Zil== Ipn the convergence result of Adam satisfies
log ())-
Epn (S((0()) 9u 10
Vn
Note that this result not comparable to our convergence criterion (in terms of iterations), which differs non- non-trivially from stationarity or function value analysis. While the convergence of Adam without nuisance has been studied in the literature, still remains unclear that how analysis Adam under an estimated nuisance 9 and what should be the nuisance effect on the gradient norm criterion.
84


Reviews:
[{"review_id": "VXTB4ZQNsh", "reviewer": "Reviewer_rpHD", "summary": "SUMMARY: \nThe paper studies learning problems where the target objective depends on an unknown nuisance parameter. It establishes stochastic gradient convergence guarantees under the assumption of Neyman orthogonality and shows that even when orthogonality is violated, orthogonalized gradient updates can still achieve linear convergence. The work is relevant for causal inference and semiparametric estimation, though its theoretical results appear limited to convex objectives and standard stochastic gradient descent without extensions such as momentum. The paper lacks any empirical validation.", "questions": "QUESTIONS:\n1) What is the connection of Neyman orthogonality and unbiasedness of the gradient estimators?\n2) Why don't the authors apply their method on any DML or OSL problem? Can you show that you obtain unbiased estimator of a data generating process?", "limitations": "LIMITATIONS\n1) The results are constrained to Vanilla SGD, however most modern SGD algorithms use momentum or are ADAM variants, perhaps the authors could extend their results towards this optimizers.\n2) The results are restricted to convex objective assumptions, neural networks do not have convex loss landscapes.", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "STRENGTHS:\n1) The paper presents interesting convergence guarantees for SGD under nuisance estimators, and Neyman orthogonality assumptions.\n2) Figure 1 offers a very clear explanation of the paper's motivation, I would suggest that you move it closer to the introduction. \n3) The Theorem in the paper is conveniently presented, and contrasted between the nuisance sensitivity conditions.\n\n\nWEAKNESSES:\n1) The paper introduces the Neyman orthogonality. Since Neyman orthogonality is highly technical concept it should be accompanied earlier with intuitive explanations.\n1.1) If a lot of the intuitions from Neyman orthogonality are borrowed from double machine learning and causal inference, \n\nTt would be convenient for the paper to add the explanations of the concepts in the paper or an abstract of the paper.\n2) In spite of Section 3 being clearly explained and illustrated, the abstract and Section 1 lacks a clear motivation, on why learning under nuisance is important.\n3) The paper organization and motivation can be improved.\n4) The paper lacks any empirical validation of the proposed method.", "was_revised": true, "final_justification": "The lack of empirical studies and proper justification made me update my score from borderline accept to reject.", "rebuttal": "Thank you for thorough and insightful feedback. We address your comments below. We have also incorporated your comments on improving the motivation (by elaborating on existing examples) and commenting on the intuitions from DML/OSL in the revision. If you find your concerns are addressed, we kindly request you increase your score or let us know what we can provide.\n\n>**\"The results are constrained to Vanilla SGD, however most modern SGD algorithms use momentum or are ADAM variants, perhaps the authors could extend their results towards this optimizers.\"**\n\nRegarding momentum, we first note that due to the presence of noise, momentum variants of SGD do *not* improve the achievable convergence rates (see [Li et al (ALT, 2022)](https://proceedings.mlr.press/v167/li22a/li22a.pdf)). However, it has been observed that momentum updates can be one-to-one mapped to averaged SGD under particular averaging assumptions ([Defazio, 2022](https://arxiv.org/abs/2010.00406)). We proved an $O(1/n)$ convergence result for the $n$-th iterate averaged uniformly across iterations, $\\bar{\\theta}^{(n)} = \\frac{1}{n}\\sum_{i=1}^n \\theta^{(i)}$, but did not include it in the submission due the aforementioned limitations of momentum for SGD analyses. Stated in terms of momentum updates, this averaging sequence corresponds to the updates:\n\n$$\n m^{(n+1)} = \\frac{1}{n} m^{(n)} + S_\\theta(\\theta^{(n)}, \\hat{g}, Z_{n+1}) \\text{ and } \\bar{\\theta}^{(n+1)} = \\bar{\\theta}^{(n)} - \\eta\\left(1-\\frac{1}{n+1}\\right) m^{(n)}.\n$$\n\nRegarding Adam variants such as AdaGrad, we comment on recent approaches such as [Ward et al (2019)](https://www.jmlr.org/papers/volume21/18-352/18-352.pdf) and [Défossez et al (2022)](https://openreview.net/pdf?id=ZPQhzTSWA7). We rely on the observation that the AdaGrad update for our method can be written as:\n\n$$\n\\theta^{(n)} = \\operatorname{argmin}_{\\theta \\in \\mathbb{R}^d}  \\langle S\\_\\theta(\\theta^{(n-1)}, \\hat{g}, Z_n), \\theta \\rangle + \\frac{1}{2\\eta} \\Vert \\theta - \\theta^{(n-1)} \\Vert_n^2,\n$$\n\nwhere $\\Vert \\cdot \\Vert_n$ is a norm defined by the variance pre-conditioner in AdaGrad. To prove an analog of Theorem 1, we change the norm of $f\\_n$ from Lemma 8 and follow a similar analysis but with a changing norm across iterations. By bounding the differences in the norms, we achieve a similar result with an additional error term. We note that these ideas are in service of providing a novel analysis of Adam/AdaGrad in the strongly convex setting, which would be an independent contribution even in absence of Neyman orthogonality, and may be beyond the scope of this paper.\n\nWe can provide further details in the discussion period due to character limitations.\n\n>**\"What is the connection of Neyman orthogonality and unbiasedness of the gradient estimators?\"**\n\nThere are two notions of bias to consider in this problem. The first is the bias of any estimator for the population gradient $\\nabla_\\theta L(\\theta, \\hat{g}) = E_{Z \\sim \\mathbb{P}}[\\nabla_\\theta \\ell(\\theta, \\hat{g}, Z)]$, which is zero under the standard stochastic gradient oracle and the NO oracle analyzed in Theorems 1 and 2, respectively.  \n\nThe second bias results from optimizing $\\theta \\mapsto L(\\theta, \\hat{g})$ instead of $\\theta \\mapsto L(\\theta, g_0)$, or in other words, the nuisance estimation error. Here, Neyman orthogonality allows us to provide precise bounds on the error incurred by optimizing the first function when we are in fact pursuing the optimum of the second.\n\n>**\"The paper lacks any empirical validation of the proposed method.\"**\n\nWe have now added an experiment section to illustrate Theorem 2 in the revision where we consider SGD versus OSGD for the non-orthogonal loss based on the partially linear model $Y =  \\langle \\theta_0, X \\rangle + \\alpha_0(W) + \\epsilon$. Specifically, we consider the following data generating process:\n\n$$ \n\\begin{bmatrix} X\\\\\\ \nW \\end{bmatrix} \n= N\\left(\n\\begin{bmatrix} \\boldsymbol{\\mu}_X \\\\\\ \n\\boldsymbol{\\mu}_W \n\\end{bmatrix}, \n\\begin{bmatrix} 1.05I_2 &\\lambda I_2\\\\\\ \n\\lambda I_2 & 1.05I_2 \n\\end{bmatrix}\\right),$$\n\nwhere $U = \\alpha_0(W) + \\xi$, $Y = \\langle \\theta_0, X \\rangle + \\alpha_0(W) + \\epsilon$,  $X,W \\in \\mathbb{R}^2$, $U, Y \\in \\mathbb{R}$, $\\xi \\sim N(0,1)$ and $\\epsilon \\sim N(0,1)$ are independent Gaussian noises, and $\\lambda \\in [0,1]$ is used to control the covariance between $X$ and $W$. We define the true parameter $\\theta_0 = [-0.5 ~ 1]$ and the nonlinear function $\\alpha_0$ as\n\n$$\\alpha_0(w) = 0.5\\times \\cos\\left(\\frac{w_1 + w_2}{2}\\right) + 0.5\\times \\sin\\left(\\frac{w_1 + w_2}{2}\\right).$$\n\nWe estimate the nuisances and the orthogonalizing operator nonparametrically using ridge regression with random Fourier features, and we estimate the target parameter using SGD with orthogonalized and non-orthogonalized oracles, respectively. The nuisance error is defined as $\\Vert \\hat g - g_0 \\Vert_{\\mathcal{G}}$ where the norm is defined in Eq. (31). The orthogonalizing operator error $\\Vert \\hat \\Gamma - \\Gamma_0 \\Vert_{\\mathrm{Fro}}$ is defined as $\\sqrt{\\Vert \\hat{g}(W) -  E[X \\mid W] \\Vert_2^2}$ since $\\Gamma_0: g \\mapsto E[E[X\\mid W] g(W)]$ has this explicit form.\n\nBelow are two tables that summarize the estimation performance of each gradient oracle where $m$ is the number of samples used to estimate the nuisances and $k$ is the number of examples used to estimate the orthogonalizing operator. We also provide the risk suboptimality $L(\\cdot, g\\_0) - L(\\theta\\_\\star, g\\_0)$ when using the true nuisance parameter and orthogonalizing operator to represent the idealized performance. To understand the results, first note that each choice of $\\lambda$ represents a different data-generating distribution (i.e., another dataset).\n\nTable 1: SGD Performance\n\n|$\\lambda$|$m$|$g_0$ Error|$\\theta_\\star$ Error|Excess Risk|\n|---------|---|-----------|--------------------|------------|\n|0.0|16|1.6851|0.0404|0.0732|\n|0.0|1024|0.2297|0.0011|0.0012|\n|0.0|0|0.0000|0.0008|0.0011|\n|1.0|16|1.8792|0.5234|0.4485|\n|1.0|1024|0.2145|0.0019|0.0019|\n|1.0|0|0.0000|0.0008|0.0011|\n\n\nTable 2: OSGD Performance\n\n|$\\lambda$|$m$|$k$|$g_0$ error|$\\Gamma_0$ Error|$\\theta_\\star$ Error|Excess Risk|\n|---------|---|---|------------|----------------|--------------------|------------|\n|0.0|16|1024|1.6851|2.1097|0.0270|0.0301|\n|0.0|16|0|1.6851|0.0000|0.0030|0.0047|\n|0.0|1024|1024|0.2297|2.1008|0.0091|0.0097|\n|0.0|1024|0|0.2297|0.0000|0.0011|0.0013|\n|0.0|0|1024|0.0000|2.1075|0.0106|0.0115|\n|0.0|0|0|0.0000|0.0000|0.0016|0.0019|\n|1.0|16|1024|1.8792|0.6399|0.1450|0.1995|\n|1.0|16|0|1.8792|0.0000|0.0155|0.0163|\n|1.0|1024|1024|0.2145|0.6387|0.0449|0.0529|\n|1.0|1024|0|0.2145|0.0000|0.0095|0.0087|\n|1.0|0|1024|0.0000|0.6398|0.0481|0.0506|\n|1.0|0|0|0.0000|0.0000|0.0086|0.0077|\n\nThe results demonstrate that: \n\n1. Across values of $\\lambda$ in Table 1, when the nuisance estimators approximate the true nuisances well, the performance of SGD under the estimated nuisances is numerically indistinguishable from the performance of SGD under the true nuisance. \n2. Across values of $\\lambda$ in Table 2, the performance of OSGD largely depends on the quality of the NO estimator and the correlation between $X$ and $W$. When the nuisance estimation is accurate, the $\\theta_\\star$ error decreases as demonstrated in Theorem 2.\n3. Comparing Table 2 with Table 1, using the estimated NO gradient oracle reduces $\\theta_\\star$ error when $m = 16$, which aligns with Theorem 2. The large correlation between $X$ and $W$ would impact the target estimation using an approximated nuisance and the approximated NO gradient oracle for OSGD. However, for a bad nuisance estimator, using a well approximated NO gradient oracle can still improve the target estimation.\n\nAs discussed in Appx. F.3, we also perform SGD and OSGD on the non-orthogonal loss with updated nuisances and the updated NO oracle using the same data generating process above. For the nuisance and NO estimation, we use a kernel-based estimator with random Fourier features and SGD. When we update the nuisance and NO for 10 times with batch sizes 16 and 1024, respectively, and we iterate SGD 100 times with batch size 10 between every two nuisance updates, we achieve a relative error 0.0008 for SGD and a smaller relative error 0.0005 for OSGD when $\\lambda = 0$, which implies that both SGD and OSGD estimate the target perfectly since both the nuisance and the NO gradient oracle are well estimated through the updates, and that OSGD reduces the relative error due to Prop. 20 and Prop. 21 in our paper.  \n\nFor real data analysis, we consider the Diabetes 130-Hospitals Dataset as the real dataset example, where we use 6 of these features as covariates such as the change indicator in diabetic medications (change), the time in hospital (time_in_hospital). We conduct analysis based on a partially linear model in Example 1 and Appx. B.1 so that we can use the synthetic outcome based on this model instead of a real outcome to examine the performance of our proposed methods. Using the synthetic outcome is common in causal inference, such as Sec. 4.1 of [Nie et al. (2021)](https://arxiv.org/abs/1712.04912). For comparison, we perform SGD and OSGD for the non-orthogonal loss. For nuisance estimation with batch size 64, we achieve relative error 0.0095 for SGD, while with the same nuisance batch size, we achieved a smaller relative error 0.0013 with an estimated operator learned with batchsize=1024 for OSGD. \n\nWe also have experiments of SGD on the orthogonal loss, which can be provided in the discussion period due to space limitation. This comparison would illustrate the nuisance sensitive and insensitive bounds from Theorem 1."}, {"review_id": "qbq4tUhlgK", "reviewer": "Reviewer_ZwEM", "summary": "This paper considers the problem of nuisanced stochastic optimization, where the loss depends as an input on an unknown nuisance parameter $g \\in \\mathcal G$. The paper provides the last-iterate convergence rates of the vanilla SGD and Orthogonal SGD algorithms with the plug-in estimate $\\hat g$ of $g_0$ (the \"ground-truth\" nuisance parameter). \n\nThe OSGD algorithm adds an orthogonalizing factor to the otherwise non-orthogonal gradient (coinciding with SGD when it is already orthogonal), leading to a faster convergence rate.", "questions": "- Can the authors provide detailed justification that Assumption 6 can be satisfied, and Theorem 2 is thus non-vacuous?\n\n- How is the functional estimate $\\hat g$ computed in the partially linear model, and what is the choice of the norm $ || \\cdot  ||_{\\mathcal G}$ in this function space? These details need to be addressed in B.1 so that the readers may understand the full procedure of OSGD on this example.", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- The paper is well motivated and (mostly) well written. The results are involved, sound, and insightful. While the concept of Neyman orthogonality existed in the literature, the gradient orthogonalization procedure is novel and well justified, as it accelerates convergence.\n\n- Occasionally symbols that appear in the main text are defined in the appendices. This is particularly the case around Theorem 2, the primary contribution of this paper.\n\n- There might be a lack of demonstration that Assumption 6 holds in any of the provided examples.", "was_revised": true, "final_justification": "I thank the authors for their detailed rebuttal. In particular, I followed their example demonstrating the non-vacuity of Assumption 6 and found it convincing. This now seems to me a quite reasonable assumption as far as Theorem 2 (being the first such last-iterate analysis on OSGD) goes.\n\nI have revised my rating accordingly.", "rebuttal": "Thank you for your review and thorough feedback. We address each of your comments below.\n\n>**“Occasionally symbols that appear in the main text are defined in the appendices.”**\n\nDue to the 9 page limit of submission, we moved Asm. 6 to the appendix. However, the notations in Asm. 6, as stated in line 259, can be understood similarly as notations in Asm. 3. We will make this more clear in the final version.\n\n>**“There might be a lack of demonstration that Assumption 6 holds in any of the provided examples… Can the authors provide detailed justification that Assumption 6 can be satisfied...?**\n\nThank you for this feedback. As we discuss in lines 906-912, Asm. 6 can be satisfied easily for an orthogonal loss. For the case of a non-orthogonal loss, we consider below the example in Appx. B.1.2 and derive mild sufficient conditions for Asm. 6 to be satisfied. We will incorporate this argument into the final version to improve the paper.\n\nConsider the non-orthogonal loss is defined as $\\ell(\\theta, g; z) = \\frac{1}{2}(y - g(w) - \\langle x, \\theta \\rangle )^2$. By the definition of derivative operator in Def. 1, we have the computations\n\n- $D_g \\ell(\\theta, g; z)[h] = -(y - g(w) - \\langle x, \\theta \\rangle)h(w),$\n- $D_\\theta D_g \\ell(\\theta, g; z)[h, \\theta - \\theta_\\star] = \\langle x, \\theta - \\theta_\\star \\rangle h(w),$\n- $D_g^2 \\ell(\\theta, g; z)[h_1, h_2] = h_1(w)h_2(w).$\n\nThus, by the definition in line 851 and line 852, we have that $H_{\\theta g} = E[X \\mid W]$, $H_{gg} = I$ (the identity operator). According to line 858, the NO gradient oracle is defined as\n\n$$S_{no}(\\theta, g; z) = -(y - g(w) - \\langle x, \\theta \\rangle)(x - E[X \\mid W=w]). $$\n\nUnder the partially linear model defined in Eq. (16), we have \n\n1. $g_0(W) = E[Y - \\langle X, \\theta_0 \\rangle \\mid W]$ and $\\theta_0 = \\theta_\\star$. Plugging this into $S_{no}(\\theta_\\star, g_0) = E[S_{no}(\\theta_\\star, g_0; Z)]$ and we will see that it is the exact gradient of the orthogonal loss in Appx. B.1.1. Thus, $S_{no}(\\theta_\\star, g_0) = 0$.\n2. $D_g \\ell(\\theta_\\star, g_0)[h] = E[-\\epsilon h(W)] = 0.$\n\nThus, Asm. 6(a) is satisfied. For Asm. 6(b)-(d), they can be easily verified by definitions directly and following the same analysis as the proof of Lem. 3 in Appx. B.1.1 or Lem. 4 in Appx. B.1.2. Lastly, Asm. 6(e) holds true since $D_g^2 S_{no} = 0$ by Def. 1.\n\n>**“How is the functional estimate $\\hat{g}$ computed in the partially linear model, and what is the choice of the norm $\\Vert \\cdot \\Vert_{\\mathcal{G}}$ in this function space?”**\n\nThank you for raising this point. In general, the function $g$ will often have both a closed-form expression and variational expression depending on the data-generating distribution. This will naturally lead to $\\hat g$ trained via standard empirical risk minimization and a norm based on the chosen function class. Consider the following examples:\n1. For the orthogonal loss in Appx. B.1.1, the nuisance consists of two conditional expectations $(E[Y\\mid W], E[X \\mid W])$, which can be estimated using nonparametric methods like random forests and kernel methods under squared error loss. The corresponding nuisance norm $\\Vert \\cdot \\Vert_{\\mathcal{G}}$ is defined in Eq. (22) in the proof of Lemma 3.\n2. For the non-orthogonal loss in Appx. B.1.2, the nuisance is $g_0$ itself, which is usually modeled as the conditional expectation $E[U \\mid W]$, where $U$ is the additional feature vector. Thus, to estimate $g_0$, we can do the same as in the previous item. The norm $\\Vert \\cdot \\Vert_{\\mathcal{G}}$ is defined in Eq. (31) in the proof of Lemma 4.\nWe will incorporate the upcoming discussion in the final version.\n\n>**\"Are these colored backdrops allowed?\"**\n\nWe leave it to the AC’s discretion and will gladly remove them if asked."}, {"review_id": "kgTY7QtkG6", "reviewer": "Reviewer_TZV1", "summary": "Build a Neyman orthogonal gradient method that avoids establishing a double machine learning objective in a case-by-case manner when there are nuisance parameters. Achieve the same theoretical result, yet the method is much more versatile. This is a really nice paper that combines statistical ideas with optimization methods. I find discussions in the appendix very insightful and valuable. I would give the highest score if the motivation for (9) and (10) can be more clearly stated. The writing could accommodate a bit more for optimization readers.", "questions": "Overall, I really like the paper, though I still have a few questions. \n1. In stochastic optimization with unknown parameters, the formulation is similar to the problem considered in the paper (without NO of course). Does it imply that the designed method will also have improvements for the general stochastic optimization with unknown parameter settings? \n2. Are there any other applications where constructing the bias-corrected objective is very difficult, but the proposed methods could be directly applied to achieve a better or equivalent convergence?\n3. Higher-order smoothness intuitively decreases the dependence on the nuisance estimation error. How does higher-order smoothness play a role in Theorem 2? \n4. NO objective usually needs to be carefully designed as seen in the examples given in the paper. The proposed method does not seem to need such an assumption anymore. What is the key explanation behind such great improvements?\n5. Biased gradient methods can be categorized into two types. Type 1, as cited in the manuscript in P9, https://arxiv.org/abs/2305.16296 considers biased gradient methods where bias comes from the problem structure and thus can be absorbed in the analysis of SGD, resulting in a final convergence rate that does not exhibit an explicit bias. Type 2 is more closely related to the setting considered in the paper, where bias comes from additional estimation of some unknown terms or other optimization problems and cannot be easily absorbed in the analysis of gradient methods https://arxiv.org/abs/2408.11084 The discussion on the relationship to the biased gradient method should focus on type 2, in fact. For an overview of biased gradient methods and the difference between type I and II, see http://dx.doi.org/10.1007/978-3-030-54621-2_887-1\n6. The paper should highlight that g is independent of theta. Otherwise, one needs to construct estimators of g after updating theta at each iteration. This means that the setting considered in the paper is fundamentally different from DRO. Such a point should be clearly explained.\n7. The equations (8) and (13) are performing gradient ascent instead of gradient descent. Is there a typo that \"+\" should be replaced with \"-\"?\n8. The motivation for constructing OSGD is not clear. Why one would formulate (9) and use a gradient estimator (10)? Are there any requirements or design principle behind (10)? The current explanation is too vague.\n9. The notation system for section 1 is broken. There are five different loss function l, L, l_0, L(\\cdot, g). Yet their relationships are largely missing.\n10. Line 988, it should be \"(ii)\"?", "limitations": "Although codes are provided, no experiments are demonstrated in the paper.", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. First SGD method that handles nuisance without building a corresponding objective. \n2. Motivation is very clean and intuitive. \n3. Avoid conducting bias correction in a case-by-case manner for the objective. Build it directly on the gradient level. A good combination of statistical ideas and optimization methods.\n4. Theoretical results are convincing and interesting. \n\nWeaknesses: \n1. Computational costs can be high as it requires computing the Hessian inverse and Jacobian per iteration. \n2. The applicability of the proposed method should be more clearly stated.", "was_revised": true, "final_justification": "All my concerns have been fully addressed. I greatly appreciate that the paper presents novel and original ideas, demonstrates applicability across different domains, and provides a comprehensive comparison along with a rigorous analysis of the proposed methods. Accordingly, I have raised my score to 6. I would like to thank all the authors for their efforts in producing such a high-quality piece of work. It clearly reflects a substantial amount of work and is well-deserved.", "rebuttal": ">**\"I would give the highest score if the motivation for (9) and (10) can be more clearly stated.\"**\n\nAs in the discussion “Comparison of Orthogonalizing Operators” in Appx. F.2, the motivation for Eq. (9) and Eq. (10) comes from the semiparametric inference literature, wherein the goal is to reduce the asymptotic variance of the estimate for $\\theta_\\star$. Often, the orthogonalizing process is described using the language of differential/information geometry, in that the so-called efficient influence functions are constructed by doing an orthogonal projection in a Hilbert space. \n\nOur intention with (9) and (10) is to describe the same concept in a way that appeals to machine learning audiences; the correction term subtracts the regression of the $\\theta$ gradient of the loss on the $g$ “gradient” of the loss. By the law of total variance, the variance of the gradient reduces and improves the trajectory of stochastic optimization. Furthermore, this variational description (9)  hints at how such an operator can be computed algorithmically, instead of the historical semiparametric inference approach of deriving the operator via calculation by hand. \n\n>**\"The writing could accommodate a bit more for optimization readers.\"**\n\nThank you for this feedback. We are happy to incorporate any concrete suggestions, and otherwise will emphasize the variance reduction viewpoint stated above if you find it helpful. \n\n>**\"Computational costs can be high as it requires computing the Hessian inverse and Jacobian per iteration… The applicability of the proposed method should be more clearly stated.\"**\n\nThe problem (9) does not have to be solved at every iteration, and is instead computed once for the entire trajectory in the setting of Theorem 2. That being said, practical algorithms that compute $\\hat\\Gamma$ using an optimization approach may interleave their updates with the updates for $\\theta^{(n)}$. We discuss these interleaving strategies for $\\hat{g}$ toward the end of Section 3.\n\nWe will further clarify the precise implementation and applicability of the orthogonalizing operator in the final version. We also implement a version of OSGD on the partial linear model. Please see the experiments in our response to Reviewer rpHD for details. \n\n>**\"In stochastic optimization with unknown parameters, the formulation is similar... Does it imply that the designed method will also have improvements for the general stochastic optimization with unknown parameter settings?\"**\n\nYes. In this case, we can treat the unknown parameters as a nuisance, and apply the results of Theorems 1 and 2 based on whether (i) the loss is Neyman orthogonal with respect to the unknown parameters, and (ii) whether the NO gradient oracle can be efficiently computed.\n\n>**\"Are there any other applications where constructing the bias-corrected objective is very difficult, but the proposed methods could be directly applied to achieve a better or equivalent convergence?\"**\n\nThe squared loss used in many estimation problems are usually non-orthogonal while our orthogonalizing method can still be used. For example, consider the estimation of the weighted averaged derivative and $Z = (D, X, Y)$ where $D$ is a continuous distributed random variable, $X$ is the covariate vector, and $Y$ is the outcome. Let $\\gamma_0(d,x) = E[Y \\mid D = d, X = x]$, and $\\omega(d)$ is a probability density function. Define $S(u) = -\\omega(u)^{-1}\\partial \\omega(u)/\\partial u$ as the negative score for the pdf  $\\omega$ and let $U$ be a random variable that is independent of $X$ with pdf $\\omega$. Then the target can be written as \n\n$$\\theta_0 = \\operatorname{argmin}_{\\theta \\in \\mathbb{R}} E[(\\theta - S(U)\\gamma_0(U,X))^2],$$\n\nwhere the true nuisance is $g_0 = (S(U), \\gamma_0(U,X))$. We can show that this squared loss is not an orthogonal loss. However, we can perform OSGD to obtain an orthogonalized gradient oracle.\n\n>**\"Higher-order smoothness intuitively decreases the dependence on the nuisance estimation error. How does higher-order smoothness play a role in Theorem 2?\"**\n\nThe higher-order smoothness refers to Asm. 4 for Thm. 1 (the higher-order smoothness of the orthogonal loss), Asm. 6(e) for Thm. 2 (the higher-order smoothness of NO score), and their generalizations. For Thm. 2, the higher-order smoothness impacts the coefficient $\\beta_2$ and the power of the nuisance error (like the fourth power of $\\Vert \\hat g - g_0\\Vert_{\\mathcal{G}}$). When we have an even higher order smoothness condition instead of Asm. 6(e), the term $\\beta_2^2\\Vert \\hat g - g_0\\Vert_{\\mathcal{G}}^4$ in Thm. 2 would be replaced by a similar term with higher order. \n\nHowever, the cross-product term $\\alpha_2^2\\Vert  \\hat g - g_0\\Vert_G^2\\cdot \\Vert  \\hat g - g_0\\Vert_{\\mathrm{Fro}}^2$ would still remain even under higher order smoothness of the NO score since the loss function itself is nonorthogonal, which causes this term to appear.\n\n>**\"NO objective usually needs to be carefully designed as seen in the examples given in the paper. The proposed method does not seem to need such an assumption anymore. What is the key explanation behind such great improvements?\"**\n\nA popular practice in semiparametric estimation is to handcraft an orthogonalized learning objective for estimation, and to use batch full-sample algorithm for optimization. One of the goals of our paper is to investigate the rate of convergence of stochastic gradient algorithms for non-orthogonalized objective and to delineate when they achieve the best rates of convergence. \n\nPut simply, iterative orthogonalizing stochastic gradient algorithms on non-orthogonalized learning objectives can relieve us of manually orthogonalizing the objective and using batch full sample optimization algorithms, as we mentioned in the discussion surrounding (9) and (10). \n\n>**\"The discussion on the relationship to the biased gradient method should focus on type 2... where bias comes from additional estimation of some unknown terms or other optimization problems.\"**\n\nThank you for these references. We have updated the discussion on biased SGD methods to reflect the relationship with biased SGD methods. Our setting does still differ slightly from the “Natural Biased Gradient Methods” (Type 2), in that the estimation of $\\hat{g}$ occurs once at the start of the trajectory and does not affect the oracle cost (such as the parameter $l$ does in from [Hu (2024)](http://dx.doi.org/10.1007/978-3-030-54621-2_887-1)). In the case of interleaved nuisance and target updates (F.3), the bias term depends on the total number of iterations used to update the nuisance, not the per-iteration complexity.\n\n>**\"The paper should highlight that $g$ is independent of theta. Otherwise, one needs to construct estimators of $g$ after updating $\\theta$ at each iteration. This means that the setting considered in the paper is fundamentally different from DRO.\"**\n\nThank you for raising this point. For Thm. 1 and Thm. 2, $\\hat g$ is always fixed during the training of SGD for learning $\\theta$ and we emphasized in line 55 that $(Z_i)\\_{i=1}^{n}$ used for learning $\\theta_\\star$  is an independent data stream. However, in Appx. F.3, we discuss interleaving $\\theta^{(n)}$ and $\\hat{g}$ updates, in which the nuisance estimate does indeed depend on the value of $\\theta^{(n)}$. We do not claim to solve DRO using OSGD updates, but do wish to clarify the dependence structures we consider. We use DRO simply as a recent example of loss minimization with an unknown nuisance (see lines 45-49 for the statement of focus).\n\n>**\"The equations (8) and (13) are performing gradient ascent instead of gradient descent. Is there a typo that \"+\" should be replaced with \"-\"?\"**\n\nThank you for catching this. Yes, \"+\" in  Eq. (8) and Eq. (13) are typos. We have corrected them to \"-\".\n\n>**\"The notation system for section 1 is broken. There are five different loss functions $\\ell$, $L$, $\\ell_0$, $L(\\cdot, g)$. Yet their relationships are largely missing.\"**\n\nThroughout the paper, we focus on two kinds of losses under nuisance: (1) the individual level loss $\\ell(\\theta, g; z)$ and (2) the population level loss $L(\\theta, g) = E[\\ell(\\theta, g; z)]$. In Sec. 1, we want to introduce (1) and (2) from losses without nuisances that readers in optimization and machine learning are familiar with. These losses without nuisance can also be understood as the losses under the true nuisance as $\\ell(\\theta, g_0; z)$ and $L(\\theta, g_0)$, where we used $\\ell_0$ and $L_0$ to describe them.\n\n>**\"Line 988, it should be \"(ii)\"?\"**\n\nIt should be (iii), as (ii) would be considered when deriving guarantees in terms of function value suboptimality as opposed to the squared distance to $\\theta_\\star$. While these criteria can sometimes be easily mapped between one another in traditional optimization analyses, incorporating Neyman orthogonality may be non-trivial for other proof structures. For example, consider the argument of Lemma 9 in Appx C, which employs NO. The function value gap is lower bounded by a term from which the nuisance bias term is extracted.\n\n>**\"Although codes are provided, no experiments are demonstrated in the paper.\"**\n\nThank you for raising this point. Please see the response to Reviewer rpHD, for additional experiments with SGD/OSGD on the partially linear model."}]

Author rebuttal:

Meta-review: This paper studies stochastic gradient methods for learning problems where the objective depends on unknown nuisance parameters. The authors provide non-asymptotic convergence guarantees, showing that classical stochastic gradient algorithms can still converge under conditions such as Neyman orthogonality. Additionally, they propose an algorithm with approximately orthogonalized updates that achieves similar performance even when strict orthogonality is not satisfied. Applications to orthogonal statistical learning and causal inference are discussed.

Although there is a substantial divergence in reviewer opinions, I find the core contributions both novel and technically solid. The theoretical insights into how nuisance parameters affect convergence, and the development of a practical solution through approximate orthogonalization, make this work a valuable addition to the NeurIPS community.

I recommend acceptance, with the expectation that the authors carefully address all outstanding concerns raised during the discussion in the camera-ready version.
Decision: Accept (poster)