Robin is a second-year PhD student at the Institute for Computational and Mathematical engineering. Prior to coming to Stanford, she attended the California Institute of Technology where she received her B.S. in Mathematics; Business, Economics, and Managements, and Control and Dynamical Systems (minor). Her current research focuses on scalable and efficient algorithms for large-scale multi-agent systems.
Abstract: Verifying that input-output relationships of a neural network conform to prescribed operational specifications is a key enabler towards deploying these networks in safety-critical applications. Semidefinite programming (SDP)-based approaches to Rectified Linear Unit (ReLU) network verification transcribe this problem into an optimization problem, where the accuracy of any such formulation reflects the level of fidelity in how the neural network computation is represented, as well as the relaxations of intractable constraints. While the literature contains much progress on improving the tightness of SDP formulations while maintaining tractability, comparatively little work has been devoted to the other extreme, i.e., how to most accurately capture the original verification problem before SDP relaxation. In this work, we develop an exact, convex formulation of verification as a completely positive program (CPP), and provide analysis showing that our formulation is minimal—the removal of any constraint fundamentally misrepresents the neural network computation. We leverage our formulation to provide a unifying view of existing approaches, and give insight into the source of large relaxation gaps observed in some cases.
@inproceedings{BrownSchmerlingEtAl2022, author = {Brown, R. and Schmerling, E. and Azizan, N. and Pavone, M.}, title = {A Unified View of SDP-based Neural Network Verification through Completely Positive Programming}, booktitle = {{Int. Conf. on Artificial Intelligence and Statistics}}, year = {2022}, owner = {rabrown1}, timestamp = {2022-02-17} }
Abstract:
@unpublished{BrownBernalEtAl2022, author = {Brown, R. and Bernal, D. and Sahasrabudhe, A. and Lott, A. and Venturelli, D. and Pavone, M.}, title = {Copositive optimization via Ising solvers}, note = {Int. Conf. on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Extended Abstract.}, year = {2022}, owner = {rabrown1}, url = {/wp-content/papercite-data/pdf/Brown.Bernal.ea.pdf}, timestamp = {2022-04-07} }
Abstract:
@article{BrownBernalNeiraEtAl2022, author = {Brown, R. A. and Bernal Neira, D. E. and Venturelli, D. and Pavone, M.}, title = {Copositive programming for mixed-binary quadratic optimization via Ising solvers}, journal = {{SIAM Journal on Optimization}}, note = {Submitted}, year = {2022}, keywords = {sub}, timestamp = {2022-10-04} }
Abstract: A number of prototypical optimization problems in multi-agent systems (e.g., task allocation and network load-sharing) exhibit a highly local structure: that is, each agent’s decision variables are only directly coupled to few other agent’s variables through the objective function or the constraints. In this paper, we develop a rigorous notion of "locality" that quantifies the degree to which agents can compute their portion of the global solution of such a distributed optimization problem based solely on information in their local neighborhood. We build upon the results of Rebeschini and Tatikonda (2019) to develop a more general theory of locality that fully captures the importance of problem data to individual solution components, as opposed to a theory that only captures response to perturbations. This analysis provides a theoretical basis for a rather simple algorithm in which agents individually solve a truncated sub-problem of the global problem, where the size of the sub-problem used depends on the locality of the problem, and the desired accuracy. Numerical results show that the proposed theoretical bounds are remarkably tight for well-conditioned problems.
@article{BrownRossiEtAl2020, author = {Brown, R. A. and Rossi, F. and Solovey, K. and Tsao, M. and Wolf, M. T. and Pavone, M.}, title = {On Local Computation for Network-Structured Convex Optimization in Multi-Agent Systems}, journal = {{IEEE Transactions on Control of Network Systems}}, volume = {8}, number = {2}, pages = {542-554}, year = {2021}, url = {/wp-content/papercite-data/pdf/Brown.Rossi.ea.TCNS20.pdf}, owner = {rabrown1}, timestamp = {2021-08-31} }
Abstract: A number of prototypical optimization problems in multi-agent systems (e.g. task allocation and network load-sharing) exhibit a highly local structure: that is, each agent’s decision variables are only directly coupled to few other agent’s variables through the objective function or the constraints. Nevertheless, existing algorithms for distributed optimization generally do not exploit the locality structure of the problem, requiring all agents to compute or exchange the full set of decision variables. In this paper, we develop a rigorous notion of "locality" that relates the structural properties of a linearly-constrained convex optimization problem (in particular, the sparsity structure of the constraint matrix and the objective function) to the amount of information that agents should exchange to compute an arbitrarily high-quality approximation to the problem from a cold-start. We leverage the notion of locality to develop a locality-aware distributed optimization algorithm, and we show that, for problems where individual agents only require to know a small portion of the optimal solution, the algorithm requires very limited inter-agent communication. Numerical results show that the convergence rate of our algorithm is directly explained by the locality parameter proposed, and that the proposed theoretical bounds are remarkably tight.
@inproceedings{BrownRossiEtAl20, author = {Brown, R. A. and Rossi, F. and Solovey, K. and Wolf, M. T. and Pavone, M.}, title = {Exploiting Locality and Structure for Distributed Optimization in Multi-Agent Systems}, booktitle = {{European Control Conference}}, year = {2020}, address = {St. Petersburg, Russia}, month = may, url = {/wp-content/papercite-data/pdf/Brown.Rossi.ea.ECC20.pdf}, owner = {rabrown1}, timestamp = {2020-02-25} }