Sharp implications of AGSPs for degenerate ground spaces

• URL: http://arxiv.org/abs/2003.08406v1
• Date: Wed, 18 Mar 2020 18:00:20 GMT
• Title: Sharp implications of AGSPs for degenerate ground spaces
• Abstract summary: We generalize the off-the-rack' AGSP$Rightarrow$entanglement bound implication of [Arad, Landau, and Vazirani '12] from unique ground states to degenerate ground spaces. Our condition $RDeltale1/2$ on a $(Delta,R)$-AGSP matches the non-degenerate case, whereas existing tools in the literature of spin chains would only be adequate to prove a less natural implication.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We generalize the `off-the-rack' AGSP$\Rightarrow$entanglement bound implication of [Arad, Landau, and Vazirani '12] from unique ground states to degenerate ground spaces. Our condition $R\Delta\le1/2$ on a $(\Delta,R)$-AGSP matches the non-degenerate case, whereas existing tools in the literature of spin chains would only be adequate to prove a less natural implication which assumes $R^{\text{Const}}\Delta\le c$. To show that $R\Delta\le1/2$ still suffices in the degenerate case we prove an optimal error reduction bound which improves on the literature by a factor $\delta\mu$ where $\delta=1-\mu$ is the viability. The generalized off-the-rack bound implies the generalization of a recent 2D subvolume law of [Anshu, Arad, and Gosset '19] from the non-degenerate case to the sub-exponentially degenerate case.

Related papers

• Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails [47.36630149538994]
  For isotropic sub-Gaussian measurements, the benchmark sample size is $1+w(A)2$, where $w(A)$ is the Gaussian width of the normalized descent cone.<n>We give an explicit and systematic negative answer to the general question as formulated there: the proposed law fails in its full dimension-free, arbitrary-set form.<n>Under isotropy, a distribution-free fallback governed by affine dimension times squared enclosing radius is sharp on this family.
  arXiv  Detail & Related papers  (2026-09-03T08:05:05Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Dimension-Independent Convergence of Underdamped Langevin Monte Carlo in KL Divergence [50.719298242863744]
  Underdamped Langevin dynamics (ULD) is a widely-used sampler for Gibbs distributions $propto e-V$.<n>We prove the first dimension-free KL divergence bounds for discretized ULD.
  arXiv  Detail & Related papers  (2026-03-02T22:14:38Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Harmful Overfitting in Sobolev Spaces [49.47221415754556]
  We study the generalization behavior of functions in Sobolev spaces $Wk, p(mathbbRd)$ that perfectly fit a noisy training data set.<n>We show that approximately norm-minimizing interpolators, which are canonical solutions selected by smoothness bias, exhibit harmful overfitting.<n>Our proof uses a geometric argument which identifies harmful neighborhoods of the training data using Sobolev inequalities.
  arXiv  Detail & Related papers  (2026-01-31T17:40:56Z)
• Super-fast rates of convergence for Neural Networks Classifiers under the Hard Margin Condition [9.993044620455338]
  We show that DNNs which minimize the empirical risk with square loss surrogate and $ell_p$ penalty can achieve finite-sample excess risk of order $mathcalOleft(n-alpharight)$ for arbitrarily large $alpha>0$ under the hard-margin condition.<n>The proof relies on a novel decomposition of the excess risk which might be of independent interest.
  arXiv  Detail & Related papers  (2025-05-13T06:26:04Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Renormalization group for Anderson localization on high-dimensional lattices [0.0]
  We show how in the delocalized region, including the transition point, the $beta$-function for the fractal dimension $D_1$ evolves smoothly. We put forward a conjecture about a lower bound for the fractal dimension.
  arXiv  Detail & Related papers  (2024-03-04T12:16:35Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  We study the generalized low-rank matrix bandit problem, proposed in citelu2021low under the Generalized Linear Model (GLM) framework. To overcome the computational infeasibility and theoretical restrain of existing algorithms, we first propose the G-ESTT framework. We show that G-ESTT can achieve the $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret while G-ESTS can achineve the $tildeO
  arXiv  Detail & Related papers  (2024-01-14T14:14:19Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits [76.2262680277608]
  We study linear contextual bandits in the misspecified setting, where the expected reward function can be approximated by a linear function class. We show that our algorithm enjoys the same gap-dependent regret bound $tilde O (d2/Delta)$ as in the well-specified setting up to logarithmic factors.
  arXiv  Detail & Related papers  (2023-03-16T15:24:29Z)
• Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA [17.75853665586128]
  This paper is concerned with estimating the column subspace of a low-rank matrix $boldsymbolXstar in mathbbRn_1times n$ from contaminated data. How to obtain optimal statistical accuracy while accommodating the widest range of signal-to-noise ratios (SNRs) becomes challenging.
  arXiv  Detail & Related papers  (2023-03-10T20:22:18Z)
• Variance-aware robust reinforcement learning with linear function approximation with heavy-tailed rewards [6.932056534450556]
  We present two algorithms, AdaOFUL and VARA, for online sequential decision-making in the presence of heavy-tailed rewards. AdaOFUL achieves a state-of-the-art regret bound of $widetildemathcalObig. VarA achieves a tighter variance-aware regret bound of $widetildemathcalO(dsqrtHmathcalG*K)$.
  arXiv  Detail & Related papers  (2023-03-09T22:16:28Z)
• Delta-Closure Structure for Studying Data Distribution [21.70710923045654]
  We introduce $Delta$-closedness, a generalization of the closure operator, where $Delta$ measures how a closed set differs from its upper neighbors in the partial order induced by closure. A $Delta$-class of equivalence includes minimum and maximum elements and allows us to characterize the distribution underlying the data. A $Delta$-class of equivalence with a high level demonstrates correlations among many attributes, which are supported by more observations when $Delta$ is large.
  arXiv  Detail & Related papers  (2022-10-13T11:50:27Z)
• Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits [8.508198765617198]
  We propose a novel contextual bandit algorithm for generalized linear rewards with an $tildeO(sqrtkappa-1 phi T)$ regret over $T$ rounds. We also provide an $O(kappa-1 phi log (NT) log T)$ regret bound for $N$ arms under a probabilistic margin condition.
  arXiv  Detail & Related papers  (2022-09-15T00:20:38Z)
• Annihilating Entanglement Between Cones [77.34726150561087]
  We show that Lorentz cones are the only cones with a symmetric base for which a certain stronger version of the resilience property is satisfied. Our proof exploits the symmetries of the Lorentz cones and applies two constructions resembling protocols for entanglement distillation.
  arXiv  Detail & Related papers  (2021-10-22T15:02:39Z)
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance [14.06947898164194]
  Heavy tails emerge in gradient descent (SGD) in various scenarios. We provide convergence guarantees for SGD under a state-dependent and heavy-tailed noise with a potentially infinite variance. Our results indicate that even under heavy-tailed noise with infinite variance, SGD can converge to the global optimum.
  arXiv  Detail & Related papers  (2021-02-20T13:45:11Z)
• Scattering data and bound states of a squeezed double-layer structure [77.34726150561087]
  A structure composed of two parallel homogeneous layers is studied in the limit as their widths $l_j$ and $l_j$, and the distance between them $r$ shrinks to zero simultaneously. The existence of non-trivial bound states is proven in the squeezing limit, including the particular example of the squeezed potential in the form of the derivative of Dirac's delta function. The scenario how a single bound state survives in the squeezed system from a finite number of bound states in the finite system is described in detail.
  arXiv  Detail & Related papers  (2020-11-23T14:40:27Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

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.