Timezone: »
Poster
Algorithms and matching lower bounds for approximatelyconvex optimization
Andrej Risteski · Yuanzhi Li
In recent years, a rapidly increasing number of applications in practice requires solving nonconvex objectives, like training neural networks, learning graphical models, maximum likelihood estimation etc. Though simple heuristics such as gradient descent with very few modifications tend to work well, theoretical understanding is very weak. We consider possibly the most natural class of nonconvex functions where one could hope to obtain provable guarantees: functions that are ``approximately convex'', i.e. functions $\tf: \Real^d \to \Real$ for which there exists a \emph{convex function} $f$ such that for all $x$, $\tf(x)  f(x) \le \errnoise$ for a fixed value $\errnoise$. We then want to minimize $\tf$, i.e. output a point $\tx$ such that $\tf(\tx) \le \min_{x} \tf(x) + \err$. It is quite natural to conjecture that for fixed $\err$, the problem gets harder for larger $\errnoise$, however, the exact dependency of $\err$ and $\errnoise$ is not known. In this paper, we strengthen the known \emph{information theoretic} lower bounds on the tradeoff between $\err$ and $\errnoise$ substantially, and exhibit an algorithm that matches these lower bounds for a large class of convex bodies.
Author Information
Andrej Risteski (Princeton University)
Yuanzhi Li (Princeton University)
More from the Same Authors

2017 Poster: Convergence Analysis of Twolayer Neural Networks with ReLU Activation »
Yuanzhi Li · Yang Yuan 
2017 Poster: Linear Convergence of a FrankWolfe Type Algorithm over TraceNorm Balls »
Zeyuan AllenZhu · Elad Hazan · Wei Hu · Yuanzhi Li 
2017 Spotlight: Linear Convergence of a FrankWolfe Type Algorithm over TraceNorm Balls »
Zeyuan AllenZhu · Elad Hazan · Wei Hu · Yuanzhi Li 
2016 Poster: Approximate maximum entropy principles via GoemansWilliamson with applications to provable variational methods »
Andrej Risteski · Yuanzhi Li 
2016 Poster: Recovery Guarantee of Nonnegative Matrix Factorization via Alternating Updates »
Yuanzhi Li · Yingyu Liang · Andrej Risteski 
2016 Poster: Even Faster SVD Decomposition Yet Without Agonizing Pain »
Zeyuan AllenZhu · Yuanzhi Li 
2015 Poster: On some provably correct cases of variational inference for topic models »
Pranjal Awasthi · Andrej Risteski 
2015 Spotlight: On some provably correct cases of variational inference for topic models »
Pranjal Awasthi · Andrej Risteski