اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn Min-Max affine approximants of convex or concave real valued functions from $mathbb R^k$, Chebyshev equioscillation and graphics
54
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We study Min-Max affine approximants of a continuous convex or concave function $f:Deltasubset mathbb R^kxrightarrow{} mathbb R$ where $Delta$ is a convex compact subset of $mathbb R^k$. In the case when $Delta$ is a simplex we prove that there is a vertical translate of the supporting hyperplane in $mathbb R^{k+1}$ of the graph of $f$ at the vertices which is the unique best affine approximant to $f$ on $Delta$. For $k=1$, this result provides an extension of the Chebyshev equioscillation theorem for linear approximants. Our result has interesting connections to the computer graphics problem of rapid rendering of projective transformations.
قيم البحث
اقرأ أيضاً
Min-max problems have broad applications in machine learning, including learning with non-decomposable loss and learning with robustness to data distribution. Convex-concave min-max problem is an active topic of research with efficient algorithms and
sound theoretical foundations developed. However, it remains a challenge to design provably efficient algorithms for non-convex min-max problems with or without smoothness. In this paper, we study a family of non-convex min-max problems, whose objective function is weakly convex in the variables of minimization and is concave in the variables of maximization. We propose a proximally guided stochastic subgradient method and a proximally guided stochastic variance-reduced method for the non-smooth and smooth instances, respectively, in this family of problems. We analyze the time complexities of the proposed methods for finding a nearly stationary point of the outer minimization problem corresponding to the min-max problem.
We provide improved convergence rates for constrained convex-concave min-max problems and monotone variational inequalities with higher-order smoothness. In min-max settings where the $p^{th}$-order derivatives are Lipschitz continuous, we give an al
gorithm HigherOrderMirrorProx that achieves an iteration complexity of $O(1/T^{frac{p+1}{2}})$ when given access to an oracle for finding a fixed point of a $p^{th}$-order equation. We give analogous rates for the weak monotone variational inequality problem. For $p>2$, our results improve upon the iteration complexity of the first-order Mirror Prox method of Nemirovski [2004] and the second-order method of Monteiro and Svaiter [2012]. We further instantiate our entire algorithm in the unconstrained $p=2$ case.
We provide a first-order oracle complexity lower bound for finding stationary points of min-max optimization problems where the objective function is smooth, nonconvex in the minimization variable, and strongly concave in the maximization variable. W
e establish a lower bound of $Omegaleft(sqrt{kappa}epsilon^{-2}right)$ for deterministic oracles, where $epsilon$ defines the level of approximate stationarity and $kappa$ is the condition number. Our analysis shows that the upper bound achieved in (Lin et al., 2020b) is optimal in the $epsilon$ and $kappa$ dependence up to logarithmic factors. For stochastic oracles, we provide a lower bound of $Omegaleft(sqrt{kappa}epsilon^{-2} + kappa^{1/3}epsilon^{-4}right)$. It suggests that there is a significant gap between the upper bound $mathcal{O}(kappa^3 epsilon^{-4})$ in (Lin et al., 2020a) and our lower bound in the condition number dependence.
Convexification based on convex envelopes is ubiquitous in the non-linear optimization literature. Thanks to considerable efforts of the optimization community for decades, we are able to compute the convex envelopes of a considerable number of funct
ions that appear in practice, and thus obtain tight and tractable approximations to challenging problems. We contribute to this line of work by considering a family of functions that, to the best of our knowledge, has not been considered before in the literature. We call this family ray-concave functions. We show sufficient conditions that allow us to easily compute closed-form expressions for the convex envelope of ray-concave functions over arbitrary polytopes. With these tools, we are able to provide new perspectives to previously known convex envelopes and derive a previously unknown convex envelope for a function that arises in probability contexts.
The like-Lebesgue integral of real-valued measurable functions (abbreviated as textit{RVM-MI})is the most complete and appropriate integration Theory. Integrals are also defined in abstract spaces since Pettis (1938). In particular, Bochner integrals
received much interest with very recent researches. It is very commode to use the textit{RVM-MI} in constructing Bochner integral in Banach or in locally convex spaces. In this simple not, we prove that the Bochner integral and the textit{RVM-MI} with respect to a finite measure $m$ are the same on $mathbb{R}$. Applications of that equality may be useful in weak limits on Banach space.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
