Cover Image

Tight Bounds for Learning Polyhedra with a Margin

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Patel, Shyamal, Vempala, Santosh
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Geometry of Efficient Nonconvex Sampling
by: Vempala, Santosh S., et al.
Published: (2026)

Sampling and Integration of Logconcave Functions by Algorithmic Diffusion
by: Kook, Yunbum, et al.
Published: (2024)

Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling
by: Kook, Yunbum, et al.
Published: (2023)

Faster logconcave sampling from a cold start in high dimension
by: Kook, Yunbum, et al.
Published: (2025)

In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies
by: Kook, Yunbum, et al.
Published: (2024)

Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
by: Klivans, Adam R., et al.
Published: (2026)

Zeroth-order Logconcave Sampling
by: Kook, Yunbum, et al.
Published: (2025)

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

A Unified View of Graph Regularity via Matrix Decompositions
by: Bodwin, Greg, et al.
Published: (2019)

Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap
by: Karpov, Nikolai, et al.
Published: (2025)

A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
by: Fahrbach, Matthew, et al.
Published: (2025)

Replicable Learning of Large-Margin Halfspaces
by: Kalavasis, Alkis, et al.
Published: (2024)

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

The Localization Method for High-Dimensional Inequalities
by: Kook, Yunbum, et al.
Published: (2025)

Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
by: Nadimpalli, Shivam, et al.
Published: (2024)

Almost Tight Error Bounds on Differentially Private Continual Counting
by: Henzinger, Monika, et al.
Published: (2022)

Improved Margin Generalization Bounds for Voting Classifiers
by: Høgsgaard, Mikael Møller, et al.
Published: (2025)

Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
by: Diakonikolas, Ilias, et al.
Published: (2025)

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

Sampling Sphere Packings with Continuum Glauber Dynamics
by: Kuchukova, Aiya, et al.
Published: (2026)

Tight Differentially Private PCA via Matrix Coherence
by: d'Orsi, Tommaso, et al.
Published: (2025)

A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
by: Chen, Xi, et al.
Published: (2025)

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
by: Chen, Xi, et al.
Published: (2024)

Finite Sample Bounds for Learning with Score Matching
by: Smedira, Devin, et al.
Published: (2026)

Lower Bounds for the Algorithmic Complexity of Learned Indexes
by: Croquevielle, Luis Alberto, et al.
Published: (2026)

Statistical Query Lower Bounds for Smoothed Agnostic Learning
by: Diakonikolas, Ilias, et al.
Published: (2026)

The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
by: Ahmadian, Sara, et al.
Published: (2025)

A Simple Algorithm for Dynamic Carpooling with Recourse
by: Efron, Yuval, et al.
Published: (2024)

Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
by: Ye, Zichun, et al.
Published: (2025)

Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
by: Klivans, Adam R., et al.
Published: (2024)

DNF Learning via Locally Mixing Random Walks
by: Alman, Josh, et al.
Published: (2025)

Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models
by: Diakonikolas, Ilias, et al.
Published: (2025)

Mistake-Bounded Language Generation
by: Kleinberg, Jon, et al.
Published: (2026)

Better Bounds for the Distributed Experts Problem
by: Woodruff, David P., et al.
Published: (2026)

Improved Bounds for Online Facility Location with Predictions
by: Fotakis, Dimitris, et al.
Published: (2021)

Sharper Bounds for Chebyshev Moment Matching, with Applications
by: Musco, Cameron, et al.
Published: (2024)

Sharper Bounds for $\ell_p$ Sensitivity Sampling
by: Woodruff, David P., et al.
Published: (2023)

A Note On Deterministic Submodular Maximization With Bounded Curvature
by: Li, Wenxin
Published: (2024)

Faster exact learning of k-term DNFs with membership and equivalence queries
by: Alman, Josh, et al.
Published: (2025)