Search

When are two algorithms the same? How can we be sure a recently proposed algorithm is novel, and not a minor twist on an existing method? In this paper, we present a framework for reasoning about equivalence between a broad class of iterative algorithms, with a focus on algorithms designed for convex optimization. We propose several notions of what it means for two algorithms to be equivalent, and provide computationally tractable means to detect equivalence. Our main definition, oracle equivalence, states that two algorithms are equivalent if they result in the same sequence of calls to the function oracles (for suitable initialization). Borrowing from control theory, we use state-space realizations to represent algorithms and characterize algorithm equivalence via transfer functions. Our framework can also identify and characterize equivalence between algorithms that use different oracles that are related via a linear fractional transformation. Prominent examples include linear transformations and function conjugation., Comment: This paper generalizes and provides new analysis and examples compared to arxiv:2105.04684

This paper considers the discrete-time, stochastic LQR problem with $p$ steps of disturbance preview information where $p$ is finite. We first derive the solution for this problem on a finite horizon with linear, time-varying dynamics and time-varying costs. Next, we derive the solution on the infinite horizon with linear, time-invariant dynamics and time-invariant costs. Our proofs rely on the well-known principle of optimality. We provide an independent proof for the principle of optimality that relies only on nested information structure. Finally, we show that the finite preview controller converges to the optimal noncausal controller as the preview horizon $p$ tends to infinity. We also provide a simple example to illustrate both the finite and infinite horizon results.

We study a stealthy range-sensor placement problem where a set of range sensors are to be placed with respect to targets to effectively localize them while maintaining a degree of stealthiness from the targets. This is an open and challenging problem since two competing objectives must be balanced: (a) optimally placing the sensors to maximize their ability to localize the targets and (b) minimizing the information the targets gather regarding the sensors. We provide analytical solutions in 2D for the case of any number of sensors that localize two targets.

This paper introduces a novel control strategy for agile spacecraft attitude control, addressing reaction wheel-related input and state constraints. An optimal-decay control Lyapunov function quadratic program stabilizes the system and mitigates chattering at low sampling frequencies, while control barrier functions enforce hard state constraints. Numerical simulations validate the method's practicality and efficiency for real-time agile spacecraft attitude control.

Backtracking line search is foundational in numerical optimization. The basic idea is to adjust the step size of an algorithm by a constant factor until some chosen criterion (e.g. Armijo, Goldstein, Descent Lemma) is satisfied. We propose a new way for adjusting step sizes, replacing the constant factor used in regular backtracking with one that takes into account the degree to which the chosen criterion is violated, without additional computational burden. For convex problems, we prove adaptive backtracking requires fewer adjustments to produce a feasible step size than regular backtracking does for two popular line search criteria: the Armijo condition and the descent lemma. For nonconvex smooth problems, we additionally prove adaptive backtracking enjoys the same guarantees of regular backtracking. Finally, we perform a variety of experiments on over fifteen real world datasets, all of which confirm that adaptive backtracking often leads to significantly faster optimization.

We present Model Predictive Planning (MPP), a trajectory planner for low-agility vehicles such as a fixed-wing aircraft to navigate obstacle-laden environments. MPP consists of (1) a multi-path planning procedure that identifies candidate paths, (2) a raytracing procedure that generates linear constraints around these paths to enforce obstacle avoidance, and (3) a convex quadratic program that finds a feasible trajectory within these constraints if one exists. Low-agility aircraft cannot track arbitrary paths, so refining a given path into a trajectory that respects the vehicle's limited maneuverability and avoids obstacles often leads to an infeasible optimization problem. The critical feature of MPP is that it efficiently considers multiple candidate paths during the refinement process, thereby greatly increasing the chance of finding a feasible and trackable trajectory. We demonstrate the effectiveness of MPP on a longitudinal aircraft model.

We consider the distributed optimization problem for a multi-agent system. Here, multiple agents cooperatively optimize an objective by sharing information through a communication network and performing computations. In this tutorial, we provide an overview of the problem, describe the structure of its algorithms, and use simulations to illustrate some algorithmic properties based on this structure., Comment: 6 pages, 14 figures, to appear at IEEE Conference on Decision and Control 2023

