亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

We study a core algorithmic problem in network design called $\mathcal{F}$-augmentation that involves increasing the connectivity of a given family of cuts $\mathcal{F}$. Over 30 years ago, Williamson et al. (STOC `93) provided a 2-approximation primal-dual algorithm when $\mathcal{F}$ is a so-called uncrossable family but extending their results to families that are non-uncrossable has remained a challenging question. In this paper, we introduce the concept of the crossing density of a set family and show how this opens up a completely new approach to analyzing primal-dual algorithms. We study pliable families, a strict generalization of uncrossable families introduced by Bansal et al. (ICALP `23), and provide the first approximation algorithm for $\mathcal{F}$-augmentation of such families based on the crossing density. We also improve on the results in Bansal et al. (ICALP `23) by providing a 5-approximation algorithm for the $\mathcal{F}$-augmentation problem when $\mathcal{F}$ is a family of near min-cuts using the concept of crossing densities. This immediately improves approximation factors for the Capacitated Network Design Problem. Finally, we study the $(p,3)$-flexible graph connectivity problem. By carefully analyzing the structure of feasible solutions and using the techniques developed in this paper, we provide the first constant factor approximation algorithm for this problem exhibiting a 12-approximation algorithm.

Classically, the continuous-time Langevin diffusion converges exponentially fast to its stationary distribution $\pi$ under the sole assumption that $\pi$ satisfies a Poincar\'e inequality. Using this fact to provide guarantees for the discrete-time Langevin Monte Carlo (LMC) algorithm, however, is considerably more challenging due to the need for working with chi-squared or R\'enyi divergences, and prior works have largely focused on strongly log-concave targets. In this work, we provide the first convergence guarantees for LMC assuming that $\pi$ satisfies either a Lata\l{}a--Oleszkiewicz or modified log-Sobolev inequality, which interpolates between the Poincar\'e and log-Sobolev settings. Unlike prior works, our results allow for weak smoothness and do not require convexity or dissipativity conditions.

We consider the proof system Res($\oplus$) introduced by Itsykson and Sokolov (Ann. Pure Appl. Log.'20), which is an extension of the resolution proof system and operates with disjunctions of linear equations over $\mathbb{F}_2$. We study characterizations of tree-like size and space of Res($\oplus$) refutations using combinatorial games. Namely, we introduce a class of extensible formulas and prove tree-like size lower bounds on it using Prover-Delayer games, as well as space lower bounds. This class is of particular interest since it contains many classical combinatorial principles, including the pigeonhole, ordering, and dense linear ordering principles. Furthermore, we present the width-space relation for Res($\oplus$) generalizing the results by Atserias and Dalmau (J. Comput. Syst. Sci.'08) and their variant of Spoiler-Duplicator games.

This note provides a basic description of subgaussianity, by defining $(\sigma, \rho)$-subgaussian random variables $X$ ($\sigma>0, \rho>0$) as those satisfying $\mathbb{E}(\exp(\lambda X))\leq \rho\exp(\frac{1}{2}\sigma^2\lambda^2)$ for any $\lambda\in\mathbb{R}$. The introduction of the parameter $\rho$ may be particularly useful for those seeking to refine bounds, or align results from different sources, in the analysis of stochastic processes and concentration inequalities.

For a fixed graph property $\Phi$ and integer $k \geq 1$, the problem $\#\mathrm{IndSub}(\Phi,k)$ asks to count the induced $k$-vertex subgraphs satisfying $\Phi$ in an input graph $G$. If $\Phi$ is trivial on $k$-vertex graphs (i.e., if $\Phi$ contains either all or no $k$-vertex graphs), this problem is trivial. Otherwise we prove, among other results: - If $\Phi$ is edge-monotone (i.e., closed under deleting edges), then $\#\mathrm{IndSub}(\Phi,k)$ cannot be solved in time $n^{o(k)}$ assuming ETH. This strengthens a result by D\"oring, Marx and Wellnitz [STOC 2024] that only ruled out an exponent of $o(\sqrt{\log k}/ \log \log k)$. Our results also hold when counting modulo fixed primes. - If there is some fixed $\varepsilon > 0$ such that at most $(2-\varepsilon)^{\binom{k}{2}}$ graphs on $k$ vertices satisfy $\Phi$, then $\#\mathrm{IndSub}(\Phi,k)$ cannot be solved in time $n^{o(k/\sqrt{\log k})}$ assuming ETH. Our results hold even when each of the graphs in $\Phi$ may come with an arbitrary individual weight. This generalizes previous results for hereditary properties by Focke and Roth [SIAM J.\ Comput.\ 2024] up to a $\sqrt{\log k}$ factor in the exponent of the lower bound. - If $\Phi$ only depends on the number of edges, then $\#\mathrm{IndSub}(\Phi,k)$ cannot be solved in time $n^{o(k)}$ assuming ETH. This improves on a lower bound by Roth, Schmitt and Wellnitz [FOCS 2020] that only ruled out an exponent of $o(k / \sqrt{\log k})$. In all cases, we also obtain $\mathsf{\#W[1]}$-hardness if $k$ is part of the input and the problem is parameterized by $k$. We also obtain lower bounds on the Weisfeiler-Leman dimension. Our results follow from relatively straightforward Fourier analysis, and our paper subsumes most of the known $\mathsf{\#W[1]}$-hardness results known in the area, often with tighter lower bounds under ETH.

Beam search with masked language models (MLMs) is challenging in part because joint probability distributions over sequences are not readily available, unlike for autoregressive models. However, estimating such distributions has important domain-specific applications such as ancient text restoration and protein engineering. Here we present probabilistically-sound methods for beam search with MLMs. First, we clarify the conditions under which it is theoretically sound to perform text infilling with MLMs using standard beam search. When these conditions fail, we provide a probabilistically-sound modification with no additional computational complexity and demonstrate that it is superior to the aforementioned beam search in the expected conditions. We then present empirical results comparing several infilling approaches with MLMs across several domains.

Finding the most sparse solution to the underdetermined system $\mathbf{y}=\mathbf{Ax}$, given a tolerance, is known to be NP-hard. A popular way to approximate a sparse solution is by using Greedy Pursuit algorithms, and Orthogonal Matching Pursuit (OMP) is one of the most widely used such solutions. For this paper, we implemented an efficient implementation of OMP that leverages Cholesky inverse properties as well as the power of Graphics Processing Units (GPUs) to deliver up to 200x speedup over the OMP implementation found in Scikit-Learn.

We consider Kernelized Bandits (KBs) to optimize a function $f : \mathcal{X} \rightarrow [0,1]$ belonging to the Reproducing Kernel Hilbert Space (RKHS) $\mathcal{H}_k$. Mainstream works on kernelized bandits focus on a subgaussian noise model in which observations of the form $f(\mathbf{x}_t)+\epsilon_t$, being $\epsilon_t$ a subgaussian noise, are available (Chowdhury and Gopalan, 2017). Differently, we focus on the case in which we observe realizations $y_t \sim \text{Ber}(f(\mathbf{x}_t))$ sampled from a Bernoulli distribution with parameter $f(\mathbf{x}_t)$. While the Bernoulli model has been investigated successfully in multi-armed bandits (Garivier and Capp\'e, 2011), logistic bandits (Faury et al., 2022), bandits in metric spaces (Magureanu et al., 2014), it remains an open question whether tight results can be obtained for KBs. This paper aims to draw the attention of the online learning community to this open problem.

Cold-start problems are long-standing challenges for practical recommendations. Most existing recommendation algorithms rely on extensive observed data and are brittle to recommendation scenarios with few interactions. This paper addresses such problems using few-shot learning and meta learning. Our approach is based on the insight that having a good generalization from a few examples relies on both a generic model initialization and an effective strategy for adapting this model to newly arising tasks. To accomplish this, we combine the scenario-specific learning with a model-agnostic sequential meta-learning and unify them into an integrated end-to-end framework, namely Scenario-specific Sequential Meta learner (or s^2 meta). By doing so, our meta-learner produces a generic initial model through aggregating contextual information from a variety of prediction tasks while effectively adapting to specific tasks by leveraging learning-to-learn knowledge. Extensive experiments on various real-world datasets demonstrate that our proposed model can achieve significant gains over the state-of-the-arts for cold-start problems in online recommendation. Deployment is at the Guess You Like session, the front page of the Mobile Taobao.