Dimension-free uniform concentration bound for logistic regression

• URL: http://arxiv.org/abs/2405.18055v5
• Date: Mon, 14 Oct 2024 16:40:26 GMT
• Title: Dimension-free uniform concentration bound for logistic regression
• Authors: Shogo Nakakita,
• Abstract summary: We provide a novel-free uniform concentration bound for the dimension risk function of constrained logistic regression. Our bound yields a milder sufficient condition for a uniform law of large numbers than conditions derived by the Rademacher complexity argument and McDiarmid's inequality.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide a novel dimension-free uniform concentration bound for the empirical risk function of constrained logistic regression. Our bound yields a milder sufficient condition for a uniform law of large numbers than conditions derived by the Rademacher complexity argument and McDiarmid's inequality. The derivation is based on the PAC-Bayes approach with second-order expansion and Rademacher-complexity-based bounds for the residual term of the expansion.

Related papers

• Wasserstein Distributionally Robust Nash Equilibrium Seeking with Heterogeneous Data: A Lagrangian Approach [10.82417971001311]
  We study a class of distributionally robust games where agents are allowed to heterogeneously choose their risk aversion with respect to distributional shifts of the uncertainty.<n>We then formulate the distributionally robust Nash equilibrium problem and show that under certain assumptions it is equivalent to a finite-dimensional variational inequality problem with a strongly monotone mapping.
  arXiv  Detail & Related papers  (2025-11-18T01:56:33Z)
• A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm [3.7498611358320733]
  We study stability of unboundeds and convergence of Sinkhorn's algorithm in the framework of entropic optimal transport. New applications include subspace elastic costs, weakly log-concave marginals, marginals with light tails.
  arXiv  Detail & Related papers  (2024-12-12T12:45:31Z)
• Tamed Langevin sampling under weaker conditions [27.872857402255775]
  We investigate the problem of sampling from distributions that are not log-concave and are only weakly dissipative. We introduce a taming scheme which is tailored to the growth and decay properties of the target distribution. We provide explicit non-asymptotic guarantees for the proposed sampler in terms of the Kullback-Leibler divergence, total variation, and Wasserstein distance to the target distribution.
  arXiv  Detail & Related papers  (2024-05-27T23:00:40Z)
• Randomized Midpoint Method for Log-Concave Sampling under Constraints [5.548787731232499]
  We study the problem of sampling from log-concave distributions supported on convex, compact sets.<n>We propose a unified proximal framework for handling constraints via a broad class of projection operators.
  arXiv  Detail & Related papers  (2024-05-24T09:24:21Z)
• Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems [78.96969465641024]
  We extend mean-field Langevin dynamics to minimax optimization over probability distributions for the first time with symmetric and provably convergent updates. We also study time and particle discretization regimes and prove a new uniform-in-time propagation of chaos result.
  arXiv  Detail & Related papers  (2023-12-02T13:01:29Z)
• Taming under isoperimetry [0.0]
  In this article we propose a Langevin-based scheme calledmathbfsTULA$ to sample from distributions with growing log. We derive non-asymientKL and consequently consequently satisfy a Log-Sobolev inequality.
  arXiv  Detail & Related papers  (2023-11-15T14:44:16Z)
• An Improved Uniform Convergence Bound with Fat-Shattering Dimension [4.5349436061325425]
  The state-of-the-art upper bounds feature a multiplicative squared logarithmic factor on the sample complexity, leaving an open gap with the existing lower bound. We provide an improved uniform convergence bound that closes this gap.
  arXiv  Detail & Related papers  (2023-07-13T09:20:57Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• On the Importance of Gradient Norm in PAC-Bayesian Bounds [92.82627080794491]
  We propose a new generalization bound that exploits the contractivity of the log-Sobolev inequalities. We empirically analyze the effect of this new loss-gradient norm term on different neural architectures.
  arXiv  Detail & Related papers  (2022-10-12T12:49:20Z)
• Role of boundary conditions in the full counting statistics of topological defects after crossing a continuous phase transition [62.997667081978825]
  We analyze the role of boundary conditions in the statistics of topological defects. We show that for fast and moderate quenches, the cumulants of the kink number distribution present a universal scaling with the quench rate.
  arXiv  Detail & Related papers  (2022-07-08T09:55:05Z)
• Nearest neighbor empirical processes [7.034466417392574]
  An empirical measure based on the responses from the nearest neighbors to a given point $x$ is introduced and studied as a central statistical quantity. A uniform non-asymptotic bound is established under a well-known condition, often referred to as Vapnik-Chervonenkis, on the uniform entropy numbers. This suggests the possibility of using standard formulas to estimate the variance by using only the nearest neighbors instead of the full data.
  arXiv  Detail & Related papers  (2021-10-27T08:15:20Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• R\'enyi divergence inequalities via interpolation, with applications to generalised entropic uncertainty relations [91.3755431537592]
  We investigate quantum R'enyi entropic quantities, specifically those derived from'sandwiched' divergence. We present R'enyi mutual information decomposition rules, a new approach to the R'enyi conditional entropy tripartite chain rules and a more general bipartite comparison.
  arXiv  Detail & Related papers  (2021-06-19T04:06:23Z)
• Statistical optimality conditions for compressive ensembles [7.766921168069532]
  We present a framework for the theoretical analysis of ensembles of low-complexity empirical risk minimisers trained on independent random compressions of high-dimensional data. We introduce a general distribution-dependent upper-bound on the excess risk, framed in terms of a natural notion of compressibility. We then instantiate this general bound to classification and regression tasks, considering Johnson-Lindenstrauss mappings as the compression scheme.
  arXiv  Detail & Related papers  (2021-06-02T11:52:31Z)

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.