-
Spectral Recovery in the Labeled SBM
Authors:
Julia Gaudio,
Heming Liu
Abstract:
We consider the problem of exact community recovery in the Labeled Stochastic Block Model (LSBM) with $k$ communities, where each pair of vertices is associated with a label from the set $\{0,1, \dots, L\}$. A pair of vertices from communities $i,j$ is given label $\ell$ with probability $p_{ij}^{(\ell)}$, and the goal is to recover the community partition. We propose a simple spectral algorithm f…
▽ More
We consider the problem of exact community recovery in the Labeled Stochastic Block Model (LSBM) with $k$ communities, where each pair of vertices is associated with a label from the set $\{0,1, \dots, L\}$. A pair of vertices from communities $i,j$ is given label $\ell$ with probability $p_{ij}^{(\ell)}$, and the goal is to recover the community partition. We propose a simple spectral algorithm for exact community recovery, and show that it achieves the information-theoretic threshold in the logarithmic-degree regime, under the assumption that the eigenvalues of certain parameter matrices are distinct and nonzero. Our results generalize recent work of Dhara, Gaudio, Mossel, and Sandon (2023), who showed that a spectral algorithm achieves the information-theoretic threshold in the Censored SBM, which is equivalent to the LSBM with $L = 2$. Interestingly, their algorithm uses eigenvectors from two matrix representations of the graph, while our algorithm uses eigenvectors from $L$ matrices.
△ Less
Submitted 23 August, 2024;
originally announced August 2024.
-
Exact Label Recovery in Euclidean Random Graphs
Authors:
Julia Gaudio,
Charlie Guan,
Xiaochun Niu,
Ermin Wei
Abstract:
In this paper, we propose a family of label recovery problems on weighted Euclidean random graphs. The vertices of a graph are embedded in $\mathbb{R}^d$ according to a Poisson point process, and are assigned to a discrete community label. Our goal is to infer the vertex labels, given edge weights whose distributions depend on the vertex labels as well as their geometric positions. Our general mod…
▽ More
In this paper, we propose a family of label recovery problems on weighted Euclidean random graphs. The vertices of a graph are embedded in $\mathbb{R}^d$ according to a Poisson point process, and are assigned to a discrete community label. Our goal is to infer the vertex labels, given edge weights whose distributions depend on the vertex labels as well as their geometric positions. Our general model provides a geometric extension of popular graph and matrix problems, including submatrix localization and $\mathbb{Z}_2$-synchronization, and includes the Geometric Stochastic Block Model (proposed by Sankararaman and Baccelli) as a special case. We study the fundamental limits of exact recovery of the vertex labels. Under a mild distinctness of distributions assumption, we determine the information-theoretic threshold for exact label recovery, in terms of a Chernoff-Hellinger divergence criterion. Impossibility of recovery below the threshold is proven by a unified analysis using a Cramér lower bound. Achievability above the threshold is proven via an efficient two-phase algorithm, where the first phase computes an almost-exact labeling through a local propagation scheme, while the second phase refines the labels. The information-theoretic threshold is dictated by the performance of the so-called genie estimator, which decodes the label of a single vertex given all the other labels. This shows that our proposed models exhibit the local-to-global amplification phenomenon.
△ Less
Submitted 15 July, 2024;
originally announced July 2024.
-
Exact Community Recovery (under Side Information): Optimality of Spectral Algorithms
Authors:
Julia Gaudio,
Nirmit Joshi
Abstract:
In this paper, we study the problem of exact community recovery in general, two-community block models considering both Bernoulli and Gaussian matrix models, capturing the Stochastic Block Model, submatrix localization, and $\mathbb{Z}_2$-synchronization as special cases. We also study the settings where $side$ $information$ about community assignment labels is available, modeled as passing the tr…
▽ More
In this paper, we study the problem of exact community recovery in general, two-community block models considering both Bernoulli and Gaussian matrix models, capturing the Stochastic Block Model, submatrix localization, and $\mathbb{Z}_2$-synchronization as special cases. We also study the settings where $side$ $information$ about community assignment labels is available, modeled as passing the true labels through a noisy channel: either the binary erasure channel (where some community labels are known while others are erased) or the binary symmetric channel (where some labels are flipped). We provide a unified analysis of the effect of side information on the information-theoretic limits of exact recovery, generalizing prior works and extending to new settings. Additionally, we design a simple but optimal spectral algorithm that incorporates side information (when present) along with the eigenvectors of the matrix observation. Using the powerful tool of entrywise eigenvector analysis [Abbe, Fan, Wang, Zhong 2020], we show that our spectral algorithm can mimic the so called $genie$-$aided$ $estimators$, where the $i^{\mathrm{th}}$ genie-aided estimator optimally computes the estimate of the $i^{\mathrm{th}}$ label, when all remaining labels are revealed by a genie. This perspective provides a unified understanding of the optimality of spectral algorithms for various exact recovery problems in a recent line of work.
△ Less
Submitted 18 June, 2024;
originally announced June 2024.
-
On the stability of second order gradient descent for time varying convex functions
Authors:
Travis E. Gibson,
Sawal Acharya,
Anjali Parashar,
Joseph E. Gaudio,
Anurdha M. Annaswamy
Abstract:
Gradient based optimization algorithms deployed in Machine Learning (ML) applications are often analyzed and compared by their convergence rates or regret bounds. While these rates and bounds convey valuable information they don't always directly translate to stability guarantees. Stability and similar concepts, like robustness, will become ever more important as we move towards deploying models i…
▽ More
Gradient based optimization algorithms deployed in Machine Learning (ML) applications are often analyzed and compared by their convergence rates or regret bounds. While these rates and bounds convey valuable information they don't always directly translate to stability guarantees. Stability and similar concepts, like robustness, will become ever more important as we move towards deploying models in real-time and safety critical systems. In this work we build upon the results in Gaudio et al. 2021 and Moreu and Annaswamy 2022 for second order gradient descent when applied to explicitly time varying cost functions and provide more general stability guarantees. These more general results can aid in the design and certification of these optimization schemes so as to help ensure safe and reliable deployment for real-time learning applications. We also hope that the techniques provided here will stimulate and cross-fertilize the analysis that occurs on the same algorithms from the online learning and stochastic optimization communities.
△ Less
Submitted 22 May, 2024;
originally announced May 2024.
-
Exact Community Recovery in the Geometric SBM
Authors:
Julia Gaudio,
Xiaochun Niu,
Ermin Wei
Abstract:
We study the problem of exact community recovery in the Geometric Stochastic Block Model (GSBM), where each vertex has an unknown community label as well as a known position, generated according to a Poisson point process in $\mathbb{R}^d$. Edges are formed independently conditioned on the community labels and positions, where vertices may only be connected by an edge if they are within a prescrib…
▽ More
We study the problem of exact community recovery in the Geometric Stochastic Block Model (GSBM), where each vertex has an unknown community label as well as a known position, generated according to a Poisson point process in $\mathbb{R}^d$. Edges are formed independently conditioned on the community labels and positions, where vertices may only be connected by an edge if they are within a prescribed distance of each other. The GSBM thus favors the formation of dense local subgraphs, which commonly occur in real-world networks, a property that makes the GSBM qualitatively very different from the standard Stochastic Block Model (SBM). We propose a linear-time algorithm for exact community recovery, which succeeds down to the information-theoretic threshold, confirming a conjecture of Abbe, Baccelli, and Sankararaman. The algorithm involves two phases. The first phase exploits the density of local subgraphs to propagate estimated community labels among sufficiently occupied subregions, and produces an almost-exact vertex labeling. The second phase then refines the initial labels using a Poisson testing procedure. Thus, the GSBM enjoys local to global amplification just as the SBM, with the advantage of admitting an information-theoretically optimal, linear-time algorithm.
△ Less
Submitted 5 January, 2024; v1 submitted 20 July, 2023;
originally announced July 2023.
-
Average-case and smoothed analysis of graph isomorphism
Authors:
Julia Gaudio,
Miklós Z. Rácz,
Anirudh Sridhar
Abstract:
We propose a simple and efficient local algorithm for graph isomorphism which succeeds for a large class of sparse graphs. This algorithm produces a low-depth canonical labeling, which is a labeling of the vertices of the graph that identifies its isomorphism class using vertices' local neighborhoods.
Prior work by Czajka and Pandurangan showed that the degree profile of a vertex (i.e., the sort…
▽ More
We propose a simple and efficient local algorithm for graph isomorphism which succeeds for a large class of sparse graphs. This algorithm produces a low-depth canonical labeling, which is a labeling of the vertices of the graph that identifies its isomorphism class using vertices' local neighborhoods.
Prior work by Czajka and Pandurangan showed that the degree profile of a vertex (i.e., the sorted list of the degrees of its neighbors) gives a canonical labeling with high probability when $n p_n = ω( \log^{4}(n) / \log \log n )$ (and $p_{n} \leq 1/2$); subsequently, Mossel and Ross showed that the same holds when $n p_n = ω( \log^{2}(n) )$. We first show that their analysis essentially cannot be improved: we prove that when $n p_n = o( \log^{2}(n) / (\log \log n)^{3} )$, with high probability there exist distinct vertices with isomorphic $2$-neighborhoods. Our first main result is a positive counterpart to this, showing that $3$-neighborhoods give a canonical labeling when $n p_n \geq (1+δ) \log n$ (and $p_n \leq 1/2$); this improves a recent result of Ding, Ma, Wu, and Xu, completing the picture above the connectivity threshold.
Our second main result is a smoothed analysis of graph isomorphism, showing that for a large class of deterministic graphs, a small random perturbation ensures that $3$-neighborhoods give a canonical labeling with high probability. While the worst-case complexity of graph isomorphism is still unknown, this shows that graph isomorphism has polynomial smoothed complexity.
△ Less
Submitted 18 September, 2023; v1 submitted 29 November, 2022;
originally announced November 2022.
-
Joint Facility and Demand Location Problem
Authors:
Ali Kaan Kurbanzade,
Julia Gaudio
Abstract:
In typical applications of facility location problems, the location of demand is assumed to be an input to the problem. The demand may be fixed or dynamic, but ultimately outside the optimizers control. In contrast, there are settings, especially in humanitarian contexts, in which the optimizer decides where to locate a demand node. In this work, we introduce an optimization framework for joint fa…
▽ More
In typical applications of facility location problems, the location of demand is assumed to be an input to the problem. The demand may be fixed or dynamic, but ultimately outside the optimizers control. In contrast, there are settings, especially in humanitarian contexts, in which the optimizer decides where to locate a demand node. In this work, we introduce an optimization framework for joint facility and demand location. As examples of our general framework, we extend the well-known k-median and k-center problems into joint facility and demand location problems (JFDLP) and formulate them as integer programs. We propose a local search heuristic based on network flow. We apply our heuristic to a hurricane evacuation response case study. Our results demonstrate the challenging nature of these simultaneous optimization problems, especially when there are many potential locations. The local search heuristic is most promising when the the number of potential locations is large, while the number of facility and demand nodes to be located is small.
△ Less
Submitted 22 November, 2022;
originally announced November 2022.
-
The Power of Two Matrices in Spectral Algorithms
Authors:
Souvik Dhara,
Julia Gaudio,
Elchanan Mossel,
Colin Sandon
Abstract:
Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms have been successfully used for graph partitioning, hidden clique recovery and graph coloring. In this paper, we study the power of spectral alg…
▽ More
Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms have been successfully used for graph partitioning, hidden clique recovery and graph coloring. In this paper, we study the power of spectral algorithms using two matrices in a graph partitioning problem. We use two different matrices resulting from two different encodings of the same graph and then combine the spectral information coming from these two matrices.
We analyze a two-matrix spectral algorithm for the problem of identifying latent community structure in large random graphs. In particular, we consider the problem of recovering community assignments exactly in the censored stochastic block model, where each edge status is revealed independently with some probability. We show that spectral algorithms based on two matrices are optimal and succeed in recovering communities up to the information theoretic threshold. On the other hand, we show that for most choices of the parameters, any spectral algorithm based on one matrix is suboptimal. This is in contrast to our prior works (2022a, 2022b) which showed that for the symmetric Stochastic Block Model and the Planted Dense Subgraph problem, a spectral algorithm based on one matrix achieves the information theoretic threshold. We additionally provide more general geometric conditions for the (sub)-optimality of spectral algorithms.
△ Less
Submitted 7 March, 2023; v1 submitted 11 October, 2022;
originally announced October 2022.
-
Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix
Authors:
Julia Gaudio,
Nirmit Joshi
Abstract:
Community detection is a fundamental problem in network science. In this paper, we consider community detection in hypergraphs drawn from the $hypergraph$ $stochastic$ $block$ $model$ (HSBM), with a focus on exact community recovery. We study the performance of polynomial-time algorithms which operate on the $similarity$ $matrix$ $W$, where $W_{ij}$ reports the number of hyperedges containing both…
▽ More
Community detection is a fundamental problem in network science. In this paper, we consider community detection in hypergraphs drawn from the $hypergraph$ $stochastic$ $block$ $model$ (HSBM), with a focus on exact community recovery. We study the performance of polynomial-time algorithms which operate on the $similarity$ $matrix$ $W$, where $W_{ij}$ reports the number of hyperedges containing both $i$ and $j$. Under this information model, while the precise information-theoretic limit is unknown, Kim, Bandeira, and Goemans derived a sharp threshold up to which the natural min-bisection estimator on $W$ succeeds. As min-bisection is NP-hard in the worst case, they additionally proposed a semidefinite programming (SDP) relaxation and conjectured that it achieves the same recovery threshold as the min-bisection estimator.
In this paper, we confirm this conjecture. We also design a simple and highly efficient spectral algorithm with nearly linear runtime and show that it achieves the min-bisection threshold. Moreover, the spectral algorithm also succeeds in denser regimes and is considerably more efficient than previous approaches, establishing it as the method of choice. Our analysis of the spectral algorithm crucially relies on strong $entrywise$ bounds on the eigenvectors of $W$. Our bounds are inspired by the work of Abbe, Fan, Wang, and Zhong, who developed entrywise bounds for eigenvectors of symmetric matrices with independent entries. Despite the complex dependency structure in similarity matrices, we prove similar entrywise guarantees.
△ Less
Submitted 14 October, 2023; v1 submitted 23 August, 2022;
originally announced August 2022.
-
Exact Community Recovery in Correlated Stochastic Block Models
Authors:
Julia Gaudio,
Miklos Z. Racz,
Anirudh Sridhar
Abstract:
We consider the problem of learning latent community structure from multiple correlated networks. We study edge-correlated stochastic block models with two balanced communities, focusing on the regime where the average degree is logarithmic in the number of vertices. Our main result derives the precise information-theoretic threshold for exact community recovery using multiple correlated graphs. T…
▽ More
We consider the problem of learning latent community structure from multiple correlated networks. We study edge-correlated stochastic block models with two balanced communities, focusing on the regime where the average degree is logarithmic in the number of vertices. Our main result derives the precise information-theoretic threshold for exact community recovery using multiple correlated graphs. This threshold captures the interplay between the community recovery and graph matching tasks. In particular, we uncover and characterize a region of the parameter space where exact community recovery is possible using multiple correlated graphs, even though (1) this is information-theoretically impossible using a single graph and (2) exact graph matching is also information-theoretically impossible. In this regime, we develop a novel algorithm that carefully synthesizes algorithms from the community recovery and graph matching literatures.
△ Less
Submitted 29 March, 2022;
originally announced March 2022.
-
Spectral Algorithms Optimally Recover Planted Sub-structures
Authors:
Souvik Dhara,
Julia Gaudio,
Elchanan Mossel,
Colin Sandon
Abstract:
Spectral algorithms are an important building block in machine learning and graph algorithms. We are interested in studying when such algorithms can be applied directly to provide optimal solutions to inference tasks. Previous works by Abbe, Fan, Wang and Zhong (2020) and by Dhara, Gaudio, Mossel and Sandon (2022) showed the optimality for community detection in the Stochastic Block Model (SBM), a…
▽ More
Spectral algorithms are an important building block in machine learning and graph algorithms. We are interested in studying when such algorithms can be applied directly to provide optimal solutions to inference tasks. Previous works by Abbe, Fan, Wang and Zhong (2020) and by Dhara, Gaudio, Mossel and Sandon (2022) showed the optimality for community detection in the Stochastic Block Model (SBM), as well as in a censored variant of the SBM. Here we show that this optimality is somewhat universal as it carries over to other planted substructures such as the planted dense subgraph problem and submatrix localization problem, as well as to a censored version of the planted dense subgraph problem.
△ Less
Submitted 11 October, 2022; v1 submitted 22 March, 2022;
originally announced March 2022.
-
Inhalation and deposition of spherical and pollen particles after middle turbinate resection in a human nasal cavity
Authors:
Kiao Inthavong,
Yidan Shang,
John M. Del Gaudio,
Sarah K. Wise,
Thomas S. Edwards,
Kimberley Bradshaw,
Eugene Wong,
Murray Smith,
Narinder Singh
Abstract:
Middle turbinate resection significantly alters the anatomy and redistributes the inhaled air. The superior half of the main nasal cavity is opened up, increasing accessibility to the region. This is expected to increase inhalation dosimetry to the region during exposure to airborne particles. This study investigated the influence of middle turbinate resection on the deposition of inhaled pollutan…
▽ More
Middle turbinate resection significantly alters the anatomy and redistributes the inhaled air. The superior half of the main nasal cavity is opened up, increasing accessibility to the region. This is expected to increase inhalation dosimetry to the region during exposure to airborne particles. This study investigated the influence of middle turbinate resection on the deposition of inhaled pollutants that cover spherical and non-spherical particles (e.g. pollen). A computational model of the nasal cavity from CT scans, and its corresponding post-operative model with virtual surgery performed was created. Two constant flow rates of 5_L/min, and 15_L/min were simulated under a laminar flow field. Inhaled particles including pollen (non-spherical), and a spherical particle with reference density of 1000 kg/m3 were introduced in the surrounding atmosphere. The effect of surgery was most prominent in the less patent cavity side, since the change in anatomy was proportionally greater relative to the original airway space. The left cavity produced an increase in particle deposition at a flow rate of 15_L/min. The main particle deposition mechanisms were inertial impaction, and to a lesser degree gravitational sedimentation. The results are expected to provide insight into inhalation efficiency of different aerosol types, and the likelihood of deposition in different nasal cavity surfaces.
△ Less
Submitted 8 August, 2021;
originally announced August 2021.
-
Spectral Recovery of Binary Censored Block Models
Authors:
Souvik Dhara,
Julia Gaudio,
Elchanan Mossel,
Colin Sandon
Abstract:
Community detection is the problem of identifying community structure in graphs. Often the graph is modeled as a sample from the Stochastic Block Model, in which each vertex belongs to a community. The probability that two vertices are connected by an edge depends on the communities of those vertices. In this paper, we consider a model of {\em censored} community detection with two communities, wh…
▽ More
Community detection is the problem of identifying community structure in graphs. Often the graph is modeled as a sample from the Stochastic Block Model, in which each vertex belongs to a community. The probability that two vertices are connected by an edge depends on the communities of those vertices. In this paper, we consider a model of {\em censored} community detection with two communities, where most of the data is missing as the status of only a small fraction of the potential edges is revealed. In this model, vertices in the same community are connected with probability $p$ while vertices in opposite communities are connected with probability $q$. The connectivity status of a given pair of vertices $\{u,v\}$ is revealed with probability $α$, independently across all pairs, where $α= \frac{t \log(n)}{n}$. We establish the information-theoretic threshold $t_c(p,q)$, such that no algorithm succeeds in recovering the communities exactly when $t < t_c(p,q)$. We show that when $t > t_c(p,q)$, a simple spectral algorithm based on a weighted, signed adjacency matrix succeeds in recovering the communities exactly.
While spectral algorithms are shown to have near-optimal performance in the symmetric case, we show that they may fail in the asymmetric case where the connection probabilities inside the two communities are allowed to be different. In particular, we show the existence of a parameter regime where a simple two-phase algorithm succeeds but any algorithm based on the top two eigenvectors of the weighted, signed adjacency matrix fails.
△ Less
Submitted 10 November, 2021; v1 submitted 13 July, 2021;
originally announced July 2021.
-
Online Algorithms and Policies Using Adaptive and Machine Learning Approaches
Authors:
Anuradha M. Annaswamy,
Anubhav Guha,
Yingnan Cui,
Sunbochen Tang,
Peter A. Fisher,
Joseph E. Gaudio
Abstract:
This paper considers the problem of real-time control and learning in dynamic systems subjected to parametric uncertainties. We propose a combination of a Reinforcement Learning (RL) based policy in the outer loop suitably chosen to ensure stability and optimality for the nominal dynamics, together with Adaptive Control (AC) in the inner loop so that in real-time AC contracts the closed-loop dynam…
▽ More
This paper considers the problem of real-time control and learning in dynamic systems subjected to parametric uncertainties. We propose a combination of a Reinforcement Learning (RL) based policy in the outer loop suitably chosen to ensure stability and optimality for the nominal dynamics, together with Adaptive Control (AC) in the inner loop so that in real-time AC contracts the closed-loop dynamics towards a stable trajectory traced out by RL. Two classes of nonlinear dynamic systems are considered, both of which are control-affine. The first class of dynamic systems utilizes equilibrium points %with expansion forms around these points and a Lyapunov approach while second class of nonlinear systems uses contraction theory. AC-RL controllers are proposed for both classes of systems and shown to lead to online policies that guarantee stability using a high-order tuner and accommodate parametric uncertainties and magnitude limits on the input. In addition to establishing a stability guarantee with real-time control, the AC-RL controller is also shown to lead to parameter learning with persistent excitation for the first class of systems. Numerical validations of all algorithms are carried out using a quadrotor landing task on a moving platform.
△ Less
Submitted 9 June, 2023; v1 submitted 13 May, 2021;
originally announced May 2021.
-
New Algorithms for Discrete-Time Parameter Estimation
Authors:
Yingnan Cui,
Joseph E. Gaudio,
Anuradha M. Annaswamy
Abstract:
We propose two algorithms for discrete-time parameter estimation, one for time-varying parameters under persistent excitation (PE) condition, another for constant parameters under no PE condition. For the first algorithm, we show that in the presence of time-varying unknown parameters, the parameter estimation error converges uniformly to a compact set under conditions of persistent excitation, wi…
▽ More
We propose two algorithms for discrete-time parameter estimation, one for time-varying parameters under persistent excitation (PE) condition, another for constant parameters under no PE condition. For the first algorithm, we show that in the presence of time-varying unknown parameters, the parameter estimation error converges uniformly to a compact set under conditions of persistent excitation, with the size of the compact set proportional to the time-variation of unknown parameters. Leveraging a projection operator, the second algorithm is shown to result in boundedness guarantees when the plant has constant unknown parameters. Simulations show better convergence results compared to recursive least squares (RLS) and comparable results to RLS with forgetting factor.
△ Less
Submitted 14 March, 2022; v1 submitted 30 March, 2021;
originally announced March 2021.
-
A High-order Tuner for Accelerated Learning and Control
Authors:
Spencer McDonald,
Yingnan Cui,
Joseph E. Gaudio,
Anuradha M. Annaswamy
Abstract:
Gradient-descent based iterative algorithms pervade a variety of problems in estimation, prediction, learning, control, and optimization. Recently iterative algorithms based on higher-order information have been explored in an attempt to lead to accelerated learning. In this paper, we explore a specific a high-order tuner that has been shown to result in stability with time-varying regressors in l…
▽ More
Gradient-descent based iterative algorithms pervade a variety of problems in estimation, prediction, learning, control, and optimization. Recently iterative algorithms based on higher-order information have been explored in an attempt to lead to accelerated learning. In this paper, we explore a specific a high-order tuner that has been shown to result in stability with time-varying regressors in linearly parametrized systems, and accelerated convergence with constant regressors. We show that this tuner continues to provide bounded parameter estimates even if the gradients are corrupted by noise. Additionally, we also show that the parameter estimates converge exponentially to a compact set whose size is dependent on noise statistics. As the HT algorithms can be applied to a wide range of problems in estimation, filtering, control, and machine learning, the result obtained in this paper represents an important extension to the topic of real-time and fast decision making.
△ Less
Submitted 23 March, 2021;
originally announced March 2021.
-
Shotgun Assembly of Erdos-Renyi Random Graphs
Authors:
Julia Gaudio,
Elchanan Mossel
Abstract:
Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. In this paper, we consider shotgun assembly of \ER random graphs $G(n, p_n)$, where $p_n = n^{-α}$ for $0 < α< 1$. We consider both reconstruction up to isomorphism as well as exact reconstruction (recovering the vertex labels as well as the structure). We show that given the collection…
▽ More
Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. In this paper, we consider shotgun assembly of \ER random graphs $G(n, p_n)$, where $p_n = n^{-α}$ for $0 < α< 1$. We consider both reconstruction up to isomorphism as well as exact reconstruction (recovering the vertex labels as well as the structure). We show that given the collection of distance-$1$ neighborhoods, $G$ is exactly reconstructable for $0 < α< \frac{1}{3}$, but not reconstructable for $\frac{1}{2} < α< 1$. Given the collection of distance-$2$ neighborhoods, $G$ is exactly reconstructable for $α\in \left(0, \frac{1}{2}\right) \cup \left(\frac{1}{2}, \frac{3}{5}\right)$, but not reconstructable for $\frac{3}{4} < α< 1$.
△ Less
Submitted 12 January, 2022; v1 submitted 27 October, 2020;
originally announced October 2020.
-
A large deviation principle for block models
Authors:
Christian Borgs,
Jennifer Chayes,
Julia Gaudio,
Samantha Petti,
Subhabrata Sen
Abstract:
We initiate a study of large deviations for block model random graphs in the dense regime. Following Chatterjee-Varadhan(2011), we establish an LDP for dense block models, viewed as random graphons. As an application of our result, we study upper tail large deviations for homomorphism densities of regular graphs. We identify the existence of a "symmetric" phase, where the graph, conditioned on the…
▽ More
We initiate a study of large deviations for block model random graphs in the dense regime. Following Chatterjee-Varadhan(2011), we establish an LDP for dense block models, viewed as random graphons. As an application of our result, we study upper tail large deviations for homomorphism densities of regular graphs. We identify the existence of a "symmetric" phase, where the graph, conditioned on the rare event, looks like a block model with the same block sizes as the generating graphon. In specific examples, we also identify the existence of a "symmetry breaking" regime, where the conditional structure is not a block model with compatible dimensions. This identifies a "reentrant phase transition" phenomenon for this problem---analogous to one established for Erdos-Renyi random graphs (Chatterjee-Dey(2010), Chatterjee-Varadhan(2011)). Finally, extending the analysis of Lubetzky-Zhao(2015), we identify the precise boundary between the symmetry and symmetry breaking regime for homomorphism densities of regular graphs and the operator norm on Erdos-Renyi bipartite graphs.
△ Less
Submitted 28 July, 2020;
originally announced July 2020.
-
Accurate Parameter Estimation for Risk-aware Autonomous Systems
Authors:
Arnab Sarker,
Peter Fisher,
Joseph E. Gaudio,
Anuradha M. Annaswamy
Abstract:
Analysis and synthesis of safety-critical autonomous systems are carried out using models which are often dynamic. Two central features of these dynamic systems are parameters and unmodeled dynamics. This paper addresses the use of a spectral lines-based approach for estimating parameters of the dynamic model of an autonomous system. Existing literature has treated all unmodeled components of the…
▽ More
Analysis and synthesis of safety-critical autonomous systems are carried out using models which are often dynamic. Two central features of these dynamic systems are parameters and unmodeled dynamics. This paper addresses the use of a spectral lines-based approach for estimating parameters of the dynamic model of an autonomous system. Existing literature has treated all unmodeled components of the dynamic system as sub-Gaussian noise and proposed parameter estimation using Gaussian noise-based exogenous signals. In contrast, we allow the unmodeled part to have deterministic unmodeled dynamics, which are almost always present in physical systems, in addition to sub-Gaussian noise. In addition, we propose a deterministic construction of the exogenous signal in order to carry out parameter estimation. We introduce a new tool kit which employs the theory of spectral lines, retains the stochastic setting, and leads to non-asymptotic bounds on the parameter estimation error. Unlike the existing stochastic approach, these bounds are tunable through an optimal choice of the spectrum of the exogenous signal leading to accurate parameter estimation. We also show that this estimation is robust to unmodeled dynamics, a property that is not assured by the existing approach. Finally, we show that under ideal conditions with no unmodeled dynamics, the proposed approach can ensure a $\tilde{O}(\sqrt{T})$ regret, matching existing literature. Experiments are provided to support all theoretical derivations, which show that the spectral lines-based approach outperforms the Gaussian noise-based method when unmodeled dynamics are present, in terms of both parameter estimation error and Regret obtained using the parameter estimates with a Linear Quadratic Regulator in feedback.
△ Less
Submitted 16 March, 2022; v1 submitted 22 June, 2020;
originally announced June 2020.
-
Estimation of Monotone Multi-Index Models
Authors:
David Gamarnik,
Julia Gaudio
Abstract:
In a multi-index model with $k$ index vectors, the input variables are transformed by taking inner products with the index vectors. A transfer function $f: \mathbb{R}^k \to \mathbb{R}$ is applied to these inner products to generate the output. Thus, multi-index models are a generalization of linear models. In this paper, we consider monotone multi-index models. Namely, the transfer function is ass…
▽ More
In a multi-index model with $k$ index vectors, the input variables are transformed by taking inner products with the index vectors. A transfer function $f: \mathbb{R}^k \to \mathbb{R}$ is applied to these inner products to generate the output. Thus, multi-index models are a generalization of linear models. In this paper, we consider monotone multi-index models. Namely, the transfer function is assumed to be coordinate-wise monotone. The monotone multi-index model therefore generalizes both linear regression and isotonic regression, which is the estimation of a coordinate-wise monotone function. We consider the case of nonnegative index vectors. We provide an algorithm based on integer programming for the estimation of monotone multi-index models, and provide guarantees on the $L_2$ loss of the estimated function relative to the ground truth.
△ Less
Submitted 4 June, 2020;
originally announced June 2020.
-
Accelerated Learning with Robustness to Adversarial Regressors
Authors:
Joseph E. Gaudio,
Anuradha M. Annaswamy,
José M. Moreu,
Michael A. Bolender,
Travis E. Gibson
Abstract:
High order momentum-based parameter update algorithms have seen widespread applications in training machine learning models. Recently, connections with variational approaches have led to the derivation of new learning algorithms with accelerated learning guarantees. Such methods however, have only considered the case of static regressors. There is a significant need for parameter update algorithms…
▽ More
High order momentum-based parameter update algorithms have seen widespread applications in training machine learning models. Recently, connections with variational approaches have led to the derivation of new learning algorithms with accelerated learning guarantees. Such methods however, have only considered the case of static regressors. There is a significant need for parameter update algorithms which can be proven stable in the presence of adversarial time-varying regressors, as is commonplace in control theory. In this paper, we propose a new discrete time algorithm which 1) provides stability and asymptotic convergence guarantees in the presence of adversarial regressors by leveraging insights from adaptive control theory and 2) provides non-asymptotic accelerated learning guarantees leveraging insights from convex optimization. In particular, our algorithm reaches an $ε$ sub-optimal point in at most $\tilde{\mathcal{O}}(1/\sqrtε)$ iterations when regressors are constant - matching lower bounds due to Nesterov of $Ω(1/\sqrtε)$, up to a $\log(1/ε)$ factor and provides guaranteed bounds for stability when regressors are time-varying. We provide numerical experiments for a variant of Nesterov's provably hard convex optimization problem with time-varying regressors, as well as the problem of recovering an image with a time-varying blur and noise using streaming data.
△ Less
Submitted 4 June, 2021; v1 submitted 4 May, 2020;
originally announced May 2020.
-
Parameter Estimation in Adaptive Control of Time-Varying Systems Under a Range of Excitation Conditions
Authors:
Joseph E. Gaudio,
Anuradha M. Annaswamy,
Eugene Lavretsky,
Michael A. Bolender
Abstract:
This paper presents a new parameter estimation algorithm for the adaptive control of a class of time-varying plants. The main feature of this algorithm is a matrix of time-varying learning rates, which enables parameter estimation error trajectories to tend exponentially fast towards a compact set whenever excitation conditions are satisfied. This algorithm is employed in a large class of problems…
▽ More
This paper presents a new parameter estimation algorithm for the adaptive control of a class of time-varying plants. The main feature of this algorithm is a matrix of time-varying learning rates, which enables parameter estimation error trajectories to tend exponentially fast towards a compact set whenever excitation conditions are satisfied. This algorithm is employed in a large class of problems where unknown parameters are present and are time-varying. It is shown that this algorithm guarantees global boundedness of the state and parameter errors of the system, and avoids an often used filtering approach for constructing key regressor signals. In addition, intervals of time over which these errors tend exponentially fast toward a compact set are provided, both in the presence of finite and persistent excitation. A projection operator is used to ensure the boundedness of the learning rate matrix, as compared to a time-varying forgetting factor. Numerical simulations are provided to complement the theoretical analysis.
△ Less
Submitted 16 November, 2021; v1 submitted 9 November, 2019;
originally announced November 2019.
-
Adaptive Flight Control in the Presence of Limits on Magnitude and Rate
Authors:
Joseph E. Gaudio,
Anuradha M. Annaswamy,
Michael A. Bolender,
Eugene Lavretsky
Abstract:
Input constraints as well as parametric uncertainties must be accounted for in the design of safe control systems. This paper presents an adaptive controller for multiple-input-multiple-output (MIMO) plants with input magnitude and rate saturation in the presence of parametric uncertainties. A filter is introduced in the control path to accommodate the presence of rate limits. An output feedback a…
▽ More
Input constraints as well as parametric uncertainties must be accounted for in the design of safe control systems. This paper presents an adaptive controller for multiple-input-multiple-output (MIMO) plants with input magnitude and rate saturation in the presence of parametric uncertainties. A filter is introduced in the control path to accommodate the presence of rate limits. An output feedback adaptive controller is designed to stabilize the closed loop system even in the presence of this filter. The overall control architecture includes adaptive laws that are modified to account for the magnitude and rate limits. Analytical guarantees of bounded solutions and satisfactory tracking are provided. Three flight control simulations with nonlinear models of the aircraft dynamics are provided to demonstrate the efficacy of the proposed adaptive controller for open loop stable and unstable systems in the presence of uncertainties in the dynamics as well as input magnitude and rate saturation.
△ Less
Submitted 27 July, 2019;
originally announced July 2019.
-
An Improved Lower Bound for the Traveling Salesman Constant
Authors:
Julia Gaudio,
Patrick Jaillet
Abstract:
Let $X_1, X_2, \dots, X_n$ be independent uniform random variables on $[0,1]^2$. Let $L(X_1, \dots, X_n)$ be the length of the shortest Traveling Salesman tour through these points. It is known that there exists a constant $β$ such that $$\lim_{n \to \infty} \frac{L(X_1, \dots, X_n)}{\sqrt{n}} = β$$ almost surely (Beardwood 1959). The original analysis in (Beardwood 1959) showed that…
▽ More
Let $X_1, X_2, \dots, X_n$ be independent uniform random variables on $[0,1]^2$. Let $L(X_1, \dots, X_n)$ be the length of the shortest Traveling Salesman tour through these points. It is known that there exists a constant $β$ such that $$\lim_{n \to \infty} \frac{L(X_1, \dots, X_n)}{\sqrt{n}} = β$$ almost surely (Beardwood 1959). The original analysis in (Beardwood 1959) showed that $β\geq 0.625$. Building upon an approach proposed in (Steinerberger 2015), we improve the lower bound to $β\geq 0.6277$.
△ Less
Submitted 4 July, 2019;
originally announced July 2019.
-
Sparse High-Dimensional Isotonic Regression
Authors:
David Gamarnik,
Julia Gaudio
Abstract:
We consider the problem of estimating an unknown coordinate-wise monotone function given noisy measurements, known as the isotonic regression problem. Often, only a small subset of the features affects the output. This motivates the sparse isotonic regression setting, which we consider here. We provide an upper bound on the expected VC entropy of the space of sparse coordinate-wise monotone functi…
▽ More
We consider the problem of estimating an unknown coordinate-wise monotone function given noisy measurements, known as the isotonic regression problem. Often, only a small subset of the features affects the output. This motivates the sparse isotonic regression setting, which we consider here. We provide an upper bound on the expected VC entropy of the space of sparse coordinate-wise monotone functions, and identify the regime of statistical consistency of our estimator. We also propose a linear program to recover the active coordinates, and provide theoretical recovery guarantees. We close with experiments on cancer classification, and show that our method significantly outperforms standard methods.
△ Less
Submitted 2 July, 2019;
originally announced July 2019.
-
Connections Between Adaptive Control and Optimization in Machine Learning
Authors:
Joseph E. Gaudio,
Travis E. Gibson,
Anuradha M. Annaswamy,
Michael A. Bolender,
Eugene Lavretsky
Abstract:
This paper demonstrates many immediate connections between adaptive control and optimization methods commonly employed in machine learning. Starting from common output error formulations, similarities in update law modifications are examined. Concepts in stability, performance, and learning, common to both fields are then discussed. Building on the similarities in update laws and common concepts,…
▽ More
This paper demonstrates many immediate connections between adaptive control and optimization methods commonly employed in machine learning. Starting from common output error formulations, similarities in update law modifications are examined. Concepts in stability, performance, and learning, common to both fields are then discussed. Building on the similarities in update laws and common concepts, new intersections and opportunities for improved algorithm analysis are provided. In particular, a specific problem related to higher order learning is solved through insights obtained from these intersections.
△ Less
Submitted 11 April, 2019;
originally announced April 2019.
-
Provably Correct Learning Algorithms in the Presence of Time-Varying Features Using a Variational Perspective
Authors:
Joseph E. Gaudio,
Travis E. Gibson,
Anuradha M. Annaswamy,
Michael A. Bolender
Abstract:
Features in machine learning problems are often time-varying and may be related to outputs in an algebraic or dynamical manner. The dynamic nature of these machine learning problems renders current higher order accelerated gradient descent methods unstable or weakens their convergence guarantees. Inspired by methods employed in adaptive control, this paper proposes new algorithms for the case when…
▽ More
Features in machine learning problems are often time-varying and may be related to outputs in an algebraic or dynamical manner. The dynamic nature of these machine learning problems renders current higher order accelerated gradient descent methods unstable or weakens their convergence guarantees. Inspired by methods employed in adaptive control, this paper proposes new algorithms for the case when time-varying features are present, and demonstrates provable performance guarantees. In particular, we develop a unified variational perspective within a continuous time algorithm. This variational perspective includes higher order learning concepts and normalization, both of which stem from adaptive control, and allows stability to be established for dynamical machine learning problems where time-varying features are present. These higher order algorithms are also examined for provably correct learning in adaptive control and identification. Simulations are provided to verify the theoretical results.
△ Less
Submitted 27 May, 2019; v1 submitted 11 March, 2019;
originally announced March 2019.
-
Attracting Random Walks
Authors:
Julia Gaudio,
Yury Polyanskiy
Abstract:
This paper introduces the Attracting Random Walks model, which describes the dynamics of a system of particles on a graph with $n$ vertices. At each step, a single particle moves to an adjacent vertex (or stays at the current one) with probability proportional to the exponent of the number of other particles at a vertex. From an applied standpoint, the model captures the rich get richer phenomenon…
▽ More
This paper introduces the Attracting Random Walks model, which describes the dynamics of a system of particles on a graph with $n$ vertices. At each step, a single particle moves to an adjacent vertex (or stays at the current one) with probability proportional to the exponent of the number of other particles at a vertex. From an applied standpoint, the model captures the rich get richer phenomenon. We show that the Markov chain exhibits a phase transition in mixing time, as the parameter governing the attraction is varied. Namely, mixing time is $O(n\log n)$ when the temperature is sufficiently high and $\exp(Ω(n))$ when temperature is sufficiently low. When $\mathcal{G}$ is the complete graph, the model is a projection of the Potts model, whose mixing properties and the critical temperature have been known previously. However, for any other graph our model is non-reversible and does not seem to admit a simple Gibbsian description of a stationary distribution. Notably, we demonstrate existence of the dynamic phase transition without decomposing the stationary distribution into phases.
△ Less
Submitted 29 May, 2020; v1 submitted 1 March, 2019;
originally announced March 2019.
-
Exponential Convergence Rates for Stochastically Ordered Markov Processes with Random Initial Conditions
Authors:
Julia Gaudio,
Saurabh Amin,
Patrick Jaillet
Abstract:
In this brief paper we find computable exponential convergence rates for a large class of stochastically ordered Markov processes. We extend the result of Lund, Meyn, and Tweedie (1996), who found exponential convergence rates for stochastically ordered Markov processes starting from a fixed initial state, by allowing for a random initial condition that is also stochastically ordered. Our bounds a…
▽ More
In this brief paper we find computable exponential convergence rates for a large class of stochastically ordered Markov processes. We extend the result of Lund, Meyn, and Tweedie (1996), who found exponential convergence rates for stochastically ordered Markov processes starting from a fixed initial state, by allowing for a random initial condition that is also stochastically ordered. Our bounds are formulated in terms of moment-generating functions of hitting times. To illustrate our result, we find an explicit exponential convergence rate for an M/M/1 queue beginning in equilibrium and then experiencing a change in its arrival or departure rates, a setting which has not been studied to our knowledge.
△ Less
Submitted 17 October, 2018;
originally announced October 2018.
-
Liquid-solid impacts of yield-stress fluids
Authors:
Marc E. Deetjen,
Brendan C. Blackwell,
Joseph E. Gaudio,
Randy H. Ewoldt
Abstract:
This is an entry to the Gallery of Fluid Motion at the 66th annual meeting of the APS-DFD, held November 2013 in Pittsburgh, PA. In this fluid dynamics video we demonstrate distinct features of yield-stress fluid droplets impacting pre-coated surfaces.
This is an entry to the Gallery of Fluid Motion at the 66th annual meeting of the APS-DFD, held November 2013 in Pittsburgh, PA. In this fluid dynamics video we demonstrate distinct features of yield-stress fluid droplets impacting pre-coated surfaces.
△ Less
Submitted 12 October, 2013;
originally announced October 2013.
