skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, February 13 until 2:00 AM ET on Friday, February 14 due to maintenance. We apologize for the inconvenience.


Title: Wirtinger Flow for Nonconvex Blind Demixing with Optimal Step Size
The prospect of massive deployment of devices for Internet-of-Things (IoT) motivates grant-free access for simultaneously uplink transmission by multiple nodes. Blind demixing represents a promising technique for recovering multiple such source signals over unknown channels. Recent studies show Wirtinger Flow (WF) algorithm can be effective in blind demixing. However, existing theoretical results on WF step size selection tend to be conservative and slow down convergence rates. To overcome this limitation, we propose an improved WF (WF-OPT) by optimizing its step size in each iteration and expediting the convergence. We provide a theoretical guarantee on the strict contraction of WF-OPT and present the upper bounds of the contraction ratio. Simulation results demonstrate the expected convergence gains.  more » « less
Award ID(s):
2009001 2029027
PAR ID:
10351732
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
IEEE wireless communications letters
ISSN:
2162-2337
Page Range / eLocation ID:
2477-2481
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    In this work, we analyze the convergence of constant modulus algorithm (CMA) in blindly recovering multiple signals to facilitate grant-free wireless access. The CMA typically solves a non-convex problem by utilizing stochastic gradient descent. The iterative convergence of CMA can be affected by additive channel noise and finite number of samples, which is a problem not fully investigated previously. We point out the strong similarity between CMA and the Wirtinger Flow (WF) algorithm originally proposed for Phase retrieval. In light of the convergence proof of WF under limited data samples, we adopt the WF algorithm to implement CMA-based blind signal recovery. We generalize the convergence analysis of WF in the context of CMA-based blind signal recovery. Numerical simulation results also corroborate the analysis. 
    more » « less
  2. As applications of Internet-of-things (IoT) rapidly expand, unscheduled multiple user access with low latency and low cost communication is attracting growing more interests. To recover the multiple uplink signals without strict access control under dynamic co-channel interference environment, the problem of blind demixing emerges as an important obstacle for us to overcome. Without channel state information, successful blind demixing can recover multiple user signals more effectively by leveraging prior information on signal characteristics such as constellations and distribution. This work studies how forward error correction (FEC) codes in Galois Field can generate more effective blind demixing algorithms. We propose a constrained Wirtinger flow algorithm by defining a valid signal set based on FEC codewords. Specifically, targeting the popular polar codes for FEC of short IoT packets, we introduce signal projections within iterations of Wirtinger Flow based on FEC code information. Simulation results demonstrate stronger robustness of the proposed algorithm against noise and practical obstacles and also faster convergence rate compared to regular Wirtinger flow algorithm. 
    more » « less
  3. We propose a new nonconvex framework for blind multiple signal demixing and recovery. The proposed Riemann geometric approach extends the well known constant modulus algorithm to facilitate grant-free wireless access. For multiple signal demixing and recovery, we formulate the problem as non-convex problem optimization problem with signal orthogonality constraint in the form of Riemannian Orthogonal CMA(ROCMA). Unlike traditional stochastic gradient solutions that require large data samples, parameter tuning, and careful initialization, we leverage Riemannian geometry and transform the orthogonality requirement of recovered signals into a Riemannian manifold optimization. Our solution demonstrates full recovery of multiple access signals without large data sample size or special initialization with high probability of success. 
    more » « less
  4. Stochastic (sub)gradient methods require step size schedule tuning to perform well in practice. Classical tuning strategies decay the step size polynomially and lead to optimal sublinear rates on (strongly) convex problems. An alternative schedule, popular in nonconvex optimization, is called geometric step decay and proceeds by halving the step size after every few epochs. In recent work, geometric step decay was shown to improve exponentially upon classical sublinear rates for the class of sharp convex functions. In this work, we ask whether geometric step decay similarly improves stochastic algorithms for the class of sharp weakly convex problems. Such losses feature in modern statistical recovery problems and lead to a new challenge not present in the convex setting: the region of convergence is local, so one must bound the probability of escape. Our main result shows that for a large class of stochastic, sharp, nonsmooth, and nonconvex problems a geometric step decay schedule endows well-known algorithms with a local linear (or nearly linear) rate of convergence to global minimizers. This guarantee applies to the stochastic projected subgradient, proximal point, and prox-linear algorithms. As an application of our main result, we analyze two statistical recovery tasks—phase retrieval and blind deconvolution—and match the best known guarantees under Gaussian measurement models and establish new guarantees under heavy-tailed distributions. 
    more » « less
  5. Oh, A ; Naumann, T ; Globerson, A ; Saenko, K ; Hardt, M ; Levine, S (Ed.)
    Multi-agent reinforcement learning (MARL) has primarily focused on solving a single task in isolation, while in practice the environment is often evolving, leaving many related tasks to be solved. In this paper, we investigate the benefits of meta-learning in solving multiple MARL tasks collectively. We establish the first line of theoretical results for meta-learning in a wide range of fundamental MARL settings, including learning Nash equilibria in two-player zero-sum Markov games and Markov potential games, as well as learning coarse correlated equilibria in general-sum Markov games. Under natural notions of task similarity, we show that meta-learning achieves provable sharper convergence to various game-theoretical solution concepts than learning each task separately. As an important intermediate step, we develop multiple MARL algorithms with initialization-dependent convergence guarantees. Such algorithms integrate optimistic policy mirror descents with stage-based value updates, and their refined convergence guarantees (nearly) recover the best known results even when a good initialization is unknown. To our best knowledge, such results are also new and might be of independent interest. We further provide numerical simulations to corroborate our theoretical findings. 
    more » « less