Jaehong Moon

Jaehong Moon

We study gradient descent for rank-1 matrix factorization through a certificate-based viewpoint. The central object is a parameterized quadratic certificate $I(δ;\,\cdot)$ whose level sets shrink along the dynamics, thereby inducing a monotone state parameter $δ_t$. In the certified regime, this mechanism yields convergence to a global minimizer; in the post-critical regime, it forces trajectories toward a terminal balanced manifold. To explain the origin of these certificates, we formulate a state-dependent Lyapunov framework based on structural axioms. Within this framework, the scalar certificate is uniquely determined, and the same local Lagrange analysis constrains the signal and noise blocks of rank-1 extensions. Thus, the certificates arise from the monotonicity structure of the dynamics, rather than from ad hoc algebraic constructions. We also provide numerical evidence beyond the proved cases. For the 2-dimensional rank-1 approximation problem $X=\mathrm{diag}(1,σ)$ with $σ\in(0,1)$, the experiments are consistent with the existence of a $C^1$ admissible certificate branch. For the quartic-augmented scalar loss $\frac12(ab-1)^2+μ(ab-1)^4$, the same scalar certificate remains predictive for several values of $μ$ after choosing an empirical threshold. These experiments suggest that the state-dependent Lyapunov method may extend beyond the settings proved in this paper.

Jaehong Moon

Fictitious play (FP) is a history-based strategy to choose actions in normal-form games, where players best-respond to the empirical frequency of their opponents' past actions. While it is well-established that FP converges to the set of Nash equilibria (NE) in zero-sum games, the question of whether it converges to a single equilibrium point, especially when multiple equilibria exist, has remained an open challenge. In this paper, we establish that FP does not necessarily stabilize at a single equilibrium. Specifically, we identify a class of zero-sum games where pointwise convergence fails, regardless of the tie-breaking rules employed. We prove that two geometric conditions on the NE set (A1 and A2) and a technical assumption (A3) are sufficient to preclude pointwise convergence. Furthermore, we conjecture that the first two conditions alone may be sufficient to guarantee this non-convergence, suggesting a broader fundamental instability in FP dynamics.