A Full Characterization of Excess Risk via Empirical Risk Landscape

• URL: http://arxiv.org/abs/2012.02456v2
• Date: Fri, 29 Jan 2021 11:35:16 GMT
• Title: A Full Characterization of Excess Risk via Empirical Risk Landscape
• Authors: Mingyang Yi, Ruoyu Wang, Zhi-Ming Ma
• Abstract summary: In this paper, we provide a unified analysis of the risk of the model trained by a proper algorithm with both smooth convex and non- loss functions.
• Score: 8.797852602680445
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we provide a unified analysis of the excess risk of the model trained by a proper algorithm with both smooth convex and non-convex loss functions. In contrast to the existing bounds in the literature that depends on iteration steps, our bounds to the excess risk do not diverge with the number of iterations. This underscores that, at least for smooth loss functions, the excess risk can be guaranteed after training. To get the bounds to excess risk, we develop a technique based on algorithmic stability and non-asymptotic characterization of the empirical risk landscape. The model obtained by a proper algorithm is proved to generalize with this technique. Specifically, for non-convex loss, the conclusion is obtained via the technique and analyzing the stability of a constructed auxiliary algorithm. Combining this with some properties of the empirical risk landscape, we derive converged upper bounds to the excess risk in both convex and non-convex regime with the help of some classical optimization results.

Related papers

• LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
  An adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown to the learner. We present a robust online rounds optimization framework, where an adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown.
  arXiv  Detail & Related papers  (2024-08-12T17:08:31Z)
• OPSurv: Orthogonal Polynomials Quadrature Algorithm for Survival Analysis [19.65859820376036]
  This paper introduces the Orthogonal Polynomials Quadrature Algorithm for Survival Analysis (OPSurv) OPSurv provides time-continuous functional outputs for both single and competing risks scenarios in survival analysis.
  arXiv  Detail & Related papers  (2024-02-02T23:26:09Z)
• 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)
• Risk-aware linear bandits with convex loss [0.0]
  We propose an optimistic UCB algorithm to learn optimal risk-aware actions, with regret guarantees similar to those of generalized linear bandits. This approach requires solving a convex problem at each round of the algorithm, which we can relax by allowing only approximated solution obtained by online gradient descent.
  arXiv  Detail & Related papers  (2022-09-15T09:09:53Z)
• Mitigating multiple descents: A model-agnostic framework for risk monotonization [84.6382406922369]
  We develop a general framework for risk monotonization based on cross-validation. We propose two data-driven methodologies, namely zero- and one-step, that are akin to bagging and boosting.
  arXiv  Detail & Related papers  (2022-05-25T17:41:40Z)
• Efficient Risk-Averse Reinforcement Learning [79.61412643761034]
  In risk-averse reinforcement learning (RL), the goal is to optimize some risk measure of the returns. We prove that under certain conditions this inevitably leads to a local-optimum barrier, and propose a soft risk mechanism to bypass it. We demonstrate improved risk aversion in maze navigation, autonomous driving, and resource allocation benchmarks.
  arXiv  Detail & Related papers  (2022-05-10T19:40:52Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  This paper unifies the analysis of risk-averse Thompson sampling algorithms for the multi-armed bandit problem. Using the contraction principle in the theory of large deviations, we prove novel concentration bounds for continuous risk functionals. We show that a wide class of risk functionals as well as "nice" functions of them satisfy the continuity condition.
  arXiv  Detail & Related papers  (2021-08-25T17:09:01Z)
• Risk-Constrained Thompson Sampling for CVaR Bandits [82.47796318548306]
  We consider a popular risk measure in quantitative finance known as the Conditional Value at Risk (CVaR) We explore the performance of a Thompson Sampling-based algorithm CVaR-TS under this risk measure.
  arXiv  Detail & Related papers  (2020-11-16T15:53:22Z)
• Entropic Risk Constrained Soft-Robust Policy Optimization [12.362670630646805]
  It is important in high-stakes domains to quantify and manage risk induced by model uncertainties. We propose an entropic risk constrained policy gradient and actor-critic algorithms that are risk-averse to the model uncertainty.
  arXiv  Detail & Related papers  (2020-06-20T23:48:28Z)
• A Stochastic Subgradient Method for Distributionally Robust Non-Convex Learning [2.007262412327553]
  robustness is with respect to uncertainty in the underlying data distribution. We show that our technique converges to satisfying perturbationity conditions. We also illustrate the performance of our algorithm on real datasets.
  arXiv  Detail & Related papers  (2020-06-08T18:52:40Z)

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.