More Like this

1. Plant-and-Steal: Truthful Fair Allocations via Predictions

   Cohen, Ilan Reuven; Eden, Alon; Eden, Talya; Vasilyan, Arsen (December 2024, Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems (NeurIPS 2024))

   We study truthful mechanisms for approximating the Maximin-Share (MMS) allocation of agents with additive valuations for indivisible goods. Algorithmically, constant factor approximations exist for the problem for any number of agents. When adding incentives to the mix, a jarring result by Amanatidis, Birmpas, Christodoulou, and Markakis [EC 2017] shows that the best possible approximation for two agents and m items is ⌊m2⌋. We adopt a learning-augmented framework to investigate what is possible when some prediction on the input is given. For two agents, we give a truthful mechanism that takes agents' ordering over items as prediction. When the prediction is accurate, we give a 2-approximation to the MMS (consistency), and when the prediction is off, we still get an ⌈m2⌉-approximation to the MMS (robustness). We further show that the mechanism's performance degrades gracefully in the number of mistakes" in the prediction; i.e., we interpolate (up to constant factors) between the two extremes: when there are no mistakes, and when there is a maximum number of mistakes. We also show an impossibility result on the obtainable consistency for mechanisms with finite robustness. For the general case of n≥2 agents, we give a 2-approximation mechanism for accurate predictions, with relaxed fallback guarantees. Finally, we give experimental results which illustrate when different components of our framework, made to insure consistency and robustness, come into play. 

   more » « less
2. Projection-free nonconvex stochastic optimization on Riemannian manifolds

   https://doi.org/10.1093/imanum/drab066  

   Weber, Melanie; Sra, Suvrit (September 2021, IMA Journal of Numerical Analysis)

   Abstract We study stochastic projection-free methods for constrained optimization of smooth functions on Riemannian manifolds, i.e., with additional constraints beyond the parameter domain being a manifold. Specifically, we introduce stochastic Riemannian Frank–Wolfe (Fw) methods for nonconvex and geodesically convex problems. We present algorithms for both purely stochastic optimization and finite-sum problems. For the latter, we develop variance-reduced methods, including a Riemannian adaptation of the recently proposed Spider technique. For all settings, we recover convergence rates that are comparable to the best-known rates for their Euclidean counterparts. Finally, we discuss applications to two classic tasks: the computation of the Karcher mean of positive definite matrices and Wasserstein barycenters for multivariate normal distributions. For both tasks, stochastic Fw methods yield state-of-the-art empirical performance. 

   more » « less
3. An algorithm for the grade-two rheological model

   https://doi.org/10.1051/m2an/2022024  

   Pollock, Sara; Scott, L. Ridgway (May 2022, ESAIM: Mathematical Modelling and Numerical Analysis)

   We develop an algorithm for solving the general grade-two model of non-Newtonian fluids which for the first time includes inflow boundary conditions. The algorithm also allows for both of the rheological parameters to be chosen independently. The proposed algorithm couples a Stokes equation for the velocity with a transport equation for an auxiliary vector-valued function. We prove that this model is well posed using the algorithm that we show converges geometrically in suitable Sobolev spaces for sufficiently small data. We demonstrate computationally that this algorithm can be successfully discretized and that it can converge to solutions for the model parameters of order one. We include in the appendix a description of appropriate boundary conditions for the auxiliary variable in standard geometries. 

   more » « less
4. Role of Regularization in the Prediction of Valence from Speech

   https://doi.org/10.21437/Interspeech.2018-2508  

   Sridhar, Kusha; Parthasarathy, Srinivas; Busso, Carlos (September 2018, Interspeech 2018)

   Regularization plays a key role in improving the prediction of emotions using attributes such as arousal, valence and dominance. Regularization is particularly important with deep neural networks (DNNs), which have millions of parameters. While previous studies have reported competitive performance for arousal and dominance, the prediction results for valence using acoustic features are significantly lower. We hypothesize that higher regularization can lead to better results for valence. This study focuses on exploring the role of dropout as a form of regularization for valence, suggesting the need for higher regularization. We analyze the performance of regression models for valence, arousal and dominance as a function of the dropout probability. We observe that the optimum dropout rates are consistent for arousal and dominance. However, the optimum dropout rate for valence is higher. To understand the need for higher regularization for valence, we perform an empirical analysis to explore the nature of emotional cues conveyed in speech. We compare regression models with speakerdependent and speaker-independent partitions for training and testing. The experimental evaluation suggests stronger speaker dependent traits for valence. We conclude that higher regularization is needed for valence to force the network to learn global patterns that generalize across speakers. 

   more » « less
5. Numerical analysis of sparse initial data identification for parabolic problems

   https://doi.org/10.1051/m2an/2019083  

   Leykekhman, Dmitriy; Vexler, Boris; Walter, Daniel (July 2020, ESAIM: Mathematical Modelling and Numerical Analysis)

   null (Ed.)

   In this paper we consider a problem of initial data identification from the final time observation for homogeneous parabolic problems. It is well-known that such problems are exponentially ill-posed due to the strong smoothing property of parabolic equations. We are interested in a situation when the initial data we intend to recover is known to be sparse, i.e. its support has Lebesgue measure zero. We formulate the problem as an optimal control problem and incorporate the information on the sparsity of the unknown initial data into the structure of the objective functional. In particular, we are looking for the control variable in the space of regular Borel measures and use the corresponding norm as a regularization term in the objective functional. This leads to a convex but non-smooth optimization problem. For the discretization we use continuous piecewise linear finite elements in space and discontinuous Galerkin finite elements of arbitrary degree in time. For the general case we establish error estimates for the state variable. Under a certain structural assumption, we show that the control variable consists of a finite linear combination of Dirac measures. For this case we obtain error estimates for the locations of Dirac measures as well as for the corresponding coefficients. The key to the numerical analysis are the sharp smoothing type pointwise finite element error estimates for homogeneous parabolic problems, which are of independent interest. Moreover, we discuss an efficient algorithmic approach to the problem and show several numerical experiments illustrating our theoretical results. 

   more » « less