Publications by Subject Area

Distributed Optimization

• Local SGD With a Communication Overhead Depending Only on the Number of Workers
  A. Spiridonoff, A. Olshevsky, Y. Paschalidis
  Preprint.
• Asymptotic Network Independence and Step-Size for a Distributed Subgradient Method
  A. Olshevsky
  Preprint.
• Robust Asynchronous Stochastic Gradient Push: Asymptotically Optimal and Network Independent Performance for Strongly Convex Functions
  A. Spiridonoff, A. Olshevsky, Y. Paschalidis
  Journal of Machine Learning Research,  2020.
• Asymptotic Network Independence in Distributed Optimization for Machine Learning
  S. Pu, A. Olshevsky, Y. Paschalidis
  IEEE Signal Processing Magazine,  2020.
• Network Topology and Communication-Computation Tradeoffs in Distributed Optimization
  A. Nedic, A. Olshevsky, M. Rabbat
  Proceedings of the IEEE, 2018.
• Federated Learning of Predictive Models from Federated Electronic Health Records
  T. Brisimi, R. Chen, T. Mela, A. Olshevsky, Y. Paschalidis, W. Shi
  International Journal of Medical Informatics, 2018.
• A Non-Asymptotic Analysis of Network Independence for Distributed Stochastic Gradient Descent
  S. Pu, A. Olshevsky, Y. Paschalidis
  Preprint.
• Improved Convergence Rates for Distributed Resource Allocation
  A. Nedic, A. Olshevsky, W. Shi
  preprint
• Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs
  A. Nedic, A. Olshevsky, W. Shi
  SIAM Journal on Optimization, 2017.
• Linear Time Average Consensus on Fixed Graphs and Implications for Decentralized Optimization and Multi-Agent Control
  A. Olshevsky
  SIAM Journal on Control and Optimization, 2017.
• Distributed Resource Allocation on Dynamic Networks in Quadratic Time
  T. T. Doan, A. Olshevsky
  Systems & Control Letters, 2017.
• Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
  A. Nedic, A. Olshevsky
  IEEE Transactions on Automatic Control, 2016.
• Distributed Optimization over Time-Varying Directed Graphs
  A. Nedic, A. Olshevsky
  IEEE Transactions on Automatic Control, 2015.
• Fast Algorithms for Distributed Optimization and Hypothesis Testing: A Tutorial
  A. Olshevsky
  Proc. of CDC 2016, the 55th IEEE Conference on Decision and Control, Las Vegas, USA, 2016.
• Distributed Subgradient Methods and Quantization Effects
  A. Nedic, A. Olshevsky, A. Ozdaglar, J.N. Tsitsiklis
  Proc. CDC 08, the 47th IEEE Conference on Decision and Control, Cancun, Mexico, 2008.

Learning and Networks

• Temporal Difference Learning as Gradient Splitting, R. Liu, A. Olshevsky, Proceedings of ICML 2021, to appear.
• Adversarial Crowdsourcing Through Robust Rank-1 Matrix Completion
  Q. Ma, A. Olshevsky
  Proceedings of NeurIPS 2020.
• Minimax Rate for Pairwise Comparisons in the BTL Model, J. Hendrickx, A. Olshevsky, V. Saligrama,
  Proceedings of ICML 2020.
• Minimax Rank-1 Matrix Factorization
  J. Hendrickx, A. Olshevsky, V. Saligrama
  Proceedings of AISTATS 2020, the 23rd International Conference on Artificial Intelligence and Statistics, 2020.
• Graph Resistance and Learning from Pairwise Comparisons
  J. M. Hendrickx, A. Olshevsky, V. Saligrama
  Proceedings of ICML 2019, the 36th International Conference on Machine Learning, Long Beach, USA, 2019.
• Distributed Learning for Cooperative Inference
  A. Nedic, A. Olshevsky, C. Uribe
  preprint
• Gradient Descent for Sparse Rank-One Matrix Completion for Crowd-Sourced Aggregation of Sparsely Interacting Workers
  Y. Ma, A. Olshevsky, V. Saligrama, C. Szepesvari
  Proceedings of ICML 2018, the 35th International Conference on Machine Learning, Stockholm, Sweden, 2018.
  Journal in Journal of Machine Learning Research, 2020.
