More Like this

1. Private Optimal Inventory Policy Learning for Feature-Based Newsvendor with Unknown Demand

   https://doi.org/10.1287/mnsc.2023.01268  

   Zhao, Tuoyi; Zhou, Wen-Xin; Wang, Lan (October 2024, Management Science)

   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 estimating a privacy-preserving optimal inventory policy within the f-differential privacy framework, an extension of the classical [Formula: see text]-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: (i) unknown demand distribution and nonsmooth loss function, (ii) provable privacy guarantees for individual-level data, and (iii) 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 with 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. This paper was accepted by J. George Shanthikumar, data science. Funding: This work was supported by the National Science Foundation [Grants DMS-2113409 and DMS 2401268 to W.-X. Zhou, and FRGMS-1952373 to L. Wang]. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2023.01268 . 

   more » « less
2. Optimal Rates for Robust Stochastic Convex Optimization

   https://doi.org/10.4230/LIPIcs.FORC.2025.9  

   Gao, Changyu; Lowy, Andrew; Zhou, Xingyu; Wright, Stephen J (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Bun, Mark (Ed.)

   Machine learning algorithms in high-dimensional settings are highly susceptible to the influence of even a small fraction of structured outliers, making robust optimization techniques essential. In particular, within the ε-contamination model, where an adversary can inspect and replace up to an ε-fraction of the samples, a fundamental open problem is determining the optimal rates for robust stochastic convex optimization (SCO) under such contamination. We develop novel algorithms that achieve minimax-optimal excess risk (up to logarithmic factors) under the ε-contamination model. Our approach improves over existing algorithms, which are not only suboptimal but also require stringent assumptions, including Lipschitz continuity and smoothness of individual sample functions. By contrast, our optimal algorithms do not require these stringent assumptions, assuming only population-level smoothness of the loss. Moreover, our algorithms can be adapted to handle the case in which the covariance parameter is unknown, and can be extended to nonsmooth population risks via convolutional smoothing. We complement our algorithmic developments with a tight information-theoretic lower bound for robust SCO. 

   more » « less
3. Nonasymptotic Convergence Rates for the Plug-in Estimation of Risk Measures

   https://doi.org/10.1287/moor.2022.1333  

   Bartl, Daniel; Tangpi, Ludovic (November 2022, Mathematics of Operations Research)

   Let ρ be a general law-invariant convex risk measure, for instance, the average value at risk, and let X be a financial loss, that is, a real random variable. In practice, either the true distribution μ of X is unknown, or the numerical computation of [Formula: see text] is not possible. In both cases, either relying on historical data or using a Monte Carlo approach, one can resort to an independent and identically distributed sample of μ to approximate [Formula: see text] by the finite sample estimator [Formula: see text] (μ_Ndenotes the empirical measure of μ). In this article, we investigate convergence rates of [Formula: see text] to [Formula: see text]. We provide nonasymptotic convergence rates for both the deviation probability and the expectation of the estimation error. The sharpness of these convergence rates is analyzed. Our framework further allows for hedging, and the convergence rates we obtain depend on neither the dimension of the underlying assets nor the number of options available for trading. Funding: Daniel Bartl is grateful for financial support through the Vienna Science and Technology Fund [Grant MA16-021] and the Austrian Science Fund [Grants ESP-31 and P34743]. Ludovic Tangpi is supported by the National Science Foundation [Grant DMS-2005832] and CAREER award [Grant DMS-2143861]. 

   more » « less
4. A new inexact gradient descent method with applications to nonsmooth convex optimization

   https://doi.org/10.1080/10556788.2024.2322700  

   Khanh, Pham Duy; Mordukhovich, Boris S; Tran, Dat Ba (March 2024, Optimization Methods and Software)

   The paper proposes and develops a novel inexact gradient method (IGD) for minimizing smooth functions with Lipschitzian gradients. We show that the sequence of gradients generated by IGD converges to zero. The convergence of iterates to stationary points is guaranteed under the Kurdyka- Lojasiewicz property of the objective function with convergence rates depending on the KL exponent. The newly developed IGD is applied to designing two novel gradient-based methods of nonsmooth convex optimization such as the inexact proximal point methods (GIPPM) and the inexact augmented Lagrangian method (GIALM) for convex programs with linear equality constraints. These two methods inherit global convergence properties from IGD and are confirmed by numerical experiments to have practical advantages over some well-known algorithms of nonsmooth convex optimization 

   more » « less
5. High-Dimensional Robust Mean Estimation via Gradient Descent

   Cheng, Yu; Diakonikolas, Ilias; Ge, Rong; Soltanolkotabi, Mahdi (July 2020, International Conference on Machine Learning 2020)

   We study the problem of high-dimensional robust mean estimation in the presence of a constant fraction of adversarial outliers. A recent line of work has provided sophisticated polynomialtime algorithms for this problem with dimension-independent error guarantees for a range of natural distribution families. In this work, we show that a natural non-convex formulation of the problem can be solved directly by gradient descent. Our approach leverages a novel structural lemma, roughly showing that any approximate stationary point of our non-convex objective gives a near-optimal solution to the underlying robust estimation task. Our work establishes an intriguing connection between algorithmic high-dimensional robust statistics and non-convex optimization, which may have broader applications to other robust estimation tasks. 

   more » « less