In this paper, we consider an unconstrained optimization model where the objective is a sum of a large number of possibly nonconvex functions, though overall the objective is assumed to be smooth and convex. Our bid to solving such model uses the framework of cubic regularization of Newton's method. As well known, the crux in cubic regularization is its utilization of the Hessian information, which may be computationally expensive for large-scale problems. To tackle this, we resort to approximating the Hessian matrix via sub-sampling. In particular, we propose to compute an approximated Hessian matrix by either uniformly or non-uniformly sub-sampling the components of the objective. Based upon such sampling strategy, we develop accelerated adaptive cubic regularization approaches and provide theoretical guarantees on global iteration complexity of $\O(\epsilon^{-1/3})$ with high probability, which matches that of the original accelerated cubic regularization methods Jiang et al. (2020) using the full Hessian information. Interestingly, we also show that in the worst case scenario our algorithm still achieves an $O(\epsilon^{-5/6}\log(\epsilon^{-1}))$ iteration complexity bound. The proof techniques are new to our knowledge and can be of independent interets. Experimental results on the regularized logistic regression problems demonstrate a clear effect of acceleration on several real data sets.

This paper studies the generalization bounds for the empirical saddle point (ESP) solution to stochastic saddle point (SSP) problems. For SSP with Lipschitz continuous and strongly convex-strongly concave objective functions, we establish an $O\left(1/n\right)$ generalization bound by using a probabilistic stability argument. We also provide generalization bounds under a variety of assumptions, including the cases without strong convexity and without bounded domains. We illustrate our results in three examples: batch policy learning in Markov decision process, stochastic composite optimization problem, and mixed strategy Nash equilibrium estimation for stochastic games. In each of these examples, we show that a regularized ESP solution enjoys a near-optimal sample complexity. To the best of our knowledge, this is the first set of results on the generalization theory of ESP.

This paper is concerned with finding an optimal algorithm for minimizing a composite convex objective function. The basic setting is that the objective is the sum of two convex functions: the first function is smooth with up to the d-th order derivative information available, and the second function is possibly non-smooth, but its proximal tensor mappings can be computed approximately in an efficient manner. The problem is to find – in that setting – the best possible (optimal) iteration complexity for convex optimization. Along that line, for the smooth case (without the second non-smooth part in the objective), Nesterov (1983) proposed an optimal algorithm for the first-order methods (d=1) with iteration complexity O( 1 / k^2 ). A high-order tensor algorithm with iteration complexity of O( 1 / k^{d+1} ) was proposed by Baes (2009) and Nesterov (2018). In this paper, we propose a new high-order tensor algorithm for the general composite case, with the iteration complexity of O( 1 / k^{(3d+1)/2} ), which matches the lower bound for the d-th order methods as established in Nesterov (2018) and Shamir et al. (2018), and hence is optimal. Our approach is based on the Accelerated Hybrid Proximal Extragradient (A-HPE) framework proposed in Monteiro and Svaiter (2013), where a bisection procedure is installed for each A-HPE iteration. At each bisection step a proximal tensor subproblem is approximately solved, and the total number of bisection steps per A-HPE iteration is bounded by a logarithmic factor in the precision required.

In this merged paper, we consider the problem of minimizing a convex function with Lipschitz-continuous $p$-th order derivatives. Given an oracle which when queried at a point returns the first $p$-derivatives of the function at that point we provide some methods which compute an $\e$ approximate minimizer in $O\left(\e^{-\frac{2}{3p+1}} \right)$ iterations. These methods match known lower bounds up to polylogarithmic factors for constant $p$.

In this paper, we consider online learning with non-convex loss functions. Similar to Besbes et al. [2015] we apply non-stationary regret as the performance metric. In particular, we study the regret bounds under different assumptions on the information available regarding the loss functions. When the gradient of the loss function at the decision point is available, we propose an online normalized gradient descent algorithm (ONGD) to solve the online learning problem. In another situation, when only the value of the loss function is available, we propose a bandit online normalized gradient descent algorithm (BONGD). Under a condition to be called weak pseudo-convexity (WPC), we show that both algorithms achieve a cumulative regret bound of O($\sqrt{T+V_T T}$), where $V_T$ is the total temporal variations of the loss functions, thus establishing a sublinear regret bound for online learning with non-convex loss functions and non-stationary regret measure.

Consider a unicast downlink beamforming optimization problem with robust signal-to-interference-plus-noise ratio constraints to account for non-perfect channel state information at the base station. The convexity of the robust beamforming problem remains unknown. A slightly conservative version of the robust beamforming problem is thus studied herein as a compromise. It is in the form of a semi-infinite second-order cone program (SOCP), and more importantly, it possesses an equivalent and explicit convex reformulation, due to an linear matrix inequality description of the cone of Lorentz-positive maps. Hence the robust beamforming problem can be efficiently solved by an optimization solver. The simulation results show that the conservativeness of the robust form of semi-infinite SOCP is appropriate in terms of problem feasibility rate and the average transmission power.

Consider a robust downlink beamforming optimization problem for secondary multicast transmission in a multiple-input multiple-output (MIMO) spectrum sharing cognitive radio (CR) network. The minimization problem of transmit power is formulated subject to both the quality-of-service (QoS) constraints on the secondary receivers and the interference temperature constraints on the primary users, under the assumption of imperfect channel state information (CSI). The problem is non-convex quadratically constrained quadratic program (QCQP), and it is hard to achieve the global optimality. As a compromise, we present a randomized approximation algorithm for the problem via convex optimization techniques. In particular, we point out that the robust beamforming problem is efficiently solvable when the number of primary and secondary links in the CR network is not larger than three. Simulation results are presented to demonstrate the performance gains of the proposed algorithm over an existing robust design.

Consider a bandwidth constrained sensor network in which a set of distributed sensors and a fusion center (FC) collaborate to estimate an unknown vector. Due to power and cost limitations, each sensor must compress its data in order to minimize the amount of information that need to be communicated to the FC. In this paper, we consider the design of a linear decentralized estimation scheme (DES) whereby each sensor transmits over a noisy channel to the FC a fixed number of real-valued messages which are linear functions of its observations, while the FC linearly combines the received messages to estimate the unknown parameter vector. Assuming each sensor collects data according to a local linear model, we propose to design optimal linear message functions and linear fusion function according to the minimum mean squared error (MMSE) criterion. We show that the resulting design problem is nonconvex and NP-hard in general, and identify two special cases for which the optimal linear DES design problem can be efficiently solved either in closed form or by semi-definite programming (SDP).