Related papers: A common variable minimax theorem for graphs

A common variable minimax theorem for graphs

URL: http://arxiv.org/abs/2107.14747v1
Date: Fri, 30 Jul 2021 16:47:25 GMT
Title: A common variable minimax theorem for graphs
Authors: Ronald R. Coifman, Nicholas F. Marshall, Stefan Steinerberger
Abstract summary: We study the problem of understanding whether there exists a nonconstant function that is smooth with respect to all graphs in $mathcalG$, simultaneously, and how to find it if it exists.
Score: 3.0079490585515343
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Let $\mathcal{G} = \{G_1 = (V, E_1), \dots, G_m = (V, E_m)\}$ be a collection of $m$ graphs defined on a common set of vertices $V$ but with different edge sets $E_1, \dots, E_m$. Informally, a function $f :V \rightarrow \mathbb{R}$ is smooth with respect to $G_k = (V,E_k)$ if $f(u) \sim f(v)$ whenever $(u, v) \in E_k$. We study the problem of understanding whether there exists a nonconstant function that is smooth with respect to all graphs in $\mathcal{G}$, simultaneously, and how to find it if it exists.

Related papers

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
arXiv Detail & Related papers (2024-10-07T19:47:13Z)
Efficient Continual Finite-Sum Minimization [52.5238287567572]
We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization. Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires. We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
arXiv Detail & Related papers (2024-06-07T08:26:31Z)
Perfect state transfer on Cayley graphs over a non-abelian group of order $8n$ [0.0]
We study the existence of perfect state transfer on Cayley graphs $textCay(V_8n, S)$.
arXiv Detail & Related papers (2024-05-03T14:24:51Z)
A note on estimating the dimension from a random geometric graph [2.3020018305241337]
We study the problem of estimating the dimension $d$ of the underlying space when we have access to the adjacency matrix of the graph. We also show that, without any condition on the density, a consistent estimator of $d$ exists when $n r_nd to infty$ and $r_n = o(1)$.
arXiv Detail & Related papers (2023-11-21T23:46:44Z)
Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
arXiv Detail & Related papers (2023-04-17T10:38:08Z)
(1,1)-Cluster Editing is Polynomial-time Solvable [0.0]
Abu-Khzam introduced the $(a,d)$- Editing problem, where for fixed natural numbers $a,d$, given a graph $G and affirmative-weights $a*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*: V(
arXiv Detail & Related papers (2022-10-14T11:40:34Z)
Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
arXiv Detail & Related papers (2021-10-21T18:43:00Z)
Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
This paper deals with the problem of graph matching or network alignment for ErdHos--R'enyi graphs. It can be viewed as a noisy average-case version of the graph isomorphism problem.
arXiv Detail & Related papers (2021-10-11T05:07:50Z)
Linear Bandits on Uniformly Convex Sets [88.3673525964507]
Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
arXiv Detail & Related papers (2021-03-10T07:33:03Z)
Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
We show that the exponential dependence on the dimension dimension $d in the celebrated fast multipole method of Greengard and Rokhlin cannot be improved. This is the first formal limitation proven about fast multipole methods.
arXiv Detail & Related papers (2020-11-04T18:35:02Z)
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
arXiv Detail & Related papers (2020-02-17T18:41:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.