Iterative gradient-based optimization algorithms are widely used to solve difficult or large-scale optimization problems. There are many algorithms to choose from, such as gradient descent and its accelerated variants such as Polyak's Heavy Ball method or Nesterov's Fast Gradient method. It has long been observed that iterative algorithms can be viewed as dynamical systems, and more recently, as robust controllers. Here, the "uncertainty" in the dynamics is the gradient of the function being optimized. Therefore, worst-case or average-case performance can be analyzed using tools from robust control theory, such as integral quadratic constraints (IQCs). In this tutorial paper, we show how such an analysis can be carried out using an alternative Lyapunov-based approach. This approach recovers the same performance bounds as with IQCs, but with the added benefit of constructing a Lyapunov function., Comment: 6 pages, 3 figures, to appear at IEEE Conference on Decision and Control 2023

Primal-dual algorithms are frequently used for iteratively solving large-scale convex optimization problems. The analysis of such algorithms is usually done on a case-by-case basis, and the resulting guaranteed rates of convergence can be conservative. Here we consider a class of first-order algorithms for linearly constrained convex optimization problems, and provide a linear matrix inequality (LMI) analysis framework for certifying worst-case exponential convergence rates. Our approach builds on recent results for interpolation of convex functions and linear operators, and our LMI directly constructs a Lyapunov function certifying the guaranteed convergence rate. By comparing to rates established in the literature, we show that our approach can certify significantly faster convergence for this family of algorithms., Comment: 6 pages, 2 figures, to appear at IEEE Conference on Decision and Control 2023

It is well-known that linear quadratic regulators (LQR) enjoy guaranteed stability margins, whereas linear quadratic Gaussian regulators (LQG) do not. In this letter, we consider systems and compensators defined over directed acyclic graphs. In particular, there are multiple decision-makers, each with access to a different part of the global state. In this setting, the optimal LQR compensator is dynamic, similar to classical LQG. We show that when sub-controller input costs are decoupled (but there is possible coupling between sub-controller state costs), the decentralized LQR compensator enjoys similar guaranteed stability margins to classical LQR. However, these guarantees disappear when cost coupling is introduced.

We revisit the classical problem of absolute stability; assessing the robust stability of a given linear time-invariant (LTI) plant in feedback with a nonlinearity belonging to some given function class. Standard results typically take the form of sufficient conditions on the LTI plant, the least conservative of which are based on O'Shea--Zames--Falb multipliers. We present an alternative analysis based on lifting and interpolation that directly constructs a Lyapunov function that certifies absolute stability without resorting to frequency-domain inequalities or integral quadratic constraints. In particular, we use linear matrix inequalities to search over Lyapunov functions that are quadratic in the iterates and linear in the corresponding function values of the system in a lifted space. We show that our approach recovers state-of-the-art results on a set of benchmark problems., Comment: 7 pages, to be published in proceedings of the IEEE Conference on Decision and Control, 2022

People have expectations about how colors map to concepts in visualizations, and they are better at interpreting visualizations that match their expectations. Traditionally, studies on these expectations (inferred mappings) distinguished distinct factors relevant for visualizations of categorical vs. continuous information. Studies on categorical information focused on direct associations (e.g., mangos are associated with yellows) whereas studies on continuous information focused on relational associations (e.g., darker colors map to larger quantities; dark-is-more bias). We unite these two areas within a single framework of assignment inference. Assignment inference is the process by which people infer mappings between perceptual features and concepts represented in encoding systems. Observers infer globally optimal assignments by maximizing the "merit," or "goodness," of each possible assignment. Previous work on assignment inference focused on visualizations of categorical information. We extend this approach to visualizations of continuous data by (a) broadening the notion of merit to include relational associations and (b) developing a method for combining multiple (sometimes conflicting) sources of merit to predict people's inferred mappings. We developed and tested our model on data from experiments in which participants interpreted colormap data visualizations, representing fictitious data about environmental concepts (sunshine, shade, wild fire, ocean water, glacial ice). We found both direct and relational associations contribute independently to inferred mappings. These results can be used to optimize visualization design to facilitate visual communication., Comment: To appear in IEEE Transactions on Visualization and Computer Graphics

