Private Optimal Inventory Policy Learning for Feature-based Newsvendor with Unknown Demand
Tuoyi Zhao Wen-xin Zhou Lan Wang


 






 













%̂ŝ%̃s̃ | 

































































































































































































































  
  
                                                        


































condCondition









































skeptic






































##1#
    #1

$#1$
    #1




∑_i=1^n
𝐒















 





















#1 #1


 






myabstract[1][Abstract]
#1 

    
    

    

mykeywords
    

§ KEYWORDS:

    

    

















 [, ](),a,
 
 
 24pt
  
 and

















fancy
 
[R] 

























Zhao, Zhou and Wang




Privacy-Preserving Data-driven Newsvendor




Private Optimal Inventory Policy Learning for Feature-based Newsvendor with Unknown Demand






Tuoyi Zhao
Department of Management Science, Miami Herbert Business School, University of Miami, Coral Gables, FL 33146, txz311@miami.edu
Wen-Xin Zhou
Department of Information and Decision Sciences, University of Illinois at Chicago, Chicago, IL 60607, wenxinz@uic.edu 
Lan Wang
Department of Management Science, Miami Herbert Business School, University of Miami, Coral Gables, FL 33146, lxw611@miami.edu





The data-driven newsvendor problem with features has recently emerged as a significant area of research, driven by the proliferation of data across various sectors such as retail, supply chains, e-commerce, and healthcare. Given the sensitive nature of customer or organizational data often used in feature-based analysis, it is crucial to ensure individual privacy to uphold trust and confidence. Despite its importance, privacy preservation in the context of inventory planning remains unexplored.  
A key challenge is the nonsmoothness of the newsvendor loss function, which sets it apart from existing work on privacy-preserving algorithms in other settings. This paper introduces a novel approach to estimate a privacy-preserving optimal inventory policy within the f-differential privacy framework, an extension of the classical (ϵ, δ)-differential privacy with several appealing properties.
We develop a clipped noisy gradient descent algorithm based on convolution smoothing for optimal inventory estimation to simultaneously address three main challenges: (1) unknown demand distribution and nonsmooth loss function; (2) provable privacy guarantees for individual-level data; and (3) desirable statistical precision.
We derive finite-sample high-probability bounds for optimal policy parameter estimation and regret analysis.
By leveraging the structure of the newsvendor problem, we attain a faster excess population risk bound compared to that obtained from an indiscriminate application of existing results for general nonsmooth convex loss. Our bound aligns with that for strongly convex and smooth
loss function.
Our numerical experiments demonstrate that the proposed new method can achieve desirable privacy protection with a marginal increase in cost.

newsvendor; differential privacy; 
data-driven decision-making;
convolution smoothing; regret analysis 


    Private Optimal Inventory Policy Learning for Feature-based Newsvendor with Unknown Demand
    

    Tuoyi Zhao[ Department of Management Science, University of Miami. txz311@miami.edu.], Wen-Xin Zhou [ Department of Information and
Decision Sciences, University of Illinois at Chicago. wenxinz@uic.edu.] and Lan Wang[ Department of Management Science, University of Miami. lxw611@miami.edu.  The research of Zhao and Wang was partially supported by Grant NSF FRGMS-1952373.]
    

    


    The data-driven newsvendor problem with features has recently emerged as a significant area of research, driven by the proliferation of data across various sectors such as retail, supply chains, e-commerce, and healthcare. Given the sensitive nature of customer or organizational data often used in feature-based analysis, it is crucial to ensure individual privacy to uphold trust and confidence. Despite its importance, privacy preservation in the context of inventory planning remains unexplored.  
A key challenge is the nonsmoothness of the newsvendor loss function, which sets it apart from existing work on privacy-preserving algorithms in other settings. This paper introduces a novel approach to estimate a privacy-preserving optimal inventory policy within the f-differential privacy framework, an extension of the classical (ϵ, δ)-differential privacy with several appealing properties.
We develop a clipped noisy gradient descent algorithm based on convolution smoothing for optimal inventory estimation to simultaneously address three main challenges: (1) unknown demand distribution and nonsmooth loss function; (2) provable privacy guarantees for individual-level data; and (3) desirable statistical precision.
We derive finite-sample high-probability bounds for optimal policy parameter estimation and regret analysis.
By leveraging the structure of the newsvendor problem, we attain a faster excess population risk bound compared to that obtained from an indiscriminate application of existing results for general nonsmooth convex loss. Our bound aligns with that for strongly convex and smooth
loss function.
Our numerical experiments demonstrate that the proposed new method can achieve desirable privacy protection with a marginal increase in cost.

0.4pt

    newsvendor; differential privacy; 
data-driven decision-making;
convolution smoothing; regret analysis.



§ INTRODUCTION

 

The newsvendor problem, a classical example of the inventory-control problem, is of fundamental importance to operations management. In recent years, there has been growing interest in data-driven feature-based newsvendor problems, due to the vast amount of data generated by retail and supply chains, e-commerce, banking, financial, hospitals, and other business domains. The goal of the feature-based newsvendor problem is to estimate the optimal inventory policy based on the historical demand data as well as the observed features (e.g., product characteristics, customer characteristics) associated with the demand. The ability to determine optimal inventory levels based on features (or contextual information) such as location and usage is essential for supply chain planning. Recently, <cit.> carefully justified from a theoretical perspective the value of incorporating features in the newsvendor problem when such information is available. They proved that ignoring features may lead to estimation bias, which does not diminish as the number of observations gets large.

In a host of applications, feature-based inventory analysis involves sensitive customer or organizational data. Examples include but are not restricted to the following:

    
  * Healthcare. In hospitals, nurse staffing in the emergency room can be formulated as a feature-based newsvendor problem, see, for example, <cit.>, <cit.> and <cit.>. The features can include the hospital inflow and outflow conditions, surgical case volume, behavioral health patients' boarding information,
    doctor staffing information, and nurses' credentials. As another application, surgical procedures require a large number of consumable supplies that need to be kept in hospital inventory and transported to the operating rooms.  <cit.> formulate the problem of preparing a surgical preference card, a list of items for each surgery, as a newsvendor problem. The features include surgery type, patient disease status, and physicians' past records, among others. Hospitals in general would prefer to keep the related information internal and any physician- and patient-level information private.
    
  * E-commerce. Companies such as Chewey, an online retailer of pet supplies or grocery stores with online ordering and delivery service, often leverage customer-level data for inventory management. This helps not only coordinate shipping from its local warehouses but also design targeted marketing campaigns (e.g., sending coupons to different groups of customers based on predicted individualized inventory levels). 
    
  * Finance. In portfolio management, mutual funds hold a certain percentage of their assets in cash to meet redemption demand from investors. The decision on how much cash to reserve can be formulated as a feature-based newsvendor problem. If not enough cash is held, the fund must sell some of its holdings and will incur transaction costs. In the recent Silicon Valley Bank’s downfall in March 2023, the bank had to sell its securities to raise cash to meet a wave of withdrawals from customers. A strategy of inventory policy can be planned based on the financial and operational variables and clients' behaviors.



In the context of the applications discussed above, the preservation of privacy is of critical importance. Despite this, systematic studies in the realm of inventory planning are lacking.
The protection of individual privacy is essential in maintaining customer trust and confidence, and in helping the business avoid financial losses and reputation damage <cit.>. The prevalence of individual-level data and the increased awareness of privacy concerns motivate us to develop a principled privacy-preserving framework for data-driven feature-based newsvendor problems with unknown demand.  We focus on the scenario where there is a trusted curator, such as the company's in-house business analytics team, responsible for processing and analyzing the data. The primary objective of this paper is to develop a data-driven approach that generates valuable outputs.
These outputs assist a decision maker (hereafter referred to as “DM") in estimating the optimal inventory level, all while safeguarding the privacy of historical individual-level data. 
In essence, our approach controls the likelihood of an adversary making harmful inferences about a data subject based on a differentially private data release, ensuring it remains a small probability event.




In more detail, we study a feature-based newsvendor problem where the demand distribution is unknown to the DM. The trusted curator has access only to n past records (historical data) she collects {d_i, _i}, i=1,…,n where d_i is the observed demand, and _i is the associated vector of features (or covariates). 
When presented with a new query, the curator utilizes a data-driven iterative algorithm to 
release a private output. This output guides the DM in determining the optimal inventory level, while ensuring that the sensitive information from the historical data remains non-inferable from the output. The iterative algorithm introduces a carefully tuned amount of random noise
to the statistical outputs, aiming to strike a balance between privacy protection and statistical accuracy. See Figure <ref> for an illustration.

Distinct from prior work on privacy-preserving algorithms in other business applications, we 
confront the challenge of the nonsmoothness of the newsvendor loss function. In this setting, we 
leverage the recently introduced concept
of f-differential privacy <cit.> and propose a noisy clipped gradient descent algorithm based on convolution smoothing for optimal inventory estimation. The new approach simultaneously addresses the three main challenges: (1) unknown demand distribution and nonsmooth loss function; (2) provable privacy guarantees for individual-level data; and (3) desirable statistical precision. Importantly, our theoretical and numerical results demonstrate that a reasonable degree of privacy protection can be achieved with
minimal sacrifice of data utility, particularly when the size of the historical dataset is large.




 §.§ Contributions

Our major results and contributions are summarized as follows.



  §.§.§ Provable privacy-protection guarantee in the f-differential privacy framework.

 
 To establish rigorous privacy protection properties, we adopt a recently introduced novel privacy framework named f-differential privacy (f-DP, <cit.>), which generalizes the classical (ϵ, δ)-DP notion <cit.> with several attractive properties, see Section 4.1 for a more in-depth introduction. The (ϵ, δ)-DP notion was proposed by the computer science community and has become a popular framework for provable privacy protection against arbitrary adversaries while allowing the release of analytical summaries. It provides a statistical hypothesis testing interpretation for differential privacy, thereby making the privacy guarantees easily understandable. Despite its great success, a major shortcoming of
 (ϵ, δ)-DP is its inability to tightly handle composition (a.k.a. repeated application of the mechanism to the same data set). Using the output of an (ϵ, δ)-DP
mechanism, the power of any α-level test is bounded by e^ϵα+δ. Recall that the composition of (ϵ_1,δ_1)- and (ϵ_2,δ_2)-DP mechanisms results in an (ϵ_1 + ϵ_2, δ_1 + δ_2)-DP mechanism. The resulting power bound e^ϵ_1+ϵ_2α + δ_1 +δ_2 of any α-level test no longer tightly characterizes the trade-off between significance level and power.
As a fundamental observation, <cit.> pointed out that (ϵ, δ)-DP is mis-parameterized in the sense that the guarantees of the composition of (ϵ_i, δ_i)-DP mechanisms cannot be characterized by any single pair of parameters (ϵ, δ). Many recent efforts have been devoted to developing relaxations of DP for which composition can be handled exactly. These notions of DP no longer have hypothesis testing interpretations; rather, they are based on studying divergences that satisfy a certain information processing inequality. We refer to Section 1 of <cit.> for an in-depth discussion on this matter.
 
 
 
 



The main idea of the f-DP is the usage of the so-called trade-off functions as a measure of indistinguishability of two neighboring data sets rather than a few parameters as (ϵ, δ)-DP and other prior relaxations do. It preserves the hypothesis testing interpretation of differential privacy. Furthermore, it captures all the desirable properties of prior differential privacy definitions, in particular, composition, amplification by sampling, and Gaussian mechanism, tightly and analytically. It provides a powerful technique to import existing results proven for the (ϵ, δ)-DP to f-DP. 

 In the powerful and versatile f-DP framework, we rigorously establish that our data-driven algorithm provides the desired privacy guarantees. 



  §.§.§ A computationally efficient algorithm to estimate the feature-based optimal inventory policy with unknown demand function.


Traditionally, the newsvendor problem is solved based on the assumption that the demand distribution is known up to a small number of parameters. The commonly used data-driven estimation procedures often consist of two steps: the first step estimates the parameters using the observed data and the second step performs the optimization to estimate the optimal order quantity.  However, in reality, the true demand distribution is hardly ever known to the DM. 

For the data-driven feature-based newsvendor problem, <cit.> proposed a one-step estimation procedure based on empirical risk minimization (ERM) and established its connection to quantile regression <cit.>. In terms of computation, <cit.> reframed the ERM problem as a linear program and utilized existing linear programming solvers. These general-purpose solvers are capable of generating solutions with high precision (low duality gap). However, in the context of machine learning, this is inefficient for two reasons. First, generic toolboxes are often unaware of the problem structure and tend to be too slow or encounter memory issues. Secondly,  high precision is not always necessary for machine learning problems, and a duality gap of the order of machine precision may not be required <cit.>. More importantly, commonly used algorithms for solving linear programs, such as simplex-based methods and interior point methods, may not be readily adaptable for privacy preservation purposes.


To address the computational and privacy concerns mentioned above, we propose a new approach that utilizes convolution-smoothing <cit.>. This approach transforms the non-differentiable newsvendor loss function into a twice-differentiable, convex, and locally strongly convex surrogate, allowing for fast and scalable gradient-based algorithms for optimization. Additionally, to ensure privacy protection while maintaining computational tractability, inspired by <cit.>, <cit.> and <cit.>, we adopt a noisy optimization approach by adding Gaussian noise to the gradient of the smoothed empirical cost in each iteration. By carefully selecting the scale of the added noise and the number of iterations, we can achieve the desired privacy level along a sequence of outputs. The algorithm is designed for efficient implementation, and in this paper, we provide both privacy-protection guarantees and statistical accuracy guarantees for the output of this novel algorithm. 





  §.§.§ Finite-sample performance bounds and excess risk analysis.



Under a linear demand model with an unknown error distribution and a potentially large number of features, we analyze the convergence of the proposed algorithm and its finite sample performance error bounds. We also derive its regret bound, which is the difference between its expected cost and the optimal cost of the clairvoyant who knows the underlying demand distribution. The regret upper bound is of the order O(log (n)max{(p+log n/μ n)^2, p/n} ), where n is the size of the historical data set, p is the number of the features, μ is the privacy parameter. As we discuss in Section <ref>, μ=0.5 (or less) indicates a reasonable degree of privacy protection in practice. The term O( log(n)(p+log n/μ n)^2 )  corresponds to the additional regret due to privacy protection, which goes to zero quickly as n gets large for a reasonable choice of μ. The theory and our numerical results suggest that privacy protection can be achieved with a reasonably small additional cost.



The idea of convolution smoothing was initially proposed in the optimization community by <cit.>, where sigmoid functions were used as smooth approximations of the plus function max{ x, 0}. However, the impact of smoothing on statistical performance, in terms of estimation error bounds or regret bounds, remained largely unknown until recent studies in the context of quantile regression by <cit.>, <cit.> and <cit.>. 



In this paper, we conduct a comprehensive analysis of the noisy clipped gradient descent iterates, as opposed to the hypothesized empirical risk minimizer. By exploring the specific structure of the newsvendor problem, we achieve a faster excess population risk bound compared to the results obtained by indiscriminately applying existing results developed for general nonsmooth convex loss. Our bound matches with what one would obtain when the loss function is both strongly convex and smooth. The combination of carefully selected smoothing and noise scale parameters allows for control over the trade-off between statistical efficiency and the level of privacy. A key aspect of our analysis is a novel characterization of the local strong convexity and smoothness of the smoothed cost function, which subtly depends on the order of the smoothing parameter. The technical devices we employ in this paper to establish the theoretical framework are distinct from earlier works, such as those presented in <cit.>, and yield sharper results, as elaborated in Section <ref>. Furthermore, we relax the i.i.d. error condition in their paper. By allowing the error distribution to be heteroscedastic, we permit the features to influence not only the location of the demand distribution but also its dispersion. Furthermore, we do not require the error distribution to be bounded. 





 §.§ Notation and Organization


The following general notation will be used throughout the paper. We use _p to denote the p× p identity matrix. For a vector ∈ℝ^p (p≥ 2), we write ^2 = ^. For a positive definite matrix , we write _2 = max_: _2 = 1_2 and _ = √(^). We use 𝕊^p-1 to denote the unit sphere in ℝ^p, that is, 𝕊^p-1 = {∈ℝ^p: _2 =1 }. For two sequences of positive numbers { a_n }_n≥ 1 and { b_n }_n≥ 1, we write a_n ≲ b_n if there exists some constant C>0 independent of n such that a_n ≤ C b_n for all n; write a_n ≳ b_n if b_n ≲ a_n, and write a_n ≍ b_n if a_n≲ b_n and b_n ≲ a_n. For an event or set E, let 1(E) or 1{ E } denote the indicator function.

The paper is organized as follows. In Section 2, we review the related literature. Section 3 presents the model and introduces the underlying assumptions. In Section 4, we introduce the basics of f-differential privacy, present the new privacy-preserving algorithm for the feature-based newsvendor problem, and provide theoretical justifications for privacy-preserving guarantees. In Section 5, we provide high-probability bounds for the estimated private parameter indexing the optimal inventory policy and
the regret analysis. We analyze the performance of our approach through an extensive numerical study and a real data example in Section 6. Section 7 contains some concluding remarks. The technical details are given in the appendices. 




§ RELATED REVIEW

We briefly review related research in data-driven newsvendor problems and differential privacy for operations management.

Data-driven newsvendor problem with unknown demand.
Earlier work on newsvendor problems often assumes the demand distribution is known. There has also been extensive literature on relaxing the known demand distribution assumption but without using any feature information. <cit.> provided an excellent literature review and broadly characterized these methods
into three categories: the Bayesian approach, the minimax approach, and the data-driven approach. Our proposed method is more closely related to the data-driven approach where the DM uses the observed sample to make decisions, see <cit.>, among others. Related to this line of work, <cit.> incorporated feature-based information. <cit.> provided a systematic study on the benefits of incorporating features, proposed new algorithms, and derived performance bounds. <cit.> considered a deep-learning approach.

Our approach differs from the aforementioned work in several major aspects. First, our algorithm provides individual-level data privacy protection. To the best of our knowledge, this is the first time in the literature of newsvendor problems the issue of privacy is systematically investigated. Second, we provide a theoretical error bound for the T-step output of the proposed algorithm directly. In contrast, the theory of the early work is for the limiting (or theoretical) solution of their proposed algorithms. Third, we substantially relax the technical conditions on the random error distribution for the theory compared with the earlier work.


Differential privacy for operations management. In the last decade, privacy preservation has 
received substantial attention in theoretical computer science, database, and cryptography literature. There exist different notions of privacy. Differential privacy, a seminal concept introduced in <cit.>, has emerged as the foundation to develop a rigorous framework
for provable privacy protection against arbitrary adversaries. The most commonly used form of 
differential privacy relies on two parameters ϵ≥ 0 and 0≤δ≤ 1, and is often also referred to as the (ϵ, δ)-differential privacy. This concept has an intuitive hypothesis interpretation. Suppose an attacker would like to distinguish two neighboring data sets which differ by only one observation. Formulated as a hypothesis testing problem, accepting the null hypothesis means
the attacker cannot tell the two data sets apart. Then for any level α test (0<α<1) based on the output of a privacy-preserving algorithm satisfying (ϵ, δ)-differential privacy, its power (a.k.a. the probability of rejecting the null hypothesis when the two data sets are different)
is upper bounded by e^ϵα+δ. Moreover, (ϵ, δ)-differential privacy is immune to postprocessing, that is, combining two differential private algorithms preserves differential privacy. Although (ϵ, δ)-differential privacy provides an elegant formalism for privacy protection, it is known to suffer from the major drawback that it does not tightly 
handle composition. This makes it challenging to provide a tight analysis of the cumulative privacy loss over multiple computations thus limiting its applicability to practically useful privacy-preserving algorithms which often involve injecting privacy protection into different modules and iterative steps. 

Although several relaxations of the (ϵ, δ)-differential privacy have been proposed, they do not handle well fundamental primitives associated with differential privacy such as privacy amplification by subsampling.
This motivated us to adopt a recently proposed 
new notion of f-differential privacy  <cit.> which 
extends (ϵ, δ)-differential privacy and overcomes the above limitations. Similarly to (ϵ, δ)-differential privacy, f-differential privacy characterizes privacy preservation from the hypothesis testing perspective. Rather than using a pair of parameters (ϵ, δ) to balance between type I and type II errors, f-differential privacy uses a trade-off function. This functional extension of differential privacy avoids the drawbacks mentioned above. We refer to Section <ref> for more detailed discussions on the properties of f-differential privacy.
The notion of f-differential privacy was recently published as a discussion paper in the leading statistical journal Journal of the Royal Statistical Society, Series B. 
One of the discussants wrote “One can expect the latter (f-differential privacy) to become
a dominant approach in this literature given its appealing intuitive hypothesis-testing interpretation,
exact composition property, the central limit role for composition, and computational tractability
for approximating privacy losses."


Differentially private convex optimization. Our work is also related to the literature on differentially private convex optimization. Differentially private empirical risk minimization (ERM) is a well-studied area. The earlier popular approaches include output perturbation <cit.> and objective Perturbation <cit.>.

Motivated by <cit.> and <cit.>, we consider a noisy gradient descent algorithm. 
Differential privacy with various types of gradient descent algorithms have been studied by
<cit.>, <cit.>, <cit.>, <cit.>, <cit.>, <cit.>, and <cit.>, among others.
The methods in <cit.>, <cit.>, <cit.> and others do not directly apply to our setting. Most of the prior work requires strong convexity and other smoothness
 conditions that are not satisfied by the newsvendor loss function. In the case for which Lipschitz continuity suffices, the known excess loss rate is suboptimal in our setting as they do not explore the specific structure for the newsvendor loss as we do. Unlike the earlier literature, we do not assume the gradient is bounded by a constant and carefully analyzed a clipped DP gradient descent algorithm.
In the statistical literature, <cit.> recently investigated optimization-based approaches for Gaussian differentially private M-estimators. However, the objective function in our setting does not satisfy the local strong convexity and smoothness in their paper. However, our proof technique deviates from theirs. We will discuss the main challenges and our proof strategies in Section <ref>.
Despite the nonsmooth newsvendor loss, our novel analysis based on restricted strong convexity and smoothness leads to a faster excess population risk rate, which is only obtained in Section 5 of <cit.> when the loss function is both λ-strongly convex and β-smooth.
From this perspective, our results and proof techniques bring new insights and results to the differential private convex optimization literature.



Our work is also related to the growing but still limited literature on privacy preservation in operations management. <cit.> addressed privacy preservation for personalized pricing with demand following a generalized linear model. They proposed the new notion of anticipating (ϵ, δ)-differential privacy that is tailored to the dynamic pricing problem. 
<cit.> and <cit.> considered 
personalized pricing using the notion of central differential privacy and local differential privacy.
The aforementioned papers do not face the challenge of nonsmooth loss function as we have here.
However, our work is not a mere application of existing results on private nonsmooth convex optimization, nor does it utilize standard arguments such as uniform stability. Furthermore,
in contrast to these existing works, we adopt the f-differential privacy framework 
to study the performance of the new privacy-preserving algorithm and establish its provable privacy protection guarantees. 






§ PROBLEM FORMULATION




 §.§ Feature-based Newsvendor Problem

We consider the classical single-period newsvendor problem setting. The DM needs to determine the ordering level q based on the observable demand d and feature vector .
Both d and  are random. We assume that the distribution of the demand d is unknown. In the feature-based newsvendor problem, given a realization of the feature vector
∈ℝ^p, the DM sets the ordering level q() to
minimize the conditional expected cost function

    { C(q(), d ))|} ={[h(q()-d )^++b( d -q())^+]|},

