Some remarks on the Gram-Schmidt walk algorithm and consequences for Komlos conjecture

2024/04/04 by Witold Bednorz, Bednorz, Witold, Piotr Godlewski +1 · 1 citation
Mathematics · Physics and Astronomy · #60G15 #60G17 #Advanced Differential Equations and Dynamical Systems #FOS: Mathematics #Mathematical Dynamics and Fractals #Probability (math.PR) #Quantum chaos and dynamical systems

paper · pdf · doi:10.48550/arxiv.2404.03534

openalex publication_date 2024/04/04 · openalex created_date 2024/04/06 · openalex updated_date 2026/07/28

Abstract

In this paper we improve the best known constant for the discrepancy formulated in the Komlos Conjecture. The result is based on the improvement of the subgaussian bound for the random vector constructed in the Gram-Schmidt Random Walk algorithm. Moreover, we present detailed argument for the smoothed analysis of this random vector. The analysis concerns a modification of a given matrix in the conjecture by a Gaussian type perturbation. Our result improves the recent paper in this direction.

Cited by

• Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors

Related

• Smoothed Analysis of the Komlós Conjecture
• Smoothed Analysis of the Komlós Conjecture: Rademacher Noise
• The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
• A Gaussian fixed point random walk
• Discrepancy Minimization via a Self-Balancing Walk