In this article, we consider a cooperative control problem involving a heterogeneous network of dynamically decoupled continuous-time linear plants. The (output-feedback) controllers for each plant may communicate with each other according to a fixed and known transitively closed directed graph. Each transmission incurs a fixed and known time delay. We provide an explicit closed-form expression for the optimal decentralized controller and its associated cost under these communication constraints and standard linear quadratic Gaussian (LQG) assumptions for the plants and cost function. We find the exact solution without discretizing or otherwise approximating the delays. We also present an implementation of each sub-controller that is efficiently computable, and is composed of standard finite-dimensional linear time-invariant (LTI) and finite impulse response (FIR) components, and has an intuitive observer-regulator architecture reminiscent of the classical separation principle.

In the distributed optimization problem for a multi-agent system, each agent knows a local function and must find a minimizer of the sum of all agents' local functions by performing a combination of local gradient evaluations and communicating information with neighboring agents. We prove that every distributed optimization algorithm can be factored into a centralized optimization method and a second-order consensus estimator, effectively separating the "optimization" and "consensus" tasks. We illustrate this fact by providing the decomposition for many recently proposed distributed optimization algorithms. Conversely, we prove that any optimization method that converges in the centralized setting can be combined with any second-order consensus estimator to form a distributed optimization algorithm that converges in the multi-agent setting. Finally, we describe how our decomposition may lead to a more systematic algorithm design methodology.

Optimization problems in engineering and applied mathematics are typically solved in an iterative fashion, by systematically adjusting the variables of interest until an adequate solution is found. The iterative algorithms that govern these systematic adjustments can be viewed as a control system. In control systems, the output in measured and the input is adjusted using feedback to drive the error to zero. Similarly, in iterative algorithms, the optimization objective is evaluated and the candidate solution is adjusted to drive it toward the optimal point. Choosing an algorithm that works well for a variety of optimization problems is akin to robust controller design. Just as dissipativity theory can be used to analyze the stability properties of control systems, it can also be used to analyze the convergence properties of iterative algorithms. By defining an appropriate notion of "energy" that dissipates with every iteration of the algorithm, the convergence properties of the algorithm can be characterized. This article formalizes the connection between iterative algorithms and control systems and shows through examples how dissipativity theory can be used to analyze the performance of many classes of optimization algorithms. This control-theoretic viewpoint enables the selection and tuning of optimization algorithms to be performed in an automated and systematic way.

We study a partially observable nonlinear stochastic system with unknown parameters, where the given time scales of the states and measurements may be distinct. The proposed setting is inspired by disease management, particularly leukemia.

We study the trade-off between convergence rate and sensitivity to stochastic additive gradient noise for first-order optimization methods. Ordinary Gradient Descent (GD) can be made fast-and-sensitive or slow-and-robust by increasing or decreasing the stepsize, respectively. However, it is not clear how such a trade-off can be navigated when working with accelerated methods such as Polyak's Heavy Ball (HB) or Nesterov's Fast Gradient (FG) methods. We consider three classes of functions: (1) smooth strongly convex quadratics, (2) smooth strongly convex functions, and (3) functions that satisfy the Polyak-Lojasiewicz property and have one-sided Lipschitz gradients. For each function class, we present a tractable way to compute the convergence rate and sensitivity to additive gradient noise for a broad family of first-order methods, and we present algorithm designs that trade off these competing performance metrics. Each design consists of a simple analytic update rule with two states of memory, similar to HB and FG. Moreover, each design has a scalar tuning parameter that explicitly trades off convergence rate and sensitivity to additive gradient noise. We numerically validate the performance of our designs by comparing their convergence rate and sensitivity to those of many other algorithms, and through simulations on Nesterov's "bad function"., Comment: 45 pages

