Cover Image

Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jiang, Minhui, Chen, Yuansi
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Machine Learning Computation
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
by: Silwal, Sandeep, et al.
Published: (2025)

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

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

Optimal Dimension-Free Sampling for Regularized Classification
by: Alishahi, Meysam, et al.
Published: (2026)

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

Online Metric Matching: Beyond the Worst Case
by: Yang, Mingwei, et al.
Published: (2024)

Beyond Worst Case Local Computation Algorithms
by: Biswas, Amartya Shankha, et al.
Published: (2024)

A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Dynamic Data Layout Optimization with Worst-case Guarantees
by: Rong, Kexin, et al.
Published: (2024)

Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions
by: Qin, Yilong, et al.
Published: (2023)

Efficient Parameter Estimation of Truncated Boolean Product Distributions
by: Fotakis, Dimitris, et al.
Published: (2020)

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

Graph-based Nearest Neighbors with Dynamic Updates via Random Walks
by: Mishra, Nina, et al.
Published: (2025)

Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach
by: Pinto Jr, Renato Ferreira
Published: (2024)

The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions
by: McWhorter, Atticus, et al.
Published: (2025)

Worst-case Error Bounds for Online Learning of Smooth Functions
by: Xie, Weian
Published: (2025)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
by: Bansal, Nikhil, et al.
Published: (2024)

Truncated Variance Reduced Value Iteration
by: Jin, Yujia, et al.
Published: (2024)

Private Statistical Estimation via Truncation
by: Zampetakis, Manolis, et al.
Published: (2025)

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

Sample-Adaptivity Tradeoff in On-Demand Sampling
by: Haghtalab, Nika, et al.
Published: (2025)

From Amortized to Worst Case Delay in Enumeration Algorithms
by: Capelli, Florent, et al.
Published: (2021)

InstaHide's Sample Complexity When Mixing Two Private Images
by: Huang, Baihe, et al.
Published: (2020)

On the Efficiency of Sinkhorn-Knopp for Entropically Regularized Optimal Transport
by: He, Kun
Published: (2026)

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

The Sample Complexity of Replicable Realizable PAC Learning
by: Larsen, Kasper Green, et al.
Published: (2026)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
by: Abboud, Amir, et al.
Published: (2024)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
by: Blanc, Guy, et al.
Published: (2024)

Truthfulness of Calibration Measures
by: Haghtalab, Nika, et al.
Published: (2024)

(Worst-Case) Optimal Adaptive Dynamic Bitvectors
by: Navarro, Gonzalo
Published: (2024)

Dynamic Set Cover with Worst-Case Recourse
by: Solomon, Shay, et al.
Published: (2025)

Efficient Certificates of Anti-Concentration Beyond Gaussians
by: Bakshi, Ainesh, et al.
Published: (2024)

Thompson Sampling Itself is Differentially Private
by: Ou, Tingting, et al.
Published: (2024)

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

Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
by: Manthey, Bodo, et al.
Published: (2023)

Hypergraph Samplers: Typical and Worst Case Behavior
by: Alev, Vedat Levi, et al.
Published: (2026)

Fast and explainable clustering based on sorting
by: Chen, Xinye, et al.
Published: (2022)