where h is the per-unit holding cost, b is the per-unit lost-sales penalty cost, t^+=max{t,0}, and the expectation is taken with respect to the conditional distribution of d given .

Similarly to <cit.> and <cit.>, we consider a linear decision function of the
 form 
 
    q()=  ^  = ∑_j=1^p x_jβ_j,

 where the p-dimensional feature vector = (x_1,…, x_p)^ has x_1≡ 1, and = (β_1, …, β_p)^ is the coefficient vector. Considering the linear decision space is not a restriction in theory or practice. By replacing the features with their transformations (e.g., via series functions), the framework can be adapted to accommodate nonlinear decision rules. More specifically, one may approximate a nonlinear function ↦ q() by linear forms ()^, where ↦() := (z_1(), …, z_k())^ is a vector of approximating functions and k = k_n ≥ 1 may increase with n. Then, we denote the transformed features as {_i = (_i)}_i=1^n. Popular choices of the series approximating functions include B-splines (or regression splines), polynomials, Fourier series, and compactly supported wavelets. We refer to <cit.> and <cit.> for a detailed description of these series functions. Under the linear decision model, we define the parameter indexing the optimal decision rule as

    ^*=_∈ℝ^p    C() := { h( ^-d )^++b( d - ^ )^+}   ,

where the expectation is taken with respect to the joint distribution of (d, ). 
Write ε =d- ^^*.
Then the linear decision function (<cit.>) is
equivalent to assuming that the conditional b / (b+h) quantile of ε given  is zero. Unlike <cit.>, we do not assume independence between  and ε.




 §.§ Convolution Smoothing for Empirical Risk Minimization


In the case without features, it is well known that the
optimal decision is given by the b / (b+h) quantile of the demand distribution. It can be estimated by the data-driven sample average approximation (SAA) <cit.>,
an approach without making any parametric distributional assumption on d.  In the setting with features, <cit.> extended it
to the conditional case, proposed a linear programming-based empirical risk minimization algorithm (NV-ERM), and established the connection to conditional quantile regression. 
More explicitly, one can rewrite
C(q(), d)=(b+h)ρ_τ(d -q()),
where τ= b / (b+h), and ρ_τ(u) = u {τ - 1(u<0)} is referred to as the 
quantile loss function or the check function
corresponding to the τ-th quantile <cit.>.



For an arbitrary ∈^p, let 
ε_i() := d_i -  _i^,
i=1,…, n. Consider the empirical cumulative distribution function (ECDF) of the ε_i(): F̂(u;)
=(1/n) 1{ε_i()  ≤ u }, u ∈.
Then, the 
empirical risk minimization approach (NV-ERM) of
<cit.> minimizes the following empirical loss function
#
Ĉ() = (b+h)∫_-∞^∞ρ_τ(u)  d F̂(u;) , 
#
which can be solved via a linear program reformulation. The empirical loss function is nonsmooth
and poses significant challenges to developing a privacy-protection procedure.
To come up with an efficient algorithm
to estimate the optimal decision with 
provable privacy-preserving  guarantees, we
adopt convolution smoothing to address the challenge associated with the non-differentiability of
the loss function. This aims to simultaneously 
achieve two goals: (1) to have a feasible algorithm with 
privacy-preserving guarantee; (2) to have
an algorithm with a statistical accuracy guarantee
as measured by the accuracy of estimating ^*
and the regret, which is the cost gap
between the estimated policy from the algorithm and the clairvoyant benchmark.

The idea of convolution smoothing originates from <cit.> in a special case, and has been re-examined from a statistical perspective by <cit.>.
Specifically, let
F̂_ϖ(·;) be a 
smoothed estimator of the distribution function of ε_i() based on the classical Rosenblatt–Parzen kernel density estimator. That is, for u∈,
#
	F̂_ϖ(u;) = ∫_-∞^u f̂_ϖ(t;)  d   t     f̂_ϖ(t;) = 1/n K_ϖ (  t-ε_i() ) , #
where K_ϖ(u) := (1/ϖ) K(u/ϖ), 
K:ℝ→[0,∞) is a symmetric, non-negative kernel that integrates to one,  and ϖ=ϖ_n >0 is a smoothing parameter. We consider the following smoothed counterpart of Ĉ():

    Ĉ_ϖ() :=   (b+h)∫_-∞^∞ρ_τ(u)   dF̂_ϖ(u;) = b+h /n   (ρ_τ * K_ϖ) (d_i - _i^) ,

where “*" denotes the convolution operator that for any two measurable functions f and g, (f * g)(u) = ∫_-∞^∞ f(v) g(u-v)  d v. Therefore, Ĉ_ϖ is also referred to as the convolution-smoothed loss/cost function. Commonly used kernel functions in optimization and statistics include (i) Gaussian kernel K(u)=(2π)^-1/2e^-u^2/2, (ii) Laplacian kernel K(u) = e^-|u|/2, (iii) logistic kernel K(u) =e^-u/(1+e^-u)^2, (iv) uniform kernel K(u) =(1/2)1(|u|≤ 1), and (v) Epanechnikov kernel K(u) = (3/4) (1-u^2)1(|u|≤ 1). The following lemma shows that, given any symmetric kernel K and smoothing parameter ϖ>0, the resulting smoothed loss ρ_τ *K_ϖ provides an upper approximation of  ρ_τ with uniform approximation error that scales with ϖ.

 
Let K be a symmetric, non-negative kernel function with κ_1 := ∫_-∞^∞ |u| K(u)  du <∞. For any ϖ >0, it holds uniformly over u∈ℝ that ρ_τ(u) ≤ (ρ_τ *K_ϖ) (u) ≤ρ_τ(u) + κ_1 ϖ /2.


From Lemma <ref> we see that uniformly over ∈ℝ^p,
Ĉ () ≤Ĉ_ϖ() ≤Ĉ ()  + 0.5 κ_1(b+h)  ϖ. The analysis of the discrepancy between the respective minimizers necessitates a more nuanced examination and additional assumptions on the data-generating process. In the following subsection, we elucidate the assumptions necessary for the analysis of the privacy-preserving algorithm proposed for feature-based newsvendor problems. We also discuss their connections with the assumptions imposed in <cit.>.


To address the non-differentiability (at the origin) of the check loss, <cit.> proposed a more direct approach by replacing the indicator function 1(u<0) in ρ_τ(u) with G(-u/ϖ), where G(·) is a smooth, non-decreasing function that takes values between 0 and 1, and ϖ>0 is a smoothing parameter. However, Horowitz’s smoothing gains smoothness at the cost of convexity, which inevitably raises optimization challenges, 
particularly when dealing with a large number of features is large. On the contrary, provided a non-negative kernel is used, the convolution-smoothed loss ρ_τ * K_ϖ remains convexity, as its second derivative (ρ_τ * K_ϖ)^(2)(u) = K_ϖ(u) = K(u/ϖ) /ϖ is everywhere non-negative.  See Figure <ref> below for a visualization of Horowitz’s and convolution-smoothed check losses.

Using an approximate Hessian matrix, <cit.> proposed a Newton-type algorithm to solve Horowtiz's smoothed empirical loss minimization problem. In their convergence analysis, they assumed the initial estimator to be consistent, albeit at a sub-optimal rate. In contrast, our analysis imposes minimal assumptions on the initial value, as demonstrated in Theorems <ref> and <ref> in Section <ref>. To achieve differential privacy in their algorithm, it may be necessary to inject noise into both the gradient and the approximate Hessian of the empirical loss function. However, the theoretical analysis of their algorithm in the presence of inconsistent initial estimates is currently unknown.







The choice of the smoothing technique has an impact on the optimality of the algorithm.
Section A of <cit.> considered an example in the setting of hinge loss with 
Huberization method (quadratic smoothing)  and argued that it does not allow one to get the optimal excess risk bounds. An alternative popular smoothing method for minimizing a non-differentiable convex objective ↦Ĉ() is through Moreau-Yosida inf-convolution (or envelope) <cit.>. Recall that ρ_τ(u) = τ u 1(u > 0) - (1-τ) u1(u ≤  0). Its Moreau-Yosida envelop is given by

    ρ_τ^γ(u) = min_v∈ℝ{ρ_τ(v) + 1/2γ (u- v)^2 },

where γ>0 is the regularization parameter. It follows from standard calculations that 

    ρ_τ^γ(u) = 
        - (1-τ) u - 1/2(1-τ)^2 γ     u <  - (1-τ)γ , 
    1/2γu^2 ,        u ∈ [  - (1-τ) γ ,  τγ ],  
    τ u  - 1/2τ^2 γ      u >   τγ

and ( ρ_τ^γ)'(u) = τ1(u > τγ) - (1-τ) 1{ u < - (1-τ)γ}  + 1/γ u 1{   - (1-τ)γ≤  u ≤τγ}. 
When the convex loss is nonsmooth, i.e., not everywhere differentiable, <cit.> proposed a variant of the noisy stochastic gradient descent (SGD) algorithm and established upper bounds on the expected excess risk. Applying their general results to the check loss ρ_τ, it follows that the expected excess risk of the output from their (ϵ, δ)-DP algorithm is of order 

    O( √(p/n) + √(log(1/δ))p/ϵ n).

In Section <ref>, by proving a form of restricted strong convexity that holds with high probability, we will show that the expected excess risk of the proposed noisy GD estimator satisfies a faster rate, which is of the order

    O ( log(n) {p/n + (p+log n/μ n)^2 }) ,

where μ>0 is the privacy parameter for the Gaussian mechanism.







 §.§ Assumptions




Suppose we observe an i.i.d. sample { (d_i, _i) }_i=1^n from (d,) that follows a linear demand model d= ^^* + ε, where the observation noise ε is such that the conditional τ-th quantile of ε given  is 0 and τ=b/b+h.
Moreover, we assume that the conditional density function of ε|, denoted by f_ε |, exists and satisfies some regularity conditions described below. Compared to the linear model (18) considered in <cit.>, here we do not assume the independence between the observation noise ε and the random feature . Under the above model, the τ-th conditional quantile of
d given  is ^^*. Specifically, let F_d(· | ) be the conditional distribution function of d given . Then, the conditional τ-th conditional quantile of d given  is formally defined as Q_d(τ|) = inf{ u : F_d(u | ) ≥τ}.

Write =(x_1, _-^)^, where x_1 ≡ 1 and _- = (x_2,…, x_p)^ consists of the remaining random features. For theoretical analysis, we assume without loss of generality that μ_j  := (x_j) = 0 for j=2,…, p. Otherwise, it suffices to work with the demeaned model Q_d(τ|) =   β^♭_1 +   ∑_j=2^p (x_j - μ_j) β^*_j, where β^♭_1 = β^*_1 +∑_j=2^p   μ_j β^*_j.

To facilitate the analysis, we adopt the following technical conditions.
 
[Kernel function]  Let K(·) be a symmetric, non-negative, and Lipschitz continuous kernel function, that is, K(u)= K(-u), K(u) ≥ 0 for all u and ∫_-∞^∞ K(u)    du  = 1. Moreover, assume κ_u := sup_u∈ K(u) and κ_ℓ := ∫_-∞^∞ |u|^ℓ K(u)  du, ℓ=1,2 are bounded.

 
  
  [Feature distribution] 
 The random predictor _- ∈^p-1 is sub-Gaussian: there exists υ_1 ≥ 1 such that e^λ^_-  ≤ e^λ^2 υ_1^2 /2 for all λ∈ and ∈𝕊^p-2, where _-  = ^-1/2_- and = ( _- _-^) is positive definite. 
 
 
Under Condition <ref>,  the p× p matrix Σ = (^) is also positive definite. Let = Σ^-1/2=(1, _-^)^ denote the standardized feature vector satisfying (^) = _p and () = (1, _p-1^)^.

 
[Observational noise  ε=d - ^^*]   


There exist constants l_0>0 and f_u≥ f_l>0 such that |f_ε |(u) - f_ε |(u) | ≤ l_0 | u-v|, f_ε |(u) ≤ f_u  for all u, v ∈ almost surely (over ), and 
#
  inf_t∈[0,1],      ∈𝕊^p-1    {  f_ε|(t ⟨, ⟩) ⟨, ⟩^2 }  ≥f_l . 
#


 
Below, we discuss how Conditions <ref> and <ref> are comparable to Assumptions 1 and 2 in <cit.>. For the random feature vector =(1, _-^)^∈^p, <cit.> assumed that the coordinates of _- are normalized with mean zero and standard deviation one, and _2 ≤ C√(p) for some constant C>0. Condition <ref>, on the other hand, requires feature vector  to be sub-Gaussian, extending the concept of sub-Gaussian random variables to higher dimensions through one-dimensional marginals. Examples of such sub-Gaussian vectors include: (i) Gaussian and Bernoulli random vectors, (ii) spherical random vectors,1 (iii) random vectors uniformly distributed on the Euclidean ball centered at the origin with radius √(p), and (iv) random vectors uniformly distributed on the unit cube [-1, 1]^p. We refer to Chapter 3.4 in <cit.> for detailed discussions on multivariate sub-Gaussian distributions. For sub-Gaussian features vectors _i's, from Theorem 2.1 in <cit.> it follows that max_1≤ i≤ n_i _2 ≲√(p+log n) with high probability. For the observation noise ε,  <cit.> assumed that its density function, denote by f_ε, is bounded away from zero on some compact interval [D, D]. In Condition <ref>, it is worth noticing that the constant f_l may depend on both the conditional distribution of ε given , and the distribution of ∈^p. To see this, define ι_δ = inf{ι >0 :  ⟨ , ⟩^2 1_{|⟨ , ⟩| > ι}≤δ ∈𝕊^p-1} for δ∈ (0,1]. It is easy to see that δ↦ι_δ is non-decreasing and ι_δ≤ (m_q/δ)^1/(q-2) for any q>2, where m_q := sup_∈𝕊^p-1 | ⟨, ⟩|^q. Then, a sufficient condition for (<ref>) is min_|t|≤ι_δ f_ε |(t) ≥ c_δ  >0 almost surely (over ) for some 0<δ<1, because
$
     inf_t∈[0,1],      ∈𝕊^p-1    {  f_ε|(t ⟨, ⟩) ⟨, ⟩^2 }   ≥c_δinf_ ∈𝕊^p-1    { ⟨, ⟩^2 1  ( | ⟨, ⟩| ≤ι_δ) }  ≥(1-δ)c_δ.
$ 




§ A PRIVACY-PRESERVING ALGORITHM FOR FEATURE-BASED NEWSVENDOR PROBLEM





 §.§ Preliminaries on f-differential Privacy



We will first review the (ϵ, δ)-differential privacy concept introduced in <cit.>. Let 𝒮 denote a data set consisting of observations {_1,…, _n}, where _i=(d_i, _i), i=1,…,n. A pair of data sets 𝒮 and 𝒮' are said to be neighboring data sets if they differ in only one data point.