People's associations between colors and concepts influence their ability to interpret the meanings of colors in information visualizations. Previous work has suggested such effects are limited to concepts that have strong, specific associations with colors. However, although a concept may not be strongly associated with any colors, its mapping can be disambiguated in the context of other concepts in an encoding system. We articulate this view in semantic discriminability theory, a general framework for understanding conditions determining when people can infer meaning from perceptual features. Semantic discriminability is the degree to which observers can infer a unique mapping between visual features and concepts. Semantic discriminability theory posits that the capacity for semantic discriminability for a set of concepts is constrained by the difference between the feature-concept association distributions across the concepts in the set. We define formal properties of this theory and test its implications in two experiments. The results show that the capacity to produce semantically discriminable colors for sets of concepts was indeed constrained by the statistical distance between color-concept association distributions (Experiment 1). Moreover, people could interpret meanings of colors in bar graphs insofar as the colors were semantically discriminable, even for concepts previously considered "non-colorable" (Experiment 2). The results suggest that colors are more robust for visual communication than previously thought., Comment: Published in IEEE Transactions on Visualization and Computer Graphics

When are two algorithms the same? How can we be sure a recently proposed algorithm is novel, and not a minor twist on an existing method? In this paper, we present a framework for reasoning about equivalence between a broad class of iterative algorithms, with a focus on algorithms designed for convex optimization. We propose several notions of what it means for two algorithms to be equivalent, and provide computationally tractable means to detect equivalence. Our main definition, oracle equivalence, states that two algorithms are equivalent if they result in the same sequence of calls to the function oracles (for suitable initialization). Borrowing from control theory, we use state-space realizations to represent algorithms and characterize algorithm equivalence via transfer functions. Our framework can also identify and characterize some algorithm transformations including permutations of the update equations, repetition of the iteration, and conjugation of some of the function oracles in the algorithm. To support the paper, we have developed a software package named Linnaeus that implements the framework to identify other iterative algorithms that are equivalent to an input algorithm. More broadly, this framework and software advances the goal of making mathematics searchable., Comment: This paper documents a software system for identifying equivalence between optimization algorithms. The analysis in this paper has been improved in arxiv:2501.04972

We study a linear-quadratic, optimal control problem on a discrete, finite time horizon with distributional ambiguity, in which the cost is assessed via Conditional Value-at-Risk (CVaR). We take steps toward deriving a scalable dynamic programming approach to upper-bound the optimal value function for this problem. This dynamic program yields a novel, tunable risk-averse control policy, which we compare to existing state-of-the-art methods., Comment: This version of the article makes almost-everywhere notions explicit (Lemma 3, Theorem 2)

Smooth minimax games often proceed by simultaneous or alternating gradient updates. Although algorithms with alternating updates are commonly used in practice, the majority of existing theoretical analyses focus on simultaneous algorithms for convenience of analysis. In this paper, we study alternating gradient descent-ascent (Alt-GDA) in minimax games and show that Alt-GDA is superior to its simultaneous counterpart~(Sim-GDA) in many settings. We prove that Alt-GDA achieves a near-optimal local convergence rate for strongly convex-strongly concave (SCSC) problems while Sim-GDA converges at a much slower rate. To our knowledge, this is the \emph{first} result of any setting showing that Alt-GDA converges faster than Sim-GDA by more than a constant. We further adapt the theory of integral quadratic constraints (IQC) and show that Alt-GDA attains the same rate \emph{globally} for a subclass of SCSC minimax problems. Empirically, we demonstrate that alternating updates speed up GAN training significantly and the use of optimism only helps for simultaneous algorithms., Comment: AISTATS 2022

Classical sufficient conditions for ensuring the robust stability of a dynamical system in feedback with a nonlinearity include passivity, small gain, circle, and conicity theorems. We present a generalized version of these results for arbitrary semi-inner product spaces. Our result is purely algebraic, and holds even when the conventional discrete or continuous-time causal dynamical systems are replaced by general nonlinear relations, where there need not exist a notion of time. Our result clarifies when the sufficient conditions for robust stability are also necessary, and explains why stronger assumptions such as linearity and time-invariance are typically needed to prove necessity in the conventional dynamical systems setting.

