The Heilbronn triangle problem asks for the placement of $n$ points in a unit square that maximizes the smallest area of a triangle formed by any three of those points. In $1972$, Schmidt considered a natural generalization of this problem. He asked for the placement of $n$ points in a unit square that maximizes the smallest area of the convex hull formed by any four of those points. He showed a lower bound of $\Omega(n^{-3/2})$, which was improved to $\Omega(n^{-3/2}\log{n})$ by Leffman. A trivial upper bound of $3/n$ could be obtained, and Schmidt asked if this could be improved asymptotically. However, despite several efforts, no asymptotic improvement over the trivial upper bound was known for the last $50$ years, and the problem started to get the tag of being notoriously hard. Szemer{\'e}di posed the question of whether one can, at least, improve the constant in this trivial upper bound. In this work, we answer this question by proving an upper bound of $2/n+o(1/n)$. We also extend our results to any convex hulls formed by $k\geq 4$ points.
相關內容
Fitting's Heyting-valued logic and Heyting-valued modal logic have already been studied from an algebraic viewpoint. In addition to algebraic axiomatizations with the completeness of Fitting's Heyting-valued logic and Heyting-valued modal logic, both topological and coalgebraic dualities have also been developed for algebras of Fitting's Heyting-valued modal logic. Bitopological methods have recently been employed to investigate duality for Fitting's Heyting-valued logic. However, the concepts of bitopology and biVietoris coalgebras are conspicuously absent from the development of dualities for Fitting's many-valued modal logic. With this study, we try to bridge that gap. We develop a bitopological duality for algebras of Fitting's Heyting-valued modal logic. We construct a bi-Vietoris functor on the category $PBS_{\mathcal{L}}$ of $\mathcal{L}$-valued ($\mathcal{L}$ is a Heyting algebra) pairwise Boolean spaces. Finally, we obtain a dual equivalence between categories of biVietoris coalgebras and algebras of Fitting's Heyting-valued modal logic. As a result, we conclude that Fitting's many-valued modal logic is sound and complete with respect to the coalgebras of a biVietoris functor. We discuss the application of this coalgebraic approach to bitopological duality.
We introduce a new Langevin dynamics based algorithm, called e-TH$\varepsilon$O POULA, to solve optimization problems with discontinuous stochastic gradients which naturally appear in real-world applications such as quantile estimation, vector quantization, CVaR minimization, and regularized optimization problems involving ReLU neural networks. We demonstrate both theoretically and numerically the applicability of the e-TH$\varepsilon$O POULA algorithm. More precisely, under the conditions that the stochastic gradient is locally Lipschitz in average and satisfies a certain convexity at infinity condition, we establish non-asymptotic error bounds for e-TH$\varepsilon$O POULA in Wasserstein distances and provide a non-asymptotic estimate for the expected excess risk, which can be controlled to be arbitrarily small. Three key applications in finance and insurance are provided, namely, multi-period portfolio optimization, transfer learning in multi-period portfolio optimization, and insurance claim prediction, which involve neural networks with (Leaky)-ReLU activation functions. Numerical experiments conducted using real-world datasets illustrate the superior empirical performance of e-TH$\varepsilon$O POULA compared to SGLD, TUSLA, ADAM, and AMSGrad in terms of model accuracy.
An $n$-bit boolean function is resilient to coalitions of size $q$ if any fixed set of $q$ bits is unlikely to influence the function when the other $n-q$ bits are chosen uniformly. We give explicit constructions of depth-$3$ circuits that are resilient to coalitions of size $cn/\log^{2}n$ with bias $n^{-c}$. Previous explicit constructions with the same resilience had constant bias. Our construction is simpler and we generalize it to biased product distributions. Our proof builds on previous work; the main differences are the use of a tail bound for expander walks in combination with a refined analysis based on Janson's inequality.
When the target of inference is a real-valued function of probability parameters in the k-sample multinomial problem, variance estimation may be challenging. In small samples, methods like the nonparametric bootstrap or delta method may perform poorly. We propose a novel general method in this setting for computing exact p-values and confidence intervals which means that type I error rates are correctly bounded and confidence intervals have at least nominal coverage at all sample sizes. Our method is applicable to any real-valued function of multinomial probabilities, accommodating an arbitrary number of samples with varying category counts. We describe the method and provide an implementation of it in R, with some computational optimization to ensure broad applicability. Simulations demonstrate our method's ability to maintain correct coverage rates in settings where the nonparametric bootstrap fails.
This paper proposes a multivariate nonlinear function-on-function regression model, which allows both the response and the covariates can be multi-dimensional functions. The model is built upon the multivariate functional reproducing kernel Hilbert space (RKHS) theory. It predicts the response function by linearly combining each covariate function in their respective functional RKHS, and extends the representation theorem to accommodate model estimation. Further variable selection is proposed by adding the lasso penalty to the coefficients of the kernel functions. A block coordinate descent algorithm is proposed for model estimation, and several theoretical properties are discussed. Finally, we evaluate the efficacy of our proposed model using simulation data and a real-case dataset in meteorology.
We give a $(1.796+\epsilon)$-approximation for the minimum sum coloring problem on chordal graphs, improving over the previous 3.591-approximation by Gandhi et al. [2005]. To do so, we also design the first polynomial-time approximation scheme for the maximum $k$-colorable subgraph problem in chordal graphs.
Given an Abelian group G, a Boolean-valued function f: G -> {-1,+1}, is said to be s-sparse, if it has at most s-many non-zero Fourier coefficients over the domain G. In a seminal paper, Gopalan et al. proved "Granularity" for Fourier coefficients of Boolean valued functions over Z_2^n, that have found many diverse applications in theoretical computer science and combinatorics. They also studied structural results for Boolean functions over Z_2^n which are approximately Fourier-sparse. In this work, we obtain structural results for approximately Fourier-sparse Boolean valued functions over Abelian groups G of the form,G:= Z_{p_1}^{n_1} \times ... \times Z_{p_t}^{n_t}, for distinct primes p_i. We also obtain a lower bound of the form 1/(m^{2}s)^ceiling(phi(m)/2), on the absolute value of the smallest non-zero Fourier coefficient of an s-sparse function, where m=p_1 ... p_t, and phi(m)=(p_1-1) ... (p_t-1). We carefully apply probabilistic techniques from Gopalan et al., to obtain our structural results, and use some non-trivial results from algebraic number theory to get the lower bound. We construct a family of at most s-sparse Boolean functions over Z_p^n, where p > 2, for arbitrarily large enough s, where the minimum non-zero Fourier coefficient is 1/omega(n). The "Granularity" result of Gopalan et al. implies that the absolute values of non-zero Fourier coefficients of any s-sparse Boolean valued function over Z_2^n are 1/O(s). So, our result shows that one cannot expect such a lower bound for general Abelian groups. Using our new structural results on the Fourier coefficients of sparse functions, we design an efficient testing algorithm for Fourier-sparse Boolean functions, thata requires poly((ms)^phi(m),1/epsilon)-many queries. Further, we prove an Omega(sqrt{s}) lower bound on the query complexity of any adaptive sparsity testing algorithm.
In this paper, we study the problem of noisy, convex, zeroth order optimisation of a function $f$ over a bounded convex set $\bar{\mathcal X}\subset \mathbb{R}^d$. Given a budget $n$ of noisy queries to the function $f$ that can be allocated sequentially and adaptively, our aim is to construct an algorithm that returns a point $\hat x\in \bar{\mathcal X}$ such that $f(\hat x)$ is as small as possible. We provide a conceptually simple method inspired by the textbook center of gravity method, but adapted to the noisy and zeroth order setting. We prove that this method is such that the $f(\hat x) - \min_{x\in \bar{\mathcal X}} f(x)$ is of smaller order than $d^2/\sqrt{n}$ up to poly-logarithmic terms. We slightly improve upon existing literature, where to the best of our knowledge the best known rate is in [Lattimore, 2024] is of order $d^{2.5}/\sqrt{n}$, albeit for a more challenging problem. Our main contribution is however conceptual, as we believe that our algorithm and its analysis bring novel ideas and are significantly simpler than existing approaches.
We consider an on-line least squares regression problem with optimal solution $\theta^*$ and Hessian matrix H, and study a time-average stochastic gradient descent estimator of $\theta^*$. For $k\ge2$, we provide an unbiased estimator of $\theta^*$ that is a modification of the time-average estimator, runs with an expected number of time-steps of order k, with O(1/k) expected excess risk. The constant behind the O notation depends on parameters of the regression and is a poly-logarithmic function of the smallest eigenvalue of H. We provide both a biased and unbiased estimator of the expected excess risk of the time-average estimator and of its unbiased counterpart, without requiring knowledge of either H or $\theta^*$. We describe an "average-start" version of our estimators with similar properties. Our approach is based on randomized multilevel Monte Carlo. Our numerical experiments confirm our theoretical findings.
We investigate perturbations of orthonormal bases of $L^2$ via a composition operator $C_h$ induced by a mapping $h$. We provide a comprehensive characterization of the mapping $h$ required for the perturbed sequence to form an orthonormal or Riesz basis. Restricting our analysis to differentiable mappings, we reveal that all Riesz bases of the given form are induced by bi-Lipschitz mappings. In addition, we discuss implications of these results for approximation theory, highlighting the potential of using bijective neural networks to construct complete sequences with favorable approximation properties.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191