Imagen de Portada

Efficient Certificates of Anti-Concentration Beyond Gaussians

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bakshi, Ainesh, Kothari, Pravesh, Rajendran, Goutham, Tulsiani, Madhur, Vijayaraghavan, Aravindan
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms Machine Learning
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals
por: Guo, Anxin, et al.
Publicado: (2024)

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

Agnostic Learning of General ReLU Activation Using Gradient Descent
por: Awasthi, Pranjal, et al.
Publicado: (2022)

Low-Degree Method Fails to Predict Robust Subspace Recovery
por: Jia, He, et al.
Publicado: (2026)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
por: Bakshi, Ainesh, et al.
Publicado: (2023)

Compact Conformal Subgraphs
por: Gollapudi, Sreenivas, et al.
Publicado: (2026)

Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms
por: Kalavasis, Alkis, et al.
Publicado: (2026)

Overcomplete Tensor Decomposition via Koszul-Young Flattenings
por: Kothari, Pravesh K., et al.
Publicado: (2024)

Structure learning of Hamiltonians from real-time evolution
por: Bakshi, Ainesh, et al.
Publicado: (2024)

Improved Certificates for Independence Number in Semirandom Hypergraphs
por: Kothari, Pravesh, et al.
Publicado: (2026)

Sample-Optimal Private Regression in Polynomial Time
por: Anderson, Prashanti, et al.
Publicado: (2025)

Learning quantum Hamiltonians at any temperature in polynomial time
por: Bakshi, Ainesh, et al.
Publicado: (2023)

Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery
por: Gao, Chao, et al.
Publicado: (2025)

Computing High-dimensional Confidence Sets for Arbitrary Distributions
por: Gao, Chao, et al.
Publicado: (2025)

An Improved Classical Singular Value Transformation for Quantum Machine Learning
por: Bakshi, Ainesh, et al.
Publicado: (2023)

Additive Approximation Schemes for Low-Dimensional Embeddings
por: Anderson, Prashanti, et al.
Publicado: (2025)

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

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

Rapid mixing for high-temperature Gibbs states with arbitrary external fields
por: Bakshi, Ainesh, et al.
Publicado: (2026)

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

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
por: Srivastava, Shashank, et al.
Publicado: (2025)

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
por: Kothari, Pravesh K., et al.
Publicado: (2025)

Sum-Of-Squares To Approximate Knapsack
por: Kothari, Pravesh K., et al.
Publicado: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
por: Singer, Noah G., et al.
Publicado: (2026)

Sketching approximations and LP approximations for finite CSPs are related
por: Singer, Noah G., et al.
Publicado: (2025)

High-Temperature Gibbs States are Unentangled and Efficiently Preparable
por: Bakshi, Ainesh, et al.
Publicado: (2024)

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

Semirandom Planted Clique and the Restricted Isometry Property
por: Błasiok, Jarosław, et al.
Publicado: (2024)

Sparsifying Sums of Positive Semidefinite Matrices
por: Basu, Arpon, et al.
Publicado: (2025)

Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information
por: Gayen, Sutanu, et al.
Publicado: (2024)

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

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
por: Axiotis, Kyriakos, et al.
Publicado: (2024)

Rounding Large Independent Sets on Expanders
por: Bafna, Mitali, et al.
Publicado: (2024)

Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
por: Haah, Jeongwan, et al.
Publicado: (2021)

Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians
por: Lee, Jane H., et al.
Publicado: (2024)

Tight Bounds for Answering Adaptively Chosen Concentrated Queries
por: Rapoport, Emma, et al.
Publicado: (2025)

Linear Regression with Unknown Truncation Beyond Gaussian Features
por: Kouridakis, Alexandros, et al.
Publicado: (2026)

Interpreting the Curse of Dimensionality from Distance Concentration and Manifold Effect
por: Peng, Dehua, et al.
Publicado: (2023)

Reliable Learning of Halfspaces under Gaussian Marginals
por: Diakonikolas, Ilias, et al.
Publicado: (2024)

Learning general Gaussian mixtures with efficient score matching
por: Chen, Sitan, et al.
Publicado: (2024)