The theory of integral quadratic constraints (IQCs) allows the certification of exponential convergence of interconnected systems containing nonlinear or uncertain elements. In this work, we adapt the IQC theory to study first-order methods for smooth and strongly-monotone games and show how to design tailored quadratic constraints to get tight upper bounds of convergence rates. Using this framework, we recover the existing bound for the gradient method~(GD), derive sharper bounds for the proximal point method~(PPM) and optimistic gradient method~(OG), and provide \emph{for the first time} a global convergence rate for the negative momentum method~(NM) with an iteration complexity $\mathcal{O}(\kappa^{1.5})$, which matches its known lower bound. In addition, for time-varying systems, we prove that the gradient method with optimal step size achieves the fastest provable worst-case convergence rate with quadratic Lyapunov functions. Finally, we further extend our analysis to stochastic games and study the impact of multiplicative noise on different algorithms. We show that it is impossible for an algorithm with one step of memory to achieve acceleration if it only queries the gradient once per batch (in contrast with the stochastic strongly-convex optimization setting, where such acceleration has been demonstrated). However, we exhibit an algorithm which achieves acceleration with two gradient queries per batch., Comment: Journal of Machine Learning Research

To interpret information visualizations, observers must determine how visual features map onto concepts. First and foremost, this ability depends on perceptual discriminability; e.g., observers must be able to see the difference between different colors for those colors to communicate different meanings. However, the ability to interpret visualizations also depends on semantic discriminability, the degree to which observers can infer a unique mapping between visual features and concepts, based on the visual features and concepts alone (i.e., without help from verbal cues such as legends or labels). Previous evidence suggested that observers were better at interpreting encoding systems that maximized semantic discriminability (maximizing association strength between assigned colors and concepts while minimizing association strength between unassigned colors and concepts), compared to a system that only maximized color-concept association strength. However, increasing semantic discriminability also resulted in increased perceptual distance, so it is unclear which factor was responsible for improved performance. In the present study, we conducted two experiments that tested for independent effects of semantic distance and perceptual distance on semantic discriminability of bar graph data visualizations. Perceptual distance was large enough to ensure colors were more than just noticeably different. We found that increasing semantic distance improved performance, independent of variation in perceptual distance, and when these two factors were uncorrelated, responses were dominated by semantic distance. These results have implications for navigating trade-offs in color palette design optimization for visual communication., Comment: To Appear in IEEE Transactions on Visualization and Computer Graphics

We consider the problem of controlling a set of dynamically decoupled plants where the plants' subcontrollers communicate with each other according to a fixed and known network topology. We assume the communication to be instantaneous but there is a fixed processing delay associated with incoming transmissions. We provide explicit closed-form expressions for the optimal decentralized controller under these communication constraints and using standard LQG assumptions for the plants and cost function. Although this problem is convex, it is challenging due to the irrationality of continuous-time delays and the decentralized information-sharing pattern. We show that the optimal subcontrollers each have an observer-regulator architecture containing LTI and FIR blocks and we characterize the signals that subcontrollers should transmit to each other across the network.

We consider the distributed optimization problem, where a group of agents work together to optimize a common objective by communicating with neighboring agents and performing local computations. For a given algorithm, we use tools from robust control to systematically analyze the performance in the case where the communication network is time-varying. In particular, we assume only that the network is jointly connected over a finite time horizon (commonly referred to as B-connectivity), which does not require connectivity at each time instant. When applied to the distributed algorithm DIGing, our bounds are orders of magnitude tighter than those available in the literature., Comment: 6 pages, CDC 2020

To interpret the meanings of colors in visualizations of categorical information, people must determine how distinct colors correspond to different concepts. This process is easier when assignments between colors and concepts in visualizations match people's expectations, making color palettes semantically interpretable. Efforts have been underway to optimize color palette design for semantic interpretablity, but this requires having good estimates of human color-concept associations. Obtaining these data from humans is costly, which motivates the need for automated methods. We developed and evaluated a new method for automatically estimating color-concept associations in a way that strongly correlates with human ratings. Building on prior studies using Google Images, our approach operates directly on Google Image search results without the need for humans in the loop. Specifically, we evaluated several methods for extracting raw pixel content of the images in order to best estimate color-concept associations obtained from human ratings. The most effective method extracted colors using a combination of cylindrical sectors and color categories in color space. We demonstrate that our approach can accurately estimate average human color-concept associations for different fruits using only a small set of images. The approach also generalizes moderately well to more complicated recycling-related concepts of objects that can appear in any color., Comment: IEEE VIS InfoVis 2019 ACM 2012 CSS: 1) Human-centered computing, Human computer interaction (HCI), Empirical studies in HCI 2) Human-centered computing, Human computer interaction (HCI), HCI design and evaluation methods, Laboratory experiments 3) Human-centered computing, Visualization, Empirical studies in visualization

