-
作者：Yang, Shuoguang; Truong, Van-Anh
作者单位：Hong Kong University of Science & Technology; Columbia University
摘要：We propose the analysis of the online learning problem for independent cascade (IC) models under node-level feedback. These models have widespread applications in modern social networks. Existing works for IC models have only shed light on edge-level feedback models, where the agent knows the explicit outcome of every observed edge. Little is known about node-level feedback models where only combined outcomes for sets of edges are observed; in other words, the realization of each edge is censo...
-
作者：Kahale, Nabil
作者单位：heSam Universite; ESCP Business School
摘要：We consider an online least squares regression problem with optimal solution u' and Hessian matrix H, and study a time-average stochastic gradient descent estimator of u'. For k >= 2, we provide an unbiased estimator of u' that is a modification of the timeaverage estimator and runs with an expected number of time-steps of order k, with O(1=k) expected excess risk. The constant behind the O notation depends on parameters of the regression and is a polylogarithmic function of the smallest eigen...
-
作者：Callegaro, Giorgia; Di Tella, Paolo; Ongarato, Beatrice; Sgarra, Carlo
作者单位：University of Padua; Technische Universitat Dresden; Universita degli Studi di Bari Aldo Moro
摘要：The aim of this paper is to investigate a quadratic, that is, variance-optimal, semistatic hedging problem in an incomplete market model where the underlying log-asset price is driven by a diffusion process with stochastic volatility and a self-exciting jump process of the Hawkes type. More precisely, we aim at hedging a claim at time T > 0 by using a portfolio of available contingent claims so as to minimize the variance of the residual hedging error at time T. In order to improve the replica...
-
作者：Chen, Lin; Tao, Liangde; Verschae, Jose
作者单位：Zhejiang University; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
摘要：We consider a classical scheduling problem on m identical machines. For an arbitrary constant q > 1, the aim is to assign jobs to machines such that Sigma(m)(i=1) C-i(q) is minimized, where C-i is the total processing time of jobs assigned to machine i. It is well known that this problem is strongly NP-hard. Under mild assumptions, the running time of a (1 + epsilon)-approximation algorithm for a strongly NP-hard problem cannot be polynomial on 1/epsilon, unless P=NP. For most problems in the ...
-
作者：Giannakopoulos, Yiannis; Melissourgos, Themistoklis; Grosz, Alexander
作者单位：University of Glasgow; Technical University of Munich; University of Essex
摘要：We propose a unifying framework for smoothed analysis of combinatorial local optimization problems and show how a variety of problems within the complexity class PLS (Polynomial Local Search) can be cast within this model. This abstraction enables identifying key structural properties, and corresponding parameters, that determine the smoothed running time of local search dynamics. Our black-box tool provides concrete bounds on the expected maximum number of steps needed until local search reac...
-
作者：Jiao, Liguo; Lee, Jae Hyoung; Pham, Tien-Son
作者单位：Northeast Normal University - China; Pukyong National University; Dalat University
摘要：We are interested in optimality conditions for semialgebraic vector optimization problems with a situation in which generalized (weakly) nondominated points do exist but are not attained as image points of (weakly) efficient solutions. To this end, cones associated with unbounded semialgebraic sets at infinity are introduced and studied. Then, optimality conditions at infinity in terms of the Newton polyhedra of the objective mappings and of the cones associated with the constraint sets at inf...
-
作者：Ma, Jianhao; Fattahi, Salar
作者单位：University of Michigan System; University of Michigan
摘要：We explore the local landscape of low-rank matrix recovery, focusing on reconstructing a d1 x d2 matrix X* with rank r from m linear measurements, some potentially noisy. When the noise is distributed according to an outlier model, minimizing a nonsmooth & ell;1-loss with a simple subgradient method can often perfectly recover the ground truth matrix X*. Given this, a natural question is what optimization property (if any) enables such learning behavior. The most plausible answer is that the g...
-
作者：Zhang, Xilin; Cheung, Wang Chi
作者单位：National University of Singapore
摘要：We study a general reusable resource allocation model under both model uncertainty and nonstationarity. Our study involves a set of heterogeneous customers who arrive sequentially at the decision maker's (DM's) platform, each associated with a different customer type. Each arriving customer's type is drawn from an unknown and time-varying probability distribution. Upon observing the customer's type, the DM selects an allocation decision that generates a random amount of reward and occupies ran...
-
作者：Bayraktar, Erhan; Han, Bingyan
作者单位：University of Michigan System; University of Michigan; Hong Kong University of Science & Technology (Guangzhou)
摘要：Given two probability measures on sequential data, we investigate the transport problem with time-inconsistent preferences in a discrete-time setting. Motivating examples are nonlinear objectives, state-dependent costs, and regularized optimal transport with general f-divergence. Under the bicausal constraint, we introduce the concept of equilibrium transport. Existence is proved in the semidiscrete Markovian case and the continuous non-Markovian case with strict quasiconvexity, whereas unique...
-
作者：Han, Xiyue; Schied, Alexander
作者单位：University of Waterloo
摘要：We study the problem of reconstructing the Faber-Schauder coefficients of a continuous functionf from discrete observations of its antiderivative F. For instance, this question arises in financial mathematics when estimating the roughness of volatility from the integrated volatility of an asset price trajectory. Our approach starts with mathematically formulating the reconstruction problem through piecewise quadratic spline interpolation. We then provide a closed-form solution and an in-depth ...
