Clustering is a fundamental primitive in unsupervised learning which gives rise to a rich class
of computationally-challenging inference tasks. In this work, we focus on the canonical task of
clustering d-dimensional Gaussian mixtures with unknown (and possibly degenerate) covariance.
Recent works (Ghosh et al. ’20; Mao, Wein ’21; Davis, Diaz, Wang ’21) have established lower
bounds against the class of low-degree polynomial methods and the sum-of-squares (SoS) hierarchy
for recovering certain hidden structures planted in Gaussian clustering instances. Prior work
on many similar inference tasks portends that such lower bounds strongly suggest the presence
of an inherent statistical-to-computational gap for clustering, that is, a parameter regime where
the clustering task is statistically possible but no polynomial-time algorithm succeeds.
One special case of the clustering task we consider is equivalent to the problem of finding a
planted hypercube vector in an otherwise random subspace. We show that, perhaps surprisingly,
this particular clustering model does not exhibit a statistical-to-computational gap, despite the
aforementioned low-degree and SoS lower bounds. To achieve this, we give an algorithm based
on Lenstra–Lenstra–Lovász lattice basis reduction which achieves the statistically-optimal sample
complexity of d + 1 samples. This result extends the class of problems whose conjectured
statistical-to-computational gaps can be “closed” by “brittle” polynomial-time algorithms, highlighting
the crucial but subtle role of noise in the onset of statistical-to-computational gaps.
more »
« less
Data-Driven Superstabilizing Control of Error-in-Variables Discrete-Time Linear Systems
This paper proposes a method to find superstabilizing
controllers for discrete-time linear systems that are
consistent with a set of corrupted observations. The L-infinity
bounded measurement noise introduces a bilinearity between
the unknown plant parameters and noise terms. A superstabilizing
controller may be found by solving a feasibility
problem involving a set of polynomial nonnegativity constraints
in terms of the unknown plant parameters and noise terms. A
sequence of sum-of-squares (SOS) programs in rising degree
will yield a super-stabilizing controller if such a controller exists.
Unfortunately, these SOS programs exhibit very poor scaling as
the degree increases. A theorem of alternatives is employed to
yield equivalent, convergent (under mild conditions), and more
computationally tractable SOS programs.
more »
« less
- Award ID(s):
- 2208182
- NSF-PAR ID:
- 10447843
- Date Published:
- Journal Name:
- 60th IEEE Conf. Decision and Control
- Page Range / eLocation ID:
- 4924 to 4929
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We present a dual form of Lyapunov-Krasovskii functional which allows the problem of controller synthesis for multi-delay systems to be formulated and solved in a convex manner. First, we give a generalized version of the dual stability condition formulated in terms of Lyapunov operators which are positive, self-adjoint and preserve the structure of the state-space. Second, we provide a class of such operators and express the stability conditions as positivity and negativity of quadratic Lyapunov-Krasovskii functional forms. Next, we adapt the SOS methodology to express positivity and negativity of these forms as LMIs, describing a new set of polynomial manipulation tools designed for this purpose. We apply the resulting LMIs to a battery of numerical examples and demonstrate that the stability conditions are not significantly conservative. Finally, we formulate a test for controller synthesis for systems with multiple delays, apply the test to a numerical example, and simulate the resulting closed-loop system.more » « less
-
null (Ed.)This article examines the degree to which optimizing a Rijke tube experiment can improve the accuracy of thermoacoustic model parameter estimation, thereby facilitating robust stability control. We use a one-dimensional thermoacoustic model to describe the combustion dynamics in a Rijke tube. This model contains two unknown parameters that relate velocity perturbations to heat release rate oscillations, namely, a time delay τ and amplification factor β. The parameters are estimated from experiments where the system input is the acoustic excitation from a loudspeaker and the output is the pressure response captured by a microphone. Our work is grounded in the insight that optimizing an experiment’s design for higher Fisher identifiability leads to more accurate parameter estimates. The novel goal of this paper is to apply this insight in the laboratory using a flame-driven Rijke tube setup. For comparison purposes, we conduct a benchmark experiment with a broadband chirp signal as the excitation input. Next, we excite the Rijke tube at two frequencies optimized for Fisher identifiability. Repeats of both experiments show that the optimal experiment achieves parameter estimates with uncertainties at least one order of magnitude smaller than the benchmark. With smaller parameter estimate uncertainties, an LQG controller designed to attenuate combustion instabilities is able to achieve stronger robustness guarantees, quantified in terms of closed-loop structured singular values that account for parameter estimation uncertainty.more » « less
-
INTRODUCTION During the independent process of cereal evolution, many trait shifts appear to have been under convergent selection to meet the specific needs of humans. Identification of convergently selected genes across cereals could help to clarify the evolution of crop species and to accelerate breeding programs. In the past several decades, researchers have debated whether convergent phenotypic selection in distinct lineages is driven by conserved molecular changes or by diverse molecular pathways. Two of the most economically important crops, maize and rice, display some conserved phenotypic shifts—including loss of seed dispersal, decreased seed dormancy, and increased grain number during evolution—even though they experienced independent selection. Hence, maize and rice can serve as an excellent system for understanding the extent of convergent selection among cereals. RATIONALE Despite the identification of a few convergently selected genes, our understanding of the extent of molecular convergence on a genome-wide scale between maize and rice is very limited. To learn how often selection acts on orthologous genes, we investigated the functions and molecular evolution of the grain yield quantitative trait locus KRN2 in maize and its rice ortholog OsKRN2 . We also identified convergently selected genes on a genome-wide scale in maize and rice, using two large datasets. RESULTS We identified a selected gene, KRN2 ( kernel row number2 ), that differs between domesticated maize and its wild ancestor, teosinte. This gene underlies a major quantitative trait locus for kernel row number in maize. Selection in the noncoding upstream regions resulted in a reduction of KRN2 expression and an increased grain number through an increase in kernel rows. The rice ortholog, OsKRN2 , also underwent selection and negatively regulates grain number via control of secondary panicle branches. These orthologs encode WD40 proteins and function synergistically with a gene of unknown function, DUF1644, which suggests that a conserved protein interaction controls grain number in maize and rice. Field tests show that knockout of KRN2 in maize or OsKRN2 in rice increased grain yield by ~10% and ~8%, respectively, with no apparent trade-off in other agronomic traits. This suggests potential applications of KRN2 and its orthologs for crop improvement. On a genome-wide scale, we identified a set of 490 orthologous genes that underwent convergent selection during maize and rice evolution, including KRN2/OsKRN2 . We found that the convergently selected orthologous genes appear to be significantly enriched in two specific pathways in both maize and rice: starch and sucrose metabolism, and biosynthesis of cofactors. A deep analysis of convergently selected genes in the starch metabolic pathway indicates that the degree of genetic convergence via convergent selection is related to the conservation and complexity of the gene network for a given selection. CONCLUSION Our findings show that common phenotypic shifts during maize and rice evolution acting on conserved genes are driven at least in part by convergent selection, which in maize and rice likely occurred both during and after domestication. We provide evolutionary and functional evidence on the convergent selection of KRN2/OsKRN2 for grain number between maize and rice. We further found that a complete loss-of-function allele of KRN2/OsKRN2 increased grain yield without an apparent negative impact on other agronomic traits. Exploring the role of KRN2/OsKRN2 and other convergently selected genes across the cereals could provide new opportunities to enhance the production of other global crops. Shared selected orthologous genes in maize and rice for convergent phenotypic shifts during domestication and improvement. By comparing 3163 selected genes in maize and 18,755 selected genes in rice, we identified 490 orthologous gene pairs, including KRN2 and its rice ortholog OsKRN2 , as having been convergently selected. Knockout of KRN2 in maize or OsKRN2 in rice increased grain yield by increasing kernel rows and secondary panicle branches, respectively.more » « less
-
This paper presents a method to lower-bound the distance of closest approach between points on an unsafe set and points along system trajectories. Such a minimal distance is a quantifiable and interpretable certificate of safety of trajectories, as compared to prior art in barrier and density methods which offers a binary indication of safety/unsafety. The distance estimation problem is converted into a infinitedimensional linear program in occupation measures based on existing work in peak estimation and optimal transport. The moment-SOS hierarchy is used to obtain a sequence of lower bounds obtained through solving semidefinite programs in increasing size, and these lower bounds will converge to the true minimal distance as the degree approaches infinity under mild conditions (e.g. Lipschitz dynamics, compact sets).more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/CDC51059.2022.9992363
