Semidefinite Optimization, Approximation and Applications 2014
2014-09-24..2014-09-26
Berkeley, United States
[Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017), Optimization and Algorithm Design 2023, ITCS 2022, Discrete Optimization via Continuous Relaxation, Randomized Numerical Linear Algebra and Applications 2018, Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)]
| title | author | length |
|---|---|---|
| Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints | Benjamin Recht | 01h 10m |
Claims that optimization algorithms map to a linear dynamical plant plus a nonlinear gradient block and that stability/rate can be certified by searching for… | ||
| Adventures in Linear Algebra++ and Unsupervised Learning | Sanjeev Arora | 01h 00m |
Sanjeev Arora, Princeton University
Semidefinite Optimization, Approximation and Applications
http://simons.berkeley.edu/talks/sanjeev-arora-2014-09-22 | ||
| Learning Overcomplete Latent Variable Models through Tensor Power Method | Rong Ge | 54m |
Presents a polynomial-time algorithm that recovers overcomplete latent-variable models (mixtures and multiview) by constructing a third-order moment tensor and… | ||
| Robust PCA via Non-convex Methods: Provable Bounds | Animashree Anandkumar | 49m |
Claims a provable non‑convex algorithm that exactly recovers a low‑rank plus sparse decomposition under the same deterministic incoherence and sparsity regimes… | ||
| Convex Relaxations for Recovering Simultaneously Structured Objects | Maryam Fazel | 40m |
Claim: combining convex penalties (weighted sums or pointwise maxima of structure-promoting norms) fails to exploit multiple structures and requires as many… | ||
| The Edge of Tractability: Unique Games vs Sum of Squares | David Steurer | 01h 03m |
Argues that the sum-of-squares meta-algorithm formally captures the strongest known approximation methods, gives certificates (low-degree SOS proofs) that rule… | ||
| Recovering Hidden Sparsity via Sum of Squares | Jonathan Kelner | 01h 05m |
Planted sparse vectors inside a random Haar subspace can be recovered even when the sparse support fraction mu is constant (not 1/√N) for subspace dimension D… | ||
| A Polynomial Time Algorithm for Lossy Population Recovery | Ankur Moitra | 34m |
Proves a polynomial time algorithm for lossy population recovery for any fixed mu>0, showing recovery even when only ~1% of bits survive. Turns the problem… | ||
| Serialrank: Spectral Ranking using Seriation | Alexandre d'Aspremont | 50m |
Constructs a similarity matrix S_match similarity by counting how many pairwise outcomes two items agree on and shows that for a consistent total order this… | ||
| Relative Entropy Relaxations for Signomial Optimization | Venkat Chandrasekaran | 57m |
Introduces a hierarchy of convex relaxations for signomial optimization that uses relative entropy to certify nonnegativity via AM–GM weights, defines SAGE… | ||
| Robust Sketching for Large-Scale Multi-Instance Conic Optimization | Laurent El Ghaoui | 33m |
Proposes robust sketching: replace data matrix A by a low‑rank approximation à and add an uncertainty ball so solutions remain valid for any A within that… | ||
| Spectrahedra and their Shadows | Bernd Sturmfels | 01h 07m |
Spectrahedra in three dimensions behave concretely: cubic examples come only in two combinatorial types — samosa vs lemon — with either four or two real nodes… | ||
| Spectral Bounds and SDP Hierarchies for Geometric Packing Problems | Frank Vallentin | 53m |
Uses a unified sum-of-squares SDP hierarchy to get provable upper bounds for geometric packings by recasting independent sets on Cayley graphs as optimization… | ||
| Positive Semidefinite Rank | Rekha Thomas | 56m |
Definition: smallest K for which KxK PSD matrices A_i, B_j satisfy <A_i,B_j>=M_ij, so positive semidefinite rank measures factorizations through PSD cones… | ||
| An SDP-based Algorithmic Cheeger Inequality for Vertex Expansion | Santosh Vempala | 55m |
An SDP relaxation for symmetric vertex expansion is formulated and shown to round to a cut by solving for vertex vectors, picking a random Gaussian projection… | ||
| Tensor Decompositions: Uniqueness and Smoothed Analysis | Moses Charikar | 01h 11m |
Proves a robust analog of Kruskal's theorem so noisy empirical moment tensors yield factor estimates with polynomially related error, and analyzes a smoothed… | ||
| Convex Optimization and Quantum Information | Aram Harrow | 01h 04m |
Explains concrete results connecting convex relaxations to quantum tasks: shows HSEP (separability support function) equals injective tensor norms and 2→4… | ||
| Noncommutative Polynomial Optimization under Dimension Constraints | Miguel Navascués Cobo | 42m |
Presents a convergent SDP hierarchy for noncommutative polynomial optimization with explicit dimension constraints, mapping operator instances to linear moment… | ||
| Convergence of SDP Hierarchies Using Kernel Based Methods: Moment Matrices | Stephanie Wehner | 57m |
Provides a general kernel-based rounding that converts an SDP pseudo-distribution P into a true probability Q by convolving with a squared kernel (Zeta^2)… | ||
| Faster SDP Hierarchy Solvers for Local Rounding Algorithms | Ali Sinop | 46m |
Claims a concrete speedup that removes the exponential-in-level bottleneck for solving SDP hierarchies, giving a provable runtime bound that scales… | ||
| Effectivity Issues and Results for Hilbert's 17th Problem | Marie-Françoise Roy | 45m |
Gives constructive, effective versions of Artin's solution to Hilbert 17th with explicit degree and bit-size bounds for representing a nonnegative polynomial… | ||
| nothing matches | ||