Buchumschlag

Efficient Certificates of Anti-Concentration Beyond Gaussians

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bakshi, Ainesh, Kothari, Pravesh, Rajendran, Goutham, Tulsiani, Madhur, Vijayaraghavan, Aravindan
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals
von: Guo, Anxin, et al.
Veröffentlicht: (2024)

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2026)

Agnostic Learning of General ReLU Activation Using Gradient Descent
von: Awasthi, Pranjal, et al.
Veröffentlicht: (2022)

Low-Degree Method Fails to Predict Robust Subspace Recovery
von: Jia, He, et al.
Veröffentlicht: (2026)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2023)

Compact Conformal Subgraphs
von: Gollapudi, Sreenivas, et al.
Veröffentlicht: (2026)

Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms
von: Kalavasis, Alkis, et al.
Veröffentlicht: (2026)

Overcomplete Tensor Decomposition via Koszul-Young Flattenings
von: Kothari, Pravesh K., et al.
Veröffentlicht: (2024)

Structure learning of Hamiltonians from real-time evolution
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2024)

Improved Certificates for Independence Number in Semirandom Hypergraphs
von: Kothari, Pravesh, et al.
Veröffentlicht: (2026)

Sample-Optimal Private Regression in Polynomial Time
von: Anderson, Prashanti, et al.
Veröffentlicht: (2025)

Learning quantum Hamiltonians at any temperature in polynomial time
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2023)

Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery
von: Gao, Chao, et al.
Veröffentlicht: (2025)

Computing High-dimensional Confidence Sets for Arbitrary Distributions
von: Gao, Chao, et al.
Veröffentlicht: (2025)

An Improved Classical Singular Value Transformation for Quantum Machine Learning
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2023)

Additive Approximation Schemes for Low-Dimensional Embeddings
von: Anderson, Prashanti, et al.
Veröffentlicht: (2025)

Entrywise Low-Rank Approximation and Matrix $p \rightarrow q$ Norms via Global Correlation Rounding
von: Anderson, Prashanti, et al.
Veröffentlicht: (2026)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
von: Kothari, Pravesh, et al.
Veröffentlicht: (2024)

Rapid mixing for high-temperature Gibbs states with arbitrary external fields
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2026)

New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
von: Bhaskara, Aditya, et al.
Veröffentlicht: (2024)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
von: Srivastava, Shashank, et al.
Veröffentlicht: (2025)

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
von: Kothari, Pravesh K., et al.
Veröffentlicht: (2025)

Sum-Of-Squares To Approximate Knapsack
von: Kothari, Pravesh K., et al.
Veröffentlicht: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

Sketching approximations and LP approximations for finite CSPs are related
von: Singer, Noah G., et al.
Veröffentlicht: (2025)

High-Temperature Gibbs States are Unentangled and Efficiently Preparable
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2024)

A Dobrushin condition for quantum Markov chains: Rapid mixing and conditional mutual information at high temperature
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2025)

Semirandom Planted Clique and the Restricted Isometry Property
von: Błasiok, Jarosław, et al.
Veröffentlicht: (2024)

Sparsifying Sums of Positive Semidefinite Matrices
von: Basu, Arpon, et al.
Veröffentlicht: (2025)

Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information
von: Gayen, Sutanu, et al.
Veröffentlicht: (2024)

SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
von: Diakonikolas, Ilias, et al.
Veröffentlicht: (2024)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
von: Axiotis, Kyriakos, et al.
Veröffentlicht: (2024)

Rounding Large Independent Sets on Expanders
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
von: Haah, Jeongwan, et al.
Veröffentlicht: (2021)

Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians
von: Lee, Jane H., et al.
Veröffentlicht: (2024)

Tight Bounds for Answering Adaptively Chosen Concentrated Queries
von: Rapoport, Emma, et al.
Veröffentlicht: (2025)

Linear Regression with Unknown Truncation Beyond Gaussian Features
von: Kouridakis, Alexandros, et al.
Veröffentlicht: (2026)

Interpreting the Curse of Dimensionality from Distance Concentration and Manifold Effect
von: Peng, Dehua, et al.
Veröffentlicht: (2023)

Reliable Learning of Halfspaces under Gaussian Marginals
von: Diakonikolas, Ilias, et al.
Veröffentlicht: (2024)

Learning general Gaussian mixtures with efficient score matching
von: Chen, Sitan, et al.
Veröffentlicht: (2024)