Search

This paper presents a family of algorithms for decentralized convex composite problems. We consider the setting of a network of agents that cooperatively minimize a global objective function composed of a sum of local functions plus a regularizer. Through the use of intermediate consensus variables, we remove the need for inner communication loops between agents when computing curvature-guided updates. A general scheme is presented which unifies the analysis for a plethora of computing choices, including gradient descent, Newton updates, and BFGS updates. Our analysis establishes sublinear convergence rates under convex objective functions with Lipschitz continuous gradients, as well as linear convergence rates when the local functions are further assumed to be strongly convex. Moreover, we explicitly characterize the acceleration due to curvature information. Last but not the least, we present an asynchronous implementation for the proposed algorithms, which removes the need for a central clock, with linear convergence rates established in expectation under strongly convex objectives. We ascertain the effectiveness of the proposed methods with numerical experiments on benchmark datasets.

Convolutional and recurrent neural networks have been widely employed to achieve state-of-the-art performance on classification tasks. However, it has also been noted that these networks can be manipulated adversarially with relative ease, by carefully crafted additive perturbations to the input. Though several experimentally established prior works exist on crafting and defending against attacks, it is also desirable to have theoretical guarantees on the existence of adversarial examples and robustness margins of the network to such examples. We provide both in this paper. We focus specifically on recurrent architectures and draw inspiration from dynamical systems theory to naturally cast this as a control problem, allowing us to dynamically compute adversarial perturbations at each timestep of the input sequence, thus resembling a feedback controller. Illustrative examples are provided to supplement the theoretical discussions., Comment: Submitted to IEEE Transactions on Neural Networks and Learning Systems

To use neural networks in safety-critical settings it is paramount to provide assurances on their runtime operation. Recent work on ReLU networks has sought to verify whether inputs belonging to a bounded box can ever yield some undesirable output. Input-splitting procedures, a particular type of verification mechanism, do so by recursively partitioning the input set into smaller sets. The efficiency of these methods is largely determined by the number of splits the box must undergo before the property can be verified. In this work, we propose a new technique based on shadow prices that fully exploits the information of the problem yielding a more efficient generation of splits than the state-of-the-art. Results on the Airborne Collision Avoidance System (ACAS) benchmark verification tasks show a considerable reduction in the partitions generated which substantially reduces computation times. These results open the door to improved verification methods for a wide variety of machine learning applications including vision and control.