Information-theoretic lower bounds for convex optimization with erroneous oracles.
Yaron SingerJan VondrákPublished in: NIPS (2015)
Keyphrases
- convex optimization
- information theoretic
- lower bound
- upper bound
- mutual information
- information theory
- primal dual
- total variation
- interior point methods
- low rank
- objective function
- optimal solution
- np hard
- information theoretic measures
- convex relaxation
- worst case
- vc dimension
- active learning
- convex optimization problems
- denoising
- kl divergence
- interior point
- image denoising
- higher order
- image analysis
- multiscale
- feature selection