:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Gu, Xiang, Zhang, Huichun, Sun, Jian
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2604.12211
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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)

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

Lower Bounds for Greedy Teaching Set Constructions
by: Compton, Spencer, 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)

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

SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions
by: Diakonikolas, Ilias, et al.
Published: (2024)

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
by: Assadi, Sepehr, et al.
Published: (2023)

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

Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover
by: Harris, Blake, et al.
Published: (2024)

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
by: Chen, Yixin, et al.
Published: (2026)

Quantum Algorithms and Lower Bounds for Finite-Sum Optimization
by: Zhang, Yexin, et al.
Published: (2024)

Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes
by: Peter, Naty, et al.
Published: (2023)

Query Lower Bounds for Diffusion Sampling
by: Xun, Zhiyang, et al.
Published: (2026)

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
by: Li, Yi, et al.
Published: (2024)

Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes
by: Portella, Victor S., et al.
Published: (2024)

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

Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis
by: Lyu, Xin, et al.
Published: (2024)

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

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

Tight Bounds for Learning Polyhedra with a Margin
by: Patel, Shyamal, 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 Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming
by: Xu, Haoran, et al.
Published: (2026)

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

PTF Testing Lower Bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2025)

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

Towards Optimal Differentially Private Regret Bounds in Linear MDPs
by: Sahu, Sharan
Published: (2025)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
by: Luo, Yuetian, et al.
Published: (2023)

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
by: Sakaue, Shinsaku, et al.
Published: (2026)

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

Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk
by: Gu, Yuzhou, et al.
Published: (2024)

Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets
by: Oki, Taihei, et al.
Published: (2026)

Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification
by: Zhang, Guangyi, et al.
Published: (2026)

An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum $s$-Bundle Problem
by: Xue, Jinghui, et al.
Published: (2024)

Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation
by: Pagh, Rasmus, et al.
Published: (2024)

Dynamic Spectral Clustering with Provable Approximation Guarantee
by: Laenen, Steinar, et al.
Published: (2024)

Knowing When to Stop Matters: A Unified Algorithm for Online Conversion under Horizon Uncertainty
by: Wang, Yanzhao, et al.
Published: (2025)