Ruichen Jiang

Ruichen Jiang, Zakaria Mhammedi, Mehryar Mohri et al.

We study online linear optimization with matrix variables constrained by the operator norm, a setting where the geometry renders designing data-dependent and efficient adaptive algorithms challenging. The best-known adaptive regret bounds are achieved by Shampoo-like methods, but they require solving a costly quadratic projection subproblem. To address this, we extend the gradient-based prediction scheme to adaptive matrix online learning and cast algorithm design as constructing a family of smoothed potentials for the nuclear norm. We define a notion of admissibility for such smoothings and prove any admissible smoothing yields a regret bound matching the best-known guarantees of one-sided Shampoo. We instantiate this framework with two efficient methods that avoid quadratic projections. The first is an adaptive Follow-the-Perturbed-Leader (FTPL) method using Gaussian stochastic smoothing. The second is Follow-the-Augmented-Matrix-Leader (FAML), which uses a deterministic hyperbolic smoothing in an augmented matrix space. By analyzing the admissibility of these smoothings, we show both methods admit closed-form updates and match one-sided Shampoo's regret up to a constant factor, while significantly reducing computational cost. Lastly, using the online-to-nonconvex conversion, we derive two matrix-based optimizers, Pion (from FTPL) and Leon (from FAML). We prove convergence guarantees for these methods in nonsmooth nonconvex settings, a guarantee that the popular Muon optimizer lacks.

Ruichen Jiang, Sheng Zhou

In this paper, we study a federated learning system at the wireless edge that uses over-the-air computation (AirComp). In such a system, users transmit their messages over a multi-access channel concurrently to achieve fast model aggregation. Recently, an AirComp scheme based on digital modulation has been proposed featuring one-bit gradient quantization and truncated channel inversion at users and a majority-voting based decoder at the fusion center (FC). We propose an improved digital AirComp scheme to relax its requirements on the transmitters, where users perform phase correction and transmit with full power. To characterize the decoding failure probability at the FC, we introduce the normalized detection signal-to-noise ratio (SNR), which can be interpreted as the effective participation rate of users. To mitigate wireless fading, we further propose a cluster-based system and design the relay selection scheme based on the normalized detection SNR. By local data fusion within each cluster and relay selection, our scheme can fully exploit spatial diversity to increase the effective number of voting users and accelerate model convergence.