ABGD parametrizes piecewise linear functions as difference of max-affine functions and converges linearly to an epsilon-accurate solution with O(d max(sigma/epsilon,1)^2) samples under sub-Gaussian noise, which is minimax optimal up to logs.
Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
We consider the problem of solving mixed random linear equations with $k$ components. This is the noiseless setting of mixed linear regression. The goal is to estimate multiple linear models from mixed samples in the case where the labels (which sample corresponds to which model) are not observed. We give a tractable algorithm for the mixed linear equation problem, and show that under some technical conditions, our algorithm is guaranteed to solve the problem exactly with sample complexity linear in the dimension, and polynomial in $k$, the number of components. Previous approaches have required either exponential dependence on $k$, or super-linear dependence on the dimension. The proposed algorithm is a combination of tensor decomposition and alternating minimization. Our analysis involves proving that the initialization provided by the tensor method allows alternating minimization, which is equivalent to EM in our setting, to converge to the global optimum at a linear rate.
citation-role summary
method 1
citation-polarity summary
roles
method 1polarities
use method 1representative citing papers
Gradient EM converges exponentially to optimal population loss minimizers for agnostic fitting of k parametric functions under strong convexity and smoothness of the loss, proper initialization, and separation conditions.
Sp-GD recovers sparse max-affine parameters to epsilon accuracy with O(s log(d/s)) samples in the noise-free case under sub-Gaussian assumptions, supported by sparse-PCA initialization and an RMD transformation for generalized polynomials.
citing papers explorer
-
Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions
ABGD parametrizes piecewise linear functions as difference of max-affine functions and converges linearly to an epsilon-accurate solution with O(d max(sigma/epsilon,1)^2) samples under sub-Gaussian noise, which is minimax optimal up to logs.
-
Expectation Maximization (EM) Converges for General Agnostic Mixtures
Gradient EM converges exponentially to optimal population loss minimizers for agnostic fitting of k parametric functions under strong convexity and smoothness of the loss, proper initialization, and separation conditions.
-
Sparse Max-Affine Regression
Sp-GD recovers sparse max-affine parameters to epsilon accuracy with O(s log(d/s)) samples in the noise-free case under sub-Gaussian assumptions, supported by sparse-PCA initialization and an RMD transformation for generalized polynomials.