Search for: All records

Non-asymptotic analysis of quasi-Newton methods have gained traction recently. In particular, several works have established a non-asymptotic superlinear rate of O((1/sqrt{t})^t) for the (classic) BFGS method by exploiting the fact that its error of Newton direction approximation approaches zero. Moreover, a greedy variant of BFGS was recently proposed which accelerates its convergence by directly approximating the Hessian, instead of the Newton direction, and achieves a fast local quadratic convergence rate. Alas, the local quadratic convergence of Greedy-BFGS requires way more updates compared to the number of iterations that BFGS requires for a local superlinear rate. This is due to the fact that in Greedy-BFGS the Hessian is directly approximated and the Newton direction approximation may not be as accurate as the one for BFGS. In this paper, we close this gap and present a novel BFGS method that has the best of both worlds in that it leverages the approximation ideas of both BFGS and GreedyBFGS to properly approximate the Newton direction and the Hessian matrix simultaneously. Our theoretical results show that our method outperforms both BFGS and Greedy-BFGS in terms of convergence rate, while it reaches its quadratic convergence rate with fewer steps compared to Greedy-BFGS. Numerical experiments on various datasets also confirm our theoretical findings. 

We consider a group of agents that estimate their locations in an environment through sensor measurements and aim to transmit a message signal to a client via collaborative beamforming. Assuming that the localization error of each agent follows a Gaussian distribution, we study the problem of forming a reliable communication link between the agents and the client that achieves a desired signal-to-noise ratio (SNR) at the client with minimum variability. In particular, we develop a greedy subset selection algorithm that chooses only a subset of the agents to transmit the signal so that the variance of the received SNR is minimized while the expected SNR exceeds a desired threshold. We show the optimality of the proposed algorithm when the agents’ localization errors satisfy certain sufficient conditions that are characterized in terms of the carrier frequency.