This work concerns the analysis and design of distributed first-order optimization algorithms over time-varying graphs. The goal of such algorithms is to optimize a global function that is the average of local functions using only local computations and communications. Several different algorithms have been proposed that achieve linear convergence to the global optimum when the local functions are strongly convex. We provide a unified analysis that yields the worst-case linear convergence rate as a function of the condition number of the local functions, the spectral gap of the graph, and the parameters of the algorithm. The framework requires solving a small semidefinite program whose size is fixed; it does not depend on the number of local functions or the dimension of their domain. The result is a computationally efficient method for distributed algorithm analysis that enables the rapid comparison, selection, and tuning of algorithms. Finally, we propose a new algorithm, which we call SVL, that is easily implementable and achieves a faster worst-case convergence rate than all other known algorithms.

We consider a dynamically decoupled network of agents each with a local output-feedback controller. We assume each agent is a node in a directed acyclic graph and the controllers share information along the edges in order to cooperatively optimize a global objective. We develop explicit state-space formulations for the jointly optimal networked controllers that highlight the role of the graph structure. Specifically, we provide generically minimal agent-level implementations of the local controllers along with intuitive interpretations of their states and the information that should be transmitted between controllers., Comment: Published at IEEE Conference on Decision and Control, 2019

We propose an algorithm for distributed optimization over time-varying communication networks. Our algorithm uses an optimized ratio between the number of rounds of communication and gradient evaluations to achieve fast convergence. The iterates converge to the global optimizer at the same rate as centralized gradient descent when measured in terms of the number of gradient evaluations while using the minimum number of communications to do so. Furthermore, the iterates converge at a near-optimal rate when measured in terms of the number of communication rounds. We compare our algorithm with several other known algorithms on a distributed target localization problem., Comment: 6 pages

Iterative first-order methods such as gradient descent and its variants are widely used for solving optimization and machine learning problems. There has been recent interest in analytic or numerically efficient methods for computing worst-case performance bounds for such algorithms, for example over the class of strongly convex loss functions. A popular approach is to assume the algorithm has a fixed size (fixed dimension, or memory) and that its structure is parameterized by one or two hyperparameters, for example a learning rate and a momentum parameter. Then, a Lyapunov function is sought to certify robust stability and subsequent optimization can be performed to find optimal hyperparameter tunings. In the present work, we instead fix the constraints that characterize the loss function and apply techniques from robust control synthesis to directly search over algorithms. This approach yields stronger results than those previously available, since the bounds produced hold over algorithms with an arbitrary, but finite, amount of memory rather than just holding for algorithms with a prescribed structure., Comment: American Control Conference, 2020

We consider a linear time-invariant system in discrete time where the state and input signals satisfy a set of integral quadratic constraints (IQCs). Analogous to the autonomous linear systems case, we define a new notion of spectral radius that exactly characterizes stability of this system. In particular, (i) when the spectral radius is less than one, we show that the system is asymptotically stable for all trajectories that satisfy the IQCs, and (ii) when the spectral radius is equal to one, we construct an unstable trajectory that satisfies the IQCs. Furthermore, we connect our new definition of the spectral radius to the existing literature on IQCs., Comment: To appear in IEEE Conference on Decision and Control, 2019

We study data poisoning attacks in the online setting where training items arrive sequentially, and the attacker may perturb the current item to manipulate online learning. Importantly, the attacker has no knowledge of future training items nor the data generating distribution. We formulate online data poisoning attack as a stochastic optimal control problem, and solve it with model predictive control and deep reinforcement learning. We also upper bound the suboptimality suffered by the attacker for not knowing the data generating distribution. Experiments validate our control approach in generating near-optimal attacks on both supervised and unsupervised learning tasks.

