论文标题
关于随机凸优化问题与$ p $ norm球上的经验风险最小化问题的关系
On the relations of stochastic convex optimization problems with empirical risk minimization problems on $p$-norm balls
论文作者
论文摘要
在本文中，我们考虑了在机器学习应用中（例如，风险最小化）和数学统计（例如，最大似然估计）中引起的凸随机优化问题。有两种解决此类问题的主要方法，即随机近似方法（在线方法）和样本平均近似方法，也称为Monte Carlo方法（离线方法）。在离线方法中，问题被其经验对应物（经验风险最小化问题）取代。自然的问题是如何定义问题样本量，即应采样多少实现，以使经验问题的非常准确的解决方案是原始问题的解决方案。这个问题是现代机器学习和优化的主要问题之一。在过去的十年中，在这些地区取得了许多重大进展，以解决欧几里得球（或整个空间）上的凸随机优化问题。在这项工作中，我们基于这些进步，并研究了$ \ ell_p $ -norms中任意球的情况。我们还探讨了参数$ p $如何影响所需条款数量的估计值的问题。
In this paper, we consider convex stochastic optimization problems arising in machine learning applications (e.g., risk minimization) and mathematical statistics (e.g., maximum likelihood estimation). There are two main approaches to solve such kinds of problems, namely the Stochastic Approximation approach (online approach) and the Sample Average Approximation approach, also known as the Monte Carlo approach, (offline approach). In the offline approach, the problem is replaced by its empirical counterpart (the empirical risk minimization problem). The natural question is how to define the problem sample size, i.e., how many realizations should be sampled so that the quite accurate solution of the empirical problem be the solution of the original problem with the desired precision. This issue is one of the main issues in modern machine learning and optimization. In the last decade, a lot of significant advances were made in these areas to solve convex stochastic optimization problems on the Euclidean balls (or the whole space). In this work, we are based on these advances and study the case of arbitrary balls in the $\ell_p$-norms. We also explore the question of how the parameter $p$ affects the estimates of the required number of terms as a function of empirical risk.
