Efficient Stochastic Approximation of Minimax Excess Risk Optimization

• URL: http://arxiv.org/abs/2306.00026v2
• Date: Tue, 28 May 2024 14:31:16 GMT
• Title: Efficient Stochastic Approximation of Minimax Excess Risk Optimization
• Authors: Lijun Zhang, Haomin Bai, Wei-Wei Tu, Ping Yang, Yao Hu,
• Abstract summary: We develop efficient approximation approaches which directly target MERO. We demonstrate that the bias, caused by the estimation error of the minimal risk, is under-control. We also investigate a practical scenario where the quantity of samples drawn from each distribution may differ, and propose an approach that delivers distribution-dependent convergence rates.
• Score: 36.68685001551774
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While traditional distributionally robust optimization (DRO) aims to minimize the maximal risk over a set of distributions, Agarwal and Zhang (2022) recently proposed a variant that replaces risk with excess risk. Compared to DRO, the new formulation$\unicode{x2013}$minimax excess risk optimization (MERO) has the advantage of suppressing the effect of heterogeneous noise in different distributions. However, the choice of excess risk leads to a very challenging minimax optimization problem, and currently there exists only an inefficient algorithm for empirical MERO. In this paper, we develop efficient stochastic approximation approaches which directly target MERO. Specifically, we leverage techniques from stochastic convex optimization to estimate the minimal risk of every distribution, and solve MERO as a stochastic convex-concave optimization (SCCO) problem with biased gradients. The presence of bias makes existing theoretical guarantees of SCCO inapplicable, and fortunately, we demonstrate that the bias, caused by the estimation error of the minimal risk, is under-control. Thus, MERO can still be optimized with a nearly optimal convergence rate. Moreover, we investigate a practical scenario where the quantity of samples drawn from each distribution may differ, and propose a stochastic approach that delivers distribution-dependent convergence rates.

Related papers

• Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization [3.802030070947573]
  We propose a zeroth-order mirror descent (ZO-SMD) algorithm available for both smooth and non-smooth MERO. The proposed algorithm is proved to converge at optimal convergence rates of $mathcalOleft (1/sqrttright)$ on the estimate of $R_i*$ and $mathcalOleft (1/sqrttright)$ on the optimization error of both smooth and non-smooth MERO.
  arXiv  Detail & Related papers  (2024-08-22T08:35:41Z)
• Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
  We consider the problem of quantifying uncertainty over expected cumulative rewards in model-based reinforcement learning. We propose a new uncertainty Bellman equation (UBE) whose solution converges to the true posterior variance over values. We introduce a general-purpose policy optimization algorithm, Q-Uncertainty Soft Actor-Critic (QU-SAC) that can be applied for either risk-seeking or risk-averse policy optimization.
  arXiv  Detail & Related papers  (2023-12-07T15:55:58Z)
• Pitfall of Optimism: Distributional Reinforcement Learning by Randomizing Risk Criterion [9.35556128467037]
  We present a novel distributional reinforcement learning algorithm that selects actions by randomizing risk criterion to avoid one-sided tendency on risk. Our theoretical results support that the proposed method does not fall into biased exploration and is guaranteed to converge to an optimal return.
  arXiv  Detail & Related papers  (2023-10-25T10:53:04Z)
• Domain Generalization without Excess Empirical Risk [83.26052467843725]
  A common approach is designing a data-driven surrogate penalty to capture generalization and minimize the empirical risk jointly with the penalty. We argue that a significant failure mode of this recipe is an excess risk due to an erroneous penalty or hardness in joint optimization. We present an approach that eliminates this problem. Instead of jointly minimizing empirical risk with the penalty, we minimize the penalty under the constraint of optimality of the empirical risk.
  arXiv  Detail & Related papers  (2023-08-30T08:46:46Z)
• Out-of-Distribution Optimality of Invariant Risk Minimization [20.389816785165333]
  Invariant Risk Minimization (IRM) is considered to be a promising approach to minimize the o.o.d. risk. This paper rigorously proves that a solution to the bi-level optimization problem minimizes the o.o.d. risk under certain conditions.
  arXiv  Detail & Related papers  (2023-07-22T03:31:15Z)
• On the Variance, Admissibility, and Stability of Empirical Risk Minimization [80.26309576810844]
  Empirical Risk Minimization (ERM) with squared loss may attain minimax suboptimal error rates. We show that under mild assumptions, the suboptimality of ERM must be due to large bias rather than variance. We also show that our estimates imply stability of ERM, complementing the main result of Caponnetto and Rakhlin (2006) for non-Donsker classes.
  arXiv  Detail & Related papers  (2023-05-29T15:25:48Z)
• Distributed Distributionally Robust Optimization with Non-Convex Objectives [24.64654924173679]
  Asynchronous distributed algorithm named Asynchronous Single-looP alternatIve gRadient projEction is proposed. New uncertainty set, i.e., constrained D-norm uncertainty set, is developed to leverage the prior distribution and flexibly control the degree of robustness. empirical studies on real-world datasets demonstrate that the proposed method can not only achieve fast convergence, but also remain robust against data as well as malicious attacks.
  arXiv  Detail & Related papers  (2022-10-14T07:39:13Z)
• Risk-averse Heteroscedastic Bayesian Optimization [45.12421486836736]
  We propose a novel risk-averse heteroscedastic Bayesian optimization algorithm (RAHBO) RAHBO aims to identify a solution with high return and low noise variance, while learning the noise distribution on the fly. We provide a robust rule to report the final decision point for applications where only a single solution must be identified.
  arXiv  Detail & Related papers  (2021-11-05T17:38:34Z)
• On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
  In this paper, we demonstrate the power of a widely used estimator based on moving average (SEMA) problems. For all these-the-art results, we also present the results for all these-the-art problems.
  arXiv  Detail & Related papers  (2021-04-30T08:50:24Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  We argue for the use of neural generative models to characterize the worst-case distribution. This approach poses a number of implementation and optimization challenges. We find that the proposed approach yields models that are more robust than comparable baselines.
  arXiv  Detail & Related papers  (2021-03-18T14:26:26Z)

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.