Smoothed $f$-Divergence Distributionally Robust Optimization

• URL: http://arxiv.org/abs/2306.14041v2
• Date: Thu, 12 Oct 2023 14:16:15 GMT
• Title: Smoothed $f$-Divergence Distributionally Robust Optimization
• Authors: Zhenyuan Liu and Bart P. G. Van Parys and Henry Lam
• Abstract summary: We argue that a special type of distributionallly robust optimization (DRO) formulation offers theoretical advantages. DRO uses an ambiguity set based on a Kullback Leibler (KL) divergence smoothed by the Wasserstein or L'evy-Prokhorov (LP) distance.
• Score: 5.50764401597583
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In data-driven optimization, sample average approximation (SAA) is known to suffer from the so-called optimizer's curse that causes an over-optimistic evaluation of the solution performance. We argue that a special type of distributionallly robust optimization (DRO) formulation offers theoretical advantages in correcting for this optimizer's curse compared to simple ``margin'' adjustments to SAA and other DRO approaches: It attains a statistical bound on the out-of-sample performance, for a wide class of objective functions and distributions, that is nearly tightest in terms of exponential decay rate. This DRO uses an ambiguity set based on a Kullback Leibler (KL) divergence smoothed by the Wasserstein or L\'evy-Prokhorov (LP) distance via a suitable distance optimization. Computationally, we also show that such a DRO, and its generalized versions using smoothed $f$-divergence, are not harder than DRO problems based on $f$-divergence or Wasserstein distances, rendering our DRO formulations both statistically optimal and computationally viable.

Related papers

• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  We identify the source of misalignment as a form of distributional shift and uncertainty in learning human preferences. To mitigate overoptimization, we first propose a theoretical algorithm that chooses the best policy for an adversarially chosen reward model. Using the equivalence between reward models and the corresponding optimal policy, the algorithm features a simple objective that combines a preference optimization loss and a supervised learning loss.
  arXiv  Detail & Related papers  (2024-05-26T05:38:50Z)
• A Primal-Dual Algorithm for Faster Distributionally Robust Optimization [12.311794669976047]
  We present Drago, a primal-dual algorithm that achieves a state-of-the-art linear convergence rate on strongly convex-strongly concave DRO problems. We support our theoretical results with numerical benchmarks in classification and regression.
  arXiv  Detail & Related papers  (2024-03-16T02:06:14Z)
• DRAUC: An Instance-wise Distributionally Robust AUC Optimization Framework [133.26230331320963]
  Area Under the ROC Curve (AUC) is a widely employed metric in long-tailed classification scenarios. We propose an instance-wise surrogate loss of Distributionally Robust AUC (DRAUC) and build our optimization framework on top of it.
  arXiv  Detail & Related papers  (2023-11-06T12:15:57Z)
• Hedging Complexity in Generalization via a Parametric Distributionally Robust Optimization Framework [18.6306170209029]
  Empirical risk minimization (ERM) and distributionally robust optimization (DRO) are popular approaches for solving optimization problems. We propose a simple approach in which the distribution of random perturbations is approximated using a parametric family of distributions. We show that this new source of error can be controlled by suitable DRO formulations.
  arXiv  Detail & Related papers  (2022-12-03T03:26:34Z)
• Scalable Distributional Robustness in a Class of Non Convex Optimization with Guarantees [7.541571634887807]
  Distributionally robust optimization (DRO) has shown robustness in learning as well as sample based problems. We propose a mixed-integer clustering program (MISOCP) which does not scale enough to solve problems with real worldsets.
  arXiv  Detail & Related papers  (2022-05-31T09:07:01Z)
• When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guarantee [51.527543027813344]
  We propose systematic and efficient gradient-based methods for both one-way and two-way partial AUC (pAUC) For both one-way and two-way pAUC, we propose two algorithms and prove their convergence for optimizing their two formulations, respectively.
  arXiv  Detail & Related papers  (2022-03-01T01:59:53Z)
• Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis [16.499651513178012]
  Distributionally robust optimization (DRO) is a widely-used approach to learn models that are robust against distribution shift. We provide non-asymptotic convergence guarantees even though the objective function is possibly prominent nonsmooth- and has normalized gradient descent.
  arXiv  Detail & Related papers  (2021-10-24T14:56:38Z)
• Sinkhorn Distributionally Robust Optimization [15.194516549163245]
  We derive convex programming dual reformulation for general nominal distributions, transport costs, and loss functions. Compared with Wasserstein DRO, our proposed approach offers enhanced computational tractability for a broader class of loss functions.
  arXiv  Detail & Related papers  (2021-09-24T12:40:48Z)
• Variational Refinement for Importance Sampling Using the Forward Kullback-Leibler Divergence [77.06203118175335]
  Variational Inference (VI) is a popular alternative to exact sampling in Bayesian inference. Importance sampling (IS) is often used to fine-tune and de-bias the estimates of approximate Bayesian inference procedures. We propose a novel combination of optimization and sampling techniques for approximate Bayesian inference.
  arXiv  Detail & Related papers  (2021-06-30T11:00:24Z)
• Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence [66.83161885378192]
  Area under ROC (AUROC) and precision-recall curves (AUPRC) are common metrics for evaluating classification performance for imbalanced problems. We propose a technical method to optimize AUPRC for deep learning.
  arXiv  Detail & Related papers  (2021-04-18T06:22:21Z)
• Distributionally Robust Bayesian Optimization [121.71766171427433]
  We present a novel distributionally robust Bayesian optimization algorithm (DRBO) for zeroth-order, noisy optimization. Our algorithm provably obtains sub-linear robust regret in various settings. We demonstrate the robust performance of our method on both synthetic and real-world benchmarks.
  arXiv  Detail & Related papers  (2020-02-20T22:04:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.