Ill-conditioning is a major challenge for optimization with first-order methods. This is especially the case for stochastic optimization, where the classical preconditioners - designed to compensate ill-conditioned curvatures - are hard to construct due to the inherent variability of stochastic gradients. Compounding this challenge, heavy-tailed noise further corrupts the reliability of gradient-based update directions. This thesis confronts these challenges through three algorithms. For deterministic non-convex problems, we analyze a subgradient method whose convergence rate is independent of the functional conditioning. In stochastic regimes, we derive a stochastic gradient method with block-coordinate stepsizes that effectively combat imbalanced gradients and inhomogeneous noise. Finally, we propose a statistically efficient data-driven method that adapts to the heavy-tail distribution of the noise. In Chapter 2, we analyze a preconditioned subgradient method for optimizing composite functions $h\circ c$, where $h$ is a locally Lipschitz function and $c$ is a smooth nonlinear mapping. We prove that when $c$ satisfies a constant rank property and $h$ is semismooth and sharp on the image of $c$, the method converges linearly. In contrast to standard subgradient methods, its oracle complexity is invariant under reparameterizations of $c$. In Chapter 3, we consider stochastic approximation methods with block-coordinate stepsizes and propose adaptive stepsize rules that aim to minimize the expected distance of the next iterate from an optimal point.These stepsize rules use online estimates of the mean and second moment of the search direction along each block coordinate. The popular Adam algorithm can be interpreted as using a particular heuristic for such estimation. By leveraging a simple conditional estimator, we derive variants that require fewer hyperparameters and optimizer states but obtain comparable performance. In addition, our convergence analysis relies on a simple aiming condition that is weaker than convexity, thus has broader applicability. In Chapter 4, we develop statistically efficient data-driven methods that can adapt to the heavy-tail distribution of the noise and obtain optimal performance. Our methods build upon the pioneering work of Polyak and Tsypkin in the 1980's, who developed a framework of nonlinear stochastic gradient methods where the stochastic gradients first go through a monotone nonlinear mapping, determined by the probability distribution of the noise, before being used to update the optimization variable. These methods are statistically efficient, in the sense that their asymptotic performance achieves the Cram'er-Rao lower bound. We extend the framework of Polyak and Tsypkin to the non-asymptotic regime, showing that the same nonlinear mapping obtains the optimal statistical performance with finite samples; in addition, we allow the nonlinear mapping to be non-monotone, thus can handle heavier-tail noises than Laplacian. Empirically, we identify families of heavy-tail distributions that not only give good approximations in practice but also admit simple nonlinear mappings and can be implemented efficiently. Chapter 5 documents future directions beyond the scope of this thesis.