More Like this

1. Edge Expansion and Spectral Gap of Nonnegative Matrices

   https://doi.org/10.1137/1.9781611975994.73  

   Mehta, Jenish C.; Schulman, Leonard J. (January 2020, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms)

   The classic graphical Cheeger inequalities state that if $$M$$ is an $$n\times n$$ \emph{symmetric} doubly stochastic matrix, then \[ \frac{1-\lambda_{2}(M)}{2}\leq\phi(M)\leq\sqrt{2\cdot(1-\lambda_{2}(M))} \] where $$\phi(M)=\min_{S\subseteq[n],|S|\leq n/2}\left(\frac{1}{|S|}\sum_{i\in S,j\not\in S}M_{i,j}\right)$$ is the edge expansion of $$M$$, and $$\lambda_{2}(M)$$ is the second largest eigenvalue of $$M$$. We study the relationship between $$\phi(A)$$ and the spectral gap $$1-\re\lambda_{2}(A)$$ for \emph{any} doubly stochastic matrix $$A$$ (not necessarily symmetric), where $$\lambda_{2}(A)$$ is a nontrivial eigenvalue of $$A$$ with maximum real part. Fiedler showed that the upper bound on $$\phi(A)$$ is unaffected, i.e., $$\phi(A)\leq\sqrt{2\cdot(1-\re\lambda_{2}(A))}$$. With regards to the lower bound on $$\phi(A)$$, there are known constructions with \[ \phi(A)\in\Theta\left(\frac{1-\re\lambda_{2}(A)}{\log n}\right), \] indicating that at least a mild dependence on $$n$$ is necessary to lower bound $$\phi(A)$$. In our first result, we provide an \emph{exponentially} better construction of $$n\times n$$ doubly stochastic matrices $$A_{n}$$, for which \[ \phi(A_{n})\leq\frac{1-\re\lambda_{2}(A_{n})}{\sqrt{n}}. \] In fact, \emph{all} nontrivial eigenvalues of our matrices are $$0$$, even though the matrices are highly \emph{nonexpanding}. We further show that this bound is in the correct range (up to the exponent of $$n$$), by showing that for any doubly stochastic matrix $$A$$, \[ \phi(A)\geq\frac{1-\re\lambda_{2}(A)}{35\cdot n}. \] As a consequence, unlike the symmetric case, there is a (necessary) loss of a factor of $$n^{\alpha}$ for $$\frac{1}{2}\leq\alpha\leq1$$ in lower bounding $$\phi$$ by the spectral gap in the nonsymmetric setting. Our second result extends these bounds to general matrices $$R$$ with nonnegative entries, to obtain a two-sided \emph{gapped} refinement of the Perron-Frobenius theorem. Recall from the Perron-Frobenius theorem that for such $$R$$, there is a nonnegative eigenvalue $$r$$ such that all eigenvalues of $$R$$ lie within the closed disk of radius $$r$$ about $$0$$. Further, if $$R$$ is irreducible, which means $$\phi(R)>0$$ (for suitably defined $$\phi$$), then $$r$$ is positive and all other eigenvalues lie within the \textit{open} disk, so (with eigenvalues sorted by real part), $$\re\lambda_{2}(R) 

   more » « less
2. Channels, Billiards, and Perfect Matching 2-Divisibility

   https://doi.org/10.37236/9151  

   Barkley, Grant T.; Liu, Ricky Ini (April 2021, The Electronic Journal of Combinatorics)

   null (Ed.)

   Let $$m_G$$ denote the number of perfect matchings of the graph $$G$$. We introduce a number of combinatorial tools for determining the parity of $$m_G$$ and giving a lower bound on the power of 2 dividing $$m_G$$. In particular, we introduce certain vertex sets called channels, which correspond to elements in the kernel of the adjacency matrix of $$G$$ modulo $$2$$. A result of Lovász states that the existence of a nontrivial channel is equivalent to $$m_G$$ being even. We give a new combinatorial proof of this result and strengthen it by showing that the number of channels gives a lower bound on the power of $$2$$ dividing $$m_G$$ when $$G$$ is planar. We describe a number of local graph operations which preserve the number of channels. We also establish a surprising connection between 2-divisibility of $$m_G$$ and dynamical systems by showing an equivalency between channels and billiard paths. We exploit this relationship to show that $$2^{\frac{\gcd(m+1,n+1)-1}{2}}$$ divides the number of domino tilings of the $$m\times n$$ rectangle. We also use billiard paths to give a fast algorithm for counting channels (and hence determining the parity of the number of domino tilings) in simply connected regions of the square grid. 

   more » « less
