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. More basis reduction for linear codes: backward reduction, BKZ, slide reduction, and more

   Ghentiyala, Surendra; Stephens-Davidowitz, Noah (August 2024, APPROX)

   We expand on recent exciting work of Debris-Alazard, Ducas, and van Woerden [Transactions on Information Theory, 2022], which introduced the notion of basis reduction for codes, in analogy with the extremely successful paradigm of basis reduction for lattices. We generalize DDvW's LLL algorithm and size-reduction algorithm from codes over F_2 to codes over F_q, and we further develop the theory of proper bases. We then show how to instantiate for codes the BKZ and slide-reduction algorithms, which are the two most important generalizations of the LLL algorithm for lattices. Perhaps most importantly, we show a new and very efficient basis-reduction algorithm for codes, called full backward reduction. This algorithm is quite specific to codes and seems to have no analogue in the lattice setting. We prove that this algorithm finds vectors as short as LLL does in the worst case (i.e., within the Griesmer bound) and does so in less time. We also provide both heuristic and empirical evidence that it outperforms LLL in practice, and we give a variant of the algorithm that provably outperforms LLL (in some sense) for random codes. Finally, we explore the promise and limitations of basis reduction for codes. In particular, we show upper and lower bounds on how ``good'' of a basis a code can have, and we show two additional illustrative algorithms that demonstrate some of the promise and the limitations of basis reduction for codes. 

   more » « less