• Fast Convergence Rates for Distributed Non-Bayesian Learning
  A. Nedic, A. Olshevsky, C. Uribe
  IEEE Transactions on Automatic Control, 2017.
• Cooperative Learning in Multi-Agent Systems From Intermittent Measurements
  N. E. Leonard, A. Olshevsky
  SIAM Journal on Control and Optimization, 2015.
• A Tutorial on Distributed (Non-Bayesian) Learning: Problem, Algorithm, and Results
  A. Nedic, A. Olshevsky, C. Uribe
  Proc. of CDC 2016, the 55th IEEE Conference on Decision and Control, Las Vegas, USA
• Distributed Gaussian Learning over Time-Varying Directed Graphs
  A. Nedic, A. Olshevsky, C. Uribe
  Proc. of Asilomar 2016, the 51st Asilomar Conference on Signals, Systems, and Computers, Monterey, USA, 2016.

Control of Networks

• Deterministic and Randomized Actuator Scheduling with Guaranteed Performance Bounds
  M. Siami, A. Jadbabaie, A. Olshevsky
  IEEE Transactions on Automatic Control, 2021.
• On A Relaxation of Time-Varying Actuator Placement
  A. Olshevsky
  IEEE Control System Letters, 2020.
• Minimal Reachability is Hard to Approximate
  A. Jadbabaie, A. Olshevsky, G. Pappas, V. Tzoumas
  IEEE Transactions on Automatic Control, 2019.
• On (Non)Supermodularity of Average Control Energy
  A. Olshevsky
  IEEE Transactions on Control of Networked Systems, 2018.
• Eigenvalue Clustering, Control Energy, and Logarithmic Capacity
  A. Olshevsky
  Systems & Control Letters, 2016.
• Minimal Controllability Problems
  A. Olshevsky
  IEEE Transactions on Control of Networked Systems, 2014.
• Minimum Input Selection for Structural Controllability
  A. Olshevsky
  Proc. ACC 2015, the American Control Conference, Chicago, USA, 2015.

Multi-Agent Coordination and Control

• Graph Theoretic Analysis of Belief System Dynamics Under Logic Constraints
  A. Nedic, A. Olshevsky, C. Uribe
  Scientific Reports, 2019.
• Nonuniform Line Coverage from Noisy Scalar Measurements
  P. Davison, N.E. Leonard, A. Olshevsky, M. Schwemmer
  IEEE Transactions on Automatic Control, 2015.
• On Symmetric Continuum Opinion Dynamics
  J. M. Hendrickx, A. Olshevsky
  SIAM Journal on Control and Optimization, 2016.
• Nonuniform Coverage Control on the Line
  N.E. Leonard, A. Olshevsky
  IEEE Transactions on Automatic Control, 2013.
• Distributed Anonymous Discrete Function Computation
  J. M. Hendrickx, A. Olshevsky, J.N. Tsitsklis
  IEEE Transactions on Automatic Control, 2011.
  Special issue on Wireless Sensor and Actuator Networks.
• Primal-Dual Algorithms for QoS Multimedia Multicast
  G. Calinescu, C. Fernaneds, I. Mandoiu, A. Olshevsky, K. Yang, A. Zelikovsky
  Proc. GLOBECOM 03, the IEEE Global Communication Conference, San Francisco, USA, 2003.
• Network Lifetime and Power Assignment for Ad-Hoc Wireless Networks
  G. Galinescu, S. Kapoor, A. Olshevsky, and A. Zelikovsky
  Proc. ESA 03, the European Sympoisum on Algorithms, Budapest, Hungary, 2003.

Consensus Protocols

• Asymptotic Convergence Rate of Alternating Minimization for Rank One Matrix Completion
  R. Liu, A. Olshevsky
  IEEE Control Systems Letters, 2020
• Scaling Laws for Consensus Protocols Subject to Noise
  A. Jadbabaie, A. Olshevsky
  IEEE Transactions on Automatic Control, 2018.
