More Like this

1. SGD and Hogwild! Convergence Without the Bounded Gradients Assumption

   Nguyen, Lam M.; Nguyen, Phuong Ha; Dijk, Marten van; Richtárik, Peter; Scheinberg, Katya; Takáč, Martin (January 2018, Proceedings of Machine Learning Research)

   Stochastic gradient descent (SGD) is the optimization algorithm of choice in many machine learning applications such as regularized empirical risk minimization and training deep neural networks. The classical analysis of convergence of SGD is carried out under the assumption that the norm of the stochastic gradient is uniformly bounded. While this might hold for some loss functions, it is always violated for cases where the objective function is strongly convex. In (Bottou et al.,2016) a new analysis of convergence of SGD is performed under the assumption that stochastic gradients are bounded with respect to the true gradient norm. Here we show that for stochastic problems arising in machine learning such bound always holds. Moreover, we propose an alternative convergence analysis of SGD with diminishing learning rate regime, which is results in more relaxed conditions that those in (Bottou et al.,2016). We then move on the asynchronous parallel setting, and prove convergence of the Hogwild! algorithm in the same regime, obtaining the first convergence results for this method in the case of diminished learning rate. 

   more » « less
2. Optimal Regularity for Hölder continuous Hamiltonian Stationary Lagrangian graphs

   Bhattacharya, A; Ogden, J W (October 2025, arXiv:2510.22756)

   In this paper, we establish optimal regularity for Hölder continuous Hamiltonian stationary Lagrangian graphs in $$\mathbb{C}^n$$. We prove that such a graph is smooth whenever its Hölder exponent is strictly larger than $$\frac{1}{3}$$ and the Lagrangian phase is supercritical, which yields semi-convexity of the potential. We establish the optimality of our result by constructing explicit singular solutions to the fourth order Hamiltonian stationary equation when the Hölder exponent of the graph is $$\frac{1}{3}$$. The singular solutions exist even under the strongest convexity assumption on the Lagrangian phase, namely the hypercritical phase, which enforces convexity of the potential. This presents a striking departure from the theory of special Lagrangian graphs. 

   more » « less
3. Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL

   Doron, Dean; Pyne, Ted; Tell, Roei (June 2024, 56th Annual ACM Symposium on Theory of Computing (STOC 2024))

   We provide compelling evidence for the potential of hardness-vs.-randomness approaches to make progress on the long-standing problem of derandomizing space-bounded computation. Our first contribution is a derandomization of bounded-space machines from hardness assumptions for classes of uniform deterministic algorithms, for which strong (but non-matching) lower bounds can be unconditionally proved. We prove one such result for showing that BPL=L “on average”, and another similar result for showing that BPSPACE[O(n)]=DSPACE[O(n)]. Next, we significantly improve the main results of prior works on hardness-vs.-randomness for logspace. As one of our results, we relax the assumptions needed for derandomization with minimal memory footprint (i.e., showing BPSPACE[S]⊆ DSPACE[c · S] for a small constant c), by completely eliminating a cryptographic assumption that was needed in prior work. A key contribution underlying all of our results is non-black-box use of the descriptions of space-bounded Turing machines, when proving hardness-to-randomness results. That is, the crucial point allowing us to prove our results is that we use properties that are specific to space-bounded machines. 

   more » « less
4. Effective medium theory for mechanical phase transitions of fiber networks

   https://doi.org/10.1039/d3sm00810j  

   Chen, Sihan; Markovich, Tomer; MacKintosh, Fred C (November 2023, Soft Matter)

   Networks of stiff fibers govern the elasticity of biological structures such as the extracellular matrix of collagen.These networks are known to stiffen nonlinearly under shear or extensional strain. Recently, it has been shown that such stiffening is governed by a strain-controlled athermal but critical phase transition, from a floppy phase below the critical strain to a rigid phase above the critical strain. While this phase transition has been extensively studied numerically and experimentally, a complete analytical theory for this transition remains elusive. Here, we present an effective medium theory (EMT) for this mechanical phase transition of fiber networks. We extend a previous EMT appropriate for linear elasticity to incorporate nonlinear effects via an anharmonic Hamiltonian. The mean-field predictions of this theory, including the critical exponents, scaling relations and non-affine fluctuations qualitatively agree with previous experimental and numerical results. 

   more » « less
5. Towards Robust and Reliable Recourse

   Upadhyay, Sohini; Joshi, Shalmali; Lakkaraju, Himabindu (December 2021, Advances in neural information processing systems)

   As predictive models are increasingly being deployed in high-stakes decision making (e.g., loan approvals), there has been growing interest in post-hoc techniques which provide recourse to affected individuals. These techniques generate recourses under the assumption that the underlying predictive model does not change. However, in practice, models are often regularly updated for a variety of reasons (e.g., dataset shifts), thereby rendering previously prescribed recourses ineffective. To address this problem, we propose a novel framework, RObust Algorithmic Recourse (ROAR), that leverages adversarial training for finding recourses that are robust to model shifts. To the best of our knowledge, this work proposes the first ever solution to this critical problem. We also carry out theoretical analysis which underscores the importance of constructing recourses that are robust to model shifts: 1) We quantify the probability of invalidation for recourses generated without accounting for model shifts. 2) We prove that the additional cost incurred due to the robust recourses output by our framework is bounded. Experimental evaluation on multiple synthetic and real-world datasets demonstrates the efficacy of the proposed framework. 

   more » « less