We propose a randomized multiplicative weight update (MWU) algorithm for $\ell_{\infty}$ regression that runs in $\widetilde{O}\left(n^{2+1/22.5} \text{poly}(1/\epsilon)\right)$ time when $\omega = 2+o(1)$, improving upon the previous best $\widetilde{O}\left(n^{2+1/18} \text{poly} \log(1/\epsilon)\right)$ runtime in the low-accuracy regime. Our algorithm combines state-of-the-art inverse maintenance data structures with acceleration. In order to do so, we propose a novel acceleration scheme for MWU that exhibits {\it stabiliy} and {\it robustness}, which are required for the efficient implementations of the inverse maintenance data structures. We also design a faster {\it deterministic} MWU algorithm that runs in $\widetilde{O}\left(n^{2+1/12}\text{poly}(1/\epsilon)\right))$ time when $\omega = 2+o(1)$, improving upon the previous best $\widetilde{O}\left(n^{2+1/6} \text{poly} \log(1/\epsilon)\right)$ runtime in the low-accuracy regime. We achieve this by showing a novel stability result that goes beyond the previous known works based on interior point methods (IPMs). Our work is the first to use acceleration and inverse maintenance together efficiently, finally making the two most important building blocks of modern structured convex optimization compatible.
相關內容
Can the $\lambda$-calculus be considered a reasonable computational model? Can we use it for measuring the time $\textit{and}$ space consumption of algorithms? While the literature contains positive answers about time, much less is known about space. This paper presents a new reasonable space cost model for the $\lambda$-calculus, based on a variant over the Krivine abstract machine. For the first time, this cost model is able to accommodate logarithmic space. Moreover, we study the time behavior of our machine and show how to transport our results to the call-by-value $\lambda$-calculus.
We prove that the number of partitions of the hypercube ${\bf Z}_q^n$ into $q^m$ subcubes of dimension $n-m$ each for fixed $q$, $m$ and growing $n$ is asymptotically equal to $n^{(q^m-1)/(q-1)}$. For the proof, we introduce the operation of the bang of a star matrix and demonstrate that any star matrix, except for a fractal, is expandable under some bang, whereas a fractal remains to be a fractal under any bang.
We consider a novel algorithm, for the completion of partially observed low-rank matrices in a structured setting where each entry can be chosen from a finite discrete alphabet set, such as in common recommender systems. The proposed low-rank matrix completion (MC) method is an improved variation of state-of-the-art (SotA) discrete aware matrix completion method which we previously proposed, in which discreteness is enforced by an $\ell_0$-norm regularizer, not by replaced with the $\ell_1$-norm, but instead approximated by a continuous and differentiable function normalized via fractional programming (FP) under a proximal gradient (PG) framework. Simulation results demonstrate the superior performance of the new method compared to the SotA techniques as well as the earlier $\ell_1$-norm-based discrete-aware matrix completion approach.
The problem of identifying the satisfiability threshold of random $3$-SAT formulas has received a lot of attention during the last decades and has inspired the study of other threshold phenomena in random combinatorial structures. The classical assumption in this line of research is that, for a given set of $n$ Boolean variables, each clause is drawn uniformly at random among all sets of three literals from these variables, independently from other clauses. Here, we keep the uniform distribution of each clause, but deviate significantly from the independence assumption and consider richer families of probability distributions. For integer parameters $n$, $m$, and $k$, we denote by $\DistFamily_k(n,m)$ the family of probability distributions that produce formulas with $m$ clauses, each selected uniformly at random from all sets of three literals from the $n$ variables, so that the clauses are $k$-wise independent. Our aim is to make general statements about the satisfiability or unsatisfiability of formulas produced by distributions in $\DistFamily_k(n,m)$ for different values of the parameters $n$, $m$, and $k$.
This paper develops a general asymptotic theory of series estimators for spatial data collected at irregularly spaced locations within a sampling region $R_n \subset \mathbb{R}^d$. We employ a stochastic sampling design that can flexibly generate irregularly spaced sampling sites, encompassing both pure increasing and mixed increasing domain frameworks. Specifically, we focus on a spatial trend regression model and a nonparametric regression model with spatially dependent covariates. For these models, we investigate $L^2$-penalized series estimation of the trend and regression functions. We establish uniform and $L^2$ convergence rates and multivariate central limit theorems for general series estimators as main results. Additionally, we show that spline and wavelet series estimators achieve optimal uniform and $L^2$ convergence rates and propose methods for constructing confidence intervals for these estimators. Finally, we demonstrate that our dependence structure conditions on the underlying spatial processes include a broad class of random fields, including L\'evy-driven continuous autoregressive and moving average random fields.
How hard is it to estimate a discrete-time signal $(x_{1}, ..., x_{n}) \in \mathbb{C}^n$ satisfying an unknown linear recurrence relation of order $s$ and observed in i.i.d. complex Gaussian noise? The class of all such signals is parametric but extremely rich: it contains all exponential polynomials over $\mathbb{C}$ with total degree $s$, including harmonic oscillations with $s$ arbitrary frequencies. Geometrically, this class corresponds to the projection onto $\mathbb{C}^{n}$ of the union of all shift-invariant subspaces of $\mathbb{C}^\mathbb{Z}$ of dimension $s$. We show that the statistical complexity of this class, as measured by the squared minimax radius of the $(1-\delta)$-confidence $\ell_2$-ball, is nearly the same as for the class of $s$-sparse signals, namely $O\left(s\log(en) + \log(\delta^{-1})\right) \cdot \log^2(es) \cdot \log(en/s).$ Moreover, the corresponding near-minimax estimator is tractable, and it can be used to build a test statistic with a near-minimax detection threshold in the associated detection problem. These statistical results rest upon an approximation-theoretic one: we show that finite-dimensional shift-invariant subspaces admit compactly supported reproducing kernels whose Fourier spectra have nearly the smallest possible $\ell_p$-norms, for all $p \in [1,+\infty]$ at once.
In metric $k$-clustering, we are given as input a set of $n$ points in a general metric space, and we have to pick $k$ centers and cluster the input points around these chosen centers, so as to minimize an appropriate objective function. In recent years, significant effort has been devoted to the study of metric $k$-clustering problems in a dynamic setting, where the input keeps changing via updates (point insertions/deletions), and we have to maintain a good clustering throughout these updates. The performance of such a dynamic algorithm is measured in terms of three parameters: (i) Approximation ratio, which signifies the quality of the maintained solution, (ii) Recourse, which signifies how stable the maintained solution is, and (iii) Update time, which signifies the efficiency of the algorithm. We consider the metric $k$-median problem, where the objective is the sum of the distances of the points to their nearest centers. We design the first dynamic algorithm for this problem with near-optimal guarantees across all three performance measures (up to a constant factor in approximation ratio, and polylogarithmic factors in recourse and update time). Specifically, we obtain a $O(1)$-approximation algorithm for dynamic metric $k$-median with $\tilde{O}(1)$ recourse and $\tilde{O}(k)$ update time. Prior to our work, the state-of-the-art here was the recent result of [Bhattacharya et al., FOCS'24], who obtained $O(\epsilon^{-1})$-approximation ratio with $\tilde{O}(k^{\epsilon})$ recourse and $\tilde{O}(k^{1+\epsilon})$ update time. We achieve our results by carefully synthesizing the concept of robust centers introduced in [Fichtenberger et al., SODA'21] along with the randomized local search subroutine from [Bhattacharya et al., FOCS'24], in addition to several key technical insights of our own.
The celebrated Morris counter uses $\log_2\log_2 n + O(\log_2 \sigma^{-1})$ bits to count up to $n$ with a relative error $\sigma$, where if $\hat{\lambda}$ is the estimate of the current count $\lambda$, then $\mathbb{E}|\hat{\lambda}-\lambda|^2 <\sigma^2\lambda^2$. A natural generalization is \emph{multi-dimensional} approximate counting. Let $d\geq 1$ be the dimension. The count vector $x\in \mathbb{N}^d$ is incremented entry-wisely over a stream of coordinates $(w_1,\ldots,w_n)\in [d]^n$, where upon receiving $w_k\in[d]$, $x_{w_k}\gets x_{w_k}+1$. A \emph{$d$-dimensional approximate counter} is required to count $d$ coordinates simultaneously and return an estimate $\hat{x}$ of the count vector $x$. Aden-Ali, Han, Nelson, and Yu \cite{aden2022amortized} showed that the trivial solution of using $d$ Morris counters that track $d$ coordinates separately is already optimal in space, \emph{if each entry only allows error relative to itself}, i.e., $\mathbb{E}|\hat{x}_j-x_j|^2<\sigma^2|x_j|^2$ for each $j\in [d]$. However, for another natural error metric -- the \emph{Euclidean mean squared error} $\mathbb{E} |\hat{x}-x|^2$ -- we show that using $d$ separate Morris counters is sub-optimal. In this work, we present a simple and optimal $d$-dimensional counter with Euclidean relative error $\sigma$, i.e., $\mathbb{E} |\hat{x}-x|^2 <\sigma^2|x|^2$ where $|x|=\sqrt{\sum_{j=1}^d x_j^2}$, with a matching lower bound. The upper and lower bounds are proved with ideas that are strikingly simple. The upper bound is constructed with a certain variable-length integer encoding and the lower bound is derived from a straightforward volumetric estimation of sphere covering.
The $d$-independence number of a graph $G$ is the largest possible size of an independent set $I$ in $G$ where each vertex of $I$ has degree at least $d$ in $G$. Upper bounds for the $d$-independence number in planar graphs are well-known for $d=3,4,5$, and can in fact be matched with constructions that actually have minimum degree $d$. In this paper, we explore the same questions for 1-planar graphs, i.e., graphs that can be drawn in the plane with at most one crossing per edge. We give upper bounds for the $d$-independence number for all $d$. Then we give constructions that match the upper bound, and (for small $d$) also have minimum degree $d$.
$\mathsf{QMA}_1$ is $\mathsf{QMA}$ with perfect completeness, i.e., the prover must accept with a probability of exactly $1$ in the YES-case. Whether $\mathsf{QMA}_1$ and $\mathsf{QMA}$ are equal is still a major open problem. It is not even known whether $\mathsf{QMA}_1$ has a universal gateset; Solovay-Kitaev does not apply due to perfect completeness. Hence, we do not generally know whether $\mathsf{QMA}_1^G=\mathsf{QMA}_1^{G'}$ (superscript denoting gateset), given two universal gatesets $G,G'$. In this paper, we make progress towards the gateset question by proving that for all $k\in\mathbb N$, the gateset $G_{2^k}$ (Amy et al., RC 2024) is universal for all gatesets in the cyclotomic field $\mathbb{Q}(\zeta_{2^k}),\zeta_{2^k}=e^{2\pi i/2^k}$, i.e. $\mathsf{QMA}_1^G\subseteq\mathsf{QMA}_1^{G_{2^k}}$ for all gatesets $G$ in $\mathbb{Q}(\zeta_{2^k})$. For $\mathsf{BQP}_1$, we can even show that $G_2$ suffices for all $2^k$-th cyclotomic fields. We exhibit complete problems for all $\mathsf{QMA}_1^{G_{2^k}}$: Quantum $l$-SAT in $\mathbb{Q}(\zeta_{2^k})$ is complete for $\mathsf{QMA}_1^{G_{2^k}}$ for all $l\ge4$, and $l=3$ if $k\ge3$, where quantum $l$-SAT is the problem of deciding whether a set of $l$-local Hamiltonians has a common ground state. Additionally, we give the first $\mathsf{QMA}_1$-complete $2$-local Hamiltonian problem: It is $\mathsf{QMA}_1^{G_{2^k}}$-complete (for $k\ge3$) to decide whether a given $2$-local Hamiltonian $H$ in $\mathbb{Q}(\zeta_{2^k})$ has a nonempty nullspace. Our techniques also extend to sparse Hamiltonians, and so we can prove the first $\mathsf{QMA}_1(2)$-complete (i.e. $\mathsf{QMA}_1$ with two unentangled provers) Hamiltonian problem. Finally, we prove that the Gapped Clique Homology problem defined by King and Kohler (FOCS 2024) is $\mathsf{QMA}_1^{G_2}$-complete, and the Clique Homology problem without promise gap is PSPACE-complete.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191