Paper: arXiv 2403.09532

Authors: Ariel Neufeld, Matthew Ng Cheng En, Ying Zhang

Abstract

In this paper we develop a Stochastic Gradient Langevin Dynamics (SGLD) algorithm tailored for solving a certain class of non-convex distributionally robust optimisation (DRO) problems. By deriving non-asymptotic convergence bounds, we build an algorithm which for any prescribed accuracy $\varepsilon>0$ outputs an estimator whose expected excess risk is at most $\varepsilon$. As a concrete application, we consider the problem of identifying the best non-linear estimator of a given regression model involving a neural network using adversarially corrupted samples. We formulate this problem as a DRO problem and demonstrate both theoretically and numerically the applicability of the proposed robust SGLD algorithm. Moreover, numerical experiments show that the robust SGLD estimator outperforms the estimator obtained using vanilla SGLD in terms of test accuracy, which highlights the advantage of incorporating model uncertainty when optimising with perturbed samples.

Complexity vs Empirical Score

  • Math Complexity: 8.5/10
  • Empirical Rigor: 5.0/10
  • Quadrant: Holy Grail — high math complexity, high empirical rigor

Why this score: The paper presents strong theoretical contributions with non-asymptotic convergence bounds for a novel robust SGLD algorithm applied to non-convex DRO. While the mathematical foundation is rigorous and highly complex, the empirical evaluation is mostly illustrative via numerical experiments on neural network regression under adversarial corruption.

Research Flowchart

  flowchart TD
    A[Goal: Solve Non-Convex DRO using Robust SGLD] --> B[Input: Adversarially Corrupted Regression Samples & NN Model]
    B --> C[Formulate Non-Convex DRO Problem with Model Uncertainty]
    C --> D[Develop Robust SGLD Algorithm & Derive Non-Asymptotic Convergence Bounds]
    D --> E[Compute Estimator for Prescribed Accuracy ε]
    E --> F[Outcomes: Guaranteed Risk ≤ ε & Superior Test Accuracy vs Vanilla SGLD]

Cited References (169)

  1. Strong convergence of an explicit numerical method for SDEs with nonglobally Lipschitz continuous coefficients (2012)
  2. A note on tamed Euler approximations (2013)
  3. Numerical approximations of stochastic differential equations with non-globally Lipschitz continuous coefficients (2015)
  4. Euler approximations with varying coefficients: the case of superlinearly growing diffusion coefficients (2016)
  5. Theoretical guarantees for approximate sampling from smooth and log-concave densities (2017)
  6. F urther and stronger analogy between sampling and optimization: L angevin M onte C arlo and gradient descent (2017)
  7. Nonasymptotic convergence analysis for the unadjusted L angevin algorithm (2017)
  8. High-dimensional B ayesian inference via the unadjusted L angevin algorithm (2019)