Given a sequential learning algorithm and a target model, sequential machine teaching aims to find the shortest training sequence to drive the learning algorithm to the target model. We present the first principled way to find such shortest training sequences. Our key insight is to formulate sequential machine teaching as a time-optimal control problem. This allows us to solve sequential teaching by leveraging key theoretical and computational tools developed over the past 60 years in the optimal control community. Specifically, we study the Pontryagin Maximum Principle, which yields a necessary condition for optimality of a training sequence. We present analytic, structural, and numerical implications of this approach on a case study with a least-squares loss function and gradient descent learner. We compute optimal training sequences for this problem, and although the sequences seem circuitous, we find that they can vastly outperform the best available heuristics for generating training sequences.

Classical conditions for ensuring the robust stability of a linear system in feedback with a sector-bounded nonlinearity include small gain, circle, passivity, and conicity theorems. In this work, we present a similar stability condition, but expressed in terms of relations defined on a general semi-inner product space. This increased generality leads to a clean result that can be specialized in a variety of ways. First, we show how to recover both sufficient and necessary-and-sufficient versions of the aforementioned classical results. Second, we show that suitably choosing the semi-inner product space leads to a new necessary and sufficient condition for weighted stability, which is in turn sufficient for exponential stability., Comment: To appear in IEEE Conference on Decision and Control, 2019

We consider the distributed optimization problem in which a network of agents aims to minimize the average of local functions. To solve this problem, several algorithms have recently been proposed where agents perform various combinations of communication with neighbors, local gradient computations, and updates to local state variables. In this paper, we present a canonical form that characterizes any first-order distributed algorithm that can be implemented using a single round of communication and gradient computation per iteration, and where each agent stores up to two state variables. The canonical form features a minimal set of parameters that are both unique and expressive enough to capture any distributed algorithm in this class. The generic nature of our canonical form enables the systematic analysis and design of distributed optimization algorithms.

Techniques for reducing the variance of gradient estimates used in stochastic programming algorithms for convex finite-sum problems have received a great deal of attention in recent years. By leveraging dissipativity theory from control, we provide a new perspective on two important variance-reduction algorithms: SVRG and its direct accelerated variant Katyusha. Our perspective provides a physically intuitive understanding of the behavior of SVRG-like methods via a principle of energy conservation. The tools discussed here allow us to automate the convergence analysis of SVRG-like methods by capturing their essential properties in small semidefinite programs amenable to standard analysis and computational techniques. Our approach recovers existing convergence results for SVRG and Katyusha and generalizes the theory to alternative parameter choices. We also discuss how our approach complements the linear coupling technique. Our combination of perspectives leads to a better understanding of accelerated variance-reduced stochastic methods for finite-sum problems., Comment: to appear at ICML 2018

We present a novel way of generating Lyapunov functions for proving linear convergence rates of first-order optimization methods. Our approach provably obtains the fastest linear convergence rate that can be verified by a quadratic Lyapunov function (with given states), and only relies on solving a small-sized semidefinite program. Our approach combines the advantages of performance estimation problems (PEP, due to Drori & Teboulle (2014)) and integral quadratic constraints (IQC, due to Lessard et al. (2016)), and relies on convex interpolation (due to Taylor et al. (2017c;b))., Comment: to appear in ICML'18

We present a convergence rate analysis for biased stochastic gradient descent (SGD), where individual gradient updates are corrupted by computation errors. We develop stochastic quadratic constraints to formulate a small linear matrix inequality (LMI) whose feasible points lead to convergence bounds of biased SGD. Based on this LMI condition, we develop a sequential minimization approach to analyze the intricate trade-offs that couple stepsize selection, convergence rate, optimization accuracy, and robustness to gradient inaccuracy. We also provide feasible points for this LMI and obtain theoretical formulas that quantify the convergence properties of biased SGD under various assumptions on the loss functions., Comment: Accepted to Mathematical Programming

