We propose dynamic sampled stochastic approximation (SA) methods for stochastic optimization with a heavy-tailed distribution (with finite 2nd moment). The objective is the sum of a smooth convex function with a convex regularizer. Typically, it is assumed an oracle with an upper bound @math on its variance (OUBV). Differently, we assume an oracle with . This rarely addressed setup is more aggressive but realistic, where the variance may not be bounded. Our methods achieve optimal iteration complexity and (near) optimal oracle complexity. For the smooth convex class, we use an accelerated SA method a la FISTA which achieves, given tolerance @math , the optimal iteration complexity of @math with a near-optimal oracle complexity of @math . This improves upon Ghadimi and Lan [, 156:59-99, 2016] where it is assumed an OUBV. For the strongly convex class, our method achieves optimal iteration complexity of @math and optimal oracle complexity of @math . This improves upon [, 134:127-155, 2012] where it is assumed an OUBV. In terms of variance, our bounds are local: they depend on variances @math at solutions @math and the per unit distance multiplicative variance @math . For the smooth convex class, there exist policies such that our bounds resemble those obtained if it was assumed an OUBV with @math . For the strongly convex class such property is obtained exactly if the condition number is estimated or in the limit for better conditioned problems or for larger initial batch sizes. In any case, if it is assumed an OUBV, our bounds are thus much sharper since typically @math .
The performance of a SA method can be measured by its and given a tolerance @math on the mean optimality gap. The first is the total number of iterations, a measure for the optimization error, while the second is the total number of samples and oracle calls, a measure for the estimation error. Statistical lower bounds @cite_22 show that the optimal oracle complexities are @math for the smooth convex class and @math for the smooth strongly convex class. Anyhow, an important question that remains is ( Q ): ? Related to such question is the ability of method to treat the with .
@cite_22
2158940042 2962961444 2964310650 1992208280
SUMMARY With ideal spatial adaptation, an oracle furnishes information about how best to adapt a spatially variable estimator, whether piecewise constant, piecewise polynomial, variable knot spline, or variable bandwidth kernel, to the unknown function. Estimation with the aid of an oracle offers dramatic advantages over traditional linear estimation by nonadaptive kernels; however, it is a priori unclear whether such performance can be obtained by a procedure relying on the data alone. We describe a new principle for spatially-adaptive estimation: selective wavelet reconstruction. We show that variable-knot spline fits and piecewise-polynomial fits, when equipped with an oracle to select the knots, are not dramatically more powerful than selective wavelet reconstruction with an oracle. We develop a practical spatially adaptive method, RiskShrink, which works by shrinkage of empirical wavelet coefficients. RiskShrink mimics the performance of an oracle for selective wavelet reconstruction as well as it is possible to do so. A new inequality in multivariate normal decision theory which we call the oracle inequality shows that attained performance differs from ideal performance by at most a factor of approximately 2 log n, where n is the sample size. Moreover no estimator can give a better guarantee than this. Within the class of spatially adaptive procedures, RiskShrink is essentially optimal. Relying only on the data, it comes within a factor log 2 n of the performance of piecewise polynomial and variableknot spline methods equipped with an oracle. In contrast, it is unknown how or if piecewise polynomial methods could be made to function this well when denied access to an oracle and forced to rely on data alone. We present an information-theoretic approach to lower bound the oracle complexity of nonsmooth black box convex optimization, unifying previous lower bounding techniques by identifying a combinatorial problem, namely string guessing, as a single source of hardness. As a measure of complexity, we use distributional oracle complexity, which subsumes randomized oracle complexity as well as worst case oracle complexity. We obtain strong lower bounds on distributional oracle complexity for the box @math , as well as for the @math -ball for @math (for both low-scale and large-scale regimes), matching worst case upper bounds, and hence we close the gap between distributional complexity, and in particular, randomized complexity and worst case complexity. Furthermore, the bounds remain essentially the same for high-probability and bounded-error oracle complexity, and even for combination of the two, i.e., bounded-error high-probability oracle complexity. This considerably extends the applicability of known bounds. We characterise the asymptotic upper bounds on the use of Chaitin's ź in oracle computations of halting probabilities (i.e. c.e. reals). We show that the following two conditions are equivalent for any computable function h such that h ( n ) - n is non-decreasing: (1) h ( n ) - n is an information content measure, i.e. the series ź n 2 n - h ( n ) converges, (2) for every c.e. real α there exists a Turing functional via which ź computes α with use bounded by h. We also give a similar characterisation with respect to computations of c.e. sets from ź, by showing that the following are equivalent for any computable non-decreasing function g: (1) g is an information-content measure, (2) for every c.e. set A, ź computes A with use bounded by g. Further results and some connections with Solovay functions (studied by a number of authors 38,3,26,11) are given. Optimal oracle-use of Chaitin's Omega number.Qualification and optimization of the completeness of Chaitin's Omega.Tight bounds on oracle use in the computably enumerable sets and reals. In this paper we consider optimization problems where the objective function is given in a form of the expectation. A basic difficulty of solving such stochastic optimization problems is that the involved multidimensional integrals (expectations) cannot be computed with high accuracy. The aim of this paper is to compare two computational approaches based on Monte Carlo sampling techniques, namely, the stochastic approximation (SA) and the sample average approximation (SAA) methods. Both approaches, the SA and SAA methods, have a long history. Current opinion is that the SAA method can efficiently use a specific (say, linear) structure of the considered problem, while the SA approach is a crude subgradient method, which often performs poorly in practice. We intend to demonstrate that a properly modified SA approach can be competitive and even significantly outperform the SAA method for a certain class of convex stochastic problems. We extend the analysis to the case of convex-concave stochastic saddle point problems and present (in our opinion highly encouraging) results of numerical experiments.