and 161 more
  1. User-friendly guarantees for the L angevin Monte Carlo with inaccurate gradient (2019)
  2. Nonasymptotic bounds for sampling algorithms without log-concavity (2020)
  3. On stochastic gradient L angevin dynamics with dependent data streams in the logconcave case (2021)
  4. On stochastic gradient langevin dynamics with dependent data streams: The fully nonconvex case (2021)
  5. Nonasymptotic estimates for Stochastic Gradient L angevin Dynamics under local conditions in nonconvex optimization (2023)
  6. The tamed unadjusted L angevin algorithm (2019)
  7. Taming neural networks with tusla: Nonconvex learning via adaptive stochastic gradient langevin algorithms (2023)
  8. Non-asymptotic estimates for TUSLA algorithm for non-convex learning with applications to neural networks with ReLU activation function (2023)
  9. Ergodicity for SDEs and approximations: locally Lipschitz vector fields and degenerate noise (2002)
  10. Strong and weak divergence in finite time of Euler’s method for stochastic differential equations with non-globally Lipschitz continuous coefficients (2011)
  11. Quantitative Harris-type theorems for diffusions and McKean–Vlasov processes (2019)
  12. Nonasymptotic mixing of the MALA algorithm (2013)
  13. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis (2017)
  14. Sharp convergence rates for L angevin dynamics in the nonconvex setting (2018) — link
  15. Global convergence of L angevin dynamics based algorithms for nonconvex optimization (2018)
  16. An introduction to MCMC for machine learning (2003)
  17. MCMC methods for functions: modifying old algorithms to make them faster (2013)
  18. Partial differential equations and stochastic methods in molecular dynamics (2016)
  19. Distributionally robust stochastic optimization with W asserstein distance (2022)
  20. Efficient optimal transport algorithm by accelerated gradient descent (2022)
  21. Computational aspects of robust optimized certainty equivalents (2017)
  22. On the properties of the softmax function with application in game theory and reinforcement learning (2017) — link
  23. Minimizing CVaR and VaR for a portfolio of derivatives (2006)
  24. Risk, uncertainty and profit (1921)
  25. Risk, ambiguity, and the Savage axioms (1961)
  26. Distributionally robust optimization under moment uncertainty with application to data-driven problems (2010)
  27. Data-driven distributionally robust optimization using the W asserstein metric: performance guarantees and tractable reformulations (2018)
  28. Robust resource allocations in temporal networks (2012)
  29. Models for minimax stochastic linear optimization problems with risk aversion (2010)
  30. Production planning with a two-stage stochastic programming model in a kitting facility under demand and yield uncertainties (2020)
  31. Target-oriented robust location–transportation problem with service-level measure (2021)
  32. Distributionally robust linear and discrete optimization with marginals (2022)
  33. Appointment scheduling under time-dependent patient no-show behavior (2020)
  34. Appointment scheduling with limited distributional information (2015)
  35. Likelihood robust optimization for data-driven problems (2016)
  36. Data-driven distributionally robust capacitated facility location problem (2021)
  37. Distributionally robust convex optimization (2014)
  38. Numerical method for approximately optimal solutions of two-stage distributionally robust optimization with marginal constraints (2022) — link
  39. Feasible approximation of matching equilibria for large-scale matching for teams problems (2023) — link
  40. Quantifying distributional model risk via optimal transport (2019)
  41. Optimal transport-based distributionally robust optimization: Structural properties and iterative schemes (2022)
  42. Exploiting partial correlations in distributionally robust optimization (2021)
  43. Distributionally robust logistic regression (2015)
  44. On distributionally robust extreme value analysis (2020)
  45. Robust growth-optimal portfolios (2016)
  46. Distributionally Robust Inventory Management with Advance Purchase Contracts (2022)
  47. A distributionally robust approach to fair classification (2020) — link
  48. Sequential domain adaptation by synthesizing distributionally robust experts (2021)
  49. Distributionally robust views on extremal queues (2022)
  50. Wasserstein Distributionally Robust Estimation in High Dimensions: Performance Analysis and Optimal Hyperparameter Tuning
  51. Certifying some distributional robustness with principled adversarial training (2017) — link
  52. On the convergence and robustness of adversarial training (2021) — link
  53. Theoretical analysis of adversarial learning: A minimax approach (2019)
  54. Principled learning method for W asserstein distributionally robust optimization with local perturbations (2020)
  55. Distributional uncertainty propagation via optimal transport (2023) — link
  56. Distributionally robust stochastic optimization with W asserstein distance (2023)
  57. Sensitivity analysis of W asserstein distributionally robust optimization problems (2021)
  58. Sensitivity of Multiperiod Optimization Problems with Respect to the Adapted W asserstein Distance (2023)
  59. A parametric approach to the estimation of convex risk functionals based on W asserstein distance (2022) — link
  60. Wasserstein distributionally robust optimization and variation regularization (2022)
  61. Distributionally robust portfolio maximization and marginal utility pricing in one period financial markets (2021)
  62. Wasserstein distributional sensitivity to model uncertainty in a dynamic context. DP hil T ransfer of S tatus T hesis. U niversity of O xford, J anuary 2023.
  63. Model uncertainty, recalibration, and the emergence of delta–vega hedging (2017)
  64. Hedging with small uncertainty aversion (2017)
  65. Sensitivity of robust optimization problems under drift and volatility uncertainty — → 2311.11248
  66. Duality formulas for robust pricing and hedging in discrete time (2017)
  67. Robust expected utility maximization with medial limits (2019)
  68. Viability and arbitrage under Knightian uncertainty (2021)
  69. Equilibria under Knightian price uncertainty (2019)
  70. A model-free version of the fundamental theorem of asset pricing and the super-replication theorem (2016)
  71. Quasi-sure Stochastic Analysis through Aggregation (2011) — link
  72. Martingale optimal transport duality (2021)
  73. Robust utility maximization in nondominated models with 2BSDE : the uncertain volatility model (2015)
  74. Arbitrage and duality in nondominated discrete-time models (2015) — link
  75. On the adversarial robustness of robust estimators (2020)
  76. The robust superreplication problem: a dynamic approach (2019)
  77. Multiple-priors optimal investment in discrete time for unbounded utility function (2018)
  78. Portfolio optimization with ambiguous correlation and stochastic volatilities (2016)
  79. Robust consumption-investment with return ambiguity: A dual approach with volatility ambiguity (2022)
  80. Portfolio diversification and model uncertainty: A robust dynamic mean-variance approach (2022)
  81. Robust risk aggregation with neural networks (2020)
  82. Risk measures based on weak optimal transport — → 2312.05973
  83. Bipolar Theorems for Sets of Non-negative Random Variables — → 2212.14259
  84. A theoretical framework for the pricing of contingent claims in the presence of model uncertainty (2006) — link
  85. G-expectation, G-Brownian motion and related stochastic calculus of It ^o type (2007)
  86. Robust utility maximization in discrete-time markets with friction (2018)
  87. Superreplication under volatility uncertainty for measurable claims (2013) — link
  88. Robust utility maximization with L 'e vy processes (2018)
  89. Duality theory for robust utility maximisation (2021)
  90. Model-free bounds for multi-asset options using option-implied information and their exact computation (2023)
  91. A deep learning approach to data-driven model-free pricing and to martingale optimal transport (2023)
  92. Martingale optimal transport and robust hedging in continuous time (2014)
  93. Robust control and model uncertainty (2001)
  94. Maxmin expected utility with non-unique prior (1989)
  95. Intertemporal asset pricing under Knightian uncertainty (2004)
  96. Ambiguity aversion, robustness, and the variational representation of preferences (2006)
  97. A smooth model of decision making under ambiguity (2005)
  98. Markov decision processes under model uncertainty (2023)
  99. Robust $ Q $-learning Algorithm for M arkov Decision Processes under W asserstein Uncertainty (2022) — link
  100. Distributionally Robust $ Q $-Learning (2022)
  101. Robust hedging with proportional transaction costs (2014)
  102. A stochastic subgradient method for distributionally robust non-convex and non-smooth learning (2022)
  103. Data-Driven Non-Parametric Robust Control under Dependence Uncertainty (2024)
  104. Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets (2023) — link
  105. A fully data-driven approach to minimizing C V a R for portfolio of assets via SGLD with discontinuous updating (2020) — link
  106. Non-asymptotic estimation of risk measures using stochastic gradient L angevin dynamics (2021) — link
  107. T he promises and pitfalls of stochastic gradient L angevin dynamics (2018)
  108. Bayesian learning via stochastic gradient L angevin dynamics (2011)
  109. P olygonal U nadjusted L angevin A lgorithms: C reating stable and efficient adaptive algorithms for neural networks (2021) — link
  110. A nalysis of L angevin M onte C arlo via convex optimization (2019)
  111. On the convergence of stochastic gradient MCMC algorithms with high-order integrators (2015)
  112. Preconditioned stochastic gradient L angevin dynamics for deep neural networks (2016)
  113. Stochastic gradient markov chain monte carlo (2021)
  114. Langevin algorithms for very deep Neural Networks with application to image classification (2023)
  115. Efficient B ayesian model selection in PARAFAC via stochastic thermodynamic integration (2018)
  116. Stochastic thermodynamic integration: efficient B ayesian model selection via stochastic gradient MCMC (2016)
  117. Uncertainty quantification for plant disease detection using B ayesian deep learning (2020)
  118. Low-precision stochastic gradient langevin dynamics (2022)
  119. Bayesian posterior sampling via stochastic gradient fisher scoring (2012)
  120. Bayesian Analysis of Exponential Random Graph Models Using Stochastic Gradient M arkov Chain Monte Carlo (2023)
  121. Variationally inferred sampling through a refined bound (2021)
  122. High-order stochastic gradient thermostats for B ayesian learning of deep models (2016)
  123. Adageo: Adaptive geometric learning for optimization and sampling (2018)
  124. Langevin dynamics based algorithm e-TH $\varepsilon $ O POULA for stochastic optimization problems with discontinuous stochastic gradient (2022) — link
  125. A hitting time analysis of stochastic gradient langevin dynamics (2017)
  126. On stationary-point hitting time and ergodicity of stochastic gradient L angevin dynamics (2020)
  127. Faster convergence of stochastic gradient langevin dynamics for non-log-concave sampling (2021)
  128. Time-independent generalization bounds for SGLD in non-convex settings (2021)
  129. Improved convergence rate of stochastic gradient L angevin dynamics with variance reduction and its application to optimization (2022)
  130. Uniform-in-Time W asserstein Stability Bounds for (Noisy) Stochastic Gradient Descent (2024)
  131. Langevin algorithms for markovian neural networks and deep stochastic control — → 2212.12018
  132. Improvements on scalable stochastic B ayesian inference methods for multivariate Hawkes process (2024)
  133. Poisoning attacks on data-driven utility learning in games (2018)
  134. Robust reinforcement learning via adversarial training with langevin dynamics (2020)
  135. Swing Contract Pricing: A Parametric Approach with Adjoint Automatic Differentiation and Neural Networks — → 2306.03822
  136. Granger causality for time-series anomaly detection (2012)
  137. Differential bayesian neural nets (2019) — link
  138. Deep learning and optimisation for quality of service modelling (2022)
  139. Stochastic gradient MCMC for state space models (2019)
  140. Spectral subsampling MCMC for stationary time series (2020)
  141. Latent dirichlet analysis of categorical survey responses (2022)
  142. Scaling up dynamic topic models (2016)
  143. Distributing the stochastic gradient sampler for large-scale LDA (2016)
  144. An adaptively weighted stochastic gradient MCMC algorithm for Monte Carlo simulation and global optimization (2022)
  145. A complete recipe for stochastic gradient MCMC (2015)
  146. Scalable MCMC for mixed membership stochastic blockmodels (2016)
  147. Characterizing membership privacy in stochastic gradient langevin dynamics (2020)
  148. Estimation and uncertainty quantification for the output from quantum simulators (2019)
  149. Quality of uncertainty quantification for B ayesian neural network inference (2019) — link
  150. Uncertainty quantified discovery of chemical reaction systems via B ayesian scientific machine learning (2023)
  151. Physics-informed information field theory for modeling physical systems with uncertainty quantification (2023)
  152. Differentially private bayesian neural networks on accuracy, privacy and reliability (2022)
  153. Data-driven risk-averse stochastic optimization with W asserstein metric (2018)
  154. Non-asymptotic convergence bounds for modified tamed unadjusted L angevin algorithm in non-convex setting (2022) — link
  155. Robust distortion risk measures (2023)
  156. Robust risk-aware reinforcement learning (2022)
  157. A robust learning approach for regression models based on distributionally robust optimization (2018)
  158. A stochastic smoothing framework for nonconvex-nonconcave min-sum-max problems with applications to Wasserstein distributionally robust optimization (2025) — link
  159. Numerical method for nonlinear Kolmogorov PDEs via sensitivity analysis (2024) — link
  160. Sensitivity of causal distributionally robust optimization (2024) — link
  161. First order Martingale model risk and semi-static hedging — → 2410.06906

6 of 169 cited works are in the corpus; resolved via arXiv source bundles, Semantic Scholar and OpenAlex. Corpus-wide: 2518 linked papers.