Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds

• URL: http://arxiv.org/abs/2310.20102v1
• Date: Tue, 31 Oct 2023 00:44:20 GMT
• Title: Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds
• Abstract summary: We present new information-theoretic generalization guarantees through the a novel construction of the "neighboring-hypothesis" matrix. Our approach yields sharper bounds that improve upon previous information-theoretic bounds in various learning scenarios.
• Score: 41.25859594345433
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present new information-theoretic generalization guarantees through the a novel construction of the "neighboring-hypothesis" matrix and a new family of stability notions termed sample-conditioned hypothesis (SCH) stability. Our approach yields sharper bounds that improve upon previous information-theoretic bounds in various learning scenarios. Notably, these bounds address the limitations of existing information-theoretic bounds in the context of stochastic convex optimization (SCO) problems, as explored in the recent work by Haghifam et al. (2023).

Related papers

• Statistical inverse learning problems with random observations [0.0]
  We provide an overview of recent progress in statistical inverse problems with random experimental design, covering both linear and nonlinear inverse problems. We discuss recent results in spectral regularization methods and regularization by projection, exploring both approaches within the context of Hilbert scales. We demonstrate the application of these concepts to nonlinear inverse problems in pharmacokinetic/pharmacodynamic (PK/PD) models, where the task is to predict changes in drug concentrations in patients.
  arXiv  Detail & Related papers  (2023-12-23T20:34:49Z)
• Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments [1.90365714903665]
  We present a convergence theorem for iterations, and iterate in particular, Q-learnings under a general, possibly non-Markovian, environment. We discuss the implications and applications of this theorem to a variety of control problems with non-Markovian environments.
  arXiv  Detail & Related papers  (2023-10-31T19:53:16Z)
• On the Local Quadratic Stability of T-S Fuzzy Systems in the Vicinity of the Origin [7.191780076353627]
  The main goal of this paper is to introduce new local stability conditions for continuous-time Takagi-Sugeno (T-S) fuzzy systems. These stability conditions are based on linear matrix inequalities (LMIs) in combination with quadratic Lyapunov functions.
  arXiv  Detail & Related papers  (2023-09-13T09:43:55Z)
• Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization [48.12845778927164]
  We consider the prospect of establishing minimax rates for gradient descent in the setting of convex optimization. We consider a common tactic employed in studying gradient methods, whereby the final iterate is corrupted by Gaussian noise, producing a noisy "surrogate" algorithm. Our results suggest that new ideas are required to analyze gradient descent using information-theoretic techniques.
  arXiv  Detail & Related papers  (2022-12-27T17:16:48Z)
• A Local Convergence Theory for the Stochastic Gradient Descent Method in Non-Convex Optimization With Non-isolated Local Minima [0.0]
  Non-isolated minima presents a unique challenge that has remained under-explored. In this paper, we study the local convergence of the gradient descent method to non-isolated global minima.
  arXiv  Detail & Related papers  (2022-03-21T13:33:37Z)
• Robust and Provable Guarantees for Sparse Random Embeddings [72.24615341588846]
  We improve upon the guarantees for sparse random embeddings provided by Freksen at al. (NIPS'18) and Jagadeesan (NIPS'18) We show that (a) our bounds are explicit as opposed to the guarantees provided previously, and (b) our bounds are guaranteed to be sharper by practically significant constants. We empirically demonstrate that our bounds significantly outperform prior works on a wide range of real-world datasets.
  arXiv  Detail & Related papers  (2022-02-22T11:15:59Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
  We introduce a new stability measure called on-average model stability, for which we develop novel bounds controlled by the risks of SGD iterates. This yields generalization bounds depending on the behavior of the best model, and leads to the first-ever-known fast bounds in the low-noise setting. To our best knowledge, this gives the firstever-known stability and generalization for SGD with even non-differentiable loss functions.
  arXiv  Detail & Related papers  (2020-06-15T06:30:19Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)

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.