Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Min-Max affine approximants of convex or concave real valued functions from $mathbb R^k$, Chebyshev equioscillation and graphics
54
0
0.0
(
0
)
Added by
Steven Damelin Dr
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 algorithm 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. We 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 functions 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