((ϵ, δ)-differential privacy or (ϵ, δ)-DP)
A randomized algorithm M is (ϵ, δ)-differentially private if 
for any neighboring data sets 𝒮 and 𝒮', and any event 
ℰ, we have

    P(M(𝒮)∈ℰ) ≤ e^ϵP(M(𝒮')∈ℰ)+δ,

where ϵ≥ 0 and 0≤δ≤ 1 are constants.


An intuitive way to understand the concept of (ϵ, δ)-differential privacy is via the lens of a hypothesis testing problem for distinguishing two neighboring  data sets 𝒮 and 𝒮':

    H_0:     
        H_1: '.

Consider any given test procedure ϕ based on the output of the randomized algorithm M, and denote its type I error and type II error by α_ϕ and β_ϕ, respectively. It can be shown that for a test ϕ based on the output of any (ϵ, δ)-differentially private algorithm, its power is bounded by min{e^ϵα_ϕ+δ, 1-e^-ϵ(1-α_ϕ-δ)}. If ϵ and δ are both small, then any α-level (0<α<1) test will be nearly powerless.


<cit.> extended <cit.>
by introducing the trade-off function to characterize the trade-off between the type I and type II errors.




(trade-off function <cit.>) For any two probability distributions P
and Q, the trade-off function T(P,Q): [0, 1]→ [0,1]
is defined as T(P,Q)(α)=inf{β_ϕ: α_ϕ≤α},
where the infimum is taken over all measurable rejection rules to distinguish P and Q.


The greater the trade-off function is, the harder it
is to distinguish the two distributions via hypothesis testing. 
<cit.> showed that a function 
f: [0,1]→ [0,1] is a trade-off function if and only if f
is convex, continuous, nonincreasing and f(x)≤ 1-x for all x∈ [0,1].
In the following, for any two functions f and g defined on [0,1], we write
g≥ f if g(x)≥ f(x), ∀ x∈ [0,1]. 
We abuse the notation a little by identifying 
𝒮 and 𝒮' with their 
respective probability distributions.


(f-differential privacy or f-DP <cit.>)
A randomized algorithm M is said to be f-differentially private if 
for any neighboring data sets 𝒮 and 𝒮'

    T(𝒮,𝒮')≥ f

for some trade-off function f.


If f=T(P, Q) for some distributions P and Q,
then a mechanism M is f-DP if distinguishing any two neighboring datasets based on the output of M 
is at least as difficult as distinguishing P and Q
based on a single draw.
This functional perspective avoids some of the pitfalls associated with (ϵ, δ)-differential
privacy. f-DP is a generalization of  
(ϵ, δ)-DP. A result of 
<cit.>
indicates that
a mechanism M is (ϵ, δ)-DP
if and only if M is f_ϵ, δ-DP
where 
f_ϵ, δ(α)
=max{0, 1-e^ϵα_ϕ-δ, e^-ϵ(1-α_ϕ-δ)}.




(Gaussian differential privacy <cit.>)
A randomized algorithm M is said to satisfy 
μ-Gaussian differential privacy if 
for any neighboring data sets 𝒮 and 𝒮'

    T(𝒮,𝒮')≥ G_μ

where G_μ(α)=Φ(Φ^-1(1-α)-μ)
and Φ is the distribution function of the
standard normal distribution.




GDP provides a parametric family of f-DP
that guarantees and enjoys many desirable properties. As a rule of thumb, μ≤ 0.5 guarantees a reasonable amount of privacy, 
μ=1 is borderline private,
and μ>6 promises almost no privacy guarantee. The trade-off of Type I and type II errors is illustrated in 
Figure <ref>. 






 §.§ Proposed Differentially Private Algorithm


To obtain a differentially private counterpart of _ϖ = _Ĉ_ϖ(), we draw inspiration from works <cit.> and <cit.> and utilize a noisy optimization approach that involves adding Gaussian noise during each iteration of the gradient descent method.
Minimizing the loss function Ĉ() used in <cit.> poses a challenge as it is convex but not differentiable everywhere, and subgradient methods commonly employed for such cases exhibit slow (sublinear) convergence, leading to computational instability. 
In this work, we propose a differentially private algorithm that leverages convolution smoothing and noisy gradient descent. Its privacy protection guarantee is established in Theorem <ref>
in Section <ref>.
We further investigate its finite sample performance in Section <ref> and demonstrate that the proposed approach achieves a balanced trade-off between statistical accuracy and computational stability, owing to the effectiveness of convolution smoothing.

Given a non-negative kernel function K(·) introduced earlier, we define

    K̅(u) = ∫_-∞^u K(v) dv     K̅_ϖ(u) = K̅(u/ϖ),

so that K̅'_ϖ(u) = K_ϖ(u). If the p × p matrix Σ= (^) were known, we consider the following noisy smoothed gradient descent method, starting at iteration 0 with an initial estimate ^(0). At iteration t= 0 , 1, 2, …, T-1, we update the solution as follows

    ^(t+1)  = ^(t) -  η_0/nΣ^-1/2[  {K̅_ϖ(_i^^(t) - d_i ) - τ}    w_B(_i)    +    σ_t ]  ,

where _i = Σ^-1/2_i denotes the standardized covariates vector in the sense that (_i _i^) = _p, w_B() =  / max{ 1 , _2/ B }, and _t ∈^p (t=0, 1,…, T-1) are independent (,   _p ) vectors.  Here, η_0>0 is the step size, T≥ 1 is a prespecified number of iterations,  B≥ 1 is a truncation parameter,  and σ is a positive constant
adjusting the level of noise injected into the gradient perturbation.
We summarize this procedure in Algorithm <ref>.


The presence of Σ in Algorithm <ref> is primarily for theoretical convenience as it allows us to establish upper bounds on the estimation error {^(_ϖ - ^*)}^2 by expressing it as Σ^1/2 (_ϖ - ^*  ) _2^2, where the expectation is only taken with respect to  that is independent of _ϖ.
When Σ is unknown, we consider the following update 

    ^(t+1)  = ^(t) -   η_0/n[ {K̅_ϖ(_i^^(t) - d_i ) - τ}    w_B(_i)  +    σ_t  ]

with a slight abuse of notation.


In both (<ref>) and (<ref>),   the use of covariate clipping/truncation guarantees a bounded ℓ_2-sensitivity of the gradient function, which is the key to achieving differential privacy. For the initial value, one can take ^(0) to be either  or a random guess that is uniformly distributed over the unit sphere.








 §.§ Privacy-protection Guarantee of the Proposed Algorithm


We first review some useful results about f-DP. 



 
(Theorem 1 in <cit.>)
Define the Gaussian mechanism that operates on a statistic θ
as M(𝒮)=θ(𝒮)+ξ,
where ξ∼(0, (θ)^2/μ^2),
and the sensitivity (θ)=sup_𝒮,𝒮'
|θ(𝒮)-θ(𝒮')| with the supremum over all neighborhood data sets 𝒮 and 𝒮'.
Then M is μ-GDP.
 

A nice property of f-DP is that the composition of private mechanisms is closed and tight in the f-DP framework. 
A two-step composition can be written as
M(𝒮)=(y_1, M_2(𝒮, y_1)),
where y_1=M_1(𝒮) with
M_1: X→ Y_1 being the first mechanism,
and M_2: X× Y_1→ Y_2
is the second mechanism. 
In general, given a sequence of
mechanisms M_i: X× Y_1×⋯× Y_i-1→ Y_i, i=1,…,n, we consider the n-fold composed mechanism:
M:X→ Y_1×⋯× Y_n.


The tensor product of two trade-off functions f=T(P,Q)
and g=T(P',Q') is f⊗ g=T(P× P', Q× Q').


 
(Theorem 4 in <cit.>)
Let M_i(·, y_1,…, y_i-1) be f_i-DP for all
y_1∈ Y_1, …, y_i-1∈ Y_i-1. Then the n-fold composed mechanism 
M: X→ Y_1×⋯ Y_n is f_1⊗⋯⊗ f_n-DP.
 

 (Corollary 2 in <cit.>)
The n-fold composition of μ_i-GDP mechanisms is
√(μ_1^2+…+μ_n^2)-GDP.




<cit.> revealed that the Gaussian mechanism in Proposition <ref> satisfies G_μ(α)=inf _neighboring  S, S^' T(M(S), M(S^'))(α). For all possible type I error rate α, the infimum could be achieved at two neighboring data sets which satisfy |θ(S)-θ(S^')| = sens(θ). This implies that the characterization by GDP is precise in the pointwise sense. GDP offers the tightest possible privacy bound of the Gaussian mechanism. 



Theorem <ref> below establishes the Gaussian differential privacy property of the proposed algorithm. For any given
sample size n, number of iterations T and noise scale
σ, the output of the algorithm ^(T)
satisfies the Gaussian differential privacy property with privacy level μ as outlined in the theorem.


  (Privacy-protection guarantees)
Given an initial estimate ^(0)∈^p and a dataset _n = { (d_i, _i ) }_i=1^n,  consider the noisy gradient descent iterates {^(t)}_t=0, …, T defined in (<ref>). Given a privacy level μ>0,
if σ>0
satisfies σ≥  2τ̅B T^1/2/μ with τ̅= max(τ, 1-τ), then   
the final output ^(T) is μ-GDP.


Proof of Theorem <ref>
Consider two datasets _n and '_n that differ by one datum,  say (d_1, _1) ∈_n versus (d_1', _1')∈_n'.  At the first iteration, note that
$
	      Σ^1/2 ^(1) (_n) -Σ^1/2 ^(1) ('_n) _2  

	      =  η_0/n   { K̅_ϖ(⟨_1  ,  ^(t)  ⟩- d_1) - τ}    w_B(_1)  - { K̅_ϖ( ⟨_1' ,  ^(t)  ⟩- d'_1 ) - τ}    w_B('_1)   _2 

	     ≤2  max( 1-τ, τ)  B  η_0/n = 2τ̅B  η_0  /n .
$
By Proposition 1,  Σ^1/2^(1) is (T^-1/2μ)-GDP as long as σ≥ 2τ̅B T^1/2  / μ. After post-processing (by a deterministic map), ^(1) is also (T^-1/2μ)-GDP.


By definition,  the second iterate ^(2) = ^(2) (_n) takes ^(1) as  input  in addition to the dataset.  Together, Proposition 2 and Corollary 1 show that the two-fold composed (joint) mechanism (^(1) , ^(2) ) is √(μ^2/T + μ^2/T)-GDP.
Using the same argument repeatedly, we conclude that the T-fold composed mechanism (^(1) ,  …, ^(T) ) is μ-GDP, and  hence  so is  ^(T). 

 

 


§ THEORETICAL PERFORMANCE



Theorem <ref> in Section <ref> establishes the privacy-protection guarantees 
of the proposed new algorithm.
This section provides a statistical analysis of the privacy-preserving coefficient estimate ^(T) under Conditions <ref>–<ref> from Section <ref>. 
Section <ref> provides upper bounds for the finite-sample bias of the estimated optimal policy both in high probability and under expectation. Section <ref> provides the regret analysis. To prove these bounds, the main technical challenge is that the empirical cost function after convolution smoothing does not satisfy the local strong convexity as required in <cit.>.
We provide main proof strategies and important intermediate results in Section <ref>.







 §.§ Performance Bound on Estimation Error



The parameter indexing the clairvoyant optimal policy, where the demand distribution is known a priori is given by
(<ref>): 
^*=_:  q()=  ^{ C(q(), d))|} . 
Given a feature vector , the clairvoyant optimal
to-order-quantity is ^^*. Given an estimate  of the unknown parameter ^* based on a random, independent
sample { (d_1, _1), …, (d_n, _n) } of size n drawn from the linear demand model, we use the following two metrics to evaluate its performance: (i) the estimation error - ^* _2 under the vector ℓ_2-norm or its variant, and (ii) the excess (population) risk C() - C(^*), where C(· ) is defined in (<ref>).


With a predetermined bandwidth ϖ>0, step size η_0>0, truncation level B≥ 1, number of iterations T≥ 1, and noise scale σ=2τ̅B T^1/2/μ, let ^(T) be the μ-GDP estimator of ^* obtained from Algorithm <ref>, where τ̅= max(τ, 1-τ).
Our first theorem provides upper bounds for the estimation error ^(T)  - ^* _Σ both in high probability and under expectation, where ·_Σ denotes the Σ-induced norm, that is, _Σ = √(^Σ) for ∈ℝ^p. 


 
In addition to Conditions <ref>–<ref>, assume κ_l := min_|u|≤ 1 K(u) >0. Let the triplet of parameters (ϖ, B, T) and sample size n satisfy 
#
    ϖ≍(  p+ logn/n )^1/4,   B ≍√(p+logn),   T ≍logn       n ≳T^1/2    p+ logn/  μf_l   . 
#
Moreover, let the step size η_0 satisfy 0<η_0 ≤ 1/max(  2 f_u ,  f_l + τ̅). Then, the μ-GDP estimated coefficient ^(T) obtained from noisy gradient descent initialized at any ^(0)∈^* + Θ_Σ(1) satisfies
$
	  ^(T) - ^*   _Σ≤C_0 ( η_0 T^1/2  p + logn /   μn +  1/f_l √(p logn/n)   )    1- C_1/n^2   
$
and
$
  ^(T) - ^*   _Σ≤C_2 √(logn)( η_0 p + logn /   μn + 1/f_l√(p /n)   ) ,
$
where C_0, C_1 and C_2 are positive constants independent of (n, p).


As a benchmark, we use _ϖ to denote the non-private empirical (smoothed) risk minimizer, that is, _ϖ = _∈^pĈ_ϖ() with Ĉ_ϖ(·) defined in (<ref>).
From the proof of Theorem <ref> we see that the second term on the right-hand side upper bound is the bound on the estimation error of _ϖ, which is of order √(p/n) with a properly chosen smoothing parameter ϖ <cit.>. The first term quantifies the “cost of privacy" of the noisy gradient descent algorithm for solving the feature-based newsvendor problem. For sufficiently small values of μ, the obtained upper bound (on ·_Σ-error) matches the minimax lower bound, up to logarithmic factors, for (μ, δ)-DP estimation of ^* under a linear model with normal errors; see Theorem 4.1 in <cit.>. By Corollary 1 in <cit.>, an algorithm is μ-GDP if and only if (μ, δ(μ))-DP, where δ(μ) = Φ(-1+μ/2) - e^μΦ(-1-μ/2).





 §.§ Regret Analysis



We next provide a finite-sample analysis of the regret C(   ^(T)) - C( ^*), where C() = {Ĉ() } is as in (<ref>). 
The regret is the difference between the expected cost obtained with the estimated privacy-preserving optimal policy and the clairvoyant optimal expected cost with known demand distribution but without privacy protection.

Without loss of generality (up to a constant scale),
we consider the regret of ^(T), defined as Q(^(T)) - Q(^*) = Q(^(T)) - inf_∈ℝ Q(), where Q() = (b+h)^-1  C() ={ρ_τ(d- ^) } with τ=b/(b+h) is the population cost (without smoothing). Recall that the coefficient ^* indexing the optimal inventory policy satisfies the first-order condition ∇ Q(^*) =. By the mean value theorem and Condition <ref> that sup_u∈ℝ f_ε | (u) ≤ f_u, it can be shown that Q() - Q(^*) = Q() - Q(^*) - ⟨∇ Q(^*),  - ^* ⟩≤ 0.5 f_u  - ^* _Σ^2 for any ∈ℝ^p. This, combined with Theorem <ref>, implies the following high probability upper bound on the regret along with an expected regret bound.


 
(High probability bound for excess risk)
Under the same set of assumptions in Theorem <ref>,  we have

    Q(^(T)  ) - Q(^*)  ≲log(n) {1/f_u(  p + log n/μ n)^2  + f_u/f_l^2p/  n}

with probability at least 1-C_1 n^-2.


 (Excess population risk bound)
Under the conditions of Theorem <ref>,

the excess population risk bound satisfies

    { Q(^(T)  ) - Q(^*) }≲log(n) { f_u^-1 (p+log n)^2/(μ n)^2 + (f_u/f_l^2)  ·   p /n }.



For fixed cost parameters b and h, the bound (<ref>) indicates that if the number of relevant features p is small relative to the number of observations in the sense that plog n = o(n), the expected cost of the μ-GDP estimated decision converges to that of the optimal decision at a fast rate O( p/n +  μ^-2 (p/n)^2 ), up to logarithmic factors. Without privacy guarantees, <cit.> obtained a similar performance bound, which implies consistency but under a stronger condition on the number of features, that is, p^2 = o(n).





 §.§ Proof Strategy and Key Intermediate Results




The statistical analysis of the noisy gradient descent iterates {^(t)}_t=1,…, T depends crucially on the landscape of the empirical loss function, as highlighted in recent research <cit.>. Unlike many commonly used loss functions in statistical learning,  such as squared loss, Huber loss (and its smoothed variants), and logistic loss, the quantile loss ρ_τ exhibits piecewise linearity, which lacks local strong convexity.  Instead, its “curvature energy” is concentrated in a single point. Notably, the local strong convexity and smoothness of Q̂_ϖ(·) are intricately influenced by the bandwidth used in the analysis.

In this study, we present the key findings for analyzing the landscape of Q̂_ϖ(·).  Specifically, we illustrate that by conditioning on a series of “good events” related to the empirical smoothed cost function,   the proposed noisy gradient descent iterates exhibit favorable convergence properties. Moreover, we demonstrate that these good events will occur with high probability under Conditions <ref>–<ref>.   We conclude this section with a supplementary analysis of the initialization of the algorithm.

 


Given a kernel function K(·) and bandwidth ϖ >0, we define the empirical smoothed loss

    Q̂_ϖ() =  (b+h)^-1Ĉ_ϖ()   = 1/n (  ρ_τ * K_ϖ  ) _=:  ℓ_ϖ ( d_i - _i^),

where “*" is the convolution operator. Its gradient and Hessian are given, respectively, by
$
 ∇_ϖ() =  1/n { K̅_ϖ( _i^- d_i ) - τ} _i      ∇^2 _ϖ() = 1/n K_ϖ( d_i - _i^) _i _i^.
$
Let Q() = {Q̂() } and Q_ϖ() = {_ϖ()} be the population quantile and smoothed quantile losses, respectively. Note that although the parameter ^* indexing the theoretically optimal inventory policy satisfies the moment condition ∇   Q(^*) =, in general, ∇ Q_ϖ(^*) ≠. Therefore, we use

    b^* := Σ^-1/2∇ Q_ϖ(^*) _2 = {K̅_ϖ( ^^* - d) - τ}_2
 
to quantify the smoothing bias. Together, Condition <ref> and the Lipschitz continuity of f_ε|(·) ensure that b^* ≤ 0.5 l_0 κ_2  ϖ^2; see Lemma 1.3 in the supplementary material. 


For any r>0, define the local ellipses centered at the origin and ^*, respectively, as
$
	 Θ_Σ(r) =  { ∈^p:  _Σ ≤r }      Θ_Σ^*(r)    = { ∈^p:  - ^* _Σ ≤r }  .
$
Moreover, for every ∈^p,  we write 
#
	 D̂_ϖ()       = _ϖ() - _ϖ(^* )       D_ϖ() = { D̂_ϖ() }     = - ^*.       
#
Given parameters B,  R ≥ 1 and δ_0 , δ_1 >0,  define the “good events”
#
  _0(B )     = { max_1≤i≤n   _i _2 ≤B  }   ,  

 _1(δ_0,  δ_1 )  
    = {    | D̂_ϖ() - D_ϖ() | ≤δ_0   _Σ   ∈Θ_Σ(1)∖Θ_Σ(1/n)    }     
 
             ∩{     ∇_ϖ() - ∇Q_ϖ() _Σ^-1 ≤δ_1     ∈Θ_Σ^*(1) }  , 

 _2(R)     =    {     ∇^2 _ϖ() - ∇^2 Q_ϖ() _Σ^-1 ≤f_u    ∈Θ_Σ^*(R) }  .  
#  
Here we write _Σ^-1 = Σ^-1/2Σ^-1/2_2 for any p× p matrix . In the following, we will restrict our analysis to the intersection of the above events.


    (Restricted strong convexity and smoothness)
Let 0< ϖ≤ f_l /(2 l_0κ_1 ) and set ϕ_1= 0.5(f_l - l_0 κ_1 ϖ) ≥ 0.25f_l > 0. Then, conditioned on the event _1(δ_0,δ_1) ∩_2(R), we have
#
       Q̂_ϖ() - _ϖ(^* )   

     ≥
ϕ_1  - ^* _Σ^2 -  (δ_0 + b^*  )  - ^* _Σ          ∈Θ_Σ^*(1)∖Θ_Σ^*(1/n) 
  
 ( ϕ_1 - δ_0  - b^*   )  - ^* _Σ        ∈Θ_Σ^*(1)^  ,  
#
#
     _ϖ(^*) - _ϖ()  -  ⟨∇_ϖ(), ^* - ⟩

                             ≥ϕ_1  - ^* _Σ^2 -  (δ_0 +  δ_1 )  - ^* _Σ    ∈Θ_Σ^*(1)∖Θ_Σ^*(1/n) ,   
#
and
#
          Q̂_ϖ(_2) - _ϖ(_1 ) - ⟨∇_ϖ(_1) , _2 - _1 ⟩≤f_u     _2 - _1 ^2_Σ    _1, _2 ∈Θ_Σ^*(R) .  
# 



Note that the lower bound (<ref>) implies a restricted strong convexity (RSC) for _ϖ() when ∈Θ_Σ^*(1) / Θ_Σ^*( n^-1∨   r_1  ) with r_1  = (δ_0+δ_1)/ϕ_1. The upper bound (<ref>) is related to the local strong smoothness of the empirical cost, which no longer holds without convolution smoothing. In addition, we define a “good” event on which the smoothed empirical loss Q̂_ϖ(·) satisfies a refined RSC property. Given a radius r > 0 and a curvature parameter ϕ_2∈ (0, f_l), define 

    ℰ_3(r, ϕ_2) = {inf__1 ∈^* + Θ_Σ(r/2),  _2 ∈_1 + Θ_Σ(r) Q̂_ϖ(_1) - Q̂_ϖ(_2) - ⟨∇Q̂_ϖ(_2), _1 - _2 ⟩/_1 - _2  _Σ^2≥ϕ_2 }.

Now we are ready to present the following general upper bound on the estimation error conditioning on the above good events.
 

 
Assume Conditions <ref> and <ref> hold, ^(0)∈Θ_Σ^*(1)  and let (ϖ, η_0) satisfy 0< ϖ≤ f_l /( 2l_0 κ_1) and 0<η_0 ≤ 1/ max(2f_u, f_l+τ̅), where τ̅= max(τ, 1-τ). Set R=2, and let δ_0, δ_1>0 be such that
#
 r_0 :=   (δ_0+b^* )/ϕ_1  < 1       r_1 :=  (δ_0 +δ_1)/ϕ_1  ≤1     , 
#
where ϕ_1 = 0.5 (f_l - l_0 κ_1 ϖ ).
Moreover, let Δ = ϕ_1 - δ_0 - b^* ∈ (0, f_l/2) and ϵ = η_0 ϕ_1   ∈ (0, 1/2). For any z≥ 0,  let the sample size satisfy
#
   n ≥σ  p^1/2 + √(2 (logT + z) )    / Δ   . 
#
Then, conditioned on  the event _0(B)∩_1(δ_0,δ_1 ) ∩_2( 2), the noisy gradient descent iterate ^(T) with T ≥ 2 log( n)/ log( (1- ϵ )^-1 ) satisfies
#
	  ^(T)  - ^* _Σ≤r^* : =  √(  1/n^2  +(1+1/ϵ)   {       (2p/ϵ+ 3z)  ( η_0 σ/n )^2  +  (r_0 ∨r_1)^2 } )     
#
with probability (over the i.i.d. normal vectors {_t}_t=0^T-1) at least 1-2e^-z. Moreover, the non-private empirical (smoothed) risk minimizer satisfies _ϖ - ^* _Σ≤ r_0.

Let r=r^* + r_0. Conditioned further on ℰ_3(r, ϕ_2), ^(T) with T≥ 3log(n) / log((1-ϵ)^-1) satisfies
#
  ^(T) - _ϖ_Σ≤r^†:= √(r^2/n + (1+1/ϵ) (2p/ϵ+ 3z) (η_0 σ/n )^2 ) 
 
#
with probability (over the i.i.d. normal vectors {_t}_t=0^T-1) at least 1-2e^-z.



Under local strong convexity and smoothness conditions, <cit.> established statistical convergence guarantees for private M-estimators obtained via noisy gradient descent. Let ℒ_n: ℝ^p →ℝ be a general (empirical) loss function of interest, and Θ⊆ℝ^p be the parameter space. As high-level conditions, <cit.> assumed that ℒ_n is locally τ_1-strongly convex and τ_2-smooth, that is,

    ℒ_n(_1) -  ℒ_n(_2) ≥⟨∇ℒ_n(_2) , _1-_2 ⟩ + τ_1 _1 - _2 _2^2 ,   ∀_1, _2 ∈{∈ℝ^p:  - ^* _2 ≤ r }

for some r>0, and ℒ_n(_1) -  ℒ_n(_2) ≤⟨∇ℒ_n(_2) , _1-_2 ⟩ + τ_2 _1 - _2 _2^2, ∀_1, _2 ∈Θ. To our knowledge, it remains uncertain whether the aforementioned local strong assumption holds with high probability for either the empirical newsvendor loss Q̂ or its convolution-smoothed counterpart Q̂_ϖ. Therefore, a more delicate argument is required to analyze the convergence of noisy gradient descent iterates obtained from Algorithm <ref>. Our proof of Theorem <ref> crucially relies on the structural properties of Q̂_ϖ stated in Proposition <ref>. In Proposition <ref> below, we will show that the event conditioned on in Proposition <ref> holds with high probability. 



The proof of the error bound _ϖ - ^* _Σ≤ r_0 in Theorem <ref>, which holds conditioning on event _1(δ_0, δ_1), extends the argument in <cit.>. The main contribution of Theorem <ref> is to establish finite sample performance bounds for the noisy gradient descent iterates {^(t)}_t=1^T in a sequential manner, which involves a more intricate analysis compared to that for the non-private empirical (smoothed) risk minimizer _ϖ. More specifically, the analysis conducted in <cit.> necessitates that the empirical loss satisfies only condition (<ref>),  while our approach requires a more comprehensive version of the restricted strong convexity property (<ref>). 
We also establish a connection between statistical theory and algorithmic complexity, demonstrating that to achieve a statistically efficient estimator as shown in Theorem <ref>, the computational complexity is of order O(n p log(n)). In contrast, the conventional interior-point method commonly used for solving the LP reformulation of empirical check loss minimization demands a significantly higher average-case computational complexity of O_P(n^1.25 p^3 log n) <cit.>.


The convergence result stated in Theorem <ref> relies on the assumption that the initial value ^(0) falls within the neighborhood Θ^*_Σ(1), which we term as the tightening region. In each iteration of the noisy gradient descent, the current estimate contracts towards the true parameter, progressively moving closer to the region of near-optimal convergence.


In general, let us define R_0:= ^(0) - _ϖ _Σ to be the distance between the initial value ^(0) and the non-private empirical risk minimizer _ϖ.  The following result presents the number of iterations necessary for the noisy gradient descent to enter the tightening region.


 


 
Assume Conditions <ref> and <ref> hold, and let (ϖ, η_0) satisfy 0< ϖ≤ f_l /( 2l_0 κ_1) and 0< η_0 ≤min{ 1, 1/(2f_u) }. Without loss of generality, assume R_0 = ^(0) - _ϖ _Σ > 1, and let

    Δ = ϕ_1 - δ_0 - b^* ∈ (0, f_l/2),    r_0 = (δ_0 + b^*)/ϕ_1 ∈ (0, 1) ,
 
where ϕ_1 = (f_l - l_0 κ_1 ϖ ) /2. Given z≥ 0, let the number of iterations T_0 and sample size n satisfy
#
 T_0 ≥R_0^2/η_0 Δ    
 n ≥2 B_T_0 σmax{    2 R_0 + (τ̅B + 1/4) (T_0+1) η_0 /Δ ,  e-1/4-e( τ̅B + 1/4 ) T_0  } , 
#
where B_T_0 = √(p) + √(2(log T_0 + z) ).
Then, conditioned on _0(B) ∩_1(δ_0, δ_1) ∩_2(R) with R= 2 R_0 + r_0,  the noisy gradient descent iterate ^(T_0) satisfies 

    _ϖ(^(T_0)  ) - _ϖ(_ϖ) ≤Δ    ^(T_0)  - ^* _Σ≤ 1
 with probability (over normal vectors {_t}_t=0^T_0-1) at least 1-e^-z.
 



The aforementioned high-level findings demonstrate that, given a sequence of “good events” associated with the empirical smoothed cost function, the proposed noisy gradient descent iterates exhibit desirable convergence properties. To complement this deterministic analysis, we further provide probabilistic bounds, which subsequently yield finite sample performance bounds as presented in Sections <ref> and <ref>.

 
 

 
Assume Conditions <ref>–<ref> hold.  Given R>0,  for any z>0 we have that with probability at least 1-5e^-z,
#
	 max_1≤i≤n   Σ^-1/2 _i _2     ≤C_0 υ_1 √( p + log(n) + z  ) ,  

	 sup_∈Θ_Σ(1) ∖Θ_Σ(1/n)  | D̂_ϖ() - D_ϖ() | / _Σ     ≤C_1  υ_1   √(p + log_2(n) + z /n ), 

	  sup_∈Θ^*_Σ(1)    ∇_ϖ() - ∇Q_ϖ() _Σ^-1      ≤C_2 υ_1 √(p log(n/ϖ) + z/n) +  f_u ϖ+  2 κ_u/n #
and  
#
      sup_∈Θ^*_Σ(R)    ∇^2 _ϖ() -∇^2 Q_ϖ() _Σ^-1 
  

      ≤C_2 υ_1^2 {    √(p log(n/ϖ) + z/n ϖ) + p log(n/ϖ) + z/ n ϖ } + C_2'  R υ_1 ( p + logn + z)^1/2 + l_0 m_3 ϖ^2 /n^2 , #
provided that n≳υ_1^4 (p + z), where C_0, C_1, C_2, C_2'>0 are absolute constants. 
Moreover,  b^*  = ∇ Q_ϖ(^*) _Σ^-1≤ 0.5 l_0 κ_2 ϖ^2 and ∇^2 Q_ϖ(^*) _Σ^-1≤ f_u.





 In addition to Conditions <ref>–<ref>, assume 
$
	κ_l := min_|u|≤1 K(u) >0     inf_|u|≤1 1/2 u ∫_-u^u f_ε| (v) d v ≥f'_l   
$
for some f'_l>0.  Let r_ loc = ϖ/(16max{ m_4, 3}^1/4υ_1). Then, for any z>0, we have that with probability at least 1-e^-z,
#
Q̂_ϖ(_1) - Q̂_ϖ(_2) - ⟨∇Q̂_ϖ(_2) , _1 - _2 ⟩≥ϕ_2  _1 - _2 _Σ^2    
#
holds uniformly over _1 ∈^* +  Θ_Σ(r_ loc/2) and _2 ∈_1 + Θ_Σ(r_ loc),  provided that the “effective sample size” n ϖ satisfies n ϖ≳ m_4^1/2υ_1^2(  p + z), where ϕ_2>0 is a constant depending only on (κ_l, f'_l).
 


Let the sample size n and bandwidth ϖ = ϖ_n >0 satisfy
n ϖ≳ p log n and ϖ≲{(p+log n)/n}^1/4.
Then, Proposition <ref> implies b^* ≲√((p+log n)/n) and event _0(B) ∩_1(δ_0, δ_1) ∩_2(2) with (B, δ_0, δ_1) satisfying
$
		B ≍√(p + logn) ,     δ_0 ≍√(p+ logn/n)     
		δ_1 ≍√(p logn/n )
$
occurs with high probability. Combining this with Theorem <ref> implies the finite sample performance bounds in Theorem <ref>.

Moreover, under the additional assumptions stated in Proposition <ref>, there exist some curvature parameter ϕ_2 > 0 and a local radius r_ loc≍ϖ such that the event ℰ_3(r_ loc, ϕ_2) also occurs with high probability. This further implies that the μ-GDP estimate ^(T), obtained from noisy gradient descent initialized at any ^(0)∈^* + Θ_Σ(1), satisfies with probability at least 1-Cn^-1 that

    ^(T) - _ϖ_Σ≲√(log n)/(f_l ∧ f_l')^2p+log n/μ n.

Here, we implicitly assume that both the smoothing parameter ϖ and the number of iterations T are chosen appropriately. The above bound, in turn, implies that the excess (smoothed) empirical risk is bounded with high probability by

    Ĉ_ϖ(^(T)) -  Ĉ_ϖ(_ϖ) =   Ĉ_ϖ(^(T)) -  min_∈ℝ^pĈ_ϖ( ) ≲log n ( p+log n/μ n)^2.

The above rate also matches (up to a logarithm factor) the one in <cit.> for Lipschitz and strongly convex loss functions (after adjusting for scaling differences).



§ NUMERICAL AND EMPIRICAL STUDIES



In this section, we utilize synthetic data as well as real-world data to showcase the empirical performance of the proposed privacy-preserving feature-driven policy. We compare its performance against that of the theoretically optimal policy, which assumes known demand but lacks privacy protection measures. For the sake of simplicity and consistency, we employ the Gaussian kernel in all of our numerical experiments.



 §.§ Synthetic Data


We consider the linear demand model d = ^^* + ε, where ^* = (1.5,1,-2.5,-1.5,3)^∈ℝ^5 and ^ = (1,^)^. The feature vector ∈ℝ^4 is generated from a centered multivariate normal distribution with covariance matrix Σ= ( 0.5^|j-k|)_1≤ j, k ≤ 4. Independent of the feature vector , the observation noise variable ε  follows one of the following three distributions: (i) standard norm distribution (0,1), (ii) t-distribution with 3 degrees of freedom (t_3), and (iii) Gaussian mixture distribution 0.9 (0,1)+0.1 (0,100). 






In all of our numerical experiments, we set b+h = 1 so that with the distribution of ε known as a priori information, the optimal quantity to order can be determined by the τ-th quantile of the conditional distribution of d given , where τ =b. Specifically, the clairvoyant optimal policy is ^^* with
^* = ^* + (Q_ε(τ),0,0,0,0)^, where Q_ε(·) denotes the quantile function of ε.

 
For the hyper-parameters in the noisy gradient descent method, we set T = 10, B = 2 and σ = ⌈ 2τ̅BT^1/2/μ⌉, where μ∈{ 0.3,0.5,0.9 } is privacy level and τ∈{ 0.25,0.5,0.75 }.  The step size η_0 is chosen via backtracking line search. As suggested in <cit.>, the bandwidth ϖ is taken to be √(τ (1-τ))·{ (p + log n)/n }^2/5. The final output ^(T) is μ-GDP according to Theorem <ref>. We fix p=5 and let the sample size increase from 100 to 500. Figures <ref>–<ref> present plots of the logarithmic ℓ_2-error and regret versus the sample size under different error distributions and privacy levels, averaged over 300 repetitions. The regret of ^(T), defined as  [ C(^^(T) ,d)]- [C(^^*,d)] where the expectation is taken over the joint distribution of (d, ), is evaluated using an additional data set of size one million. Figures <ref>–<ref> display the boxplots of regrets under different error distributions and privacy levels based on 300 repetitions with a sample size of 400. Table <ref> reports the corresponding average regrets and standard deviations.













From Figures <ref>–<ref> we see that both the estimation errors and regrets decrease as the number of observations grows, as expected. The spacing of these error curves further illustrates the impact of privacy. From Table <ref> we observe that the variability of regrets is low when the sample size is reasonably large. These numerical results also highlight the robustness of newsvendor loss minimization against heavy-tailed error distributions.




 §.§ Real Data Example



We demonstrate the effectiveness of the proposed privacy-preserving algorithm using the restaurant data from <cit.>. This dataset comprises demand data for main ingredients at a casual restaurant in Stuttgart over approximately 750 days.  The restaurant manager needs to decide on the amount of ingredients to defrost overnight to prepare meals, considering that leftover ingredients result in holding costs. Therefore, we formulate the problem of determining the optimal amount of ingredients to defrost as a newsvendor problem. It is worth noting that during the data collection period, the store manager's strategy was to maintain a service level of nearly 100%, rendering the issue of censored demand negligible.
 





In our analysis, we utilize the private algorithm to determine the optimal strategy for defrosting the amount of lamb (which is the ingredient with the highest demand) to minimize costs and maximize performance. We compare the outcomes obtained from the private algorithm with those from the standard non-private algorithm. Our model incorporates three distinct features: (1) calendric features, which include binary variables indicating holidays or non-holidays extracted from the date; (2) lag features, incorporating demand information from the previous periods, such as demand from exactly one week ago and exactly two weeks ago; and (3) weather features, encompassing rain and temperature data. We assume a per-unit (per kilogram) holding cost h for lamb of $30. We consider four different values for the lost-sales penalty cost b: $50, $70, $90, and $120 per kilogram. These values correspond to gross profit margins (excluding labor costs) of roughly 62.5%, 70%, 75%, and 80% respectively, which are similar to the gross profit margin of a financially viable restaurant, estimated to be around 70%. We use a training dataset of n = 552 past demand observations to train our model and evaluate its performance by measuring the out-of-sample error on a separate testing dataset consisting of 184 observations.
 
The algorithm hyper-parameters are set as T = 10, B = 2 and σ = ⌈ 2τ̅BT^1/2/μ⌉ with privacy level μ∈{ 0.3, 0.5, 0.9}. We conduct 100 random partitions of the dataset into training and testing data and summarize the average out-of-sample cost across these partitions. Table <ref> presents the out-of-sample cost of our private estimator (at different privacy levels) and the naive non-private estimator for various choices of b. The average cost of our private algorithm is at most 2% higher than the cost of the non-private algorithm. This indicates that the proposed algorithm can be effectively used by the restaurant to predict future demands while maintaining a reasonable level of privacy protection, albeit at a slightly higher cost.




§ CONCLUDING REMARKS AND DISCUSSIONS


In this paper, we investigate the learning of privacy-preserving optimal policies for feature-based newsvendor problems with unknown demand. We consider the problem within the framework of f-differential privacy, a recently proposed approach that extends the classical (ϵ, δ)-differential privacy with several appealing features. To address the challenge of nonsmoothness associated with the newsvendor loss function, we propose a new noisy gradient algorithm based on convolution smoothing.  We provide privacy-preserving guarantees for the T-step output of the proposed algorithm and establish rigorous finite-sample high-probability bounds for estimation error and regret. Importantly, we demonstrate that a reasonable level of privacy protection can be achieved without sacrificing performance compared to the clairvoyant policy with known demand distribution but without privacy protection.

A future endeavor is to find proper conditions on the mini-batch size m under which the noisy SGD estimators are consistent. If m is fixed, there will be a non-vanishing noise term in noisy SGD. Thus, we might not have consistent noisy SGD estimators unless m→∞, and the cost of privacy might not be negligible unless we also have that m^2 /n →∞. These problems deserve further attention in future research. From the practical perspective, the choice of appropriate mini-batch size is critical and nontrivial to ensure high-quality performance. In the newsvendor problem, when the data size is not on the scale of millions, the full gradient descent method remains computationally efficient and exhibits fast geometric convergence.















The authors are grateful to the department editor, associate editor,
and two anonymous referees for their extensive and constructive
comments. The research of Zhao and Wang was partially supported by Grant NSF FRGMS-1952373.






§ TECHNICAL LEMMAS


 
This section presents several technical lemmas that are essential for certifying that events _0(B), _1(δ_0,δ_1) and _2(R) defined in (<ref>)–(<ref>) hold with high probability for properly chosen (B, δ_0, δ_1, R).
For ∈^p, after a change of variable =  - ^* we define
#
	 R̂_ϖ()    =_ϖ() - _ϖ(^* ) - ⟨∇_ϖ(^*) , - ^* ⟩,   

	  B̂_ϖ()     =_ϖ(^*) - _ϖ() - ⟨∇_ϖ() , ^*- ⟩, 
#
and their population counterparts R_ϖ()  = {R̂_ϖ() } and B_ϖ()  = {B̂_ϖ() }.

Lemma <ref> provides lower bounds for the first-order Taylor series remainder of the population (smoothed) loss in a neighborhood of ^*, that is, R_ϖ(·) and B_ϖ(·). 
Lemma <ref> provides upper bounds (in high probability) for the fluctuation of the empirical loss |D̂_ϖ() -  D_ϖ()| uniformly over  in a compact set excluding a local neighborhood of the origin. 
Lemma <ref> establishes uniform convergence of the gradient and Hessian
of the smoothed quantile loss to their population counterparts, as long as the sample size scales linearly in the number of features.
 
Note that under Condition <ref>,  m_q = sup_∈𝕊^p-1 | ⟨, ⟩|^q (q=3,4)  are bounded and only depend on υ_1.


  
Conditions <ref>–<ref> ensure that 
$
   min{ 	R_ϖ() , B_ϖ() } ≥0.5 ( f_l - l_0 κ_1 ϖ)  _Σ^2   ∈Θ_Σ(1).
$


 
  
Let r > δ >0.  For any u≥ 0, the following bounds hold:


  (i) With probability at least 1-e^-u,
#
D̂_ϖ()   - D_ϖ()   ≤C_0  υ_1 r √(p + u/n)       ∈Θ_Σ(r) ; 
#

  (ii)  With probability at least 1-e^-u,
 #
	D̂_ϖ()   - D_ϖ()   ≤C_1 υ_1√(p+ log_2(r/δ) + u/n)  · _Σ     ∈Θ_Σ(r)∖Θ_Σ(δ) , 
#

where C_0, C_1>0 are absolute constants. The same upper bounds in (<ref>) and (<ref>)  also apply to D_ϖ()  - D̂_ϖ().  

 
 
  
Assume Conditions <ref>–<ref> hold and let R>0 be a fixed constant. For any u≥ 0, the following bounds hold with probability at least 1-3e^-u as long as n≳υ_1^4 (p+u): max_1≤ i≤ nΣ^-1/2_i _2  ≤    1 + υ_1    √(p-1) +υ_1     √(2(u+log n)), 
#
    sup_∈Θ^*_Σ(R)     ∇Q̂_ϖ() - ∇Q_ϖ()    _Σ^-1 ≤C_2  υ_1 √(p log(n/ϖ)  +u/n) + ( f_u ϖ+ 2κ_u ) R/n      
#
and
#
       sup_∈Θ^*_Σ(R)   ∇^2 _ϖ() - ∇^2 Q_ϖ() _Σ^-1 

      ≲υ_1^2 {   √(plog(n/ ϖ) + u/ n ϖ) + plog(n/ϖ)+ u/n ϖ} +   { υ_1 (p+ logn+ u)^1/2   + l_0  m_3  ϖ^2 } R/n^2 .   
# 
Moreover,  ∇   Q_ϖ(^*) _Σ^-1≤ 0.5 l_0 κ_2 ϖ^2 and sup_∈ℝ^p∇ Q_ϖ()    _Σ^-1≤τ̅= max(τ, 1-τ).

 


The following lemma provides upper bounds for the i.i.d. standard normal random vectors {_t}_t=0^T-1 in the noisy gradient descent algorithm. In particular, inequality (<ref>) slightly improves the tail bound in Lemma 11 of <cit.>.

 
Let _0,  _1,…,  _T-1 (T ≥ 1) be independent random vectors from (,   _p). Then, for any z≥ 0,
#
	 P {  max_0≤t≤T-1  _t _2 ≥√(p) + √(2(logT + z ) )   } ≤e^-z .  
#
Moreover, for any ρ∈ (0,1), we have with probability at least 1-e^-z that
#
	∑_t=0^T-1 ρ^t  _t _2^2 ≤p/1-ρ + 2 √(p z/1-ρ^2) + 2 z   ≤2p/1-ρ +(1/1+ρ + 2 )z . 
#



 
Let z≥ 0. In addition to (<ref>),  assume
#
   n ≥B_T σ/Δ,  
#
where B_T :=  √(p) + √(2(log T + z ) ) and  Δ =  ϕ_1 -  δ_0 - b^* ∈ (0, f_l/2). 
Then,  conditioning on  _0(B) ∩_1(δ_0, δ_1) ∩_2(2),   the  noisy gradient descent iterates satisfy ^(t)∈Θ_Σ^*(1) for all t= 1,…, T with probability (over {_t }_t=0^T-1) at least 1-e^-z.
  

 
Let R_0 = ^(0) - _ϖ _Σ, and assume _ϖ - ^* _Σ≤ r_0 and η_0 ∈ (0, 1/(2f_u)].  For any T_0≥ 2 and z≥ 0, assume the sample size satisfies
$
  n ≥e-1/4-e (2 τ̅B + 1) max{ 1, η_0 / R_0 }^2  T_0  B_T_0σ,
$
where B_T_0 :=  √(p) + √(2(log T_0 + z ) ). Then, conditioned on the event _0(B) ∩_2(R) with R≥2R_0   + r_0, we have
$
	  ^(t) - _ϖ  _Σ^2 ≤(1+1/T_0)^t R_0^2 +   { (1+1/T_0)^t - 1   } ( 2 τ̅B + 1  )   η_0^2    T_0  B_T_0σ/n  ,    1≤t≤T_0 
$
with probability (over i.i.d. normal vectors {_t}_t=0^T_0-1) at least 1- e^-z. In particular, max_1≤ t≤ T_0^(t) - _ϖ _Σ≤  2 R_0.






§ PROOF OF THEOREMS



 §.§ Proof of Theorems <ref> and <ref>


The high probability bound in Theorem <ref> is a direct consequence of Theorem <ref> and Proposition <ref> by taking z=2log n therein. To obtain the second bound under expectation, note that

    ^(1) - ^(0)_Σ≤η_0/n{K̅_ϖ(_i^^(0)) - τ}_i  + η_0 σ/n_0 _2  ≤τ̅η_0 B  + η_0 σ/n_0 _2 ,

where we have used the property that max_1≤ i≤ n_i _2 ≤ B. Similarly, it can be shown that for each t≥ 1, ^(t) - ^(t-1)_Σ≤τ̅η_0 B + η_0 σ/n_t _2. With σ = 2 τ̅B T^1/2 / μ, applying the triangle inequality repeatedly yields

    ^(T) - ^(0)_Σ≤∑_t=1^T ^(t) - ^(t-1)_Σ≤τ̅η_0 B T +  2 τ̅η_0 B T^1/2 1 /μ n∑_t=0^T-1_t _2 .

Initialized at any ^(0) satisfying ^(0)  - ^* _Σ≤ 1, it holds almost surely that

    ^(T) - ^* _Σ≤ 1 + τ̅η_0 B T +  2 τ̅η_0 B T^1/2 1/μ n∑_t=0^T-1_t _2  .

From the first high probability bound, we see that there exists an event  such that P() ≥ 1 - C_1 n^-2 and on  it holds

    ^(T) - ^* _Σ≤ r_n≍   T^1/2η_0 p+log n/μ n + 1/f_l√(plog n/n) .

By combining the above two bounds, with one being almost surely true and the other holding with high probability, we further derive that

    ^(T) - ^* _Σ = {^(T) - ^* _Σ1() } +  {^(T) - ^* _Σ1(^ c) }
       ≤ r_n + (1 + τ̅η_0 B T ) P(^ c) +  2 τ̅η_0  B T^1/21/μ n∑_t=0^T-1{_t _2  1(^ c)  }
       ≤ r_n + C_1 1 + τ̅η_0 B T/n^2 +  2 τ̅η_0 B T^1/2 1/μ n∑_t=0^T-1  ( _t_2^2 )^1/2 P(^ c)^1/2
       ≤ r_n + C_1 1 + τ̅η_0 B T/n^2 +  2 τ̅η_0 √(C_1 p)B T^3/2/μ n^2     .

Taking B ≍√(p+log n) and T≍log n, the second and third terms on the right-hand side are dominated by r_n in order. This proves the claimed upper bound under expectation.


To prove the regret bound in Theorem <ref>,  recall that the optimal coefficient ^* in the linear demand model satisfies the first-order condition ∇ Q(^*) = 0. Under Condition <ref>, the Hessian matrix ∇^2 Q() =  { f_ε |  ( ^ ( - ^*) ) ^} satisfies Σ^-1/2∇^2 Q()  Σ^-1/2_2 ≤ f_u  (^ ) _2 = f_u for all ∈^p. Therefore, applying the mean value theorem yields Q() -  Q(^*) = Q() -  Q(^*) - ⟨∇ Q(^*) ,  - ^* ⟩≤ 0.5 f_u  - ^* _Σ^2 for any ∈^p. This, joint with the property that ^(T) - ^*_Σ≲  f_l^-1√((plog n) /n) + √(log n) η_0 (p+log n)/(μ n) holds with high probability, proves the claimed regret bound. 

To bound the expected regret, by (<ref>) and the assumption η_0≤ 1/max{ 2f_u, f_l+τ̅} we have 

    ^(T) - ^* _Σ^2    ≤ 2(1+  τ̅η_0 B T  )^2 +  8 τ̅^2 η_0^2 B^2 T  1/(μ n)^2 ( ∑_t=0^T-1_t _2 )^2 
       ≤ 2(1+  0.5 τ̅f_u^-1 B T )^2 + 2τ̅^2 ( BT/ f_uμ n)^2∑_t=0^T-1_t _2^2 .

This, together with the inequality _t _2^4 ≤ p ∑_j=1^p  g_t,j^4 = 3 p^2, implies

    ^(T) - ^* _Σ^2  ≤ r_n^2 + (1+  0.5 τ̅f_u^-1 B T)^2 2 C_1/n^2 +  2 τ̅^2 √(3C_1)p/n( BT/f_u μ n)^2 .

 Once again, the leading term on the right-hand side is r_n^2 (in order). This proves the claimed expected regret bound. 




 §.§ Proof of Theorem <ref>

 
For simplicity, we write _0 = _0(B), _1=_1(δ_0, δ_1) and _2 = _2(2) for the events defined in (<ref>)–(<ref>), where δ_0,δ_1>0 satisfy the constraints in (<ref>).  
 
To control the random perturbations in noisy gradient descent, for any z>0 we define 
#
 = (z) =   {   max_ 0 ≤t≤T-1  _t _2 ≤B_T  } ⋂{ ∑_t=0^T-1 (1-ϵ)^t   _T-1-t _2^2 ≤2p/ϵ+ 3z  } 
#
where B_T  := √(p) + √(2(log T + z) ) and ϵ :=η_0 ϕ_1. It thus follows from Lemma <ref> that P{ (z)   }≥ 1-2 e^-z.
In the following, we prove (<ref>) by conditioning on these events.
  
Lemma <ref> shows that starting at an initial estimate ^(0)∈Θ_Σ^*(1) and conditioning on _0 ∩_1 ∩_2 ∩, all the successive iterates will stay in Θ_Σ^*(1). Next, we establish a contraction property for the noisy gradient descent iterates. Define
$
     ^(t+1)  = ^(t) -  η_0 Σ^-1 ∇Q̂_ϖ(^(t))      _t =   η_0 σ/ n_t ,   t = 0, 1, …, T-1,
$
and note that ^(t+1) = ^(t+1) + Σ^-1/2_t. Note that (<ref>) is guaranteed by (<ref>). Lemma <ref> ensures that ^(t)∈Θ_Σ^*(1) for all t= 0 ,1 ,…, T. Similarly, it can be shown that the non-private gradient descent iterates ^(t) also stay in the ball Θ_Σ^*(1) for t=1,…, T.
For simplicity, set
$
	^(t) = ^(t ) - ^* ,    ^(t ) = ^(t) - ^*     t= 0 , 1, …, T.
$
To upper bound ^(t+1)_Σ at each iteration,  we split the analysis into two cases. 

Case 1:  Suppose the non-private gradient descent iterate ^(t+1) is in Θ_Σ(r_0). Then
#
   ^(t+1)   _Σ≤r_0 +  _t _2.  
#

Case 2: Assume otherwise ^(t+1)∉Θ_Σ(r_0).
For the previously defined ϵ =η_0 ϕ_1  ∈ (0, 1/2],
#
   ^(t+1)   _Σ^2  
	    =   ^(t+1)  _Σ^2 +  _t _2^2 + 2 ⟨Σ^ 1/2 ^(t+1)  ,  _t ⟩

	    ≤( 1 + ϵ)  ^(t+1)   _Σ^2 + (1+1/ϵ)  _t _2^2 

	    = (1+ϵ)   ^(t)   _Σ^2   + (1+1/ϵ)  _t _2^2    

	        + 2η_0 (1+ϵ)     {   η_0/2   ∇Q̂_ϖ(^(t)  )_Σ^-1^2 -  ⟨^(t) - ^* , ∇Q̂_ϖ(^(t) ) ⟩_  Π }  .  #
To bound Π, we use the local strong convexity and smoothness properties of _ϖ(·) as in (<ref>) and (<ref>). The latter implies
$
 Q̂_ϖ(^(t+1 )) - Q̂_ϖ(  ^(t) )  ≤⟨∇Q̂_ϖ( ^(t) ) , ^(t+1) - ^(t) ⟩+ f_u  ^(t+1) - ^(t) _Σ^2 .
$
For the former, we assume without loss generality that r_1 = (δ_0 + δ_1) /ϕ_1  ≥  1/n. Otherwise if r_1<1/n, (<ref>) implies _ϖ(^*) - _ϖ()  -  ⟨∇_ϖ(), ^* - ⟩≥ϕ_1   (   - ^* _Σ^2 -   n^-1 - ^* _Σ  ) for all ∈Θ_Σ^*(1)∖Θ_Σ^*(1/n). Then we obtain (<ref>) with r_1 replaced by 1/n.

Since r_1  ≥  1/n, it holds for every ^(t)∈Θ^*_Σ(1/n) that
$
 Q̂_ϖ(^* ) - Q̂_ϖ(^(t)) - ⟨∇Q̂_ϖ(^(t)) , ^* - ^(t) ⟩≥0 ≥ϕ_1  ^(t) - ^* _Σ^2 - (δ_0+δ_1)  ^(t) - ^* _Σ.
$
Otherwise if ^(t)∈Θ^*_Σ(1)∖Θ^*_Σ(1/n),
$
 Q̂_ϖ(^* ) - Q̂_ϖ(^(t))  -  ⟨∇Q̂_ϖ(^(t)) , ^* - ^(t) ⟩≥ϕ_1  ^(t) - ^* _Σ^2 - (δ_0+δ_1)  ^(t) - ^* _Σ.
$
 Together, the above upper and lower bounds imply
$
      Q̂_ϖ(^(t+1 ))  -  Q̂_ϖ(^* )  
  
     ≤⟨∇Q̂_ϖ(^(t) )  , ^(t+1) - ^*   ⟩+ f_u  ^(t+1) - ^(t) _Σ^2 -  ϕ_1  ^(t) - ^* _Σ^2  + (δ_0+δ_1)  ^(t) - ^* _Σ

     = ⟨∇Q̂_ϖ(^(t) )  , ^(t+1) - ^*   ⟩+ f_u η_0^2    ∇Q̂_ϖ(^(t) ) _ Σ^-1^2 -  ϕ_1  ^(t) - ^* _Σ^2  + (δ_0+δ_1)  ^(t) - ^* _Σ

      = ⟨∇Q̂_ϖ(^(t) )  ,  ^(t) - ^*   ⟩- η_0 ( 1 - f_u η_0)       ∇Q̂_ϖ(^(t) ) _ Σ^-1^2    -  ϕ_1  ^(t) - ^* _Σ^2  + (δ_0+δ_1)  ^(t) - ^* _Σ

      ≤⟨∇Q̂_ϖ(^(t) )  ,  ^(t) - ^*   ⟩-    η_0/2    ∇Q̂_ϖ(^(t) ) _ Σ^-1^2    -  ϕ_1  ^(t)   _Σ^2  + (δ_0+δ_1)  ^(t)   _Σ,
$
where the last inequality holds when η_0 ≤ 1/(2f_u). Since ^(t+1)∈Θ^*_Σ(1) ∖Θ^*_Σ(r_0), the restricted lower bound (<ref>) yields
$
Q̂_ϖ(^(t+1 ))  -  Q̂_ϖ(^* )  ≥ϕ_1   ^(t+1 ) - ^* _Σ·(     ^(t+1 ) - ^* _Σ- r_0 ) ≥0.
$
We hence conclude that Π≤   -  ϕ_1 ^(t)_Σ^2  + (δ_0+δ_1) ^(t)_Σ. Substituting this into (<ref>) implies
#
      ^(t+1)   _Σ^2 

    ≤{  1 + ϵ- 2η_0 ϕ_1  (1+ϵ)  }  ^(t)   _Σ^2 +  (  1 + 1/ϵ)  _t _2^2 +  2η_0   (1+ϵ) (δ_0+δ_1)  ^(t)  _Σ

   ≤{  1 +  ϵ- 2η_0 ϕ_1  (1+ϵ)  }  ^(t)  _Σ^2 +  (  1 + 1/ϵ)  _t _2^2  

                                                     +  (1+ϵ) (η_0 ϕ_1)^2  ^(t)   _Σ^2  + (1+ϵ)(δ_0 + δ_1)^2  /ϕ_1^2  

    = (1+ϵ) (1-η_0 ϕ_1 )^2  ^(t)   _Σ^2 +  (  1 + 1/ϵ)  _t _2^2+ (1+ϵ) r_1^2 . 
#
On the other hand, observe that 

    (r_0 + _t _2   )^2 = r_0^2 + _t_2^2 + 2 r_0 _t _2 ≤  (  1 + 1/ϵ  ) _t _2^2 +  (1+ϵ) r_0^2 .

Recall that ϵ = η_0   ϕ_1 ∈ (0, 1/2]. It then follows from (<ref>) and (<ref>) that
#
   ^(t+1)   _Σ^2 ≤(1-ϵ)    ^(t)  _Σ^2 +   (  1 + 1/ϵ)  _t _2^2 +  (1+ϵ) (r_0 ∨r_1)^2, #
for t=0,1, … , T-1. This recursive bound further implies
#
 ^(T) - ^* _Σ^2      ≤(1-ϵ)^T  +(1+1/ϵ)   {   ( η_0 σ/n )^2   ∑_t=0^T-1 (1-ϵ)^t  _T-1-t _2^2 _≤  2p/ϵ+ 3z  on    +   (r_0 ∨r_1)^2 } . 
#

Let T = T_1 + T_2  with T_1  ≥  2 log (n) / log ((1-ϵ)^-1), and r^* be as in (<ref>).
Then,  conditioned on _0 ∩_1 ∩_2 ∩, we obtain
^(t) - ^* _Σ≤   r^* for all T_1 ≤ t ≤ T, as desired. In other words, r^* given in (<ref>) characterizes the convergence rate of the noisy gradient descent iterators ^(t) to the true parameter ^*.

Turning to the non-private empirical risk minimizer _ϖ∈_∈ℝ^pQ̂_ϖ(), we claim that _ϖ - ^* _Σ≤ r_0 = (δ_0+b^*)/ϕ_1 conditioning on ℰ_1. To see this, note that for any ∈Θ_Σ(1), 

    D̂_ϖ () = R_ϖ() + ⟨∇ Q_ϖ(^*) , ⟩ + {D̂_ϖ() -    D_ϖ() }≥ϕ_1 _Σ^2 - (δ_0 + b^*) _Σ .

By (<ref>), D̂_ϖ () ≥ϕ_1 - δ_0 - b^* >0 for all ∈∂Θ_Σ(1)–the boundary of Θ_Σ(1). On the other hand, note that = _ϖ - ^* satisfies D̂_ϖ (_ϖ) ≤ 0. By the convexity of Q̂_ϖ(·), we must have _ϖ∈Θ_Σ^*(1). Otherwise if _ϖ - ^* _Σ >1, there exists some α∈ (0, 1) such that = α_ϖ + (1-α) ^* lies on the boundary of Θ_Σ^*(1), that is, - ^* _Σ =1. Then := - ^* satisfies D̂_ϖ() >0. However, by the convexity of D̂_ϖ,

    D̂_ϖ() = D̂_ϖ(α_ϖ + (1-α) ) ≤αD̂_ϖ(  ) + (1-α) D̂_ϖ()  ≤ 0.

This leads to a contradiction. As a result, from (<ref>) it can be deduced that

    0 ≥D̂_ϖ() ≥ϕ_1 _Σ^2 - (δ_0 + b^*) _Σ ,

 thereby verifying the claim.

Finally, we prove the convergence of ^(t) towards the non-private estimator _ϖ, for which it has been shown that _ϖ - ^* _Σ≤ r_0 conditioned on ℰ_1. By the triangle inequality, ^(t) - _ϖ_Σ≤^(t) - ^* _Σ + _ϖ - ^* _Σ≤ r^*+ r_0 for all T_1≤ t≤ T conditioned on ℰ_0 ∩ℰ_1 ∩ℰ_2 ∩𝒢. To improve this “crude” bound, the key element is the refined restricted strong convexity property, guaranteed by the event ℰ_3 = ℰ_3(r, ϕ_2) with r= r^* + r_0.

Thus far we have shown that {^(t)}_t=0, 1, …, T⊆Θ^*_Σ(1) and {^(t)}_t=T_1, …, T ⊆Θ^*_Σ(r^*). Moreover, note that inequality (<ref>) remains valid if ^* is replaced by _ϖ, that is, 

    ^(t+1) - _ϖ_Σ^2      ≤ (1+ϵ) ^(t) - _ϖ_Σ^2 + (1+1/ϵ) _t _2^2  
            + 2 η_0 ( 1+ϵ) {η_0/2∇Q̂_ϖ(^(t) ) _Σ^-1^2 - ⟨^(t) - _ϖ , ∇Q̂_ϖ(^(t) ) ⟩} .

Conditioned on ℰ_3(r,ϕ_2) with r=r^*+r_0 ≥ 2r_0, we have, for t=T_1, T_1+1,…, T-1,

    Q̂_ϖ(^(t+1) ) = Q̂_ϖ (^(t)≤⟨∇Q̂_ϖ (^(t)) , ^(t+1) - ^(t)⟩ + f_u ^(t+1) - ^(t)_Σ^2  
     Q̂_ϖ(_ϖ) - Q̂_ϖ(^(t) ) ≥⟨∇Q̂_ϖ(^(t) ) , _ϖ - ^(t)⟩ + ϕ_2 ^(t) - _ϖ_Σ^2 .

Following a similar argument, and recall that _ϖ minimizes Q̂_ϖ(·), we obtain

    0    ≤Q̂_ϖ (^(t+1) - Q̂_ϖ(_ϖ) 
       ≤⟨∇Q̂_ϖ (^(t) ) , ^(t) - _ϖ⟩ - η_0/2∇Q̂_ϖ(^(t)_Σ^-1^2 - ϕ_2 ^(t) - _ϖ_Σ^2 .

Putting together the pieces yields the recursive bound 

    ^(t+1) - _ϖ_Σ^2 ≤ (1-ϵ) ^(t) - _ϖ_Σ^2 + (1+1/ϵ)  _t _2^2,    t=T_1, T_1+1, …, T.

Provided T_2 ≥log(n)/log((1-ϵ)^-1), conditioning on ℰ_0∩ℰ_1∩ℰ_2 ∩ℰ_3 ∩𝒢 it follows that

    ^(T) - _ϖ_Σ^2    ≤ (1-ϵ)^T_2^(T_1) -_ϖ_Σ^2 + (1+1/ϵ) ( η_0σ/n)^2 ∑_t=0^T_2-1 (1-ϵ)^t _T-1-t_2^2  
       ≤r^2/n + (1+1/ϵ) (2p/ϵ + 3z) (η_0 σ/n)^2 ,

as claimed. This completes the proof of the theorem. 




 §.§ Proof of Theorem <ref>




To begin with, recall from the proof of Theorem <ref> that conditioning on _0(B) ∩_1(δ_0, δ_1) ∩_2(2), the non-private empirical risk minimizer _ϖ satisfies _ϖ - ^* _Σ≤ r_0 = (δ_0 + b^*) / ϕ_1 < 1.  For any T_0≥ 2 and z≥ 0,  set
$
_0(z) = { max_0≤t ≤T_0 - 1   _t _2 ≤B_T_0 : = √(p) + √(2(logT_0 + z ) ) }, 
$
so that P {_0(z) }≥  1- e^-z. From Lemma <ref> we see that conditioned on _0(B) ∩_2(R) ∩_0(z) with R= 2R_0 + r_0,  the iterates {^(t)}_t=1,…, T_0 satisfy
#
   ^(t) - _ϖ_Σ^2 ≤e R_0^2 + (e-1) (2  τ̅B + 1/2)    T_0 B_T_0 σ/n η_0^2  ≤4 R_0^2   
#
as long as n≥e-1/4-e  ( 2  τ̅B + 1/2 )   T_0  B_T_0σ.
Consequently, ^(t) - ^* _Σ≤^(t) - _ϖ_Σ + _ϖ - ^* _Σ≤ R, and hence  ^(t)∈Θ^*_Σ(R) for all t=0, 1, …, T_0.

Keep the notation from the proof of Theorem <ref>, and note that ^(t+1) = ^(t) - η_0  Σ^-1∇_ϖ(^(t) )  - Σ^-1/2_t, where _t = η_0  σ/n_t and η_0 ≤ 1/(2f_u). Conditioned on _0(z), 
#
	 max_0≤t≤T_0 -1   _t _2 ≤e_priv :=  η_0  B_T_0 σ/n  <  η_0/2. 
# 
By (<ref>) and the convexity of _ϖ(·), for each t = 0 , 1, …, T_0 -1 we have
#
	_ϖ(^(t+1) )       ≤_ϖ(^(t) )   + ⟨∇_ϖ(^(t)) , ^(t+1) - ^(t) ⟩+ f_u   ^(t+1) - ^(t) _Σ^2  

     = _ϖ(^(t) )   -  ⟨∇_ϖ(^(t)) ,   η_0 Σ^-1 ∇_ϖ(^(t) )  + Σ^-1/2 _t ⟩
 
        + f_u    η_0  Σ^-1 ∇_ϖ(^(t) )  + Σ^-1/2 _t _Σ^2 

    ≤_ϖ(^(t) )  - η_0 ( 1- f_u η_0 )    ∇_ϖ(^(t) ) _Σ^-1^2   

           +  ( 1 + 2 f_u η_0  )  _t _2    ∇_ϖ(^(t) ) _Σ^-1 + f_u     _t _2^2 
 
       ≤_ϖ(^(t) )  - η_0/2     ∇_ϖ(^(t) ) _Σ^-1^2 +    (2 τ̅B +  f_u e_priv  ) e_priv  

       ≤_ϖ( _ϖ)  +    ⟨∇_ϖ(^(t) ) , ^(t)  - _ϖ⟩- η_0/2     ∇_ϖ(^(t) ) _Σ^-1^2  _=:   Π_t+   (2 τ̅B + f_u e_priv   ) e_priv . #
Moreover,
$
	Π_t      = 1/2η_0   {   2η_0 ⟨∇_ϖ(^(t) ) , ^(t)  - _ϖ⟩-  η_0^2     ∇_ϖ(^(t) ) _Σ^-1^2 } 

	    =   1/2η_0    {       ^(t)  - _ϖ   _Σ^2  -    ^(t) - η_0  Σ^-1 ∇_ϖ(^(t) ) -   _Σ^2 } 

	    =  1/2η_0    {       ^(t)  - _ϖ_Σ^2  -    ^(t+1) + Σ^-1/2 _t  - _ϖ_Σ^2 } 

	    =  1/2η_0    {       ^(t)  - _ϖ_Σ^2  -   ^(t+1)   - _ϖ_Σ^2 -       _t  _2^2   - 2 ⟨_t , Σ^1/2 ( ^(t+1)  - _ϖ)  ⟩} 

	    ≤1/2η_0    {       ^(t)  - _ϖ_Σ^2  -   ^(t+1)   - _ϖ_Σ^2 } +  1/η_0   _t  _2   ^(t+1)   - _ϖ_Σ.
$
Summing over t=0, 1, …, T_0-1 gives
$
	   	∑_t=0^T_0-1 {  _ϖ(^(t+1) ) - _ϖ( _ϖ) }  

	    ≤1/2η_0 {       ^(0)  - _ϖ_Σ^2  -   ^(T_0)   - _ϖ_Σ^2 } 
 
          + 1/η_0∑_t=0^T_0-1   ^(t+1)   - _ϖ_Σ· _t _2 +  T_0  (2 τ̅B + f_u  e_priv  )   e_priv ,
$
On the other hand, applying (<ref>) repeatedly yields
$
 T_0  _ϖ(^(T_0) )   ≤∑_t=1^T_0   _ϖ(^(t ) )   + T_0(T_0-1)/2  (2 τ̅B +  f_u e_priv  ) e_priv . 
$
Combining the last two bounds with (<ref>) and (<ref>) gives that
$
_ϖ(^(T_0) )  - _ϖ( _ϖ)     ≤1/T_0    ∑_t=1^T_0   { _ϖ(^(t ) ) -  _ϖ( _ϖ) } +   T_0-1 /2  (2 τ̅B +  f_u e_priv  ) e_priv 

    ≤1/2  T_0η_0   ^(0) - _ϖ_Σ^2 +   2R_0 e_priv /η_0     + (T_0+1) (  τ̅B + f_u  e_priv /2 )  e_priv 

    < R_0^2/2  T_0 η_0   +    2 R_0 B_T_0 σ/n  + (  τ̅B + 1/4 )  (T_0+1) η_0  B_T_0 σ/n .
$
Under condition (<ref>) on (T_0, n), it follows that
$
_ϖ(^(T_0) ) <   _ϖ( _ϖ) + Δ≤_ϖ(^* ) + Δ.
$ 

Finally,  define Δ̂_1 = inf_∉Θ^*_Σ(1) _ϖ() - _ϖ(^* ), so that any  such that _ϖ() < _ϖ(^*) + Δ̂_1 must satisfy - ^* _Σ≤ 1.
Recall that _ϖ = _∈^p_ϖ() ∈Θ^*_Σ(r_0)⊆Θ^*_Σ(1). By the convexity of _ϖ(·), the infimum over ^p∖Θ^*_Σ(1) must be achieved on the boundary ∂Θ^*_Σ(1).
On the other hand, Proposition (<ref>) ensures that conditioned on _1(δ_0, δ_1),  _ϖ(  )  - _ϖ(   ^* )  ≥Δ = ϕ_1 - δ_0 - b^* for any ∈∂Θ^*_Σ(1), thus implying 

    Δ̂_1 ≥Δ > _ϖ(^(T_0) )  -  _ϖ(^* )  .

Therefore, we must have ^(T_0) - ^* _Σ≤ 1, as claimed. 






§ PROOF OF PROPOSITIONS






 §.§ Proof of Proposition <ref>


Proof of (<ref>). For ∈^p, write =  - ^*, and note that D̂_ϖ(·) given in (<ref>) satisfies
#
 D̂_ϖ()        =  ⟨∇Q_ϖ(^*), ⟩+ R_ϖ() - { D_ϖ() -D̂_ϖ() } 

    ≥R_ϖ() -   ∇Q_ϖ(^*) _Σ^-1 ·  _Σ -   { D_ϖ() - D̂_ϖ()   }  

    =  R_ϖ() -  b^*     _Σ -   { D_ϖ() - D̂_ϖ()   } . 
#
By Lemma <ref>, R_ϖ() ≥ϕ_1 _Σ^2 for all ∈Θ_Σ(1); and conditioned on _1, D_ϖ() - D̂_ϖ( )  ≤δ_0 _Σ for all δ∈Θ_Σ(1) ∖Θ_Σ(1/n). Substituting these two bounds into (<ref>) proves the first part of (<ref>).


To prove the second part of (<ref>), consider the decomposition
#
  Q̂_ϖ( ) - Q̂_ϖ(^*)   =   R̂_ϖ() +   ⟨∇Q̂_ϖ(^*), - ^* ⟩, #
where R̂_ϖ() = D̂_ϖ() - ⟨∇_ϖ(^* ), ⟩.  By the mean value theorem,
$
  R̂_ϖ()   =  ∫_0^1 ⟨∇_ϖ(^* + t ) - ∇_ϖ(^*) , ⟩dt .
$
By Lemma 8 in <cit.> and  the convexity of _ϖ(·), we have
$
  ⟨∇_ϖ(^* + t ) - ∇_ϖ(^*) ,  t ⟩≥1/s   ⟨∇_ϖ(^* +  t ·s ) - ∇_ϖ(^*) ,  t ·s ⟩$
for any s∈ (0,1], hence implying R̂_ϖ()  ≥      s^-1R̂_ϖ(s  ).  Consequently,  for any ∈Θ^*_Σ(1)^ c,  we set s= 1/_Σ∈ (0,1), _1 =  / _Σ∈∂Θ_Σ(1), and obtain that
$
 _ϖ() - _ϖ(^*)      ≥ _Σ ·R̂_ϖ(_1)  +   _Σ ·⟨∇_ϖ(^*),  _1 ⟩

      =   _Σ ·{ _ϖ(^* +_1 ) - _ϖ(^*) } .
$
Combining this with the earlier lower bound when ∈Θ^*_Σ(1) proves the second part of (<ref>).


Proof of (<ref>).  The goal is to bound  B̂_ϖ( ) defined in (<ref>) from below uniformly over  in a compact set. Note that
 $
B̂_ϖ()       =   - D̂_ϖ() + ⟨∇Q_ϖ() , ⟩+ ⟨∇Q̂_ϖ() - ∇Q_ϖ() , ⟩

    =    - D_ϖ() + ⟨∇Q_ϖ() , ⟩_=  B_ϖ()   - { D̂_ϖ() - D_ϖ() } + ⟨∇Q̂_ϖ() - ∇Q_ϖ() , ⟩

    ≥B_ϖ() - {   D̂_ϖ()   - D_ϖ()  } -    ∇Q̂_ϖ() - ∇Q_ϖ()    _Σ^-1 ·_Σ.
$
Again, from Lemma <ref> we see that B_ϖ() ≥ϕ_1 _Σ^2 for all ∈Θ_Σ(1). Conditioned on _1=_1(δ_0,δ_1), the following bounds
$
  D̂_ϖ()   - D_ϖ()   ≤δ_0  _Σ    
   ∇Q̂_ϖ() - ∇Q_ϖ()    _Σ^-1  ≤δ_1
$
hold uniformly over ∈Θ_Σ(1) ∖Θ_Σ(1/n) and ∈Θ_Σ^*(1), respectively. Putting together the pieces yields (<ref>).

Proof of (<ref>). 
For _1, _2∈Θ^*_Σ(2), applying a second-order Taylor series expansion yields
$
_ϖ(_2 ) - _ϖ(_1) - ⟨∇_ϖ(_1) , _2 - _1 ⟩= 1/2 (_2 - _1)^∇^2 _ϖ(t_1 + (1-t)_2 ) (_2 - _1) 
$
for some t ∈ [0,1]. Since t_1 + (1-t)_2 ∈Θ^*_Σ(2), the right-hand side is further bounded by
$
 1/2  _2 -_1 _Σ^2 ·sup_∈Θ^*_Σ(2)   Σ^-1/2 ∇^2 _ϖ( ) Σ^-1/2  _2 = 1/2  _2 -_1 _Σ^2 ·sup_∈Θ^*_Σ(2)    ∇^2 _ϖ( )   _Σ^-1  .
$
By the triangle inequality,
$
    sup_∈Θ^*_Σ(2)    ∇^2 _ϖ( )   _Σ^-1  ≤    sup_∈Θ^*_Σ(2)     ∇^2 _ϖ( )  - ∇^2 Q_ϖ( ) _Σ^-1   _≤ f_u  conditioned on  _2(2)   +     sup_∈Θ^*_Σ(2)    ∇^2 Q_ϖ( )   _Σ^-1  .
$
For the population Hessian, note that  Σ^-1/2∇^2 Q_ϖ(  ) Σ^-1/2    = { K_ϖ(ε - ^ ) ^}, where =   - ^* and { K_ϖ(ε -  ^ ) | } = ∫_-∞^∞ K(v) f_ε|(  ^ + h v )  d v. Hence, it follows from Condition <ref> that ∇^2 Q_ϖ(  )   _Σ^-1≤ f_u for all ∈^p. Combining this with the above two bounds proves (<ref>).  

 §.§ Proof of Proposition <ref>


The claimed bounds follow immediately from Lemmas <ref> and <ref>. 



 §.§ Proof of Proposition <ref>


For each pair (_1, _2) of parameters, it follows from a second-order Taylor series expansion that

    Q̂_ϖ( _1 )  - Q̂_ϖ( _2  )   - ⟨∇Q̂_ϖ(_2) , _1 - _2 ⟩
        =   1/2^∇Q̂_ϖ( (1-t)_1 + t_2 )   = 1/2 n  K_ϖ(  ε_i - ⟨_i,  (1-t)_1 + t _2 - ^* ⟩) ⟨_i, ⟩^2   
        = 1/2 n∑_i=1^n  K_ϖ(  ε_i - t ⟨_i, ⟩ - ⟨_i, _1 - ^* ⟩) ⟨_i, ⟩^2

for some t∈ [0,1], where = _2- _1. For each i, define the event 
$
 ℱ_i = { | ε_i | ≤ϖ/4 } ∩{ |  ⟨_i, _1 - ^* ⟩| ≤ϖ/4 } ∩{ |⟨_i, ⟩| ≤ _Σ·ϖ/(2 r) } ,
$
on which | t ⟨_i, ⟩ + ⟨_i, _1 - ^* ⟩ | ≤ϖ /2 + ϖ /4= 3ϖ/4 for all _2 ∈_1 + Θ_Σ(r). Consequently.
$
Q̂_ϖ( _1 )  - Q̂_ϖ( _2  )   - ⟨∇Q̂_ϖ(_2) , _1 - _2 ⟩≥κ_l /2n ϖ ⟨_i, ⟩^2 1(_i) ,
$
where κ_l = min_|u|≤ 1 K(u).
For R>0, define  functions  φ_R(u)=u^2 1(|u|≤ R/2) + { u(u) -R }^2 1( R/2 < |u| ≤ R) and ψ_R(u)= 1(|u|≤ R/2) + { 2 - (2/R) (u)}1 (R/2 < |u| ≤ R), which are smoothed versions of u↦ u^2 1(|u|≤ R) and u↦1(|u|≤ R).
Moreover,  note that φ_cR(cu) = c^2 φ_R(u) for any c > 0 and φ_0(u) = 0. The right-hand side of the above inequality can be further bounded from below by
#
     κ_l/2 n ϖ 1(|ε_i| ≤ϖ/4 )  ·φ_ _Σ·ϖ/(2 r) (⟨_i, ⟩)  ·ψ_ϖ/4 (⟨_i, _1 - ^* ⟩)   

     = κ_l  _Σ^2 ·1/2   1/  n ϖ 1(|ε_i| ≤ϖ/4)  ·φ_   ϖ/(2r) (⟨_i, / _Σ⟩) ·ψ_ϖ/4 (⟨_i, _1 - ^* ⟩)  _ =: V_n(_1, _2)  . 
#

In the following, we bound V_n(_1, _2) and V_n(_1, _2)  -   V_n(_1, _2), respectively. Write = Σ^1/2 / _Σ∈𝕊^p-1, we have
$
     { φ_ϖ/(2 r) ( ⟨_i , ⟩) ·ψ_ϖ/4 (⟨_i, _1 - ^*⟩) ·1(|ε_i|≤ϖ/4 ) }  

     ≥1/2 f_l' ϖ·{ ⟨_i, ⟩^2  1(  | ⟨_i, ⟩| ≤ϖ/(4 r))  ·ψ_ϖ/4 (⟨_i, _1  - ^*⟩)    } 
 
     ≥1/2   f_l' ϖ·{  1-  ⟨_i, ⟩^2  1(  | ⟨_i, ⟩| > ϖ/(4 r))     -    ⟨_i, ⟩^2  1(  | ⟨_i, _1 - ^* ⟩| >  ϖ/ 8 )  
 } 

     ≥1/2 f_l' ϖ·{  1-   m_4^1/2   P(  | ⟨_i, ⟩| > ϖ/ (4 r) )^1/2   -    m_4^1/2  P(  | ⟨_i, _1 - ^* ⟩| > ϖ/ 8 )^1/2 
 }    .
$
Under Condition <ref> with υ_1≥ 1, it can be shown that for any ∈𝕊^p-1 and _1 ∈Θ^*_Σ(r/2),
$
P(  | ⟨_i,  ⟩| > ϖ/ (4 r) ) ≤2  exp{ 1/2  -1/2 ϖ^2/(4 υ_1 r )^2   }   

P(  | ⟨_i, _1 - ^* ⟩| > ϖ/ 8 ) ≤2  exp{ 1/2  -1/2 ϖ^2/(4 υ_1  r )^2   }.
$
Let ϖ/ r  ≥ 16 (m_4 ∨ 3)^1/4υ_1.  It then follows from a numerical calculation that
$
 1/4{  1-   m_4^1/2   P(  | ⟨_i, ⟩| > ϖ/ (4 r) )^1/2   -    m_4^1/2  P(  | ⟨_i, _1 - ^* ⟩| > ϖ/ 8 )^1/2 
 }  ≥c_0 ≈0.248
$ 
holds uniformly over ∈𝕊^p-1 and _1 ∈^* + Θ_Σ(r). Putting together the pieces yields
#
    inf_  _1 ∈^* +  Θ_Σ(r/2),   
_2 ∈_1 + Θ_Σ(r)   1/2 V_n (_1 , _2 )  ≥c_0 f_l'  . 
#

Next we upper bound the supremum

    Ω(r)    : = sup__1 ∈^* + Θ_Σ(r/2),  _2 ∈_1 + Θ_Σ(r)  {   -  V_n(_1, _2 )  +      V_n(_1, _2 ) } .
 
Write V_n(_1, _2) = (1/n)  v_i(_1, _2 ), where v_i(_1, _2 ) =   ϖ^-11(|ε_i| ≤ϖ/4)  ·φ_ϖ/(2r) (⟨_i, ⟩  ) ·ψ_ϖ/4 (⟨_i, _1 - ^* ⟩ ) satisfies 
$
	 0 ≤v_i(_1, _2) ≤ϖ/(4 r)^2     
v^2_i(_1, _2) ≤ f_u   m_4/2 ϖ.
$
Applying Theorem 7.3 in <cit.>, a refined version of Talagrand’s inequality, we obtain that for any t>0,
#
Ω(r)   ≤Ω(r)   +  { Ω(r)   }^1/2  1/2r √( ϖt/n)  +  (f_u m_4)^1/2  √(t/ n ϖ)  + ϖ/(4r)^2 t/3 n  
#
holds with probability at least 1-e^-t. To bound the expectation Ω(r), using Rademacher symmetrization and Lemma 4.5 in <cit.>, we obtain
#
Ω(r) ≤2 ·√(π/2) ·(  sup__1, _2   𝔾__1, _2     ),  
#
where the supremum is taken over ( _1 , _2)  ∈Θ^*_Σ(r/2) ×{_1 + Θ_Σ(r)}—including (^*, ^*), 

    𝔾__1, _2   = 1/n ϖ g_i ·χ_i ·φ_ϖ /(2 r) ( ⟨_i , ⟩  ) ·ψ_ϖ/4 (⟨_i, _1 - ^*⟩ )    χ_i  = 1( | ε_i | ≤ϖ /4 ) ,

and g_1, …, g_n are independent standard normal variables. Conditional on {(y_i,_i)}_i=1^n,  𝔾__1, _2 is a centered Gaussian process and 𝔾_^*, ^*   = 0. 
For any two admissible pairs (_1, _2) and (_1',_2'), write = Σ^1/2 (  _2 - _1 )/ _2 - _1 _Σ, ' = Σ^1/2 ( _2' -_1') / '_2 - '_1 _Σ, and note that

    𝔾__1, _2  - 𝔾_'_1, '_2     =  __1, _2  -  __1' ,  '_1 + +  __1'  , '_1 +  - _'_1, '_2 
        = 1/n ϖ g_i ·χ_i ·φ_ϖ/(2 r) (⟨_i, ⟩ ) {ψ_ϖ/4 ( ⟨_i, _1 - ^* ⟩ ) - ψ_ϖ/4 ( ⟨_i, '_1 - ^* ⟩  ) }
            + 1/n ϖ g_i ·χ_i ·ψ_ϖ/4 ( ⟨_i, '_1 - ^* ⟩  )   {φ_ϖ/(2 r) (⟨_i, ⟩ ) - φ_ϖ/(2 r) (⟨_i, ' ⟩ )  } .

Recall that φ_R and ψ_R are, respectively, R- and (2/R)-Lipschitz continuous, and φ_R(u) ≤ (R/2)^2. It follows that
$
     ^* ( __1, _2  -  __1' ,  '_1 +  )^2 

    ≤1/(n ϖ)^2   ( 8/ϖ )^2( ϖ/4r )^4 χ_i  ⟨_i, _1 - _1' ⟩^2  =  1/4 r^4 n^2  χ_i  ⟨_i, _1 - _1'  ⟩^2 
$
and 
$
     ^* (    __1'  , '_1 +  - _'_1, '_2   )^2 

    ≤1/(n ϖ)^2  ( ϖ/2r )^2  χ_i ( ⟨_i, ⟩- ⟨_i , ' ⟩)^2  = 1/4 r^2 n^2 χ_i⟨_i, - ' ⟩^2 .
$
Together, the last two displays imply
$
^* ( 𝔾__1, _2  - 𝔾_'_1, '_2   )^2 ≤1/2 r^4 n^2  χ_i  ⟨_i, _1 -  _1'  ⟩^2  +  1/2r^2 n^2 χ_i ⟨_i, - ' ⟩^2.
$
Define another (conditional) Gaussian process {ℤ__1, _2} as 
$
ℤ__1, _2 =  1/2^1/2 r^2 n  g_i'  χ_i ⟨_i, _1 - ^* ⟩+ 1/2^1/2 r n g”_i χ_i ⟨_i, _2 - _1 ⟩/ _2 - _1 _Σ ,
$
where { g'_i } and {g_i”} are two dependent copies of { g_i}. The above calculations show that
$
 ^* ( 𝔾__1, _2  - 𝔾_'_1, '_2   )^2  ≤^* ( ℤ__1, _2  - ℤ_'_1, '_2   )^2  .
$
 Using Sudakov-Fernique's Gaussian comparison inequality (see, e.g. Theorem 7.2.11 in <cit.>) gives
#
 ^* ( sup__1, _2  𝔾__1, _2   ) 
 ≤^* ( sup__1, _2   ℤ__1, _2    ) . 
#
The same bound also applies to unconditional expectations of the two suprema.  For the random process {ℤ__1, _2 }, using the bound P(|ε_i|≤ϖ/4|_i ) ≤ f_u ϖ/2 (a.s.) we derive that
$
     ( sup__1, _2   ℤ__1, _2    )  

     ≤1/2^1/2 r^2 sup__1 ∈Θ^*_Σ(r/2)   _1 -^* _Σ· 1/n g_i' χ_i _i _2 +  1/2^1/2 r    1/n g”_i χ_i _i _2  

    ≤f_u^1/2 1/4 r     √( ϖp/n) +  f_u^1/2  1/2r   √(ϖp/n) = f_u^1/23  /4 r √( ϖp/n).
$
This, joint with (<ref>), (<ref>) and (<ref>), implies that, with probability at least 1-e^-t,
#
 Ω(r)      ≤5/4 Ω(r) + (f_u m_4)^1/2 √(t/n ϖ) + (4+1/3)ϖt/(4r)^2 n  

    ≤(f_u m_4)^1/2 √(t/n ϖ)  + 15 (π/2)^1/2  f_u^1/21/ 8 r √(ϖp/ n) +   (4+1/3)ϖt/16 r^2 n   . 
#


Finally, combining (<ref>), (<ref>) and (<ref>), we conclude that for all _1 ∈Θ^*_Σ(r/2) and _2 ∈_1+Θ_Σ(r) with r = ϖ/(16 max{m_4, 3 }^1/4υ_1),
$
       _h( _1 )  - _h( _2  )   - ⟨∇_h(_2) , _1 - _2 ⟩/ κ_l   _1- _2 _Σ^2   

                       ≥c_0  f_l' -  1/2 (f_u m_4)^1/2 √(t/n ϖ)  -    C_1   f_u^1/2  m_4^1/4 υ_1 √( p /n ϖ)  -  C_2 m_4^1/2 υ_1^2 t/  n ϖ 
$
holds with probability at least 1-e^-t, where C_1, C_2>0 are absolute constants.  Let nϖ be sufficiently large—n ϖ≳  m_4^1/2υ_1^2 (p+t)—so that the right-hand side is bounded from below by c_0  f_l' /2. This completes the proof. 
 



 


§ PROOFS OF TECHNICAL LEMMAS





 §.§ Proof of Lemma <ref>



For simplicity, define the re-scaled kernel W(u) = K_ϖ(u)=K(u/ϖ) / ϖ, which is also symmetric and non-negative.
Note that ρ_τ(u)= |u|/2 + (τ-1/2) u and (ρ_τ * W)(u) = (1/2) ∫_-∞^∞ |v| W(u-v) dv +  (τ-1/2) u. It thus suffices to prove that for any u∈ℝ,

    |u| ≤∫_-∞^∞ |v| W(u-v) dv ≤ |u| + κ_1 ϖ .

The upper bound follows from the triangle inequality and a change of variable that

    ∫_-∞^∞ |v| W(u-v) dv    ≤∫_-∞^∞ |u-v| W(u-v) dv + ∫_-∞^∞ |u | W(u-v) dv  
        = |u| + 1/ϖ∫_-∞^∞ |u-v| K(u-v/ϖ)  d v  = |u| +  ϖ∫_-∞^∞ |s| K(s)  d s  = |u| + κ_1 ϖ .

 
To prove the lower bound, we first assume u≥ 0. Utilizing the change of variable and the properties ∫ W(u) du=1 and ∫ u W(u) du =0,  we derive that

    ∫_-∞^∞ |v| W(u-v) dv = ∫_-∞^∞ | u + w| W(w)  d w 
        = ∫_-u^∞ (u+w) W(w)  d w - ∫_-∞^-u (u+w) W(w)  d w 
        =  ∫_-u^∞ (u+w) W(w)  d w +  ∫_u^∞ (-u+w) W(w)  d w 
        = u ∫_-u^u W(w)  d w + ∫_-u^∞ w W(w)  d w + ∫_u^∞ w W(w)  dw  
        = u -  ∫_u^∞  u W(w)  d w -  ∫_-∞^-u  u W(w)  d w+ ∫_-u^∞ w W(w)  d w_= -∫_-∞^-u w W(w) dw   by symmetry + ∫_u^∞ w W(w)  dw  
        = u + ∫_u^∞ (w-u) W(w)  dw_≥ 0 - ∫_-∞^-u (w+u) W(w)  d w_≤ 0≥ u .

This proves the lower bound when u≥ 0. The case where u<0 can be proven using a similar argument, and therefore we omit the details for brevity. 




 §.§ Proof of Lemma <ref>


Starting with R_ϖ(),  using a second-order Taylor series expansion yields
#
	R_ϖ() =  1/2 {  K_ϖ( ε-  t⟨,  ⟩) ⟨, ⟩^2 }    t∈[0,1] , #
where = Σ^-1/2 and = Σ^1/2= Σ^1/2 (- ^*).
By a change of variable and the Lipschitz continuity of f_ε |(·), we have
$
 {  K_ϖ( ε-  t⟨,  ⟩) | } = ∫_-∞^∞K(v) f_ε| ( t ⟨, ⟩+ ϖv ) d v ≥f_ε| ( t ⟨, ⟩)  - l_0()  κ_1 ϖ.
 
$ 
It follows that for any ∈^p satisfying _Σ≤ 1 (so that ∈𝔹^p(1)),
#
     2 R_ϖ()  ≥{ f_ε|(t ⟨,⟩) ⟨, ⟩^2 }  -  l_0 κ_1 ϖ·⟨, ⟩^2 

      = { f_ε|(  t  _2    _∈[0,1] ⟨,/ _2⟩) ⟨, / _2⟩^2 }  · _2^2 -  l_0 κ_1 ϖ· _2^2  

       ≥(f_l - l_0κ_1 ϖ)   _2^2 , 

# 
where the second inequality follows from Condition <ref>.
The same argument also applies to B_ϖ(). We thus omit the details. 

 §.§ Proof of Lemma <ref>



We only need to derive an upper bound for D̂_ϖ( ) - D_ϖ() uniformly over ∈^p in a compact subset. The same argument applies to  D_ϖ() - D̂_ϖ().  For each sample _i = (_i, ε_i) with _i = Σ^-1/2_i, define d_ϖ(; _i) =  ℓ_ϖ(ε_i - ⟨_i, ⟩ ) - ℓ_ϖ(ε_i), so that D̂_ϖ() = (1/n)  d_ϖ(; _i) for = Σ^1/2. Note that ℓ_ϖ(·) is continuously differentiable with |ℓ'_ϖ(u) | ≤τ̅= max(τ, 1-τ) for all u. Hence, for any _i and , ' ∈^p, | d_ϖ(; _i) -d_ϖ('; _i) |  ≤τ̅| ⟨_i, ⟩ - ⟨_i, '⟩ |.
In other words, d_ϖ(;_i) is τ̅-Lipschitz continuous in ⟨_i, ⟩.
 
 
For any fixed r>0 and some ϵ∈ (0,1) to be determined, define the random variable 

    Δ_ϵ(r)  =   1-ϵ/2τ̅r n^1/2sup_∈^p(r){D̂_ϖ() -  D_ϖ() } = 1-ϵ/2τ̅rsup_∈^p(r){1/n^1/2  (1-) d_ϖ(;_i)  } .
  
By Chernoff's inequality, for any z ≥ 0,
#
	P{ Δ_ϵ(r) ≥z } ≤exp[  - sup_λ≥0    {  λz - loge^λΔ_ϵ(r)   }  ] . 
#
To control the moment generating function e^λΔ_ϵ(r),  by Rademacher symmetrization we have 
$
e^λΔ_ϵ(r)  ≤exp{   (1-ϵ)  2 λ/2 τ̅r sup_∈^p(r)   1/n^1/2   e_i  d_ϖ(; _i)   } , 
$
where e_1, …, e_n are independent Rademacher random variables.  Recall that d_ϖ( ; _i) is τ̅-Lipschitz continuous in ⟨_i, ⟩,  and d_ϖ( ; _i)=0 if ⟨_i, ⟩ = 0. Then, applying the Ledoux-Talagrand contraction inequality (see Theorem 4.12 and inequality (4.20) in <cit.>) yields
$
    exp{   (1-ϵ)   λ/  τ̅r sup_∈^p(r)    1/n^1/2 e_i  d_ϖ(; _i)  }  

     ≤exp{  (1-ϵ) λ/r sup_∈^p(r)    1/n^1/2  e_i  ⟨_i, ⟩}  ≤exp{   (1-ϵ)λ  1/n^1/2 e_i _i _2 } .
$
For this ϵ∈ (0,1), there exists an ϵ-net {_1,  … , _N_ϵ} of 𝕊^p-1 with cardinality N_ϵ≤ (1+2/ϵ)^p such that e_i _i  _2 ≤ (1-ϵ)^-1max_1≤ j≤ N_ϵ e_i _j^_i. Therefore,
$
 exp{    (1-ϵ) λ 1/n^1/2 e_i _i _2 } 
  ≤∑_j=1^N_ϵ   exp(  λ/n^1/2  e_i _j^_i  ) .
$
Write S_j = n^-1/2 e_i _j^_i, which is a sum of zero-mean random variables.
Note that e_i ∈{-1, 1} is symmetric, and  Condition <ref> ensures that
logexp (  c e_i _j^_i ) ≤ c^2 υ_1^2/2 for all c∈. Consequently,
$
     exp(λS_j ) =  ∏_i=1^n exp(  λn^-1/2 e_i _j^_i  ) ≤∏_i=1^n e^λ^2 υ_1^2 / (2n ) = e^λ^2 υ_1^2 / 2 ,
$
from which it follows that
$
  loge^λΔ_ϵ(r)   ≤logN_ϵ+    1 / 2 υ_1^2 λ^2 .
 $
For any u≥ 0,  note that
$
sup_λ≥0  {  λz - loge^λΔ_ϵ(r)   } ≥-logN_ϵ+ sup_λ≥0  (  λz  -  1/2 υ_1^2λ^2 ) = -logN_ϵ+ z^2/(2υ_1^2).
$
Substituting this into (<ref>) and taking v= z^2/(2υ_1^2), we obtain that with probability at least 1-exp{ plog(1+2/ϵ) - v },
#
	 sup_∈^p(r)   { D̂_ϖ()   - D_ϖ()  }  ≤2τ̅υ_1 /1-ϵ   r   √(2v/n) . 
# 
This proves (<ref>) by setting ϵ=2/(e^4-1) and v= 4p +u.


Via a peeling/slicing argument, next, we prove a uniform version of (<ref>), which holds for all ∈^p(r_l, r_u) = {∈^p: r_l ≤_2 ≤ r_u}.  For some γ>1 to be determined, and positive integers k =1 ,…, N := ⌈log (r_u/r_l )/log(γ) ⌉, define the sets Θ_k={∈^p:  γ^k-1 r_l ≤_2 ≤γ^k  r_l }, so that ^p(r_l, r_u) ⊆∪_k=1^N Θ_k.
Then,
$
     	P{   ∃∈^p(r_l, r_u)    D̂_ϖ()   -  D_ϖ()  >  2√(2)γ/1-ϵ τ̅υ_1    _2  √( v/n)    } 

    ≤∑_k=1^N  	P{   ∃∈Θ_k     D̂_ϖ()   -  D_ϖ()   >2√(2)γ/1-ϵ  τ̅υ_1  γ^k-1 r_l    √(v/n)     } 

    ≤∑_k=1^N  	P{  sup_∈^p(γ^k r_l)    D̂_ϖ()   -  D_ϖ()    >  2√(2)/1-ϵ τ̅υ_1 γ^k  r_l    √(v/n)    } 

    (i)≤ ∑_k=1^N   exp{ p log(1+2/ϵ) - v } ≤⌈log(r_ur_l)/log(γ) ⌉exp{ p log(1+2/ϵ) - v  } ,
$
where inequality (i) follows from (<ref>) with r= γ^k  r_l for k=1,…, N.  Taking ϵ=2/(e^4-1), γ = e^1/e and v=4p+log{ e log(r_u/r_l) }+u yields that with probability at least 1- e^-u,
#
D̂_ϖ()  - D_ϖ() ≤4.25 τ̅υ_1 · _2 √(4 p + log{ e log( r_u/r_l ) } +  u/n) . # 
This proves (<ref>) by taking (r_l, r_u) = (δ, r). 




 §.§ Proof of Lemma <ref>


Proof of (<ref>). By a change of variable =  Σ^ 1/2 ( - ^*), define the centered gradient process
#
  G_ϖ()  =    Σ^-1/2 { Q̂_ϖ() - Q_ϖ() }     =  1/n  (1-)  {  K̅_ϖ(_i^- ε_i ) - τ} _=: ξ_i,  _i   . # 
For any ϵ∈ (0, R), there exists an ϵ-net {_1, … , _N_ϵ} of ^p(R) with N_ϵ≤ (1+2R/ϵ)^p. For any ∈^p(R), there exists some 1≤ j≤ N_ϵ such that - _j _2≤ϵ. Then, by the triangle inequality,
$
	    G_ϖ()  _2 ≤  G_ϖ() - G_ϖ(_j ) _2 +  G_ϖ(_j) _2. 
$  

We first control the approximation error G_ϖ () - G_ϖ(_j ) _2. Using integration by parts and a change of variable, we have (ξ_i, |_i ) = ∫_-∞^∞ K(u) F_ε_i | _i (_i^ - h u )  d u. Condition <ref> ensures that
$
    (ξ_i,  _i  ) - (ξ_i,_j  _i  ) _2  ≤sup_∈𝕊^p-1  { f_u()|⟨_i, ⟩·⟨_i, -_j ⟩|}  ≤f_u  ϵ.
$
Turning to ξ_i,_i and ξ_i,_j_i, since K(·) is bounded by κ_u, we have
$
  1/n  ξ_i,   _i - 1/n  ξ_i,_j    _i _2      ≤sup_∈𝕊^p-1 1/n   |  K̅_ϖ(_i^- ε_i) - K̅_ϖ(_i^_j - ε_i)  | ·|_i^| 

    ≤κ_u/ϖ sup_∈𝕊^p-1 1/n   | _i^(- _j) | ·|_i^|  

    ≤κ_u  ϵ/ϖ  ·λ_max (   1/n _i _i^) .
$
Note that _i = (1, _i,-^)^, where _i,-∈^p-1 are zero-mean sub-Gaussian random vectors.   By a standard covering argument, paired with Bernstein's inequality, it can be shown that (see, e.g. Theorem 4.6.1 in <cit.>) with probability at least 1-(1/2)e^-u,
#
 λ_max (   1/n _i _i^)    ≤1 + C_1 υ_1^2 (  √(p+ u/n) + p+u/n)  , #
where C_1 >0 is an absolute constant. Provided n≳υ_1^4( p+u), it follows that with probability at least 1-(1/2)e^-u, 
#
       G_ϖ() - G_ϖ(_j ) _2 ≤f_u ϵ+ 2  κ_u ϵ/ ϖ
#
holds uniformly over all the pairs (, _j) satisfying - _j _2≤ϵ.

It remains to deal with G_ϖ(_j)  _2 for each j=1,…, N_ϵ. For simplicity, we write ξ_ij = ξ_i,_j =K̅_ϖ( _i^_j - ε_i ) - τ, and define
$
 S_j = 1/n  (ξ_i - ξ_i)      _j = 1/n   { ξ_ij  _i,- -  ( ξ_ij  _i,-)} ∈^p-1.
$
Then, G_ϖ(_j)  _2^2 = S_j^2 + _j  _2^2. For S_j, note that ξ_ij∈ [-τ, 1-τ ]. As a direct application of Hoeffding's inequality, we have that for any v≥ 0,
#
	 P (  |S_j | ≥√(log4  + v/2n )   ) ≤1/2 e^-v. 
#
Next we use a covering argument to bound _j  _2. For any δ∈ (0,1), there exists an δ-net _δ of 𝕊^p-2 (unit sphere in ^p-1) with cardinality M_δ≤ (1+2/δ)^p-1 such that 

    _j  _2 ≤ (1-δ)^-12τ̅υ_1/n^1/2max_∈_δ1/2 τ̅υ_1 n^1/2⟨, ξ_ij_i,- - ( ξ_ij_i,- ) ⟩_=: Δ_δ,

where τ̅= max(1-τ,τ). For any z ≥ 0, applying Chernoff's inequality gives 
$
	P(Δ_δ≥z ) ≤exp{ - sup_λ≥0   (  λz - loge^λΔ_δ   ) }  .
$
By Rademacher symmetrization and independence,
$
e^λΔ_δ   ≤exp(   max_∈_δ λ/ τ̅υ_1 n^1/2 e_i ξ_ij ^_i,-  ) ≤∑_u∈_δ ∏_i=1^n exp(    λ/ τ̅υ_1 n^1/2   e_i ξ_ij  ^_i,-   ) ,
$
where e_i's are independent Rademacher random variables. Fix ∈_δ, and set ω_i  = ^_i,-   /υ_1. We further have
$
  exp(    λ/ τ̅n^1/2   e_i ξ_ij ω_i   )   = ∑_k=0^∞1/k! ( λ/n^1/2)^k    (e_i ξ_ij  ω_i  / τ̅)^k _= 0  if k is odd ≤1+∑_ℓ=1^∞1/(2ℓ)! ( λ/n^1/2 )^2ℓ (  ω_i ^2ℓ ).
 $
 Recall from Condition <ref> that (e^t ω_i   )≤ e^t^2/2 for all t∈, and (ω_i^2) ≤ 1. For ℓ≥ 2,
 $
  ( ω_i^2ℓ ) = 2ℓ∫_0^∞u^2ℓ-1 P(|ω_i| ≥u) d u ≤4 ℓ∫_0^∞u^2ℓ-1 e^-u^2/2 du = 2^ℓ+1 ℓ!  .
 $
Substituting this into the previous exponential moment bound yields
$
 exp(    λ/ τ̅n^1/2   e_i ξ_ij ω_i   )  ≤1  +  λ^2/n +∑_ℓ=2^∞4/3/ ℓ! ( λ^2 /n  )^ ℓ 
≤exp( 2/√(3)  n   λ^2 ), 
$
which in turn implies
$
 loge^λΔ_δ ≤logM_δ+ 2/√(3) λ^2    sup_λ≥0  { λz - loge^λΔ_δ  }  ≥- logM_δ+  √(3)/8 z^2 .
$
Combining this with Chernoff's bound and a change of variable, we obtain that with probability at least 1-(1/2)e^-v,
#
   _j  _2^2  ≤ 32 τ̅^2υ_1^2/3^1/2(1-δ)   (p-1)log(1+2/δ) +log2 + v /n .  
#
Together, (<ref>) and (<ref>) with a properly chosen δ, say, δ=2/(e^2-1), imply that G_ϖ(_j  ) _2 ≤ C_2 υ_1 √((p+v)/n) holds with probability at least 1-e^-v, where C_2>0 is an absolute constant. Taking the union bound over j=1,…, N_ϵ, we have that with probability at least 1- exp{ plog(1+2R/ϵ) - v},
#
    max_1≤j≤N_ϵ G_ϖ(_j  ) _2 ≤C_2 υ_1 √(p+ v /n) . 
#

Taking ϵ=R ϖ/n and v=log(2)+plog(1+2  n/ϖ)+u in (<ref>) and (<ref>), we obtain that  with probability at least 1-e^-u,
$
 sup_∈^p(R)   G_ϖ() _2 ≤( f_u ϖ+  2κ_u ) R/n + C_2 υ_1 √(log2 + plog( e + 2e n/ϖ)+ u /n)  
$
as long as n≳υ_1^4(p+u). This proves (<ref>).

For  the population gradient, noting that |K̅_ϖ( y_i - _i^ ) - τ| ≤τ̅ for any ∈^p, we have sup_∈^p∇ Q_ϖ() _Σ^-1≤τ̅sup_∈𝕊^p-1 | ⟨, ⟩ | ≤τ̅. At ^*, the bound ∇ Q_ϖ(^*) _Σ^-1≤ 0.5 l_0 κ_2 ϖ^2 follows from (C.2) in <cit.>.

Proof of (<ref>).  For ∈^p, define after a change of variable =  Σ^1/2 (  - ^*) that
$
 _ϖ()  = Σ^-1/2 ∇^2 _ϖ( ) Σ^-1/2  = 1/n K_ϖ(ε_i - ⟨_i, ⟩) _i _i^     _ϖ() =  { _ϖ() }  .
$
To upper bound sup_∈^p(R)_ϖ()  - _ϖ()  _2, we use a similar discretization argument as in the proof of (<ref>) and obtain
$
     sup_∈^p(R)   _ϖ()  - _ϖ()  _2  

     ≤l_K ϵ/ϖ^2 max_1≤i≤n  _i _2 · 1/n _i _i^_2  

         +   max_1≤j≤N_ϵ   _ϖ(_j)  - _ϖ(_j)  _2  _sampling error+     max_1≤j≤N_ϵ   _ϖ(_j)  - _ϖ(_j)  _2 _ approximation error ,
$
where l_K is the Lipschitz constant of the kernel K(·), {_1, …, _N_ϵ} is an ϵ-net of ^p(R) and N_ϵ≤ (1+2R/ϵ)^p.
For the last term on the right-hand side, the Lipschitz continuity of f_ε |(·) ensures that
$
max_1≤j≤N_ϵ   _ϖ(_j)  - _ϖ(_j)  _2 ≤l_0 m_3 ϵ, 
$
where m_3 = sup_∈𝕊^p-1 |⟨, ⟩|^3.



We have already shown that λ_max ( n^-1_i _i^ ) ≤ 2 with probability at least 1-(1/2)e^-u as long as n≳υ_1^4(p+u). Moreover, applying
Theorem 2.1 in <cit.> to each _i,- yields that  with probability at least 1-e^-z,
$
  _i,- _2^2 ≤υ_1^2 {   p-1 + 2√((p-1) z) + 2 z  } 
 ≤υ_1^2 ( √(p-1) + √(2 z) )^2 .
$
Taking the union bound over i=1,…, n and setting z= log n + u, we obtain that with probability 1- e^-u,
$
	max_1≤i≤n  Σ^-1/2 _i _2 = max_1≤i≤n  _i  _2  ≤1 + υ_1  { √(p-1) + √(2 logn +2 u  ) } ≤C υ_1 ( p + logn + u )^1/2 .
$

Turning to max_1≤ j≤ N_ϵ_ϖ(_j)  - _ϖ(_j)  _2, it has been shown in the proof of Proposition 3.2 in <cit.> (see, e.g. (C.61)) that with probability at least 1- e^-u,
$
 max_1≤j≤N_ϵ   _ϖ(_j)  - _ϖ(_j)  _2 ≲υ_1^2 { √(p log(R/ϵ)   + u/n ϖ) + p log(R/ϵ)  + u/n ϖ   }.
$
Finally, as long as n≳υ_1^4(p+u), taking ϵ = (ϖ/n)^2R yields the bound
$
    sup_∈^p(R)   _ϖ()  - _ϖ()  _2 
 
   ≲υ_1^2 { √(p log(n /ϖ)   + u/n ϖ) + p log(n/ϖ)  + u/n ϖ   }   +      { υ_1 (p+ logn+ u)^1/2   + l_0  m_3  ϖ^2 }  R /n^2.
$
This proves (<ref>), and thus completes the proof.  




 §.§ Proof of Lemma <ref>


For each t=0,1,…, T-1,  we apply the concentration inequality for Lipschitz functions of standard normal random variables and obtain that
$
 P (  _t_2   ≥√(p) + √(2z) ) ≤e^-z,    z≥0.	
$
Combining this with the union bound (over t=0,1,…, T-1) yields (<ref>).

Note that  _t _2^2 follows the chi-square distribution χ_p^2, which is a special case of the gamma distribution Γ(p/2,1/2). The centered variable, _t _2^2- p, is known to be sub-gamma with parameters v=2p and c=2 <cit.>.  Let Z= ∑_t=0^T-1ρ^t  ( _t_2^2 - p ). For each t and 0<λ <1/c,
$
 loge^λρ^t  (  _t_2^2 - p )  ≤v λ^2 ρ^2t /2(1 - c λρ^t ) ≤v λ^2 ρ^2t /2(1-cλ).
$
By independence,
$
loge^λZ  = ∑_t=0^T-1  loge^λρ^t  (  _t_2^2 - p )  ≤v λ^2  ∑_t=0^T-1ρ^2t /2(1-cλ) ≤v/1-ρ^2   λ^2  /2(1-cλ) .
$
In other words, the centered variable Z is sub-gamma with parameters (v/(1-ρ^2), c)=(2p/(1-ρ^2), 2). Applying Chernoff's bound to Z (see, e.g. Section 2.4 of <cit.>) yields that, for any z>0,
$
 P (  Z > 2 √( p z /1-ρ^2) + 2 z  ) ≤e^-z.
$
This, combined with the elementary inequality ∑_t=0^T-1ρ^t ≤ 1/(1-ρ), proves (<ref>). 

 

 §.§ Proof of Lemma <ref>

 
To begin with, note that conditioned on event _0(B) ∩_1 (δ_0, δ_1) with δ_0 + b^* < ϕ_1,  
$
sup_∈Θ_Σ^*(1)   ∇_ϖ() _Σ^-1      ≤δ_1+ τ̅, 

_ϖ(  ) -  _ϖ( ^*  )     ≥(  ϕ_1 - δ_0  - b^* _= Δ)  - ^* _Σ    ∈Θ_Σ^*(1)^$
and ^(t+1) = ^(t) - η_0 Σ^-1∇_ϖ(^(t))  -   η_0  σΣ^-1/2_t / n for t=0,1,…, T-1.

Now assume that ^(t)  -^* _Σ≤ 1 for some t≥ 0. 
Recall that δ_1 < ϕ_1 < 0.5 f_l. Hence, conditioned further on  defined in (<ref>), we have
$
    ^ (t+1) - ^* _Σ      ≤ ^(t) - ^* _Σ + η_0   ∇_ϖ(^(t) ) _Σ^-1 +   η_0 σ/ n    _t_2  

     ≤1 + (   f_l +  τ̅)  η_0     ≤2  ,
$
where we used the assumptions η_0 ≤ 1/ (f_l + τ̅) and n ≥ 2  B_T σ/f_l in the last inequality.  Proceeding via proof by contradiction,   suppose ^(t+1) - ^* _Σ > 1 so that
$
    Δ· ^(t+1) - ^* _Σ ≤_ϖ(   ^(t+1) ) -  _ϖ( ^*  ) .
$
For the right-hand side, we have
$
           _ϖ(   ^(t+1) ) -  _ϖ( ^*  ) =  _ϖ(  ^(t+1 ) ) - _ϖ(^(t) ) + _ϖ(^(t) ) -  _ϖ( ^*  )  

     (i)≤ ⟨∇_ϖ(^(t) ),  ^(t+1) - ^(t)  ⟩+ f_u    ^(t+1) - ^(t)  _Σ^2 - ⟨∇_ϖ(^(t) ) , ^* - ^(t)  ⟩

     = 1/η_0 ⟨^(t)  -    ^(t+1)   ,    ^(t+1) - ^* ⟩_Σ + f_u     ^(t+1) - ^(t)  _Σ^2  +  σ/ n⟨Σ^-1/2  _t  ,    ^(t+1) - ^* ⟩
 
     = 1/2 η_0  ^(t)  - ^* _Σ^2 - 1/2η_0     ^(t+1) - ^* _Σ^2 - 1/2 η_0    ^(t+1) - ^(t)  _Σ^2  
 
        + f_u      ^(t+1) - ^(t)  _Σ^2 +      σ/ n ⟨Σ^-1/2  _t  ,    ^(t+1) - ^* ⟩

     (ii)≤  1/2 η_0  ^(t)  - ^* _Σ^2 - 1/2η_0    ^(t+1) - ^* _Σ^2 +       σ/  n    ^(t+1) - ^* _Σ ·  _t _2  

     (iii)≤   1/2 η_0  ^(t)  - ^* _Σ^2 - 1/2η_0    ^(t+1) - ^* _Σ^2 +   B_T σ/ n      ^(t+1) - ^* _Σ ,
$
where inequality (i) follows from the restricted smoothness property (<ref>), inequality (ii) holds if η_0 ≤ 1/(2 f_u), and inequality (iii) uses conditioning on .  
Provided that B_T σ/ n ≤Δ,  combining the above lower and upper bounds on _ϖ(   ^(t+1) ) -  _ϖ( ^*  )  yields
$
     ^(t+1) - ^* _Σ^2 ≤ ^(t)  - ^* _Σ^2  ≤1 ,
$ 
which leads to a contradiction. Therefore, starting from an initial value ^(0)∈Θ^*(1),  and conditioning on event _0 ∩_1 ∩ with properly chosen parameters, we must have ^(t ) - ^* _Σ≤ 1 for all t= 1,…, T. 



 §.§ Proof of Lemma <ref>

 
Recall that conditioning on _0 ∩_1,  _ϖ∈Θ^*_Σ(r_0) with r_0 = (δ_0 + b^*)/ϕ_1, ^(t+1) = ^(t) - η_0 Σ^-1∇_ϖ(^(t))  +  η_0  σΣ^-1/2_t / n and ∇^2 _ϖ( ) _Σ^-1≤ 2 f_u for all ∈Θ^*_Σ(R). The upper bound on the Hessian also implies
$
	⟨∇_ϖ(_1) -  ∇_ϖ(_2) , _1 - _2 ⟩≥1/2f_u    ∇_ϖ(_1) -  ∇_ϖ(_2) _Σ^-1^2 ,   _1, _2 ∈Θ^*_Σ(R) .
$
Provided  η_0 ≤ 1/(2f_u) and R ≥ R_0 + r_0,  applying this bound with (_1, _2) = (^(0) ,  _ϖ  ) we obtain  
$
	  ^(1) - _ϖ   _Σ^2      =   ^(0)  -   η_0 Σ^-1 ∇_ϖ(^(0))  +  η_0  σΣ^-1/2_0  / n- _ϖ   _Σ^2  

	    =  ^(0) - _ϖ   _Σ^2   + η_0^2   Σ^-1/2 ∇_ϖ(^(0)) - σ_0 / n _2^2  

	         - 2 η_0 ⟨^(0) -_ϖ, ∇_ϖ(^(0))  - σΣ^ 1/2_0 / n ⟩

	     ≤ ^(0) - _ϖ   _Σ^2  + η_0^2   ∇_ϖ(^(0))  _Σ^-1^2 +      ( η_0 σ/n )^2  _0 _2^2 +   2 η_0^2 σ/n   ∇_ϖ(^(0))  _Σ^-1  _0 _2     

	           - η_0/f_u   ∇_ϖ(^(0))  _Σ^-1^2  + 2  η_0 σ/n   ^(0) - _ϖ   _Σ _0 _2 

	     ≤ ^(0) - _ϖ   _Σ^2 - η_0/2 f_u   ∇_ϖ(^(0))  _Σ^-1^2   +       2 (R_0 +   η_0 τ̅B)     η_0 σ/n    _0 _2 + ( η_0 σ/n )^2  _0 _2^2   .
$

For any given T_0≥ 1,  write R_t = ^(t) - _ϖ_Σ for t=1, …, T_0.  Provided R ≥max_0≤ t≤ T_0-1 R_t + r_0, it can similarly shown that for any 0≤ t≤ T_0-1,
$
	     ^(t+1) - _ϖ_Σ^2   

     ≤ ^(t) - _ϖ   _Σ^2 - η_0/2 f_u   ∇_ϖ(^(t))  _Σ^-1^2   +       2 (R_t +   η_0 τ̅B)     η_0 σ/n    _t _2 + ( η_0 σ/n )^2  _t _2^2  .
$
Given z≥ 0,  by Lemma <ref> we have that with probability at least 1-e^-z,
$	
	max_0≤t≤T_0-1  _t _2 ≤B_T_0 := √(p) + √(2(logT_0 + z ) ) .
$
Define e_ priv = η_0 B_T_0σ/n. 
For some ϵ∈(0,1) to be determined, the above recursive bound implies
$
	R_t+1^2 ≤(1+ϵ) R_t^2 + (1+1/ϵ)  e_priv^2 + C_0 e_priv ,   t = 0, 1, …, T_0 -1
$
and hence
$
R_t^2      ≤(1+ϵ)^t R_0^2 + { (1+1/ϵ) e_priv^2 + C_0 e_priv } ∑_k=0^t-1 (1+ϵ)^k   

    ≤(1+ϵ)^t R_0^2 + (1+ϵ)^t  -1/ϵ { (1+1/ϵ) e_priv^2 + C_0 e_priv },   t= 1, …, T_0, 
$
where C_0 = 2 η_0 τ̅B. Provided T_0≥ 2 and 

    n≥e-1/4-e  ( 2  τ̅B + 1/2 ) max{ 1 ,  η_0/R_0 }^2 T_0  B_T_0σ >  2 (T_0+1)    B_T_0σ ,

taking ϵ=1/T_0 ∈ (0,1) we obtain that 
$
 R_t^2     ≤e R_0^2 + (e-1)    {  (T_0+1) e_priv  + C_0}  T_0 e_priv  

     ≤e R_0^2 + (e-1)   ( 2   τ̅B  +1/2 )   T_0  B_T_0 σ/n  η_0^2  ≤e R_0^2 + (4-e) R_0^2 = 4 R_0^2
$
for all t=1, …, T_0, as claimed. 


 
















informs2014



















