:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Beretta, Lorenzo
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2505.05819
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Feature Selection and Junta Testing are Statistically Equivalent
by: Beretta, Lorenzo, et al.
Published: (2025)

Learning Juntas under Markov Random Fields
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
by: Beretta, Lorenzo, et al.
Published: (2025)

Computational and Statistical Hardness of Calibration Distance
by: Qiao, Mingda
Published: (2026)

Statistical-Computational Trade-offs for Density Estimation
by: Aamand, Anders, et al.
Published: (2024)

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification
by: Rohatgi, Dhruv, et al.
Published: (2025)

On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
by: Joshi, Nirmit, et al.
Published: (2024)

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

Testable Learning with Distribution Shift
by: Klivans, Adam R., et al.
Published: (2023)

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

Efficient Discrepancy Testing for Learning with Distribution Shift
by: Chandrasekaran, Gautam, et al.
Published: (2024)

Distribution Learning Meets Graph Structure Sampling
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Iterative Chow Filtering for Learning with Distribution Shift
by: Chandrasekaran, Gautam, et al.
Published: (2026)

Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees
by: Chandrasekaran, Gautam, et al.
Published: (2025)

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

On Computing Total Variation Distance Between Mixtures of Product Distributions
by: Feng, Weiming, et al.
Published: (2026)

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

Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approach
by: Kang, Bosun, et al.
Published: (2025)

Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries
by: Beretta, Lorenzo, 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)

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

On Computing Optimal Tree Ensembles
by: Komusiewicz, Christian, et al.
Published: (2023)

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

Binary Search with Distributional Predictions
by: Dinitz, Michael, et al.
Published: (2024)

Statistical Query Lower Bounds for Learning Truncated Gaussians
by: Diakonikolas, Ilias, et al.
Published: (2024)

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

Distribution-Free Sequential Prediction with Abstentions
by: Yu, Jialin, et al.
Published: (2026)

A Statistical View of Column Subset Selection
by: Sood, Anav, et al.
Published: (2023)

Optimal Algorithms for Augmented Testing of Discrete Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2024)

Ski Rental with Distributional Predictions of Unknown Quality
by: Cui, Qiming, et al.
Published: (2026)

Detection of Common Subtrees with Identical Label Distribution
by: Azaïs, Romain, et al.
Published: (2023)

Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2026)

Efficient Adaptive Data Analysis over Dense Distributions
by: Huh, Joon Suk
Published: (2026)

Self-Supervised Graph Learning via Spectral Bootstrapping and Laplacian-Based Augmentations
by: Bini, Lorenzo, et al.
Published: (2025)

Handling Delayed Feedback in Distributed Online Optimization : A Projection-Free Approach
by: Nguyen, Tuan-Anh, et al.
Published: (2024)

New Bounds for Kernel Sums via Fast Spherical Embeddings
by: Wagner, Tal
Published: (2026)

DDPM Score Matching and Distribution Learning
by: Chewi, Sinho, et al.
Published: (2025)

Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach
by: Yang, Yichun, et al.
Published: (2024)

New bounds on the cohesion of complete-link and other linkage methods for agglomeration clustering
by: Dasgupta, Sanjoy, et al.
Published: (2024)

A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs
by: Shah, Poojan, et al.
Published: (2025)