Secure Approximation Guarantee for Cryptographically Private Empirical Risk Minimization.
Toshiyuki TakadaHiroyuki HanadaYoshiji YamadaJun SakumaIchiro TakeuchiPublished in: CoRR (2016)
Keyphrases
- empirical risk minimization
- approximation guarantees
- greedy algorithm
- approximation ratio
- uniform convergence
- approximation algorithms
- vc dimension
- rates of convergence
- statistical learning theory
- empirical risk
- linear programming relaxation
- phase transition
- lower bound
- np hard
- computationally tractable
- special case
- objective function
- generalization bounds
- worst case
- generalization error
- constraint satisfaction
- theoretical framework
- loss function