• Linear Time Average Consensus on Fixed Graphs and Implications for Decentralized Optimization and Multi-Agent Control
  A. Olshevsky
  SIAM Journal on Control and Optimization, 2017.
• Convergence Time of Quantized Metropolis Consensus over Time-Varying Networks
  T. Basar, S. R. Etesami, A. Olshevsky
  IEEE Transactions on Automatic Control, 2016.
• How to Decide Consensus? A Combinatorial Necessary and Sufficient Condition and a Proof that Consensus is Decidable but NP-hard
  V. Blondel, A. Olshevsky
  SIAM Journal on Control and Optimization, 2014.
• Consensus with Ternary Messages
  A. Olshevsky
  SIAM Journal on Control and Optimization, 2014.
• Graph Diameter, Eigenvalues, and Minimum-Time Consensus 
  J. M. Hendrickx, R. M. Jungers, A. Olshevsky, G.  Vankeerberghen
  Automatica, 2014.
  
• Degree Fluctuations and the Convergence Time of Consensus Algorithms
  A. Olshevsky, J.N. Tsitsiklis
  IEEE Transactions on Automatic Control, 2013.
• How to Decide Consensus? A Combinatorial Necessary and Sufficient Condition and a Proof that Consensus is Decidable but NP-hard
  V. Blondel, A. Olshevsky
  SIAM Journal on Control and Optimization, 2014.
• Consensus with Ternary Messages
  A. Olshevsky
  SIAM Journal on Control and Optimization, 2014.
• Graph Diameter, Eigenvalues, and Minimum-Time Consensus 
  J. M. Hendrickx, R. M. Jungers, A. Olshevsky, G.  Vankeerberghen
  Automatica, 2014.
• Convergence Speed in Distributed Consensus and Averaging
  A. Olshevsky, J. N. Tsitsiklis
  SIAM Review, 2011
  This is a revision of paper originally published in SICON, rewritten
  for a more general audience at the invitation of the SIAM Review.
• Degree Fluctuations and the Convergence Time of Consensus Algorithms
  A. Olshevsky, J.N. Tsitsiklis
  IEEE Transactions on Automatic Control, 2013.
• On Distributed Averaging Algorithms and Quantization Effects
  A. Nedic, A. Olshevsky, A. Ozdaglar, J.N. Tsitsiklis
  IEEE Transactions on Automatic Control, 2009.
• A Lower Bound on Distributed Averaging on the Line Graph
  A. Olshevsky, J.N. Tsitsiklis
  IEEE Transactions on Automatic Control, 2011.
• On the Nonexistence of Quadratic Lyapunov Functions for Consensus Algorithms
  A. Olshevsky, J.N. Tsitsiklis
  IEEE Transactions on Automatic Control, 2008.

Complexity in Control and Optimization

• On the Inapproximability of the Discrete Witsenhausen Problem
  A. Olshevsky
  IEEE Control System Letters, 2019
• On Primitivity of Sets of Matrices
  V. Blondel, R. Jungers, A. Olshevsky
  Automatica, 2015.
  
• NP-hardness of Deciding Convexity for Quartic Polynomials and Related Problems
  A.A. Ahmadi, A. Olshevsky, P.A. Parrilo, J.N. Tsitsiklis
  Mathematical Programming, 2013.
• Matrix p-Norms are NP-hard to Approximate if p ≠ 1,2,∞ 
  J. M. Hendrickx, A. Olshevsky
  SIAM Journal on Matrix Analysis and Applications, 2010.
• On the NP-Hardness of Checking Matrix Polytope Stability and Continuous-Time Switching Stability
  L. Gurvits, A. Olshevsky
  IEEE Transactions on Automatic Control, 2009.
• Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem
  M. Karpinski, I. Mandoiu, A. Olshevsky, A. Zelikovsky
  Algorithmica, 2005.
• Stability Testing of Matrix Polytopes
  L. Gurvits, A. Olshevsky,
  Proc. of ECC 07, the European Control Conference, Kos, Greece, 2007.