More Like this

1. Outlier Robust Multivariate Polynomial Regression

   https://doi.org/10.4230/LIPIcs.ESA.2024.12  

   Arora, Vipul; Bhattacharyya, Arnab; Boban, Mathews; Guruswami, Venkatesan; Kelman, Esty (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz (Ed.)

   We study the problem of robust multivariate polynomial regression: let p: ℝⁿ → ℝ be an unknown n-variate polynomial of degree at most d in each variable. We are given as input a set of random samples (𝐱_i,y_i) ∈ [-1,1]ⁿ × ℝ that are noisy versions of (𝐱_i,p(𝐱_i)). More precisely, each 𝐱_i is sampled independently from some distribution χ on [-1,1]ⁿ, and for each i independently, y_i is arbitrary (i.e., an outlier) with probability at most ρ < 1/2, and otherwise satisfies |y_i-p(𝐱_i)| ≤ σ. The goal is to output a polynomial p̂, of degree at most d in each variable, within an 𝓁_∞-distance of at most O(σ) from p. Kane, Karmalkar, and Price [FOCS'17] solved this problem for n = 1. We generalize their results to the n-variate setting, showing an algorithm that achieves a sample complexity of O_n(dⁿlog d), where the hidden constant depends on n, if χ is the n-dimensional Chebyshev distribution. The sample complexity is O_n(d^{2n}log d), if the samples are drawn from the uniform distribution instead. The approximation error is guaranteed to be at most O(σ), and the run-time depends on log(1/σ). In the setting where each 𝐱_i and y_i are known up to N bits of precision, the run-time’s dependence on N is linear. We also show that our sample complexities are optimal in terms of dⁿ. Furthermore, we show that it is possible to have the run-time be independent of 1/σ, at the cost of a higher sample complexity. 

   more » « less
2. Fast Regression for Structured Inputs

   Meyer, Raphael; Musco, Cameron; Musco, Christopher; Woodruff, David P.; Zhou, Samson (April 2022, International Conference on Learning Representations (ICLR))

   We study the $$\ell_p$$ regression problem, which requires finding $$\mathbf{x}\in\mathbb R^{d}$$ that minimizes $$\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_p$$ for a matrix $$\mathbf{A}\in\mathbb R^{n \times d}$$ and response vector $$\mathbf{b}\in\mathbb R^{n}$$. There has been recent interest in developing subsampling methods for this problem that can outperform standard techniques when $$n$$ is very large. However, all known subsampling approaches have run time that depends exponentially on $$p$$, typically, $$d^{\mathcal{O}(p)}$$, which can be prohibitively expensive. We improve on this work by showing that for a large class of common \emph{structured matrices}, such as combinations of low-rank matrices, sparse matrices, and Vandermonde matrices, there are subsampling based methods for $$\ell_p$$ regression that depend polynomially on $$p$$. For example, we give an algorithm for $$\ell_p$$ regression on Vandermonde matrices that runs in time $$\mathcal{O}(n\log^3 n+(dp^2)^{0.5+\omega}\cdot\text{polylog}\,n)$$, where $$\omega$$ is the exponent of matrix multiplication. The polynomial dependence on $$p$$ crucially allows our algorithms to extend naturally to efficient algorithms for $$\ell_\infty$$ regression, via approximation of $$\ell_\infty$$ by $$\ell_{\mathcal{O}(\log n)}$$. Of practical interest, we also develop a new subsampling algorithm for $$\ell_p$$ regression for arbitrary matrices, which is simpler than previous approaches for $$p \ge 4$$. 

   more » « less
3. Equivalence of codes for countable sets of reals

   https://doi.org/10.4153/S0008439520000661  

   Chan, William (September 2021, Canadian Mathematical Bulletin)

   null (Ed.)

   Abstract A set $$U \subseteq {\mathbb {R}} \times {\mathbb {R}}$$ is universal for countable subsets of $${\mathbb {R}}$$ if and only if for all $$x \in {\mathbb {R}}$$ , the section $$U_x = \{y \in {\mathbb {R}} : U(x,y)\}$$ is countable and for all countable sets $$A \subseteq {\mathbb {R}}$$ , there is an $$x \in {\mathbb {R}}$$ so that $$U_x = A$$ . Define the equivalence relation $$E_U$$ on $${\mathbb {R}}$$ by $$x_0 \ E_U \ x_1$$ if and only if $$U_{x_0} = U_{x_1}$$ , which is the equivalence of codes for countable sets of reals according to U . The Friedman–Stanley jump, $=^+$ , of the equality relation takes the form $$E_{U^*}$$ where $U^*$ is the most natural Borel set that is universal for countable sets. The main result is that $=^+$ and $$E_U$$ for any U that is Borel and universal for countable sets are equivalent up to Borel bireducibility. For all U that are Borel and universal for countable sets, $$E_U$$ is Borel bireducible to $=^+$ . If one assumes a particular instance of $$\mathbf {\Sigma }_3^1$$ -generic absoluteness, then for all $$U \subseteq {\mathbb {R}} \times {\mathbb {R}}$$ that are $$\mathbf {\Sigma }_1^1$$ (continuous images of Borel sets) and universal for countable sets, there is a Borel reduction of $=^+$ into $$E_U$$ . 

   more » « less
4. Zeroes of polynomials on definable hypersurfaces: pathologies exist, but they are rare

   https://doi.org/10.1093/qmath/haz022  

   Basu, Saugata; Lerario, Antonio; Natarajan, Abhiram (October 2019, The Quarterly Journal of Mathematics)

   Abstract Given a sequence $$\{Z_d\}_{d\in \mathbb{N}}$$ of smooth and compact hypersurfaces in $${\mathbb{R}}^{n-1}$$, we prove that (up to extracting subsequences) there exists a regular definable hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^n$$ such that each manifold $$Z_d$$ is diffeomorphic to a component of the zero set on $$\Gamma$$ of some polynomial of degree $$d$$. (This is in sharp contrast with the case when $$\Gamma$$ is semialgebraic, where for example the homological complexity of the zero set of a polynomial $$p$$ on $$\Gamma$$ is bounded by a polynomial in $$\deg (p)$$.) More precisely, given the above sequence of hypersurfaces, we construct a regular, compact, semianalytic hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^{n}$$ containing a subset $$D$$ homeomorphic to a disk, and a family of polynomials $$\{p_m\}_{m\in \mathbb{N}}$$ of degree $$\deg (p_m)=d_m$$ such that $$(D, Z(p_m)\cap D)\sim ({\mathbb{R}}^{n-1}, Z_{d_m}),$$ i.e. the zero set of $$p_m$$ in $$D$$ is isotopic to $$Z_{d_m}$$ in $${\mathbb{R}}^{n-1}$$. This says that, up to extracting subsequences, the intersection of $$\Gamma$$ with a hypersurface of degree $$d$$ can be as complicated as we want. We call these ‘pathological examples’. In particular, we show that for every $$0 \leq k \leq n-2$$ and every sequence of natural numbers $$a=\{a_d\}_{d\in \mathbb{N}}$$ there is a regular, compact semianalytic hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^n$$, a subsequence $$\{a_{d_m}\}_{m\in \mathbb{N}}$$ and homogeneous polynomials $$\{p_{m}\}_{m\in \mathbb{N}}$$ of degree $$\deg (p_m)=d_m$$ such that (0.1)$$\begin{equation}b_k(\Gamma\cap Z(p_m))\geq a_{d_m}.\end{equation}$$ (Here $$b_k$$ denotes the $$k$$th Betti number.) This generalizes a result of Gwoździewicz et al. [13]. On the other hand, for a given definable $$\Gamma$$ we show that the Fubini–Study measure, in the Gaussian probability space of polynomials of degree $$d$$, of the set $$\Sigma _{d_m,a, \Gamma }$$ of polynomials verifying (0.1) is positive, but there exists a constant $$c_\Gamma$$ such that $$\begin{equation*}0<{\mathbb{P}}(\Sigma_{d_m, a, \Gamma})\leq \frac{c_{\Gamma} d_m^{\frac{n-1}{2}}}{a_{d_m}}.\end{equation*}$$ This shows that the set of ‘pathological examples’ has ‘small’ measure (the faster $$a$$ grows, the smaller the measure and pathologies are therefore rare). In fact we show that given $$\Gamma$$, for most polynomials a Bézout-type bound holds for the intersection $$\Gamma \cap Z(p)$$: for every $$0\leq k\leq n-2$$ and $t>0$: $$\begin{equation*}{\mathbb{P}}\left(\{b_k(\Gamma\cap Z(p))\geq t d^{n-1} \}\right)\leq \frac{c_\Gamma}{td^{\frac{n-1}{2}}}.\end{equation*}$$ 

   more » « less
5. Subconvexity in Inhomogeneous Vinogradov Systems

   https://doi.org/10.1093/qmath/haac027  

   Wooley, Trevor D. (August 2022, The Quarterly Journal of Mathematics)

   Abstract When k and s are natural numbers and $${\mathbf h}\in {\mathbb Z}^k$$, denote by $$J_{s,k}(X;\,{\mathbf h})$$ the number of integral solutions of the system $$ \sum_{i=1}^s(x_i^j-y_i^j)=h_j\quad (1\leqslant j\leqslant k), $$ with $$1\leqslant x_i,y_i\leqslant X$$. When $$s\lt k(k+1)/2$$ and $$(h_1,\ldots ,h_{k-1})\ne {\mathbf 0}$$, Brandes and Hughes have shown that $$J_{s,k}(X;\,{\mathbf h})=o(X^s)$$. In this paper we improve on quantitative aspects of this result, and, subject to an extension of the main conjecture in Vinogradov’s mean value theorem, we obtain an asymptotic formula for $$J_{s,k}(X;\,{\mathbf h})$$ in the critical case $s=k(k+1)/2$. The latter requires minor arc estimates going beyond square-root cancellation. 

   more » « less