This work proposes an accelerated first-order algorithm we call the Robust Momentum Method for optimizing smooth strongly convex functions. The algorithm has a single scalar parameter that can be tuned to trade off robustness to gradient noise versus worst-case convergence rate. At one extreme, the algorithm is faster than Nesterov's Fast Gradient Method by a constant factor but more fragile to noise. At the other extreme, the algorithm reduces to the Gradient Method and is very robust to noise. The algorithm design technique is inspired by methods from classical control theory and the resulting algorithm has a simple analytical form. Algorithm performance is verified on a series of numerical simulations in both noise-free and relative gradient noise cases., Comment: to appear in proceedings of the American Control Conference, 2018

In this paper, we adapt the control theoretic concept of dissipativity theory to provide a natural understanding of Nesterov's accelerated method. Our theory ties rigorous convergence rate analysis to the physically intuitive notion of energy dissipation. Moreover, dissipativity allows one to efficiently construct Lyapunov functions (either numerically or analytically) by solving a small semidefinite program. Using novel supply rate functions, we show how to recover known rate bounds for Nesterov's method and we generalize the approach to certify both linear and sublinear rates in a variety of settings. Finally, we link the continuous-time version of dissipativity to recent works on algorithm analysis that use discretizations of ordinary differential equations., Comment: to appear in the International Conference on Machine Learning 2017

The theory of integral quadratic constraints (IQCs) allows verification of stability and gain-bound properties of systems containing nonlinear or uncertain elements. Gain bounds often imply exponential stability, but it can be challenging to compute useful numerical bounds on the exponential decay rate. This work presents a generalization of the classical IQC results of Megretski and Rantzer that leads to a tractable computational procedure for finding exponential rate certificates that are far less conservative than ones computed from $L_2$ gain bounds alone. An expanded library of IQCs for certifying exponential stability is also provided and the effectiveness of the technique is demonstrated via numerical examples., Comment: arXiv admin note: text overlap with arXiv:1503.07222

First-order iterative optimization methods play a fundamental role in large scale optimization and machine learning. This paper presents control interpretations for such optimization methods. First, we give loop-shaping interpretations for several existing optimization methods and show that they are composed of basic control elements such as PID and lag compensators. Next, we apply the small gain theorem to draw a connection between the convergence rate analysis of optimization methods and the input-output gain computations of certain complementary sensitivity functions. These connections suggest that standard classical control synthesis tools may be brought to bear on the design of optimization algorithms., Comment: To appear, American Control Conference 2017

To see color, the human visual system combines the response of three types of cone cells in the retina--a compressive process that discards a significant amount of spectral information. Here, we present an approach to enhance human color vision by breaking its inherent binocular redundancy, providing different spectral content to each eye. We fabricated a set of optical filters that "splits" the response of the short-wavelength cone between the two eyes in individuals with typical trichromatic vision, simulating the presence of approximately four distinct cone types ("tetrachromacy"). Such an increase in the number of effective cone types can reduce the prevalence of metamers--pairs of distinct spectra that resolve to the same tristimulus values. This technique may result in an enhancement of spectral perception, with applications ranging from camouflage detection and anti-counterfeiting to new types of artwork and data visualization., Comment: Main text and supplementary info

The theory of integral quadratic constraints (IQCs) allows verification of stability and gain-bound properties of systems containing nonlinear or uncertain elements. Gain bounds often imply exponential stability, but it can be challenging to compute useful numerical bounds on the exponential decay rate. In this work, we present a modification of the classical IQC results of Megretski and Rantzer that leads to a tractable computational procedure for finding exponential rate certificates.

We provide a new proof of the linear convergence of the alternating direction method of multipliers (ADMM) when one of the objective terms is strongly convex. Our proof is based on a framework for analyzing optimization algorithms introduced in Lessard et al. (2014), reducing algorithm convergence to verifying the stability of a dynamical system. This approach generalizes a number of existing results and obviates any assumptions about specific choices of algorithm parameters. On a numerical example, we demonstrate that minimizing the derived bound on the convergence rate provides a practical approach to selecting algorithm parameters for particular ADMM instances. We complement our upper bound by constructing a nearly-matching lower bound on the worst-case rate of convergence., Comment: 10 pages, 6 figures