3. On cusps of caustics by reflection in two dimensional projective Finsler metrics

   https://doi.org/10.2298/TAM250109004T  

   Tabachnikov, Serge (January 2025, Theoretical and Applied Mechanics)

   Given a projective Finsler metric in a convex domain in the projective plane, that is, a metric in which geodesics are straight lines, consider the respective Finsler billiard system. Choose a generic point inside the table and consider the billiard trajectories that start at this point and undergo N reflection off the boundary. The envelope of the resulting 1-parameter family of straight lines is the Nth caustic by reflection. We prove that, for every N, it has at least four cusps, generalizing a similar result for Euclidean metric, obtained recently jointly with G. Bor. 

   more » « less
4. Concatenating Bipartite Graphs

   https://doi.org/10.37236/8451  

   Chudnovsky, Maria; Hompe, Patrick; Scott, Alex; Seymour, Paul; Spirkl, Sophie (April 2022, The Electronic Journal of Combinatorics)

   Let $$x,y\in (0,1]$$, and let $A,B,C$ be disjoint nonempty stable subsets of a graph $$G$$, where every vertex in $$A$$ has at least $x|B|$ neighbours in $$B$$, and every vertex in $$B$$ has at least $y|C|$ neighbours in $$C$$, and there are no edges between $A,C$. We denote by $$\phi(x,y)$$ the maximum $$z$$ such that, in all such graphs $$G$$, there is a vertex $$v\in C$$ that is joined to at least $z|A|$ vertices in $$A$$ by two-edge paths. This function has some interesting properties: we show, for instance, that $$\phi(x,y)=\phi(y,x)$$ for all $x,y$, and there is a discontinuity in $$\phi(x,x)$$ when $1/x$ is an integer. For $z=1/2, 2/3,1/3,3/4,2/5,3/5$, we try to find the (complicated) boundary between the set of pairs $(x,y)$ with $$\phi(x,y)\ge z$$ and the pairs with $$\phi(x,y)1/3$. 

   more » « less
5. Lion secretly solves constrained optimization: As lyapunov predicts

   Chen, Lizhang; Liu, Bo; Liang, Kaizhao; Liu, Qiang (January 2024, International Conference of Learning Representations)

   Lion (Evolved Sign Momentum), a new optimizer discovered through program search, has shown promising results in training large AI models. It performs comparably or favorably to AdamW but with greater memory efficiency. As we can expect from the results of a random search program, Lion incorporates elements from several existing algorithms, including signed momentum, decoupled weight decay, Polak, and Nesterov momentum, but does not fit into any existing category of theoretically grounded optimizers. Thus, even though Lion appears to perform well as a general-purpose optimizer for a wide range of tasks, its theoretical basis remains uncertain. This lack of theoretical clarity limits opportunities to further enhance and expand Lion's efficacy. This work aims to demystify Lion. Based on both continuous-time and discrete-time analysis, we demonstrate that Lion is a theoretically novel and principled approach for minimizing a general loss function $f(x)$ while enforcing a bound constraint $$\norm{x}_\infty \leq 1/\lambda$$. Lion achieves this through the incorporation of decoupled weight decay, where $$\lambda$$ represents the weight decay coefficient. Our analysis is made possible by the development of a new Lyapunov function for the Lion updates. It applies to a broader family of Lion-$$\phi$$ algorithms, where the $$\text{sign}(\cdot)$$ operator in Lion is replaced by the subgradient of a convex function $$\phi$$, leading to the solution of a general composite optimization problem of $$\min_x f(x) + \phi^*(x)$$. Our findings provide valuable insights into the dynamics of Lion and pave the way for further improvements and extensions of Lion-related algorithms. 

   more » « less